Relaxing rules on slice comparison: would it make sense?

[Chad]

Just been thinking that since a slice is a "reference" type, why not allow slice equality?

Of course the number of cases where two slices are equal would be quite low, irrelevant of whether the view they have on their respective arrays is the same.

I'm thinking about something analogous to comparing pointer values. No notion of deep equality as can be done via reflect.

[Chad]

And actually the same for any other similar types such as maps...

[Konstantin Khomoutov]

What would be the use cases?

[Chad]

So that it becomes valid map inputs.

What should be hashed would be the slice/map/ref type value.

[Dan Kortschak]

*(*uintptr)(unsafe.Pointer(&a)) == *(*uintptr)(unsafe.Pointer(&b)) for
maps

*(*reflect.SliceHeader)(unsafe.Pointer(&a) ==
*(*reflect.SliceHeader)(unsafe.Pointer(&b) for slices.

Neither are wildly useful for most cases (we use the map case for some
fast path comparisons of maps).

[Ian Lance Taylor]

The problem is that different programs need different things for slice
equality. Some want pointer equality as you suggest. Some want
element comparisons, as is done for array equality. Without an
obvious semantics for the operation, the language omits it entirely.

To store slices in maps using pointer equality, you could perhaps
store a pointer to the slice instead.

Ian

[Viktor Kojouharov]

This would probably introduce unnecessary confusion. People are used to the equality operator comparing values in go, as opposed to references. It's much better if the slices finally support the equality operator, even though the comparison speed will depend on the number of items in the slices.

[Chad]

The problem is that different programs need different things for slice
equality.  Some want pointer equality as you suggest.  Some want
element comparisons, as is done for array equality.  Without an
obvious semantics for the operation, the language omits it entirely.

That's true. However, the flipside of the coin is that perfectly marshallable objects cannot be used as map keys because at least one field is a slice, map or function.

That restricts the usage of maps sometimes unnecessarily.

If the equality operator were to have the same semantic everywhere (mere value comparison, whether for a pointer, map/slice/func or an array), it would solve the issue.

The spec would not even have to rely on the internal structure of a slice, map or function.

[Chad]

On Thursday, June 30, 2016 at 8:32:58 AM UTC+2, Viktor Kojouharov wrote:

This would probably introduce unnecessary confusion. People are used to the equality operator comparing values in go, as opposed to references. It's much better if the slices finally support the equality operator, even though the comparison speed will depend on the number of items in the slices.

Well, in fact, everything is a value in Go. It's just that  the internal structure of the standard reference types are not exposed.

The behaviour should not be very different from the comparison between user defined structs where one or more fields are pointers.

It also makes sense to say that two slices are equal iff they represent the exact same views of the exact same underlying array.

 

[Paul Borman]

It would be very surprising to people to use a slice as a key to map, say []int{1,2} and then find that using another []int{1,2} does not find that entry.  While I think it would be nice to have == on slices, I must agree with Ian and authors that it is better left unsaid.

    -Paul

--
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...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Chad]

It's a view in another array.

Why should they be equal? Unless the second slice is constructed by subslicing the other as such `[:]`, the slices are different.

If I were to access one of the slice backing array and mutate it, I wouldn't expect the slices to be equal anymore.

The argument that it would be surprising is perhaps flawed because it stems from a misconception.

A slice is a dynamic view. For two slices to be equal it makes sense to be looking at the same thing at all time.

Taken mathematically, if we describe an indirection as a mathematical function, a slice is such a function. Two functions are equals if they are equals everywhere they are defined. A slice is equal to another slice if the backign arrays always have the same values, whatever mutation occurs on any of them.

Comparing the snapshot view of a slice would then different. The behaviour seems consistent to me.

[Ian Lance Taylor]

On Thu, Jun 30, 2016 at 9:24 AM, Chad <send...@gmail.com> wrote:
> It's a view in another array.
> Why should they be equal? Unless the second slice is constructed by
> subslicing the other as such `[:]`, the slices are different.
>
> If I were to access one of the slice backing array and mutate it, I wouldn't
> expect the slices to be equal anymore.
>
> The argument that it would be surprising is perhaps flawed because it stems
> from a misconception.
> A slice is a dynamic view. For two slices to be equal it makes sense to be
> looking at the same thing at all time.
>
> Taken mathematically, if we describe an indirection as a mathematical
> function, a slice is such a function. Two functions are equals if they are
> equals everywhere they are defined. A slice is equal to another slice if the
> backign arrays always have the same values, whatever mutation occurs on any
> of them.
>
> Comparing the snapshot view of a slice would then different. The behaviour
> seems consistent to me.

This discussion is a good example of why the language does not define
the behavior. There are solid arguments on both sides.

Ian

[Chad]

I understand the worry but the more I think about it, the less I think it would end up being a real issue.

Taking the example of maps... two different maps that have not the same location in memory are never equal, especially since modifying one does not modify the other. It's easily explained.

For slices, explaining that it's a view of an array, and views of different arrays are not considered equals, it would also be easily explained to a beginning programmer.

Well it's merely food for thoughts. (but it would solve later issues in the usability of maps)

[Konstantin Khomoutov]

On Thu, 30 Jun 2016 09:55:30 -0700 (PDT)
Chad <send...@gmail.com> wrote:

> I understand the worry but the more I think about it, the less I
> think it would end up being a real issue.
>
> Taking the example of maps... two different maps that have not the
> same location in memory are never equal, especially since modifying
> one does not modify the other. It's easily explained.
>
> For slices, explaining that it's a view of an array, and views of
> different arrays are not considered equals, it would also be easily
> explained to a beginning programmer.
>
> Well it's merely food for thoughts. (but it would solve later issues
> in the usability of maps)

I think you can get away using helper functions.

Say, having

type SliceKey struct {
Ptr unitptr
}

func Key(s []byte) SliceKey
{
...
}

which would calculate whatever suits your needs from its parameter,
you could use it to actually turn your slices and maps into proper keys.

Such a function can just use package unsafe to crack the slice header
value in whatever way it wishes (as in the piece of advice from Daniel
Skinner earlier in this thread).

Working with a map would then look something like

m := make(map[SliceKey]int)

b := []byte{1, 2, 3}

m[Key(b)] = 42

v := m[Key(b)]

[Chad]

In fact I'd rather deal with the general issue by relaxing some rules, if it's something that is deemed worthy of being dealt with.

Basically if you have a map[interface{}]interface{} because you have a mixed bag of value that you fill at runtime, you cannot actually use any type you want as the key.

Semantically, there is an additional constraint that I don't believe should exist.

And it's on any type that has one or more fields of type slice/map/ or func.

The alternative is to implement one's own associative array datastructure with one's own hashing algorithm etc but that's still going to be clunky since it will be implementation dependent and will rely on the use of unsafe.

[Konstantin Khomoutov]

On Thu, 30 Jun 2016 11:57:38 -0700 (PDT)
Chad <send...@gmail.com> wrote:

> In fact I'd rather deal with the general issue by relaxing some
> rules, if it's something that is deemed worthy of being dealt with.

