faiss benchs 目录实战指南：复现 Polysemous Codes 与十亿级 GPU 相似度搜索基准

benchs/ 是 faiss 仓库中用于复现论文实验数据的基准测试脚本目录：它既包含 SIFT1M 上 Polysemous 量化码的召回-速度曲线，也包含 SIFT1B / Deep1B 十亿级数据集的 CPU 与多 GPU 搜索基准。读完本篇，你可以掌握这些脚本的完整参数体系（数据集名、index_factory 键、搜索参数网格）、中间结果的断点续跑机制（训练/索引缓存目录）、以及 GPU 侧内存控制选项（-tempmem、-altadd、-noptables）的使用方法，并理解每个脚本背后的调用链与数据来源。

一、目录定位：复现两篇论文的实验数据

benchs/README.md 开宗明义：该目录中的脚本用于复现以下两篇论文中报告的数据

• Polysemous codes（ECCV 2016，Douze / Jégou / Perronnin）：

  @inproceedings{DJP16,
    Author = {Douze, Matthijs and J{\'e}gou, Herv{\'e} and Perronnin, Florent},
    Booktitle = "ECCV",
    Organization = {Springer},
    Title = {Polysemous codes},
    Year = {2016}
  }
  

• Billion-scale similarity search with GPUs（arXiv:1702.08734，Johnson / Douze / Jégou）：

  @inproceedings{JDJ17,
     Author = {Jeff Johnson and Matthijs Douze and Herv{\'e} J{\'e}gou},
     journal = {arXiv:1702.08734},
     Title = {Billion-scale similarity search with GPUs},
     Year = {2017},
  }
  

README 特别提示：由于实现演进、机器差异等因素，复现出的数值（尤其是耗时）会与论文略有出入。所有脚本都是自包含的：只依赖 Faiss 本身和存放在子目录中的外部训练/查询数据，不需要其他基础设施。

整个目录的脚本可分为三类：论文复现脚本（polysemous、GPU）、通用工具（benchs/datasets.py）、以及 README 末尾列出的"附加基准"（见本文第五节）。

二、公共工具：datasets.py 中的加载与评测函数

所有 SIFT1M 脚本共用 benchs/datasets.py，值得先了解三个函数：

• fvecs_read(fname) / ivecs_read(fname)：分别读取 fvecs（float32 向量）与 ivecs（int32 向量）格式文件；
• load_sift1M()：固定读取四个文件——sift1M/sift_learn.fvecs（训练集）、sift1M/sift_base.fvecs（库向量）、sift1M/sift_query.fvecs（查询）、sift1M/sift_groundtruth.ivecs（真值），返回 (xb, xq, xt, gt)；
• evaluate(index, xq, gt, k)：执行一次 index.search(xq, k)，计算每查询平均耗时（ms）以及 R@1、R@10、R@100 召回，返回 (t, recalls)。

这意味着：运行任何 SIFT1M 脚本前，工作目录下必须存在 sift1M/ 子目录。README 给出的数据集来源是 corpus-texmex（IRISA 实验室的 ANN_SIFT1M 数据集，README 原文附有下载链接），解压到 sift1M/ 子目录即可。

三、SIFT1M 上的 Polysemous 实验

3.1 脚本做了什么

benchs/bench_polysemous_sift1m.py 复现 "Polysemous" 论文 Figure 3 的数据。其核心逻辑从源码看非常简洁：

1. 构建 faiss.IndexPQ(d, 16, 8)（16 子空间、每子空间 8 位码字，共 8 字节码长），并设置 index.do_polysemous_training = True，即启用 polysemous 训练（脚本在 10 万训练点上训练 PQ）；
2. 重复训练 5 次（NUM_TRAIN_RUNS = 5），输出训练耗时的中位数/均值/标准差/最小/最大值；
3. 将全部库向量加入索引后，先用 faiss.omp_set_num_threads(1) 把 OpenMP 线程数固定为 1，保证搜索计时可复现；
4. 基线：index.search_type = faiss.IndexPQ.ST_PQ 测一次；
5. 扫一遍 Hamming 阈值：for ht in 64, 62, 58, 54, 50, 46, 42, 38, 34, 30，将 search_type 切换为 ST_polysemous 并设置 index.polysemous_ht = ht 后逐个评测。

Polysemous 检索的机制是：对 PQ 码先做廉价的 Hamming 距离初筛，只有通过阈值 ht 的候选才计算精确 ADC（asymmetric distance），因此 ht 越小、初筛越激进、速度越快，但召回随之下降——这正是输出表中速度从 7.5ms 单调降到 1.2ms、R@1 从 0.447 跌到 0.18 的内在原因。

3.2 参考输出

README 给出的输出样例：

PQ training on 100000 points, remains 0 points: training polysemous on centroids
add vectors to index
PQ baseline        7.517 ms per query, R@1 0.4474
Polysemous 64      9.875 ms per query, R@1 0.4474
Polysemous 62      8.358 ms per query, R@1 0.4474
Polysemous 58      5.531 ms per query, R@1 0.4474
Polysemous 54      3.420 ms per query, R@1 0.4478
Polysemous 50      2.182 ms per query, R@1 0.4475
Polysemous 46      1.621 ms per query, R@1 0.4408
Polysemous 42      1.448 ms per query, R@1 0.4174
Polysemous 38      1.331 ms per query, R@1 0.3563
Polysemous 34      1.334 ms per query, R@1 0.2661
Polysemous 30      1.272 ms per query, R@1 0.1794

可以观察到一个细节：ht=64（等于码长，即不做任何初筛过滤）时 polysemous 比 PQ 基线更慢——这是 Hamming 检查本身的额外开销，只有当 ht 降到 58 以下、初筛开始真正省掉 ADC 计算后，时间才开始显著下降。

四、十亿级数据集实验（SIFT1B / Deep1B）

4.1 数据准备

benchs/bench_polysemous_1bn.py 复现 "Polysemous codes" 论文中两个 10 亿规模数据集的实验。脚本对数据目录的约定（源码中的硬编码路径）：

• BIGANN / SIFT1B：从 corpus-texmex 下载 ANN_SIFT1B 的四个文件到 bigann/ 子目录，脚本会以内存映射方式读取 bigann_base.bvecs、bigann_query.bvecs、bigann_learn.bvecs，真值读 bigann/gnd/idx_{M}M.ivecs；
• Deep1B：查询与真值文件按 README 指引下载，库向量与训练向量按 README 指引（借助 GNOIMI 项目的下载脚本）下载到 deep1b/，然后拼接为 base.fvecs 与 learn.fvecs。脚本读取 deep1b/base.fvecs、deep1b/deep1B_queries.fvecs、deep1b/learn.fvecs、deep1b/deep1B_groundtruth.ivecs，并且由于 Deep1B 训练集过大，源码里会截断 xt = xt[:10_000_000] 只用前 1000 万条。

十亿向量的文件不可能全部放进内存，脚本用 np.memmap 做只读内存映射，并在 matrix_slice_iterator / dataset_iterator 中按 10 万条一个 block 流式喂给 index.add()。

4.2 命令行参数体系

脚本的取参方式是位置参数：

python bench_polysemous_1bn.py <数据集名> <index_factory 键> [搜索参数 ...]

• 数据集名：SIFT1000M（即 SIFT1B/BIGANN）、Deep1B；也支持 SIFT1M、SIFT2M 等子集名以便小规模调试。README 特别提示：作为 SIFT1B 子集的 SIFT1M 与第三节的独立 SIFT1M 数据集不是同一份数据；
• 索引类型：任意合法的 index_factory 键，对应源码中 faiss.index_factory(d, index_key) 的调用；
• 剩余参数：逐个被解析为搜索期参数，通过 faiss.ParameterSpace 的 ps.set_index_parameters(index, param) 应用到索引上。

4.3 断点续跑：训练与索引缓存

这些实验动辄数小时，脚本把中间结果落到临时目录 /tmp/bench_polysemous/（源码中 tmpdir = "/tmp/bench_polysemous"），实现两级缓存：

1. 训练缓存：{数据集}_{索引键}_trained.index——训练一次后 faiss.write_index 落盘，下次直接 faiss.read_index 加载；
2. 填充缓存：{数据集}_{索引键}_populated.index——10 亿向量全部 add 完之后落盘。

训练向量的数量由 choose_train_size(index_key) 按索引键自动决定（源码可见规则）：

• 基础量 n_train = 256 * 1000（供 PQ 子码本与 PCA 使用）；
• 若键中含 IVF{n}：n_train = max(n_train, 100 * ncentroids)，保证 kmeans 训练点数约为质心数的 100 倍；
• 若键中含 IMI2x{b}：n_train = max(n_train, 256 * (1 << b))，按 IMI 子簇总量给足训练点。

此外，rate_limited_imap 用单线程池做"生产者-消费者"限流，让 mmap 块的解码与 add 重叠执行，避免内存峰值。

4.4 复现论文 Table 2（IMI+PolyD+ADC）

16 字节版本的 Table 2 结果（README 原文命令）：

python bench_polysemous_1bn.py SIFT1000M IMI2x12,PQ16 nprobe=16,max_codes={10000,30000},ht={44..54}

注意这里借助了 bash 的花括号展开生成参数网格：max_codes 与 ht 的笛卡尔积会展开成 2×11=22 组参数，每组单独跑一次搜索。README 报告的耗时量级：训练约 2 分钟、向索引添加 10 亿向量约 3.1 小时（均多线程）；搜索是单线程的（源码中 faiss.omp_set_num_threads(1)）。

输出样例（节选自 README）：

                                        R@1    R@10   R@100     time    %pass
nprobe=16,max_codes=10000,ht=44         0.1779 0.2994 0.3139    0.194   12.45
nprobe=16,max_codes=10000,ht=48         0.2033 0.3694 0.3917    0.640   20.77
nprobe=16,max_codes=10000,ht=54         0.2170 0.4240 0.4546    0.256   39.66
nprobe=16,max_codes=30000,ht=44         0.1882 0.3327 0.3555    0.226   11.29
nprobe=16,max_codes=30000,ht=54         0.2278 0.4601 0.5031    0.303   39.20

%pass 列是脚本从 C++ 静态统计对象算出的：源码中为 ivfpq_stats.n_hamming_pass * 100.0 / ivf_stats.ndis，即 IVFPQ 中通过 Hamming 初筛的码比较占全部距离计算的比例。README 指出 Table 2 报告的工作点是 %pass 约 20% 的那一行，对应 ht=48（上表 ht=48 行 %pass=20.77 与之吻合）。8 字节版本只需把 factory 键换成 IMI2x12,PQ8。

4.5 复现论文附录 Table 3 与 Deep1B 自动调参

附录实验（仅在 ArXiv 版中有）用 OPQ 预处理，README 原文命令：

python bench_polysemous_1bn.py SIFT1000M OPQ8_64,IMI2x13,PQ8 nprobe={1,2,4,8,16,32,64,128},ht={20,24,26,28,30}

同样依赖 bash 花括号展开（{1,2,4,...} 是枚举列表、{44..54} 是范围序列，二者语法不同）。README 说明原论文数据对应 nprobe=32,ht=28 的运行点。

Deep1B 则展示了 faiss 的运行时自动调参接口：传一个 autotune 关键字即可，脚本内部构建 faiss.OneRecallAtRCriterion(nq, 1) 作为准则函数（优化 1-R@1），然后调用 ps.explore(index, xq, crit) 让 Faiss 自己扫操作点：

python bench_polysemous_1bn.py Deep1B OPQ20_80,IMI2x14,PQ20 autotune
...
Done in 4067.555 s, available OPs:
Parameters                                1-R@1     time
nprobe=1,ht=22,max_codes=256              0.0215    3.115
nprobe=512,ht=68,max_codes=524288         0.4478   36.903
nprobe=1024,ht=80,max_codes=131072        0.4557   46.363
nprobe=1024,ht=78,max_codes=262144        0.4616   61.939

README 说明论文原结果取自 nprobe=1024,ht=66,max_codes=262144。源码中还有 autotuneMT 变体（不调 omp_set_num_threads(1)），允许多线程搜索时调参。

五、GPU 实验

以下基准在原论文中跑在 1 或 4 块 Titan X 上，同时它们也是学习 GPU Faiss 用法的良好起点。适用前提：当前 faiss 构建需带 GPU 支持（faiss.get_num_gpus() 返回大于 0），且数据文件已按前述方式就位。

5.1 SIFT1M GPU 搜索（bench_gpu_sift1m.py）

benchs/bench_gpu_sift1m.py 复现 GPU 论文中"exact k-NN time"曲线，分两段实验：

精确搜索：faiss.GpuIndexFlatL2(res, d, flat_config) 建 GPU Flat 索引（GpuIndexFlatConfig 指定 device = 0），add 全部库向量、warmup 一次后，对 k = 1, 2, 4, ..., 1024（源码中 for lk in range(11): k = 1 << lk）分别评测，输出如下（README 样例）：

k=1 0.715 s, R@1 0.9914
k=128 0.761 s, R@1 0.9935
k=1024 1.424 s, R@1 0.9935

近似搜索：用 faiss.index_factory(d, "IVF4096,PQ64") 在 CPU 侧建模，再 faiss.index_cpu_to_gpu(res, 0, index, co) 克隆到 GPU，随后 train → add → warmup，扫 nprobe = 1..512 输出召回曲线：

nprobe=   1 0.043 s recalls= 0.3909 0.4312 0.4312
nprobe=  32 0.134 s recalls= 0.7957 0.9549 0.9550
nprobe= 512 1.348 s recalls= 0.8228 0.9999 1.0000

源码中有两处值得注意的实现细节：

• co.useFloat16 = True：README 与源码注释都解释了原因——64 字节长的 PQ 需要 16 位浮点查找表才能放进有限的临时显存（temp memory）；

• README 指出对小数据集更高效的做法是把 factory 串改成 "IVF16384,Flat"（即 GpuIVFFlat，倒排列表存全向量而非 PQ 码），脚本中保留了这行注释掉的备选代码。样例输出：

  nprobe=   1 0.025 s recalls= 0.4084 0.4105 0.4105
  nprobe= 256 0.299 s recalls= 0.9866 0.9944 0.9944
  

README 同时解释了输出中两条警告的含义：kmeans 训练点不足 4096×39 会告警（10 万训练点不足以支撑 4096 质心，属预期现象）；add() 的临时内存分配告警只在频繁触发时才值得关注，且基准测的并非 add 速度。

5.2 MNIST8m 上的 k-means 聚类（kmeans_mnist.py）

benchs/kmeans_mnist.py 复现 GPU 论文中的聚类实验。它使用 Léon Bottou 的"无限 MNIST"数据集（README 指引按其网站说明获取），脚本约定 mnist8m-patterns-idx3-ubyte 文件位于 mnist8m 子目录；注意源码中 basedir = "/path/to/mnist/data" 是一个需要指向实际下载位置的变量，完整读取路径为 basedir + "mnist8m/mnist8m-patterns-idx3-ubyte"。

命令行两个位置参数：k（质心数）与 ngpu（GPU 数），例如 python kmeans_mnist.py 1 256。从源码看其结构：

• faiss.Clustering(d, k)，niter = 20，并设 clus.max_points_per_centroid = 10000000 以禁止 kmeans 对训练集降采样；
• 每块 GPU 建一个 GpuIndexFlatL2（useFloat16 = False 保持 float32 精度）；多 GPU 时用 IndexReplicas 包装多个 GPU Flat 索引，kmeans 的最近邻查找在副本间自动分片；
• 输出最终目标函数与总耗时。

README 样例输出：

Clustering 8100000 points in 784D to 256 clusters, redo 1 times, 20 iterations
  Preprocessing in 7.94526 s
  Iteration 19 (131.697 s, search 114.78 s): objective=1.44881e+13 imbalance=1.05963 nsplit=0
final objective: 1.449e+13
total runtime: 140.615 s

5.3 SIFT1B / Deep1B 的 GPU 搜索与 knn-graph（bench_gpu_1bn.py）

benchs/bench_gpu_1bn.py 是本目录中最复杂的脚本：它把数据集构建流程在 Python 里拆解成"预处理 → 粗量化器训练 → PQ/Flat 训练 → 分片 add"多阶段流水线，以最大化 CPU/GPU 并行度与 GPU 间分布。README 提醒：即使多卡，构建 10 亿索引也可能耗时数小时，建议先用 SIFT1M/SIFT2M 等小数据集验证流程。

用法：python bench_gpu_1bn.py <数据集> <index_factory 键> [选项]。脚本 usage() 中列出的完整选项集（与源码逐一对应）：

选项	含义	默认值
-ngpu N	使用的 GPU 数	全部可见 GPU
-tempmem N	每块 GPU 的临时显存字节数	系统默认
-nocache	不读写中间缓存文件	使用缓存
-float16	GPU 侧使用 16 位浮点	关闭
-abs N	add 按不超过 N 个向量分块	32768
-max_add N	每 add N 个向量把分片刷回 CPU（防几何扩容溢出）	-1（关闭）
-altadd	替代 add 路径：add 期间索引不常驻 GPU，对慢速 GPU 上的大数据集略快	关闭
-R R	数据集副本数（数据复制到 ngpu/R 块 GPU 上）	1
-noptables	IVFPQ 不使用预计算查找表	使用
-qbs N	查询按不超过 N 个向量分块	16384
-nnn N	每个查询搜索的邻居数	10
-nprobe a,b,c	尝试这些 nprobe 值	1,2,...,256
-knngraph	改为构建 k-nn 图模式	关闭
-oI xx%d.npy / -oD xx%d.npy	把搜索结果索引/距离存为 numpy 文件	不存

中间产物同样缓存在临时目录（源码 cacheroot = "/tmp/bench_gpu_1bn"），按"数据集+预处理+IVF+量化器"命名 preproc/质心/索引三类缓存文件；-knngraph 模式的缓存文件带 BK_ 前缀以免与普通实验冲突。

SIFT1B 搜索（README 原文命令，复现 GPU 论文数据）：

python bench_gpu_1bn.py SIFT1000M OPQ8_32,IVF262144,PQ8 -nnn 10 -ngpu 1 -tempmem $[1536*1024*1024]
...
0/10000 (0.024 s)      probe=1  : 0.161 s 1-R@1: 0.0752 1-R@10: 0.1924
0/10000 (0.005 s)      probe=64 : 0.353 s 1-R@1: 0.1332 1-R@10: 0.4461
0/10000 (0.006 s)      probe=256: 1.160 s 1-R@1: 0.1342 1-R@10: 0.4511

-tempmem $[1536*1024*1024] 是 bash 的算术展开（$[...] 语法），把临时显存压到 1.5G，否则索引放不下。

Deep1B 搜索（4 卡、带副本）：

python bench_gpu_1bn.py Deep1B OPQ20_80,IVF262144,PQ20 -nnn 10 -R 2 -ngpu 4 -altadd -noptables -tempmem $[1024*1024*1024]
...
0/10000 (0.006 s)      probe=64 : 0.238 s 1-R@1: 0.4841 1-R@10: 0.8649

README 解释了这里显存吃紧的对策：-noptables 关掉预计算表、限制临时显存、-altadd 避免 add 期间显存溢出（源码中 -R 2 会把 CPU 索引"手动"复制成两个分片 GPU 索引组，源码注释称之为 replicas are made "manually"）。

Deep1B knn-graph：

python bench_gpu_1bn.py Deep1B OPQ20_80,IVF262144,PQ20 -nnn 10 -altadd -knngraph -R 2 -noptables -tempmem $[1<<30] -ngpu 4

knngraph 模式下（源码逻辑）：查询集换成库向量本身（xq = xb），先用多卡 GPU Flat 索引对 1 万个节点（nq_gt = 10000）计算 100 邻的精确真值（分块 add + float_maxheap_array_t 归并），再以 rank-10 交集率（faiss.ranklist_intersection_size）作为质量指标随 nprobe 递增：

999997440/1000000000 (9741.095 s, 0.4722)      probe=4  : 9741.128 s rank-10 intersection results: 0.4722
999997440/1000000000 (70616.392 s, 0.6047)      probe=256: 70616.581 s rank-10 intersection results: 0.6047

注意 README 的提醒：knngraph 不会复用前面搜索实验的倒排文件，因为两者的训练集不同（knngraph 用全库做训练，源码中也因此给缓存文件加 BK_ 前缀）。

六、附加基准脚本一览

README 还列出了一批"附加基准"，它们更多是 Faiss 各组件的用法示例，并声明"某些测试/基准可能已过时"。完整清单（继承自 benchs/README.md）：

• bench_6bit_codec.cpp —— 在合成数据集上测试 SQ6 向量编码
• bench_cppcontrib_sa_decode.cpp —— 对 PQ / IVFPQ / Residual+PQ 的专用解码 kernel 做基准
• bench_for_interrupt.py —— 评估可由 Python 代码触发的中断回调处理器的开销
• bench_hamming_computer.cpp —— Hamming 距离计算的各专门实现
• bench_heap_replace.cpp —— Heap 数据结构不同实现调用的基准
• bench_hnsw.py —— SIFT1M 上 HNSW 与其他索引的组合基准
• bench_hnsw_prune_headroom.py —— HNSW prune_headroom 的召回与构建时间影响
• bench_index_flat.py —— 合成数据集上的 IndexFlatL2
• bench_index_pq.py —— SIFT1M 上的 PQ
• bench_ivf_fastscan_single_query.py —— BIGANN 上不同 nprobe 的单查询 IVF{nlist},PQ{M}x4fs 基准
• bench_ivf_fastscan.py —— SIFT1M 上 IVF{nlist},PQ{M}x4fs 与其他索引对比
• bench_ivf_selector.cpp —— faiss::IDSelectorAll 接口可能的开销
• bench_pairwise_distances.py —— 两个合成数据集间的成对距离计算
• bench_partition.py —— 分区（partitioning）函数基准
• bench_pq_tables.py —— ProductQuantizer.compute_inner_prod_tables() 与 compute_distance_tables() 调用基准
• bench_quantizer.py —— SIFT1M / Deep1B / BigANN 上多种量化器对比
• bench_scalar_quantizer.py —— Sift1M 上的 IVF+SQ

除上述清单外，当前目录中还存在若干 README 未收录的较新脚本（从目录结构看，如 benchs/bench_rabitq.py、benchs/bench_eden.py、benchs/bench_hybrid_cpu_gpu.py，以及 benchs/bench_all_ivf/、benchs/distributed_ondisk/ 等带独立说明的子目录），可作为新量化器与分布式/磁盘场景的额外参考；C++ 基准的构建入口见 benchs/CMakeLists.txt。

七、运行要点小结

1. 路径约定：脚本按相对路径读取数据子目录（sift1M/、bigann/、deep1b/），运行时工作目录须为 benchs/ 或数据子目录的父目录；
2. 缓存目录：CPU 实验用 /tmp/bench_polysemous/，GPU 实验用 /tmp/bench_gpu_1bn/，两者都会把训练好的索引/填充好的索引/质心/预处理器落盘，删除对应缓存文件即可强制重训，这也是复跑单一参数组而不必重建 10 亿索引的关键；
3. 计时口径：搜索前显式 faiss.omp_set_num_threads(1)（CPU 脚本）保证单线程可复现；GPU 脚本先做 warmup 搜索再进入计时循环；
4. 数值差异：README 明确提示复现数值（尤其耗时）与论文会有出入，比较时应以同一硬件上的相对趋势为准。