mphf_benchmark 是由 Piotr Beling 编写的用于基准测试最小完美哈希函数的程序。

它可以测试以下crates中包含的算法

• ph,
• boomphf,
• cmph-sys （仅当编译时带有 cmph-sys 功能，并且仅支持 CHD 算法）。

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

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

安装

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

请遵循 https://rust-lang.net.cn/tools/install 中的说明。

安装完成后，只需执行以下操作即可使用原生优化安装 mphf_benchmark

RUSTFLAGS="-C target-cpu=native" cargoinstall mphf_benchmark

重现论文中的实验

基于指纹的最小完美哈希重新审视

(Piotr Beling, 《基于指纹的最小完美哈希重新审视》，ACM实验算法杂志，2023年，DOI: https://doi.org/10.1145/3596453)

对于具有广泛参数范围和随机均匀生成的1亿个64位整数键的FMPHGO，结果可以通过以下方式计算：

mphf_benchmark -d -s xs64 -n 100000000 fmphgo-all

对于FMPH、FMPHGO和boomphf，对于随机均匀生成的39,459,925个64位整数键，结果可以通过以下方式计算：

mphf_benchmark -d -s xs64 -n 39459925 -b 30 -l 30 fmph
mphf_benchmark -d -s xs64 -n 39459925 -b 30 -l 30 fmph -c 0
mphf_benchmark -d -s xs64 -n 39459925 -b 30 -l 30 fmphgo
mphf_benchmark -d -s xs64 -n 39459925 -b 30 -l 30 fmphgo -c 0
mphf_benchmark -d -s xs64 -n 39459925 -b 30 -l 30 boomphf

上述调用中后续的部分/标志具有以下含义：

• -d将准确的结果写入文件（或者，如果您认为屏幕上打印的信息足够，您也可以不使用此标志），
• -s xs64指向伪随机数生成器XorShift64作为键源，
• -n指定键的数量，
• -b 30 -l 30表示构建时间和平均（在键上）查找（评估）时间都是在30次运行中平均的，
• -c 0（在方法名之后给出）将禁用FMPH或FMPHGO中的哈希缓存。

我们使用类似的调用，但对于5亿个键，使用-n 500000000和-b 5。

请运行

mphf_benchmark --help

以查看所有方法可用的选项，或者

mphf_benchmark help <method name>

（例如，mphf_benchmark help fmph）以查看方法名称之后给出的特定方法选项。

要使用UbiCrawler在2005年收集的.uk URL集合进行测试，首先从uk-2005-nat.urls.gz文件https://law.di.unimi.it/webdata/uk-2005/下载并解压它

gzip -d uk-2005-nat.urls.gz

然后运行（我们使用cat将解压的uk-nat-2005.urls文件打印到标准输出，然后将其重定向到mphf_benchmark）

cat uk-nat-2005.urls | mphf_benchmark -d -s stdin -n 39459925 -b 30 -l 30 fmph
cat uk-nat-2005.urls | mphf_benchmark -d -s stdin -n 39459925 -b 30 -l 30 fmph -c 0
cat uk-nat-2005.urls | mphf_benchmark -d -s stdin -n 39459925 -b 30 -l 30 fmphgo
cat uk-nat-2005.urls | mphf_benchmark -d -s stdin -n 39459925 -b 30 -l 30 fmphgo -c 0
cat uk-nat-2005.urls | mphf_benchmark -d -s stdin -n 39459925 -b 30 -l 30 boomphf

为了测量构建过程的内存消耗，我们使用memusage分析器，并且单独运行每组参数的方法。例如，我们运行

memusage mphf_benchmark -s xs64 -n 39459925 -b 1 -l 0 -t single fmphgo -c 0 -s 1 -l 100

来测量FMPHGO s=1（-s 1）b=8（根据s选择）$\gamma$=1（-l 100）不缓存哈希（-c 0）的单线程构建的内存消耗。

为了同时使用cat和memusage（这并不简单），我们创建一个名为mphf_uk2005.sh的bash脚本，其内容如下

cat uk-2005-nat.urls | mphf_benchmark "$@"

然后我们可以像这样运行它，例如

memusage mphf_uk2005.sh -s stdin -n 39459925 -b 1 -l 0 -t single fmphgo -c 0 -s 1 -l 100

为了减去构建过程无关的键和数据占用的内存（实际上可以忽略不计），我们还测量了基准程序执行的内存消耗，这些程序在键加载或生成后立即终止

memusage mphf_benchmark -s xs64 -n 39459925 none
memusage mphf_benchmark -s xs64 -n 500000000 none
memusage mphf_uk2005.sh -s stdin -n 39459925 none

为了测试RecSplit、PTHash和CHD，我们使用另一个同名程序（mphf_benchmark），但它是由Giulio Ermanno Pibiri和Roberto Trani用C++编写的，可在https://github.com/roberto-trani/mphf_benchmark（此网站还包含编译说明；默认情况下使用本地优化编译）。作者已经接受我们对他们程序的修改，这确保了两个基准程序可以为测试MPHFs生成完全相同的键。

例如，对于使用XorShift64随机均匀生成39,459,925个64位整数键的RecSplit、PTHash和CHD的结果，以及平均30次运行的结果，可以通过以下方式计算：

mphf_benchmark recsplit -n 39459925 --gen xs64 --num_construction_runs 30 --num_lookup_runs 30
mphf_benchmark pthash -n 39459925 --gen xs64 --num_construction_runs 30 --num_lookup_runs 30
mphf_benchmark chd -n 39459925 --gen xs64 --num_construction_runs 30 --num_lookup_runs 30

类似的调用，但使用来自uk-2005集合的URL作为键看起来是这样的

cat uk-2005-nat.urls | mphf_benchmark recsplit -n 39459925 --gen stdin --num_construction_runs 30 --num_lookup_runs 30
cat uk-2005-nat.urls | mphf_benchmark pthash -n 39459925 --gen stdin --num_construction_runs 30 --num_lookup_runs 30
cat uk-2005-nat.urls | mphf_benchmark chd -n 39459925 --gen stdin --num_construction_runs 30 --num_lookup_runs 30

再次，使用memusage测量内存消耗需要逐个运行一个变体，这可以通过使用--variant开关来实现，其参数是要测试的后续方法变体的数量。例如，测量RecSplit的第一个变体可能看起来像这样（注意，对于uk-2005集合，我们再次使用mphf_uk2005.sh脚本）

memusage mphf_benchmark recsplit --variant 1 -n 39459925 --gen xs64 --num_construction_runs 1 --num_lookup_runs 0
memusage mphf_benchmark recsplit --variant 1 -n 500000000 --gen xs64 --num_construction_runs 1 --num_lookup_runs 0
memusage mphf_uk2005.sh recsplit --variant 1 -n 39459925 --gen stdin --num_construction_runs 1 --num_lookup_runs 0

可以给出一个不存在的变体号（例如，9）来测量基准程序执行时的内存消耗，这些程序在键加载或生成后立即终止

memusage mphf_benchmark recsplit --variant 9 -n 39459925 --gen xs64
memusage mphf_benchmark recsplit --variant 9 -n 500000000 --gen xs64
memusage mphf_uk2005.sh recsplit --variant 9 -n 39459925 --gen stdin