下面整理了Faiss一些实现细节，涵盖常见问题、权衡取舍以及部分设计选择和运行结果的说明。

使用矩阵乘法高效计算大量L2距离

在IndexFlatL2中，常见的操作是将 $nq$ 个查询向量与 $nb$ 个数据库向量进行全面比较（向量维度为 $d$ ），进而选取距离最小的前k个结果。

Faiss为此提供了两种实现方式：

直接实现：遍历所有的 $nq$ 、 $nb$ 以及向量维度 $d$ ，依次计算每对L2距离。
利用公式 $\|x - y\|^2 = \|x\|^2 + \|y\|^2 - 2 \langle x, y \rangle$ ，将累加最耗时的部分交由BLAS（高效的矩阵运算库）处理。算法复杂度同样为 $O(nq \times nb \times d)$ ，但由于BLAS做了高度优化，速度更快。

当 $nq < 20$ 时，Faiss默认采用方式1；当 $nq \geq 20$ 时，采用方式2。该阈值可通过全局变量faiss::distance_compute_blas_threshold调整，Python接口为faiss.cvar.distance_compute_blas_threshold。

注意

第二种方式在向量幅值差异很大时，数值稳定性可能不如第一种。详细讨论请见 issue #297。

k-means（K均值）实现说明

k-means聚类通过Clustering对象实现。

初始化后，k-means会循环以下两步：

将训练点分配给最近的中心点（质心）；
重新计算每个质心为对应分配点的平均值。

上述两步中，第1步计算量最大，需要大量“最近邻查找”。在Faiss的实现里，最近邻查找可由任何索引结构实现，因此可以根据场景更换不同索引。例如，可替换为GPU索引（示例）或HNSW索引（示例）。

提示

更换Index可以充分利用不同硬件能力，提升性能。

IVFPQ中的预计算查找表

在“乘积量化”（Product Quantization, PQ）检索中，核心操作是查找距离表（详见原论文 "Product quantization for nearest neighbor search"）。

对于IVFPQ（倒排文件PQ），还可以进一步预计算加速这些查找表的生成，方法详见 "Billion-scale similarity search with GPUs" 第5.2节。该预计算仅在L2距离与残差编码（默认）时有效。主要权衡在于：使用更多内存换取查找速度提升。

在CPU上，由IndexIVFPQ.use_precomputed_table控制，可能取值包括：-1（禁用）、0（默认，自动判定表是否过大，超出IndexIVFPQ::precomputed_tables_max_bytes，默认为2GB则禁用），1（强制开启，表大小为256 × nlist × M），2（为MultiIndexQuantizer定制，显著更紧凑）。调用precompute_table()会根据当前设置生成数据。
在GPU上，构建时如GpuIndexIVFConfig::usePrecomputedTables为true则开启，运行时可通过GpuIndexIVF::setPrecomputedCodes(bool enable)切换。

备注

开启预计算表可以显著加速搜索，但会增加内存消耗，特别是在大规模场景下需要按需设置。

PQ的转置质心表（Transposed centroids table）

训练后的ProductQuantizer结构体，会将所有质心坐标保存在名为::centroids的一维数组中，排列方式为(M, ksub, dsub)，方便直接访问。

Faiss 1.7.3引入了两个新字段，可以提升ProductQuantizer::compute_code()的速度：

::transposed_centroids：保存转置后的质心坐标，排列方式为(dsub, M, ksub)。
::centroids_sq_lengths：保存每个质心的平方长度，排列方式为(M, ksub)。

这两个字段为临时数据，用户无需直接访问。

使用流程如下：

准备一个ProductQuantizer。
若需调整，直接训练或修改::centroids字段。
调用新函数ProductQuantizer::sync_transposed_centroids()，会自动根据当前的::centroids填充上述两个字段，并启用更高效的核函数计算ProductQuantizer::compute_code()。目前支持 $dsub=1,2,4,8$ 。
执行ProductQuantizer::compute_code()或compute_codes()。
如无需再用，可调用ProductQuantizer::clear_transposed_centroids()清理缓存。

代码示例：

# 准备pq
pq = faiss.ProductQuantizer(...)
pq.train(...)

# 启用转置质心表，加快compute_codes()
pq.sync_transposed_centroids()

# 计算代码
codes_transposed = pq.compute_codes(...)

# 不再需要时禁用转置质心表
pq.clear_transposed_centroids()

注意

