A simple hash table in C
theleo.zone
theleo.zone
If the author sees this, you might want to take a look at it.
Without appropriate memory barriers, you can end up with an inconsistent view of the memory due to out-of-order execution and other weird stuff the CPU does behind the scenes.
There's significant footguns around low level concurrency primitives.
That said, they are using RCU to allow writers and readers to operate concurrently.
Yes, but how do you ensure there are no writes during those reads?
You have to protect the reads against concurrent writes.
The simplest way is to use a mutex, but that doesn't support concurrent reads.
The next way, which is fairly common, is to use a read-write lock. That allows reads that are concurrent with each other, but only one write at a time, and no concurrency between reads and writes.
A standard read-write lock is not particularly fast for concurrent reads. The lock-for-read operation is required so that reads prevent a concurrent write from starting, and wait for a write already started to finish. That's not fast on a multi-core system because it forces cache line bouncing between cores.
That is, unless particularly fancy types of read-write locks optimised for mostly reading are used, such as rwlock-per-core, and those are slow for writes. They are somewhat fast for reads on architectures with fast atomic operations, but not as fast as possible.
Read-write locks also come in different flavours, depending on whether you want new reads to be blocked and queued when there's a write blocked waiting for current reads to finish. Fairness is an issue. This can get complicated, and bugs in libc rwlocks are not unheard of because of the complication.
A seqlock can be used which has fast reads when there are no writes. They are fast on a multi-core system because there's no cache line bouncing between cores when there are only reads. But if there is a high rate of writes in one thread it can block all reads continuously, by causing them to livelock in loops. This is called spinning. More commonly, the writes tend to slow down seqlocked reads by a large factor in some scenarios, without blocking them completely. Just wasting a lot of CPU time and running slowly, out of proportion to the amount of blocking you would expect is necessary.
Rather like an over-contended spinlock. Spinlocks, which can come in a mutex flavour or read-write flavour, should rarely be used in threaded code outside a kernel. Because they spin as described above, out of proportion to the amount of blocking that's really required, and the effect is much worse in pre-empted userspace threads than in a non-premptible kernel.
It's possible to reduce seqlock and spinlock CPU spinning by transitioning to a different type of lock after some number of spins. Sometimes a dynamically estimated number of spins. This makes them behave better in userspace threaded code outside a kernel. But now your lock is rather complicated, and still not consistently fast at reads.
An approach which works really well is RCU. Concurrent reads can be very simple and never spin because there's no loop. There's no multi-core cache line bouncing. Writes are more complicated, and the reads have to adhere to certain patterns because the kind of concurrency allowed between reads and writes is different in RCU than with locks. It works best if your program has some kind of top-level event loop that is returned to often, to provide the "quiescent states" RCU requires. But there are other ways to do it, if there's no top level, they just require reads to do a bit more work than almost nothing.
Even RCU requires a little something in reads though, to get correct data. This is a data-dependency memory barrier. These barrier operations require zero instructions on nearly all CPUs because of how memory systems are designed, but are famously not free on the DEC Alpha which shows that it's not a "no operation", it just happens to be a side effect that is usually baked in. Even with zero instructions on nearly all CPUs, they limit which code optimisations the compiler is allowed to do, so have a non-zero average overhead, but it is very small in practice.
RCU is what the QEMU hash table uses.
Look here for example:
Entry *newVal = malloc(sizeof(Entry)); newVal->key = strdup(key);
Why not:
Entry* e = malloc(sizeof(Entry) + strlen(key));
Now you can also skip the pointer to the key, saving 8 bytes for each entry. Also, just return the hashtable by value, it's so small.
I think that if we're coding in C, C++ or Zig, then it can be fun to actually use the lower level power to our advantage :).
struct KeyedEntry {
struct Entry entry;
char key[]; // flexible array member
};
[1]: https://en.wikipedia.org/wiki/Flexible_array_member, or https://beej.us/guide/bgc/html/split/structs-ii-more-fun-wit...
_Edit_: Something like this might not be suitable for the author, since they did mention how they wanted each `struct` to have a fixed size.
Don't forget +1 for the terminator.
I also think a linked list is not a great data structure in practice. Having the buckets be one of those amortized-O(1)-append heap allocations would be kinder on CPU caches. But, if you are making the string part of the entry, that would also require padding the string length to word boundaries so that the struct gets aligned.
Note also if you kept the length of the string somewhere (which you would need to for my above paragraph's suggestion), you could avoid strcmp-ing hash collisions where the string has different length. Strcmp is going to add up to an expensive thing in this code.
This code also never checks the return value of malloc. Color me unimpressed with this code. (Cue people arguing that checking for malloc failure is a bad idea ... Linux oom killer and high level languages have you spoiled, there i said it! /s)
> Don't forget +1 for the terminator.
Also should check for arithmetic overflow, or at least static_assert that sizeof(Entry) is "too small" to matter. (Hopefully the process of deciding what "too small" should be results in just adding the overflow check.)
It also makes deletion a far more complicated situation. You'd essentially be implementing your own allocator then.
more info: https://stackoverflow.com/questions/6118539/why-are-there-no...
Also you could 'delete' with item.data set to some sentinel.
Besides which, this statement is just inflammatory:
"In true POSIX fashion they are close to useless."
The straw man does not support the conclusion .. POSIX is full of utility.
- https://github.com/attractivechaos/klib/blob/master/khash.h
The trick is that you make sure that your table is large enough to not have a lot of collisions, then if you have a collision instead of storing exactly in the bucket given by the hash, you store it in the next available bucket. When you look for a key, you get the hash, then the index from the hash, and you start searching at this point. If you reach an empty value, then there is no value. If you find the value then you return that. So everything is stored in a single array, no need for extra allocations and it is better for cache locality.
The same principle is used here for very minimal hash table (13 lines): https://nullprogram.com/blog/2020/10/19/
This video also talk about how to optimize hash table and look into several implementations: https://www.youtube.com/watch?v=DMQ_HcNSOAI&t=1690s&ab_chann... . It talks about techniques used by advanced hash table. There was a lot more that I didn't know.
It’s an open addressing hash table (https://en.wikipedia.org/wiki/Open_addressing), with a linear probing collision resolution (https://en.wikipedia.org/wiki/Linear_probing).
Usually yes, though it’s also possible to perform gradual resizing that’s less efficient so it’s only used when needed (e.g. real time systems which can’t afford a full resize).
> What are the Performance implications of that?
Same as a vector. That’s why hashmaps generally provide an amortized insertion time.
> What we didn't look at though was, what happens when the hash table is full?
Of note: a hash table never gets full, hash tables have a load factor (which mostly depends on the collision resolution algorithm, as that informs how performances degrade as collisions increase), and the table will resize when it exceeds its load factor, to maintain a “healthy” rate of collisions.
When it's full, insertion requires rehashing into a bigger table. (Or you can use an overflow list when the table is full or nearly full, if you don't want to rehash and prefer to treat this case as rare and ok to be slow.)
So for a general purpose open addressing / closed hashing hash table where you don't know the number of items in advance, rehashing to a bigger table is done at some threshold before it's actually full.
As long as you do rehashing using a multiplier, for example doubling the size at 50% full (as opposed to adding a fixed amount to the size), it stays fast on average, but the rehashing operations are of course individually slow. They just don't happen often, so the average stays at O(1) time. This is called amortised O(1) time complexity. The ideal threshold for resizing depends on the probing type.
Linked list hash tables, (also called closed addressing or open hashing - I think linked list is a clearer name) don't suffer from catastrophic slowdown with size in the same way as the open addressing / closed hashing type. Nor abrupt failure when full, because they're never full. These can still be resized and this is required if O(1) time is required to arbitrary numbers of items, but the resizing threshold is not as critical. If not resized they gradually degrade to O(N) time performance when filled too much. Many applications use fixed size linked list hash tables safely because of this.
Array-of-arrays hash tables behave similarly to linked list hash tables.
I have been working on trying to design a contiguous hash table data structure that has these two mutual requirements:
a) allows deep clones (due to contiguous memory copyable with memcpy)
b) supports arbitrarily nestable hash tables
The closest library I know about is smolworld ( https://github.com/snej/smol_world ) but I don't know how easy it can be cloned.
These requirements rules out multiple mallocs: I do one single malloc and expect that to be enough for the entire hashmap.
I'm not sure if these constraints might also force a fixed number of buckets and a fixed capacity.
The clonable property requires interior mutability be limited, because if you memcpy pointers they would cause structure sharing, that I'm trying to avoid, hence a deep clone.
Rationale: these are the use cases I have for such a data structure. The first is cheap copy on write. I also have a left-right concurrency control hashmap, but I feel the properties of this data structure are even better. The first is a sharding in multithreading design: do a cheap memcpy for each thread and shard the processing and merge at the end, without any synchronization cost while the threads are working. I know that deep cloning is slow in Java and presumably C if you do it with loops rather than memcpy. Another use case is efficient serialization for network.
In other words, a protobuf but easily deep clonable without loops.
https://gist.github.com/williamcotton/99ab6e8efa3c4b6c07a149...
I'm probably that guy that pipes up when he doesn't know what he's talking about but.
You can store offsets instead of pointers. You can then just memcpy the whole thing and it'll just work as long as everything is self contained.
This is what smol_world does, it uses 32 bit indexes.
I really like the idea of smol_world, I just don't know if you can easily .clone() it.
https://news.ycombinator.com/item?id=26590234
How to implement a hash table in C (benhoyt.com) 302 points by benhoyt on March 26, 2021, 158 comments
In my article I use "open addressing" [2] instead of linked lists for collisions, as 1) it tends to be simpler, as you only have one data structure to manage (array, rather than array and linked list), and 2) it tends to be faster, as linked lists are slow on modern CPUs because they require jumping around in memory.
It well enough and is conceptually probably the easiest approach to grok with relatively few pitfalls.
Another question-- at the moment where one would normally decide to resize the table for performance reasons (i.e., buckets are getting too full), how would the array-bucket style perform compared to the linked-list bucket style?
A lot of mallocs. Just malloc a pool and implement an allocation strategy on top of it. Malloc more as necessary (say 2^n).
You mention map types in other languages. They're not always implemented as a hashmap. A tree is commonly used to implement maps too.
Embedded environments generally avoid `malloc` and the heap entirely. You have a simple allocator on top of a fixed allotment of memory instead.
Good mallocs do that themselves already. It's built in, they use a pool. Really good mallocs use a fast, cache-friendly pool, typically per CPU-core or per-thread.
By using a pool on top of a good malloc, you are implementing a second pool on top of the first pool. For something general purpose like a general purpoe hash table, layering pools like that often provides no advantage and some disadvantages including to performance. It's often, though not always, better to use a really good malloc
> You mention map types in other languages. They're not always implemented as a hashmap. A tree is commonly used to implement maps too.
Notably the C++ `std::map` is a tree. A later standard added `std::unordered_map` which is a hash table. The effect is many C++ programs use trees for their maps, and some C++ devs don't realise they are using a tree with O(log N) time operations instead of a hash table with O(1) time operations.
> Embedded environments generally avoid `malloc` and the heap entirely. You have a simple allocator on top of a fixed allotment of memory instead.
I think that's a strange way to look at it, because `malloc` is a simple allocator on top of a fixed allotment of memory when you have a fixed allotment of memory to work with. You can write whatever `malloc` and `free` functions you like to suit the situation. You don't have to use the one in libc, and small embedded environments often don't have one. E.g. I've seen extremely memory-constrained bootloaders and DSPs where there is still a function called `malloc`, but it is a very simple allocator for the situation.
In high reliability systems you might need to control the pattern of allocations in the progam so that memory use stays bounded. But in a general purpose hash table, the way to bound memory use is to control the pattern of hash table usage, i.e. the callers.
https://en.wikipedia.org/wiki/Cuckoo_hashing
No bucket lists are necessary. Guaranteed O(1) read access (not amortized, but always). Can be parameterized wrt. access time vs. memory efficiency. Can also be precompiled for offline data, e.g., Unicode codepoint tables (thought tries are also really good for this).
It's funny how many people come up with the same ideas.
For better ones I would point to my linked list implementation: https://github.com/rurban/ctl/blob/master/ctl/unordered_set.... (because it has various security policies, nobody else has) or https://github.com/LIMachi/swiss-table (all in C)
The CTL "unordered set" is roughly the same bad design as its namesake in C++, presumably on purpose. We really shouldn't be teaching new users this bad structure, nor the "security policy" mitigations it provides. And by the way it's not a "distributed" denial of service when somebody plugs 128 colliding values into your API, just a normal trivial DOS.
typedef struct HashTable {
Entry *buckets[4];
int nBuckets;
} HashTable;
Because of that, basically.
2. Implement bloom filter
3. Download list of Bitcoin wallets with non-zero amount of BTC
4. Generate long list of random key pairs
5. ???
6. Profit