This benchmark compares tsl::hopscotch_map (hopscotch hashing) to google::sparse_hash_map (sparse quadratic probing), google::dense_hash_map (quadratic probing), boost::unordered_map (chaining), std::unordered_map (GCC implementation, chaining), QHash from Qt (chaining) and spp::sparse_hash_map (sparse quadratic probing) to see how hopscotch hashing performs and how fast each hash table is.

To do so we will use the http://incise.org/hash-table-benchmarks.html benchmark with a few modifications to fix some of its short-commings:

  • The glib, python and ruby hash maps were removed and tsl::hopscotch_map and spp::sparse_hash_map were added.
  • We now use std::string as key instead of const char * for the string tests.
  • Some tests were added:
    • Add a benchmark for long std::string to avoid small string optimization.
    • Add iteration tests.
    • Add read miss tests.
  • We use std::hash<T> as hash function for all maps for a fair comparison.
  • Compiled with -O3 -march=native -DNDEBUG flags.

When inserting elements into the maps the reserve function is not called beforehand. The insertion time thus also benchmark how fast a map grows through the rehashes.

The fork of the benchmark can be found on GitHub. The raw results of the charts can be found here.

The benchmark was compiled with GCC 6.1 and ran on Linux x64 with an Intel i5-5200u and 8Go of RAM.

The following hash maps were also tested: rabbit::unordered_map (linear probing and chaining mix), rabbit::sparse_unordered_map (sparse linear probing and chaining mix), emilib::HashMap (linear probing) and sherwood_map (linear robin hood). To avoid too much jumble on the charts, the tests are on a separate page (warning, the page may be slow to load).

Benchmark

Integers

For the integers tests, we use maps with int64_t as key and int64_t as value.

Sequential inserts: execution time (integers)

For each key k in [0, nb_entries), we insert the key-value pair (k, 1) in the map.

number of entries in hash table

    Note that the GCC implementation of std::hash<int64_t> uses an identity hash for positive int64_t. Sequential inserts will thus insert values with sequential hashes.

    Random shuffle inserts: execution time (integers)

    Before the test, we generate a vector with the values [0, nb_entries) and shuffle this vector. Then for each value k in the vector, we insert the key-value pair (k, 1) in the map.

    number of entries in hash table

      The roller-coaster shape of google::sparse_hash_map is normal. The map seems to be quite sensitive to the order in which the values are inserted with the hash function we use. Depending on the size of the vectors at each test, std::shuffle will shuffle the vectors in completely different ways even if the seed is the same. It explains why the time varies so much depending on the number of elements.

      Random full inserts: execution time (integers)

      Before the test, we generate a vector of nb_entries size where each value is randomly taken from an uniform random number generator from all possible positive values an int64_t can hold. Then for each value k in the vector, we insert the key-value pair (k, 1) in the map.

      number of entries in hash table

        Deletes: execution time (integers)

        Before the test, we insert nb_entries elements in the same way as in the random full insert test. We then delete each key one by one in a different and random order than the one they were inserted.

        number of entries in hash table

          Sequential reads: execution time (integers)

          Before the test, we insert nb_entries elements in the same way as in the sequential inserts test. We then read each key-value pair in the same order as they were inserted.

          number of entries in hash table

            Random shuffle reads: execution time (integers)

            Before the test, we insert nb_entries elements in the same way as in the random shuffle inserts test. We then read each key-value pair in a different and random order than the one they were inserted.

            number of entries in hash table

              Random full reads: execution time (integers)

              Before the test, we insert nb_entries elements in the same way as in the random full inserts test. We then read each key-value pair in a different and random order than the one they were inserted.

              number of entries in hash table

                Random full reads miss: execution time (integers)

                Before the test, we insert nb_entries elements in the same way as in the random full inserts test. We then generate another vector of nb_entries random elements different from the inserted elements and we try to search for these unknown elements in the map.

                number of entries in hash table

                  Iteration: execution time (integers)

                  Before the test, we insert nb_entries elements in the same way as in the random full inserts test. We then use the map iterators to read all the key-value pairs.

                  number of entries in hash table

                    Memory usage (integers)

                    Before the random full inserts benchmark finishes, we measure the memory that the benchmark is using.

                    number of entries in hash table

                      Small strings

                      For the small string tests, we use maps with std::string as key and int64_t as value.

                      When we generate a string key, we stringify the entry number for each entry in the range [0, nb_entries). This result in a small string which doesn’t need any heap allocation and will be stored on the stack as GCC 6.1 will use small string optimization for any string smaller than 16 characters (which is our case for the range of strings we generate for the tests). The size of each std::string is 32 bytes.

                      Inserts: execution time (small strings)

                      For each entry in the range [0, nb_entries), we generate a string as key and insert it with the value 1.

                      number of entries in hash table

                        Deletes: execution time (small strings)

                        Before the test, we insert nb_entries elements in the map as in the inserts test. We then delete each key one by one in a different and random order than the one they were inserted.

                        number of entries in hash table

                          Reads: execution time (small strings)

                          Before the test, we insert nb_entries elements in the map as in the inserts test. We then read each key-value pair in a different and random order than the one they were inserted.

                          number of entries in hash table

                            Reads miss: execution time (small strings)

                            Before the test, for each entry in the range [0, nb_entries), we generate a string as key and insert it with the value 1. We then use the range [nb_entries, nb_entries*2) to generate the string keys and search for these unknown strings in the map.

                            number of entries in hash table

                              Memory usage (small strings)

                              Before the inserts benchmark finishes, we measure the memory that the benchmark is using.

                              number of entries in hash table

                                Strings

                                For the string tests, we use maps with std::string as key and int64_t as value.

                                When we generate a string key, we stringify the entry number for each entry in the range [0, nb_entries) to which we append the letter ‘a’ until we reach 50 characters. For example, we get something like “35aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa” as key for the entry 35. The string is long enough so that GCC can’t use small string optimization and has to store it in a heap allocated storage.

                                Inserts: execution time (strings)

                                For each entry in the range [0, nb_entries), we generate a string as key and insert it with the value 1.

                                number of entries in hash table

                                  Deletes: execution time (strings)

                                  Before the test, we insert nb_entries elements in the map as in the inserts test. We then delete each key one by one in a different and random order than the one they were inserted.

                                  number of entries in hash table

                                    Reads: execution time (strings)

                                    Before the test, we insert nb_entries elements in the map as in the inserts test. We then read each key-value pair in a different and random order than the one they were inserted.

                                    number of entries in hash table

                                      Reads miss: execution time (strings)

                                      Before the test, for each entry in the range [0, nb_entries), we generate a string as key and insert it with the value 1. We then use the range [nb_entries, nb_entries*2) to generate the string keys and search for these unknown strings in the map.

                                      number of entries in hash table

                                        Memory usage (strings)

                                        Before the inserts benchmark finishes, we measure the memory that the benchmark is using.

                                        number of entries in hash table

                                          Analysis

                                          The tsl::hopscotch_map is doing well with integer and small string keys but the difference is less pronounced with string keys. The main advantage of tsl::hopscotch_map is its cache-friendliness, when searching for a key on collision we go through the bucket array in a sequential order in memory, with only one cache line load in the best cases (if the key is in the first couple of neighbors depending on the size of the key, the value and the cache). With strings we lose this advantage as a big enough std::string holds pointers to a heap-allocated area. When comparing keys, we have to read this area incurring an extra cache-miss each time we want to compare the keys. Storing the hash alongside the neighborhood infos, with the StoreHash class template parameter, mitigates this effect as on read miss we may not have to compare any string. It also greatly improves the rehash process on insert as we don’t have to recalculate the hashes of the keys.

                                          We see that tsl::hopscotch_map is able to hold its game against google::dense_hash_map while using less memory. Both are performing way better than the other hash maps on this page (other hash maps are present here, slow load link) except for the memory usage where spp::sparsepp and google::sparse_hash_map obviously remain the kings (with spp::sparsepp offering an impressive balance between memory usage and speed).

                                          More tests could be done with different hash functions. We are using the GCC implementation of std::hash as hash function in all our tests for a fair comparison. Some other hash functions may give better results on some hash map implementations.

                                          The benchmark was oriented toward hash maps. Better structures like tries could be used for the string mapping, but std::string is a familiar example to test bigger keys than int64_t and it incurs a cache-miss on comparison if big enough.

                                          In conclusion, with its cache-friendliness tsl::hopscotch_map may be a good alternative to other hash maps if speed is important to you. It offers performances similar to google::dense_hash_map while using less memory in general and without the need to reserve some values of the key to mark the key as deleted or empty.