faiss库中ivf-sq（ScalarQuantizer，标量量化）代码解读-4

参考内容

参考代码解读3

调试

通过调试跑通ivfsq的流程，记录调试内容：
前面的初始化内容如下：

int d = 64;      // dimension
    int nb = 100000; // database size
    int nq = 10000;  // nb of queries

    std::mt19937 rng;
    std::uniform_real_distribution<> distrib;

    float* xb = new float[d * nb];
    float* xq = new float[d * nq];

    for (int i = 0; i < nb; i++) {
        for (int j = 0; j < d; j++)
            xb[d * i + j] = distrib(rng);
        xb[d * i] += i / 1000.;
    }

    for (int i = 0; i < nq; i++) {
        for (int j = 0; j < d; j++)
            xq[d * i + j] = distrib(rng);
        xq[d * i] += i / 1000.;
    }

• d：设置向量的维度为64维；
• nb：设置数据库的大小为100000，也就是可以存储10万条数据；
• nq：查询的向量数据我们设置为1万条；
• rng：伪随机数生成器 (PRNG, Pseudo-Random Number Generator)，std::mt19937 的周期为 $2^{19937}-1$
  ，即在达到周期之前，生成的伪随机数不会重复。
• distrib：用来生成 均匀分布 的随机数
• 第一个循环：生成数据库里面原本存在的数据
• 第二个循环：生成查询向量的数据
  • 其中xq[d * i] += i / 1000.，在每个数据的第一个插入随机数，使得数据不是完全的一致，并且保证为浮点数。

我们直接忽视掉前面初始化数据库和向量的内容，直接对下面的代码进行解读，把这个过程分为3个部分：

###################################################################################
# 第一部分
###################################################################################

int nlist = 100;
    int k = 4;
    int m = 8;                       // bytes per vector
    faiss::IndexFlatL2 quantizer1(d); // the other index
    faiss::IndexIVFScalarQuantizer index1(
            &quantizer1, d, nlist, faiss::ScalarQuantizer::QT_8bit);
    index1.sq.rangestat = faiss::ScalarQuantizer::RS_meanstd;
    index1.train(nb, xb);
    index1.add(nb, xb);

###################################################################################
# 第二部分
###################################################################################
    { // sanity check
        idx_t* I = new idx_t[k * 5];
        float* D = new float[k * 5];

        index1.search(5, xb, k, D, I);

        printf("I=\n");
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < k; j++)
                printf("%5zd ", I[i * k + j]);
            printf("\n");
        }

        printf("D=\n");
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < k; j++)
                printf("%7g ", D[i * k + j]);
            printf("\n");
        }

        delete[] I;
        delete[] D;
    }
###################################################################################
# 第三部分
###################################################################################
    { // search xq
        idx_t* I = new idx_t[k * nq];
        float* D = new float[k * nq];

        //index.nprobe = 10;
        index1.search(nq, xq, k, D, I);

        printf("ivfsq8 I=\n");
        for (int i = nq - 5; i < nq; i++) {
            for (int j = 0; j < k; j++)
                printf("%5zd ", I[i * k + j]);
            printf("\n");
        }

        delete[] I;
        delete[] D;
    }

    delete[] xb;
    delete[] xq;

    return 0;
}

第一部分

faiss::IndexFlatL2 quantizer1(d)

针对faiss::IndexFlatL2 quantizer1(d);，获取的调试信息如下：

逐步调用分析
1.

faiss::IndexFlatL2 quantizer1(d);

• 这是 IndexFlatL2 的构造函数调用，传入了向量维度 d=64。
• IndexFlatL2 是 IndexFlat 的子类，最终会调用 IndexFlat 和 IndexFlatCodes 的构造函数，最后到最顶层基类 Index。

2. faiss::IndexFlatL2::IndexFlatL2(idx_t d)

explicit IndexFlatL2(idx_t d) : IndexFlat(d, METRIC_L2) {}

• 调用了父类 IndexFlat 的构造函数，传入了维度 d=64 和度量类型 METRIC_L2。
• 这里选择 METRIC_L2，表明后续计算中会使用欧氏距离 (L2-norm) 作为向量之间的距离度量。

3. faiss::IndexFlat::IndexFlat(idx_t d, MetricType metric)

IndexFlat::IndexFlat(idx_t d, MetricType metric)
    : IndexFlatCodes(sizeof(float) * d, d, metric) {}

• 调用了父类 IndexFlatCodes 的构造函数。
• 这里计算了 code_size = sizeof(float) * d = 4 * 64 = 256，表示每个向量的编码大小为 256 字节（因为 float 是 4 字节）。
• 传入了维度 d=64 和距离度量方式 METRIC_L2。

4. faiss::IndexFlatCodes::IndexFlatCodes(size_t code_size, idx_t d, MetricType metric)

IndexFlatCodes::IndexFlatCodes(size_t code_size, idx_t d, MetricType metric)
    : Index(d, metric), code_size(code_size) {}

• 调用了最顶层基类 Index 的构造函数，并初始化了 code_size。
• code_size=256 表示每个向量的存储占用空间。

5. faiss::Index::Index(idx_t d, MetricType metric)

Index::Index(idx_t d, MetricType metric)
    : d(d), ntotal(0), verbose(false), is_trained(true), 
      metric_type(metric), metric_arg(0) {}

