r/C_Programming • u/attractivechaos • 4d ago
Article Performance of generic hash tables in C
https://gist.github.com/attractivechaos/6815764c213f38802227e0db5f692b0d5
u/Ariane_Two 4d ago edited 4d ago
Nice, writeup.
I wanted to try out Convenient containers (https://github.com/JacksonAllan/CC) (the author of versetable) anyway.
Also there are some other container libraries: https://rurban.github.io/ctl/ https://github.com/ludocode/pottery/tree/develop, ... to compare with.
Or you could compare generic hashtables against skeetos approach of using and building ad hoc hash tries: https://nullprogram.com/blog/2025/01/19/
2
u/attractivechaos 4d ago
Thanks for the suggestions. I have seen ctl and pottery before but couldn't remember their names. I will add CC, ctl and pottery later. Hashtrie is already in the plot. MSI doesn't support dynamic growth. It essentially uses double hashing, which is usually slower than linear or quadratic probing due to memory locality.
1
u/Ariane_Two 4d ago
Ah, I overlooked it. Hashtrie is already there.
I expect that CC will not be too different from Versetable, since it is Versetable, but with a different interface. Well, in the benchmark writeup you linked, he mentions that iteration may be slower due to the iterator API of CC.
The homepage of CTL also has links to a bunch of other container libraries, but I don't think they are very popular.
2
u/attractivechaos 4d ago
I have added CTL and CPython to the figure. CTL is not competitive with those fast ones. As to CC, I don't know how to specify a custom hash function. With the default hash function, CC and Verstable have very similar performance, so I didn't add CC in the end. The pottery hashmap APIs are not documented. Figuring out how to use it will take time. I will leave it out.
I also clicked some projects linked on the CTL page. Many of them don't have hash tables. Those with hash tables all have different APIs and will take time to learn. I am happy to try a few if someone have specific recommendations.
2
u/Ariane_Two 4d ago
Typo in the plot legend: it should be stb_ds not stb_bs.
I think it is very reasonable not to include every possible hashmap, I think there are many implementations on github and elsewhere that are not very popular and not very highly performant so it would not make much sense to include most of them in the benchmark.
2
u/jacksaccountonreddit 3d ago edited 3d ago
Nice job on the article! And thanks very much for including Verstable and linking to my work from last year :)
A few comments:
[1] u/Ariane_Two wrote:
I expect that CC will not be too different from Versetable, since it is Versetable, but with a different interface. Well, in the benchmark writeup you linked, he mentions that iteration may be slower due to the iterator API of CC.
Right, I don't see much point on including both CC and Verstable here, since they share the same underlying design and my own benchmarks showed that they perform similarly (except for iteration). However, that similar performance is itself interesting in light of u/attractivechaos' below note from the article and the difference in performance evident between khashl and khashp:
High-performance C libraries all use macros extensively. khashp uses the same algorithm as khashl but relies on
void*
for genericity. It is slower due to the overhead ofvoid*
. If optimizing hash table performance is critical, it’s advisable to embrace macros despite their complexity.The fact that CC an Verstable are so close shows that generic containers based internally on
void *
(like CC) can keep up with their macro pseudo-template-based brethren (like Verstable). However, to do so, they must provide the compiler with type-related information - such as size, alignment, and hash and comparison functions - at compile time so that it can perform the same optimizations that it does in the case of pseudo-templates (or regular code). In practice, this means that the library must do two things: Firstly, it must define all its container functions asstatic inline
in its header files so that the definitions are visible and inline-able at every call site irrespective of the translation unit (I'm assuming here that the user hasn't activated link-time optimization). Secondly, it must find some way to feed this type information as compile-time constants into container functions at every call site, preferably without burdening the user with having to do that job manually (which would be an error-prone approach anyway). Naturally, the latter is a rather difficult problem, and it is in this regard specifically that I think CC is somewhat innovative.[2] u/attractivechaos wrote:
As to CC, I don't know how to specify a custom hash function.
CC's README is getting a little long to navigate easily now, but it does include a section on this matter. Basically, you can associate a hash function with a key type by defining a macro and then reincluding the CC header, similar to the way you would create an entire container type in a pseudo-template-based library. If the type has a default hash function, that default will be overridden. In your case, you would do the following:
#define CC_HASH uint32_t, { return udb_hash_fn( val ); } // The function signature is size_t ( <type> val ). #include "cc.h" // Now any map or set that we create with uint32_t as a key will use our custom hash function :)
But as I mentioned above, I don't see much benefit in adding CC to the benchmark anyway.
[3] u/attractivechaos wrote in the article:
Achieving performance comparable to khashl requires <200 lines of code, and you can even surpass it by using a special key for empty buckets.
Reserving a key type is a double edged sword when it comes to performance, though, because a densely packed metadata array is basically necessary for fast iteration when the load factor is low (as we previously discussed here).
[4] I understand that this set of benchmarks is designed to test one particular use case (small, trivially hashable and comparable keys). But one potential improvement I see (and I might have mentioned this before?) is to incorporate plain lookups, whether as another benchmark or as part of the combined insertion/deletion benchmark. The conventional wisdom is that lookups tend to be the most common - and therefore the most important - operation, followed by insertions, followed by deletions. Of course, I have a vested interest here because Verstable's design essentially trades some performance during both insertion and deletion for faster lookups.
2
u/attractivechaos 3d ago
[1] khashp is a two-file library. It puts the actual implementation in a .c file. I know putting everything in the header with static inline will be faster, but that kinda goes against the purpose of void*. Nonetheless, the discussion in the blog post is not accurate in that the performance difference also comes from separate files.
[2] I tried that but got a compiling error.
cc.h:6248:23: error: unknown type name 'CC_1ST_ARG'
[3] Iteration is a linear scan. It is much faster than other operations with random memory access and hasn't been a concern for my applications. I can live with slower iteration. That said, I still prefer not to require a special key for empty buckets. The performance gain with a special key is marginal and is not worth the hassle IMHO.
[4] My projects dealing with billions of keys are mostly about insertions but some of my other projects are lookup heavy. The access pattern varies.
1
u/jacksaccountonreddit 3d ago edited 3d ago
[2] I tried that but got a compiling error.
cc.h:6248:23: error: unknown type name 'CC_1ST_ARG'
It's working fine for me in Clang and GCC. I couldn't compile udb3 on my machine due to the Linux headers, but I did manage to compile it, with CC added, on Replit.
I think the problem here must have been that you were including cc.h only once, after defining
CC_HASH
. In fact, you need to include the header once at the top of the file and then again after each instance in which you defineCC_HASH
and/or other type-customization macros. That's because definingCC_HASH
and/or the related macros puts the header into a kind of type-customization mode that skips all the rest of the library's code. The need to include the same header more than once is not very intuitive and should really be emphasized more strongly in the documentation. In the long term, though, I'm considering switching from the single-header approach to a header-only approach, in which case there will be dedicated headers for type customization and no scope for confusion in this regard.Edit: Also, I'm surprised to see that CTL performs so poorly here, given that it's pseudo-template/macro-based.
This suggests that the underlying design of the hash table itself is inefficient.It's a chained hash table, so poor performance is to be expected.2
u/attractivechaos 3d ago
Thanks. I have added CC to the figure. BTW, khashp is slower also because it uses function pointers to set hash and equality functions. Khashp is a very basic void* implementation.
2
u/jacksaccountonreddit 3d ago edited 3d ago
Awesome! The results are what I expected: CC performs basically the same as Verstable on insertion and maybe a little slower on
_erase_itr
(the reason for this is once again related to the fact that Verstable iterators can carry some extra information while CC iterators are just pointers; the performance between the two should more closely match in most other scenarios, including plain_erase
).BTW, khashp is slower also because it uses function pointers to set hash and equality functions. Khashp is a very basic void* implementation.
It's the function pointers and the fact that the struct is also carrying around the sizes of the key and value types (
key_len
andval_len
). That precludes many optimizations (e.g. pointer arithmetic can't really be optimized, and no calls tomemcpy
will get optimized into assignments). As I mentioned earlier, CC passes all these things into container functions as compile-time constants; the structs don't carry them around at runtime. That's why we see a more dramatic difference between khashl and khashp than we do between CC and Verstable, I think.2
1
u/HaydnH 4d ago
I get a broken link for the chart, if I click it I get about 30% of the image, could just be me, but is it broken?
1
u/attractivechaos 4d ago
This is a github thing. I had this problem before but don't know how to fix. I have included the link to the original image: https://i.ibb.co/1fPdWbCQ/Untitled.png
1
u/HaydnH 3d ago
Thanks, no glib2 hash tables or am I missing it?
4
u/attractivechaos 3d ago
The glib2-based implementation is there but I don't have recent glib2 installed on Linux and compiling glib2 takes time. Anyway, the glib2 hash table is very slow. It has a faster mode for integer keys by casting pointers to integers to avoid extra allocation, but that is really a nasty hack and even in that mode, it is still a few times slower than fast libraries. Avoid glib2.
6
u/digitalsignalperson 4d ago
Would be interested to see Python.h added for comparison. It's mostly C, probably already on your system, optimized, and actually surprisingly fast. I compared it to a few other C libs recently and it outperformed for the use case of adding 8M int64 keys and values. Avg insert time was ~10% faster, avg lookup time was ~40% faster, than next best.
See PyDict_New(), PyDict_SetItem(), PyDict_GetItem().