BitMagic

BitMagic C++库

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

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

BitMagic提供了一系列方法和工具，帮助您设计应用程序使用高性能计算技术，实时节省内存（从而能够在一个计算单元中容纳更多数据），改善在文件或对象存储（SQL或noSQL）中存储数据向量和模型时的存储和流量模式，从低级别（CPU缓存）到网络和存储交换优化系统带宽。

BitMagic适用于两大类场景：

内存受限的应用（WebAssembly、物联网、边缘计算、桌面/工作站应用）
大数据高性能计算（PB级问题），数据量巨大，计算和存储必须分布式（需要高效传输）和带宽优化。

应用和用例

BitMagic被用作以下方面的构建块：

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

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

优化和SIMD

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

x86（平台特定可用位扫描指令）
x86 SIMD：SSE2、SSE4.2（POPCNT、LZCNT）、AVX2（BMI1/BMI2）、AVX-512（进行中）
Arm SIMD：Neon
WebAssembly（使用WebAsm内置函数和平台特定技巧）
WebAssembly SIMD

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

压缩算法

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

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

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

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

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

范围和区间（bmintervals.h）

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

三值逻辑（bm3vl.h）

BitMagic在紧凑的两个位向量表示中实现了真/假/未知的3值逻辑（也称为三元逻辑、三值逻辑）的逻辑运算，支持按照Kleene的定义进行反转、AND、OR操作。 https://github.com/tlk00/BitMagic/tree/master/samples/bv3vlogic

带压缩的序列化

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

第一阶段：简洁内存

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

第二阶段：压缩

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

BitMagic容器被称为"稀疏"向量，但实际上其压缩方案对稀疏和密集数据都有效。

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

解压缩

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

简洁向量

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

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

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

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

比特转置表示法为数值向量提供了最佳的内存占用,适用于有限或可变位数的数据。如果数据只需要27位,简洁向量就只使用27位,而不是最接近的32位自然类型。它是自适应且完全自动的。
如果字符串向量在特定位置只需要几位来表示一个字符(如DNA字符串、化学化合物的SMILES表示法等),BitMagic可以进行透明的重映射,因此DNA字符串向量只需要2-3位(用于ATGCN字母表),重映射会分析频率,类似于霍夫曼编码。
秩选择方法允许合并所有NULL值以节省内存
为了更深层次的压缩,BitMagic还实现了XOR过滤器,可以找出位平面之间可能的相关性以减少熵 http://bitmagic.io/bm-xor.html

主要特性

使用位切片和位切片单独压缩的原生整数类型稀疏向量,支持NULL值(未赋值),用于构建内存列式结构。位转置稀疏向量可用于天文、分子生物学或其他数据的即时压缩,高效存储图的关联等。
排序和未排序简洁向量(整数或字符串向量)的搜索算法
稀疏向量算法:动态范围裁剪、搜索、群论映像(重映射)
所有容器都可序列化并支持压缩(XOR编码、二进制插值编码、Elias gamma编码)
支持简洁不可变向量。向量可以设为只读,稀疏内存块可以重新排列以碎片整理堆、节省内存并促进更好的CPU缓存重用

序列化和版本控制

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

内存分析/监控

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

64位与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

许可证:

Apache 2.0。

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

质量保证:

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

我们不仅仅依赖单元测试,我们的测试经常使用"混沌测试"(又称模糊测试),其中压力测试基于随机生成的集合和随机操作。我们定期为各种SIMD优化组合构建和运行Release和Debug模式的测试套件。

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

如果您想为BitMagic库做出贡献或支持:

GitHub主分支接受补丁请求我们的分支策略是,主分支在发布之间不能被认为是完全稳定的。 (为了生产稳定性,请使用发布版本)
需要帮助将其映射到Python和其他语言(BitMagic有C绑定)

如何构建BitMagic C++库:

BitMagic C++是一个仅头文件的软件包,您可能只需要直接将源代码放入您的项目中。所有C++库源代码/头文件都在src目录中。

但是,如果您想使用我们的makefiles,您需要遵循以下简单说明:

Unix:

传统(原地构建)

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

$ source ./bmenv.sh

(请使用"." "./bmenv.sh"来应用根环境变量)

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

$make rebuild

或(DEBUG版本)

$gmake DEBUG=YES rebuild

Unix和CygWin上的默认编译器是g++。如果您想更改默认值,可以在makefile.in中进行更改 (应该很容易做到)

基于CMake的构建项目现在带有一组用于cmake的makefiles,您可以直接构建它或为任何cmake支持的环境生成项目文件。

Windows:

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

MacOS

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

BitMagic库的C和JNI映射。

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

C构建为SSE和AVX创建BitMagic构建版本,并添加CPU识别, 因此上层系统可以支持动态CPU识别和代码分发。 C构建使用C++编译器，但不使用RTTI、异常(通过长跳转模拟)和C++内存管理，因此它是C++语言中立的，没有运行时依赖。C和C++之间共享算法和行为。

当前开发状态:

位向量功能可通过C接口使用

Python支持

Python支持正在进行中，我们需要在这方面的帮助。如果你对Python充满热情并认为你可以提供帮助，请联系: anatoliy.kuznetsov @ yahoo dot com

现代C++(C++17)

BitMagic库需要C++11。它使用了移动语义、noexcept、初始化列表、线程。下一个公开版本将使用C++17(constexpr if等)。

精细调整和优化:

所有BitMagic的精细调整参数都由预处理器定义(以及目标架构特定的编译器代码生成键)控制。

#define	描述	宽度
BMSSE2OPT	SSE2代码优化	128位
BMSSE42OPT	SSE4.2代码优化加上POPCNT、BSF等	128位
BMAVX2OPT	AVX2、POPCNT、LZCNT、BMI1、BMI2优化	256位
BMAVX512OPT	AVX-512(实验性)	512位
BMWASMSIMDOPT	WebAssembly SIMD优化(通过SSE4.2)	128位
DBMNEONOPT	Arm Neon SIMD优化(通过SSE2转换)	128位

限制:

SIMD优化定义是互斥的，你不能同时使用BMSSE42OPT和BMAVX2OPT。只能选择一个。

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

示例:

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

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++)在使用restrict关键字时可以生成更好的代码(乱序加载存储)。默认情况下此选项是关闭的，因为大多数C++编译器不支持它。要打开它，请在你的项目中#define BM_HASRESTRICT。一些编译器使用"__restrict"关键字。要纠正这一点，请将BMRESTRICT宏定义为正确的关键字。

如果你想在"无STL项目"(如嵌入式系统)中使用BM库，请定义BM_NO_STL。

这条规则只适用于核心bm::bvector<>方法。辅助算法、示例等仍会使用STL。

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

感谢使用BitMagic库!

电子邮件: info@bitmagic.io

网站: http://bitmagic.io

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