croaring-ffi

Raw Haskell bindings to a bundled copy of CRoaring, the C implementation of Roaring bitmaps.

Usage

import Data.Bitmap.Roaring.FFI.Bitmap qualified as Bitmap
import Foreign.Marshal.Array (withArrayLen)

main :: IO ()
main =
  Bitmap.with create $ \bitmap -> do
    Bitmap.addRange bitmap 10 20
    Bitmap.contains bitmap 15 >>= print
    Bitmap.getCardinality bitmap >>= print
    Bitmap.rank bitmap 100 >>= print
  where
    create = withArrayLen [1, 2, 3, 1000000] $ \count values ->
      Bitmap.ofPtr (fromIntegral count) values

Bindings are named after their C functions without the type prefixes. For example, roaring_bitmap_add_range is Bitmap.addRange. The upstream documentation describes what each function does. The _safe loaders are named *Bounded because they only bound how far they read.

Bitmap.with frees the bitmap when the action ends. If the constructor returns NULL, Bitmap.with throws NullHandle. To let the garbage collector free a bitmap instead, wrap its pointer with newForeignPtr Bitmap.finalizerFree.

Use portableDeserializeValidated for bytes from outside the program. It reads no more than the given size, and returns Nothing unless the bytes hold a valid bitmap:

import Data.Bitmap.Roaring.FFI.Bitmap qualified as Bitmap
import Data.ByteString qualified as ByteString

main :: IO ()
main = do
  bytes <- ByteString.readFile "bitmap.roaring"
  loaded <- ByteString.useAsCStringLen bytes $ \(buffer, size) ->
    Bitmap.portableDeserializeValidated buffer $ fromIntegral size
  case loaded of
    Nothing -> putStrLn "not a valid bitmap"
    Just bitmap -> do
      Bitmap.getCardinality bitmap >>= print
      Bitmap.free bitmap

Performance

At a million sparse elements, both Roaring bitmaps beat Data.IntSet at every operation by 1.5 to 7 times. They count elements 110 to 140 times faster (numbers):

In smaller sparse sets, most elements are alone in their block of 65,536 values. So IntSet combines and iterates faster until the set grows to between a hundred thousand and a million elements. Roaring still counts faster at every size, and looks up elements faster from a few thousand elements:

Much of that small-set cost is allocation. CRoaring allocates every block separately. Under GHC, glibc's malloc always runs in its slower multi-threaded mode, because the runtime keeps a timer thread.

Set GLIBC_TUNABLES=glibc.malloc.tcache_count=65535 to make small-set unions about 3.4 times faster and construction about twice as fast.

In a small range, plain bit arrays (CRoaring's bitset_t and bitvec) build, look up and combine scattered elements fastest. Roaring bitmaps count 70 to 810 times faster than them, and combine a completely filled range fastest:

Some comparisons are unfair to IntSet. It has no rank, range count, allocation-free intersection size or zero-copy loading, so it walks, rebuilds or decodes the set instead. Here Roaring is 1.4 to 2,500 times faster on sparse elements, and 10 to 560,000 times faster on dense ones:

Roaring also takes far less space. In memory, it needs 5 to 6.5 bytes per element on sparse data, where IntSet needs 64. Within a small range it needs about 2, like the plain bit arrays. A completely filled million-element range takes one to two kilobytes, where IntSet needs a megabyte. Serialized, Roaring needs at most about 2.5 bytes per element, where Data.Binary needs 8 (numbers):

Reading elements back in chunks costs about a nanosecond each, while a Haskell callback per element costs about a hundred: