Re: [go-nuts] Efficient bitmask twiddling

2020-09-02 Thread Aleksey Tulinov
https://godbolt.org/z/6n7G8q

I'm actually not sure how good this assembly is, it would be
interesting to hear from you, but it looks promising.

вт, 1 сент. 2020 г. в 22:54, Oliver Smith :
>
> In the process of developing a piece of middleware, I need to translate from 
> a bit-array into a bitmask. I am struggling to find a way to express this in 
> go that doesn't result in terrible performance.
>
> The approaches I would try in most other languages were along the lines of:
>
> ```
> mask = (bool1 << bitno1) | (bool2 << bitno2);
> // or
> mask = (bool1 ? value1 : 0) | (bool2 ? value2 : 0);
> ```
>
> but instead, after reading several old (circa 1.5) posts, I'd landed at
>
> ```
> func maskIfTrue(mask uint, predicate bool) uint {
>   if predicate {
> return mask
>   }
>   return 0
> }
>
> mask = maskIfTrue(mask1, bool1) | maskIfTrue(mask2, bool2)
> ```
>
> Here is a (boiled-down & reduced) comparison of the go implementation vs a 
> simple C implementation compiled with -O0 and -Os:
>
> The go version is branch-crazy.
>
> Is there some way I can write this that will produce simpler/efficient code 
> and also not be code salad? I don't have control over the relative ordering 
> of the bools or the bitfield values, and this is a hot path?
>
> Go branchiness:
> ```
> nop
> cmpb1(AX), $0
> jeq featToMask_pc94
> movl$2, DX
> featToMask_pc19:
> nop
> cmpb2(AX), $0
> jeq featToMask_pc90
> movl$4, BX
> featToMask_pc30:
> nop
> ```
>
> The "FeatToMask" C transliteration when compiled with optimization *disabled* 
> (-O0) looks similar, but even -O1 fixes that:
> ```
> FeatToMask:
> mov eax, edi
> movzx   eax, ah
> mov esi, edi
> shr esi, 16
> mov ecx, edi
> shr ecx, 24
> mov rdx, rdi
> shr rdx, 32
> shr rdi, 40
> or  eax, esi
> or  eax, ecx
> or  eax, edx
> or  eax, edi
> movzx   eax, al
> ret
> ```
>
> and with -Os you get down to something better than the naive-C-implementation 
> at the top of the source
>
> ```
> FeatToMask:
> mov QWORD PTR [rsp-8], rdi
> mov al, BYTE PTR [rsp-7]
> or  al, BYTE PTR [rsp-6]
> or  al, BYTE PTR [rsp-5]
> or  eax, DWORD PTR [rsp-4]
> or  al, BYTE PTR [rsp-3]
> movzx   eax, al
> ret
> ```
>
> --
> You received this message because you are subscribed to the Google Groups 
> "golang-nuts" group.
> To unsubscribe from this group and stop receiving emails from it, send an 
> email to golang-nuts+unsubscr...@googlegroups.com.
> To view this discussion on the web visit 
> https://groups.google.com/d/msgid/golang-nuts/ea364cef-3998-469c-8742-3bc794733535n%40googlegroups.com.

-- 
You received this message because you are subscribed to the Google Groups 
"golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to golang-nuts+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/golang-nuts/CAMteYTaMuRmdq0%3DGiGXJ%3DYVP%2BcamdCssGwSxAcAubY4T0DOMiw%40mail.gmail.com.


Re: [go-nuts] A question about copying

2020-07-25 Thread Aleksey Tulinov
You are probably thinking about code like this:

var f2 = *f1

Which will make a copy, although not because `f1` is dereferenced, but
because `=` was called on a value.

Dereferencing a pointer gives a reference to the same value, taking
address of the same value will produce a pointer to the same value. So
in expression like this:

var f2 = &(*f1)

`&` and `*` cancel each other out and it can be simplified to:

var f2 = f1

Which means "make a copy of pointer". If you take the address of `f1`
and `f2` you'll see that those are indeed different pointers.

If you're thinking about something like `f(*f1)`, then I believe the
function call will make a copy because arguments are passed by values.
`f(f1)` will make a copy too, but a copy of pointer.

Does that make sense?