I think this part of the discussion can be safely closed: since no one
is able to specify the semantics for comparing arbitrary slice and map
values which would be overwhelmingly better (more logical etc) that the
others, the situation is unlikely to change IMO.

> Basically if you have a map[interface{}]interface{} because you have
> a mixed bag of value that you fill at runtime, you cannot actually
> use any type you want as the key.

> Semantically, there is an additional constraint that I don't believe
> should exist.

Your proposition merely moves the semantical constraint to another
place: as Ian pointed out, if we define equality for slices to be
something resembling pointer equality suddenly []byte{1, 2} is not equal
to []byte{1, 2}.

The approach I have proposed (a custom "keying" function) is actually
what "every other language" does, just more explicit. Say, .NET's
collections rely on their members implementing various interfaces such
as IHashCodeProvider. My "keying" function merely provides a mapping
from values which cannot be used as keys directly to some other values
which can -- using your own rules. Since your rules would be codified
explicitly, there would be no cognitive burden for the next programmer
reading your code.

> And it's on any type that has one or more fields of type slice/map/
> or func.
>
> The alternative is to implement one's own associative array
> datastructure with one's own hashing algorithm etc but that's still
> going to be clunky since it will be implementation dependent and will
> rely on the use of unsafe.

I propose putting such "hashing algorithm" outside of the datastructure.

Basically what I propose is replacing

collection(K → V)

with

collection(K' → V)

where K' is derived from K using your own function: K' = fn(K).

The collection stays unmodified, you just transform its keys.

[Chad]

Your proposition merely moves the semantical constraint to another
place: as Ian pointed out, if we define equality for slices to be
something resembling pointer equality suddenly []byte{1, 2} is not equal
to []byte{1, 2}.

They are not since creating a slice allocate a different underlying array each time. They are not views on the same array.

It is merely incidental that on the example that is given, the two arrays have the same first and second elements. 

As discussed above, there is no semantic problem that has really been pointed out. 

It's a mere comparison of the slice header, a mere value comparison. Just as what would be done for any other type.

 

The approach I have proposed (a custom "keying" function) is actually
what "every other language" does, just more explicit.  Say, .NET's
collections rely on their members implementing various interfaces such
as IHashCodeProvider.  My "keying" function merely provides a mapping
from values which cannot be used as keys directly to some other values
which can -- using your own rules.  Since your rules would be codified
explicitly, there would be no cognitive burden for the next programmer
reading your code.

> And it's on any type that has one or more fields of type slice/map/
> or func.
>
> The alternative is to implement one's own associative array
> datastructure with one's own hashing algorithm etc but that's still
> going to be clunky since it will be implementation dependent and will
> rely on the use of unsafe.

I propose putting such "hashing algorithm" outside of the datastructure.

Basically what I propose is replacing

  collection(K → V)

with

  collection(K' → V)

where K' is derived from K using your own function: K' = fn(K).

The collection stays unmodified, you just transform its keys.

There is no real need for another indirection in Go. It's really straightforward.

[Jakob Borg]

2016-06-30 22:23 GMT+02:00 Chad <send...@gmail.com>:
>> Your proposition merely moves the semantical constraint to another
>> place: as Ian pointed out, if we define equality for slices to be
>> something resembling pointer equality suddenly []byte{1, 2} is not equal
>> to []byte{1, 2}.
>
>
> They are not since creating a slice allocate a different underlying array
> each time. They are not views on the same array.
> It is merely incidental that on the example that is given, the two arrays
> have the same first and second elements.

This may seem entirely obvious to you, but explaining to a newcomer why

fmt.Println(1 == 1) // => true
fmt.Println("2" == "2") // => true
fmt.Println([...]int{1, 2} == [...]int{1, 2}) // => true
fmt.Println([]int{1, 2} == []int{1, 2}) // => false

is not something I feel would make the language better.

//jb

[Chad]

I'd rather people were given a correct simple explanation rather than foregoing any explanation because it may appear complex at first sight.

Especially since it alters how maps can be used, later on. (the hashing algorithm relies on comparability).

One way to go about this would be to put more emphasis on the concept of reference type in the documentation and introduce this behaviour as the main divergence from pure value types. But that wouldn't be the most complex thing to learn.

[Dan Kortschak]

This position precludes the following use of the equality operator for
scalar values:

a := 1
b := 1

a == b would be false under the approach below since a and b are not the
same set of bits.

I think most people would find this a little surprising.

On Thu, 2016-06-30 at 09:24 -0700, Chad wrote:
> It's a view in another array.
> Why should they be equal? Unless the second slice is constructed by

> subslicing the other as such `[:]`, the slices *are* different.

[Chad]

No, it's actually fine. You are comparing values.

A slice being a struct under the hood, for slices you would compare the structs (slice headers)

For an interface, you compare two pointers (in the current implementation)

etc.

"==" is just value comparison everywhere.

Everything is a value. 

[Dan Kortschak]

On Thu, 2016-06-30 at 18:15 -0700, Chad wrote:
> No, it's actually fine. You are comparing values.

The issue is that, yes while everything is a value, the value
abstraction is tenuous in this context. The result of this tenuous
abstraction is that there would be surprising behaviours (already
outlined by others).

> A slice being a struct under the hood, for slices you would compare
> the structs (slice headers)
>
> For an interface, you compare two pointers (in the current
> implementation)
>
> etc.
>
> "==" is just value comparison everywhere.
>
> Everything is a value.

Some of the values are not specified in the language specification.
Making this equality comparison possible for all types would require
that these be specified, locking in the current implementation.

This would be to get behaviour that is already available either by
indirection or import of unsafe.

[Chad]

Again, if you really understand the datastructure and what it represents, the behaviour is really not surprising. There is no value "abstraction".

And currently, a comparison panics. Any interface comparison may panic if the underlying type is a slice. I don't see a good reason for that.

That's why I have mentioned "relaxing".

I also don't see why someone would need to import unsafe for this, leaving alone the fact that some hosting solutions may not allow the import of this package.

[Dan Kortschak]

On Thu, 2016-06-30 at 18:48 -0700, Chad wrote:
> Again, if you really understand the datastructure and what it
> represents, the behaviour is really not surprising. There is no value
> "abstraction".

CS and software engineering is abstractions all the way down.

>
> And currently, a comparison panics. Any interface comparison may panic
> if the underlying type is a slice. I don't see a good reason for that.
> That's why I have mentioned "relaxing".

The relaxation requires a tightening elsewhere.

> I also don't see why someone would need to import unsafe for this,
> leaving alone the fact that some hosting solutions may not allow the
> import of this package.

You don't have to, you can use a pointer indirection instead.

[Chad]

You don't have to, you can use a pointer indirection instead.

I have explained why it was not sufficient upstream.

I don't expect people to create two version of their types, one being for mere inclusion into maps.

[Dan Kortschak]

On Thu, 2016-06-30 at 19:10 -0700, Chad wrote:
> I have explained why it was not sufficient upstream.
> I don't expect people to create two version of their types, one being
> for mere inclusion into maps.
>

Not really; you've said it's not necessary and you've pointed to
map[interface{}]interface{} which could possibly lead in the direction
you you are suggesting (or not).

[Martin Geisler]

On Fri, Jul 1, 2016 at 3:15 AM, Chad <send...@gmail.com> wrote:
> No, it's actually fine. You are comparing values.
>
> A slice being a struct under the hood, for slices you would compare the
> structs (slice headers)

Yes, when you remember that a slice is a just a small struct with a
pointer and some bookkeeping information (length, capacity), then you
can compare two slices easily. So with

a := []int{10, 20, 30}
b := a[:]

then a == b would be fast: simply compare the pointers and the
bookkeeping information. Direct value equality between the structs
gives you the expected and correct answer.

But what about

[]int{10, 20} == []int{10, 20}

where the two slices refer to different underlying arrays? I think you
argue that this comparison should be false?

I would hope that slices from different underlying arrays could be
compared for equality based on their values, just like strings can.
Two strings (that are not slices from the same original string) can be
compared for equality just fine. I hope Go takes the shortcut when the
strings refer to the same memory and otherwise does the slower
per-byte comparison. The same could perhaps apply to slices in
general.

--
Martin Geisler

[Chad]

On Friday, July 1, 2016 at 12:11:43 PM UTC+2, Martin Geisler wrote:

On Fri, Jul 1, 2016 at 3:15 AM, Chad <send...@gmail.com> wrote:
> No, it's actually fine. You are comparing values.
>
> A slice being a struct under the hood, for slices you would compare the
> structs (slice headers)

Yes, when you remember that a slice is a just a small struct with a
pointer and some bookkeeping information (length, capacity), then you
can compare two slices easily. So with

  a := []int{10, 20, 30}
  b := a[:]

then a == b would be fast: simply compare the pointers and the
bookkeeping information. Direct value equality between the structs
gives you the expected and correct answer.

But what about

  []int{10, 20} == []int{10, 20}

where the two slices refer to different underlying arrays? I think you
argue that this comparison should be false?

 

Yes. And it is. A slice is not an array. Or an open-ended array.

I would hope that slices from different underlying arrays could be
compared for equality based on their values, just like strings can.
Two strings (that are not slices from the same original string) can be
compared for equality just fine. I hope Go takes the shortcut when the
strings refer to the same memory and otherwise does the slower
per-byte comparison. The same could perhaps apply to slices in
general.

strings are immutable. They are more akin to an array of bytes than a slice of bytes.

--
Martin Geisler

[Chad]

However, that it's a valid point you raise (re strings)

But that's exactly the reason for which, someone would probably ask whether a string is a reference type or a value type.

This could probably made clearer in the documentation.

[Martin Geisler]

On Fri, Jul 1, 2016 at 12:48 PM, Chad <send...@gmail.com> wrote:
> On Friday, July 1, 2016 at 12:11:43 PM UTC+2, Martin Geisler wrote:
>>
>> On Fri, Jul 1, 2016 at 3:15 AM, Chad <send...@gmail.com> wrote:
>> > No, it's actually fine. You are comparing values.
>> >
>> > A slice being a struct under the hood, for slices you would compare the
>> > structs (slice headers)
>>
>> Yes, when you remember that a slice is a just a small struct with a
>> pointer and some bookkeeping information (length, capacity), then you
>> can compare two slices easily. So with
>>
>> a := []int{10, 20, 30}
>> b := a[:]
>>
>> then a == b would be fast: simply compare the pointers and the
>> bookkeeping information. Direct value equality between the structs
>> gives you the expected and correct answer.
>>
>> But what about
>>
>> []int{10, 20} == []int{10, 20}
>>
>> where the two slices refer to different underlying arrays? I think you
>> argue that this comparison should be false?
>
>
> Yes. And it is. A slice is not an array. Or an open-ended array.

Right, a slice is just view into an array :-)

I was hinting at the (lack of) symmetry with how strings work.

Two strings that share no underlying memory can compare equal, so I
think it would be reasonable if equality between slices followed the
same principle. Put differently, strings are "magic" and don't follow
normal rules for comparison, in particular, they don't use direct
value comparison. Here I'm assuming that

https://golang.org/pkg/reflect/#StringHeader

shows us how strings are implemented: a small struct with a pointer
and a length. If string comparison were to use value semantics, a and
b could not compare equal in this little example

a := "hello world"
b := make([]byte, len(a))
os.Stdin.Read(b)

since the pointer in a would differ from the pointer in b. Yet a == b
is true when you enter "hello world" :-) So we see the magic slip
through the cracks...

