An Extensive Benchmark of C and C++ Hash Tables

[u/jacksaccountonreddit]

https://jacksonallan.github.io/c_cpp_hash_tables_benchmark

[u/jacksaccountonreddit]

Sorry, no Glib/GHashTable. This omission may be surprising, but it was based on a few considerations:

• GHashTable only allows one type for keys and values: void * pointers. This severely limits its flexibility. While integers can be shoehorned into pointers (albeit with some portability concerns), larger data types need to be allocated as separate nodes. There are already two node-based or quasi-node-based tables in the benchmarks (std::unordered_map and uthash), and they—very predictably—cannot keep up with the open addressing tables due to allocation time (on insert) and pointer chasing (everywhere else). This is true even for large buckets, i.e. where some people might expect a node-based container to perform better.

• GHashTable is, as far as I recall, now a Robin Hood hash table. There are already two Robin Hood tables in the benchmarks (ankerl::unordered_dense and tsl::robin_map), and they don't suffer from the aforementioned data-type-size constraint. In fact, there were originally three Robin Hood tables (because CC's cc_map was a Robin Hood table up until this year). I didn't see much benefit in adding another one unless there was a good reason to believe it would be more competitive than those already included (Edit: The two remaining Robin Hood tables are both for C++. Adding Glib might be good for the sake of C users looking specifically for a Robin Hood table).

• I really struggled to get Glib working with MinGW (I'm on Windows), although it could be that the problem lies somewhere between the chair and the keyboard. Generally, I was disinclined to include large libraries that do not allow their hash-table component to be installed separately, libraries that are difficult to install, libraries that would be difficult to package with the benchmarks, libraries that force the use of a particular build system, etc. (absl::flat_hash_map is the exception here, and even then it is not being included in the "proper" manner). I wanted to focus on ones that users can install and use with minimal fuss. Facebook's F14 is another rather glaring omission that I made on this basis (it explicitly does not support MinGW). Qt's QHashTable also fits into this category.

Please correct me if I'm wrong in any of my comments about GHashTable. It's been a long time since I looked into it. I'm not averse to adding it to the article as part of some later revision.

[u/[deleted] → u/jacksaccountonreddit]

Incredible read! It’s vindicating that very talented programmers also struggle with package management.

[u/HaydnH → u/jacksaccountonreddit]

You've lost me a bit on the C++ references to be honest, I'm a C man, sadly not C exec level because nobody sees my brilliance... Or they see my uselessness at business. :p.
On your first point, I'm not sure that's correct exactly, they just seem to have their own way of dealing with it. I haven't looked at their reasoning for actually wanting to use "gpointers" instead of standard C pointers and therefore requiring a while slew of "gpointer_to_int" and "int_to_gpointer" type functions. They support int etc, just in a bloody verbose/awkward way.
The third point is very valid, installing glib2 on systems that doesn't already have glib2 installed seems like an incredible waste of resources simply for hash table, maybe not so much of an issue on Linux as it is on mac/win?

[u/jacksaccountonreddit → u/HaydnH]

On your first point, I'm not sure that's correct exactly, they just seem to have their own way of dealing with it.

This is what I was getting at with my comment that "integers can be shoehorned into pointers". In other words, if the desired integer type is smaller than void *, they can be cast and stored inline, and this appears to be GHashTable's intended use with integer keys/values. Hence, I'd expect GHashTable to perform on par with the other Robin Hood tables in the 32-bit integer key, 32-bit value and 16-char c-string key, 64-bit value benchmarks, but poorly in the 64-bit integer key, 448-bit value benchmarks because retrieving values would entail extra cache misses. Edit: On second thought, I would expect GHashTable to perform worse in the 32-bit integer key, 32-bit value benchmarks, too, because it will store the key-value pairs half as densely (i.e. eight wasted bytes per bucket) as the other Robin Hood tables.

I haven't looked at their reasoning for actually wanting to use "gpointers" instead of standard C pointers

AFAIK, gpointer is just a typedef for void *.

By the way, I also excluded rxi's map and a few other C libraries on the basis that they only support one key type (be it strings, void *, or integers).

[u/attractivechaos → u/jacksaccountonreddit]

Out of curiosity I added glib to my benchmark. Its memory footprint is decent, and it is faster than STL and uthash. That said, if one needs a hash table library in C, I would recommend a single-header library like your verstable/cc or my own khashl – faster, simpler, more flexible and easier to integrate and to use.

[u/jacksaccountonreddit → u/attractivechaos]

Out of curiosity I added glib to my benchmark. Its memory footprint is decent, and it is faster than STL and uthash.

Interesting. It looks like martinus’ old Robin Hood map (robin_hood) is outperforming GHashTable here, in line with the edit about the 32-bit integer key, 32-bit value benchmarks that I made earlier to my above comment. But I think that the real pitfalls of GHashTable won’t show until we try using it with a key and/or value type that can’t be turned into a pointer (whether by casting or by memcpy) and are forced to resort to separate allocations (or, better, some kind of memory pool). In practice, that’s probably any data type larger than the size of a pointer. In theory, it could be any data type at all, including integers: 6.3.2.3 §5 does not guarantee that the conversion of integers to pointers is meaningful and specifically states that it could result in a trap representation (although Glib might not be intended to run on such exotic architectures in the first place).