GitHub - RoaringBitmap/CRoaring: Roaring bitmaps in C (and C++), with SIMD (AVX2, AVX-512 and NEON) optimizations: used by Apache Doris, ClickHouse, Alibaba Tair, Redpanda, YDB and StarRocks
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
list of open source C software.
Table of Contents
Using Roaring as a CPM dependency
Using as a CMake dependency with FetchContent
Dealing with large volumes of data
Compressed 64-bit Roaring bitmaps (C)
Building with cmake (Linux and macOS, Visual Studio users should see below)
Building (Visual Studio under Windows)
Usage (Using vcpkg on Windows, Linux and macOS)
How to best aggregate bitmaps?
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
and derivative systems such as
and
,
,
,
,
,
,
,
,
,
,
,
Microsoft Visual Studio Team Services (VSTS)
, and eBay's
. The CRoaring library is used in several systems such as
,
,
,
,
,
,
and
. The YouTube SQL Engine,
, 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
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 (
)
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, and generic scalar builds also work on other architectures such as RISC-V.
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 and RISC-V) do not need runtime dispatch and use the generic path unless a dedicated SIMD backend is added.
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
, or the corresponding
. 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).
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
Create a new file named demo.c with this content: #include<stdio.h>#include<stdlib.h>#include"roaring.c"intmain() { roaring_bitmap_t*r1=roaring_bitmap_create(); for (uint32_ti=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 (intk=0; k<1000; ++k) { bitset_set(b, 3*k); } printf("%zu \n", bitset_count(b)); bitset_free(b); returnEXIT_SUCCESS; }
.
Create a new file named demo.cpp with this content: #include<iostream> #include"roaring.hh"// the amalgamated roaring.hh includes roaring64map.hh and roaring64.hh #include"roaring.c"intmain() { 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; return0; }
Compile cc -o demo demo.c c++ -std=c++11 -o demopp demo.cpp
./democardinality = 900 1000
./demoppcardinality = 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, roaring64map.hh, and roaring64.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>intmain(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_valueroaring_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 bitsassert(roaring64_bitmap_contains(big, 0xFFFFFFFFFFULL)); printf("64-bit cardinality = %d\n", (int)roaring64_bitmap_get_cardinality(big)); roaring64_bitmap_free(big); returnEXIT_SUCCESS; }The C++ API
The C++ classes (roaring::Roaring, roaring::Roaring64Map, and roaring::Roaring64) 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>usingnamespaceroaring;intmain() { // --- 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 bitsassert(big.contains(uint64_t(0xFFFFFFFFFFULL))); std::cout << "64-bit cardinality = " << big.cardinality() << std::endl; returnEXIT_SUCCESS; }For more extensive, fully commented examples (serialization, bulk operations, copy-on-write, aggregating many bitmaps, etc.), see the
and
sections below.
Packages
Using Roaring as a CPM dependency
If you like CMake and CPM, you can add just a few lines in your CMakeLists.txt file to grab a CRoaring release.
See our CPM demonstration for further details
.
cmake_minimum_required(VERSION3.10) project(roaring_demo LANGUAGESCXXC ) set(CMAKE_CXX_STANDARD 17) set(CMAKE_C_STANDARD 11) add_executable(hellohello.cpp) # You can add CPM.cmake like so:# mkdir -p cmake# wget -O cmake/CPM.cmake https://github.com/cpm-cmake/CPM.cmake/releases/latest/download/get_cpm.cmakeinclude(cmake/CPM.cmake) CPMAddPackage( NAMEroaringGITHUB_REPOSITORY"RoaringBitmap/CRoaring"GIT_TAGv2.0.4OPTIONS"ENABLE_ROARING_TESTS OFF" ) target_link_libraries(helloroaring::roaring)Using as a CMake dependency with FetchContent
If you like CMake, you can add just a few lines in your CMakeLists.txt file to grab a CRoaring release.
See our demonstration for further details
.
If you installed the CRoaring library locally, you may use it with CMake's find_package function as in this example:
cmake_minimum_required(VERSION3.15) project(test_roaring_install VERSION 0.1.0 LANGUAGESCXXC) set(CMAKE_CXX_STANDARD 11) set(CMAKE_CXX_STANDARD_REQUIREDON) set(CMAKE_C_STANDARD 11) set(CMAKE_C_STANDARD_REQUIREDON) find_package(roaringREQUIRED) file(WRITEmain.cpp"#include <iostream>#include \"roaring/roaring.hh\"int main() { roaring::Roaring r1; for (uint32_t i = 100; i < 1000; i++) { r1.add(i); } std::cout << \"cardinality = \" << r1.cardinality() << std::endl; return 0;}") add_executable(repromain.cpp) target_link_libraries(reproPUBLICroaring::roaring)Amalgamating
To generate the amalgamated files yourself, you can invoke a bash script...
./amalgamation.shIf you prefer a silent output, you can use the following command to redirect stdout :
./amalgamation.sh > /dev/null(Bash shells are standard under Linux and macOS. Bash shells are available under Windows as part of the
under the name Git Shell. So if you have cloned the CRoaring GitHub repository from within the GitHub Desktop, you can right-click on CRoaring, select Git Shell and then enter the above commands.)
It is not necessary to invoke the script in the CRoaring directory. You can invoke it from any directory where you want the amalgamation files to be written.
It will generate three files for C users: roaring.h, roaring.c and amalgamation_demo.c... as well as some brief instructions. The amalgamation_demo.c file is a short example, whereas roaring.h and roaring.c are "amalgamated" files (including all source and header files for the project). This means that you can simply copy the files roaring.h and roaring.c into your project and be ready to go! No need to produce a library! See the amalgamation_demo.c file.
API
The C interface is found in the files
,
.
We also have a C++ interface:
,
,
.
Main API functions
Below is an overview of the main functions provided by CRoaring in C, covering both 32-bit (roaring.h) and 64-bit (roaring64.h) bitmaps. For more details, see the header files in include/roaring/ or the Doxygen documentation.
Creation and Destruction
roaring_bitmap_t *roaring_bitmap_create(void); Create a new empty 32-bit bitmap.
roaring64_bitmap_t *roaring64_bitmap_create(void); Create a new empty 64-bit bitmap.
void roaring_bitmap_free(roaring_bitmap_t *r); Free a 32-bit bitmap.
void roaring64_bitmap_free(roaring64_bitmap_t *r); Free a 64-bit bitmap.
Adding and Removing Values
void roaring_bitmap_add(roaring_bitmap_t *r, uint32_t x); Add value x to a 32-bit bitmap.
void roaring64_bitmap_add(roaring64_bitmap_t *r, uint64_t x); Add value x to a 64-bit bitmap.
void roaring_bitmap_remove(roaring_bitmap_t *r, uint32_t x); Remove value x from a 32-bit bitmap.
void roaring64_bitmap_remove(roaring64_bitmap_t *r, uint64_t x); Remove value x from a 64-bit bitmap.
Queries and Cardinality
bool roaring_bitmap_contains(const roaring_bitmap_t *r, uint32_t x); Check if x is present in a 32-bit bitmap.
bool roaring64_bitmap_contains(const roaring64_bitmap_t *r, uint64_t x); Check if x is present in a 64-bit bitmap.
uint64_t roaring_bitmap_get_cardinality(const roaring_bitmap_t *r); Get the number of elements in a 32-bit bitmap.
uint64_t roaring64_bitmap_get_cardinality(const roaring64_bitmap_t *r); Get the number of elements in a 64-bit bitmap.
Iteration
bool roaring_iterate(const roaring_bitmap_t *r, roaring_iterator iterator, void *param); Iterate over all values in a 32-bit bitmap, calling iterator for each value.
bool roaring64_bitmap_iterate(const roaring64_bitmap_t *r, roaring_iterator64 iterator, void *param); Iterate over all values in a 64-bit bitmap.
Set Operations
roaring_bitmap_t *roaring_bitmap_and(const roaring_bitmap_t *r1, const roaring_bitmap_t *r2); Intersection (AND) of two 32-bit bitmaps.
roaring64_bitmap_t *roaring64_bitmap_and(const roaring64_bitmap_t *r1, const roaring64_bitmap_t *r2); Intersection (AND) of two 64-bit bitmaps.
roaring_bitmap_t *roaring_bitmap_or(const roaring_bitmap_t *r1, const roaring_bitmap_t *r2); Union (OR) of two 32-bit bitmaps.
roaring64_bitmap_t *roaring64_bitmap_or(const roaring64_bitmap_t *r1, const roaring64_bitmap_t *r2); Union (OR) of two 64-bit bitmaps.
roaring_bitmap_t *roaring_bitmap_xor(const roaring_bitmap_t *r1, const roaring_bitmap_t *r2); Symmetric difference (XOR) of two 32-bit bitmaps.
roaring64_bitmap_t *roaring64_bitmap_xor(const roaring64_bitmap_t *r1, const roaring64_bitmap_t *r2); Symmetric difference (XOR) of two 64-bit bitmaps.
roaring_bitmap_t *roaring_bitmap_andnot(const roaring_bitmap_t *r1, const roaring_bitmap_t *r2); Difference (r1 \ r2) for 32-bit bitmaps.
roaring64_bitmap_t *roaring64_bitmap_andnot(const roaring64_bitmap_t *r1, const roaring64_bitmap_t *r2); Difference (r1 \ r2) for 64-bit bitmaps.
Serialization and Deserialization
size_t roaring_bitmap_portable_size_in_bytes(const roaring_bitmap_t *r); Get the number of bytes required to serialize a 32-bit bitmap.
size_t roaring64_bitmap_portable_size_in_bytes(const roaring64_bitmap_t *r); Get the number of bytes required to serialize a 64-bit bitmap.
size_t roaring_bitmap_portable_serialize(const roaring_bitmap_t *r, char *buf); Serialize a 32-bit bitmap to a buffer (portable format).
size_t roaring64_bitmap_portable_serialize(const roaring64_bitmap_t *r, char *buf); Serialize a 64-bit bitmap to a buffer (portable format).
roaring_bitmap_t *roaring_bitmap_portable_deserialize(const char *buf); Deserialize a 32-bit bitmap from a buffer. This is unsafe: it assumes buf points to a valid serialized bitmap and may read out of bounds otherwise. Prefer the safe variant below for untrusted input.
The 64-bit API does not provide an unsafe deserializer; use roaring64_bitmap_portable_deserialize_safe (below) instead.
roaring_bitmap_t *roaring_bitmap_portable_deserialize_safe(const char *buf, size_t maxbytes); Safe deserialization of a 32-bit bitmap (will not read past maxbytes). If you are loading data from an untrusted source, you should call roaring_bitmap_internal_validate prior to using the roaring_bitmap_t.
roaring64_bitmap_t *roaring64_bitmap_portable_deserialize_safe(const char *buf, size_t maxbytes); Safe deserialization of a 64-bit bitmap (will not read past maxbytes). If you are loading data from an untrusted source, you should call roaring64_bitmap_internal_validate prior to using the roaring64_bitmap_t.
size_t roaring_bitmap_portable_deserialize_size(const char *buf, size_t maxbytes); Get the size of a serialized 32-bit bitmap (returns 0 if invalid).
size_t roaring64_bitmap_portable_deserialize_size(const char *buf, size_t maxbytes); Get the size of a serialized 64-bit bitmap (returns 0 if invalid).
Validation
bool roaring_bitmap_internal_validate(const roaring_bitmap_t *r, const char **reason); Validate the internal structure of a 32-bit bitmap. Returns true if valid, false otherwise. If invalid, reason points to a string describing the problem.
bool roaring64_bitmap_internal_validate(const roaring64_bitmap_t *r, const char **reason); Validate the internal structure of a 64-bit bitmap.
Notes
All memory allocated by the library must be freed using the corresponding free function.
The portable serialization format is cross-platform and can be shared between different languages and architectures.
Always validate bitmaps deserialized from untrusted sources before using them.
C++ API functions
The C++ interface is provided via the roaring.hh (32-bit), roaring64map.hh, and roaring64.hh (64-bit) headers. These offer a modern, type-safe, and convenient API for manipulating Roaring bitmaps in C++.
Main Classes
roaring::Roaring — 32-bit Roaring bitmap
roaring::Roaring64Map — 64-bit Roaring bitmap (std::map-based)
roaring::Roaring64 — 64-bit Roaring bitmap (ART-based C API wrapper; experimental)
Common Methods (32-bit and 64-bit)
Roaring() / Roaring64Map()Construct an empty bitmap.
Roaring(std::initializer_list<uint32_t> values)Construct from a list of values.
void add(uint32_t x) / void add(uint64_t x)Add a value to the bitmap.
void remove(uint32_t x) / void remove(uint64_t x)Remove a value from the bitmap.
bool contains(uint32_t x) const / bool contains(uint64_t x) constCheck if a value is present.
uint64_t cardinality() constGet the number of elements in the bitmap.
bool isEmpty() constCheck if the bitmap is empty.
void clear()Remove all elements.
bool runOptimize()Convert internal containers to run containers for better compression. Returns true if the result has at least one run container.
void setCopyOnWrite(bool enable)Enable or disable copy-on-write mode for fast/shallow copies.
bool operator==(const Roaring&) const / bool operator==(const Roaring64Map&) constEquality comparison.
void swap(Roaring&) / void swap(Roaring64Map&)Swap contents with another bitmap.
Set Operations
Roaring operator|(const Roaring&) const / Roaring64Map operator|(const Roaring64Map&) constUnion (OR)
Roaring operator&(const Roaring&) const / Roaring64Map operator&(const Roaring64Map&) constIntersection (AND)
Roaring operator^(const Roaring&) const / Roaring64Map operator^(const Roaring64Map&) constSymmetric difference (XOR)
Roaring operator-(const Roaring&) const / Roaring64Map operator-(const Roaring64Map&) constDifference
In-place versions: operator|=, operator&=, operator^=, operator-=
Iteration
Roaring::const_iterator / Roaring64Map::const_iteratorStandard C++ iterator support: begin(), end()
void iterate(function, void* param)Call a function for each value (C-style callback).
Serialization and Deserialization
size_t getSizeInBytes() constGet the size in bytes for serialization.
size_t write(char* buf) constSerialize the bitmap to a buffer. Returns how many bytes were written.
static Roaring read(const char* buf, bool portable = true)Deserialize a bitmap from a buffer.
static Roaring readSafe(const char* buf, size_t maxbytes)Safe deserialization (will not read past maxbytes).
Bulk Operations
void addMany(size_t n, const uint32_t* values) / void addMany(size_t n, const uint64_t* values)Add many values at once.
void toUint32Array(uint32_t* out) const / void toUint64Array(uint64_t* out) constExport all values to an array.
Example Usage
#include"roaring/roaring.hh"usingnamespaceroaring; Roaring r1; r1.add(42); if (r1.contains(42)) { // ... } Roaring r2 = Roaring::bitmapOf(3, 1, 2, 3); Roaring r3 = r1 | r2; for (auto v : r3) { // iterate over values }64-bit bitmaps
For 64-bit values, there are two classes. Roaring64Map (roaring64map.hh) keys a std::map by the high 32 bits, each entry a 32-bit Roaring bitmap. Roaring64 (roaring64.hh) wraps the C API's native 64-bit bitmap, which uses an Adaptive Radix Tree with 48-bit keys and 16-bit containers.
Dealing with large volumes of data
Some users have to deal with large volumes of data. It may be important for these users to be aware of the addMany (C++) roaring_bitmap_or_many (C) functions as it is much faster and economical to add values in batches when possible. Furthermore, calling periodically the runOptimize (C++) or roaring_bitmap_run_optimize (C) functions may help.
Running microbenchmarks
We have microbenchmarks constructed with the Google Benchmarks. Under Linux or macOS, you may run them as follows:
cmake -B build -D ENABLE_ROARING_MICROBENCHMARKS=ON cmake --build build ./build/microbenchmarks/bench By default, the benchmark tools picks one data set (e.g., CRoaring/benchmarks/realdata/census1881). We have several data sets and you may pick others:
./build/microbenchmarks/bench benchmarks/realdata/wikileaks-noquotes You may disable some functionality for the purpose of benchmarking. For example, assuming you have an x64 processor, you could benchmark the code without AVX-512 even if both your processor and compiler supports it:
cmake -B buildnoavx512 -D ROARING_DISABLE_AVX512=ON -D ENABLE_ROARING_MICROBENCHMARKS=ON cmake --build buildnoavx512 ./buildnoavx512/microbenchmarks/bench You can benchmark without AVX or AVX-512 as well:
cmake -B buildnoavx -D ROARING_DISABLE_AVX=ON -D ENABLE_ROARING_MICROBENCHMARKS=ON cmake --build buildnoavx ./buildnoavx/microbenchmarks/bench Please see microbenchmarks/README.md for more details.
Custom memory allocators
For general users, CRoaring would apply default allocator without extra codes. But global memory hook is also provided for those who want a custom memory allocator. Here is an example:
#include<roaring.h>intmain(){ // define with your own memory hookroaring_memory_tmy_hook{my_malloc, my_free ...}; // initialize global memory hookroaring_init_memory_hook(my_hook); // write you code here ... }By default we use:
staticroaring_memory_tglobal_memory_hook= { .malloc=malloc, .realloc=realloc, .calloc=calloc, .free=free, .aligned_malloc=roaring_bitmap_aligned_malloc, .aligned_free=roaring_bitmap_aligned_free, };We require that the free/aligned_free functions follow the C convention where free(NULL)/aligned_free(NULL) have no effect.
Memory allocation policy
The CRoaring library makes it easy to provide your own memory allocation functions. If a memory allocation fails (for example, due to an out-of-memory condition), we recommend that you halt your process. We provide no guarantees of consistency or correctness after a memory allocation failure.
Example (C)
This example assumes that CRoaring has been build and that you are linking against the corresponding library. By default, CRoaring will install its header files in a roaring directory. If you are working from the amalgamation script, you may add the line #include "roaring.c" if you are not linking against a prebuilt CRoaring library and replace #include <roaring/roaring.h> by #include "roaring.h".
#include<roaring/roaring.h>#include<stdio.h>#include<stdlib.h>#include<assert.h>boolroaring_iterator_sumall(uint32_tvalue, void*param) { *(uint32_t*)param+=value; return true; // iterate till the end } intmain() { // create a new empty bitmaproaring_bitmap_t*r1=roaring_bitmap_create(); // then we can add valuesfor (uint32_ti=100; i<1000; i++) roaring_bitmap_add(r1, i); // check whether a value is containedassert(roaring_bitmap_contains(r1, 500)); // compute how many bits there are:uint32_tcardinality=roaring_bitmap_get_cardinality(r1); printf("Cardinality = %d \n", cardinality); // if your bitmaps have long runs, you can compress them by calling// run_optimizeuint32_texpectedsizebasic=roaring_bitmap_portable_size_in_bytes(r1); roaring_bitmap_run_optimize(r1); uint32_texpectedsizerun=roaring_bitmap_portable_size_in_bytes(r1); printf("size before run optimize %d bytes, and after %d bytes\n", expectedsizebasic, expectedsizerun); // create a new bitmap containing the values {1,2,3,5,6}roaring_bitmap_t*r2=roaring_bitmap_from(1, 2, 3, 5, 6); roaring_bitmap_printf(r2); // print it// we can also create a bitmap from a pointer to 32-bit integersuint32_tsomevalues[] = {2, 3, 4}; roaring_bitmap_t*r3=roaring_bitmap_of_ptr(3, somevalues); // we can also go in reverse and go from arrays to bitmapsuint64_tcard1=roaring_bitmap_get_cardinality(r1); uint32_t*arr1= (uint32_t*)malloc(card1*sizeof(uint32_t)); assert(arr1!=NULL); roaring_bitmap_to_uint32_array(r1, arr1); roaring_bitmap_t*r1f=roaring_bitmap_of_ptr(card1, arr1); free(arr1); assert(roaring_bitmap_equals(r1, r1f)); // what we recover is equalroaring_bitmap_free(r1f); // we can go from arrays to bitmaps from "offset" by "limit"size_toffset=100; size_tlimit=1000; uint32_t*arr3= (uint32_t*)malloc(limit*sizeof(uint32_t)); assert(arr3!=NULL); roaring_bitmap_range_uint32_array(r1, offset, limit, arr3); free(arr3); // we can copy and compare bitmapsroaring_bitmap_t*z=roaring_bitmap_copy(r3); assert(roaring_bitmap_equals(r3, z)); // what we recover is equalroaring_bitmap_free(z); // we can compute union two-by-tworoaring_bitmap_t*r1_2_3=roaring_bitmap_or(r1, r2); roaring_bitmap_or_inplace(r1_2_3, r3); // we can compute a big unionconstroaring_bitmap_t*allmybitmaps[] = {r1, r2, r3}; roaring_bitmap_t*bigunion=roaring_bitmap_or_many(3, allmybitmaps); assert( roaring_bitmap_equals(r1_2_3, bigunion)); // what we recover is equal// can also do the big union with a heaproaring_bitmap_t*bigunionheap=roaring_bitmap_or_many_heap(3, allmybitmaps); assert(roaring_bitmap_equals(r1_2_3, bigunionheap)); roaring_bitmap_free(r1_2_3); roaring_bitmap_free(bigunion); roaring_bitmap_free(bigunionheap); // we can compute intersection two-by-tworoaring_bitmap_t*i1_2=roaring_bitmap_and(r1, r2); roaring_bitmap_free(i1_2); // we can write a bitmap to a pointer and recover it lateruint32_texpectedsize=roaring_bitmap_portable_size_in_bytes(r1); char*serializedbytes=malloc(expectedsize); // When serializing data to a file, we recommend that you also use// checksums so that, at deserialization, you can be confident// that you are recovering the correct data.roaring_bitmap_portable_serialize(r1, serializedbytes); // Note: it is expected that the input follows the specification// https://github.com/RoaringBitmap/RoaringFormatSpec// otherwise the result may be unusable.// The 'roaring_bitmap_portable_deserialize_safe' function will not read// beyond expectedsize bytes.// We also recommend that you use checksums to check that serialized data corresponds// to the serialized bitmap. The CRoaring library does not provide checksumming.roaring_bitmap_t*t=roaring_bitmap_portable_deserialize_safe(serializedbytes, expectedsize); if(t==NULL) { returnEXIT_FAILURE; } constchar*reason=NULL; // If your input came from an untrusted source, then you need to validate the// resulting bitmap. Failing to do so could lead to undefined behavior, crashes and so forth.if (!roaring_bitmap_internal_validate(t, &reason)) { returnEXIT_FAILURE; } // At this point, the bitmap is safe.assert(roaring_bitmap_equals(r1, t)); // what we recover is equalroaring_bitmap_free(t); // we can also check whether there is a bitmap at a memory location without// reading itsize_tsizeofbitmap=roaring_bitmap_portable_deserialize_size(serializedbytes, expectedsize); assert(sizeofbitmap==expectedsize); // sizeofbitmap would be zero if no bitmap were found// We can also read the bitmap "safely" by specifying a byte size limit.// The 'roaring_bitmap_portable_deserialize_safe' function will not read// beyond expectedsize bytes.// We also recommend that you use checksums to check that serialized data corresponds// to the serialized bitmap. The CRoaring library does not provide checksumming.t=roaring_bitmap_portable_deserialize_safe(serializedbytes, expectedsize); if(t==NULL) { printf("Problem during deserialization.\n"); // We could clear any memory and close any file here.returnEXIT_FAILURE; } // We can validate the bitmap we recovered to make sure it is proper.// If the data came from an untrusted source, you should call// roaring_bitmap_internal_validate.constchar*reason_failure=NULL; if (!roaring_bitmap_internal_validate(t, &reason_failure)) { printf("safely deserialized invalid bitmap: %s\n", reason_failure); // We could clear any memory and close any file here.returnEXIT_FAILURE; } assert(roaring_bitmap_equals(r1, t)); // what we recover is equalroaring_bitmap_free(t); free(serializedbytes); // we can iterate over all values using custom functionsuint32_tcounter=0; roaring_iterate(r1, roaring_iterator_sumall, &counter); // we can also create iterator structscounter=0; roaring_uint32_iterator_t*i=roaring_iterator_create(r1); while (i->has_value) { counter++; // could use i->current_valueroaring_uint32_iterator_advance(i); } // you can skip over values and move the iterator with// roaring_uint32_iterator_move_equalorlarger(i,someintvalue)roaring_uint32_iterator_free(i); // roaring_bitmap_get_cardinality(r1) == counter// for greater speed, you can iterate over the data in bulki=roaring_iterator_create(r1); uint32_tbuffer[256]; while (1) { uint32_tret=roaring_uint32_iterator_read(i, buffer, 256); for (uint32_tj=0; j<ret; j++) { counter+=buffer[j]; } if (ret<256) { break; } } roaring_uint32_iterator_free(i); roaring_bitmap_free(r1); roaring_bitmap_free(r2); roaring_bitmap_free(r3); returnEXIT_SUCCESS; }Compressed 64-bit Roaring bitmaps (C)
We also support efficient 64-bit compressed bitmaps in C:
roaring64_bitmap_t *r2 = roaring64_bitmap_create(); for (uint64_t i = 100; i < 1000; i++) roaring64_bitmap_add(r2, i); printf("cardinality (64-bit) = %d\n", (int) roaring64_bitmap_get_cardinality(r2)); roaring64_bitmap_free(r2);The API is similar to the conventional 32-bit bitmaps. Please see the header file roaring64.h (compare with roaring.h).
Conventional bitsets (C)
We support convention bitsets (uncompressed) as part of the library.
Simple example:
bitset_t*b=bitset_create(); bitset_set(b,10); bitset_get(b,10);// returns truebitset_free(b); // frees memoryMore advanced example:
bitset_t*b=bitset_create(); for (intk=0; k<1000; ++k) { bitset_set(b, 3*k); } // We have bitset_count(b) == 1000.// We have bitset_get(b, 3) is true// You can iterate through the values:size_tk=0; for (size_ti=0; bitset_next_set_bit(b, &i); i++) { // You will have i == kk+=3; } // We support a wide range of operations on two bitsets such as// bitset_inplace_symmetric_difference(b1,b2);// bitset_inplace_symmetric_difference(b1,b2);// bitset_inplace_difference(b1,b2);// should make no difference// bitset_inplace_union(b1,b2);// bitset_inplace_intersection(b1,b2);// bitsets_disjoint// bitsets_intersectIn some instances, you may want to convert a Roaring bitmap into a conventional (uncompressed) bitset. Indeed, bitsets have advantages such as higher query performances in some cases. The following code illustrates how you may do so:
roaring_bitmap_t*r1=roaring_bitmap_create(); for (uint32_ti=100; i<100000; i+=1+ (i%5)) { roaring_bitmap_add(r1, i); } for (uint32_ti=100000; i<500000; i+=100) { roaring_bitmap_add(r1, i); } roaring_bitmap_add_range(r1, 500000, 600000); bitset_t*bitset=bitset_create(); boolsuccess=roaring_bitmap_to_bitset(r1, bitset); assert(success); // could fail due to memory allocation.assert(bitset_count(bitset) ==roaring_bitmap_get_cardinality(r1)); // You can then query the bitset:for (uint32_ti=100; i<100000; i+=1+ (i%5)) { assert(bitset_get(bitset,i)); } for (uint32_ti=100000; i<500000; i+=100) { assert(bitset_get(bitset,i)); } // you must free the memory:bitset_free(bitset); roaring_bitmap_free(r1);You should be aware that a convention bitset (bitset_t *) may use much more memory than a Roaring bitmap in some cases. You should run benchmarks to determine whether the conversion to a bitset has performance benefits in your case.
Example (C++)
This example assumes that CRoaring has been build and that you are linking against the corresponding library. By default, CRoaring will install its header files in a roaring directory so you may need to replace #include "roaring.hh" by #include <roaring/roaring.hh>. If you are working from the amalgamation script, you may add the line #include "roaring.c" if you are not linking against a CRoaring prebuilt library.
#include<iostream> #include"roaring.hh"usingnamespaceroaring;intmain() { Roaring r1; for (uint32_t i = 100; i < 1000; i++) { r1.add(i); } // check whether a value is containedassert(r1.contains(500)); // compute how many bits there are:uint32_t cardinality = r1.cardinality(); // if your bitmaps have long runs, you can compress them by calling// run_optimizeuint32_t size = r1.getSizeInBytes(); r1.runOptimize(); // you can enable "copy-on-write" for fast and shallow copies r1.setCopyOnWrite(true); uint32_t compact_size = r1.getSizeInBytes(); std::cout << "size before run optimize " << size << " bytes, and after " << compact_size << " bytes." << std::endl; // create a new bitmap with varargs Roaring r2 = Roaring::bitmapOf(5, 1, 2, 3, 5, 6); r2.printf(); printf("\n"); // create a new bitmap with initializer list Roaring r2i = Roaring::bitmapOfList({1, 2, 3, 5, 6}); assert(r2i == r2); // we can also create a bitmap from a pointer to 32-bit integersconstuint32_t values[] = {2, 3, 4}; Roaring r3(3, values); // we can also go in reverse and go from arrays to bitmapsuint64_t card1 = r1.cardinality(); uint32_t *arr1 = newuint32_t[card1]; r1.toUint32Array(arr1); Roaring r1f(card1, arr1); delete[] arr1; // bitmaps shall be equalassert(r1 == r1f); // we can copy and compare bitmaps Roaring z(r3); assert(r3 == z); // we can compute union two-by-two Roaring r1_2_3 = r1 | r2; r1_2_3 |= r3; // we can compute a big unionconst Roaring *allmybitmaps[] = {&r1, &r2, &r3}; Roaring bigunion = Roaring::fastunion(3, allmybitmaps); assert(r1_2_3 == bigunion); // we can compute intersection two-by-two Roaring i1_2 = r1 & r2; // we can write a bitmap to a pointer and recover it lateruint32_t expectedsize = r1.getSizeInBytes(); char *serializedbytes = newchar[expectedsize]; r1.write(serializedbytes); // readSafe will not overflow, but the resulting bitmap// is only valid and usable if the input follows the// Roaring specification: https://github.com/RoaringBitmap/RoaringFormatSpec/ Roaring t = Roaring::readSafe(serializedbytes, expectedsize); assert(r1 == t); delete[] serializedbytes; // we can iterate over all values using custom functionsuint32_t counter = 0; r1.iterate( [](uint32_t value, void *param) { *(uint32_t *)param += value; returntrue; }, &counter); // we can also iterate the C++ way counter = 0; for (Roaring::const_iterator i = t.begin(); i != t.end(); i++) { ++counter; } // counter == t.cardinality()// we can move iterators to skip valuesconstuint32_t manyvalues[] = {2, 3, 4, 7, 8}; Roaring rogue(5, manyvalues); Roaring::const_iterator j = rogue.begin(); j.move_equalorlarger(4); // *j == 4returnEXIT_SUCCESS; } Building with cmake (Linux and macOS, Visual Studio or OpenHarmony users should see below)
CRoaring follows the standard cmake workflow. Starting from the root directory of the project (CRoaring), you can do:
mkdir -p build cd build cmake .. cmake --build . # follow by 'ctest' if you want to test. # you can also type 'make install' to install the library on your system # C header files typically get installed to /usr/local/include/roaring # whereas C++ header files get installed to /usr/local/include/roaring (You can replace the build directory with any other directory name.) By default all tests are built on all platforms, to skip building and running tests add -DENABLE_ROARING_TESTS=OFF to the command line.
As with all cmake projects, you can specify the compilers you wish to use by adding (for example) -DCMAKE_C_COMPILER=gcc -DCMAKE_CXX_COMPILER=g++ to the cmake command line.
If you are using clang or gcc and you know your target architecture, you can set the architecture by specifying -DROARING_ARCH=arch. For example, if you have many server but the oldest server is running the Intel haswell architecture, you can specify -DROARING_ARCH=haswell. In such cases, the produced binary will be optimized for processors having the characteristics of a haswell process and may not run on older architectures. You can find out the list of valid architecture values by typing man gcc.
mkdir -p build_haswell cd build_haswell cmake -DROARING_ARCH=haswell .. cmake --build . For a debug release, starting from the root directory of the project (CRoaring), try
mkdir -p debug cd debug cmake -DCMAKE_BUILD_TYPE=Debug -DROARING_SANITIZE=ON .. ctest To check that your code abides by the style convention (make sure that clang-format is installed):
./tools/clang-format-check.sh To reformat your code according to the style convention (make sure that clang-format is installed):
./tools/clang-format.sh Building (Visual Studio under Windows)
We are assuming that you have a common Windows PC with at least Visual Studio 2015, and an x64 processor.
To build with at least Visual Studio 2015 from the command line:
Grab the CRoaring code from GitHub, e.g., by cloning it using
.
Install
. When you install it, make sure to ask that cmake be made available from the command line.
Create a subdirectory within CRoaring, such as VisualStudio.
Using a shell, go to this newly created directory. For example, within GitHub Desktop, you can right-click on CRoaring in your GitHub repository list, and select Open in Git Shell, then type cd VisualStudio in the newly created shell.
Type cmake -DCMAKE_GENERATOR_PLATFORM=x64 .. in the shell while in the VisualStudio repository. (Alternatively, if you want to build a static library, you may use the command line cmake -DCMAKE_GENERATOR_PLATFORM=x64 -DROARING_BUILD_STATIC=ON ...)
This last command created a Visual Studio solution file in the newly created directory (e.g., RoaringBitmap.sln). Open this file in Visual Studio. You should now be able to build the project and run the tests. For example, in the Solution Explorer window (available from the View menu), right-click ALL_BUILD and select Build. To test the code, still in the Solution Explorer window, select RUN_TESTS and select Build.
To build with at least Visual Studio 2017 directly in the IDE:
Grab the CRoaring code from GitHub, e.g., by cloning it using
.
Select the Visual C++ tools for CMake optional component when installing the C++ Development Workload within Visual Studio.
Within Visual Studio use File > Open > Folder... to open the CRoaring folder.
Right click on CMakeLists.txt in the parent directory within Solution Explorer and select Build to build the project.
For testing, in the Standard toolbar, drop the Select Startup Item... menu and choose one of the tests. Run the test by pressing the button to the left of the dropdown.
We have optimizations specific to AVX2 and AVX-512 in the code, and they are turned dynamically based on the detected hardware at runtime.
Usage (Using conan)
You can install pre-built binaries for roaring or build it from source using
. Use the following command to install latest version:
conan install --requires="roaring/[*]" --build=missing For detailed instructions on how to use Conan, please refer to the
.
The roaring Conan recipe is kept up to date by Conan maintainers and community contributors. If the version is out of date, please
create an issue or pull request
on the ConanCenterIndex repository.
Usage (Using vcpkg on Windows, Linux and macOS)
users on Windows, Linux and macOS can download and install roaring with one single command from their favorite shell.
On Linux and macOS:
$ ./vcpkg install roaring will build and install roaring as a static library.
On Windows (64-bit):
.\vcpkg.exe install roaring:x64-windows will build and install roaring as a shared library.
.\vcpkg.exe install roaring:x64-windows-static will build and install roaring as a static library.
These commands will also print out instructions on how to use the library from MSBuild or CMake-based projects.
If you find the version of roaring shipped with vcpkg is out-of-date, feel free to report it to vcpkg community either by submiting an issue or by creating a PR.
Building (OpenHarmony)
To build with OpenHarmony SDK please see the [OpenHarmony Cross Compile Guide](
https://gitcode.com/openharmony-sig/tpc_c_cplusplus/blob/master/Cross-Compilation
Guide for Open-Source Third-Party Libraries in OpenHarmony_en.md)
SIMD-related throttling
Our AVX2 code does not use floating-point numbers or multiplications, so it is not subject to turbo frequency throttling on many-core Intel processors.
Our AVX-512 code is only enabled on recent hardware (Intel Ice Lake or better and AMD Zen 4) where SIMD-specific frequency throttling is not observed.
Thread safety
Like, for example, STL containers, the CRoaring library has no built-in thread support. Thus whenever you modify a bitmap in one thread, it is unsafe to query it in others. However, you can safely copy a bitmap and use both copies in concurrently.
If you use "copy-on-write" (default to disabled), then you should pass copies to the different threads. They will create shared containers, and for shared containers, we use reference counting with an atomic counter.
To summarize:
If you do not use copy-on-write, you can access concurrent the same bitmap safely as long as you do not modify it. If you plan on modifying it, you should pass different copies to the different threads.
If you use copy-on-write, you should always pass copies to the different threads. The copies are then lightweight (shared containers).
Thus the following pattern where you copy bitmaps and pass them to different threads is safe with or without COW:
roaring_bitmap_set_copy_on_write(r1, true); roaring_bitmap_set_copy_on_write(r2, true); roaring_bitmap_set_copy_on_write(r3, true); roaring_bitmap_t*r1a=roaring_bitmap_copy(r1); roaring_bitmap_t*r1b=roaring_bitmap_copy(r1); roaring_bitmap_t*r2a=roaring_bitmap_copy(r2); roaring_bitmap_t*r2b=roaring_bitmap_copy(r2); roaring_bitmap_t*r3a=roaring_bitmap_copy(r3); roaring_bitmap_t*r3b=roaring_bitmap_copy(r3); roaring_bitmap_t*rarray1[3] = {r1a, r2a, r3a}; roaring_bitmap_t*rarray2[3] = {r1b, r2b, r3b}; std::threadthread1(run, rarray1); std::threadthread2(run, rarray2);How to best aggregate bitmaps?
Suppose you want to compute the union (OR) of many bitmaps. How do you proceed? There are many different strategies.
You can use roaring_bitmap_or_many(bitmapcount, bitmaps) or roaring_bitmap_or_many_heap(bitmapcount, bitmaps) or you may even roll your own aggregation:
roaring_bitmap_t*answer=roaring_bitmap_copy(bitmaps[0]); for (size_ti=1; i<bitmapcount; i++) { roaring_bitmap_or_inplace(answer, bitmaps[i]); }All of them will work but they have different performance characteristics. The roaring_bitmap_or_many_heap should probably only be used if, after benchmarking, you find that it is faster by a good margin: it uses more memory.
The roaring_bitmap_or_many is meant as a good default. It works by trying to delay work as much as possible. However, because it delays computations, it also does not optimize the format as the computation runs. It might thus fail to see some useful pattern in the data such as long consecutive values.
The approach based on repeated calls to roaring_bitmap_or_inplace is also fine, and might even be faster in some cases. You can expect it to be faster if, after a few calls, you get long sequences of consecutive values in the answer. That is, if the final answer is all integers in the range [0,1000000), and this is apparent quickly, then the later roaring_bitmap_or_inplace will be very fast.
You should benchmark these alternatives on your own data to decide what is best.
Wrappers for Roaring Bitmaps
This page lists several community-contributed wrappers for the Roaring Bitmap library, enabling its use in various programming languages and environments.
Python
Tom Cornebize developed a Python wrapper, PyRoaringBitMap, which can be found at
https://github.com/Ezibenroc/PyRoaringBitMap
.
Installation is straightforward using pip:
pip install pyroaring JavaScript (Node.js)
Salvatore Previti created a Node.js wrapper, roaring-node, available at
https://github.com/SalvatorePreviti/roaring-node
.
You can install it via npm with the following command:
npm install roaring Swift
Jérémie Piotte authored the
.
C#
There is a C# wrapper, CRoaring.Net, located at
https://github.com/k-wojcik/Roaring.Net
. This wrapper is compatible with Windows and Linux on x64 processors.
Go (Golang)
A Go wrapper is available at the official RoaringBitmap GitHub organization:
https://github.com/RoaringBitmap/gocroaring
.
Rust
Saulius Grigaliunas developed a Rust wrapper, croaring-rs, which can be found at
https://github.com/saulius/croaring-rs
.
D
Yuce Tekol created a D wrapper, droaring, available at
https://github.com/yuce/droaring
.
Redis Module
Antonio Guilherme Ferreira Viggiano wrote a Redis Module integrating Roaring Bitmaps, available at
https://github.com/aviggiano/redis-roaring
.
Zig
Justin Whear contributed a Zig wrapper, located at
https://github.com/jwhear/roaring-zig
.
Mailing list/discussion group
https://groups.google.com/forum/#!forum/roaring-bitmaps
Contributing
When contributing a change to the project, please run tools/run-clangcldocker.sh after making any changes if you have docker and bash. A github action runs on all PRs to ensure formatting is consistent with this.
If you are using AI, please review our
.
For large PRs, prefer smaller incremental PRs or request staged review.
Contributions are licensed under the project’s license. Ensure your work complies and does not infringe on third-party rights.
A compiler or static-analyzer warning is not a bug. Do not report such cases as bugs. We do accept pull requests if you want to silence warnings issued by code analyzers, however.
Stars
References about Roaring
Daniel Lemire, Owen Kaser, Nathan Kurz, Luca Deri, Chris O'Hara, François Saint-Jacques, Gregory Ssi-Yan-Kai, Roaring Bitmaps: Implementation of an Optimized Software Library, Software: Practice and Experience Volume 48, Issue 4 April 2018 Pages 867-895
Samy Chambi, Daniel Lemire, Owen Kaser, Robert Godin, Better bitmap performance with Roaring bitmaps, Software: Practice and Experience Volume 46, Issue 5, pages 709–719, May 2016
Daniel Lemire, Gregory Ssi-Yan-Kai, Owen Kaser, Consistently faster and smaller compressed bitmaps with Roaring, Software: Practice and Experience Volume 46, Issue 11, pages 1547-1569, November 2016
Samy Chambi, Daniel Lemire, Robert Godin, Kamel Boukhalfa, Charles Allen, Fangjin Yang, Optimizing Druid with Roaring bitmaps, IDEAS 2016, 2016.