Optimizing Open Addressing
thenumb.at
Optimizing Open Addressing
1–10 of 70 posts
Re: Optimizing Open Addressing
#2I find that there is too much of an emphasis on open-addressing in blog articles and such.
There are a lot of real and common data structures where chaining is much better suited.
For example whenever you have data part of one or multiple other node-based data structures, and you layer an index on top of that.
Chaining also tends to waste a lot less memory.
Re: Optimizing Open Addressing
#3I find that there is too much of an emphasis on open-addressing in blog articles and such. There are a lot of real and common data structures where chaining is much better suited. For example whenever you have data part of one or multiple other node-based data structures, and you layer an index on top of that. Chaining also tends to waste a lot less memory.
In my experience / tests, its way easier to write a high-performance open-addressing Hash Table than a high-performance chaining one.
That being said, chaining is easier to write.
> Chaining also tends to waste a lot less memory.
How so? A typical 32-bit integer or 32-bit float uses 4-bytes. But a typical pointer is 8-bytes. But there's also the internal malloc/new chunk header to consider.
That means, to store a 4-byte integer into a chained hash table, you need 8-bytes (pointer) + 8-byte (glibc malloc chunk header) + 4 byte integer/float. Or 20 bytes total in practice.
If you have say, 50 integers inside of the hashmap, then you'll use (table-size * 8) + 50-integers * 20 bytes each == 1000+ bytes for the pointers/data alone, plus even more for the table itself. (ex: Table of size 50 would need 50 * 8-byte pointers even when empty, for a total of 1000 bytes + 400 bytes == 1400 bytes or so)
In contrast, a 4-byte open-addressing hash table only takes up 4-bytes. So 50-integers in a hashmap with ~50% load-factor (ie: size the table to be size 128 or so) will be 128 * 4 == 512 bytes.
EDIT: Its because of this huge practical difference in memory used that I'm pretty sure open-addressing is so high performance in comparison. When your data-structures are 1/2 or smaller number of bytes than the competition, its easier to stay in L1 cache or other such size benefits.
Re: Optimizing Open Addressing
#4I find that there is too much of an emphasis on open-addressing in blog articles and such. There are a lot of real and common data structures where chaining is much better suited. For example whenever you have data part of one or multiple other node-based data structures, and you layer an index on top of that. Chaining also tends to waste a lot less memory.
I would tend to agree.
This article conveniently designs its benchmark to be exactly when open addressing would work.
In almost all of the maps implementations I have used so far, chaining was necessary and intrusive linked lists were used.
An open-addressing scheme was however preferable (cuckoo) for a read-mostly map allowing concurrent reads and locked writes.
I would be more interested in an article exploring the compromises involved there, e.g. related to paying the cost of an additional indirection when accessing the value.
Another critic of this article I would add is the many tables throughout referencing different baselines. A single baseline would be much preferable, to keep a sense of scale for each change.
Re: Optimizing Open Addressing
#5I find that there is too much of an emphasis on open-addressing in blog articles and such. There are a lot of real and common data structures where chaining is much better suited. For example whenever you have data part of one or multiple other node-based data structures, and you layer an index on top of that. Chaining also tends to waste a lot less memory.
In my experience / tests, its way easier to write a high-performance open-addressing Hash Table than a high-performance chaining one. That being said, chaining is easier to write. > Chaining also tends to waste a lot less memory. How so? A typical 32-bit integer or 32-bit float uses 4-bytes. But a typical pointer is 8-bytes. But there's also the internal malloc/new chunk header to consider. That means, to store a 4-b…
Nodes don't have to be allocated with malloc (that is actually the worst thing you could possibly do).
An open-addressing hash table only performs well up to 50-75% bucket usage. Chaining doesn't care and performs the same up to 100%.
Re: Optimizing Open Addressing
#6Earlier quoted context omitted.
In my experience / tests, its way easier to write a high-performance open-addressing Hash Table than a high-performance chaining one. That being said, chaining is easier to write. > Chaining also tends to waste a lot less memory. How so? A typical 32-bit integer or 32-bit float uses 4-bytes. But a typical pointer is 8-bytes. But there's also the internal malloc/new chunk header to consider. That means, to store a 4-b…
Nodes don't have to be allocated with malloc (that is actually the worst thing you could possibly do). An open-addressing hash table only performs well up to 50-75% bucket usage. Chaining doesn't care and performs the same up to 100%.
> Nodes don't have to be allocated with malloc (that is actually the worst thing you could possibly do).
I mean... the most obvious place to place nodes is... inside the table itself. Also known as Open Addressing.
Or what, are you going to implement a 2nd, custom heap algorithm to manage your nodes? I guess there's "buddy allocators", but buddy-allocators aren't exactly free either. Whatever method you're using to keep track of nodes is going to have some level of inefficiency.
Whatever allocation you're doing to get these nodes (above-and-beyond generic malloc) is time you could have been spent writing open-addressing instead.
> An open-addressing hash table only performs well up to 50-75% bucket usage. Chaining doesn't care and performs the same up to 100%.
Hardly an apples-to-apples comparison. As I pointed out, 50% load-factor on 50x uint32 open-addressing is only ~400 bytes used.
While 100% load factor on 50x uint32 is 1400 bytes used on chaining. (plus additional load-factor in practice due to malloc fragmentation)
Re: Optimizing Open Addressing
#7Earlier quoted context omitted.
In my experience / tests, its way easier to write a high-performance open-addressing Hash Table than a high-performance chaining one. That being said, chaining is easier to write. > Chaining also tends to waste a lot less memory. How so? A typical 32-bit integer or 32-bit float uses 4-bytes. But a typical pointer is 8-bytes. But there's also the internal malloc/new chunk header to consider. That means, to store a 4-b…
Nodes don't have to be allocated with malloc (that is actually the worst thing you could possibly do). An open-addressing hash table only performs well up to 50-75% bucket usage. Chaining doesn't care and performs the same up to 100%.
> only performs well up to 50-75% bucket usage.
Robin Hood performs well into the high 90's.
Re: Optimizing Open Addressing
#8Have you tried absl::flat_map? It uses simd in a different way than described in this article, and Google claims that it saves them a lot of memory because it still works pretty well at 90-95% occupancy.
Re: Optimizing Open Addressing
#9Reads like a great summary for the hash map ideas that work in practice. I would have loved to see flat_hash_map thrown into the benchmark mix.
Re: Optimizing Open Addressing
#10Earlier quoted context omitted.
Nodes don't have to be allocated with malloc (that is actually the worst thing you could possibly do). An open-addressing hash table only performs well up to 50-75% bucket usage. Chaining doesn't care and performs the same up to 100%.
> Nodes don't have to be allocated with malloc (that is actually the worst thing you could possibly do). I mean... the most obvious place to place nodes is... inside the table itself. Also known as Open Addressing. Or what, are you going to implement a 2nd, custom heap algorithm to manage your nodes? I guess there's "buddy allocators", but buddy-allocators aren't exactly free either. Whatever method you're using to k…
I already explained. Objects in non-trivial data structures are part of several data structures concurrently.