在人工智能的浪潮下，大家学习Python已经成为必然趋势。作为一种胶水语言，Python以其简单的语法、良好的交互性和可移植性而受到众多开发者的喜爱。但是和旧的C++相比，谁跑得更快呢？相信很多开发者无疑会选择C++，本文作者也证实了这一点。最近我一直在开发一个名为Bard(https://github.com/antlarr/bard)的命令行应用程序，它是本地音乐库的音乐管理器。Bard从歌曲中生成声学指纹（使用acousticid：https://acoustid.org/）并将所有歌曲的元数据保存到sqlite数据库中。这使您可以轻松查询和查找重复的歌曲，即使歌曲没有正确标记。本文作者分享了一个查找重复歌曲的算法，并使用Python和C++对算法进行了两次优化，探索如何让这个算法比原来快8000倍。1.判断两首歌曲是否相似，算法需要比较它们的声音指纹。这听起来很简单（实际上并非如此），但它并不像最初看起来那么简单。acoustic计算出来的声学指纹不是一个数字，而是一个数字数组，更准确的说，是一个字符数组。所以不比较数字本身，而是比较数字中的字符。如果所有角色都一模一样，那两首歌就可以认为是同一首。如果99%的字符相同，则可以认为两者有99%的概率是相同的，两者不同可能是编码问题造成的（比如一首歌编码成mp3用192kbits/s，另一种编码为128kbits/s）等。但是在比较歌曲时还有更多需要考虑的因素。有时两首歌开头的空白时间长短不同，所以指纹的位不会完全对齐，直接比较不匹配，但将其中一个指纹移动一位可能会匹配。所以要比较两首歌曲，我们不仅要比较他们的指纹，还要模拟增加或减少前导空白的长度，看看他们的匹配是上升还是下降。目前Bard会将数组在一个方向上移动100位，在相反方向上移动100位，这意味着对每首歌曲进行200次指纹比较。所以如果我们要比较一个库中的所有歌曲来查找重复的，我们需要比较ID1和2，然后比较ID3和ID1和ID2，一般每首歌曲都会和之前的所有歌曲进行比较。这样，如果曲库中有100首歌曲，则需要比对1000*1001/2=500500首歌曲（即比对100100000个指纹）。2.Bard最初的Python实现是用Python编写的，所以第一个版本的实现使用Python列表将指纹存储在整数数组中。每次在迭代过程中需要移位时，我都会在其中一个指纹数组前添加一个0，然后遍历整个数组，依次比较每个元素。比较的方法是将两个元素异或，然后用一个算法统计整数的位数：defcount_bits_set(i):i=i–((i>>1)&0x55555555)i=(i&0x33333333)+((i>>2)&0x33333333)return(((i+(i>>4)&0xF0F0F0F)*0x1010101)&0xffffffff)>>24我们把这个实现的速度作为参考值，叫做是倍速。3.第一个改进第一个改进，我尝试将位计数算法更改为更快的gmpy.popcount（http://gmpy2.readthedocs.io/en/latest/mpz.html#mpz-functions），也是一个终止添加阈值以改进算法。新算法在超过终止阈值时判断不可能匹配，从而停止比较。例如，如果在计算过程中发现两首歌匹配度不能超过55%，即使剩下的所有位都匹配，那么就直接返回“differentsong”（但还是要和其他歌曲比较，以防万一）。这种改进使得比较速度几乎快了一倍。4.使用C++在这一点上，我不认为这段代码可以很容易地扩展到更大的音乐库，所以我认为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++实现中，我使用STLvector来保存指纹，并预先加上最大偏移量，这样在算法中就不需要修改vector中的元素，只需模拟位移即可。我还使用STL的映射来保存歌曲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秒）。5.第一次并行算法尝试。我在i7CPU上运行Brad，我总是后悔我的程序只使用了一个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秒。不错，呵呵！）6.第二次并行尝试我需要找到一些我可以使用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