Given that, one could argue that it would be consistent to have
[]int{1} == []int{1} be true -- it's just yet another exception to the
rule that things are compared by value. It's not super pretty, though,
but I my opinion the illusion of prettyness has already been broken
with how some builtin types get special treatment here and there.

--
Martin Geisler

[Martin Geisler]

On Fri, Jul 1, 2016 at 12:52 PM, Chad <send...@gmail.com> wrote:
> However, that it's a valid point you raise (re strings)
> But that's exactly the reason for which, someone would probably ask whether
> a string is a reference type or a value type.
>
> This could probably made clearer in the documentation.

I keep seeing references (hah!) to this concept of a "reference type"
:-) However, I just tried searching the language spec and Effective Go
and there doesn't seem to be such a concept defined in those
documents. Effective Go talks about slices and maps having
"references" to some underlying data, but I don't think it says that
maps and slices themselves are "reference types".

So my understanding is that there is no such concept in Go. Instead
there are structs and pointers -- maps and slices are builtin types,
implemented as small structs that points to larger pieces of data.
When you pass either to a function, you end up copying the struct --
the normal value semantic we all know so well. Copying the struct is
fine since they're small: a slice is a pointer and two ints, I'm
unsure how a map looks like but I hope it's similarly sized.

I'm very new to Go, so please let me know if I'm missing anything?

--
Martin Geisler

[Chad]

Yes. You're absolutely right.That's due to the current implementation of strings.

Maybe they should be implemented as a struct with an unexported array of byte 

That would just work.

Having the string kind with the same structure as a slice is the problem here. strings should probably be pure values.

In any case, that's still an issue of defining what a value type and a reference type are. 

The implementation is a guide but it should not influence the spec so much as well.

slices are reference types and the comparison behaviour should be obvious: it's determining whether they reference the same thing.

strings are value types and likewise, the comparison behaviour is obvious.

[Chad]

On Friday, July 1, 2016 at 3:44:10 PM UTC+2, Martin Geisler wrote:

On Fri, Jul 1, 2016 at 12:52 PM, Chad <send...@gmail.com> wrote:
> However, that it's a valid point you raise (re strings)
> But that's exactly the reason for which, someone would probably ask whether
> a string is a reference type or a value type.
>
> This could probably made clearer in the documentation.

I keep seeing references (hah!) to this concept of a "reference type"
:-) However, I just tried searching the language spec and Effective Go
and there doesn't seem to be such a concept defined in those
documents.

I think it should. It is mentioned here however https://blog.golang.org/go-maps-in-action

Without that, one of the first instinct of beginning programmers is often to create pointers to slices.

I feel that, more clarifications about this area of the language would help a lot instead.

