A new fast hash table in response to Google’s new fast hash table

Moreover, this kind of optimization only makes sense if (1) latency, not throughput, is your bottleneck or (2) if you're really concerned about parallel accesses.

A reasonable default in general is to use a hash table + mutex until that is your bottleneck. (I've yet to encounter a scenario where switching from a hash map would provide significant gains in performance-relevant code)

Disclosure: I work at Google and use the fancy hash map discussed by Matt. I didn't work on it, though.

That said, I can see two counter-arguments:

1. Rehashing can be avoided if the table size is known in advance. 2. Rehashing is immaterial if the data structure is write-once, read-many.

In those cases, we might reasonably expect a hash table to perform better.

https://en.wikipedia.org/wiki/Radix_tree looks like a funky structure for _very_ specific work loads.

Edit: bytell_hash_map.cpp:464 bytell_hash_map.cpp:58

Apparently there's one extra layer of indirection via a lookup table to get the final offset.

So basically the metadata byte is a bitfield union of + status flag + status code (not sure it's actually required) or offset enum. The offset enum then indexes into a look up table, the result of which is the relative offset from the current index.

I figure it works best if you over allocate slots, so that on average you only have to do very few hops on each linked list walk (or no walk at all).

Aside: This is the method employed by .NET's Dictionary<K,V> class.

Further - it's generally faster to use structure of arrays rather than array of structures, thus in the above scheme the dictionary items/payloads and the linked list pointers could be in separate arrays.

Inside the processor there are cache-lines (usually 64 bytes). They are blocks of memory that are are tagged by CPU at once and moved together.

In the typical n-way set associative cache architecture the main RAM memory is divided blocks with n-lines each. Each set on the memory cache can hold up to n-lines from the same memory block. 8-way cache would divide 1 GB RAM to 1,024 1 MB blocks. If you work with more than 512 bytes (= 8X64) at the time within that block, there will be cache misses. In other words, CPU caches have have limited amount of cache lines dedicated to large continuous block of RAM (unless they are fully associative caches)

From CPU to DRAM access there is typically 64-byte and 4096-byte regions with range cross penalties. I think 64-byte cross penalty is typically less than 10 cycles, 4096-byte region range cross penalty is several tens of cycles (this on the top of the penalty of accessing DRAM).

https://stackoverflow.com/questions/24673567/change-to-hashm...

See:

http://kaldewey.com/pubs/FAST__SIGMOD10.pdf

I remember this sort of thing being mentioned but not in as much detail as I would have gone into (though I'd self-taught a lot of this before Uni, so for me it was more an exercise in unlearning mistakes and formalising & rounding off knowledge than it was about taking in new concepts, perhaps for others cramming the extra detail in would have been counter productive). Algorithm courses would say things like "of course caching methods should be taking into consideration, you'll cover this in architecture modules" and architecture modules would say "you'll cover the effect on some algorithms in much more detail in your software engineering modules"!

All the JS sorting demos that were an active fad a short while ago were simplified in the same way: they assumed that either a comparison or a swap was always the most expensive operation and the other can be discounted, or that all swaps/comparisons are equal due to uniform memory speed (no accounting for caching), and no consideration was made for what was being sorted (inserts are much more expensive in an array than a linked list for instance). I keep meaning to find the time to put a less superficial demo together that allows such things to be modelled at a basic level, perhaps even trying to illustrate the effect of a more distributed architecture (where there is more than one processing unit involved and everything isn't in local fast memory).

Of course, for the most part these simplifications are perfectly valid, but they should always carry a caveat noting what simplifying assumptions are being applied so people learning know that the issues could be more complicated so some critical thinking should be applied in any real world situation.

Not really, no. This isn't a matter of complexity theory being less useful than promised, it's just a matter of understanding what it tells you.

In complexity theoretic terms, platform-specific micro-optimisations are constant factors. They can have a real impact, but they're only worth worrying about after you've got good complexity.

Bubble-sort in fine-tuned SIMD assembly code will out-perform bubble-sort in Python, but will be far slower than a Python quicksort (except for small inputs).

Notice that we're discussing which hash-map to use, as opposed to which data-structure to use in the first place. Their basic time-complexities are the same, so we have the luxury of worrying about the constant factors.

Linear-scan dictionaries can't compete here, no matter how well micro-optimised. (Again, except for very small inputs.) Complexity theory tells us why.

Additionally, complexity theory is useful when reasoning about large problems (high values of n), but it doesn't tell you how to do the platform-specific micro-optimisations that are important when attacking small problems. Implementation details will dominate there, rather than the number of algorithmic operations.

Anyone who teaches complexity theory without explaining these points, has done their students a disservice.

> I wonder if there's something that's more predictive than big Oh for these types of analysis.

When it comes to real-world performance, there's no substitute for just measuring real-world performance. Detailed analysis of things like cache behaviour, and behaviour under highly concurrent access, could be neat though.

Edit For completeness, I should mention that in extreme cases, there are indeed algorithms with superior complexity which are in practice completely useless, as the break-even point is so awfully high that they could never be useful. Matrix multiplication, for instance, where the algorithms with the best time-complexity are quite literally never useful. https://en.wikipedia.org/w/index.php?title=Computational_com...

Perhaps that contradicts my whole point :-P

The other limitation of complexity theory is that in practice we often care about average-case performance, whereas theorists tend to care more about worst-care performance.

The RAM model doesn't concern itself with memory hierarchies or slow ops (ie divisions are supposed to be as fast as additions.)

For example, if you were benchmarking cuckoo hashing lookups, the results would look similar even though the number of operations is deterministically O(1) rather than expected O(1).

While, like others have said, big O and execution are different, in practice the article makes a lot of sense when evaluating execution.

To be more specific, if you place n balls into n bins, on average each bin will contain 1 ball, but the largest one, with high probability, will contain O(log(n)/log(log(n))) of them.

In practice on any particular machine all the addresses are the same length (and we have finite memory), so it doesn't quite explain the effect you are observing in the article. But it does hint that it makes sense.

> From a speed point of view Judy is chiefly a 256-ary digital tree or trie (per D. Knuth Volume 3 definitions). A degree of 256-ary is a somewhat "magic" N-ary for a variety of reasons -- but mostly because a byte (the least addressable memory unit) is 8 bits. Also a higher degree means reduced cache-line fills per access. You see the theme here -- avoid cache-line fills like the plague.

Sounds like a neat data-structure made with cache behaviour in mind. I'm not getting much out of the creator's attempts to explain it, but there's a Wikipedia article: https://en.wikipedia.org/wiki/Judy_array

[1]: https://dawn.cs.stanford.edu/2018/01/11/index-baselines/

What is interesting is you can use the TPUs and parallelize the approach.

Ultimately it is about using less power to get some work done.

I may actually have figured out a way to (theoretically) make it faster, but I don't grok C++ templates so can't write a pull-request (the general idea is: instead of a standard full swap, use two temporaries and ping-pong between them while swapping elements to do half-swaps. This reduces required assignments to move an element to its final position from three to two).

I also just want to comment that skepticism to high claims is good but your comment seems a bit too harsh. Briefly looking at his post where he goes into his “fastest hash table” it’s quite long, very detailed and has similar graphs. That doesn’t seem under-researched to me.