Roaring Bitmaps in JavaScript

Roaring bitmaps are a popular data structure to represents sets of integers. Given such sets, you can quickly compute unions, intersections, and so forth. It is a convenient tool when doing data processing.

I used to joke that Roaring bitmaps had been implemented in every language (Java, C, Rust, Go, and so forth), except JavaScript. This was a joke because I did not expect that one could implement Roaring bitmaps reasonably using JavaScript. I have written a few performance-oriented libraries in JavaScript (FastBitSet.js, FastPriorityQueue.js, FastIntegerCompression.js), but I could not imagine doing a whole Roaring bitmap implementation in JavaScript.

However, it turns out that many people who program in JavaScript run their code under Node.js. And Node.js supports “native addons”… which basically means that you can call a C/C++ library from JavaScript when you are working in Node.js, as long as someone packaged it for you.

And Salvatore Previti did just that for Roaring bitmaps. So you can, say, generate Roaring bitmaps in Java, then load them in Python modify them, and then load them again in Node.js before shipping them your Go program. Not that anyone is doing it, but it is possible, in theory.

Anyhow, how is the performance of Roaring bitmaps in Node.js? We can compare them with JavaScript’s Set data structure as well as against FastBitSet.js.

• suite intersection size
  262144 elements
Set                   33.26 ops/sec 
FastBitSet        14,364.56 ops/sec 
RoaringBitmap32  266,718.85 ops/sec 
  ➔ Fastest is RoaringBitmap32

• suite intersection (in place)
  65536 elements
Set                    199.99 ops/sec 
FastBitSet          93,394.64 ops/sec 
RoaringBitmap32  4,720,764.58 ops/sec 
  ➔ Fastest is RoaringBitmap32

• suite intersection (new)
  1048576 elements
Set                  3.32 ops/sec 
FastBitSet       1,436.14 ops/sec 
RoaringBitmap32  3,557.16 ops/sec
  ➔ Fastest is RoaringBitmap32

• suite union (in place)
  65536 elements
Set                  201.71 ops/sec 
FastBitSet       147,147.28 ops/sec 
RoaringBitmap32  497,687.77 ops/sec
  ➔ Fastest is RoaringBitmap32

• suite union size
  262144 elements
 Set                   22.77 ops/sec
 FastBitSet         7,766.65 ops/sec
 RoaringBitmap32  274,167.71 ops/sec
  ➔ Fastest is RoaringBitmap32

• suite union (new)
  1048576 elements
Set                  1.72 ops/sec
FastBitSet         698.26 ops/sec
RoaringBitmap32  2,033.11 ops/sec 
  ➔ Fastest is RoaringBitmap32

So Roaring bitmaps can be thousands of times faster than a native JavaScript Set. they can can be two orders of magnitude faster than FastBitSet.js. That Roaring bitmaps could beat FastBitSet.js is impressive: I wrote FastBitSet.js and it is fast!

Of course results will vary. No data structure is ever optimal in all use cases. But these numbers suggest that, in some cases, Roaring bitmaps will be useful in JavaScript.

What if you are not using Node.js. Maybe you are running your code in a browser? Salvatore Previti wrote a WebAssembly version as well, basically compiling the C code from the CRoaring library into WebAssembly. The wrapper is still incomplete and it is unclear whether WebAssembly is mature enough to give you good performance, but, one day soon, it might be possible to have fast Roaring bitmaps in the browser.

Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax