# croaring-ffi
Raw Haskell bindings to a bundled copy of [CRoaring](https://github.com/RoaringBitmap/CRoaring), the C implementation of [Roaring bitmaps](https://roaringbitmap.org/).
## Usage
```haskell
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](https://github.com/RoaringBitmap/CRoaring/blob/master/include/roaring/roaring.h) 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:
```haskell
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](https://gitlab.com/dpwiz/croaring-ffi/-/blob/main/bench/results.csv)):
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](https://hackage.haskell.org/package/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](https://gitlab.com/dpwiz/croaring-ffi/-/blob/main/bench/sizes.csv)):
Reading elements back in chunks costs about a nanosecond each, while a Haskell callback per element costs about a hundred:
