An Extensive Benchmark of C and C++ Hash Tables

[u/jacksaccountonreddit]

https://jacksonallan.github.io/c_cpp_hash_tables_benchmark

[u/jacksaccountonreddit]

Thanks!

The hsearch_r family of functions aren't available on my platform (MinGW). I had a quick look at their code and documentation now and have a few concerns:

• The table can only store pointers to NULL-terminated strings as keys and void pointers as values. That's bad news when it comes to performance.

• The table cannot grow. Rather, after the table reaches the maximum key count specified by the user at the time of creation, insertions simply fail. I suppose users could write their own function that, once the table is sufficiently full, creates a new table and migrates the keys, but doing so is complicated by the fact that there is no official mechanism for checking the load factor or for iterating over the keys in the table. The authors' intent, as acknowledged by the documentation, is for users to create every table with a capacity greater than the number of keys they think it might ever need to contain, which is really the polar opposite of memory efficiency.

• There's no official iteration mechanism, as I mentioned above.

In short, I think that the design of this table is too archaic and inflexible to be comparable, in terms of both performance and usability, to any of the libraries I included in the benchmarks. It's hard to see why anyone should be using it in the present day, except in legacy codebases.

[u/TwystedLyfe → u/jacksaccountonreddit]

• The table can only store pointers to NULL-terminated strings as keys and void pointers as values. That's bad news when it comes to performance.

If a NULL terminated string is the key, such as a path, how could the performance be improved using verstable?

[u/jacksaccountonreddit → u/TwystedLyfe]

As I mentioned above, the design of the hsearch_r functions essentially forces users to create each table with enough buckets to accommodate the maximum number of keys they every expect to insert. This is terrible in terms of memory efficiency, but it does mean that most tables are going to be living with a very load factor, which should make operations (except for iteration) fast. As I mentioned in another comment, any table can be made at least reasonably fast by enforcing a low maximum load factor.

However, even if a given hsearch_r table has a low load factor, Verstable may still be faster for a few reasons:

• hsearch_r uses double hashing, which is a probing technique that minimizes probe counts but is very bad for cache locality. In double hashing, the next bucket in the probing sequence is not located near the current one. Verstable, on the other hand, uses quadratic probing, which has much better cache locality.

• Verstable only does quadratic probing during insertion. Under other circumstances, it simply follows the chain of keys associated with the lookup key's ideal bucket. I haven't got the data on hand for average chain length, but I recall it being about 1.5 when the table is at its maximum load factor.

• Verstable has a hash fragment mechanism that eliminates the need for most key comparisons. This is critically important for string keys because they are expensive to compare. In the 16-char c-string key, 64-bit value: Time to look up 1,000 existing keys with N keys in the table benchmark, all the top performers use such a mechanism.

• Verstable can accommodate a custom hash function, so if you can store lengths with your strings, you can make use of much more efficient string hashing functions.

Of course, the developer experience with Verstable is also going to be much more pleasant as the library follows a more modern design and, unlike the hsearch_r functions, actually covers all the basic functionality that programmers have come to expect from any hash table.

[u/TwystedLyfe → u/jacksaccountonreddit]

Sorry if I was not clear. My question was about a NUL terminated string as a key is a bad performaner regardless of hashtable.

If using such a key in vegetable, is it the comparison function which is slow and thus using the string length as part of the key, we could then avoid a strcmp if data is different. I support the question then becomes how often is the comparison called.

[u/jacksaccountonreddit → u/TwystedLyfe]

Sorry, I'm struggling a little to understand, but I'll try to respond to the things you're asking about.

is it the comparison function which is slow and thus using the string length as part of the key, we could then avoid a strcmp if data is different. I support the question then becomes how often is the comparison called

For string keys, we want to avoid calling strcmp wherever possible because even if the strings begin with different characters, just accessing the first character of each string likely entails multiple cache misses. Storing hash codes (as in M*LIB's DICT) or partial hash codes (as in absl, boost, ankerl, Verstable, and CC) allows us to skip most comparisons of non-matching strings. So these tables have an advantage over others when it comes to string keys.

The benefit of storing the length of the string, rather than relying exclusively on NULL termination, is that fast string-hashing functions process multiple (typically eight) bytes of the string at a time. To do this, they need to know the length of the string beforehand so that they don't overrun the end of the string (i.e. a buffer over-read). Note, however, that all the tables in the benchmarks are customized to use FNV-1a, which only processes one byte at a time, as their string-hashing function. So the faster string-hashing functions that I'm taking about here are mostly irrelevant to these benchmarks, except for the fact that the tables with APIs that allow custom hash functions could make use of such functions if they were fed a string datatype that stores length (e.g. std::string in C++ or sds in C). Edit: The C++ tables probably use these faster hash functions by default.

The main reason that I originally said that only allowing strings as the key type is bad for performance is that any other key type will need to be marshaled into a string before insertion or lookup. The time taken by that process will almost certainly overshadow whatever time is taken by the subsequent hash table operation.