cseq_benchmark 是由 Piotr Beling 编写的用于基准测试紧凑序列和位图的程序。

它可以测试以下crate中包含的列表算法

• cseq: 伊利亚斯-范诺（实验性）；
• bitm: 在位向量上执行排名和选择查询；
• sucds: 在位向量上执行排名和选择查询；
• succinct: 在位向量上执行排名和选择查询；
• sux: 在位向量上执行选择查询；
• vers（只有编译时启用了 vers-vecs 特性）：在位向量上执行排名和选择查询。

请使用 --help 开关运行程序以查看可用选项。

以下您可以找到关于 安装 cseq_benchmark 和使用它进行的 重现实验 的说明，这些实验可以在已发布的或正在审查的论文中找到。请注意，这些说明已在GNU/Linux下测试过，可能需要对其他系统进行一些修改。

安装

cseq_benchmark 可以从源代码编译和安装。为此，需要一个Rust编译器。获取编译器以及其他必需工具（如 cargo）的最简单方法是使用 rustup。

请按照 https://rust-lang.net.cn/tools/install 中的说明进行操作。

一旦安装了Rust，只需执行以下命令即可使用本地优化安装 cseq_benchmark

RUSTFLAGS="-C target-cpu=native" cargoinstall --特性=vers-vecs cseq_benchmark

使用 --features=vers-vecs 标志可以编译非移植的 vers 库。如果编译出现问题时，应省略此标志。

重现论文中的实验

专注于简洁数据结构的 Rust 库和程序

(Piotr Beling 专注于简洁数据结构的 Rust 库和程序 提交给 SoftwareX)

通过运行以下命令可以获得支持在位向量上执行秩和选择查询的结构的结果（我们使用 rustc 1.75.0 编译）：

cseq_benchmark -f -t 60 -c 20 -q 10000000 -u 1000000000 -n 500000000 bv
cseq_benchmark -f -t 60 -c 20 -q 10000000 -u 1000000000 -n 100000000 bv

注意

• 使用 -t 60 -c 20 开关强制进行长时间测试（预热 60 秒 + 每个测试 60 秒 + 测试之间的冷却/睡眠 20 秒）。可以省略这些开关以更快地获得结果，但重复次数会更少。
• -f 开关会将结果写入文件。也可以跳过，因为结果无论如何都会打印到屏幕上。

可以使用位于 https://github.com/beling/benchmark-succinct 的程序（该页面还包含编译说明）来获得包含在 SDSL2 中的方法的结果（该库是用 C++ 编写的；我们使用 clang 14.0.6 编译），通过运行以下命令：

rank_sel 1000000000 500000000 60 10000000
rank_sel 1000000000 100000000 60 10000000

基准测试结果

关于支持位向量秩和选择查询的结构基准测试的说明

• 我们不区分 rank₀ 和 rank₁，因为每个都可以从另一个 trivially 计算得出。
• 在具有 adversarial 分布和 n 个 1 的位向量中，99% 的 1 占据最后 n 个索引。
• 测试的库版本：bitm 0.4.1，succinct 0.5.2，sucds 0.8.1，sux 0.2.0，vers 1.1.0。
• 标记为 * 的支持选择的结构使用或集成了相应的秩结构；为它们提供的空间开销是额外的。
• 我们使用以下内容进行基准测试：长时间测量（t=60）和冷却（c=20）时间，10⁷ 个随机查询参数，AMD Ryzen 5600G @3.9GHz CPU，以及启用原生优化编译。

位向量中 1 的均匀分布的秩

位向量中 1 的均匀分布的选择 ₁

位向量中 1 的均匀分布的选择 ₀

具有 99% 的 1 在向量末尾附近的对抗性分布的秩

具有 99% 的 1 在向量末尾附近的对抗性分布的选择 ₁

具有 99% 的 1 在向量末尾附近的对抗性分布的选择 ₀