RFC: new approach to efficiently hashing 1, 1.0, big(1), the same.

[StefanKarpinski]

The major change is that numeric values that are mathematically equal hash the same. This is tricky to do in a way that allows the hashing of Int64, Float64, Uint64 and such common numeric types to all be fast – nearly as fast as just applying the core hash to them as raw bits.

Although tests pass, this is an inherently half-baked state since isequal and hash are now badly out of sync. Many decisions still need to be made about how to hash collections: does the collection type matter or just the element type of the collection? Or neither?

This also does away with the bitmix function, instead favoring a Merkle-Damgård style of combining arbitrary amounts of data into a single, fixed-size hash value output. In a sense the hash function with two arguments replaces the bitmix function – you can give the result of hashing previous values as the second argument to hash and the result will depend on both in a difficult-to-predict way.

[StefanKarpinski]

Oh, I should also note that this is almost certainly really broken on 32-bit systems. I just didn't worry about that while developing this, but should be fixable with a little attention.

[JeffBezanson]

+:100:

Oh boy have I been waiting for this to land. This is a really nice piece of work.

Questions about comparing collections should not get in the way of this, since those issues exist anyway. Now we have

=== - our old friend egal
== - equality with respect to the abstraction implemented by the arguments
isequal - hasn't been changed yet, but should be the same as == except for -0.0 and NaN

[JeffBezanson]

Should this say num*2^pow/den?

[StefanKarpinski]

Uh, yes. Duh. Fortunately, only the documentation is wrong :-)

[JeffBezanson]

Would it suffice to have a single definition

hash(x) = hash(x, uint(0))

?

[StefanKarpinski]

Good point. That probably saves typing overall.

[IainNZ]

So does this mean

mydict = Dict{Number,Int}()
mydict[1.0] = 100
@assert mydict[BigInt(1)] == 100
@assert mydict[1] = 100

would work?

[StefanKarpinski]

Yes, @IainNZ, that's exactly what it means – but I have to fix isequal first.

[StefanKarpinski]

@JeffBezanson, this code could really benefit from specialization on default arguments since many performance-critical cases have the zero default second argument. How hard would that be to do?

[JeffBezanson]

I suppose it is really just inlining; if the function called by hash(x,0) passes inlining heuristics then it should happen already, to the extent that LLVM's constant folding helps. If we could force inlining at call sites, then default arguments could generate

hash(x) = @inline hash(x,uint(0))

but I doubt we want to do that in all cases.

[StefanKarpinski]

In this case, I suspect we might really want to do it in all cases – the hash function is expected to be called with just one argument – the second argument is for Merkle-Damgård chaining.

[StefanKarpinski]

@JeffBezanson, I can't for the life of me figure out why hash(NaN) != hash(big(NaN)). I've verified that the generic hash(::Real, ::Uint) is returning at this line, but the wrong value is somehow getting returned. I moved code around to try to make sure it wasn't #265 again but it didn't help this situation at all (although I like having all the generic code later so I left it there). Any ideas?

[JeffBezanson]

This may be due to LLVM's Demonic Constant Folding™. fptosi is undefined on NaN, so it gives a different answer when the argument is a constant NaN (in which case LLVM knows it is an undefined operation):

julia> bar() = box(Uint64,fptosi(unbox(Float64,NaN)))
bar (generic function with 2 methods)

julia> code_llvm(bar,())

define i64 @julia_bar16866() {
top:
  ret i64 0, !dbg !1324
}

julia> bar(x) = box(Uint64,fptosi(unbox(Float64,x)))
bar (generic function with 2 methods)

julia> bar(NaN)
0x8000000000000000

