在人工智能浪潮之下，全民學習 Python 已成為必然趨勢。Python 作為一門膠水語言，以簡單的語法、良好的交互性、移植性等優勢受到諸多開發者的喜愛，但要和老牌的 C++ 相較而言，誰運行的速度更快一些？相信很多開發者會毫無疑問地選擇了 C++，而本文作者也證實了這一點。

最近我在開發一個名為 Bard（https://github.com/antlarr/bard）的命令行應用，它是個管理本地音樂庫的音樂管理器。Bard 會根據歌曲生成聲音指紋（利用 acoustid：https://acoustid.org/）并將所有歌曲的元數據保存到 sqlite 數據庫中。這樣你就可以很容易地進行查詢，并找到重復的歌曲，即使歌曲的標簽不正確也能找到。本文筆者分享了查找重復歌曲的算法，并使用 Python 和 C++ 對該算法進行兩次優化，探索如何使這個算法比原來快 8000 倍。

1.算法

要判斷兩首歌曲是否相似，需要比較它們的聲音指紋。聽上去很容易（實際上的確不難），但并不是初看上去那么直接。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 次指紋）。

2.最初的 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

我們把這個實現的速度作為參考值，稱之為一倍速。

3.第一個改進

第一個改進，我嘗試將比特計數算法改成較快的gmpy.popcount（http://gmpy2.readthedocs.io/en/latest/mpz.html#mpz-functions），還加入了終止閾值來改進算法。這個新的算法會在超過終止閾值時判斷為不可能匹配，從而停止比較。例如，如果在計算的過程中發現，即使剩余的比特全部匹配，兩首歌的匹配程度也不可能超過 55%，那就直接返回“不同歌曲”（但還是要與其他歌曲比較，以防萬一）。

這個改進使得比較速度幾乎提高到了兩倍速。

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++ 實現中，我使用了 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 秒）。

5.首次并行算法嘗試

我運行 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秒。很不錯，是吧！）

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<int,std::vector> 復制到 std:;vector<std::pair<int,std:vector>>，這樣 __gnu_parallel::for_each 就能用 8 個線程的線程池運行了。

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

7.很顯然我卻忘記了的重要改進

在檢查 Bard 的編譯器時，我發現我沒有使用優化速度的編譯器開關！于是我給編譯器加上了 -Ofast-march=native -mtune=native -funroll-loops，就這么簡單。猜猜發生了什么……

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

8.免費得到的 Tumbleweed 的改進

我開發所用的系統里運行了 openSUSETumbleweed，你們估計知道，它是個非常好用的滾動發布的 Linux 發行版。有一天我在做測試時，Tumbleweed 把編譯器從 gcc 7.3 更新到了 gcc8.1。所以我覺得我應該再測試一下。

僅僅是把編譯器升級到最新版，速度就提高到了 7714 倍，35380 首歌曲/秒，1000 首歌曲只需 14 秒。

9.最終的優化

我還沒做的一個非常明顯的優化就是把 map 換成 vector，這樣就無需每次調用 for_each 之前進行轉換了。而且，vector 能提前分配空間，由于我知道在整個算法結束時 vector 的最終大小，因此我修改了代碼，以便事先分配空間。

這個修改給了我最后一次提速，速度提高到 7998 倍，36680 首歌曲/秒，完全處理 1000 首歌曲的曲庫僅需 13 秒。

結論

從這次經歷中得到的一些值得記錄的經驗：

• 花點時間優化代碼，會物有所值。

• 讓編譯器為你做一些工作。你不需要花任何時間，它就能優化代碼。
• 盡可能少地復制或移動數據。這樣會降低速度，而且多數情況下只需在開發開始之前仔細考慮下數據結構就能避免。
• 可能時使用線程。
• 可能是最重要的一條經驗：測量一切。沒有測量就沒辦法提高。（也許可以，但你得不到準確的結論。）