BitMagic: 高性能位向量和压缩算法库

BitMagic简介

BitMagic是一个高性能的C++库,专门用于内存压缩结构和算法。它最初是作为一个代数集工具包为信息检索而创建的,但现在已经发展成为一个更通用的数据科学组件库,用于内存压缩结构和压缩数据向量上的算法。

BitMagic实现了基于位切片变换、Rank-Select压缩和内存压缩模型逻辑计算思想的压缩位向量和容器(向量)。所有BitMagic压缩容器都可序列化(使用先进的二进制插值编码进行压缩),以实现高效的存储和网络传输。所有容器在压缩形式下都可以快速搜索。

BitMagic提供了一系列方法和工具,可以帮助应用程序架构师使用高性能计算技术来即时节省内存(从而能够在一个计算单元中容纳更多数据),改善存储和流量模式,优化从低级(CPU缓存)到网络和存储交换的系统带宽。

主要特性

BitMagic提供了以下主要特性:

1. 压缩位向量容器(bm::bvector<>)
2. 迭代器(bm::bvector<>::enumerator)用于将位集解码为整数
3. 对位向量和整数集的集合代数运算:AND、OR、XOR、MINUS、NOT
4. 快速位向量迭代器用于位向量遍历,基于函子的遍历算法(类似std::for_each)
5. 快速导入(压缩)整数列表(C++风格的bulk_insert_iterator或使用C数组)
6. 聚合器:对位向量组快速向量化逻辑AND、OR、AND-MINUS操作
7. 将位向量容器序列化/休眠到压缩BLOB中以实现持久性(或RAM内压缩)
8. 压缩BLOB上的集合代数操作(即时反序列化与集合代数函数)
9. 统计算法,用于高效构建相似性和距离度量,测量位向量、整数集和压缩BLOB之间的相似性
10. 与秩相关的操作:位向量上的总体计数距离。Rank-Select操作经常用于简洁的数据结构,BitMagic实现了一个紧凑的RS索引,用SIMD和BMI(PDEP)加速

应用场景

BitMagic库已被用作以下应用的构建块:

• 用于IR、数据库倒排索引构建或无索引列式数据库的集合代数
• 逻辑方案(FPGA)的仿真
• 压缩集上多维二进制距离的数据科学,二进制聚类、自组织映射的构建块
• 构建内存压缩的生物信息学模型
  • 序列比对
  • 变异和SNP集合
  • 序列读取的压缩
  • k-mer分类系统
• 在内存受限的边缘配置中可视化数据集(边缘计算、物联网、WebAssembly)
• 图形和树分析,构建关联压缩矩阵
• Web和应用程序日志分析,可靠性自动化系统
• 低延迟任务调度(编排)系统

优化和SIMD

BitMagic库是一个高性能库,为各种平台和构建目标实现了优化:

• x86(平台特定可用位扫描指令)
• x86 SIMD: SSE2, SSE4.2(POPCNT, LZCNT), AVX2(BMI1/BMI2), AVX-512(进行中)
• Arm SIMD: Neon
• WebAssembly(使用WebAsm内置和平台特定技巧)
• WebAssembly SIMD

BitMagic使用数据并行矢量化设计,目标不仅仅是提供最佳单线程性能,还要促进多核系统上的高度并行计算。

压缩算法

BitMagic使用一套压缩算法、过滤器和转换来减少内存占用、存储成本和网络数据传输。主要包括:

• 位向量的分层压缩
• 位块的D-GAP(RLE)
• 二进制插值编码(BIC)
• Elias-Gamma编码
• 向量的按位转置(也称为位平面编码或位切片)
• XOR压缩过滤器
• 基于频率的字典重映射(类似霍夫曼编码)

这些压缩算法能有效减少数据占用空间,同时保持快速的访问和操作性能。

序列化与压缩

BitMagic使用两阶段序列化-反序列化的概念。重点是快速反序列化。BitMagic实现了快速向量范围反序列化和压缩BLOB收集反序列化的API。BitMagic的终极功能是能够处理压缩数据。

第一阶段:简洁内存

这是主要的内存操作状态,向量以内存紧凑形式保存。简洁并不是压缩。可以访问容器中的随机元素,解码块,迭代向量,进行更新,运行搜索算法。第一阶段提供透明使用,它的向量看起来很像STL。简洁是内存紧凑但不是完全压缩的。

第二阶段:压缩

BitMagic可以使用基于启发式和编解码器块的附加压缩来序列化所有容器和向量。主要的编码技术是:二进制插值编码(BIC)和Elias Gamma。

BitMagic容器被称为"稀疏"向量,但实际上它的压缩方案对稀疏和密集数据都效果很好。

解压缩

反序列化总是回到第一阶段,所以数据不会被完全解码,而是在RAM中简洁。这里的目标是既减少应用程序内存占用,又提高反序列化延迟。解压缩算法支持任意范围的反序列化,甚至支持元素的收集反序列化。

简洁向量

BitMagic支持基于位转置变换(也称为位平面压缩(BPC)或位切片)和Rank-Select压缩的简洁(内存紧凑)向量。BitMagic简洁向量有点误导性地被标记为"稀疏",但它们对密集向量也同样适用。

