CRoaring

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, 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 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
   bash复制

   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 <stdio.h>
   #include <stdlib.h>
   #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.
3. Create a new file named demo.cpp with this content:

…

1. Compile
   复制

   cc -o demo demo.c
   c++ -std=c++11 -o demopp demo.cpp

2. ./demo
   复制

   cardinality = 900
   1000

3. ./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, 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().

…

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.

…

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 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(VERSION 3.10)
project(roaring_demo
  LANGUAGES CXX C
)
set(CMAKE_CXX_STANDARD 17)
set(CMAKE_C_STANDARD 11)

add_executable(hello hello.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.cmake
include(cmake/CPM.cmake)
CPMAddPackage(
  NAME roaring
  GITHUB_REPOSITORY "RoaringBitmap/CRoaring"
  GIT_TAG v2.0.4
  OPTIONS "ENABLE_ROARING_TESTS OFF"
)

target_link_libraries(hello roaring::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:

…

Amalgamating

To generate the amalgamated files yourself, you can invoke a bash script...

./amalgamation.sh

If 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  GitHub Desktop 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 ``r