custom hashing is too easy to accidentally break

[StefanKarpinski]

If you define a custom == for a type and don't define a matching hash method for it, it silently breaks hashing of that type:

julia> type Foo
           x::Int
       end

julia> ==(a::Foo, b::Foo) = a.x == b.x
== (generic function with 109 methods)

julia> [unique([Foo(4), Foo(4), Foo(4)]) for _ = 1:25]
25-element Array{Array{Foo,1},1}:
 [Foo(4),Foo(4),Foo(4)]
 [Foo(4),Foo(4),Foo(4)]
 [Foo(4),Foo(4),Foo(4)]
 [Foo(4),Foo(4),Foo(4)]
 [Foo(4),Foo(4),Foo(4)]
 [Foo(4),Foo(4)]
 [Foo(4),Foo(4)]
 [Foo(4),Foo(4),Foo(4)]
 [Foo(4),Foo(4),Foo(4)]
 [Foo(4),Foo(4),Foo(4)]
 [Foo(4),Foo(4),Foo(4)]
 [Foo(4)]
 [Foo(4),Foo(4),Foo(4)]
 [Foo(4),Foo(4),Foo(4)]
 [Foo(4),Foo(4),Foo(4)]
 [Foo(4),Foo(4),Foo(4)]
 [Foo(4),Foo(4),Foo(4)]
 [Foo(4),Foo(4)]
 [Foo(4),Foo(4),Foo(4)]
 [Foo(4),Foo(4)]
 [Foo(4),Foo(4),Foo(4)]
 [Foo(4),Foo(4),Foo(4)]
 [Foo(4),Foo(4)]
 [Foo(4),Foo(4)]
 [Foo(4),Foo(4),Foo(4)]

Whether you get one, two or three values depends on whether the last digits of their address in memory happen to be the same or not. This is because hashing is based on object identity, which is based on address. See discussion here:

• https://groups.google.com/forum/#!topic/julia-users/bi9sBnlTswQ
• https://groups.google.com/forum/#!topic/julia-users/q6F7-eVcAkQ

Having it this easy to silently break the hashing of a type seems like a bad design. Although the problem is worse for mutable types since people inevitably want to overload == for them, it's not just a problem for mutable objects:

julia> immutable Bar
           x::Int
           y::Int
       end

julia> ==(a::Bar, b::Bar) = a.x == b.x
== (generic function with 110 methods)

