Benchmarks

boost::unordered_[multi]set

All benchmarks were created using unordered_set<unsigned int> (non-duplicate) and unordered_multiset<unsigned int> (duplicate). The source code can be found here.

The insertion benchmarks insert n random values, where n is between 10,000 and 3 million. For the duplicated benchmarks, the same random values are repeated an average of 5 times.

The erasure benchmarks erase all n elements randomly until the container is empty. Erasure by key uses erase(const key_type&) to remove entire groups of equivalent elements in each operation.

The successful lookup benchmarks are done by looking up all n values, in their original insertion order.

The unsuccessful lookup benchmarks use n randomly generated integers but using a different seed value.

GCC 12 + libstdc++-v3, x64

Insertion

running insertion.xlsx.practice
running insertion.xlsx.practice non unique
running insertion.xlsx.practice non unique 5

non-duplicate elements

duplicate elements

duplicate elements,
max load factor 5

running insertion.xlsx.practice norehash
running insertion.xlsx.practice norehash non unique
running insertion.xlsx.practice norehash non unique 5

non-duplicate elements,
prior reserve

duplicate elements,
prior reserve

duplicate elements,
max load factor 5,
prior reserve

Erasure

scattered erasure.xlsx.practice
scattered erasure.xlsx.practice non unique
scattered erasure.xlsx.practice non unique 5

non-duplicate elements

duplicate elements

duplicate elements,
max load factor 5

scattered erasure by key.xlsx.practice non unique
scattered erasure by key.xlsx.practice non unique 5

by key, duplicate elements

by key, duplicate elements,
max load factor 5

Successful Lookup

scattered successful looukp.xlsx.practice
scattered successful looukp.xlsx.practice non unique
scattered successful looukp.xlsx.practice non unique 5

non-duplicate elements

duplicate elements

duplicate elements,
max load factor 5

Unsuccessful lookup

scattered unsuccessful looukp.xlsx.practice
scattered unsuccessful looukp.xlsx.practice non unique
scattered unsuccessful looukp.xlsx.practice non unique 5

non-duplicate elements

duplicate elements

duplicate elements,
max load factor 5

Clang 15 + libc++, x64

Insertion

running insertion.xlsx.practice
running insertion.xlsx.practice non unique
running insertion.xlsx.practice non unique 5

non-duplicate elements

duplicate elements

duplicate elements,
max load factor 5

running insertion.xlsx.practice norehash
running insertion.xlsx.practice norehash non unique
running insertion.xlsx.practice norehash non unique 5

non-duplicate elements,
prior reserve

duplicate elements,
prior reserve

duplicate elements,
max load factor 5,
prior reserve

Erasure

scattered erasure.xlsx.practice
scattered erasure.xlsx.practice non unique
scattered erasure.xlsx.practice non unique 5

non-duplicate elements

duplicate elements

duplicate elements,
max load factor 5

scattered erasure by key.xlsx.practice non unique
scattered erasure by key.xlsx.practice non unique 5

by key, duplicate elements

by key, duplicate elements,
max load factor 5

Successful lookup

scattered successful looukp.xlsx.practice
scattered successful looukp.xlsx.practice non unique
scattered successful looukp.xlsx.practice non unique 5

non-duplicate elements

duplicate elements

duplicate elements,
max load factor 5

Unsuccessful lookup

scattered unsuccessful looukp.xlsx.practice
scattered unsuccessful looukp.xlsx.practice non unique
scattered unsuccessful looukp.xlsx.practice non unique 5

non-duplicate elements

duplicate elements

duplicate elements,
max load factor 5

Visual Studio 2022 + Dinkumware, x64

Insertion

running insertion.xlsx.practice
running insertion.xlsx.practice non unique
running insertion.xlsx.practice non unique 5

non-duplicate elements

duplicate elements

duplicate elements,
max load factor 5

running insertion.xlsx.practice norehash
running insertion.xlsx.practice norehash non unique
running insertion.xlsx.practice norehash non unique 5

non-duplicate elements,
prior reserve

duplicate elements,
prior reserve

duplicate elements,
max load factor 5,
prior reserve

Erasure

