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.
- Introduction
- Objective
- Requirements
- Quick Start
- How to use the library?
- Packages
- Using Roaring as a CPM dependency
- Using as a CMake dependency with FetchContent
- Amalgamating
- API
- 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)
- SIMD-related throttling
- Thread safety
- How to best aggregate bitmaps?
- Wrappers for Roaring Bitmaps
- Mailing list/discussion group
- Contributing
- References about Roaring
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