hash-table

We actually wrote the original version in C with SIMD extensions as a Node.js binding, but the JavaScript version was still twice as fast. I kid you not. You will find the reason for this in the README, it's the last bullet point under "Fast": https://github.com/ronomon/hash-table#fast

One of the things I love about JavaScript is that you can write an almost 10x faster hash table than the standard library if you take care of cache misses and GC: https://github.com/ronomon/hash-table#motivation In fact, all the usual low-level optimization techniques like reducing branch mispredictions and expensive memory accesses apply, and make a huge difference, even though you're writing in a high-level language.

> Finding ways to have, say, 10 million blacklist elements with a small memory footprint is left as an exercise for the reader. In case the reader is interested (and this may not be what OP had in mind): In trading memory gains with computation, this is how I squeezed ~4M entries in less than 30 MiB: 1. Compress (reversed) individual entries using a dictionary or entropy encoder. I experimented with Shoco [0], Femto [1], and a modified LZ78 [2]. 2. Create a bloom filter for membership checks, [3] or any probabilistic structure for that matter, like the xor-filters [4]. This prevents expensive but unnecessary lookups. 3. Insert the compressed (reversed: google.com -> com.google) entries into a radix-tree [5]. You could use a directed-acyclic graph (DAG), if you don't need to store key-value pairs. 4. Compact [6][7] the radix-tree [8] (comp

I've come across a fair share of zero-alloc implementations of various things, like u/poitrus' zerolog [0] and u/jorangreef's cuckoo-hashtable [1], for instance. Given that JavaScript runs on restrictive clients, it must have libraries in spades for this kind of a thing, but I couldn't find many. I'm really interested in techniques that are generally employed in languages like Java, Golang, Rust, C/++ that are worth translating over to JavaScript, especially now that TypedArrays are a reality. I'm pretty sure there's more to zero-alloc than just Buffers, Object pools, and Recyclables, but I can't seem to find good resources to get started with this. [0] https://github.com/rs/zerolog [1] https://github.com/ronomon/hash-table/blob/master/README.md

"If memory overhead (load factor) isn't a big issue, readers may also find cuckoo hashing rather interesting." The issue with memory overhead (load factor) is actually something that Cuckoo hashing solves compared to linear probing. Bucketized Cuckoo hashing supports much higher load factors than linear probing. You can have your cake and eat it too. I have implemented hash tables with open addressing and tombstones in the past (linear probing, triangular probing etc.) and I much prefer Cuckoo hashing now. When Cuckoo hashing is combined with a bloom filter in the first position to reduce cache misses to the second position, it's almost perfect in every way: fast (drastically reduced cache misses), constant lookup time in the worst case (not so for linear probing), higher load factors (80% or more for Cuckoo hashing vs at most 50% for lin

The comparison between the classes of "Las Vegas" and "Monte Carlo" algorithms is a useful distinction, along with the author's suggestion of using a cache table as a lookup table for compression match finding. If anyone is interested, I wrote @ronomon/hash-table as a fast, scalable cuckoo hash table for Node.js. It has high load factor, constant lookup time in the worst-case and uses a non-recursive variant of the cuckoo probing scheme, together with a bloom filter to reduce cache misses to the alternative cuckoo bucket by an order of magnitude. Last but not least, caching is supported according to the CLOCK LRU algorithm, which is elegant and effective. Benchmarks and design decisions are in the README: https://github.com/ronomon/hash-table

This is a fantastic explanation of developments in hash tables in general. If anyone is interested, I recently released a scalable hash table for Node.js (@ronomon/hash-table), designed to store literally billions of elements without stressing the GC. At first, I tried writing a native addon module for Node.js in C (using SIMD), but the Javascript-to-C call cost was just too high, and doubled latency. In the end, I was surprised to find that writing directly in Javascript proved faster than the C module with SIMD, simply by avoiding the bridging cost. Also, instead of linear or quadratic probing (or double hashing or triangular probing), I used cuckoo hashing, but with a twist. Normally, in the case of a naive cuckoo hash table, if an element is not in its first bucket, then its second bucket must be fetched from memory, causing a cache m

I recently finished a scalable hash table for Node.js, designed to store billions of elements in huge flat buffers without impacting the garbage collector (no pointer chasing), and without causing memory fragmentation. At first, I tried a native add-on, using SIMD instructions to compare multiple keys per instruction. This makes the use of buckets (multiple keys per slot) compelling, because the branching cost of key comparisons almost disappears. However, in the end, the 100ns to 200ns cost of calling into C from Javascript using N-API (or V8) mitigated any SIMD gains, so I rewrote the hash table in Javascript directly. While not as fast as a pure C implementation, it's still fairly fast, and more scalable than Javascript's native vanilla objects, Sets or Maps. The notes on design and optimization decisions taken are here, if anyone is i

I recently wrote https://github.com/ronomon/hash-table for Node.js, which has a few more design tips listed in the Readme, specifically around optimizing a cuckoo hash table by reducing cache misses.

Thanks, I added Set into the rough vanilla comparison. It's slightly better than a vanilla object, but it's still almost an order of magnitude slower, and is most likely still going to have issues with GC overhead when storing millions of pointers. GC issues blocking the event loop are not fun when you have a hash table with billions of elements. Also, while a Set can technically receive an Array (or iterable) upfront in the constructor, this requires you to have your Array available upfront, which is not always the case, and an Array is also not meant for millions of objects in the first place. For example, AFAIK (and I may be wrong since last I checked) but V8's Array will switch mode and degrade into an object at around 10,000 elements. So with Set (or Map) there's still no production-quality way to allocate and reserve capacity upfron