位转置解决了两个目的:释放未使用的位平面,并将规律性和熵隔离到单独的(稀疏)位向量中。对位平面的压缩既提供了卓越的内存性能,又提供了快速搜索。设计目标之一是使用快速矢量化逻辑操作在内存压缩形式下执行无索引搜索简洁向量。

BitMagic简洁向量在内存压缩形式下是无索引可搜索的。它速度很快!

简洁的位转置实现对整数向量(有符号或无符号)和字符串向量都有效。它可以与其他简洁方案如前缀树相媲美。简洁向量可以是排序的,也可以是未排序的。这里的想法类似于Apache Arrow-Parquet,但它通过位平面压缩和广泛使用加速的Rank-Select压缩更进一步。

• 当数据使用有限或可变位率的数字时,位转置表示为数字向量提供了最佳内存占用。如果数据只需要27位,简洁向量将只使用27位,而不是最接近的自然32位类型。它是自适应的,完全自动的。
• 如果字符串向量在特定位置只需要几个位来表示一个字符(DNA字符串、化学化合物作为smiles等),BitMagic有一个选项可以进行透明重映射,因此DNA字符串向量将只使用2-3位(对于ATGCN字母表),重映射分析频率类似于霍夫曼。
• Rank-Select方法允许折叠所有NULL值并节省RAM
• 为了更深入的压缩,BitMagic还实现了XOR过滤器,它可以找到位平面之间可能的相关性以减少熵

内存分析/监控

BitMagic为所有向量实现了内存分析调用。任何向量都可以对内存占用进行采样,因此顶层系统可以根据运行时内存分析来调整内存管理。典型用例是对象的内存缓存,先压缩到RAM,然后根据资源消耗和成本(需求和供应的动态平衡)被逐出到磁盘。

64位 vs 32位

是的!BitMagic支持64位,可以与32位地址空间(开销更小)或完整的64位地址空间一起使用。32位地址空间是默认模式,2^31-1个元素应该适合短到中等范围的IR和数据科学系统。64位地址模式可通过#define BM64ADDR或#include "bm64.h"使用。当前64位实现允许大型系统使用2^48-1个向量元素。

WebAssembly和WebAssembly SIMD

BitMagic可以编译并与WebAssembly(emscripten)一起工作。最新版本包括多个针对该平台的调整。没有SIMD的性能数字接近原生代码(有时更快)。示例编译行如下:

emcc -std=c++17 -s ALLOW_MEMORY_GROWTH=1 -O2 -s WASM=1 ...

支持WebAssembly SIMD,但默认情况下不开启。使用:#define BMWASMSIMDOPT来启用它。Emscripten命令示例:

emcc -std=c++17 -s ALLOW_MEMORY_GROWTH=1 -O2 -msse4.2 -msimd128 -D BMWASMSIMDOPT -s WASM=1 -s DISABLE_EXCEPTION_CATCHING=0 -fno-rtti

当前实现使用SSE4.2转译(通过内联),因此-msse4.2是必要的。

ARM支持

BitMagic完全支持ARM CPU。所有发布版本都经过Raspberry Pi 4的压力测试。BitMagic实现了一些针对ARM的算法调整和改进(如使用LZCNT指令)。BitMagic简洁容器在可用内存有限的嵌入式系统上进行边缘计算非常有用。

ARM Neon SIMD支持可通过SSE2NEON库获得。

C语言接口

BitMagic库提供C语言包装器,可以构建为"真正的C"库。对于重新分发,它不需要C++运行时,因为它编译时不使用STL、C++内存分配(operator new)或异常。这里的目标是最终为其他数据科学语言(Python)和企业规模开发语言(Java、Scala)通过JNI提供桥梁。

正在进行的功能

• 压缩二进制关系矩阵和邻接矩阵,以及矩阵上的操作,用于实体-关系加速、图形操作、社交分析、物化RDBMS连接等。

如何开始使用BitMagic?

BitMagic C++是一个仅头文件的库(易于在项目中构建和使用),它带有一组示例。不建议使用测试作为学习库使用的代码示例。测试并不说明最佳使用模式和模型,而且经常是故意低效的。

• API文档和示例:http://www.bitmagic.io/apis.html
• 集合代数教程:http://bitmagic.io/set-algebra.html
• 用例和应用说明:http://bitmagic.io/use-case.html
• 性能优化技术说明:http://bitmagic.io/articles.html
• Doxygen:http://bitmagic.io/doxygen/html/modules.html

许可证

BitMagic使用Apache 2.0许可证。

重要提示!我们要求您在任何衍生作品或已发布材料中明确提及BitMagic项目。在您的产品/项目页面上适当引用是使用BitMagic库的要求。

质量保证

BitMagic库非常重视代码质量和测试覆盖率。作为一个构建块库,BitMagic需要稳定和一致才能有用。

他们不仅仅依赖单元测试,测试经常使用"混沌测试"(又称模糊测试),其中压力测试基于随机生成的集合和随机操作。他们定期为各种