CRoaring

Portable Roaring bitmaps in C (and C++) with full support for your favorite compiler (GNU GCC, LLVM's clang, Visual Studio, Apple Xcode, Intel oneAPI). Included in the Awesome C list of open source C software.

Table of Contents

• Introduction
• Objective
• Requirements
• Quick Start
• How to use the library?
• The C API
• The C++ API
• Packages
• Using Roaring as a CPM dependency
• Using as a CMake dependency with FetchContent
• Amalgamating
• API
• Main API functions
• C++ API functions
• Dealing with large volumes of data
• Running microbenchmarks
• Custom memory allocators
• Example (C)
• Compressed 64-bit Roaring bitmaps (C)
• Conventional bitsets (C)
• Example (C++)
• Building with cmake (Linux and macOS, Visual Studio users should see below)
• Building (Visual Studio under Windows)
• Usage (Using conan)
• Usage (Using vcpkg on Windows, Linux and macOS)
• SIMD-related throttling
• Thread safety
• How to best aggregate bitmaps?
• Wrappers for Roaring Bitmaps
• Mailing list/discussion group
• Contributing
• References about Roaring

Introduction

Bitsets, also called bitmaps, are commonly used as fast data structures. Unfortunately, they can use too much memory. To compensate, we often use compressed bitmaps.

Roaring bitmaps are compressed bitmaps which tend to outperform conventional compressed bitmaps such as WAH, EWAH or Concise. They are used by several major systems such as Apache Lucene and derivative systems such as Solr and Elasticsearch, Metamarkets' Druid, LinkedIn Pinot, Netflix Atlas, Apache Spark, OpenSearchServer, Cloud Torrent, Whoosh, InfluxDB, Pilosa, Bleve, Microsoft Visual Studio Team Services (VSTS), and eBay's Apache Kylin. The CRoaring library is used in several systems such as Apache Doris, ClickHouse, Redpanda, YDB, Alibaba Tair, clice, biscuit and StarRocks. The YouTube SQL Engine, Google Procella, uses Roaring bitmaps for indexing.

We published a peer-reviewed article on the design and evaluation of this library:

• Roaring Bitmaps: Implementation of an Optimized Software Library, Software: Practice and Experience 48 (4), 2018 arXiv:1709.07821

Roaring bitmaps are found to work well in many important applications:

Use Roaring for bitmap compression whenever possible. Do not use other bitmap compression methods (Wang et al., SIGMOD 2017)

There is a serialized format specification for interoperability between implementations. Hence, it is possible to serialize a Roaring Bitmap from C++, read it in Java, modify it, serialize it back and read it in Go and Python.

Objective

The primary goal of the CRoaring is to provide a high performance low-level implementation that fully take advantage of the latest hardware. Roaring bitmaps are already available on a variety of platform through Java, Go, Rust... implementations. CRoaring is a library that seeks to achieve superior performance by staying close to the latest hardware.

(c) 2016-... The CRoaring authors.

Requirements

• Linux, macOS, FreeBSD, Windows (MSYS2 and Microsoft Visual studio).
• We test the library with ARM, x64/x86 and POWER processors. We support big endian systems.
• Recent C compiler supporting the C11 standard (GCC 7 or better, LLVM 8 or better (clang), Xcode 11 or better, Microsoft Visual Studio 2022 or better, Intel oneAPI Compiler 2023.2 or better), there is also an optional C++ class that requires a C++ compiler supporting the C++11 standard. We support Fil-C, the memory-safe C/C++ compiler.
• CMake (to contribute to the project, users can rely on amalgamation/unity builds if they do not wish to use CMake).
• The CMake system assumes that git is available.
• Under x64 systems, the library provides runtime dispatch so that optimized functions are called based on the detected CPU features. It works with GCC, clang (version 9 and up) and Visual Studio (2017 and up). Other systems (e.g., ARM) do not need runtime dispatch.

Quick Start

The CRoaring library can be amalgamated into a single source file that makes it easier for integration into other projects. Moreover, by making it possible to compile all the critical code into one compilation unit, it can improve the performance. For the rationale, please see the SQLite documentation, or the corresponding Wikipedia entry. Users who choose this route, do not need to rely on CRoaring's build system (based on CMake).

We offer amalgamated files as part of each release.

Linux or macOS users might follow the following instructions if they have a recent C or C++ compiler installed and a standard utility (wget).

1. Pull the library in a directory wget https://github.com/RoaringBitmap/CRoaring/releases/download/v2.1.0/roaring.c wget https://github.com/RoaringBitmap/CRoaring/releases/download/v2.1.0/roaring.h wget https://github.com/RoaringBitmap/CRoaring/releases/download/v2.1.0/roaring.hh
2. Create a new file named demo.c with this content: ```C #include #include #include "roaring.c" int main() { roaring_bitmap_t *r1 = roaring_bitmap_create(); for (uint32_t i = 100; i < 1000; i++) roaring_bitmap_add(r1, i); printf("cardinality = %d\n", (int) roaring_bitmap_get_cardinality(r1)); roaring_bitmap_free(r1);

   bitset_t *b = bitset_create();
   for (int k = 0; k < 1000; ++k) {
           bitset_set(b, 3 * k);
   }
   printf("%zu \n", bitset_count(b));
   bitset_free(b);
   return EXIT_SUCCESS;
   

   } [You can try it out on Godbolt](https://godbolt.org/z/Y6oMGEo97). 2. Create a new file named `demo.cpp` with this content:C++

   include

   include "roaring.hh" // the amalgamated roaring.hh includes roaring64map.hh

   include "roaring.c"

   int main() { roaring::Roaring r1; for (uint32_t i = 100; i < 1000; i++) { r1.add(i); } std::cout << "cardinality = " << r1.cardinality() << std::endl;

   roaring::Roaring64Map r2;
   for (uint64_t i = 18000000000000000100ull; i < 18000000000000001000ull; i++) {
       r2.add(i);
   }
   std::cout << "cardinality = " << r2.cardinality() << std::endl;
   return 0;
   

   } 2. Compile cc -o demo demo.c c++ -std=c++11 -o demopp demo.cpp 3. `./demo` cardinality = 900 1000 4. `./demopp` cardinality = 900 cardinality = 900 ```

How to use the library?

The library offers both a C API (roaring.h for 32-bit bitmaps, roaring64.h for 64-bit bitmaps) and a C++ API (roaring.hh and roaring64map.hh). The two short programs below cover the most common operations: creating a bitmap, adding values, querying it, combining bitmaps with set operations, and iterating over the values. Both programs are part of our test suite, so they are guaranteed to compile and run.

The C API

Each bitmap you create with roaring_bitmap_create() (or that is returned by a set operation such as roaring_bitmap_and()) must be released with roaring_bitmap_free().

#include <roaring/roaring.h>
#include <roaring/roaring64.h>

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

int main(void) {
    // --- 32-bit bitmaps ---
    // Create an empty bitmap and add a few values.
    roaring_bitmap_t *bitmap = roaring_bitmap_create();
    roaring_bitmap_add(bitmap, 1);
    roaring_bitmap_add(bitmap, 100);
    roaring_bitmap_add(bitmap, 1000);
    roaring_bitmap_add_range(bitmap, 10, 20);  // adds the half-open range [10, 20)

    // Query the bitmap.
    assert(roaring_bitmap_contains(bitmap, 100));
    assert(!roaring_bitmap_contains(bitmap, 50));
    printf("32-bit cardinality = %d\n",
           (int)roaring_bitmap_get_cardinality(bitmap));

    // Optionally compress runs of consecutive values for a smaller footprint.
    roaring_bitmap_run_optimize(bitmap);

    // Set operations return a new bitmap that you own and must free.
    roaring_bitmap_t *other = roaring_bitmap_from(100, 1000, 5000);
    roaring_bitmap_t *intersection = roaring_bitmap_and(bitmap, other);
    assert(roaring_bitmap_get_cardinality(intersection) == 2);  // {100, 1000}

    // Iterate over the values in sorted (increasing) order.
    roaring_uint32_iterator_t *it = roaring_iterator_create(bitmap);
    while (it->has_value) {
        // do something with it->current_value
        roaring_uint32_iterator_advance(it);
    }
    roaring_uint32_iterator_free(it);

    roaring_bitmap_free(intersection);
    roaring_bitmap_free(other);
    roaring_bitmap_free(bitmap);

    // --- 64-bit bitmaps (same ideas, but with 64-bit values) ---
    roaring64_bitmap_t *big = roaring64_bitmap_create();
    roaring64_bitmap_add(big, 1);
    roaring64_bitmap_add(big, 0xFFFFFFFFFFULL);  // a value beyond 32 bits
    assert(roaring64_bitmap_contains(big, 0xFFFFFFFFFFULL));
    printf("64-bit cardinality = %d\n",
           (int)roaring64_bitmap_get_cardinality(big));
    roaring64_bitmap_free(big);

    return EXIT_SUCCESS;
}

The C++ API

The C++ classes (roaring::Roaring and roaring::Roaring64Map) wrap the C API and manage memory for you: the destructor frees the bitmap, and set operations are exposed as operators (&, |, ^, -). No explicit free is required.

#include <roaring/roaring.hh>
#include <roaring/roaring64map.hh>

#include <cassert>
#include <iostream>

using namespace roaring;

int main() {
    // --- 32-bit bitmaps ---
    Roaring r;
    r.add(1);
    r.add(100);
    r.add(1000);
    r.addRange(10, 20);  // adds the half-open range [10, 20)

    assert(r.contains(100));
    assert(!r.contains(50));
    std::cout << "32-bit cardinality = " << r.cardinality() << std::endl;

    // Construct a bitmap directly from a list of values.
    Roaring other = Roaring::bitmapOfList({100, 1000, 5000});

    // Operators return new bitmaps; their memory is managed for you.
    Roaring intersection = r & other;
    assert(intersection.cardinality() == 2);  // {100, 1000}

    // Range-based iteration visits the values in sorted (increasing) order.
    uint64_t sum = 0;
    for (uint32_t value : r) {
        sum += value;
    }
    std::cout << "sum of values = " << sum << std::endl;

    // --- 64-bit bitmaps ---
    Roaring64Map big;
    big.add(uint64_t(1));
    big.add(uint64_t(0xFFFFFFFFFFULL));  // a value beyond 32 bits
    assert(big.contains(uint64_t(0xFFFFFFFFFFULL)));
    std::cout << "64-bit cardinality = " << big.cardinality() << std::endl;

    return EXIT_SUCCESS;
}

For more extensive, fully commented examples (serialization, bulk operations, copy-on-write, aggregating many bitmaps, etc.), see the Example (C) and Example (C++) sections below.

Packages

Using Roaring as a C