为什么选择 Vers？

• Vers 是公开可用的最快的位向量实现之一，用于 rank 和 select 操作。
• Vers 的内存开销比其竞争对手低得多。
• 没有 crate 功能，所有数据结构都使用纯 Rust 实现，并且没有依赖于标准库之外的依赖项。
• 每个功能都有详细的文档。
• Vers 致力于为其数据结构提供比竞争对手更多的功能（例如，Elias-Fano 序列和 Wavelet 矩阵支持前驱和后继查询，Wavelet 矩阵支持统计查询，所有数据结构都实现了各种迭代器等）。

Crate 功能

• simd：启用 SIMD 指令进行 rank 和 select 操作。此功能需要 AVX-512 支持，并使用不安全代码。它还启用了一个特殊的 rank/select 位向量迭代器，该迭代器使用矢量操作。该功能仅在 nightly Rust 上工作。在 stable Rust 上启用它是无操作的，因为那里没有可用的所需 CPU 功能。
• serde：启用使用 serde crate 进行数据结构的序列化和反序列化。

基准测试

我对相同数据结构的公开实现进行了基准测试。基准测试代码可在 vers-benchmarks 仓库中找到。该基准测试使用了 rsdict 的 simd 功能，这需要 nightly Rust。

我在 Ryzen 9 7950X 和 32GB 内存上进行基准测试。以下是一些结果。所有基准测试均启用了 target-cpu=native 标志，并为 Vers 启用了 simd 功能。更多结果可在基准测试仓库中找到。

由于我打算在执行基准测试前改进基准测试代码，因此缺少 Wavelet Matrix 的基准测试。由于 Wavelet Matrix 的工程空间非常有限，因此预期不会出现任何令人惊讶的结果。性能完全取决于位向量实现，因此结果将与位向量基准测试相似。唯一例外是使用四重向量的 qwt 包，由于缓存未命中的减少，它比任何其他包都快得多。

位向量

Rank & Select

位向量实现是公开可用的最快速的 rank 和 select 操作实现之一。请注意，succinct 包在 Vers 的 rank 操作上显著优于 Vers，但未提供高效的 select 操作。

x 轴是位向量中的位数。对于超过 L2 缓存大小（16 MB）的输入大小，可以观察到所有运行时间的增加。

堆大小

位向量实现的内存开销显著低于其他实现。x 轴是位向量中的位数，y 轴是与位向量大小的百分比额外的开销。仅显示最快的竞争者，以使图表更易于阅读（我本想添加 bio 包的数据结构，因为它是唯一的真正紧凑的，但它不提供测量堆大小的操作。同样，对于声称比 Vers 具有更低内存开销的 bitm 包也是如此，但它不提供方便的测量方法。Vers 通过显著减少内存开销实现了其高速度，这在堆大小基准测试中可以明显看出。图例包含最大输入大小的测量值，因为我假设对于大输入，开销接近一个常数值。

Elias-Fano

该基准测试比较了序列中随机元素的访问时间。x 轴是序列中的元素数量。请注意，elias-fano 包在随机顺序访问中效率低下。顺序访问基准测试可以在基准测试仓库中找到。

以下两个基准测试显示了平均元素分布和最坏情况元素分布的前驱查询时间。请注意，Vers 的最坏情况查询时间是对数级的，而 sucds 的最坏情况查询时间是线性的。

范围最小查询

范围最小查询实现与range_minimum_query和librualg库进行了比较。Vers在两种实现中均显著优于这两个库。当输入大小超过L3缓存大小（64 MB）时，可以观察到运行时间的增加。对于BinaryRMQ实现，这种增加发生得更早，因为它具有更高的内存开销。由于同样的原因，最后两个针对BinaryRMQ实现的测量数据缺失（数据结构超过了可用的32 GB主内存）。

（是的，两个实现的命名都不太理想，但它们将保留到进行主要版本更新为止。）

内建函数

此库使用编译器内建函数进行位操作。内建函数由所有现代x86_64 CPU支持，但其他架构不支持。如果内建函数不可用，则存在回退实现，但它们速度要慢得多。不建议在没有启用BMI2和popcnt目标特性时在x86 CPU上使用此库。

涉及的内建函数包括popcnt（自SSE4.2 resp. SSE4a在AMD上支持，2007-2008年）、pdep（自Intel Haswell resp. AMD Excavator以来支持BMI2，硬件上自AMD Zen 3以来支持，2011-2013年）、以及tzcnt（自Intel Haswell resp. AMD Jaguar以来支持BMI1，大约2013年）。

安全性

此库不使用任何不安全代码，唯一的例外是用于pdep的编译器内建函数。内建函数无法因提供的输入而失败（前提是它们被目标机器支持），因此即使它们被错误实现，也不会发生内存损坏（只有结果不正确）。

不安全代码隐藏在公共API之后。

依赖项

默认情况下，该库不依赖于Rust标准库之外的库。它有大量依赖项用于基准测试，但这些对于正常使用不是必需的。可以选择启用serde功能，以允许对数据结构进行序列化和反序列化，这需要serde库及其derive功能。

许可证

根据您的选择，许可如下

• Apache许可证第2版（LICENSE-APACHE或https://apache.ac.cn/licenses/LICENSE-2.0）
• MIT许可证（LICENSE-MIT或http://opensource.org/licenses/MIT）

。

此项目包含由Gonzalo Brito Gadeschi开发的代码，最初以MIT许可证许可。它以上述双重许可证重新分发。

贡献

除非您明确声明，否则您提交给工作以供包含的任何贡献，根据Apache-2.0许可证的定义，将按照上述双重许可证许可，而不附加任何其他条款或条件。