Roaring Bitmaps are one of those data structures that most developers do not hear about often, but they power serious large-scale systems.

In this video, I show a simple C# benchmark comparing three ways to find the intersection between large sets of integer IDs:

List of int
HashSet of int
Roaring Bitmap

The result:
List of int: around 38–43 seconds
HashSet of int: around 3–4 milliseconds
Roaring Bitmap: around 70–120 microseconds

The lesson is not that Roaring Bitmaps should replace every collection. The lesson is that when you are working with huge sets of integer IDs and need fast AND, OR, COUNT, and intersection operations, Roaring Bitmaps can give you incredible performance.

Roaring Bitmaps and roaring-style bitmap indexes are used across major search, analytics, observability, and data systems, including Apache Lucene, Elasticsearch, Apache Spark, Apache Druid, Apache Pinot, Netflix Atlas, Microsoft Visual Studio Team Services / Azure DevOps Services history, Google Procella / YouTube SQL Engine, Datadog Husky, InfluxDB, Weaviate, Sourcegraph, M3, Redpanda, and many others.

GitHub repo for this demo:
https://github.com/hassanhabib/RoaringBitMapsDemoDotNet

NuGet package used:
https://www.nuget.org/packages/Roaring.Net

Research papers and references:
https://arxiv.org/abs/1402.6407
https://arxiv.org/abs/1603.06549
https://arxiv.org/abs/1709.07821

Official Roaring Bitmaps:
https://roaringbitmap.org/

CRoaring:
https://github.com/RoaringBitmap/CRoaring

Java RoaringBitmap:
https://github.com/RoaringBitmap/RoaringBitmap

Go RoaringBitmap:
https://github.com/RoaringBitmap/roaring

Google Procella / YouTube SQL Engine:
https://research.google/pubs/procella-unifying-serving-and-analytical-data-at-youtube/

Datadog Husky:
https://www.datadoghq.com/blog/engineering/introducing-husky/
https://www.datadoghq.com/blog/engineering/husky-query-architecture/

Chapters:
00:00 The performance result first
00:37 Why this matters for enterprise systems
01:24 What are Roaring Bitmaps?
02:05 Coffee and bread example
03:10 Why normal list intersections are expensive
04:00 The simple range/compression mental model
05:15 Building the List of int example
06:07 Running the slow List of int version
06:37 Building the HashSet of int example
07:20 HashSet of int performance improvement
08:19 Introducing Roaring Bitmaps in C#
09:10 Creating Roaring32Bitmap sets
10:05 Adding ranges of user IDs
10:52 Optimizing the bitmaps
11:20 Running the bitmap intersection
12:05 Why 0 milliseconds is not really zero
13:00 Measuring microseconds
13:35 Comparing all three approaches
14:20 Where Roaring Bitmaps are used in the real world
15:00 Final thoughts and shoutout

#dotnet #csharp #softwareengineering #datastructures #performance #algorithms #roaringbitmaps #opensource #azuredevops #youtube #datadog

We Are .NET

Roaring Bitmaps are a high-performance data structure used by companies like YouTube and Microsoft to run fast set intersection queries over hundreds of millions of records. By compressing sequential integers into ranges, Roaring Bitmaps can perform intersections in ~99 microseconds compared to ~3 milliseconds for HashSets and ~38 seconds for plain lists. A C# demo using the Roaring.NET NuGet package shows all three approaches side by side, with the Roaring Bitmap being orders of magnitude faster for large sequential datasets.

Roaring Bitmaps in C#: The Data Structure Behind Super Fast Queries