сб, 25 июл. 2020 г. в 11:09, chri...@surlykke.dk :
>
> When running this program:
>
> package main
>
> import (
> "fmt"
> )
>
> type Foo struct {
> i int
> }
>
> func main() {
> var f1 = {i: 0}
> var f2 = &(*f1)
> f2.i = 1
> fmt.Println(f1, f2)
> }
>
> it yields:
>
> &{1} &{1}
>
> (https://play.golang.org/p/qKtURokUCEW)
>
> I (naively) assumed that the expression
>
> &(*f1)
>
> would, first, create a copy of *f1, and then a pointer to that copy, but 
> evidently f2 becomes a pointer to the same struct as f1. Is this something I 
> should have deduced from the language spec?
>
> best regards Christian Surlykke
>
>
> --
> You received this message because you are subscribed to the Google Groups 
> "golang-nuts" group.
> To unsubscribe from this group and stop receiving emails from it, send an 
> email to golang-nuts+unsubscr...@googlegroups.com.
> To view this discussion on the web visit 
> https://groups.google.com/d/msgid/golang-nuts/f427ddf6-f4fc-42f4-bee8-d1dab0fef566n%40googlegroups.com.

-- 
You received this message because you are subscribed to the Google Groups 
"golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to golang-nuts+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/golang-nuts/CAMteYTa2Qx1Dc0x%2B1iaNi98m6jCKuru2qgBFiHF%3Dik6D65SbMA%40mail.gmail.com.


Re: [go-nuts] [Generics] Feedback on updated draft

2020-07-23 Thread Aleksey Tulinov
Ian,

First of all, thank you for taking your time to answer this topic. I
know some stuff i say is dumb, i appreciate your patience.

To answer your question: i would assume that OR is about as useful as
AND or NOT.

type Constraint interface {
   Sequence && !Channel
}

With that said. So far i'm only a theorist and you are probably the
best expert in this field, so I would rather listen to what you have
to say than express my own ideas, even though they are not really my
own and credit has to go to other people.

I get it, there is a scope for generics and you are asking this
question because there are other considerations about the scope,
usefulness, timeline and this is a problem with more than one factor
and all factors have to be considered. I hope generics version 1 will
be received very well, and I'm actually sure they will.

I absolutely trust your judgement on this matter, of course I don't
have practical experience with generics in Go, but I saw something
that I didn't like. I'll let someone who applied generics in the field
to provide practical feedback and I will be glad to hear that they are
amazing. Sorry for wasting your time. This is undoubtedly an
improvement to the language and it is very needed. Good luck.

>I've tried to outline what we need from generics in
https://blog.golang.org/why-generics.

Right. I must have read this too, but probably a year ago and forgot
about it. This all makes sense now. Thank you very much.

чт, 23 июл. 2020 г. в 09:16, Ian Lance Taylor :
>
> On Wed, Jul 22, 2020 at 9:41 PM Aleksey Tulinov
>  wrote:
> >
> > This is Java-style inheritance. It isn't bad, but i think that
> > C++-style composition is somehow more in the spirit of Go. Strictly
> > personal opinion of course. Older proposal described constraints as
> > expressions, so to me it appears superior because I could potentially
> > write an expression I want without asking for more features to be
> > added into the compiler.
> >
> > Although i'm no longer sure if I understand what Go generics are
> > supposed to do. You have the point that it's probably for a specific
> > purpose, generic types something something, i don't know, but it
> > probably isn't supposed to do what C++ concepts can do. Maybe i'm just
> > spoiled.
> >
> > If this gets us to where we want to be - that's great, I'm happy if
> > you're happy. It just doesn't feel quite right and i feel like this
> > proposal could benefit from discussion on composition and stuff like
> > that.
>
> There is no question that the older syntax was more powerful.  And I
> suspect that your syntax is also more powerful.  But we got extensive
> feedback that the approach was too complex.  C++ and Go have very
> different tolerances for complexity.
>
> You raised the possibility of a constraint that permits either
> constraintA or constraintB.  I think that supporting that kind of
> constraint would be more powerful than what the current design draft
> provides.  But is it a necessary feature?  How often does one want to
> use such a constraint?
>
> I've tried to outline what we need from generics in
> https://blog.golang.org/why-generics.  I think that that describes the
> minimum set of required features for a viable language change.  The
> possibility of alternative constraints is not in that set.  Supporting
> everything we can think of is not a goal.  It's not an inherently bad
> thing.  But anything more powerful than the minimum set has to not
> make the language more complicated to understand.
>
> Within that context, I think it's a great idea to discuss composition
> or inheritance.  If we can come up with something that is more
> powerful and less complex, that would be great.
>
> Ian

-- 
You received this message because you are subscribed to the Google Groups 
"golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to golang-nuts+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/golang-nuts/CAMteYTYWvtfkRo13dfE1XJyWkwK1EKfKRuQP-22dkLbObpMUwg%40mail.gmail.com.


Re: [go-nuts] [Generics] Feedback on updated draft

2020-07-22 Thread Aleksey Tulinov
I'm not sure if i understood everything correctly.

type structField(type T) struct {
a int
x T
}

But this is a generic type, not a constraint for a type, isn't it?
Constraint is this:

type Custom interface{
type int, float64, uint64
}

type structField(type T Custom) interface {
  type struct { a int; x T },
struct { b int; x T },
struct { c int; x T }
}

What am I missing? And I think it rather well highlights what I am
talking about. Consider the following pseudocode:

type ConstraintIWant interface {
  ConstraintA || ConstraintB // i don't care which one, either is fine
}

Maybe i'm looking in the wrong place, but i think that to do this I
have to extract `CommonPart` (`Custom`) from `ConstraintA` and
`ConstraintB`, add `CommonPart` back to both constraints so they
aren't broken and then request `CommonPart` in `ConstraintIWant`.

This is Java-style inheritance. It isn't bad, but i think that
C++-style composition is somehow more in the spirit of Go. Strictly
personal opinion of course. Older proposal described constraints as
expressions, so to me it appears superior because I could potentially
write an expression I want without asking for more features to be
added into the compiler.

Although i'm no longer sure if I understand what Go generics are
supposed to do. You have the point that it's probably for a specific
purpose, generic types something something, i don't know, but it
probably isn't supposed to do what C++ concepts can do. Maybe i'm just
spoiled.

If this gets us to where we want to be - that's great, I'm happy if
you're happy. It just doesn't feel quite right and i feel like this
proposal could benefit from discussion on composition and stuff like
that.

чт, 23 июл. 2020 г. в 06:29, :
>
> Hey! I would like to join the discussion and add my 5 cents here, since I 
> have been criticizing the contracts draft and I would like to show what were 
> my points in order to support the current design draft.
>
>
> I believe the original problem for the generics is to allow the same function 
> to work on values of different types. So that You do not need to write 
> something like AddInt, AddInt32, AddInt64 and so on. This is an example of 
> situation when we would like to write something like Add(T) and make that T 
> to be one of the list: int, int32, int64 - all of the types what we have the 
> Add function defined for.
>
>
> In this case Add(T) acts much like an expression evaluating to a different 
> function depending on the T.
>
>
> This can be called “parametrization by type” or “type parametrization” and I 
> believe it is an exceptionally simple and straightforward way to do it.
>
>
> Let me say a bit more about problems where need of contracts arise.
>
>
> When we are writing in a context of type-parametrized function something like:
>
>
> var a []T = []int{1, 2, 4}
> a[2] = 3
>
>
> It is okay to write []T[2] = T (assign a value of type T to an element of 
> array of type T by index 2) and we do not need to care what is T.
>
>
> But when we change a bit:
>
>
> var a T = []int{1, 2, 4}
> a[2] = 3
>
>
> It becomes hard to judge whether we are allowed to write T[2] = 3 (assign 3 
> to an element of type T by index 2). In order it to work, we need to state 
> somehow [2] is allowed for T. There are a few ways to achieve it and the 
> first one is the contracts:
>
>
> type T interface{
> require(a, b) {
> a[2] = b
> }
> }
>
>
> Okay, now, let’s say, we are allowed to write T[2] = 3. But let’s try a 
> harder example
>
>
> var a T = []int{1, 2, 4}
> a[2] = 3
> a = append(a, 4)
>
>
> This will not work with the previously defined contract T, since a 
> map[int]int value also fits it.
>
>
> Should we write something like this:
>
>
> type T interface{
> require(a, b) {
> a[2] = b
> a = append(a, b)
> }
> }
>
>
> But what is the point in such syntax? How the compiler could guess and how 
> exactly it should work? What if we write random garbage in the require body, 
> will it allow us to write it right in the code without any checks?
>
>
> type T interface{
> require(a, b) {
> a *@#&@#$= b
> }
> }
>
> var a T *@#&@#$= b
>
>
> Of course, we can restrict it to allow using only operators like [], == and 
> so on, still how can we distinguish between a map and an array?
>
>
> type T interface{
> require(a, b, i) {
> a[:] // only arrays and slices have this operator
> i++ // i is an integer
> a[i] = b // b is an element of array a
> }
> }
>
>
> Is this enough to define what we want? Such a contract would also require the 
> append builtin to be changed, but I believe it will only clutter up the 
> implementation with unnecessary type assertions.
>
>
> These “requires” act very much like predicates and are just tricky way to 
> “shortly” define a list of types. That is to say, a++ means any type having a 
> ++ operator defined for it no matter how exactly (which is a problem itself). 
> Anyway, 

Re: [go-nuts] [Generics] Feedback on updated draft

2020-07-22 Thread Aleksey Tulinov
Hmm. I must have read the previous version, but it probably was some
time ago. I have to say that i like the previous version more than the
current one.

I definitely don't like this:

type structField interface {
  type struct { a int; x int },
struct { b int; x float64 },
struct { c int; x uint64 }
}

If this is more readable than `require (a) { a.x++ }`, then i don't
even know what to say. My understanding of readability must be very
different.

I admit that there is a point in those concerns too, it's not
immediately obvious what `require (a) { a.x++ }` is supposed to do.

However the real point is not in a syntax, but in decoupling require
expression from constraint, so it's more generic and extensibleso to
speak. So maybe:

type IncrementX interface {
  require (a) {
evaluates(a.x) && evaluates(a.x++)
   // where evaluates() is defined elsewhere like `require (x) { x }`
  }
}

And type requirement could be `require { type int, int8, int16, int32,
int64 }`? Even though this still doesn't look right to me.

>The objection you mention to the approach used in the current draft is 
>something like: what if Go changes such that operators (other than == and !=) 
>apply to types other than primitive types?  But we're in charge of Go;

Yeah, sure. But there will be some code out there that depends on
existing constraints. If I understand this correctly, `Ordered` in the
current proposal does not define constraint that require operator `<`,
it defines a specific set of types and exploits a side effect that
operator '<' can be applied to every type from this set. This
introduces other side effects, for example, operator `==` is also
defined for all those types, so at least it defines what it wasn't
supposed to define.

I'm not sure if this is OK or not, just saying, but if Go somehow
changes "interface" of types under `Ordered`, then I think `Ordered`
will indirectly change its meaning because it will inherit those
changes even if they are unrelated to operator `<` or ordering in
general. Just wanted to point out that side effects work both ways,
and if those side effects are already exploited in existing Go code,
then it might be harder to change other parts that at first sight are
completely unrelated to what is being changed. Hope this helps.

But I dig the idea of releasing this in parts, i'll be keeping track
of this, this is a much needed feature. Thank you for looking into
this.

чт, 23 июл. 2020 г. в 00:21, Ian Lance Taylor :
>
> On Wed, Jul 22, 2020 at 1:46 PM Aleksey Tulinov
>  wrote:
> >
> > I'm not really a language designer and i don't use Go extensively, so
> > please take my words with a grain of salt. But I like Go and would
> > like to use it, and I'd like to put my 2 cents into the jar. I'm sorry
> > if this was already discussed, I checked the mailing list but didn't
> > find this.
> >
> > I've read the updated draft (sorry i'm late) and the thing that really
> > rubbed me the wrong way was this one:
> >
> > "We need a way to write a constraint that accepts only types that
> > support <. In order to do that, we observe that, aside from two
> > exceptions that we will discuss later, all the arithmetic, comparison,
> > and logical operators defined by the language may only be used with
> > types that are predeclared by the language, or with defined types
> > whose underlying type is one of those predeclared types. That is, the
> > operator < can only be used with a predeclared type such as int or
> > float64, or a defined type whose underlying type is one of those
> > types. Go does not permit using < with a composite type or with an
> > arbitrary defined type."
> >
> > This is a good observation, but what if Go changes in the future and
> > this observation is no longer true?
> >
> > I think I somewhat understand the underlying problem, interface is a
> > concept from the Java world and in Java "everything is object", and
> > classic interface is limited to describing methods, etc etc. But
> > interface is a form of constraint, so it does make a lot of sense to
> > use it as a constraint for generic types. However, I thought that
> > intention was to describe a constraint on objects composition, but
> > instead it describes constraints on object types. This doesn't feel
> > quite right.
> >
> > "If C++ and Java are about type hierarchies and the taxonomy of types,
> > Go is about composition." Am i right?
> >
> > Was it considered to decouple constraints into 1) constraints and 2)
> > constraints requirement expression? Something like this (here and
> > below everything is pseudocode):
> >
> > type comparable interface {
> >   require (a, b) {

[go-nuts] [Generics] Feedback on updated draft

2020-07-22 Thread Aleksey Tulinov
Hi,

I'm not really a language designer and i don't use Go extensively, so
please take my words with a grain of salt. But I like Go and would
like to use it, and I'd like to put my 2 cents into the jar. I'm sorry
if this was already discussed, I checked the mailing list but didn't
find this.

I've read the updated draft (sorry i'm late) and the thing that really
rubbed me the wrong way was this one:

"We need a way to write a constraint that accepts only types that
support <. In order to do that, we observe that, aside from two
exceptions that we will discuss later, all the arithmetic, comparison,
and logical operators defined by the language may only be used with
types that are predeclared by the language, or with defined types
whose underlying type is one of those predeclared types. That is, the
operator < can only be used with a predeclared type such as int or
float64, or a defined type whose underlying type is one of those
types. Go does not permit using < with a composite type or with an
arbitrary defined type."

This is a good observation, but what if Go changes in the future and
this observation is no longer true?

I think I somewhat understand the underlying problem, interface is a
concept from the Java world and in Java "everything is object", and
classic interface is limited to describing methods, etc etc. But
interface is a form of constraint, so it does make a lot of sense to
use it as a constraint for generic types. However, I thought that
intention was to describe a constraint on objects composition, but
instead it describes constraints on object types. This doesn't feel
quite right.

"If C++ and Java are about type hierarchies and the taxonomy of types,
Go is about composition." Am i right?

Was it considered to decouple constraints into 1) constraints and 2)
constraints requirement expression? Something like this (here and
below everything is pseudocode):