This is also a terminology of PLT that exists in other languages but as usual, one has to be careful about the implementation false friends.

[Chad]

On Friday, July 1, 2016 at 4:01:54 PM UTC+2, Chad wrote:

On Friday, July 1, 2016 at 3:44:10 PM UTC+2, Martin Geisler wrote:

On Fri, Jul 1, 2016 at 12:52 PM, Chad <send...@gmail.com> wrote:
> However, that it's a valid point you raise (re strings)
> But that's exactly the reason for which, someone would probably ask whether
> a string is a reference type or a value type.
>
> This could probably made clearer in the documentation.

I keep seeing references (hah!) to this concept of a "reference type"
:-) However, I just tried searching the language spec and Effective Go
and there doesn't seem to be such a concept defined in those
documents.

I think it should. It is mentioned here however https://blog.golang.org/go-maps-in-action

Without that, one of the first instinct of beginning programmers is often to create pointers to slices ** or maps **

 

(And I should know, I did that :)

 

[Matt Harden]

Conceptually, the value of a string is the sequence of bytes it contains, just like an array of bytes. It doesn't matter that the implementation of strings looks more like a slice internally. On the other hand the value of a slice is a reference to (part of) an underlying array, together with a length. In all cases == should compare values. I agree that it would be confusing to make == work for slices, because many people, myself included would intuitively want that to compare the contents of the slice (values from the underlying array) rather than the value of the slice itself which is essentially 3 pointers.

One nice feature of the current gc compiler AIUI is that it will avoid a copy in some circumstances when you convert a byte slice to a string and immediately use it as a map key. This helps with using []byte values to index into maps, but doesn't help when the []byte is part of a larger structure you want to use as a key.

[Martin Geisler]

On Fri, Jul 1, 2016 at 4:01 PM, Chad <send...@gmail.com> wrote:
>
>
> On Friday, July 1, 2016 at 3:44:10 PM UTC+2, Martin Geisler wrote:
>>
>> On Fri, Jul 1, 2016 at 12:52 PM, Chad <send...@gmail.com> wrote:
>> > However, that it's a valid point you raise (re strings)
>> > But that's exactly the reason for which, someone would probably ask
>> > whether
>> > a string is a reference type or a value type.
>> >
>> > This could probably made clearer in the documentation.
>>
>> I keep seeing references (hah!) to this concept of a "reference type"
>> :-) However, I just tried searching the language spec and Effective Go
>> and there doesn't seem to be such a concept defined in those
>> documents.
>
>
> I think it should. It is mentioned here however
> https://blog.golang.org/go-maps-in-action

You're right, that article calls maps, slices and pointers "reference types".

I feel that is a little unfortunate since it muddles the picture and
makes the implementation more obscure. I would have been happy to have
been told right from the start that a slice is a small struct, small
enough that you can pass it by value instead of with a pointer. That
allows me to build a mental model in terms of other Go constructs.

It might very well be that a slice isn't implemented *exactly* like a
struct, but if the mental picture of a struct explains the behavior
and performance characteristics, then it doesn't matter if the
compiler somehow cheats here and there when implementing the type.

> Without that, one of the first instinct of beginning programmers is often to
> create pointers to slices.
> I feel that, more clarifications about this area of the language would help
> a lot instead.
>
> This is also a terminology of PLT that exists in other languages but as
> usual, one has to be careful about the implementation false friends.

I agree, "reference type" is a widely used term. I think I prefer to
use it only for pointer types such as *int, *byte and so on.
Everything else would be value types, including string, map[int]int,
[]float and other special builtin types.

When talking about equality, the language defines some of these types
as comparable, with per-type rules for how == is implemented. Relaxing
the rules to allow comparing slices (by pair-wise comparison of the
values in the slices) seems like a natural thing to do for me. It
would make slice comparison work like string comparison works
currently. So the rule for comparison would not even be new or strange
-- just a natural extension of what is already there.

You could probably also make slices (and arrays) ordered, provides the
elements themselves are ordered. That would work the same way strings
work today: lexicographic ordering based on the elements.

--
Martin Geisler

[Martin Geisler]

On Sat, Jul 2, 2016 at 6:19 AM, Matt Harden <matt....@gmail.com> wrote:
> Conceptually, the value of a string is the sequence of bytes it contains,
> just like an array of bytes. It doesn't matter that the implementation of
> strings looks more like a slice internally. On the other hand the value of a
> slice is a reference to (part of) an underlying array, together with a
> length. In all cases == should compare values. I agree that it would be
> confusing to make == work for slices, because many people, myself included
> would intuitively want that to compare the contents of the slice (values
> from the underlying array) rather than the value of the slice itself which
> is essentially 3 pointers.

But what if you define slice comparison to be by value of the underlying array?

That would make []int{1} == []int{1} be true, despite the slices
pointing to different arrays.

It would probably also mean that

a := make([]int, 0, 5)
b := make([]int, 0, 7)

are equal since the two slices have equal elements, despite having
different capacities.

Defining slice comparison to be comparison on the values would mean
that you cannot tell if the slices refer to different underlying
arrays. Maybe you can use the reflect package to get hold of it
somehow and compare the pointers yourself.

Speaking of reflect, I just realized that what I'm proposing is to
define == as reflect.DeepEqual for slices. It seems to do everything
I'm talking about: slices from different arrays can compare equal, it
short-circuits in clever ways by looking at the length and noticing
when the slices refer to the same point in the same array.

> One nice feature of the current gc compiler AIUI is that it will avoid a
> copy in some circumstances when you convert a byte slice to a string and
> immediately use it as a map key. This helps with using []byte values to
> index into maps, but doesn't help when the []byte is part of a larger
> structure you want to use as a key.

Yes, I read about this optimization. In my opinion that is a great
optimization -- and the kind of optimization the compiler can do when
it knows the implementation of map and string. However, it shouldn't
be part of the language specification.

--
Martin Geisler

[Chad]

On Saturday, July 2, 2016 at 10:23:04 AM UTC+2, Martin Geisler wrote:

On Fri, Jul 1, 2016 at 4:01 PM, Chad <send...@gmail.com> wrote:
>
>
> On Friday, July 1, 2016 at 3:44:10 PM UTC+2, Martin Geisler wrote:
>>
>> On Fri, Jul 1, 2016 at 12:52 PM, Chad <send...@gmail.com> wrote:
>> > However, that it's a valid point you raise (re strings)
>> > But that's exactly the reason for which, someone would probably ask
>> > whether
>> > a string is a reference type or a value type.
>> >
>> > This could probably made clearer in the documentation.
>>
>> I keep seeing references (hah!) to this concept of a "reference type"
>> :-) However, I just tried searching the language spec and Effective Go
>> and there doesn't seem to be such a concept defined in those
>> documents.
>
>
> I think it should. It is mentioned here however
> https://blog.golang.org/go-maps-in-action

You're right, that article calls maps, slices and pointers "reference types".

I feel that is a little unfortunate since it muddles the picture and
makes the implementation more obscure. I would have been happy to have
been told right from the start that a slice is a small struct, small
enough that you can pass it by value instead of with a pointer. That
allows me to build a mental model in terms of other Go constructs.

