proposal: Go 2: make []byte comparable (more accurately, reflect its inherent comparability)

[a3s7p]

What version of Go are you using (go version)?

$ go version
1.14.1

Does this issue reproduce with the latest release?

Yes.

What operating system and processor architecture are you using (go env)?

I don't think this is relevant.

What did you do?

I tried to use byte slices in a context where they might be compared (most notably, as fields in a struct which is a map key).

What did you expect to see?

Considering #31587, byte slices are as comparable as strings are and the comparison does not allocate. Therefore, I would expect them to be comparable like strings and acceptable as members of a struct used as a map key.

What did you see instead?

Byte slices are not comparable while strings are.

1. Using bytes.Equal instead of == for comparing byte slices is merely a syntactic nuisance.
2. So is using byte slices as keys in a map via string(b).
3. However the current behavior means that it is not possible to use a struct containing byte slices as a map key whereas it is possible to use a struct containing strings as a map key. This leads to hacks converting one type to another or using less intuitive solutions altogether which provide no benefit over []byte being comparable as-is.

It doesn't seem to me that changing this would break backwards compatibility/any code out there as currently it is not possible to use a []byte in a comparable type context at all.

Also, the invalid map key type fnord error message could be more helpful.

[randall77]

The problem with comparable byte slices, especially for use as map keys, is that they are modifiable. What happens if you modify the slice after insertion?

m := map[[]byte]int{}
b := []byte{1,2,3}
m[b] = 7
b[1] = 8
println(m[b])
println(m[[]byte{1,2,3}])
println(m[[]byte{1,8,3}])

What do those printlns print?

We'd have to make a copy of the backing store to make this work, I think. Then that would be different from all the other reference types that can be used as keys.

[a3s7p]

Pointers used as map keys are modifiable in the same fashion. Consider this playground example.

I realize that pointers and byte slices would use a different comparison (address is compared for pointers, contents for byte slices) -- and therefore the expected behavior in the pointer case would make more sense than in the byte slice case. However as long as this is documented I don't see a problem with it per se.

Besides, arrays are also modifiable and yet allowed as map keys.

[randall77]

But maps with pointers as keys use pointer equality, not contents-of-the-thing-pointed-to equality.
But it sounds like that's not what you want for slices.

Arrays are modifiable but are values, so you implicitly make a copy on insertion into a map (same with any value type, really).

[a3s7p]

You are right. Why not treat byte slices the same as arrays then? Slice pretends to be a value type in some ways while being a reference type. Here I think it would be warranted to treat it as a value type, i. e. make a copy. That way you could probably even extend this mechanism to any slice which contains a comparable type (but this is a different discussion with a different scope -- here I am only concerned about []byte for now).

[randall77]

It seems to me that it would still be ripe for confusion.

Do we compare the values between len and cap?

b := []byte{1,2,3,4}[:3]
c := []byte{1,2,3,5}[:3]
if b == c { ... }

I could see arguments for either decision.

Does assignment make a copy?

b := []byte{1,2,3}
c := b
b[1] = 5
if c[1] == 5 { ... should reach here ... }

It never used to, but now, sometimes, it does.

Why do map keys make a copy but map values don't?

m := map[[]byte][]byte{}
k := []byte{1,2,3}
v := []byte{4,5,6}
m[k] = v
k[1] = 9
v[1] = 9
if _, ok := m[k]; !ok { ... should reach here, as map doesn't have 1,9,3 as a key ... }
if m[[]byte{1,2,3}][1] == 9 { ... should reach here, as map does have 4,9,6 as a value ... }

We certainly don't want to copy the backing store of the slice for map values. Too much code depends on the reference semantics. For example, m[k] = append(m[k], 7).

[a3s7p]

Valid concerns, thank you.

Just to clarify, I am not suggesting to necessarily change []byte's default behavior, but as it is right now, there is also no explicit way to have e. g. []byte-containing structs as keys without writing ugly code. It simply can't be done cleanly although it's technically possible (even without having to allocate extra).

The simplest solution I can think of is creating a struct type identical in structure to the []byte-containing one but with string fields instead and converting to it before assigning it as a map key. That's suboptimal. And for my use case (which is using a map as a set for <O(n) lookup) it's going to look terrible.

Another way is to serialize the struct via e. g. JSON which I am currently using but that has its own drawbacks (performance, runtime use of reflection etc).

Do you think this proposal as such has merit independent of its concrete implementation?

Might this be considered in the scope of a generics mechanism for a future Go version?

Or perhaps (if that ever makes it to Go) in the scope of an immutable type/variable mechanism?

[randall77]

Just to clarify, I am not suggesting to necessarily change []byte's default behavior, but as it is right now, there is also no explicit way to have e. g. []byte-containing structs as keys without writing ugly code. It simply can't be done cleanly although it's technically possible (even without having to allocate extra).

I agree that this would be a nice problem to solve. I'm just skeptical that this proposal is the right solution. I think it creates more issues than it solves.

Do you think this proposal as such has merit independent of its concrete implementation?

Any proposal needs to at least argue that a concrete implementation is possible. I don't think it would need details, however.

Might this be considered in the scope of a generics mechanism for a future Go version?

I don't really know how generics would figure into this. It's certainly ok to assume you have generics and design from there. It would just have to wait until generics happen before it gets implemented.

Or perhaps (if that ever makes it to Go) in the scope of an immutable type/variable mechanism?

Same. I would imagine immutable byte slices would behave much like strings. But it's hard to be sure, we don't have a immutable proposal that is likely to be accepted at the moment.

[ianlancetaylor]

There isn't anything particularly special about []byte, the same arguments apply to slices of any comparable type. See #23725.

Historically we've never implemented slice equality because there are two logical choices for equality: element-by-element comparison and identical-backing-array comparison. Different programs would prefer different choices, and neither is clearly correct. In the presence of this ambiguity, the language declines to make a choice.

When and if we have generics I'm confident that people will implement hashmap types that provide different tradeoffs, including the opportunity to define your own hash and equality functions, which can then be used to implement the semantics you need.

[ianlancetaylor]

For language change proposals, please fill out the template at https://go.googlesource.com/proposal/+/refs/heads/master/go2-language-changes.md .

When you are done, please reply to the issue with @gopherbot please remove label WaitingForInfo.

Thanks!