# Bitmap arrays: RoaringBitmap, not yet wrapped for Julia

**URL:** https://discourse.julialang.org/t/bitmap-arrays-roaringbitmap-not-yet-wrapped-for-julia/98340
**Category:** Offtopic
**Created:** [May 4, 2023, 7:05pm UTC](https://discourse.julialang.org/t/bitmap-arrays-roaringbitmap-not-yet-wrapped-for-julia/98340 "2023-05-04T19:05:00Z")
**Posts on this page:** 1
**Page:** 1

<div class="post-metadata">

### Author: ![Palli](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/palli/32/3380_2.png) [@Palli](https://discourse.julialang.org/u/Palli)
#### Post date: [May 4, 2023, 7:05pm UTC](https://discourse.julialang.org/t/bitmap-arrays-roaringbitmap-not-yet-wrapped-for-julia/98340/1 "2023-05-04T19:05:01Z")

</div>

Bitmaps have some pitfalls, either bits take 8x the storage, stored in a byte, or you have false sharing and problems with threads (I understand the container in C++ considered buggy, and in Julia likely in the same way). But even that space-efficient format isn’t as efficient as it could be. Many languages wrap CRoaring and likely Julia should too:

[https://roaringbitmap.org](https://roaringbitmap.org)

> **[RoaringBitmap Performance Tricks](https://richardstartin.github.io/posts/roaringbitmap-performance-tricks)**
>
> I have made various contributions to the RoaringBitmap Java library since early 2017, often creating performance improvements. Sometimes these performance improvements are completely transparent and just kick in when users update version, but some of...

> Wherever you could imagine using a `BitSet`, you could use a `RoaringBitmap`, and often profit from the compression. There are two benefits of compression:
> 
> 1. Take up less space in RAM and on disk.
> 2. Taking up less space means faster operations because of better memory locality and cache efficiency.
> 
> Knowing a little bit about the compression mechanism helps understand when to use it (or not) and how _not_ to benchmark it. The compression mechanism is prefix compression: the higher 16 bits of each value are stored in an array in the top level of a tree. The lower 16 bits of each value are stored in a _container_ which stores all of the values in a range corresponding to the same higher 16 bits. Recognising that each 16 bit range can have different density and clustering characteristics, there are three types of container, always requiring less than 8KB:
> 
> 1. **Sparse** : `ArrayContainer` - a sorted array of 16 bit values plus a 16 bit cardinality. Always fewer than 4096 elements.
> 2. **Dense** : `BitmapContainer` - a `long[]` just like `java.util.BitSet`, requires one bit per value, plus a 16 bit cardinality. Never fewer than 4096 elements.
> 3. **Really dense, or clustered** : `RunContainer` - another sorted array of 16 bit values, where each even value is the start of a _run_ of set bits, and each odd value is the length of the run. Converted to whenever it saves space.