A struct is considered a reference type if at least one of the field *points* to another object. (i.e. holds a reference to another object).

https://en.wikipedia.org/wiki/Reference_type

It's clearer. "small struct" would not be explicit enough nor true.

I think that slices require typically more documentation effort to clarify what they are. Then, the issue of comparability will be obvious.

There are user-defined reference types too.

type Foo struct{

   name string

   data *[192]byte

}

That would be a reference type. This one is comparable.

[Chad]

On Saturday, July 2, 2016 at 6:19:56 AM UTC+2, Matt Harden wrote:

Conceptually, the value of a string is the sequence of bytes it contains, just like an array of bytes. It doesn't matter that the implementation of strings looks more like a slice internally. On the other hand the value of a slice is a reference to (part of) an underlying array, together with a length. In all cases == should compare values.

It does(*). But for a slice, it "also" compares the location of those values. That's the difference between a slice and an array. 

(*) : well, or rather, it probably should .

 

I agree that it would be confusing to make == work for slices, because many people, myself included would intuitively want that to compare the contents of the slice (values from the underlying array) rather than the value of the slice itself which is essentially 3 pointers.

That's just a matter of realizing what a slice really is. I think It's more of a documentation issue to clear up the misconception. That should not impede the language from being improved.

[Florin Pățan]

I would also expect to compare values not memory locations, generally that's what I'm interested in comparing.

I never had the need to compare equality for memory locations of anything in Go (especially not for slices / maps oe their elements).

[Chad]

You can do that, but for correctness, I am arguing that it's not what you should expect for slices by default.

[as....@gmail.com]

Go does not have reference types. As far as I know, the word was purposefully removed from the spec to remove the ambiguity surrounding the word.

https://groups.google.com/forum/m/#!topic/golang-dev/926npffb6lA

[Martin Geisler]

Hi Chad,

On Sat, Jul 2, 2016 at 10:43 AM, Chad <send...@gmail.com> wrote:
>
> On Saturday, July 2, 2016 at 10:23:04 AM UTC+2, Martin Geisler wrote:
>>
>> On Fri, Jul 1, 2016 at 4:01 PM, Chad <send...@gmail.com> wrote:
>>>
>>> On Friday, July 1, 2016 at 3:44:10 PM UTC+2, Martin Geisler wrote:
>>>> I keep seeing references (hah!) to this concept of a "reference type"
>>>> :-) However, I just tried searching the language spec and Effective Go
>>>> and there doesn't seem to be such a concept defined in those
>>>> documents.
>>>
>>> I think it should. It is mentioned here however
>>> https://blog.golang.org/go-maps-in-action
>>
>> You're right, that article calls maps, slices and pointers "reference
>> types".
>>
>> I feel that is a little unfortunate since it muddles the picture and
>> makes the implementation more obscure. I would have been happy to have
>> been told right from the start that a slice is a small struct, small
>> enough that you can pass it by value instead of with a pointer. That
>> allows me to build a mental model in terms of other Go constructs.
>
>
> A struct is considered a reference type if at least one of the field
> *points* to another object. (i.e. holds a reference to another object).
> https://en.wikipedia.org/wiki/Reference_type

That is not how I've seen the word "reference type" used and I don't
think that's what the Wikipedia article tries to say. As I read it, it
says that a language like C++ has some types that are value types
(int, bool, structs, classes) and some types that are reference types
(&int, &bool).

As far as I know, reference types only show up in function and method
signatures in C++. It specifies that the argument should be passed by
reference instead of being copied like normal -- the compiler will
typically handle this by changing the &int parameter to a *int (int
pointer) parameter, insert & at the call site and * inside the
function. So the reference type gives you almost the same as a
pointer, but without the explicit dereferencing.

Other languages like Java and Python have reference types too: in
Java, all object instances are reference types. So when you pass an
object to a method, you pass a reference and modifications done in the
method are visible after the call.

I believe C# allows you to specify if you want a class to be a
reference type or a value type. The Wikipedia article says you use
"struct" for value types and "class" for reference types. This matches
how "struct" gives you a value type in Go.

The mail from as.utf8 points to this discussion (thanks!):

https://groups.google.com/forum/m/#!topic/golang-dev/926npffb6lA

which points to this issue:

https://github.com/golang/go/issues/5083

They make it pretty clear that people have been trying to remove the
use of "reference type".

> It's clearer. "small struct" would not be explicit enough nor true.
> I think that slices require typically more documentation effort to clarify
> what they are. Then, the issue of comparability will be obvious.
>
> There are user-defined reference types too.
>
> type Foo struct{
> name string
> data *[192]byte
> }
>
> That would be a reference type. This one is comparable.

I don't think that's a reference type in the usual sense of the word.
The basic test for me is what happens when you pass a Foo to a
function:

func ChangeTheFoo(f Foo) {
f.name = "changed"
}

if the name field is changed after the call, then Foo is indeed a
reference type. However, it won't be changed in Go since the Foo
struct is copied when the function is called and this is why I say
that Foo is not a reference type. That is true of all structs in Go.

--
Martin Geisler

[Chad]

Rob and Robert actually wrote that this area of the spec needs more work...

Otherwise, the behaviour of maps, slices and funcs cannot be fully explained.

On Sunday, July 3, 2016 at 7:25:31 AM UTC+2, as....@gmail.com wrote:

Go does not have reference types. As far as I know, the word was purposefully removed from the spec to remove the ambiguity surrounding the word.

https://groups.google.com/forum/m/#!topic/golang-dev/926npffb6lA

@Martin

As I've mentioned earlier, one ought to be careful about  false friends from other languages. 

I am not sure I understand what you mean by:

[Chad]

Oh, maybe you mistook reference type for the notion of reference.

[as....@gmail.com]

Relaxing unformalized behavior makes little sense to me. Explaining why equality is inconsistent between slices and arrays is not something I want to do either.

[Chad]

Which is why it should be formalized.

Where is the inconsistency between slices and arrays?

Why do people even think that a slice need to behave like an array wrt equality, were it introduced?

A slice is not an array!

[Florin Pățan]

If the type is *[]T then comparing memory addresses make sense to see if both terms point to the same memory address.

If the type is []T then comparing memory addresses doesn't make sense as I'd expect to compare values.

Finally, if the type is []*T then I'd still expect to compare values (even if this is inconsistent with the above two rules), mainly because I'm usually interested in the values a slice holds.

And that's exactly why Ian and others said this is complicated to define as different users expect different outcomes.

So rather than deal with this, in an auto-magic way, better let the users deal with it as they see fit from case to case.

[Chad]

What's the value of a slice?

What's the value of an array?

[Florin Pățan]

For []T the value of a slice for the purpose of comparison would be each individual value compared against each-other (ofc maybe comparing the length first as an optimization).

Same goes for an array.

And again, you are missing the whole point. Both me and you are wrong in each-others points of view.

Just accept this.

[Chad]

Not for comparison.

I am just asking what is the value of a slice and what is the value of an array.

Remember that there is no slice comparison that has been spec'ed so far.

[Florin Pățan]