julia> [unique([Bar(i,i+j), Bar(i,2i+j), Bar(i,i+2j)]) for i=1:25, j=1:3]
25x3 Array{Array{Bar,1},2}:
 [Bar(1,2),Bar(1,3)]                 [Bar(1,3),Bar(1,4)]                 [Bar(1,4),Bar(1,5),Bar(1,7)]
 [Bar(2,3),Bar(2,5),Bar(2,4)]        [Bar(2,4),Bar(2,6)]                 [Bar(2,5),Bar(2,7),Bar(2,8)]
 [Bar(3,4),Bar(3,7),Bar(3,5)]        [Bar(3,5),Bar(3,8),Bar(3,7)]        [Bar(3,6),Bar(3,9)]
 [Bar(4,5)]                          [Bar(4,6),Bar(4,10),Bar(4,8)]       [Bar(4,7),Bar(4,11),Bar(4,10)]
 [Bar(5,6),Bar(5,11),Bar(5,7)]       [Bar(5,7),Bar(5,12),Bar(5,9)]       [Bar(5,8),Bar(5,13),Bar(5,11)]
 [Bar(6,7),Bar(6,13)]                [Bar(6,8),Bar(6,14),Bar(6,10)]      [Bar(6,9),Bar(6,15)]
 [Bar(7,8),Bar(7,15),Bar(7,9)]       [Bar(7,9),Bar(7,16),Bar(7,11)]      [Bar(7,10),Bar(7,17),Bar(7,13)]
 [Bar(8,9),Bar(8,17),Bar(8,10)]      [Bar(8,10),Bar(8,18),Bar(8,12)]     [Bar(8,11),Bar(8,19),Bar(8,14)]
 [Bar(9,10),Bar(9,19),Bar(9,11)]     [Bar(9,11),Bar(9,20),Bar(9,13)]     [Bar(9,12),Bar(9,21),Bar(9,15)]
 [Bar(10,11),Bar(10,21),Bar(10,12)]  [Bar(10,12),Bar(10,22),Bar(10,14)]  [Bar(10,13),Bar(10,23),Bar(10,16)]
 [Bar(11,12),Bar(11,23),Bar(11,13)]  [Bar(11,13),Bar(11,24),Bar(11,15)]  [Bar(11,14),Bar(11,25),Bar(11,17)]
 [Bar(12,13),Bar(12,25),Bar(12,14)]  [Bar(12,14),Bar(12,16)]             [Bar(12,15),Bar(12,18)]
 [Bar(13,14),Bar(13,27),Bar(13,15)]  [Bar(13,15),Bar(13,28),Bar(13,17)]  [Bar(13,16),Bar(13,29),Bar(13,19)]
 [Bar(14,15),Bar(14,29),Bar(14,16)]  [Bar(14,16),Bar(14,30)]             [Bar(14,17)]
 [Bar(15,16),Bar(15,31),Bar(15,17)]  [Bar(15,17),Bar(15,32),Bar(15,19)]  [Bar(15,18),Bar(15,33),Bar(15,21)]
 [Bar(16,17),Bar(16,33),Bar(16,18)]  [Bar(16,18),Bar(16,34)]             [Bar(16,19),Bar(16,35)]
 [Bar(17,18),Bar(17,35),Bar(17,19)]  [Bar(17,19),Bar(17,36),Bar(17,21)]  [Bar(17,20),Bar(17,37),Bar(17,23)]
 [Bar(18,19),Bar(18,37),Bar(18,20)]  [Bar(18,20),Bar(18,38),Bar(18,22)]  [Bar(18,21),Bar(18,39),Bar(18,24)]
 [Bar(19,20),Bar(19,39),Bar(19,21)]  [Bar(19,21),Bar(19,23)]             [Bar(19,22),Bar(19,41),Bar(19,25)]
 [Bar(20,21),Bar(20,22)]             [Bar(20,22),Bar(20,42),Bar(20,24)]  [Bar(20,23),Bar(20,43),Bar(20,26)]
 [Bar(21,22),Bar(21,43)]             [Bar(21,23),Bar(21,44),Bar(21,25)]  [Bar(21,24),Bar(21,45),Bar(21,27)]
 [Bar(22,23),Bar(22,45),Bar(22,24)]  [Bar(22,24),Bar(22,46),Bar(22,26)]  [Bar(22,25),Bar(22,47),Bar(22,28)]
 [Bar(23,24),Bar(23,47),Bar(23,25)]  [Bar(23,25),Bar(23,48),Bar(23,27)]  [Bar(23,26),Bar(23,49),Bar(23,29)]
 [Bar(24,25),Bar(24,49),Bar(24,26)]  [Bar(24,26),Bar(24,50),Bar(24,28)]  [Bar(24,27),Bar(24,51),Bar(24,30)]
 [Bar(25,26),Bar(25,51)]             [Bar(25,27),Bar(25,52),Bar(25,29)]  [Bar(25,28),Bar(25,53),Bar(25,31)]

[mauro3]

julia user discussion:
https://groups.google.com/d/msg/julia-users/bi9sBnlTswQ/njsRvLzgd5gJ
https://groups.google.com/d/msg/julia-users/q6F7-eVcAkQ/Csm4zHFH2JQJ

[StefanKarpinski]

Yup, linked to that in the middle of that. Probably should have put it at the end.

[mauro3]

Oops, sorry, I should have read more carefully.

[StefanKarpinski]

No worries – I should have posted more clearly :-)

[yuyichao]

@StefanKarpinski Is there something more we need to worry about if we just cache the hash or otherwise add additional comparason of the hash as you proposed somewhere in that thread? We could just throw an error in such case.

[yuyichao]

And by such case I mean when they are == but the hash is not.

[StefanKarpinski]

That would fix it, but you would only get the error in the cases where two hashes accidentally "collide". I'm kind of into the idea of defining == and hash generically in terms of some identity_parts function or something like that.

[yuyichao]

That would fix it, but you would only get the error in the cases where two hashes accidentally "collide".

Getting a predictable result (unique retuning 3 items in the case you have above) or a clear error is argueably the best response I can imagine for an undefined behavior.

in terms of some identity_parts function

I just think it might be kind of a headache for type stability for types that allows "missing values".

[yuyichao]

Getting a predictable result (unique retuning 3 items in the case you have above) or a clear error is argueably the best response I can imagine for an undefined behavior.

I agree that it might be hard to hit the error and notice the undefined behavior in certain scenario so I'm not saying this is the best we can do either (e.g. if identity_parts works).

[yuyichao]

I just think it might be kind of a headache for type stability for types that allows "missing values".

Actually since we have such a type. The question is basically, how do you define identity_parts for Nullable.

Feels like it should return a Tuple{Bool, Union{}} for type stability if it's a missing value. Would be funny if it's not type stable for Nullable given it's the whole point of the type......

[JeffBezanson]

I guess we should just remove the fallback for hash that uses object_id.

[carnaval]

I guess we should just remove the fallback for hash that uses object_id.

Can I frame this ? Many hours wasted in debugging (lack of recompilation + wrong bootstrap order = hashing by object id unexpectedly)

[jakebolewski]

Horray!

[JeffBezanson]

Huh? What have you guys been smoking hashing?