• 初始化了基础成员变量：
  • d=64：维度。
  • ntotal=0：索引中存储的向量总数，初始为 0。
  • verbose=false：是否启用调试信息输出。
  • is_trained=true：索引是否已经被训练，Flat 索引不需要训练，所以默认为 true。
  • metric_type=METRIC_L2：距离度量类型为欧氏距离。
  • metric_arg=0：距离计算的附加参数（对于 L2 距离不需要附加参数）。

构造函数调用链：IndexFlatL2 → IndexFlat → IndexFlatCodes → Index。 构造函数需要逐级初始化父类的属性，这样可以逐步完成对象的初始化工作。IndexFlatL2 的构造依赖于 IndexFlat 和 IndexFlatCodes 的实现，因此会调用这些父类的构造函数。

faiss::IndexIVFScalarQuantizer index1(&quantizer1, d, nlist, faiss::ScalarQuantizer::QT_8bit);

调用信息：

这里仍然可以发现这里存在的调用栈也是对index1进行赋值：
构造函数调用链：IndexIVFScalarQuantizer → IndexIVF → Index。

index1.sq.rangestat = faiss::ScalarQuantizer::RS_meanstd;

这里面从

这里面的枚举类型中选择了meanstd类型。

index1.train(nb, xb);

重要的部分就是查看ivfsq如何去训练寻找聚类中心，以及如何将相对应的向量进行范围计算并进行量化操作的这个流程，先查看总体的gdb调试流程，后续对整个流程进行总结：

先记录调用栈：

在这个调用栈的第2步里面，记录Level1Quantizer数据结构的构造过程如下：
Level1Quantizer数据结构中的char quantizer_trains_alone变量的参数，默认值为0
=0: 使用量化器作为索引，这种模式通常用于高效搜索，在分配数据点到聚类中心时减少计算复杂度。
=1: 直接调用量化器的 train() 方法，适用于量化器本身能高效处理训练数据的情况。
=2: 先在扁平索引中执行 k-means 聚类，之后将计算得到的聚类中心导入量化器，这种方法可能用于特定情况下的性能优化。

展示了 faiss::Clustering 的构造过程，主要完成了以下工作：

初始化了 faiss::Clustering 类的基本成员变量（如维度 d、聚类数量 k 和聚类参数 cp）。
构造了多个 std::vector 容器，用于存储中间数据（如浮点数、迭代统计等）。
展示了 STL 容器（如 std::vector）构造过程的细节，包括分配内存和初始化分配器。

index1.add（）;

上述的7和8步骤会不断在循环，循环25次。对于这个25次的由来，如下：
7和8步骤位于这个for循环，查看niter被写定为25.

第二部分

这里其他部分比较简单， 主要是查看index1.search()，看看这模拟索引扫描的部分如何进行的。
调用栈信息：

进入到train_encoded里面就会开启很复杂的逻辑流程，后续会专门进行讲解。

第三部分

这部分的内容和第二部分是相似的，改动的就是对一些参数进行了部分修改。

这里就对后面的两层嵌套循环进行解析：
分析代码
下面的 for 循环负责输出从查询结果中获取的最后 5 个查询向量的最近邻索引（IDs）。具体来看：

for (int i = nq - 5; i < nq; i++) {
    for (int j = 0; j < k; j++)
        printf("%5zd ", I[i * k + j]);
    printf("\n");
}

变量含义

• nq: 查询向量的总数。
• k: 每个查询向量需要找到的最近邻的数量。
• I: 保存查询结果的最近邻索引数组，维度为 nq × k，即每个查询向量都有 k 个最近邻索引。
• D: 保存查询结果的距离数组，维度也为 nq × k，与 I 一一对应，记录每个查询向量到其最近邻的距离。
• 循环变量:
  • i: 遍历最后 5 个查询向量的索引，从 nq - 5 到 nq - 1。
  • j: 遍历每个查询向量对应的 k 个最近邻索引。

输出内容

1. 外层循环 (i): 遍历最后 5 个查询向量的结果。

   • i 表示第几个查询向量（编号从 0 到 nq - 1），这里输出的是最后 5 个查询向量（nq - 5 到 nq - 1）。

2. 内层循环 (j): 遍历每个查询向量的 k 个最近邻索引。

   • I[i * k + j]: 表示查询向量 i 的第 j 个最近邻的索引。

3. printf 输出:

• %5zd: 格式化输出索引值，占 5 格宽度，zd 是用于 size_t 类型的格式。
• 每一行输出一个查询向量的最近邻索引。

输出示例
假设 nq = 10（总共有 10 个查询向量），k = 4（每个查询向量找 4 个最近邻），并且 I 的内容如下：

I = [1, 3, 7, 9, ... (其余索引)]

那么，循环的输出可能为：

ivfsq8 I=
    5     1     7     3
    9     3     2     8
    4     5     6     7
    0     1     2     3
    8     4     9     5

• 每一行表示一个查询向量的 k 个最近邻的索引。
• 行数为 5（对应最后 5 个查询向量）。
• 每行有 k 个值（每个查询向量的 k 个最近邻）。

输出结构

I=
    0     1     2     3 
    0     1     2     3 
    0     1     2     3 
    0     1     2     3 
    0     1     2     3 
D=
7.02291 7.02291 7.02291 7.02291 
5.26499 5.26499 5.26499 5.26499 
5.95545 5.95545 5.95545 5.95545 
 5.3095  5.3095  5.3095  5.3095 
5.43891 5.43891 5.43891 5.43891 
ivfsq8 I=
 8493  8566  8584  8596 
 8493  8566  8584  8596 
 9744  9817  9818  9825 
 8493  8566  8584  8596 
 9744  9817  9818  9825