If I look at what %v means, print out the values of various types in Go, according to https://golang.org/pkg/fmt/ then I believe that this holds the answer: https://play.golang.org/p/GiLckoBDxa

[Chad]

No. You should not get it from here. You should get the answer from the spec. Let alone the fact that the implementation should ideally follow the spec and not the reverse.

[Chad]

In fact, that is somewhat my fault.

I should ask:

What is a slice?

What is an array?

Spoiler: a slice is a reference type in its "wikipedia-ish" definition (auto-dereferencing) which is the reason you observe such a result in the playground.

[Florin Pățan]

As you pointed out, Printf() should follow the ref spec but that doesn't happen because some humans don't perceive this accuracy as necessary or maybe because the way to resonate about slices / arrays is as containers for the actual values.

Thus we have Printf working as it does (and %p will indeed print the memory address of the slice type).

I would definitely want to be able to compare []int{1, 2, 3} with ([]int{1, 2, 3, 4, 5})[:3] and result in equality (given here for example purposes but think of them as coming from different sources)

Apparently you don't, and that's fine.

That's exactly why the compiler only allows comparison with nil, to force the user to think about that should be compared, not do it by default and have potential hidden issues that might be uncovered too late in the process.

[Chad]

Ok, Let me help you out haha :)

Here is the definition of a slice. It is not a container.

https://golang.org/ref/spec#Slice_types

I am not inventing things.

I know what people on this thread said, but that's their misconception.

[Florin Pățan]

I'm sorry but your attitude is counterproductive to the discussion.

"haha" what? I told you I see your point, I think I know the specs very well, thank you for the link.

