# Really Fast Hash Set and Map

**URL:** <https://discourse.julialang.org/t/really-fast-hash-set-and-map/14190>\
**Category:** Internals & Design\
**Created:** [August 28, 2018, 1:35pm UTC](https://discourse.julialang.org/t/really-fast-hash-set-and-map/14190 "2018-08-28T13:35:35Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![nordlow](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nordlow/32/4970_2.png) [@nordlow](https://discourse.julialang.org/u/nordlow)\
**Post date:** [August 28, 2018, 1:35pm UTC](https://discourse.julialang.org/t/really-fast-hash-set-and-map/14190/1 "2018-08-28T13:35:35Z")

</div>

Does Julia have a fast generic implementation of hashed data structures, that is hash table and hash sets?

Is the builtin `Dict()` as fast as in languages such as C++, Rust and D?

Are there alternatives or examples of collections I could modify to make Julia have such a collection?

I’m currently interested in a hash table/set with open addressing.

---

<div class="post-metadata">

**Author:** ![StefanKarpinski](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stefankarpinski/32/24_2.png) [@StefanKarpinski](https://discourse.julialang.org/u/StefanKarpinski)\
**Post date:** [August 28, 2018, 1:46pm UTC](https://discourse.julialang.org/t/really-fast-hash-set-and-map/14190/2 "2018-08-28T13:46:12Z")

</div>

> [@nordlow](#):
>
> AFAICT, the builtin `Dict()` is really slow compared implementations in languages such as C++, Rust and D.

How are you measuring this? Can you share some benchmark results.

---

<div class="post-metadata">

**Author:** ![ExpandingMan](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/expandingman/32/866_2.png) [@ExpandingMan](https://discourse.julialang.org/u/ExpandingMan)\
**Post date:** [August 28, 2018, 1:59pm UTC](https://discourse.julialang.org/t/really-fast-hash-set-and-map/14190/3 "2018-08-28T13:59:48Z")

</div>

> [@nordlow](#):
>
> AFAICT, the builtin `Dict()` is really slow compared implementations in languages such as C++, Rust and D.

```julia
julia> using BenchmarkTools

julia> dict = Dict((1:10^5) .=> rand(10^5));

julia> @benchmark dict[100]
BenchmarkTools.Trial: 
  memory estimate: 16 bytes
  allocs estimate: 1
  --------------
  minimum time: 23.364 ns (0.00% GC)
  median time: 23.941 ns (0.00% GC)
  mean time: 30.599 ns (17.99% GC)
  maximum time: 40.852 μs (99.93% GC)
  --------------
  samples: 10000
  evals/sample: 996

julia> dict = Dict([randstring(10) for i ∈ 1:10^5] .=> rand(10^5));

julia> typeof(ans)
Dict{String,Float64}

julia> @benchmark dict[$(first(keys(dict)))]
BenchmarkTools.Trial: 
  memory estimate: 16 bytes
  allocs estimate: 1
  --------------
  minimum time: 39.205 ns (0.00% GC)
  median time: 39.570 ns (0.00% GC)
  mean time: 46.894 ns (13.25% GC)
  maximum time: 46.967 μs (99.90% GC)
  --------------
  samples: 10000
  evals/sample: 992

```

That seems pretty damn fast, I’m really doubtful that there are any implementations out there much faster than that except for possibly object ID dicts (which are available in Julia, by the way). This is also on a rather slow laptop CPU. Granted this doesn’t necessarily guarantee that every object has efficient hashing, perhaps there are some common objects which have poor hashing?

---

<div class="post-metadata">

**Author:** ![nordlow](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nordlow/32/4970_2.png) [@nordlow](https://discourse.julialang.org/u/nordlow)\
**Post date:** [August 28, 2018, 2:17pm UTC](https://discourse.julialang.org/t/really-fast-hash-set-and-map/14190/4 "2018-08-28T14:17:30Z")

</div>

> [@ExpandingMan](#):
>
> dict = Dict((1:10^5) .=\> rand(10^5));

What does `dict[100]` do?

---

<div class="post-metadata">

**Author:** ![nordlow](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nordlow/32/4970_2.png) [@nordlow](https://discourse.julialang.org/u/nordlow)\
**Post date:** [August 28, 2018, 2:17pm UTC](https://discourse.julialang.org/t/really-fast-hash-set-and-map/14190/5 "2018-08-28T14:17:33Z")

</div>

Ahh, `dict[100]` looks up value of element with key `100`. I could have guessed that…

---

<div class="post-metadata">

**Author:** ![nordlow](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nordlow/32/4970_2.png) [@nordlow](https://discourse.julialang.org/u/nordlow)\
**Post date:** [August 28, 2018, 2:17pm UTC](https://discourse.julialang.org/t/really-fast-hash-set-and-map/14190/6 "2018-08-28T14:17:35Z")

</div>

How can I check which hashing that is used here?

---

<div class="post-metadata">

**Author:** ![nordlow](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nordlow/32/4970_2.png) [@nordlow](https://discourse.julialang.org/u/nordlow)\
**Post date:** [August 28, 2018, 2:17pm UTC](https://discourse.julialang.org/t/really-fast-hash-set-and-map/14190/7 "2018-08-28T14:17:36Z")

</div>

The fastest hash-table lookups with open addressing on C++, Rust and D with FNV-hasher are around 3-10 ns.

---

<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:** [August 28, 2018, 2:25pm UTC](https://discourse.julialang.org/t/really-fast-hash-set-and-map/14190/8 "2018-08-28T14:25:40Z")

</div>

It really depends on what you hash - there’s different implementations for different types. You can check them [here](https://github.com/JuliaLang/julia/blob/master/base/hashing.jl) and [here](https://github.com/JuliaLang/julia/blob/master/base/hashing2.jl). There may be other reasons beside performance for why each implementation was chosen - @StefanKarpinski may be able to shed some light on that, based on the git blame for those files.

---

<div class="post-metadata">

**Author:** ![gdkrmr](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdkrmr/32/2791_2.png) [@gdkrmr](https://discourse.julialang.org/u/gdkrmr)\
**Post date:** [August 28, 2018, 2:26pm UTC](https://discourse.julialang.org/t/really-fast-hash-set-and-map/14190/9 "2018-08-28T14:26:11Z")

</div>

I have used quite large `Dict`s and `ObjectIdDict`s and they were reasonably fast for the task (I have not benchmarked other hash tables to compare) with the exception of rehashing `ObjectIdDict` which takes hours when it reaches a certain size. `sizehint!` is your friend here if you know the approximate size of your `Dict`.

---

<div class="post-metadata">

**Author:** ![ExpandingMan](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/expandingman/32/866_2.png) [@ExpandingMan](https://discourse.julialang.org/u/ExpandingMan)\
**Post date:** [August 28, 2018, 2:35pm UTC](https://discourse.julialang.org/t/really-fast-hash-set-and-map/14190/10 "2018-08-28T14:35:57Z")

</div>

Hm, note also

```julia
julia> A = rand(5);

julia> using BenchmarkTools

julia> @benchmark A[$1]
BenchmarkTools.Trial: 
  memory estimate: 16 bytes
  allocs estimate: 1
  --------------
  minimum time: 20.913 ns (0.00% GC)
  median time: 21.449 ns (0.00% GC)
  mean time: 28.138 ns (19.46% GC)
  maximum time: 40.808 μs (99.93% GC)
  --------------
  samples: 10000
  evals/sample: 996

```

I seem to remember at some point understanding the reason why that seems slow, but right now I can’t think of what that might be and this strikes me as slow. Perhaps I’m just wrong and that’s a reasonable number.

On the bright side, it seems like hashing alone is really damn fast.

---

<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:** [August 28, 2018, 2:37pm UTC](https://discourse.julialang.org/t/really-fast-hash-set-and-map/14190/11 "2018-08-28T14:37:57Z")

</div>

yep, hashing alone is fast:

```julia
julia> @benchmark hash(rand(Int))
BenchmarkTools.Trial:
  memory estimate: 0 bytes
  allocs estimate: 0
  --------------
  minimum time: 6.000 ns (0.00% GC)
  median time: 9.000 ns (0.00% GC)
  mean time: 9.426 ns (0.00% GC)
  maximum time: 387.000 ns (0.00% GC)
  --------------
  samples: 10000
  evals/sample: 1000

```

Note though, this includes the overhead of calling `rand(Int)`. With a static number we get this (not really representative thing):

```julia
julia> x = rand(Int)
3888178585692376031

julia> @benchmark hash($x)
BenchmarkTools.Trial:
  memory estimate: 0 bytes
  allocs estimate: 0
  --------------
  minimum time: 3.000 ns (0.00% GC)
  median time: 4.000 ns (0.00% GC)
  mean time: 3.910 ns (0.00% GC)
  maximum time: 27.000 ns (0.00% GC)
  --------------
  samples: 10000
  evals/sample: 1000

```

---

<div class="post-metadata">

**Author:** ![traktofon](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/traktofon/32/591_2.png) [@traktofon](https://discourse.julialang.org/u/traktofon)\
**Post date:** [August 28, 2018, 2:50pm UTC](https://discourse.julialang.org/t/really-fast-hash-set-and-map/14190/12 "2018-08-28T14:50:50Z")

</div>

`dict` and `A` should also be interpolated when benchmarking:

```julia
julia> dict = Dict((1:10^5) .=> rand(10^5));

julia> @btime dict[100];
  19.629 ns (1 allocation: 16 bytes)

julia> @btime $dict[100];
  5.420 ns (0 allocations: 0 bytes)

julia> A=rand(5);

julia> @btime A[1];
  14.997 ns (1 allocation: 16 bytes)

julia> @btime $A[1];
  1.303 ns (0 allocations: 0 bytes)

```

---

<div class="post-metadata">

**Author:** ![nordlow](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nordlow/32/4970_2.png) [@nordlow](https://discourse.julialang.org/u/nordlow)\
**Post date:** [August 28, 2018, 5:17pm UTC](https://discourse.julialang.org/t/really-fast-hash-set-and-map/14190/13 "2018-08-28T17:17:19Z")

</div>

Cool. Can somebody please explain what interpolated means in this context. I only know about numerical interpolation and string interpolation in Julia. I am guessing it has to do with scope and local variables vs global variables.

Further, what’s the difference between @btime and normal @time in this context.

Also, how can I check what hashing algorithm that is used by default for different types.

---

<div class="post-metadata">

**Author:** ![ExpandingMan](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/expandingman/32/866_2.png) [@ExpandingMan](https://discourse.julialang.org/u/ExpandingMan)\
**Post date:** [August 28, 2018, 5:23pm UTC](https://discourse.julialang.org/t/really-fast-hash-set-and-map/14190/14 "2018-08-28T17:23:43Z")

</div>

`@time` literally just puts a timer around your code, so you might be including times other than the execution of your code like, especially, compile time. You’ve probably noticed that `@time` tends to be much faster after you run it on the same function a couple of times. `@btime` ensures that it only measures the actual execution of code.

In this context and interpolated value means a value that was computed before it goes into benchmarking. For example `@btime x[$(rand(1:3))]` executes `rand` before benchmarking, stores the value and uses that value as input to the benchmark.

Also, the `@edit` macro is extremely useful. Try, for example `@edit rand()`.

---

<div class="post-metadata">

**Author:** ![Evizero](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/evizero/32/10118_2.png) [@Evizero](https://discourse.julialang.org/u/Evizero)\
**Post date:** [August 28, 2018, 5:30pm UTC](https://discourse.julialang.org/t/really-fast-hash-set-and-map/14190/15 "2018-08-28T17:30:23Z")

</div>

> [@nordlow](#):
>
> Cool. Can somebody please explain what interpolated means in this context. I only know about numerical interpolation and string interpolation in Julia. I am guessing it has to do with scope and local variables vs global variables.

In this context its expression interpolation. Its a metaprogramming concept. Here `$A` basically says “instead of using a reference to variable `A`, just replace it with its value”.

```julia
julia> A = 2
2

julia> :(A + 2)
:(A + 2)

julia> :($A + 2)
:(2 + 2)

```

> [@nordlow](#):
>
> Further, what’s the difference between @btime and normal @time in this context.

I think a good first impression is given here: [GitHub - JuliaCI/BenchmarkTools.jl: A benchmarking framework for the Julia language](https://github.com/JuliaCI/BenchmarkTools.jl#quick-start)

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [August 28, 2018, 5:52pm UTC](https://discourse.julialang.org/t/really-fast-hash-set-and-map/14190/16 "2018-08-28T17:52:54Z")

</div>

> [@Evizero](#):
>
> > Can somebody please explain what interpolated means in this context. I only know about numerical interpolation and string interpolation in Julia. I am guessing it has to do with scope and local variables vs global variables.
> 
> In this context its expression interpolation. Its a metaprogramming concept. Here `$A` basically says “instead of using a reference to variable `A` , just replace it with its value”.

Yes, and in particular it is used by `@btime` to allow you to benchmark expressions involving global variables without paying the usual performance price in Julia for working with globals.

Without interpolation, an expression like `@btime dict[3]` is including the time to look up the type of `dict` and determine (dynamically) the correct `getindex` method to call for `getindex(dict, 3)` (= `dict[3]`), because `dict` is a non-constant global variable. This is typically not what you want, because real performance-sensitive code in Julia will normally occur in functions and act on local variables whose types are known to the compiler. By doing `@btime $dict[3]`, it interpolates the _value_ of `dict` into the expression, and allows the `@btime` macro to time it with the type known at compile time.

---

<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:** [August 28, 2018, 6:03pm UTC](https://discourse.julialang.org/t/really-fast-hash-set-and-map/14190/17 "2018-08-28T18:03:15Z")

</div>

> [@nordlow](#):
>
> Also, how can I check what hashing algorithm that is used by default for different types.

Check the links to github I posted before, you should find the implementations there. As far as I’m aware, there’s no formal description of which algorithm is used precisely and why.

---

<div class="post-metadata">

**Author:** ![kristoffer.carlsson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/kristoffer.carlsson/32/22_2.png) [@kristoffer.carlsson](https://discourse.julialang.org/u/kristoffer.carlsson)\
**Post date:** [August 29, 2018, 11:46am UTC](https://discourse.julialang.org/t/really-fast-hash-set-and-map/14190/18 "2018-08-29T11:46:10Z")

</div>

The is still a need to substantiate

> [@nordlow](#):
>
> AFAICT, the builtin `Dict()` is really slow compared implementations in languages such as C++, Rust and D.

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [August 29, 2018, 11:56am UTC](https://discourse.julialang.org/t/really-fast-hash-set-and-map/14190/19 "2018-08-29T11:56:44Z")

</div>

> [@nordlow](#):
>
> The fastest hash-table lookups with open addressing on C++, Rust and D with FNV-hasher are around 3-10 ns.

> [@traktofon](#):
>
> ```julia
> julia> dict = Dict((1:10^5) .=> rand(10^5));
> [...]
> julia> @btime $dict[100];
> 5.420 ns (0 allocations: 0 bytes)
> 
> ```

> [@kristoffer.carlsson](#):
>
> The is still a need to substantiate

My impression is that it was merely a benchmarking user issue.

---

<div class="post-metadata">

**Author:** ![StefanKarpinski](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stefankarpinski/32/24_2.png) [@StefanKarpinski](https://discourse.julialang.org/u/StefanKarpinski)\
**Post date:** [August 29, 2018, 12:14pm UTC](https://discourse.julialang.org/t/really-fast-hash-set-and-map/14190/20 "2018-08-29T12:14:02Z")

</div>

It’s worth looking into thoroughly though.

[Next page](https://discourse.julialang.org/t/really-fast-hash-set-and-map/14190.md?page=2)