type comparable interface {
  require (a, b) {
a < b
  }
}

When constraint is checked, this requirement can be rewritten as a
function for a concrete type, for example, for interface{}:

func comparableRequireInterface(a, b interface{}) {
  _ = (a < b) // this won't compile, as expected, there is no operator
<, requirement isn't satisfied
}

For struct{}:

func comparableRequireStruct(a, b struct{}) {
  _ = (a < b) // this won't compile either
}

For numeric types, specifically for int:

func comparableRequireInt(a, b int) {
  _ = (a < b) // this will compile for other numeric types too
}

Playground link: https://play.golang.org/p/vzk6l7zvBY_J

Note that `require (a, b) { a == b }` will be satisfied for structs,
interfaces, numerics and strings.

This may (or may not) eliminate the need for predeclared `comparable`
constraint and it might (or might not) answer this: "It's not clear
that we fully understand the use of composite types in type lists":

type IncrementX interface {
  require (a) {
a.x++
  }
}

Which can be rewritten for a concrete type:

type ConcreteStruct struct {
  x float64
}

As

func checkIncrementXConcreteStruct(a ConcreteStruct) {
  a.x++ // note that it can not be rewritten to _ = (a.x++)
}

With empty `struct{}` it will give a sensible error message:
"./prog.go:28:3: a.x undefined (type struct {} has no field or method
x)" and it will detect error when ++ can not be applied:
"./prog.go:24:5: invalid operation: a.x++ (non-numeric type string)"

Does any of this make any sense?

P.S. Yeah, it looks like C++, full disclosure, this is why I'm writing
this email, I thought maybe Go could borrow something from there. I
believe GCC 10+ can compile C++ concepts and there is a "playground"
available at godbolt.org.

-- 
You received this message because you are subscribed to the Google Groups 
"golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to golang-nuts+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/golang-nuts/CAMteYTbyeYKV55dLja%2BYqtGELA_4vh%3DnsvJRuaa6RUoTZ_Nx_A%40mail.gmail.com.