Hacker News Reader

Comment by _urga | Hacker News Reader

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 interested: https://github.com/ronomon/hash-table

View on HN

Wow, really nice! I had to carefully analyze the page to find the answer, first reading:

   keySize=16 valueSize=0

    @ronomon/hash-table: Inserting 4000000 elements...
    @ronomon/hash-table: 783ms

            new Set(): Inserting 4000000 elements...
            new Set(): 3695ms

...that the key and value sizes are in bytes (seen only once one reads the api). So, almost 5 times faster set insert, congratulations. The major advantage is, of course, the chance to less stress the GC when the data sets are big.

> the 100ns to 200ns cost of calling into C from Javascript using N-API (or V8)

Do you (or some reader here?) maybe know what's the current cost of calling into WebAssembly, compared to that "calling C" cost?

Thanks!

I updated the vanilla.js script and README to clarify that the key and value sizes are in bytes.

I haven't tried calling into WebAssembly so I don't know. Perhaps the bridging cost would be similar or slightly better (or who knows, worse)? Does WASM have SIMD? Do you know of any areas where WASM would outdo the current Javascript implementation?

For times like these, I wish server-side Javascript itself had SIMD, and access to CPU builtins, such as popcount etc.

WASM has a popcnt instruction, and will eventually have SIMD. I think the bridging cost is less than calling something through NAPI or a native add-on because you're still in the VM.

Great hash table by the way!

node, chrome, etc. already support the current WASM SIMD proposal

Do you know when this landed and/or if I need a flag to enable it in Node? I'm running Node 11 and get an error when trying to run a function with a SIMD instruction in it.

I hacked up a WAT file with this inside a function body and compiled it with wat2wasm --enable-simd

    (local $2 v128)
    (set_local $2
       (i8x16.splat (i32.const 8))
    )

And I get an error "invalid local type" when I try to run it within Node.

> Do you know of any areas where WASM would outdo the current Javascript implementation?

As soon as you can imagine something that would "better work in C" it's reasonable to expect that Wasm will have an edge vs. Javascript. Javascript does eventually get JIT-ed etc, but with wasm it's effectively "just the code" from the start -- conceptually, Wasm code doesn't have to contain any checks to "fall back" to some slower implementation, once it's processed.

Here's one of the "minimal" examples of calling the C function which is compiled to the WebAssembly: https://medium.freecodecamp.org/get-started-with-webassembly...

Note the resulting native assembly code in the picture on the right there. It's that minimal. I don't know how big the costs JavaScript to that are... But seeing how beautifully you've measured for your project, I'm quite sure you're more than suited to evaluate that too, and to measure the currently minimal costs. And as there is a lot of interest in these topics, if you demonstrate the obvious weakness there's a chance it could be fixed?

It seems that the string has to be copied every time a call from JavaScript to Wasm is made (there stringToUTF8):

https://blog.teamemo.com/behind-teamemo-using-a-c-library-fr...

Reply on news.ycombinator.com