Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Optimizing Open Addressing

thenumb.at

Post reply on HN
Print view View original

21–30 of 70 posts

Re: Optimizing Open Addressing

#21

Post by mananaysiempre »

camel-cdr wrote: post #12

Sometimes a very basic fixed size chaining hash tables is actually the best you can do. Take for example tcc, which is a very fast c compiler. They just use a basic chaining hash table: `Node *nodes[16384];`. Since most translation units have far less than 16384 tokens, most lookups result in a direct hit.

TCC has the advantage of being a batch process, so it can insert things using open addressing without ever considering how it intends to delete them, then just drop the whole thing on the floor at the end. Of course, if you are also a batch process, you absolutely should do that too.

Re: Optimizing Open Addressing

#22

Post by eternalban »

mgaunard wrote: post #2

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.

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

Re: Optimizing Open Addressing

#23

Post by dragontamer »

mgaunard wrote: post #19
dragontamer wrote: post #15

Earlier quoted context omitted.

Perhaps we need to start talking with actual code? Here's just a simple idea that's in my brain right now. template struct HashNode{ // Probably should be shared_ptr >, but that's // now adding even more inefficiencies like a ref_count per element struct HashNode * nextPointerChain; Data d; // Maybe Data* d if you're sharing it with other data-structures? }; template struct ChainHashTable{ HashNode theTable[size]; };…

You still fail to understand what being part of multiple data structures means. Shared pointers, separate container to check occupancy, suggesting making a container of pointers, all these things suggest you have no idea how to do hybrid data structures. The nodes contain the data along with multiple pointers in them to chain them to various data structures they are part of (trees, lists, hash tables etc.). The objec…

So you've at best removed just 8 bytes for rather inconvenient programming for...

    LinearProbingHashTable
    ChainHashTable
Note that linearProbingHashTable only uses 8 bytes per pointer. While ChainHashPointer still needs nextPtr, taking up 16 bytes.

The *2 is for 50% load factor on linear table. But we still win on linear if we're at say 75% (simple linear) or 95% load factor (which is doable with Robin Hood)

Re: Optimizing Open Addressing

#24

Post by 10000truths »

anarazel wrote: post #18
kevin_thibedeau wrote: post #7

Earlier quoted context omitted.

> only performs well up to 50-75% bucket usage. Robin Hood performs well into the high 90's.

One situation where I painfully learned that it doesn't, is when you iterate over one hashtable to fill another. To defend against that one needs to add some per-hashtable randomized state into the hash IV. Through bad experience I also learned that you need to not just grow due to fillfactor, but also due to disproportional chain length, even with the above defense in place.

> To defend against that one needs to add some per-hashtable randomized state into the hash IV.

You should almost always be doing this anyways, since most hash tables use user-provided data as keys, which opens up a well known avenue for denial-of-service attacks:

https://lwn.net/Articles/474912/

Re: Optimizing Open Addressing

#25

Post by tialaramex »

camel-cdr wrote: post #12

Sometimes a very basic fixed size chaining hash tables is actually the best you can do. Take for example tcc, which is a very fast c compiler. They just use a basic chaining hash table: `Node *nodes[16384];`. Since most translation units have far less than 16384 tokens, most lookups result in a direct hit.

Is that the best TCC could have done here? It's easy to write this in C, which is one obvious reason for TCC to do it, but it's not at all clear this is the best way.

What TCC is actually storing in TokenSym (which you've named "Node" in this context) is four pointers to other information about symbols, a unique ID, and a string.

If we used a compact inline string (like CompactString) we can squeeze all this into 60 bytes unless the string is more than 24 bytes in length such as TCC's own warn_implicit_function_declaration or is_compatible_unqualified_types which would need a heap allocation like they have today, for the string itself.

If we do that we can build a linear probed open addressed hash table and avoid paying for the extra indirection any time the symbol names are 24 bytes or shorter in length, I'd expect this is markedly better.

But it's a lot of work in C, so it isn't a surprise TCC doesn't do it.

Re: Optimizing Open Addressing

#26

Post by infinet »

I learned about Open Addressing a long time ago when I was optimizing Dnsmasq. The scenario involved looking up a very large list of domain names to block or combine with ipset in order to customize routing based on domain names. Open addressing worked very well on these large immutable lists.

Re: Optimizing Open Addressing

#27

Post by anarazel »

10000truths wrote: post #24
anarazel wrote: post #18

Earlier quoted context omitted.

One situation where I painfully learned that it doesn't, is when you iterate over one hashtable to fill another. To defend against that one needs to add some per-hashtable randomized state into the hash IV. Through bad experience I also learned that you need to not just grow due to fillfactor, but also due to disproportional chain length, even with the above defense in place.

> To defend against that one needs to add some per-hashtable randomized state into the hash IV. You should almost always be doing this anyways, since most hash tables use user-provided data as keys, which opens up a well known avenue for denial-of-service attacks: https://lwn.net/Articles/474912/

I think that's often fixed using a per run random seed, rather than a per table seed. The patch linked in the python bug linked from that article does seem to do that, for example.

Re: Optimizing Open Addressing

#28

Post by citizen_friend »

mananaysiempre wrote: post #21
camel-cdr wrote: post #12

Sometimes a very basic fixed size chaining hash tables is actually the best you can do. Take for example tcc, which is a very fast c compiler. They just use a basic chaining hash table: `Node *nodes[16384];`. Since most translation units have far less than 16384 tokens, most lookups result in a direct hit.

TCC has the advantage of being a batch process, so it can insert things using open addressing without ever considering how it intends to delete them, then just drop the whole thing on the floor at the end. Of course, if you are also a batch process, you absolutely should do that too.

This is an advantage of C style programming. If you understand the problem and tailor a solution you can utilize simplifying assumptions which make the code easier and faster.

General libraries have to handle all kinds cases you might not care about. The most egregious example is assuming every piece of code might be threaded so everything needs to be protected by locks. (I would guess > 75% of dictionaries never remove a key, and simply throw away the whole thing at the end.)

Re: Optimizing Open Addressing

#29

Post by pornel »

Modern CPUs keep making optimal algorithms weirder. Speculative superscalar execution and the colossal gap between the CPU and memory speed means that often a brute-force solution that fits in a cache line wins over solutions that would feel more elegant or efficient.

Re: Optimizing Open Addressing

#30

Post by anonymoushn »

sporadicity wrote: post #8

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

I've benchmarked swiss tables and found that (for hit-heavy workloads) a minimum of 2 loads per lookup is expensive compared to 1.
Post reply on HN