启用转置质心表时，由于浮点数有限精度，pq.compute_codes()可能和未使用该功能时结果略有差异。

PCA主成分分析矩阵的计算

PCA主成分分析的矩阵计算依具体情况而异：

若训练点数量多于维数，先算协方差矩阵，再用LAPACK的dsyev提取特征值和特征向量；
若维数多于训练点，直接计算Gram矩阵（所有训练点两两点积），再提取特征值和特征向量。

非穷举式搜索的距离统计

“非穷举搜索”指只比较数据库部分向量（如IndexIVF、IndexHNSW等变体），不会遍历所有项。

实际计算的距离数量保存在全局统计变量中：

对IndexIVF，用indexIVF_stats.ndis统计
对HNSW，用hnsw_stats.ndis统计

备注

如多线程同时调用search方法时，这些统计数据仅在单线程时准确。在Python中可通过faiss.cvar前缀访问，例如faiss.cvar.indexIVF_stats.ndis。

Faiss中的4位PQ快速扫描（fast-scan）实现

详细可参考 Fast accumulation of PQ and AQ codes (FastScan)

常见PQ分解每个子向量用8位编码，便于按字节对齐并适合查表（见 Product quantization for nearest neighbor search 中公式13）。但现代CPU的算术操作远快于内存查表。

有两种提升策略：

降级到表示能力更弱、但支持高效算术的编码（如二值、标量量化）；
搜索时，将查找表（LUT, Look-Up Table）缩小存到寄存器。

上述“LUT入寄存器”技术，源自 "Cache locality is not enough: high-performance nearest neighbor search with product quantization fast scan", André et al, VLDB 15，Faiss称之为fast-scan。

只有在如下条件下可行：

CPU架构拥有充足向量寄存器，并支持查表（如Intel AVX有16个256位寄存器，ARM Neon有32个128位寄存器）；
查找表需极短：由于8位PQ表长256，改为4位后表长仅16；
查表项必须紧凑：表中数据只能用8位整型存储，无法用浮点。

实现说明

4位PQ fast-scan的设计大量借鉴了Google SCANN。

目前仅支持AVX2，未启用时因寄存器仿真极其低效；
支持的索引类型为IndexPQFastScan和IndexIVFPQFastScan；
与标准的IndexPQ/IndexIVFPQ不同，PQ4的编码数据以32为一批次存储（也支持64和96，但一般仅32批次有竞争力）。

Re-ranking（二次排序）

由于4位PQ精度较低（如PQ32×4的精度远低于PQ16×8，尽管用相同内存），通常推荐加入重排序（re-ranking）阶段。比如：需最终k=10个结果时，不妨先查k * k_factor_rf = 100个，然后对前100个候选用更精确距离再排一次序。

该“两阶段编码”被许多研究采用，例如SCANN、3级PQ搜索（见 Searching in one billion vectors: Re-rank with source coding, Jegou et al, ICASSP'11），以及 DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node, Subramanya et al. NeurIPS'19。

Faiss中可用IndexRefine实现该流程。它持有两个索引，第一个做初选，第二个做精排。

并行排序函数

高效的基础函数对Faiss程序性能非常重要。可在faiss/utils/sorting.h找到如下高性能排序相关函数：

fvec_argsort_parallel：并行实现的argsort
bucket_sort：桶排序，将输入数组重排（间接，返回置换索引），使所有0、1、...、nbucket-1元素依次排列。Python接口 faiss.bucket_sort
matrix_bucket_sort_inplace：原地桶排序，并记录每个元素来源的行。Python接口 faiss.matrix_bucket_sort
hashtable_int64_to_int64_init、..._add、..._lookup：并行的哈希表，用于批量插入与查找 (key, value)对（均为int64），哈希表存于外部。Python接口 MapInt64ToInt64

多量化索引的内存排列

乘积量化器（PQ）与叠加量化器（additive quantizer）均会生成 $M$ 个 $n$ 比特的量化索引(Q)，通常记作PQ $M\times n$ : $q_1,...,q_M$ 。

按字节排列

若 $n=8$ 时，内存排列很直接：第1字节放 $q_1$ ，第2字节放 $q_2$ ，依此类推。

若 $n\neq 8$ ，则从每字节最低有效位开始填充。例如 $n=6$ 时：

第1字节低6位为 $q_1$
第1字节高2位为 $q_2$ 的低2位
第2字节低4位为 $q_2$ 的高4位

以此类推。