scattered erasure.xlsx.practice
scattered erasure.xlsx.practice non unique
scattered erasure.xlsx.practice non unique 5

non-duplicate elements

duplicate elements

duplicate elements,
max load factor 5

scattered erasure by key.xlsx.practice non unique
scattered erasure by key.xlsx.practice non unique 5

by key, duplicate elements

by key, duplicate elements,
max load factor 5

Successful lookup

scattered successful looukp.xlsx.practice
scattered successful looukp.xlsx.practice non unique
scattered successful looukp.xlsx.practice non unique 5

non-duplicate elements

duplicate elements

duplicate elements,
max load factor 5

Unsuccessful lookup

scattered unsuccessful looukp.xlsx.practice
scattered unsuccessful looukp.xlsx.practice non unique
scattered unsuccessful looukp.xlsx.practice non unique 5

non-duplicate elements

duplicate elements

duplicate elements,
max load factor 5

boost::unordered_(flat|node)_map

All benchmarks were created using:

  • absl::flat_hash_map<uint64_t, uint64_t>

  • boost::unordered_map<uint64_t, uint64_t>

  • boost::unordered_flat_map<uint64_t, uint64_t>

  • boost::unordered_node_map<uint64_t, uint64_t>

The source code can be found here.

The insertion benchmarks insert n random values, where n is between 10,000 and 10 million.

The erasure benchmarks erase traverse the n elements and erase those with odd key (50% on average).

The successful lookup benchmarks are done by looking up all n values, in their original insertion order.

The unsuccessful lookup benchmarks use n randomly generated integers but using a different seed value.

GCC 12, x64

Running insertion.xlsx.plot
Running erasure.xlsx.plot
Scattered successful looukp.xlsx.plot
Scattered unsuccessful looukp.xlsx.plot

running insertion

running erasure

successful lookup

unsuccessful lookup

Clang 15, x64

Running insertion.xlsx.plot
Running erasure.xlsx.plot
Scattered successful looukp.xlsx.plot
Scattered unsuccessful looukp.xlsx.plot

running insertion

running erasure

successful lookup

unsuccessful lookup

Visual Studio 2022, x64

Running insertion.xlsx.plot
Running erasure.xlsx.plot
Scattered successful looukp.xlsx.plot
Scattered unsuccessful looukp.xlsx.plot

running insertion

running erasure

successful lookup

unsuccessful lookup

Clang 12, ARM64

Running insertion.xlsx.plot
Running erasure.xlsx.plot
Scattered successful looukp.xlsx.plot
Scattered unsuccessful looukp.xlsx.plot

running insertion

running erasure

successful lookup

unsuccessful lookup

GCC 12, x86

Running insertion.xlsx.plot
Running erasure.xlsx.plot
Scattered successful looukp.xlsx.plot
Scattered unsuccessful looukp.xlsx.plot

running insertion

running erasure

successful lookup

unsuccessful lookup

Clang 15, x86

Running insertion.xlsx.plot
Running erasure.xlsx.plot
Scattered successful looukp.xlsx.plot
Scattered unsuccessful looukp.xlsx.plot

running insertion

running erasure

successful lookup

unsuccessful lookup

Visual Studio 2022, x86

Running insertion.xlsx.plot
Running erasure.xlsx.plot
Scattered successful looukp.xlsx.plot
Scattered unsuccessful looukp.xlsx.plot

running insertion

running erasure

successful lookup

unsuccessful lookup

boost::concurrent_(flat|node)_map

All benchmarks were created using:

The source code can be found here.

The benchmarks exercise a number of threads T (between 1 and 16) concurrently performing operations randomly chosen among update, successful lookup and unsuccessful lookup. The keys used in the operations follow a Zipf distribution with different skew parameters: the higher the skew, the more concentrated are the keys in the lower values of the covered range.

boost::concurrent_flat_map and boost::concurrent_node_map are exercised using both regular and bulk visitation: in the latter case, lookup keys are buffered in a local array and then processed at once each time the buffer reaches bulk_visit_size.

GCC 12, x64

Parallel workload.xlsx.500k, 0.01
Parallel workload.xlsx.500k, 0.5
Parallel workload.xlsx.500k, 0.99

500k updates, 4.5M lookups
skew=0.01

