比特魔法

BitMagic C++ 库

BitMagic 是作为用于信息检索的集合代数工具包而创建的，但目前已发展成为更通用的数据科学组件库，用于简洁数据向量上的内存紧凑结构和算法。 BitMagic 基于位切片变换、Rank-Select 压缩和内存压缩模型的逻辑计算的思想实现了压缩的位向量和容器（向量）。

所有 BitMagic 简洁容器均可序列化（使用最先进的二进制插值编码进行压缩），以实现高效存储和网络传输。所有容器都可以以压缩形式快速搜索。

BitMagic 提供了一组方法和工具来构建您的应用程序，以使用 HPC 技术来节省运行中的内存（从而能够在一个计算单元中容纳更多数据），在将数据向量和模型存储在文件或对象中时改进存储和流量模式存储（SQL 或 noSQL），优化从低级（CPU 缓存）到网络和存储交换的系统带宽。

BitMagic 支持两大类场景：

• 有限 RAM 应用程序（WebAssembly、物联网、边缘计算、桌面/工作站应用程序）
• 大数据 HPC（拍字节问题），其中数据量是天文数字，计算和存储必须分布式（需要高效传输）并针对带宽进行优化。

应用程序和用例

BitMagic 被用作以下功能的构建块：

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

请访问我们的用例说明：http://bitmagic.io/use-case.html

优化和 SIMD

BitMagic 库是一个高性能库，实现了针对各种平台和构建目标的优化：

• x86（平台特定的可用位扫描指令）
• x86 SIMD：SSE2、SSE4.2（POPCNT、LZCNT）、AVX2（BMI1/BMI2）、AVX-512（正在进行中）
• 手臂 SIMD：霓虹灯
• WebAssembly（使用 WebAsm 内置函数和平台特定技巧）
• Web汇编SIMD

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

压缩算法

BitMagic 使用一套压缩算法、过滤器和转换来减少内存占用、存储成本和网络数据传输。 http://bitmagic.io/design.html

• 位向量的分层压缩
• 位块的 D-GAP (RLE)
• 二进制内插编码 (BIC)
• 埃利亚斯-伽玛编码
• 向量的按位转置（也称为位平面编码或位切片）
• 异或压缩滤波器
• 基于频率的字典重新映射（类似于霍夫曼代码）

请访问我们的技术说明：http://bitmagic.io/articles.html

主要特点（bm::bvector<>）

• 压缩位向量容器
• 迭代器（bm::bvector<>::enumerator 将位集解码为整数
• 设置代数运算：位向量和整数集上的 AND、OR、XOR、MINUS、NOT
• 用于位向量遍历的快速位向量迭代器（枚举器），基于函子的遍历算法（类似于 std::for_each）
• 整数列表的快速导入（压缩）（C++ 风格的bulk_insert_iterator 或使用C 数组）
• 聚合器：对位向量组进行快速向量化逻辑 AND、OR、AND-MINUS 运算
• 将位向量容器序列化/休眠为压缩的 BLOB 以实现持久性（或 RAM 内压缩）
• 对压缩 BLOB 进行设置代数运算（使用设置代数函数进行动态反序列化）
• 统计算法可有效构建相似性和距离度量，测量位向量、整数集和压缩 BLOB 之间的相似性
• 排名运算：位向量上的人口计数距离。 Rank-Select 操作通常用于简洁的数据结构中，BitMagic 实现了使用 SIMD 和 BMI (PDEP) 加速的紧凑 RS 索引

范围和间隔 (bmintervals.h)

BitMagic 支持将位向量重新解释为两侧为 0 的非重叠范围 1 的集合（例如：011110110）。常规集合函数提供集合交集/并集区间操作，实现区间迭代器并搜索区间边界。范围和区间在生物信息学中具有很大的用途，因为基因组数据通常被注释为坐标范围。 BitMagic 提供了在编码为位向量的间隔上进行高效操作的构建块（查找间隔开始/结束、检查范围是否为 inetrval、迭代间隔

三值逻辑 (bm3vl.h)

BitMagic 以紧凑的双位向量表示形式实现 True/False/Unknown 的三值逻辑（也称为三元逻辑、三价、三元）的逻辑运算，支持遵循 Kleene 定义的反转、AND、OR 运算。 https://github.com/tlk00/BitMagic/tree/master/samples/bv3vlogic

带压缩的序列化

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

第一阶段：简洁记忆

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

第二阶段：压缩

BitMagic 可以序列化所有容器和向量，并基于启发式块和编解码器进行额外压缩。主要编码技术是：二进制插值编码 (BIC) 和 Elias Gamma。

BitMagic 容器被称为“稀疏”向量，但实际上它的压缩方案对于稀疏和密集数据都适用。

BitMagic 在 Gov2 倒排列表基准集和专有数据集数量上进行了测试。 http://bitmagic.io/bm5-cmpr.html

减压

反序列化总是回到第一阶段，因此数据并没有完全解码，而是
RAM 中简洁。我们的目标是减少应用程序内存占用并改善反序列化延迟。解压缩算法支持任意范围的反序列化，甚至收集元素的反序列化。

