4 ms·

I 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

I 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.

dragontamer 4y ago
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.
- mgaunard 4y ago
  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%.
  - dragontamer 4y ago
    > 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)
    - mgaunard 4y ago
      I already explained. Objects in non-trivial data structures are part of several data structures concurrently.
      - dragontamer 4y ago
        Perhaps we need to start talking with actual code? Here's just a simple idea that's in my brain right now. template <class Data> struct HashNode{ // Probably should be shared_ptr<HashNode<Data>>, but that's // now adding even more inefficiencies like a ref_count per element struct HashNode<Data>* nextPointerChain; Data d; // Maybe Data* d if you're sharing it with other data-structures? }; template <class Data, int size> struct ChainHashTable{ HashNode<Data> theTable[size]; }; template <class Data, int size> struct LinearProbingHashTable{ Data theTable[size]; vector<bool> occupied; // set to "size", 0 means empty and 1 means occupied }; nextPointerChain takes up 8 bytes, even if its nullptr. No other data-structure needs to have the nextPointerChain. If we use shared_ptr<HashNode<Data>> as per typical modern C++, there's even more inefficiencies that I forgot about. EDIT: You probably can get away with unique_ptr, now that I think of it. ---------- Pointers aren't free btw. If you're sharing the pointer with many different parts of your program, that's definitely one of those things you'll want to start getting rid of. Not only does a pointer cost 8 bytes, but its also _SIGNIFICANTLY_ slower and cache-unfriendly in practice. L1 cache works by reading data in-and-around anything you access. If you're only using 8-bytes of a cache line for pointer-indirection (8/64), you're wasting 56-bytes of your fetch. Linear Probing is extremely fast because it tends to blitz through L1 cache thanks to locality of data. Simple Linear Probing (or Robin-hood augmented probing) is probably the fastest, and simplest, approach for modern CPUs.
- kazinator 4y ago
  It is not necessary for an allocator to have any hidden overhead inside an allocated block. That would be quite unacceptable for small blocks like a 32 byte block holding four pointer-sized values. In any case, applications can do their own aggregation for small allocations: allocate the nodes in an array and dole it out from that. It can recycle unused nodes itself.
  - dragontamer 4y ago
    > In any case, applications can do their own aggregation for small allocations: allocate the nodes in an array and dole it out from that. It can recycle unused nodes itself. Or you could just write the open-addressing HashMap, which is easier than implementing your own custom small allocation malloc()/free()? That's the thing. To make chaining competitive against open-addressing HashMaps, you've got to bend-over backwards and its suddenly not easy anymore. Though you're right in that different versions of malloc/free could be more efficient. Ex: tcmalloc() has small allocations built in already like you mention. But even if you erase those 8-bytes from the glibc chunk implementation of malloc, you're _still_ 8-bytes over the open-addressing implementation (you can't get rid of the 8-byte "next" pointer). So all that work and you're still worse off than the other methodology.
    - kazinator 4y ago
      I can write aggregating allocation for a C with my eyes closed, in a tiny number of lines. These days I mostly wouldn't. If the target system thinks it's a good idea to add a header to every 32 byte allocation, that's their problem. No worthwhile malloc implementation does that, other than in a debugging configuration, where it adds "red zones". The calculations in my other post show that it's not as simple as that next pointer being pure overhead compared to open addressing. https://news.ycombinator.com/item?id=35416520 https://news.ycombinator.com/item?id=35416520
    - deleted 4y ago
      [deleted]
grive 4y ago
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.
tialaramex 4y ago
I'm not convinced there are "a lot" of these real and common structures. They certainly do arise, and particularly if you're also doing concurrency linked lists are attractive because a compare-exchange type mechanism is ideally suited for such structures and that has been implemented cheaply in hardware. But this article was about the default, and we don't want defaults tailored to niche uses. The default T-shirt size shouldn't be big enough for The Rock. The default ceiling height in new buildings shouldn't be 1.5 metres. The default beverage offered at your restaurant shouldn't be Mountain Dew Code Red. It's OK that these things are options, that somebody who wants them can have them, but they're bad defaults. I'd want to see some measurements from real world projects to believe chainig should be the default. If I take, say, the Chromium codebase, and the LibreOffice codebase, and I look at places they use any type of hash table, how often are they going to be for stuff that'd be "better suited" to chaining? Am I going to consistently find 50% ? 10% ? 1% ?
- mgaunard 4y ago
  Pretty much 95% of all hybrid data structures. Now hybrid data structures are only used in systems programming, because they require to be particularly careful about object lifetime and such.
deleted 4y ago
[deleted]
eternalban 4y ago
Choice-of-two + bias (pick L) + fixed-sized bin slices of the backing arrays = very high loading, strictly 2 ops (max) per R/W, trivial to write. I typically just use a very fast cryptographic hash (Blake3 is awesome) and have plenty of bits for h1, h2 (you can have additional choices but it is a fast dimiminishing return).
kazinator 4y ago
Chaning still requires a flat table, which can change in size, and is proportional to the number of entries in the table (to keep the average chain length ("load factor") bounded). Thus, this can still cause memory fragmentation, even though the hash table chain nodes can all be the same size and so reduce fragmentation. In terms of absolute bytes, ignoring fragmentation, it depends on the load factors. In chaining, you need at least a singly linked list. Let's assume that our nodes store the hash value, as well as the key, value and a next pointer: so four pointer-sized words. (You don't have to store the hash code, but you'd be foolish not to, because it can reject mismatches in a single one-word comparison, avoiding the need to do a full key comparison.) In addition, each chain needs a pointer-sized word which points to it from the table. (We ignore remaining overheads, like the small data structure which keeps the table and other bookkeeping info.) Let's assume we keep the load factor (maximum average chain length) to 4. Beyond that we will increase the table size. So the chained table is considered 100% full with 4 nodes per chain on average. In this situation, the root table is amortized as 1/4 word overhead per node: so each node effectively 4.25 nodes. An open-addressed table stores keys and values. To make the comparison fair, it should also store the hash codes; they are needed for the same reason: as we probe over collisions, we can use them to reject non-matching keys. So, when it's 100% full, it needs 3 words per entry. In this situation, it's beating the 4.24 value of chained hashing. However, we would never want an open-addressed table to get 100% full, because the performance degrades, regardless of the collision resolution strategy. Say we allow up to 80%. 20% (0.2 x 3 words = 0.6 words per entry) of the table is wasted space, so 3.75. Still beating chained. Now let's look at the half full situation. Below half full we might reorganize either table to be smaller, so that's our worst case. When the chained table is half full, the average chain length is 2, and so each node needs 4.5 words: the table part represents more overhead, but the value doesn't change much from the maximum load case. The half-full open-addressed table basically wastes 60% of the table: it's as if each item requires 7.5 words rather than 3. In this minimum load case, it is losing to chained hashing. (Remember, full is 80%, so half of that is 40%). Summary: Words per entry*: \ Method Load \ Chained Open Addressing +--------------------------------------- half | 4.5 7.5 | full | 4.25 3.75 * Words are pointer-sized scalar values * For chained: full means load factor of 4; half means load factor of 2. * For open addressing: full means 80% of the table, half is 40% of the table * Assuming entries store hash code, key and value. There is no clear winner in terms of memory, but it's looking as if the improvement from open addressing may not be that great, if at all realized. Of course, the values are debatable; why should the max load factor for chaining be 4? Or may be more than 80% can be crammed into an open-adressed table. I'm kind of surprised; according to the parameters I chose, I thought that open addressing would hit a better density. What points in favor of the open addressing is caching behavior: avoiding the dependent loads of pointer chasing. For Open-Addressing, cache-friendly collision strategies can be chosen so when multiple entries are probed, they tend to be cached close together in the same block.

dragontamer 4y ago

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.

mgaunard 4y ago
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%.
- dragontamer 4y ago
  > 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)
  - mgaunard 4y ago
    I already explained. Objects in non-trivial data structures are part of several data structures concurrently.
    - dragontamer 4y ago
      Perhaps we need to start talking with actual code? Here's just a simple idea that's in my brain right now. template <class Data> struct HashNode{ // Probably should be shared_ptr<HashNode<Data>>, but that's // now adding even more inefficiencies like a ref_count per element struct HashNode<Data>* nextPointerChain; Data d; // Maybe Data* d if you're sharing it with other data-structures? }; template <class Data, int size> struct ChainHashTable{ HashNode<Data> theTable[size]; }; template <class Data, int size> struct LinearProbingHashTable{ Data theTable[size]; vector<bool> occupied; // set to "size", 0 means empty and 1 means occupied }; nextPointerChain takes up 8 bytes, even if its nullptr. No other data-structure needs to have the nextPointerChain. If we use shared_ptr<HashNode<Data>> as per typical modern C++, there's even more inefficiencies that I forgot about. EDIT: You probably can get away with unique_ptr, now that I think of it. ---------- Pointers aren't free btw. If you're sharing the pointer with many different parts of your program, that's definitely one of those things you'll want to start getting rid of. Not only does a pointer cost 8 bytes, but its also _SIGNIFICANTLY_ slower and cache-unfriendly in practice. L1 cache works by reading data in-and-around anything you access. If you're only using 8-bytes of a cache line for pointer-indirection (8/64), you're wasting 56-bytes of your fetch. Linear Probing is extremely fast because it tends to blitz through L1 cache thanks to locality of data. Simple Linear Probing (or Robin-hood augmented probing) is probably the fastest, and simplest, approach for modern CPUs.
kazinator 4y ago
It is not necessary for an allocator to have any hidden overhead inside an allocated block. That would be quite unacceptable for small blocks like a 32 byte block holding four pointer-sized values. In any case, applications can do their own aggregation for small allocations: allocate the nodes in an array and dole it out from that. It can recycle unused nodes itself.
- dragontamer 4y ago
  > In any case, applications can do their own aggregation for small allocations: allocate the nodes in an array and dole it out from that. It can recycle unused nodes itself. Or you could just write the open-addressing HashMap, which is easier than implementing your own custom small allocation malloc()/free()? That's the thing. To make chaining competitive against open-addressing HashMaps, you've got to bend-over backwards and its suddenly not easy anymore. Though you're right in that different versions of malloc/free could be more efficient. Ex: tcmalloc() has small allocations built in already like you mention. But even if you erase those 8-bytes from the glibc chunk implementation of malloc, you're _still_ 8-bytes over the open-addressing implementation (you can't get rid of the 8-byte "next" pointer). So all that work and you're still worse off than the other methodology.
  - kazinator 4y ago
    I can write aggregating allocation for a C with my eyes closed, in a tiny number of lines. These days I mostly wouldn't. If the target system thinks it's a good idea to add a header to every 32 byte allocation, that's their problem. No worthwhile malloc implementation does that, other than in a debugging configuration, where it adds "red zones". The calculations in my other post show that it's not as simple as that next pointer being pure overhead compared to open addressing. https://news.ycombinator.com/item?id=35416520 https://news.ycombinator.com/item?id=35416520
  - deleted 4y ago
    [deleted]

grive 4y ago

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.

tialaramex 4y ago

I'm not convinced there are "a lot" of these real and common structures. They certainly do arise, and particularly if you're also doing concurrency linked lists are attractive because a compare-exchange type mechanism is ideally suited for such structures and that has been implemented cheaply in hardware. But this article was about the default, and we don't want defaults tailored to niche uses. The default T-shirt size shouldn't be big enough for The Rock. The default ceiling height in new buildings shouldn't be 1.5 metres. The default beverage offered at your restaurant shouldn't be Mountain Dew Code Red. It's OK that these things are options, that somebody who wants them can have them, but they're bad defaults. I'd want to see some measurements from real world projects to believe chainig should be the default. If I take, say, the Chromium codebase, and the LibreOffice codebase, and I look at places they use any type of hash table, how often are they going to be for stuff that'd be "better suited" to chaining? Am I going to consistently find 50% ? 10% ? 1% ?

mgaunard 4y ago
Pretty much 95% of all hybrid data structures. Now hybrid data structures are only used in systems programming, because they require to be particularly careful about object lifetime and such.

deleted 4y ago

[deleted]

eternalban 4y ago

Choice-of-two + bias (pick L) + fixed-sized bin slices of the backing arrays = very high loading, strictly 2 ops (max) per R/W, trivial to write. I typically just use a very fast cryptographic hash (Blake3 is awesome) and have plenty of bits for h1, h2 (you can have additional choices but it is a fast dimiminishing return).

kazinator 4y ago

Chaning still requires a flat table, which can change in size, and is proportional to the number of entries in the table (to keep the average chain length ("load factor") bounded). Thus, this can still cause memory fragmentation, even though the hash table chain nodes can all be the same size and so reduce fragmentation. In terms of absolute bytes, ignoring fragmentation, it depends on the load factors. In chaining, you need at least a singly linked list. Let's assume that our nodes store the hash value, as well as the key, value and a next pointer: so four pointer-sized words. (You don't have to store the hash code, but you'd be foolish not to, because it can reject mismatches in a single one-word comparison, avoiding the need to do a full key comparison.) In addition, each chain needs a pointer-sized word which points to it from the table. (We ignore remaining overheads, like the small data structure which keeps the table and other bookkeeping info.) Let's assume we keep the load factor (maximum average chain length) to 4. Beyond that we will increase the table size. So the chained table is considered 100% full with 4 nodes per chain on average. In this situation, the root table is amortized as 1/4 word overhead per node: so each node effectively 4.25 nodes. An open-addressed table stores keys and values. To make the comparison fair, it should also store the hash codes; they are needed for the same reason: as we probe over collisions, we can use them to reject non-matching keys. So, when it's 100% full, it needs 3 words per entry. In this situation, it's beating the 4.24 value of chained hashing. However, we would never want an open-addressed table to get 100% full, because the performance degrades, regardless of the collision resolution strategy. Say we allow up to 80%. 20% (0.2 x 3 words = 0.6 words per entry) of the table is wasted space, so 3.75. Still beating chained. Now let's look at the half full situation. Below half full we might reorganize either table to be smaller, so that's our worst case. When the chained table is half full, the average chain length is 2, and so each node needs 4.5 words: the table part represents more overhead, but the value doesn't change much from the maximum load case. The half-full open-addressed table basically wastes 60% of the table: it's as if each item requires 7.5 words rather than 3. In this minimum load case, it is losing to chained hashing. (Remember, full is 80%, so half of that is 40%). Summary: Words per entry*: \ Method Load \ Chained Open Addressing +--------------------------------------- half | 4.5 7.5 | full | 4.25 3.75 * Words are pointer-sized scalar values * For chained: full means load factor of 4; half means load factor of 2. * For open addressing: full means 80% of the table, half is 40% of the table * Assuming entries store hash code, key and value. There is no clear winner in terms of memory, but it's looking as if the improvement from open addressing may not be that great, if at all realized. Of course, the values are debatable; why should the max load factor for chaining be 4? Or may be more than 80% can be crammed into an open-adressed table. I'm kind of surprised; according to the parameters I chose, I thought that open addressing would hit a better density. What points in favor of the open addressing is caching behavior: avoiding the dependent loads of pointer chasing. For Open-Addressing, cache-friendly collision strategies can be chosen so when multiple entries are probed, they tend to be cached close together in the same block.