不朽 C++ 为新贵 Python 应用提速 8000 倍！

2018 年 7 月 23 日 CSDN

在人工智能浪潮之下，全民学习 Python 已成为必然趋势。Python 作为一门胶水语言，以简单的语法、良好的交互性、移植性等优势受到诸多开发者的喜爱，但要和老牌的 C++ 相较而言，谁运行的速度更快一些？相信很多开发者会毫无疑问地选择了 C++，而本文作者也证实了这一点。

以下为译文：

最近我在开发一个名为 Bard（https://github.com/antlarr/bard）的命令行应用，它是个管理本地音乐库的音乐管理器。Bard 会根据歌曲生成声音指纹（利用 acoustid：https://acoustid.org/）并将所有歌曲的元数据保存到 sqlite 数据库中。这样你就可以很容易地进行查询，并找到重复的歌曲，即使歌曲的标签不正确也能找到。本文笔者分享了查找重复歌曲的算法，并使用 Python 和 C++ 17 对该算法进行两次优化，探索如何使这个算法比原来快 8000 倍。

算法

要判断两首歌曲是否相似，需要比较它们的声音指纹。听上去很容易（实际上的确不难），但并不是初看上去那么直接。acoustid 计算出的声音指纹并不是一个数字，而是一个数字的数组，更准确地说，是一系列字符的数组。因此不能比较数字本身，而要比较数字中的字符。如果所有字符完全一致，则可以认为两首歌曲是同一个。如果 99% 的字符一致，则可以认为有 99% 的可能性两者相同，两者的差异可能是由编码问题（如一首歌用 192kbits/s 编码成 mp3，另一首用的是 128kbits/s）等造成的。

但在比较歌曲时还需要考虑更多情况。有时两首歌开头的空白时间长短不同，因此指纹的比特不会完美地对齐，直接比较会不匹配，但将其中一个指纹移动一位可能就能匹配。

因此，要比较两首歌，我们不仅要比较它们的指纹，还要模拟增加或减少开头空白的长度，看看它们的匹配程度是上升还是下降。目前 Bard 会将数组向一个方向移动 100 位，再向相反方向移动 100 位，也就是说每首歌都要进行 200 次指纹比较。

因此，如果要比较一个曲库中的所有歌曲以查找重复，我们需要比较 ID1 和 2，然后将 ID 3 与 ID 1 和 ID 2 比较，一般来说每首歌都要与前面的所有歌曲进行比较。这样，如果曲库里有 100 首歌曲，那么需要比较 1000 * 1001/ 2 = 500500 首歌曲（也就是说，要比较 100100000 次指纹）。

最初的 Python 实现

Bard 是用 Python 写的，所以第一版实现采用了 Python 的列表以整数数组的方式保存指纹。每次迭代过程中需要移位时，我会在其中一个指纹数组前面加个 0，然后迭代整个数组，依次比较每个元素。比较的方法是对两个元素执行异或操作，然后用一个算法来数出整数中的比特个数：

def count_bits_set(i):
    i = i – ((i >> 1) & 0x55555555)
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333)
    return (((i + (i >> 4) & 0xF0F0F0F) * 0x1010101) & 0xffffffff) >> 24

我们把这个实现的速度作为参考值，称之为一倍速。

第一个改进

第一个改进，我尝试将比特计数算法改成较快的gmpy.popcount（http://gmpy2.readthedocs.io/en/latest/mpz.html#mpz-functions），还加入了终止阈值来改进算法。这个新的算法会在超过终止阈值时判断为不可能匹配，从而停止比较。例如，如果在计算的过程中发现，即使剩余的比特全部匹配，两首歌的匹配程度也不可能超过 55%，那就直接返回“不同歌曲”（但还是要与其他歌曲比较，以防万一）。

这个改进使得比较速度几乎提高到了两倍速。

使用 C++17

此时，我认为这段代码没办法很容易扩展到更大的曲库上，因此我认为 Bard 需要更好的实现。修改内存很慢，而 C/C++ 可以实现更细粒度的底层优化，但我并不想用 C++ 重写整个应用，因此我采用了Boost.Python（https://www.boost.org/doc/libs/1_65_0/libs/python/doc/html/index.html），仅把这个算法用 C++ 实现了，并从 Python 应用中调用这个算法。不得不说，我发现在 Python 中集成 C++ 方法非常容易，因此我非常推荐使用 Boost.Python。

在新的 C++ 实现中，我使用了 STL 的 vector 来保存指纹，并且事先加入了最大的偏移量，这样在算法中就无需修改向量中的元素，只需模拟位移即可。我还使用 STL 的 map，以歌曲的 ID 为索引来保存所有指纹。最后，我还添加了一个重要的优化措施，通过 gcc 的__builtin_popcount（https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html#index-_005f_005fbuiltin_005fpopcount），利用 CPU 指令来计算字符。

