D#0003.md

optimizing cosine distance searching in a million feature-set

引言

求解两个向量之间的距离(或者说相似度)，广泛应用于数据挖掘，图像处理和深度学习中。例如很多人脸识别的模型，在网络的最后一层都是计算出输入人脸的一个固定维数的特征向量，然后根据两个人脸对应的两个特征向量之间的距离来做人脸验证和识别。在真实的应用场景中，人脸底库保存的特征向量数量很大(十万百万级)，计算特征向量之间的距离函数就会被调用很多次，所以优化这个搜索过程和最佳距离的计算函数就显得尤为重要。这里，我以优化在100万底库的场景下，找出底库中与给定512维向量之间余弦距离最近的那个样本的索引值为例，试验一下在通用PC平台上到底能优化多少。

欢迎探讨，本文持续维护。

实验平台：

• 操作系统：Ubuntu 16.04 LTS

• 编译器：g++ (Ubuntu 5.4.0-6ubuntu1~16.04.10) 5.4.0 20160609

  　　　　gcc (Ubuntu 5.4.0-6ubuntu1~16.04.10) 5.4.0 20160609

• 硬件配置：

  1. CPU Intel(R) Core(TM) i7-7700 CPU @ 3.60GHz

  2. Memory 8G DDR2

  3. GPU N/A

Step 1,最基础的实现方式

最基础的实现方式也是最容易的方式，作为我们的起点，实验代码：

耗用了3846454us

Step 2, 打开优化开关-O3 -Ofast -ffast-math(牺牲了精度)

耗用了398475us，差不多加速了x10倍

Step 3, 数据类型优化，double->float(牺牲了精度)

耗用了205285us，加速x2倍

Step 4, xXXX

杂项

以下是几点心得：

• 优化无定法，一定要根据具体的问题来做来实验。要在优化前确定优化的目标和约束，优化是一个性能（程序运行时间），资源（CPU、GPU、内存占用），代码可维护性和跨平台与成本（开发测试时间、人力投入）多者的平衡，在开始动手前最好能对能牺牲什么，一定不能牺牲什么，优化的目标，有个基本的想法，不打无准备的仗;
• 算法优化要在代码优化前面，算法才是程序的核心灵魂，一辆汽车发动机不行，外观再流线型设计也跑不快，牛顿下降比梯度下降快，二分查找比线性搜索快，做代码优化前，先考虑一下算法是不是不能优化了？
• 优化要先找到热点，找到程序中最耗时(或耗资源)的地方，下大力气挖潜力;放过非热点部分的优化;要不然就本末倒置，累死也无功;热点是变动的，一个热点优化了，可能原先排名第二的热点就成了现在排第一的了;
• 优化过程要先易后难，先吃肉后啃骨头，一般水平的程序员写的代码和算法或者训练出来的模型，都有很大的优化空间，往往开个编译器的-O3，改改数据类型，就能取得不错的效果。从人的心理学上讲，先吃几块肉，看到点优化的效果，也能给自己一点啃骨头的信心和动力。先开编译器优化选项，后做缓存优化和汇编，肯定没错的;
• 啃骨头的时候，要善于借助工具来指导优化，各个平台都有各自profiling的工具，也有各自的小实用程序(例如htop, gprof)或者自己开发的收集的小工具，找自己顺手的用，相信工具;
• 在优化的过程中要试，要记下各个优化点和优化的时间大小，还要仔细检查优化没有影响输入和输出，最好做个表格，万一修改没有取得好的效果，及时回滚;优化好了也要思考背后的道理，不能知其然不知其所以然，及时总结经验;
• 如果优化手段比较trick，做好记录和代码注释;
• 优化不必太早，在开发阶段，更重要的是代码的规范性，结果的正确性和开发进度;
• 优化也是有成本的，例如人力投入，资源占用等，而且优化往往会使代码难懂难维护，还可能引入新的bug，使代码产生对平台的依赖，不到万不得已，能不优化就不要优化

总结

参考资料

• 《深入理解计算机系统》
• 《编程珠玑》
• 《代码大全》