# Fast hash for custom type

**URL:** <https://discourse.julialang.org/t/fast-hash-for-custom-type/68135>\
**Category:** General Usage\
**Tags:** question, performance, hash\
**Created:** [September 14, 2021, 9:26am UTC](https://discourse.julialang.org/t/fast-hash-for-custom-type/68135 "2021-09-14T09:26:48Z")\
**Posts on this page:** 11\
**Page:** 1

<div class="post-metadata">

**Author:** ![jw3126](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jw3126/32/3086_2.png) [@jw3126](https://discourse.julialang.org/u/jw3126)\
**Post date:** [September 14, 2021, 9:26am UTC](https://discourse.julialang.org/t/fast-hash-for-custom-type/68135/1 "2021-09-14T09:26:48Z")

</div>

We have a custom type and we are not satisfied with the `Base.hash` performance. See [here](https://github.com/jw3126/Setfield.jl/pull/162) for the real world example.  
What are the best practice for defining a custom hash? This is what we did:

```julia

julia> struct S{T}; value::T; end

julia> s = S(1)
S{Int64}(1)

julia> seed = UInt(1)
0x0000000000000001

julia> using BenchmarkTools; @btime hash($s, $seed)
  6.990 ns (0 allocations: 0 bytes)
0xbee890e79d476a32

julia> objectid(S)
0x3ae5cb9a575935b6

julia> function myhash(s, seed)
           salt = 0x3ae5cb9a575935b6
           hash(s.value, hash(salt, seed))
       end
myhash (generic function with 1 method)

julia> @btime myhash($s, $seed)
  0.020 ns (0 allocations: 0 bytes)
0x85f4c910a0ba7fed

```

Is this a sane approach? Any problems with this?

---

<div class="post-metadata">

**Author:** ![JeffreySarnoff](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jeffreysarnoff/32/1980_2.png) [@JeffreySarnoff](https://discourse.julialang.org/u/JeffreySarnoff)\
**Post date:** [September 14, 2021, 10:27am UTC](https://discourse.julialang.org/t/fast-hash-for-custom-type/68135/2 "2021-09-14T10:27:55Z")

</div>

from the docs

> hash(x[, h::UInt]) → UInt
> 
> Compute an integer hash code such that isequal(x,y) implies hash(x)==hash(y).  
> The optional second argument h is a hash code to be mixed with the result.
> 
> _New types should implement the 2-argument form_, typically by calling the  
> 2-argument hash method recursively in order to mix hashes of the contents with  
> each other (and with h).

e.g. (using these constants)

```julia
const lens_seed = UInt === UInt64 ? 0x8aa710fd8cb95e7e : 0x4fdb9639

function Base.hash(x::Setfield.IndexLens{I}, h::UInt) where {I<:Tuple}
   h += lens_seed
   return hash(x.indices, h)
end

```

---

<div class="post-metadata">

**Author:** ![Sukera](https://avatars.discourse-cdn.com/v4/letter/s/ce7236/32.png) [@Sukera](https://discourse.julialang.org/u/Sukera)\
**Post date:** [September 14, 2021, 10:30am UTC](https://discourse.julialang.org/t/fast-hash-for-custom-type/68135/3 "2021-09-14T10:30:05Z")

</div>

> [@jw3126](#):
>
> ```julia
> julia> @btime myhash($s, $seed)
> 0.020 ns (0 allocations: 0 bytes)
> 0x85f4c910a0ba7fed
> 
> ```

That time looks like constant-folded compiler shenanigans to me. Try with

```julia
@btime myhash($(Ref(s))[], $(Ref(seed))[]) 

```

instead.

---

<div class="post-metadata">

**Author:** ![Sukera](https://avatars.discourse-cdn.com/v4/letter/s/ce7236/32.png) [@Sukera](https://discourse.julialang.org/u/Sukera)\
**Post date:** [September 14, 2021, 10:32am UTC](https://discourse.julialang.org/t/fast-hash-for-custom-type/68135/4 "2021-09-14T10:32:00Z")

</div>

The same goes for the benchmarks in the linked issue imo.

---

<div class="post-metadata">

**Author:** ![jw3126](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jw3126/32/3086_2.png) [@jw3126](https://discourse.julialang.org/u/jw3126)\
**Post date:** [September 14, 2021, 10:32am UTC](https://discourse.julialang.org/t/fast-hash-for-custom-type/68135/5 "2021-09-14T10:32:34Z")

</div>

> That time looks like constant-folded compiler shenanigans to me.

Right! (though I was happy to see, that in contrast to the default hash, the compiler can constant fold this one.)

```julia
julia> @btime myhash($(Ref(s))[], $(Ref(seed))[])
  1.793 ns (0 allocations: 0 bytes)

```

---

<div class="post-metadata">

**Author:** ![Sukera](https://avatars.discourse-cdn.com/v4/letter/s/ce7236/32.png) [@Sukera](https://discourse.julialang.org/u/Sukera)\
**Post date:** [September 14, 2021, 10:33am UTC](https://discourse.julialang.org/t/fast-hash-for-custom-type/68135/6 "2021-09-14T10:33:45Z")

</div>

What’s the timing for regular `hash` on your system? With the same `Ref` trick of course.

---

<div class="post-metadata">

**Author:** ![jw3126](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jw3126/32/3086_2.png) [@jw3126](https://discourse.julialang.org/u/jw3126)\
**Post date:** [September 14, 2021, 10:35am UTC](https://discourse.julialang.org/t/fast-hash-for-custom-type/68135/7 "2021-09-14T10:35:04Z")

</div>

```julia

julia> using BenchmarkTools; @btime hash($s, $seed)
  6.990 ns (0 allocations: 0 bytes)
julia> using BenchmarkTools; @btime hash($(Ref(s))[], $(Ref(seed))[])
7.301 ns (0 allocations: 0 bytes)

```

hash calles `objectid`, which does a ccall. It seems this ccall is the bottle neck.

---

<div class="post-metadata">

**Author:** ![jw3126](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jw3126/32/3086_2.png) [@jw3126](https://discourse.julialang.org/u/jw3126)\
**Post date:** [September 14, 2021, 10:48am UTC](https://discourse.julialang.org/t/fast-hash-for-custom-type/68135/8 "2021-09-14T10:48:25Z")

</div>

@JeffreySarnoff How did you come up with the values for the constant in the 32bit case and why  
`h += lens_seed` and not `h = hash(lens_seed, h)` ?

```julia
const lens_seed = UInt === UInt64 ? 0x8aa710fd8cb95e7e : 0x4fdb9639

function Base.hash(x::IndexLens{I}, h::UInt) where {I<:Tuple}
   h += lens_seed
   return hash(x.indices, h)
end

```

---

<div class="post-metadata">

**Author:** ![JeffreySarnoff](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jeffreysarnoff/32/1980_2.png) [@JeffreySarnoff](https://discourse.julialang.org/u/JeffreySarnoff)\
**Post date:** [September 14, 2021, 10:57am UTC](https://discourse.julialang.org/t/fast-hash-for-custom-type/68135/9 "2021-09-14T10:57:23Z")

</div>

The 64-bit constant comes from [you](https://github.com/jw3126/Setfield.jl/pull/162#issuecomment-918963521).

```julia
julia> s64 = 0x8aa710fd8cb95e7e
0x8aa710fd8cb95e7e

julia> s32 = UInt32(s64 >> 32) ⊻ UInt32(s64 & 0x00000000ffffffff)
0x061e4e83 # Palli corrected this (see next in thread)

```

They can be whatever you prefer, although they should not be known to clash with another type’s similar constants.

`h += lens_seed` is faster than `h = hash(lens_seed, h)` and all you want to do before calling the inner `hash(x.indicies, h)` is to morph the incoming `h` in some way that is consistent for `IndexLens`. I copied the `+=` approach from `Base/hashing.jl`, for hashing a String and from `Base/tuples.jl` hashing.

```julia

```

---

<div class="post-metadata">

**Author:** ![Palli](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/palli/32/3380_2.png) [@Palli](https://discourse.julialang.org/u/Palli)\
**Post date:** [September 17, 2021, 12:15pm UTC](https://discourse.julialang.org/t/fast-hash-for-custom-type/68135/10 "2021-09-17T12:15:37Z")

</div>

> [@JeffreySarnoff](#):
>
> ```julia
> julia> s32 = UInt32(s64 >> 32) ^ UInt32(s64 & 0x00000000ffffffff)
> 0x4fdb9639
> 
> ```

Was this supposed to be:

```julia
julia> s32 = UInt32(s64 >> 32) ⊻ UInt32(s64 & 0x00000000ffffffff)
0x061e4e83

```

In Julia `^` is always exponentiation, as I think you may know, not `xor` like in some other languages. I’m just making sure, maybe any mixing works. [You can also use the xor function or Unicode operator type \xor tab.]

---

<div class="post-metadata">

**Author:** ![JeffreySarnoff](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jeffreysarnoff/32/1980_2.png) [@JeffreySarnoff](https://discourse.julialang.org/u/JeffreySarnoff)\
**Post date:** [September 17, 2021, 12:45pm UTC](https://discourse.julialang.org/t/fast-hash-for-custom-type/68135/11 "2021-09-17T12:45:34Z")

</div>

**Yes** … _forgetting to forget C_