简洁向量

BitMagic 支持基于位转置变换的简洁（内存紧凑）向量
也称为位平面压缩 (BPC)（又名位切片）加上排名选择压缩。 BitMagic 简洁向量有点误导性地标记为“稀疏”，但它们适用于密集向量。

位转置解决了两个目的：释放未使用的位平面并将规律性和熵隔离为单独的（稀疏）位向量。位平面压缩提供了卓越的内存性能和快速搜索。设计目标之一是使用快速向量化逻辑运算对简洁向量执行无索引搜索。

BitMagic 简洁向量可以内存压缩形式进行无索引搜索。速度很快！

简洁的位转置实现对于整数向量（有符号或无符号）以及字符串向量都适用。它可以与前缀树等其他简洁方案相媲美。简洁向量可以是已排序的也可以是未排序的。这里的想法与 Apache Arrow-Parquet 类似，但它通过位平面压缩和加速 Rank-Select 压缩的广泛使用而走得更远。

• 当数据使用有限或可变比特率的数字时，位转置表示为数字向量提供最佳的内存占用。如果数据仅需要 27 位简洁向量，则将仅使用该数据，而不是最接近的自然 32 位类型。它是自适应的并且完全自动的。
• 如果字符串向量只需要几个位来表示特定位置的字符（DNA 字符串、微笑等化合物），BitMagic 可以选择进行透明重新映射，因此 DNA 字符串向量将仅使用 2-3 位（对于 ATGCN字母表），重新映射分析频率，与霍夫曼类似。
• Rank-Select 方法允许折叠所有 NULL 值并节省 RAM
• 为了进行更深层次的压缩，BitMagic 还实现了 XOR 滤波器，该滤波器可以找到位平面之间可能的相关性以减少熵 http://bitmagic.io/bm-xor.html

主要特点

• 使用按位切片和位切片单独压缩的本机 int 类型的稀疏向量，并支持 NULL 值（未分配）以构建内存中的柱状结构。位转置稀疏向量可用于天文学、分子生物学或其他数据的动态压缩、图形关联的有效存储等。
• 排序和未排序的简洁向量（整数或字符串向量）的搜索算法
• 稀疏向量算法：动态范围裁剪、搜索、群论图像（重新映射）。
• 所有容器均可通过压缩进行序列化（XOR 编码、二进制插值编码、elias gamma 编码）
• 支持简洁的不可变向量。向量可以变成只读，稀疏内存块重新排列以整理堆碎片，节省内存并促进更好的CPU缓存恢复

序列化和版本控制

BitMagic 支持序列化（协议）演变 - 如果序列化格式发生变化，旧保存的数据仍然可以被新代码读取。旧代码将无法读取新的 BLOB。当序列化格式更改时，BitMagic 会更改主版本号。

内存分析/监控

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

64 位与 32 位

是的！ BitMagic 支持 64 位，可以与 32 位地址空间（开销较小）或完整的 64 位地址空间一起使用。 32 位地址空间是默认模式 2^31-1 元素应该非常适合中短程 IR 和数据科学系统。使用#define BM64ADDR 或#include "bm64.h" 可以使用64 位地址模式。当前的 64 位实现允许大型系统使用 2^48-1 个向量元素。

WebAssembly 和 WebAssembly SIMD

BitMagic 编译并使用 WebAssmbly (emscripten)。最新版本包括针对该平台的多项调整。性能数字接近没有 SIMD 的本机代码（有时在之后）。示例编译行如下所示：

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

支持 WebAssembly SIMD，但默认情况下未启用。使用： #define BMWASMSIMDOPT启用它。 Emscripten cmd 示例：

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是必要的。

手臂

BitMagic 完全支持 ARM CPU。所有版本均使用 Raspberry Pi 4 进行压力测试。BitMagic 实现了一些特定于 ARM 的算法调整和改进（例如使用 LZCNT 指令）。 BitMagic 简洁容器对于可用内存量有限的边缘计算嵌入式系统非常有用。

提供 Arm Neon SIMD 支持（通过 SSE2NEON 库）。

C 库接口：

• BitMagic 库提供 C 库包装器，它构建为“真正的 C”库。对于重新分发，它不需要 C++ 运行时，因为它在编译时不使用 STL、C++ 内存分配（运算符 new）或异常。我们的目标是最终通过 JNI 为其他数据科学语言（Python）和企业级开发语言（Java、Scala）提供桥梁。

正在进行中的功能：

• 压缩二元关系矩阵和邻接矩阵以及矩阵运算，用于实体关系加速、图形操作、社交分析、物化 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

执照：

阿帕奇2.0。

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

质量保证：

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

我们不仅仅依赖单元测试，我们的测试经常使用“混沌测试” （又名模糊测试），其中压力测试基于随机生成集和随机操作。我们定期为发布和调试模式构建和运行测试套件，以实现 SIMD 优化的各种组合。

测试构建的所有变体都需要几天的时间才能运行，因此不能保证工作主分支始终是完美的。对于生产，请使用 SourceForge 的稳定 github 发布分支或发行版：https://sourceforge.net/projects/bmagic/files/