However, you seem incapable of accepting, despite an number of others saying the contrary, despite, given a reasonable example where even the standard library gets this "wrong" (according to you, according to me it's exactly as it should be).

You've been explained several times that both point of views hold valid arguments so why do you insist your point of view is the only correct one and everyone else is wrong?

The authors of the language which have far more experience that me (I can't speak for your experience or others), couldn't get to an agreement on how this should work so they took the best decision, let the user deal with this according to their individual needs.

I'll stop following this thread / replying as it's pointless to do so at this point.

Good luck proving everyone else is wrong and you know better.

[Chad]

Ok. That "haha" was merely to show that no animosity was borne. And also because you didn't really answer the question as I asked (by quoting the spec) which I found funny.

Alas, I guess we couldn't see eye to eye.

But chill a little bit. I have given all the hardcoded proofs and people have just given me feelings about what they thought should be right. I think I have the right to disagree.

Anyway, I can only wish you good continuation. :)

[as....@gmail.com]

Hardcoded proofs should be assigned well-named identifiers. If you ever have to alter them, you don't want to be rummaging around your lemmas and corollaries.

[Chad]

Pardon?

[as....@gmail.com]

I was being facetious. You have the right to opine, but elevating opinions to that of proofs doesn't give the discussion any utility. I think you should consider the underlying assumptions in some of your points:

1. A slice is a descriptor of an aggregate
2. A struct can resemble a descriptor of an aggregate.
3. A struct can resemble a slice
4. If a slice can be compared as a struct holding a descriptor, then maps can have slices as keys
5. Because it benefits this use case, it is a good feature to add to the language

Enumerating the drawbacks of this feature is more useful than trying to justify its existence. The language authors omitted this functionality for a reason. One of the reasons is that arrays and slices are similar, and changing their comparison semantics seemed confusing.  

[Chad]

I wish I could be pointed to such discussion.

The language authors omitted this functionality for a reason. One of the reasons is that arrays and slices are similar, and changing their comparison semantics seemed confusing.

 https://blog.golang.org/slices specifically mentions that arrays and slices are not similar. The spec does as well. Currently, slices do NOT compare. I am simply arguing that they could very logically.

The "==" operator is only overloaded in the case of strings currently but that's truly an implementation detail. Strings are values but their implementation is of a reference type. To get the value behaviour back, the comparison is weakened to only take into account the underlying array values and not where they are located. This probably for optimisation purposes. 

Other than that, there is a whole consistency to the language and how it works. I simply would like that consistency extended.

My main argument is that without specifying the logical "comparison" behaviour for all reference types, interface comparisons become unsafe. It's perhaps even a bug.

N.B. I gave my definition of a reference type which is the definition I would choose for Go. It does not have to be identical to what is found in other languages. In any case, there probably needs to be a way to distinguish between types that hold a reference to another datastructure from those that don't.

[as....@gmail.com]

I wish I could be pointed to such discussion.

It was briefly discussed in The Go Programming Language book by Donovan & Kernighan (p 132):

An analogous “shallow” equality test for slices could be useful, and it would solve the problem with maps, but the inconsistent treatment of slices and arrays by the == operator would be confusing. The safest choice is to disallow slice comparisons altogether. 

Given this program, how would you modify it to include interfaces?

https://play.golang.org/p/9-rhDCZol_

[Chad]

On Monday, July 4, 2016 at 12:09:57 AM UTC+2, as....@gmail.com wrote:

I wish I could be pointed to such discussion.

It was briefly discussed in The Go Programming Language book by Donovan & Kernighan (p 132):

An analogous “shallow” equality test for slices could be useful, and it would solve the problem with maps, but the inconsistent treatment of slices and arrays by the == operator would be confusing. The safest choice is to disallow slice comparisons altogether. 

A claim I find safe to be in disagreement with.

 

Given this program, how would you modify it to include interfaces?

https://play.golang.org/p/9-rhDCZol_

Starbytes is a pointer to a slice. It does not make a lot of sense to begin with.

I am pointing out the fact that if you have interfaces holding a slice, the current behaviour is not specified. (as in the Go's spec). That's a bug.

[Chad]

To illustrate.

I think that an issue should be raised.

https://play.golang.org/p/eiwG-4vsnJ

[Chad]

Actually that's my mistake. It is spec'ed but not in the bullet points.

https://golang.org/ref/spec#Comparison_operators

Still, I find this hairy.

[Chad]

I realize that the issue might be about changing/ adding a builtin:

• either add a builtin deep value Comparison function (via reflection)
  
• or add a snapshot type refinement which triggers the allocation of an immutable copy of a reference type
  (and we would recover the behaviour of the string implementation which is a special case of []byte snapshot, i.e. a value type*)

I would still expect the behaviour previously mentioned for the "==" operator.

(*) I keep using reference/value type terminology but it is indeed slightly tricky. But for lack of a better one...

[matthe...@gmail.com]

Here’s a draft for a Go 2 proposal that I’d like to add to the issue tracker since there’s no discussion there about this:

Slices should have equality defined.

https://golang.org/doc/faq#map_keys

Map lookup requires an equality operator, which slices do not implement. They don't implement equality because equality is not well defined on such types; there are multiple considerations involving shallow vs. deep comparison, pointer vs. value comparison, how to deal with recursive types, and so on.

This proposal allows slices to be used as map keys and for comparison with == and !=.

https://golang.org/ref/spec#Comparison_operators

Slice, map, and function values are not comparable.

An initial proposal is that slices are compared by nil versus non-nil, length and backing array pointer, and then by the rules for array if length is equal but different arrays are pointed:

Array values are comparable if values of the array element type are comparable. Two array values are equal if their corresponding elements are equal.

reflect.DeepEqual defines a similar slice equality except “deeply equal” defines additional criteria: https://golang.org/pkg/reflect/#DeepEqual

Slice values are deeply equal when all of the following are true: they are both nil or both non-nil, they have the same length, and either they point to the same initial entry of the same underlying array (that is, &x[0] == &y[0]) or their corresponding elements (up to length) are deeply equal. Note that a non-nil empty slice and a nil slice (for example, []byte{} and []byte(nil)) are not deeply equal.

A use case for me was a map keyed by varying length paths where the map was not shared between different path generating computations. With this proposal such a type could have shared generated paths as keys.

Ian suggests in a [this] golang-nuts thread that there are varying use cases:

The problem is that different programs need different things for slice equality.  Some want pointer equality as you suggest.  Some want element comparisons, as is done for array equality.  Without an obvious semantics for the operation, the language omits it entirely. 

 

But I don’t know where slice pointer equality would be useful. I'm also not clear on the recursive type problem.

Matt

[roger peppe]

Two significant issues that need to be thought about:

- When slices can be compared, they can be used as map keys. What happens if the contents of a slice are changed after it has been added to a map? 

- It is possible to have self-referential slices [1]. How would comparison work in such a case?

 [1] https://play.golang.org/p/lTqhKjD842K

--
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+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[matthe...@gmail.com]

- When slices can be compared, they can be used as map keys. What happens if the contents of a slice are changed after it has been added to a map? 

I’m not too familiar with Go map internals, but my thought is the key hash would depend on the backing array values. Go maps also allow reading the keys back using iteration so the slice backing array (up to length) would have to be copied. If the slice contents are changed then that would be a different key and the original key would be intact.

 - It is possible to have self-referential slices [1]. How would comparison work in such a case?

Perhaps a slice of slices would compare the contents, the slice headers, to each other like structs.

type A []A

// not equal
a0 := A{A{}}
a1 := A{}

// not equal
a2 := A{A{}, A{A{}}}
a3 := A{A{}, A{A{}}}

// not equal
a4 := A{a0}
a5 := A{A{A{}}}

// equal
a6 := A{a0}
a7 := A{a0}

// equal
a8 := A{a0}
a8[0] = a1
a9 := A{a1}

The self-reference:

a0 := A{}
// equal
a1 := A{a0, A{}}
a1[0] = a1
a2 := A{a0, a1[1]}
// not equal
a3 := A{A{}, a1[1]}

I'm not sure about this one since it seems to go against the idea of slice comparison by values.

Matt

To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.

[matthe...@gmail.com]

Correction on the self-reference example:

a0 := A{}
// equal
a1 := A{a0, A{}}
a1[0] =

a1
a2 := A{a1, a1[1]}
// not equal
a3 := A{A{a1, a1[1]}, a1[1]}

Thanks,

Matt

[Axel Wagner]

On Wed, Jan 31, 2018 at 12:19 AM, <matthe...@gmail.com> wrote:

- When slices can be compared, they can be used as map keys. What happens if the contents of a slice are changed after it has been added to a map? 

I’m not too familiar with Go map internals, but my thought is the key hash would depend on the backing array values. Go maps also allow reading the keys back using iteration so the slice backing array (up to length) would have to be copied. If the slice contents are changed then that would be a different key and the original key would be intact.

 - It is possible to have self-referential slices [1]. How would comparison work in such a case?

Perhaps a slice of slices would compare the contents, the slice headers, to each other like structs.

That flies in the ideas of consistence. All other equality operators are - if they are defined - defined recursively. Making slice-comparison *sometimes* by contents and *sometimes* by reference is pretty bad.

And to reiterate: The point of the people arguing against making slices comparable is not that it would be impossible to define consistent semantics for making that happen. Everyone agrees that it's possible. The point is, that there are *too many* ways to make it happen and too many edge-cases and it is not *obvious* what the correct answers to all these questions are. Answering the questions in an ad-hoc manner doesn't really help alleviate this concern. On the contrary, the fact that the answers seem sometimes self-contradictory and even the proponents of slice-comparisons can't seem to really agree on them underlines the argument against it.

Go tries, as much as possible, to have code map as obviously and clearly to the resulting semantics as possible. It does sometimes fail in that and that is unfortunate, but it doesn't change the fact, that we shouldn't make the language more obtuse.

 

To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.

[matthe...@gmail.com]

I agree with you Axel. One point is that allowing struct comparison but not slice comparison was counterintuitive to me at first.

What about a proposal addition of “types with self-references in slices cannot be compared”?

While comparison by header versus comparison by value may not be an obvious choice, once a choice is made then that’s easy to remember for the straightforward cases. Everything else can continue to be not allowed.

I’m curious about examples where people wanted one or the other. I only have the one example for by value.

What about maps and functions? A function is just a block of data, so I’d think they’d be equal if the compiler output is the same for each. Why wouldn’t a map comparison by value work?

Thanks,
Matt

[Axel Wagner]

> What about a proposal addition of “types with self-references in slices cannot be compared”?

Are you sure that's the only edge-case? Because this thread is kinda long and there might even be things we are not thinking about. 

> I’m curious about examples where people wanted one or the other. I only have the one example for by value.

The usecase you mentioned above seems - to me - to be served by a map[string]*T just fine. Did I misunderstand it?

For usecases for the other, I don't know - but observationally, this thread has a person who found the reference comparison the obviously correct choice, underlining again, that there seems to be at least some ambiguity. They might be able to give usecases.

> A function is just a block of data, so I’d think they’d be equal if the compiler output is the same for each.

Are two closures capturing different values the same or not? It's the same code, but they do very different things.

What about two functions which have the same code, but having different sets of functions inlined into them (because of some optimization decision taken now or in the future) so they compile to different instructions? What about languages that don't actually compile functions to an instruction stream (e.g. GopherJS)?

> Why wouldn’t a map comparison by value work?

Seems to have exactly the same ambiguities as slices. But also, is pretty expensive (more so than slices, as maps are unordered, so you'd have to roughly linearly search one and randomly access the other, trashing cashes and the like). Personally, I don't like expensive operations being made too simple.

To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.

[roger peppe]

On 30 January 2018 at 23:19, <matthe...@gmail.com> wrote:
>> - When slices can be compared, they can be used as map keys. What happens
>> if the contents of a slice are changed after it has been added to a map?
>
>
> I’m not too familiar with Go map internals, but my thought is the key hash
> would depend on the backing array values. Go maps also allow reading the
> keys back using iteration so the slice backing array (up to length) would
> have to be copied. If the slice contents are changed then that would be a
> different key and the original key would be intact.

Note that copying the slice contents to make a map key implies
that using a slice as a map key might imply copying a whole tree,
which seems rather expensive to me (especially as it might end up
using more memory than the original if some elements are duplicated,
unless an alias-aware copy algorithm is used which would be
more expensive still)

BTW you can already do something like this:
https://play.golang.org/p/q4bz8-AckN3

You can even do it without reflect, which I'll leave as an exercise
for the reader :)

[matthe...@gmail.com]

Are you sure that's the only edge-case? Because this thread is kinda long and there might even be things we are not thinking about. 

In the original discussion above I see one opinion toward comparing headers and four toward by element values (like strings). I didn't see any additional edge cases listed.

The usecase you mentioned above seems - to me - to be served by a map[string]*T just fine. Did I misunderstand it?

Each path represented as a slice of coordinates could be easily encoded to a string and compared that way.

As far as resource expenses go, we'd need benchmarks to say much. I understand looking at expensive cases too, but that doesn't mean that there aren't smaller regular use cases. Goroutines can be overused too.

Matt

[Axel Wagner]

On Fri, Feb 2, 2018 at 9:59 PM, <matthe...@gmail.com> wrote:

Each path represented as a slice of coordinates could be easily encoded to a string and compared that way.

Ah, I misunderstood "path".

 

As far as resource expenses go, we'd need benchmarks to say much. I understand looking at expensive cases too, but that doesn't mean that there aren't smaller regular use cases. Goroutines can be overused too.

Matt

On Wednesday, January 31, 2018 at 10:24:30 AM UTC-6, rog wrote:

On 30 January 2018 at 23:19,  <matthe...@gmail.com> wrote:
>> - When slices can be compared, they can be used as map keys. What happens
>> if the contents of a slice are changed after it has been added to a map?
>
>
> I’m not too familiar with Go map internals, but my thought is the key hash
> would depend on the backing array values. Go maps also allow reading the
> keys back using iteration so the slice backing array (up to length) would
> have to be copied. If the slice contents are changed then that would be a
> different key and the original key would be intact.

Note that copying the slice contents to make a map key implies
that using a slice as a map key might imply copying a whole tree,
which seems rather expensive to me (especially as it might end up
using more memory than the original if some elements are duplicated,
unless an alias-aware copy algorithm is used which would be
more expensive still)

BTW you can already do something like this:
https://play.golang.org/p/q4bz8-AckN3

You can even do it without reflect, which I'll leave as an exercise
for the reader :)

--

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+unsubscribe@googlegroups.com.

[Peter Waller]

On 31 January 2018 at 16:23, roger peppe <rogp...@gmail.com> wrote:

BTW you can already do something like this:
https://play.golang.org/p/q4bz8-AckN3

 

Neat trick!

 

You can even do it without reflect, which I'll leave as an exercise for the reader :)

I'll bite, does it involve struct { len int; content [maxCount]int }, or did you have something else in mind?

[roger peppe]

Something else. No size limit. Not what one might call efficient though. :)

