Hashing BitIntegers.jl Integers is slow

[MSRudolph]

Hello,

I am thankful for your package because bit operations with your integer implementation is much faster than with BigInt. However, my code is quite sensitive to the hashing speed, and it seems like that is slow. See the example below:

using BenchmarkTools
using BitIntegers

val1 = convert(UInt128, 123456789)
val2 = convert(UInt256, val1)
val3 = convert(UInt512, val2)
val4 = convert(UInt1024, val3)
val5 = convert(BigInt, val4)

@btime hash($val1)
@btime hash($val2)
@btime hash($val3)
@btime hash($val4)
@btime hash($val5)

>
3.182 ns (0 allocations: 0 bytes)
33.816 ns (2 allocations: 40 bytes)
55.711 ns (2 allocations: 40 bytes)
67.377 ns (2 allocations: 40 bytes)
3.136 ns (0 allocations: 0 bytes)

This shows up to a 20x slowdown over BigInts. Is there something that can be done?

[sgaure]

I think something like this should be added to BitIntegers:

Either

Base.hash(v::Union{BitIntegers.AbstractBitSigned, BitIntegers.AbstractBitUnsigned}, h::UInt) = 
    Base.hash_integer(v, h)

or

Base.hash(v::Union{BitIntegers.AbstractBitSigned, BitIntegers.AbstractBitUnsigned}, h::UInt) = 
    Base.hash(typeof(v), Base.hash_integer(v, h))

The first one uses only the value of the BitInteger. I.e. uint256"1" and uint512"1" have the same hash. This is how it's done for UInt8, UInt16, etc.

The second one also uses the actual type of the BitInteger.

Such a thing can of course be added by users, but that is type piracy and is generally advised against.

[MSRudolph]

Hi @sgaure, thanks for the reply. I would prefer to not type-pirate in our library (see Hashing BitIntegers.jl Integers is slow MSRudolph/PauliPropagation.jl#65), but we will do it if necessary.

@rfourquet, is there a plan to improve the hashing on your end?

[rfourquet]

Thanks for raising the issue. This will be fixed in #52, which I will probably merge tomorrow and release.

[MSRudolph]

Amazing! I'll happily test this on our end when you release. Thank you @rfourquet

[matthias314]

The new version is still slower than Base.hash_integer:

julia> using BitIntegers, Chairmarks

julia> @define_integers 2048; @define_integers 4096;

julia> for T in (Int256, Int512, Int1024, Int2048, Int4096)
           @show T
           display(@b rand(T) hash(_, UInt(0)), Base.hash_integer(_, UInt(0)))
       end

T = Int256
(23.648 ns, 10.816 ns)
T = Int512
(54.338 ns, 32.521 ns)
T = Int1024
(113.469 ns, 82.837 ns)
T = Int2048
(397.200 ns, 315.200 ns)
T = Int4096
(5.401 μs, 5.095 μs)

Is there a reason not to use Base.hash_integer?

EDIT: hash_integer doesn't agree with hash for more than 64 bits. This rules out hash_integer since the hash has to agree with BigInt.

julia> x = rand(Int256); hash(x), hash(BigInt(x)), Base.hash_integer(x, UInt(0))
(0xb1778d016a70ce21, 0xb1778d016a70ce21, 0xb8eba48d45b3ad6c)

[MSRudolph]

I have indeed also just pirated the hash function, which is on-par.

Base.hash(v::BitIntegers.AbstractBitUnsigned, h::UInt) = Base.hash_integer(v, h)

For our application that is fine because we never mix different int types, or rather we never use BigInt. It would of course be best if this can be fixed more generally.

[matthias314]

I've realized that it's not just BigInt, but also floating-point types. Since isequal(1, 1.0) == true, one needs that the hashes for integers and floats agree. The hash for hardware floats should be fast. I guess this means that one cannot just sequentially hash one 64 byte block of a large integer after another. That could the reason for having two separate functions hash_real and hash_integer.