如果您想贡献或支持 BitMagic 库：

---

1. GitHub master 接受补丁请求 我们的分支政策是 master 不能被认为在版本之间完全稳定。 （为了生产稳定性，请使用发布版本）

2. 需要映射到 Python 和其他语言的帮助（BitMagic 具有 C 绑定）

如何构建 BitMagic C++ 库：

---

BitMagic C++ 是一个仅包含头文件的软件包，您可能可以直接获取源代码并将其放入您的项目中。所有 C++ 库源代码/头文件都位于 src 目录中。

但是，如果您想使用我们的 makefile，您需要遵循以下简单说明：

Unix：

---

1. 传统（就地构建）

通过在项目根目录中运行 bmenv.sh 应用一些环境变量：

 $ source ./bmenv.sh

（请使用“.”“./bmenv.sh”应用根环境变量）

使用 GNU make (gmake) 来构建安装。

 $make rebuild

或（调试版本）

 $gmake DEBUG=YES rebuild

Unix 和 CygWin 上的默认编译器是 g++。如果您想更改默认值，您可以在 makefile.in 中执行此操作（应该很容易做到）

2. 基于 CMake 的构建项目现在附带了一组 cmake 的 makefile，您可以为任何 cmake 支持的环境构建它或生成项目文件。

视窗：

---

如果您使用 cygwin 安装，请遵循一般 Unix 建议。 MSVC - 解决方案和项目可通过 CMAKE 获得。

苹果系统

---

Xcode - 项目文件可通过 CMAKE 获得。

---

用于 C 和 JNI 映射的 BitMagic 库。

BitMagic 库可用于 C 语言（这是正在进行中的工作）。 C 构建的主要目标是将 BitMagic 桥接到其他编程语言中。 C build 位于子目录“lang-maps”中。

C build为SSE和AVX创建了BitMagic build的版本，并添加了CPU识别，因此上层系统可以支持动态CPU识别和代码调度。

C 构建使用 C++ 编译器，但不使用 RTTI、异常（用长跳转模拟）和 C++ 内存管理，因此它是 C++ 语言中立的，没有运行时依赖项。算法和行为在 C 和 C++ 之间共享。

目前发展状况：

• 位向量功能可通过 C 接口获得

Python支持

Python 支持正在等待中，我们需要帮助。如果您对 Python 充满热情并认为您可以提供帮助，请联系：anatoliy.kuznetsov @ yahoo dot com

现代 C++ (C++17)

BitMagic 库需要 CXX-11。它使用移动语义、noexept、初始化器列表、线程。下一个公共版本将使用 CXX-17（constexpr ifs 等）。

###微调和优化：

所有 BitMagic 微调参数均由预处理器定义（以及用于代码生成的目标架构特定编译器键）控制。

＃定义	描述	宽度
BMSSE2OPT	SSE2代码优化	128位
BMSSE42OPT	SSE4.2代码优化加上POPCNT、BSF等	128位
BMAVX2OPT	AVX2、POPCNT、LZCNT、BMI1、BMI2 优化	256位
BMAVX512OPT	AVX-512，（实验性）	512位
宝马ASMSIMDOPT	WebAssembly SIMD 优化（通过 SSE4.2）	128位
DBMNEOOPT	Arm Neon SIMD 优化（通过 SSE2 转换）	128位

####限制：

SIMD 优化定义是互斥的，不能同时拥有 BMSSE42OPT 和 BMAVX2OPT。只选一个。

BM 库不支持多代码路径和运行时 CPU 识别。您必须专门为您的目标系统构建或使用默认的便携式构建。

####示例：

BitMagic 示例和测试可以使用命令行设置通过 GCC 构建：

 make BMOPTFLAGS=-DBMAVX2OPT rebuild

或者

 make BMOPTFLAGS=-DBMSSE42OPT rebuild

它会自动为目标构建应用正确的编译器 (GCC) 标志集。

 CMAKE

cd build
cmake -DBMOPTFLAGS:STRING=BMSSE42OPT ..
make

或者

 cmake -DBMOPTFLAGS:STRING=BMAVX2OPT ..

---

BM 库支持“restrict”关键字，当限制关键字有帮助时，某些编译器（例如 Intel C++）会生成更好的代码（乱序加载存储）。该选项默认关闭，因为大多数 C++ 编译器不支持它。要打开它，请在您的项目中#define BM_HASRESTRICT。一些编译器使用“__restrict”关键字来达到此目的。要更正它，请定义 BMRESTRICT 宏来更正关键字。

---

如果您想在“非 STL 项目”（如嵌入式系统）中使用 BM 库，请定义 BM_NO_STL。

此规则仅适用于核心 bm::bvector<> 方法。辅助算法、示例等仍将使用STL。

---

在 Twitter 上关注我们：https://twitter.com/bitmagicio

感谢您使用 BitMagic 库！

电子邮件：[email protected]

网站：http://bitmagic.io

GitHub：https://github.com/tlk00/BitMagic