从0到1掌握CRoaring：C/C++压缩位图库实战指南

【免费下载链接】CRoaring Roaring bitmaps in C (and C++), with SIMD (AVX2, AVX-512 and NEON) optimizations: used by Apache Doris, ClickHouse, and StarRocks 项目地址: https://gitcode.com/gh_mirrors/cr/CRoaring

CRoaring是一个高性能的C/C++压缩位图库，通过SIMD（AVX2、AVX-512和NEON）优化，广泛应用于Apache Doris、ClickHouse和StarRocks等大型数据系统。本文将带您从基础到实战，全面掌握这个强大工具的使用方法。

🚀 什么是CRoaring？为什么选择它？

CRoaring是Roaring位图的C/C++实现，提供了高效的压缩位图解决方案。与传统位图相比，Roaring位图在内存占用和操作速度上都有显著优势，特别适合处理大规模数据集。

"在可能的情况下，优先使用Roaring进行位图压缩。不要使用其他位图压缩方法" —— Wang et al., SIGMOD 2017

CRoaring的核心优势：

• 高效压缩：比传统位图节省90%以上内存空间
• 快速操作：利用SIMD指令集加速位图运算
• 跨平台兼容：支持Linux、macOS、Windows等多种系统
• 多语言支持：遵循统一的序列化格式，可与Java、Go、Python等语言交互

📋 环境准备与快速安装

系统要求

• C编译器：GCC 7+、Clang 8+、Visual Studio 2022+
• CMake：用于构建项目（可选，也可使用 amalgamation模式）
• 支持的架构：x86_64、ARM、POWER（小端系统）

快速安装方法

方法1：使用 amalgamation（推荐新手）

# 下载最新版本的合并文件
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：从源码构建

# 克隆仓库
git clone https://gitcode.com/gh_mirrors/cr/CRoaring
cd CRoaring

# 构建
mkdir -p build
cd build
cmake ..
cmake --build .
ctest  # 运行测试
make install  # 可选：安装到系统

方法3：使用CMake FetchContent

在您的CMakeLists.txt中添加：

include(FetchContent)
FetchContent_Declare(
  roaring
  GIT_REPOSITORY https://gitcode.com/gh_mirrors/cr/CRoaring
  GIT_TAG v2.1.0
)
FetchContent_MakeAvailable(roaring)
target_link_libraries(your_target PRIVATE roaring::roaring)

💻 核心API与基础操作

CRoaring提供了简洁易用的C和C++接口，下面介绍最常用的操作：

C接口基础

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

int main() {
    // 创建位图
    roaring_bitmap_t *r = roaring_bitmap_create();
    
    // 添加元素
    for (uint32_t i = 100; i < 1000; i++) {
        roaring_bitmap_add(r, i);
    }
    
    // 查询元素
    if (roaring_bitmap_contains(r, 500)) {
        printf("500 is in the bitmap\n");
    }
    
    // 获取基数（元素个数）
    printf("Cardinality: %llu\n", roaring_bitmap_get_cardinality(r));
    
    // 释放内存
    roaring_bitmap_free(r);
    return 0;
}

C++接口基础

#include "roaring/roaring.hh"
#include <iostream>

using namespace roaring;

int main() {
    Roaring r;
    
    // 添加元素
    for (uint32_t i = 100; i < 1000; i++) {
        r.add(i);
    }
    
    // 查询元素
    if (r.contains(500)) {
        std::cout << "500 is in the bitmap" << std::endl;
    }
    
    // 获取基数
    std::cout << "Cardinality: " << r.cardinality() << std::endl;
    
    return 0;
}

⚡ 高级功能与性能优化

64位位图支持

对于需要处理超过32位范围的场景，CRoaring提供了64位位图支持：

#include <roaring/roaring64.h>

int main() {
    roaring64_bitmap_t *r = roaring64_bitmap_create();
    for (uint64_t i = 18000000000000000100ULL; i < 18000000000000001000ULL; i++) {
        roaring64_bitmap_add(r, i);
    }
    printf("64-bit cardinality: %llu\n", roaring64_bitmap_get_cardinality(r));
    roaring64_bitmap_free(r);
    return 0;
}