这个算法最大的好处就是比较过程不会修改或复制任何指纹，这使得速度增加了 126.47 倍。此时我开始计算另一个度量：每秒钟比较的歌曲数（别忘了每比较一对歌曲就要做 200 次指纹比较）。这个算法的平均速度是 580 首/秒。或者换句话说，要想比较 1000 首歌，需要花费大约 14 分 22 秒（注意原来的 Python 实现大约需要一天 6 小时 16 分 57 秒）。

首次并行算法尝试

我运行 Brad 的是一颗 i7 CPU，我总为我的程序只用了一个 CPU 感到遗憾。由于比较两个歌曲的算法并不会改变任何数据，我觉得可以尝试使用并行算法，使它能在所有 8 个核心中一起运行，并在每次迭代结束时合并结果。因此我开始研究怎样实现，我发现每首歌与前面的所有歌进行的比较是通过对包含所有已处理过的歌曲的 std::map 进行循环实现的。那么，如果有个 for-each 循环能在不同的线程上运行每次迭代就好了。结果还真有！C++17 中的std::for_each（https://en.cppreference.com/w/cpp/algorithm/for_each）可以指定 ExecutionPolicy，通过它可以让循环在不同的线程上执行。然后是坏消息：这个标准还没有被 gcc 完全支持。

所以我搜索了一些 for_each 的实现，最后在一个 stackoverflow 的问题下（https://stackoverflow.com/questions/40805197/parallel-for-each-more-than-two-times-slower-than-stdfor-each）找到了一个。这个问题提到了一个从《C++Concurrency in Action》一书中的实现方案，我不确定这段代码的版权如何，所以不能直接复制到 Brad 中，但我可以用它做一些测试以便进行测量。

这个方法能把速度提高到 1897 倍，或者说大约 8700 首歌曲/秒（1000 首歌曲需要处理大约57秒。很不错，是吧！）

第二次并行尝试

我需要找个我能用的并行版本的 for_each。幸运的是，最终我发现 gcc 包含了 C++ 标准库中部分算法的实验性并行实现，其中包含了__gnu_parallel::for_each（https://gcc.gnu.org/onlinedocs/libstdc++/manual/parallel_mode_using.html，文档页面上还有更多的并行算法）。只需要链接 openmp 库就可以了。

所以我修改了代码，结果遇到一个问题：虽然我调用了 __gnu_parallel::for_each 但每次测试时发现它只会串行执行！花了点功夫才找出原因，但阅读 gcc 关于 __gnu_parallel::for_each 的实现后，我注意到它需要一个随机访问迭代器（http://www.cplusplus.com/reference/iterator/RandomAccessIterator/），但我让它在 std::map 上迭代，而 map 结构是双向迭代器，不是随机迭代器。

于是我修改了代码，将指纹从 std::map<int,std::vector<int>> 复制到 std:;vector<std::pair<int,std:vector<int>>>，这样 __gnu_parallel::for_each 就能用 8 个线程的线程池运行了。

gcc 实现比 stackoverflow 上的实现更快，速度是 2442 倍，约 11200 首歌曲/秒，1000 首歌曲只需 44 秒。

很显然我却忘记了的重要改进

在检查 Bard 的编译器时，我发现我没有使用优化速度的编译器开关！于是我给编译器加上了 -Ofast-march=native -mtune=native -funroll-loops，就这么简单。猜猜发生了什么……

速度提高到了 6552 倍，约 30050 首歌曲/秒，1000 首歌曲只需 16 秒。

免费得到的 Tumbleweed 的改进

我开发所用的系统里运行了 openSUSETumbleweed，你们估计知道，它是个非常好用的滚动发布的 Linux 发行版。有一天我在做测试时，Tumbleweed 把编译器从 gcc 7.3 更新到了 gcc8.1。所以我觉得我应该再测试一下。

仅仅是把编译器升级到最新版，速度就提高到了 7714 倍，35380 首歌曲/秒，1000 首歌曲只需 14 秒。

最终的优化

我还没做的一个非常明显的优化就是把 map 换成 vector，这样就无需每次调用 for_each 之前进行转换了。而且，vector 能提前分配空间，由于我知道在整个算法结束时 vector 的最终大小，因此我修改了代码，以便事先分配空间。

这个修改给了我最后一次提速，速度提高到 7998 倍，36680 首歌曲/秒，完全处理 1000 首歌曲的曲库仅需 13 秒。

结论

从这次经历中得到的一些值得记录的经验：

花点时间优化代码，会物有所值。
如果你使用 C++，并且能够使用现代编译器，那一定要用 C++17，它能编译出好得多、效率高得多的代码。Lambda、结构化绑定、constexpr 等都值得花时间去阅读。
让编译器为你做一些工作。你不需要花任何时间，它就能优化代码。
尽可能少地复制或移动数据。这样会降低速度，而且多数情况下只需在开发开始之前仔细考虑下数据结构就能避免。
可能时使用线程。
可能是最重要的一条经验：测量一切。没有测量就没办法提高。（也许可以，但你得不到准确的结论。）