作为64位整数加载

有时会把上述结构当作单个整数使用（如在MulitIndexCoarseQuantizer或AdditiveCoarseQuantizer中用整串比特表作为粗量化索引）。

由于Intel与ARM属于“小端字节序”（Little Endian），所以比特以低位到高位顺序填充。如n=6时：

$q_1$ = q & 0x3f （64进制最低6位）
$q_2$ = (q >> 6) & 0x3f（第7-12位）

通用读取方式见BitstringReader，参考链接代码。

编译期参数与内核优选

许多场景下，编译器可对已知编译期参数做更激进优化。可将函数中的离散参数转换为模板参数，让编译器对不同参数值生成不同“内核”代码，从而减少运行时判断与依赖，获得更高效的性能。

调度运行时参数到内核实现的难点

实现中最大的难点在于如何将运行时参数分发到具体的内核（kernel）实现中。通常可以通过 switch / case（分支选择语句）来实现。但当多个函数都需要使用相同的分发逻辑时，意味着相同的分支代码需要多次重复。

为了避免重复，我们使用了C++的一个巧妙特性：可变参数模板（variadic template parameters）。

具体示例解析

例如，Faiss中的这段代码，为一些常见大小的二进制签名定义了多种Hamming距离（汉明距离）计算的实现。

为了将签名的大小正确地分发到对应的内核函数，我们采用了 dispatch_HammingComputer 这个调度器函数。

调度器函数的一般格式如下：

template <class Consumer, class... Types>
typename Consumer::T dispatch_HammingComputer(
        int code_size,   //< 根据这个参数构造 Consumer::f 模板所需的类
        Consumer& consumer,
        Types... args) {
    switch (code_size) {
       /// 这里一般用宏展开多个重复代码逻辑
       /// 它会构造出 Consumer::f 的模板参数
#define DISPATCH_HC(CODE_SIZE) \
    case CODE_SIZE:            \
        return consumer.template f<HammingComputer ##CODE_SIZE>(args...);

        /// 处理不同的case（针对不同签名长度的专用实现）
        DISPATCH_HC(4);
        DISPATCH_HC(8);
        DISPATCH_HC(16);
        DISPATCH_HC(20);
        DISPATCH_HC(32);
        DISPATCH_HC(64);
        default:
            return consumer.template f<HammingComputerDefault >(args...);
    }
}
:::tip
此模式允许你通过宏和模板参数组合，高效地选择合适的内核实现，而无需重复大量的分支代码。
:::

## 如何调用调度器

调度器函数通常需要接收一个 `Consumer` 类作为模板参数（目前用函数本身作为模板参数还不可行）。
具体如何应用可参考[这个实际例子](https://github.com/facebookresearch/faiss/blob/3fe0b934f3c0b3708e28a3879ce02b81a1ede53f/faiss/IndexBinaryHash.cpp#L179)。

以下是典型的调用和实现方式：

```c++
// 定义一个对象，包含 T 和 f 方法，并将参数转发给相应的模板函数
struct Run_search_single_query {
    using T = void;
    template <class HammingComputer, class... Types>
    T f(Types... args) {
        search_single_query_template<HammingComputer >(args...);
    }
};

void search_single_query(
        const IndexBinaryHash& index,
        const uint8_t* q,
        SearchResults& res,
        size_t& n0,
        size_t& nlist,
        size_t& ndis) {
    Run_search_single_query r; // 实例化 Consumer 对象
    dispatch_HammingComputer(
            index.code_size, // 传递到调度器的参数
            r, // consumer
            index, q, res, n0, nlist, ndis // 额外传递给 Consumer::f 的参数
    );
}
### 总结说明

:::note
这种调度方式虽然实现起来方便，但也有一定的副作用，例如可能导致代码体积（code bloat）明显增大。
推荐在实践中保持谨慎，可借助常识或基准性能测试（benchmarking），验证参数特化确实带来了加速，否则不宜滥用。
:::

k-means（K均值）实现说明

IVFPQ中的预计算查找表

PQ的转置质心表（Transposed centroids table）

PCA主成分分析矩阵的计算

非穷举式搜索的距离统计

Faiss中的4位PQ快速扫描（fast-scan）实现

实现说明​

Re-ranking（二次排序）

并行排序函数

多量化索引的内存排列

按字节排列​

作为64位整数加载​

编译期参数与内核优选​

调度运行时参数到内核实现的难点​

具体示例解析​