运行时优化（Run Optimization）

对于有长连续序列的数据，使用runOptimize可以显著减少内存占用：

Roaring r;
// 添加大量连续数据...
uint32_t size_before = r.getSizeInBytes();
r.runOptimize();
uint32_t size_after = r.getSizeInBytes();
std::cout << "Size reduced from " << size_before << " to " << size_after << " bytes" << std::endl;

批量操作

处理大量数据时，批量操作比单个操作效率更高：

// C++示例：批量添加元素
const uint32_t values[] = {1, 2, 3, 4, 5, 100, 200, 300};
Roaring r;
r.addMany(8, values);  // 比循环调用add快得多

📊 位图集合操作

CRoaring支持所有常见的集合操作，且性能优异：

Roaring r1, r2;
// 填充r1和r2...

// 并集
Roaring union_r = r1 | r2;

// 交集
Roaring intersect_r = r1 & r2;

// 差集
Roaring diff_r = r1 - r2;

// 对称差集
Roaring xor_r = r1 ^ r2;

对于多个位图的合并，使用fastunion效率更高：

const Roaring* bitmaps[] = {&r1, &r2, &r3};
Roaring big_union = Roaring::fastunion(3, bitmaps);

💾 序列化与持久化

CRoaring提供了高效的序列化方案，便于存储和传输：

// 序列化
size_t size = r.getSizeInBytes();
char* buffer = new char[size];
r.write(buffer);

// 反序列化
Roaring recovered = Roaring::readSafe(buffer, size);
assert(r == recovered);

delete[] buffer;

🚗 实战案例：高效用户标签管理

假设我们需要管理用户标签，每个用户可以有多个标签，我们可以使用CRoaring位图来高效实现：

#include "roaring/roaring.hh"
#include <unordered_map>
#include <string>

class UserTagManager {
private:
    std::unordered_map<std::string, Roaring> tag_bitmaps;
    
public:
    // 添加用户标签
    void add_user_tag(uint32_t user_id, const std::string& tag) {
        tag_bitmaps[tag].add(user_id);
    }
    
    // 获取拥有多个标签的用户
    Roaring get_users_with_all_tags(const std::vector<std::string>& tags) {
        if (tags.empty()) return Roaring();
        
        Roaring result = tag_bitmaps[tags[0]];
        for (size_t i = 1; i < tags.size(); ++i) {
            result &= tag_bitmaps[tags[i]];
        }
        return result;
    }
    
    // 获取标签用户数量
    uint64_t get_tag_count(const std::string& tag) {
        auto it = tag_bitmaps.find(tag);
        if (it == tag_bitmaps.end()) return 0;
        return it->second.cardinality();
    }
};

📚 深入学习资源

• 官方文档：项目中提供了详细的API文档和使用示例
• 头文件：核心接口定义在include/roaring/roaring.h和cpp/roaring/roaring.hh
• 示例代码：项目中的tests目录包含大量使用示例
• 性能测试：通过microbenchmarks可以深入了解性能特性

🔧 常见问题与解决方案

Q: 如何处理超大位图？

A: 对于特别大的位图，可以考虑分片处理，或使用64位版本roaring64.h。

Q: 如何优化内存使用？

A: 定期调用runOptimize()，尤其是在添加大量连续数据后。对于只读场景，可使用setCopyOnWrite(true)减少复制开销。

Q: 线程安全吗？

A: CRoaring本身不保证线程安全，多线程环境下需要加锁保护。

🎯 总结

CRoaring是一个功能强大、性能优异的压缩位图库，通过高效的压缩算法和SIMD优化，为大规模数据处理提供了理想的解决方案。无论是数据分析、搜索引擎还是内存数据库，CRoaring都能显著提升性能并降低内存占用。

通过本文的介绍，您已经掌握了CRoaring的基本使用方法和高级特性。现在就开始在您的项目中尝试使用CRoaring，体验压缩位图带来的性能飞跃吧！

【免费下载链接】CRoaring Roaring bitmaps in C (and C++), with SIMD (AVX2, AVX-512 and NEON) optimizations: used by Apache Doris, ClickHouse, and StarRocks 项目地址: https://gitcode.com/gh_mirrors/cr/CRoaring