# Benchmarking Dict against C++ std::unordered\_map

**URL:** https://discourse.julialang.org/t/benchmarking-dict-against-c-std-unordered-map/83669
**Category:** Internals & Design
**Tags:** performance, dictionary
**Created:** [July 2, 2022, 6:36pm UTC](https://discourse.julialang.org/t/benchmarking-dict-against-c-std-unordered-map/83669 "2022-07-02T18:36:15Z")
**Posts on this page:** 7
**Page:** 1

<div class="post-metadata">

### Author: ![greatpet](https://avatars.discourse-cdn.com/v4/letter/g/e495f1/32.png) [@greatpet](https://discourse.julialang.org/u/greatpet)
#### Post date: [July 2, 2022, 6:36pm UTC](https://discourse.julialang.org/t/benchmarking-dict-against-c-std-unordered-map/83669/1 "2022-07-02T18:36:15Z")

</div>

I benchmarked Julia’s dictionary insertion and deletion with the following code,

```julia
function test_julia_dict(n::Int64)
    m = Dict{Int, Int}()
    for i = 1:n
        m[5*i] = i
    end
    for i = 1:n-1
        delete!(m, 5*i)
    end
    return m[5*n]
end

```

I compared against C++'s `std::unordered_map` using g++ 9.4.0. The test is done by exposing an `extern "C"` interface from C++ and accessing the shared library using Julia’s `ccall`. I’ve also tested a standalone C++ version to confirm that `ccall` has essentially zero overhead. For `n=10^7`, The Julia version takes 1.7s, and the C++ version 0.87s on my laptop. I know that there are many third-party hash table libraries which out-perform `std::unordered_map`, so the difference would be even bigger. Is there anything I’ve missed? Also, if I want to use call the C++ `unordered_map` for arbitrary Julia types to speed up programs where this is a bottleneck, is there an easy way to do this? The full Julia and C++ benchmark code is attached below.

C++ code:

```julia
// MyDict.cpp
// Compile with `g++ MyDict.cpp -fPIC -shared -O2 -o MyDict.so`

#include <unordered_map>
#include <cstdint>

std::unordered_map<int64_t, int64_t> *m;

extern "C" void dict_init();
extern "C" void dict_destruct();
extern "C" void dict_setindex(int64_t, int64_t);
extern "C" int64_t dict_getindex(int64_t);
extern "C" void dict_delete(int64_t);

void dict_init() {
        m = new std::unordered_map<int64_t, int64_t>;
}

void dict_destruct() {
        delete m;
}

void dict_setindex(int64_t value, int64_t key) {
        (*m)[key] = value;
}

int64_t dict_getindex(int64_t key) {
        return (*m)[key];
}

void dict_delete(int64_t key) {
        (*m).erase(key);
}

```

Julia code:

```julia
import BenchmarkTools
import Libdl
mydict = Libdl.dlopen("./MyDict.so")
mydict_init = Libdl.dlsym(mydict, :dict_init)
mydict_destruct = Libdl.dlsym(mydict, :dict_destruct)
mydict_setindex = Libdl.dlsym(mydict, :dict_setindex)
mydict_getindex = Libdl.dlsym(mydict, :dict_getindex)
mydict_delete = Libdl.dlsym(mydict, :dict_delete)

function test_mydict(n::Int64)
    ccall(mydict_init, Cvoid, ())
    for i = 1:n
        ccall(mydict_setindex, Cvoid, (Int64, Int64), i, 5*i)
    end
    for i = 1:n-1
        ccall(mydict_delete, Cvoid, (Int64,), 5*i)
    end
    result = ccall(mydict_getindex, Int64, (Int64,), 5*n)
    ccall(mydict_destruct, Cvoid, ())
    return result
end

function test_julia_dict(n::Int64)
    m = Dict{Int, Int}()
    for i = 1:n
        m[5*i] = i
    end
    for i = 1:n-1
        delete!(m, 5*i)
    end
    return m[5*n]
end

BenchmarkTools.@btime test_julia_dict(10^7)

BenchmarkTools.@btime test_mydict(10^7)

```

P.S. I edited the code in the post to use 64-bit integers in both Julia and C++. The timing has not changed noticeably.

---

<div class="post-metadata">

### Author: ![paulmelis](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/paulmelis/32/35063_2.png) [@paulmelis](https://discourse.julialang.org/u/paulmelis)
#### Post date: [July 2, 2022, 6:55pm UTC](https://discourse.julialang.org/t/benchmarking-dict-against-c-std-unordered-map/83669/2 "2022-07-02T18:55:06Z")

</div>

For some reason setting the dict entry in Julia allocates quite a bit, probably causing a slowdown:

```julia
julia> function s(n::Int64)
                  m = Dict{Int, Int}()
                  for i = 1:n
                      m[5*i] = i
                  end
       end
s (generic function with 1 method)

julia> @time s(1000)
  0.000043 seconds (18 allocations: 91.953 KiB)

julia> @time s(1000)
  0.000033 seconds (18 allocations: 91.953 KiB)

julia> @time s(1000)
  0.000033 seconds (18 allocations: 91.953 KiB)

julia> @time s(10000)
  0.000325 seconds (24 allocations: 364.156 KiB)

julia> @time s(10000)
  0.000305 seconds (24 allocations: 364.156 KiB)

julia> @time s(10000)
  0.000305 seconds (24 allocations: 364.156 KiB)

julia> @time s(100000)
  0.004186 seconds (36 allocations: 5.669 MiB)

julia> @time s(100000)
  0.004549 seconds (36 allocations: 5.669 MiB)

julia> @time s(100000)
  0.004584 seconds (36 allocations: 5.669 MiB)

julia> @time s(1000000)
  0.074060 seconds (54 allocations: 65.169 MiB, 13.09% gc time)

julia> @time s(1000000)
  0.068651 seconds (54 allocations: 65.169 MiB, 4.95% gc time)

julia> @time s(1000000)
  0.070122 seconds (54 allocations: 65.169 MiB, 0.70% gc time)

julia> @time s(10000000)
  0.978438 seconds (72 allocations: 541.170 MiB, 18.79% gc time)

julia> @time s(10000000)
  0.770858 seconds (72 allocations: 541.170 MiB, 1.11% gc time)

julia> @time s(10000000)
  0.764971 seconds (72 allocations: 541.170 MiB)

julia> @time s(100000000)
Killed

```

At the end it I even get an out-of-memory kill, I wonder what’s causing all those allocations? Strangely the number of allocs reported is quite small, but they really add up when increasing the number of dict entries set.

```julia
julia> versioninfo()
Julia Version 1.7.3
Commit 742b9abb4d (2022-05-06 12:58 UTC)
Platform Info:
  OS: Linux (x86_64-pc-linux-gnu)
  CPU: Intel(R) Core(TM) i5-4460 CPU @ 3.20GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-12.0.1 (ORCJIT, haswell)

```

---

<div class="post-metadata">

### Author: ![paulmelis](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/paulmelis/32/35063_2.png) [@paulmelis](https://discourse.julialang.org/u/paulmelis)
#### Post date: [July 2, 2022, 7:01pm UTC](https://discourse.julialang.org/t/benchmarking-dict-against-c-std-unordered-map/83669/3 "2022-07-02T19:01:21Z")

</div>

> [@greatpet](#):
>
> // Compile with g++ MyDict.cpp -c -fPIC -O2; gcc -shared -o MyDict.so MyDict.o

By the way, you can do this in one command with `g++ -fPIC -shared -O2 -o MyDict.so MyDict.cpp` (and perhaps use `-O3 -march=native` instead of `-O2` to possibly get more code optimization).

---

<div class="post-metadata">

### Author: ![jar1](https://avatars.discourse-cdn.com/v4/letter/j/c0e974/32.png) [@jar1](https://discourse.julialang.org/u/jar1)
#### Post date: [July 2, 2022, 7:20pm UTC](https://discourse.julialang.org/t/benchmarking-dict-against-c-std-unordered-map/83669/4 "2022-07-02T19:20:20Z")

</div>

See also

> **[GitHub - andyferris/Dictionaries.jl: An alternative interface for...](https://github.com/andyferris/Dictionaries.jl)**
>
> An alternative interface for dictionaries in Julia, for improved productivity and performance - GitHub - andyferris/Dictionaries.jl: An alternative interface for dictionaries in Julia, for improved...

---

<div class="post-metadata">

### Author: ![ImreSamu](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/imresamu/32/20677_2.png) [@ImreSamu](https://discourse.julialang.org/u/ImreSamu)
#### Post date: [July 2, 2022, 10:16pm UTC](https://discourse.julialang.org/t/benchmarking-dict-against-c-std-unordered-map/83669/5 "2022-07-02T22:16:38Z")

</div>

There is a 2022Apr4 patch in the new codebase.  
[https://github.com/JuliaLang/julia/commit/51271e0f2a8b15f5e7abf417d058980561750fe1](https://github.com/JuliaLang/julia/commit/51271e0f2a8b15f5e7abf417d058980561750fe1)

If you didn’t test with the [nightly builds](https://julialang.org/downloads/nightlies/), could you test with that as well?

---

<div class="post-metadata">

### Author: ![gbaraldi](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gbaraldi/32/22101_2.png) [@gbaraldi](https://discourse.julialang.org/u/gbaraldi)
#### Post date: [July 2, 2022, 11:35pm UTC](https://discourse.julialang.org/t/benchmarking-dict-against-c-std-unordered-map/83669/6 "2022-07-02T23:35:11Z")

</div>

On master the C++ code is about twice as fast

---

<div class="post-metadata">

### Author: ![greatpet](https://avatars.discourse-cdn.com/v4/letter/g/e495f1/32.png) [@greatpet](https://discourse.julialang.org/u/greatpet)
#### Post date: [July 3, 2022, 11:27pm UTC](https://discourse.julialang.org/t/benchmarking-dict-against-c-std-unordered-map/83669/7 "2022-07-03T23:27:12Z")

</div>

For smaller problem sizes like `n=10^5`, the Julia version is actually faster than the `ccall` version, so maybe it’s memory allocation slowing down `Dict` for large problem sizes as @paulmelis observed.