500k updates, 4.5M lookups
skew=0.5

500k updates, 4.5M lookups
skew=0.99

Parallel workload.xlsx.5M, 0.01
Parallel workload.xlsx.5M, 0.5
Parallel workload.xlsx.5M, 0.99

5M updates, 45M lookups
skew=0.01

5M updates, 45M lookups
skew=0.5

5M updates, 45M lookups
skew=0.99

Clang 15, x64

Parallel workload.xlsx.500k, 0.01
Parallel workload.xlsx.500k, 0.5
Parallel workload.xlsx.500k, 0.99

500k updates, 4.5M lookups
skew=0.01

500k updates, 4.5M lookups
skew=0.5

500k updates, 4.5M lookups
skew=0.99

Parallel workload.xlsx.5M, 0.01
Parallel workload.xlsx.5M, 0.5
Parallel workload.xlsx.5M, 0.99

5M updates, 45M lookups
skew=0.01

5M updates, 45M lookups
skew=0.5

5M updates, 45M lookups
skew=0.99

Visual Studio 2022, x64

Parallel workload.xlsx.500k, 0.01
Parallel workload.xlsx.500k, 0.5
Parallel workload.xlsx.500k, 0.99

500k updates, 4.5M lookups
skew=0.01

500k updates, 4.5M lookups
skew=0.5

500k updates, 4.5M lookups
skew=0.99

Parallel workload.xlsx.5M, 0.01
Parallel workload.xlsx.5M, 0.5
Parallel workload.xlsx.5M, 0.99

5M updates, 45M lookups
skew=0.01

5M updates, 45M lookups
skew=0.5

5M updates, 45M lookups
skew=0.99

Clang 12, ARM64

Parallel workload.xlsx.500k, 0.01
Parallel workload.xlsx.500k, 0.5
Parallel workload.xlsx.500k, 0.99

500k updates, 4.5M lookups
skew=0.01

500k updates, 4.5M lookups
skew=0.5

500k updates, 4.5M lookups
skew=0.99

Parallel workload.xlsx.5M, 0.01
Parallel workload.xlsx.5M, 0.5
Parallel workload.xlsx.5M, 0.99

5M updates, 45M lookups
skew=0.01

5M updates, 45M lookups
skew=0.5

5M updates, 45M lookups
skew=0.99

GCC 12, x86

Parallel workload.xlsx.500k, 0.01
Parallel workload.xlsx.500k, 0.5
Parallel workload.xlsx.500k, 0.99

500k updates, 4.5M lookups
skew=0.01

500k updates, 4.5M lookups
skew=0.5

500k updates, 4.5M lookups
skew=0.99

Parallel workload.xlsx.5M, 0.01
Parallel workload.xlsx.5M, 0.5
Parallel workload.xlsx.5M, 0.99

5M updates, 45M lookups
skew=0.01

5M updates, 45M lookups
skew=0.5

5M updates, 45M lookups
skew=0.99

Clang 15, x86

Parallel workload.xlsx.500k, 0.01
Parallel workload.xlsx.500k, 0.5
Parallel workload.xlsx.500k, 0.99

500k updates, 4.5M lookups
skew=0.01

500k updates, 4.5M lookups
skew=0.5

500k updates, 4.5M lookups
skew=0.99

Parallel workload.xlsx.5M, 0.01
Parallel workload.xlsx.5M, 0.5
Parallel workload.xlsx.5M, 0.99

5M updates, 45M lookups
skew=0.01

5M updates, 45M lookups
skew=0.5

5M updates, 45M lookups
skew=0.99

Visual Studio 2022, x86

Parallel workload.xlsx.500k, 0.01
Parallel workload.xlsx.500k, 0.5
Parallel workload.xlsx.500k, 0.99

500k updates, 4.5M lookups
skew=0.01

500k updates, 4.5M lookups
skew=0.5

500k updates, 4.5M lookups
skew=0.99

Parallel workload.xlsx.5M, 0.01
Parallel workload.xlsx.5M, 0.5
Parallel workload.xlsx.5M, 0.99

5M updates, 45M lookups
skew=0.01

5M updates, 45M lookups
skew=0.5

5M updates, 45M lookups
skew=0.99