0 for a constant NaN, 0x8000000000000000 for non-constant. A good fix might be to move the ifelse(isnan(x) to protect the fptosi in hashing.jl:36.

[StefanKarpinski]

Go home, LLVM, you're drunk.

[StefanKarpinski]

This fucking LLVM undefined bullshit completely trashes the performance of float hashing. Pardon the language, but this is just so infuriating. I had this down to almost matching integer hashing performance and this COMPLETELY FUCKING POINTLESS UNDEFINED VALUES CRAP IS SABOTAGING IT.

[JeffBezanson]

But hey, this way LLVM lets you get the wrong answer really fast! You can save one whole instruction!

[StefanKarpinski]

I don't think this is actually a performance optimization on their part – I think this is intentionally inconsistent behavior for your own good, so you don't rely on the undefined behaviors, gasp!

[ihnorton]

Time to write a LuaJIT bytecode backend? :p

[JeffBezanson]

No, it's to make it easier and faster to map languages like C that have undefined behavior. The problem is that the behavior is undefined in the first place. If you're going to have undefined behavior then ok, better make uses of it as obvious as possible. IMO the fix would be to give everything defined behavior by default, and use intrinsics or attributes of some kind to mark that e.g. a denominator can't be zero.

[StefanKarpinski]

I don't think stashing the new key on assignment is going to have a big performance impact. The biggest implication that I could think of was that it might be slightly worse for gc, but that's highly speculative.

[JeffBezanson]

This patch works around the error, but I suspect it is more of a bandaid:

diff --git a/src/gf.c b/src/gf.c
index 6d3a168..9fd0bae 100644
--- a/src/gf.c
+++ b/src/gf.c
@@ -1262,7 +1262,10 @@ static jl_tuple_t *arg_type_tuple(jl_value_t **args, size_t nar
     size_t i;
     for(i=0; i < nargs; i++) {
         jl_value_t *a;
-        if (jl_is_type(args[i])) {
+        if (args[i] == (jl_value_t*)jl_null) {
+            a = args[i];
+        }
+        else if (jl_is_type(args[i])) {
             a = (jl_value_t*)jl_wrap_Type(args[i]);
         }
         else if (!jl_is_tuple(args[i])) {

[StefanKarpinski]

Ok – want to do the merge? There's an obvious conflict (you probably resolved it already), and then just apply your bandaid.

[JeffBezanson]

Ok, the bandaid turns out to cause problems. I'll keep working, and I'll merge when I have something decent.

[JeffBezanson]

I'm worried about isless. I fully understand wanting to synchronize isequal and isless, but it is really odd to have a function that is a total order on floating point numbers but not a total order in general. Order is quite different from equality, since it doesn't apply to all values, and there are prominent examples of types with partial, total, and both kinds of order.

[StefanKarpinski]

Maybe we can do something using cmp for the fallback definition of isless to avoid relying on < directly. Since cmp always has to make a decision, as it were, it avoids some issues. The ordering still need not be total since cmp could return 0 for elements that aren't isequal.

[StefanKarpinski]

We don't actually need isless to be a total order for sorting not to break. What we do need is for exactly one of isless(x,y) or isequal(x,y) or isless(y,x) to be true. In other words, the behavior of -0.0 and 0.0 under < is ok for a custom sort – it just means that -0.0 and 0.0 are unordered, which is not what one wants by default, but sorting works correctly. NaN under < is a different story because none of isless(x,NaN) or isequal(x,NaN) or isless(NaN,x) are ever true for any x.

[JeffBezanson]

I don't understand --- isless(x,NaN) is true for some x. If one of isless(x,y), isequal(x,y), or isless(y,x) is always true, doesn't that imply that isless is a total order?

[StefanKarpinski]

Yes, but none of x < NaN, x == NaN and NaN < x are true, which is why using < to sort floats breaks comparison sorts which assume that one of these has to be the case. There's some confusion going on here because there are many notions of equality in play and the one that is relevant to the mathematical concept of a total ordering doesn't actually make sense because these aren't mathematical objects. Which notion of equality are you using in the antisymmetry axiom?

[JeffBezanson]

I was thinking of isequal as defined in this PR.
I don't feel any of this addresses the core issue: what does isless mean? It could mean "an order that works for some implementations of sorting", but I find that odd.
As it is, sort will now happily sort arrays of sets. Is that what we want?

[JeffBezanson]

ex:

julia> c
Set{Int64}({2,3})

julia> a
Set{Int64}({4,5})

julia> b
Set{Int64}({2})

julia> sort([c,a,b])
3-element Array{Set{Int64},1}:
 Set{Int64}({2,3})
 Set{Int64}({4,5})
 Set{Int64}({2})  

The sorted order is, unsurprisingly, not consistent with the partial order.

[Keno]

Yay!