boost_unordered_benchmarks/README.md

boost::unordered_[multi]set benchmarks

Automated benchmarks of boost::unordered_[multi]set against std::unordered_[multi]set and Boost.MultiIndex.

Benchmarks

• unique_running_insertion.cpp: insertion of n random unsigned ints into a set, n = 10,000 to 3M.
• non_unique_running_insertion.cpp: same as above, but the container is a multiset and elements are repeated an average of 5 times.
• unique_scattered_erasure.cpp: erasure by iterator in random order of the n elements of a set filled as above.
• non_unique_scattered_erasure.cpp: same as prior, but with multisets.
• non_unique_scattered_erasure_by_key.cpp: erasure by key of all the elements of a multiset of std::strings filled with random strings with average repetition 5, n = 10,000 to 3M.
• unique_scattered_lookup.cpp:
  • Successful: lookup of the n keys of the container in the same order as inserted.
  • Unsuccesful: lookup of n random keys not related to those inserted (and thus not present in the container with probabilty ~100%).
• non_unique_scattered_lookup.cpp: same as prior, but with multisets.

How to read the results

Folder

• gcc: GCC 12 with libstdc++-v3, 64 bits
• clang_libcpp: Clang 15 with libc++, 64 bits
• vs: Visual Studio 2022 with (formerly known as) Dinkumware stdlib implementation, 64 bits

Excel file

• running insertion.xlsx: results of unique_running_insertion.cpp and non_unique_running_insertion.cpp
• scattered erasure.xlsx: results of unique_scattered_erasure.cpp and non_unique_scattered_erasure.cpp
• scattered erasure by key.xlsx: results of non_unique_scattered_erasure_by_key.cpp
• scattered successful looukp.xlsx: results of unique_scattered_lookup.cpp and non_unique_scattered_lookup.cpp, successful case
• scattered unsuccessful looukp.xlsx: results of unique_scattered_lookup.cpp and non_unique_scattered_lookup.cpp, unsuccessful case

Tab (inside each Excel file)

• practice: Without duplicate elements (sets)
• practice non-unique: With duplicate elements (multisets)
• practice non-unique 5: Same as above, but the maximum load factor is set to 5
• practice norehash: (Insertion only) same as practice, but reserve is called prior to insertion
• practice norehash non-unique: (Insertion only) same as practice non-unique, but reserve is called prior to insertion
• practice norehash non-unique 5: (Insertion only) same as practice non-unique 5, but reserve is called prior to insertion

Graphs

GCC 12 + libstdc++-v3

Insertion

non-duplicate elements	duplicate elements	duplicate elements, max load factor 5

non-duplicate elements, prior reserve	duplicate elements, prior reserve	duplicate elements, max load factor 5, prior reserve

Erasure

non-duplicate elements	duplicate elements	duplicate elements, max load factor 5

by key, duplicate elements	by key, duplicate elements, max load factor 5

Successful lookup

non-duplicate elements	duplicate elements	duplicate elements, max load factor 5

Unsuccessful lookup

non-duplicate elements	duplicate elements	duplicate elements, max load factor 5

Clang 15 + libc++

Insertion

non-duplicate elements	duplicate elements	duplicate elements, max load factor 5

non-duplicate elements, prior reserve	duplicate elements, prior reserve	duplicate elements, max load factor 5, prior reserve

Erasure

non-duplicate elements	duplicate elements	duplicate elements, max load factor 5

by key, duplicate elements	by key, duplicate elements, max load factor 5

Successful lookup

non-duplicate elements	duplicate elements	duplicate elements, max load factor 5

Unsuccessful lookup

non-duplicate elements	duplicate elements	duplicate elements, max load factor 5

Visual Studio 2022 + Dinkumware

Insertion

non-duplicate elements	duplicate elements	duplicate elements, max load factor 5

non-duplicate elements, prior reserve	duplicate elements, prior reserve	duplicate elements, max load factor 5, prior reserve

Erasure

non-duplicate elements	duplicate elements	duplicate elements, max load factor 5

by key, duplicate elements	by key, duplicate elements, max load factor 5

Successful lookup

non-duplicate elements	duplicate elements	duplicate elements, max load factor 5

Unsuccessful lookup

non-duplicate elements	duplicate elements	duplicate elements, max load factor 5