[Peter Waller]

On 5 February 2018 at 11:04, roger peppe <rogp...@gmail.com> wrote:

> I'll bite, does it involve struct { len int; content [maxCount]int }, or did
> you have something else in mind?

Something else. No size limit. Not what one might call efficient though. :)

[low growling]

(ok, so I've been watching Stranger Things with subtitles too much...)

I'm... not sure I can figure out what you're thinking of, dangit.

Does it involve gratuitous numbers of calls to the fmt package?

[roger peppe]

Nope. No fmt at all.

A clue: struct{x interface{}}{12} == struct{x interface{}}{12}

[roger peppe]

... tick, tick, tick, tick... dide-dudi-diddlidedum...di!

func comparable(xs []int) interface{} {
type elem struct {
first int
rest interface{}
}
var r interface{}
for _, x := range xs {
r = elem{x, r}
}
return r
}

https://play.golang.org/p/7VG1MWDI-l-

or, somewhat more generally:

https://play.golang.org/p/_vfh2nT5cZL

You can even use this technique to compare arbitrary DAGs.
Not that it would be a good idea :)

[Peter Waller]

On 6 February 2018 at 09:34, roger peppe <rogp...@gmail.com> wrote:

... tick, tick, tick, tick... dide-dudi-diddlidedum...di

http://www.reactiongifs.com/wp-content/uploads/2011/09/mind_blown.gif 

[Ian Lance Taylor]

On Tue, Feb 6, 2018 at 1:34 AM, roger peppe <rogp...@gmail.com> wrote:
> ... tick, tick, tick, tick... dide-dudi-diddlidedum...di!
>
> func comparable(xs []int) interface{} {
> type elem struct {
> first int
> rest interface{}
> }
> var r interface{}
> for _, x := range xs {
> r = elem{x, r}
> }
> return r
> }
>
> https://play.golang.org/p/7VG1MWDI-l-
>
> or, somewhat more generally:
>
> https://play.golang.org/p/_vfh2nT5cZL
>
> You can even use this technique to compare arbitrary DAGs.
> Not that it would be a good idea :)

Very nice.

Ian

> On 5 February 2018 at 17:49, roger peppe <rogp...@gmail.com> wrote:
>> On 5 February 2018 at 11:38, Peter Waller <pe...@pdftables.com> wrote:
>>> On 5 February 2018 at 11:04, roger peppe <rogp...@gmail.com> wrote:
>>>>
>>>> > I'll bite, does it involve struct { len int; content [maxCount]int }, or
>>>> > did
>>>> > you have something else in mind?
>>>>
>>>> Something else. No size limit. Not what one might call efficient though.
>>>> :)
>>>
>>>
>>> [low growling]
>>>
>>> (ok, so I've been watching Stranger Things with subtitles too much...)
>>>
>>> I'm... not sure I can figure out what you're thinking of, dangit.
>>>
>>> Does it involve gratuitous numbers of calls to the fmt package?
>>
>> Nope. No fmt at all.
>>
>> A clue: struct{x interface{}}{12} == struct{x interface{}}{12}
>

[matthe...@gmail.com]

Slice pointer keys are another option but that concept is tricky too.

Matt

[roger peppe]

On 6 February 2018 at 14:55, <matthe...@gmail.com> wrote:
> Slice pointer keys are another option but that concept is tricky too.

What do you mean by a "slice pointer key" ?

[matthe...@gmail.com]

What do you mean by a "slice pointer key" ? 

map[*[]Something]string

Then map consumers can do key comparisons. I originally used this for an unordered set type.

Matt

[matthe...@gmail.com]

I went ahead and opened a Go 2 proposal: https://github.com/golang/go/issues/23725

Thanks,
Matt

[Peter Waller]

On 6 February 2018 at 21:25, <matthe...@gmail.com> wrote:

What do you mean by a "slice pointer key" ? 

map[*[]Something]string

Then map consumers can do key comparisons. I originally used this for an unordered set type.

 I'm sure you are aware of the distinction but it might not be clear for others reading: this does "byte slice identity", but doesn't actually compare the contents of slices.

Consider https://play.golang.org/p/gjZx8nGK8EB :

foo := []int{1, 2, 3}

bar := []int{1, 2, 3}

m := map[*[]int]bool{}

m[&foo] = true

m[&bar] = true

Then you'd have len(m) == 2, even though foo and bar are the same.

The neat thing about rog's trick is that in that case you'd only have one: the two slices would be equal owing to their contents, not where the slice happens to live in memory (not to be confused with "where the backing array of the slice lives in memory").