[go-nuts] DeepEqual of maps with pointers as keys (bug?)

IMO the code behaves correctly: http://golang.org/ref/spec#Comparison_operators.

http://play.golang.org/p/_cjafjgb10

Should DeepEqual dereference pointers and compare the dereferenced
values instead? Consider

type node struct { next * node }

n := &node{}
n.next = n

reflect.NewDeepEqual(n, n) // don't expect this to ever return

Using a pointer to a string _does_ save memory, but only one machine
word. String is a value type, roughly struct{p *byte, len int}. You
can use in this case a string "dictionary":
http://godoc.org/github.com/cznic/strutil#Dict. Comparing equal valued
integers (string numercial identifiers) instead of string pointers
should work in the above code.

-j

But it does, just not in this case where the value is a map key.

http://play.golang.org/p/ScUVQ5Z_Eb

Ah, my bad. It shows that I, in the first approximation, don't touch
reflection. I implanted how I would probably write DeepEqual. As it
seemed to me dereferencing is not an option. Well, it's not "seemed",
but "seems" still. I wonder, how DeepEqual manages cyclic data? Does
it compare shapes of value-less node graphs? What about when given two
different nodes of the same non oriented graph? The ad hoc
[non]/dereferencing can get quite evil pretty fast.

However, the documentation (http://golang.org/pkg/reflect/#DeepEqual)
says the opposite: "It uses normal == equality where possible but will
scan members of arrays, slices, maps, and fields of structs.". If it
dereferences a pointer to a string and compare the dereferenced values
instead then the docs are docs are not correct.

Now I'm confused ;-)

-j
Please see the above reply to Dan.

-j

It looks like it maintains a set of visited addresses so it can
short-circuit computations if the same appears multiple times, which also
will stop you when cycles are encountered..

However, the documentation (http://golang.org/pkg/reflect/#DeepEqual)
It does say that it uses == if possible, which led me to assume the same
thing at first -- especially when coupled with my failing test case that I
believed should have passed. Might be nice to clarify in the doc string.
Not any weirder than dereferencing other pointers and comparing by value,
except the implementation is harder. The *real *trouble comes in when the
map keys: 1. Are pointers to non-data types (could fall back to ptr
comparison in that case), or 2. Have duplicate data behind different
pointers. Case 2 is really hard to solve. Consider the case:

m1[&"hi"] = 1
m1[&"hi"] = 2
m2[&"hi"] = 1
m2[&"hi"] = 2

These are clearly equivalent, but to check this you need to compare all
combinations of m1's keys + m2's keys. And then imagine if the maps'
values were deep data structures instead of simple ints...it would get
expensive to recursively compare them in all combinations.

OK, DeepEqual is probably good the way it is...but might be nice to
document this to prevent others from asking the same questions later.

Thanks,
Doug

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

But this is reflect.DeepEqual, not a comparison operator, so I don't think
that necessarily applies... Likewise, your example is with ==, and I've
already shown cases where DeepEqual does dereference-then-compare.
Hmm, that definitely is good to know that the string buffer is not being
copied around behind the scenes.. Even so, there's a 50% savings to be had,
so I might try something like that dict and use an int. Thanks for the tip.

Still, I think the DeepEqual behavior question is valid and unresolved.

Doug

You pay for those bytes with cache misses.
Since the speed of light isn't getting any faster
Since the keys aren't the string values and are instead the pointers to the
string values this would allow two maps with completely different keys to
be considered equal. That's seriously weird.