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

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

1.算法

要判斷兩首歌曲是否相似，需要比較它們的聲音指紋。聽上去很容易（實(shí)際上的確不難），但并不是初看上去那么直接。acoustid 計(jì)算出的聲音指紋并不是一個(gè)數(shù)字，而是一個(gè)數(shù)字的數(shù)組，更準(zhǔn)確地說，是一系列字符的數(shù)組。因此不能比較數(shù)字本身，而要比較數(shù)字中的字符。如果所有字符完全一致，則可以認(rèn)為兩首歌曲是同一個(gè)。如果 99% 的字符一致，則可以認(rèn)為有 99% 的可能性兩者相同，兩者的差異可能是由編碼問題（如一首歌用 192kbits/s 編碼成 mp3，另一首用的是 128kbits/s）等造成的。

但在比較歌曲時(shí)還需要考慮更多情況。有時(shí)兩首歌開頭的空白時(shí)間長短不同，因此指紋的比特不會(huì)完美地對(duì)齊，直接比較會(huì)不匹配，但將其中一個(gè)指紋移動(dòng)一位可能就能匹配。

因此，要比較兩首歌，我們不僅要比較它們的指紋，還要模擬增加或減少開頭空白的長度，看看它們的匹配程度是上升還是下降。目前 Bard 會(huì)將數(shù)組向一個(gè)方向移動(dòng) 100 位，再向相反方向移動(dòng) 100 位，也就是說每首歌都要進(jìn)行 200 次指紋比較。

因此，如果要比較一個(gè)曲庫中的所有歌曲以查找重復(fù)，我們需要比較 ID1 和 2，然后將 ID 3 與 ID 1 和 ID 2 比較，一般來說每首歌都要與前面的所有歌曲進(jìn)行比較。這樣，如果曲庫里有 100 首歌曲，那么需要比較 1000 * 1001/ 2 = 500500 首歌曲（也就是說，要比較 100100000 次指紋）。

2.最初的 Python 實(shí)現(xiàn)

Bard 是用 Python 寫的，所以第一版實(shí)現(xiàn)采用了 Python 的列表以整數(shù)數(shù)組的方式保存指紋。每次迭代過程中需要移位時(shí)，我會(huì)在其中一個(gè)指紋數(shù)組前面加個(gè) 0，然后迭代整個(gè)數(shù)組，依次比較每個(gè)元素。比較的方法是對(duì)兩個(gè)元素執(zhí)行異或操作，然后用一個(gè)算法來數(shù)出整數(shù)中的比特個(gè)數(shù)：

def count_bits_set(i):

i = i – ((i >> 1) & 0x55555555)

i = (i & 0x33333333) + ((i >> 2) & 0x33333333)

return (((i + (i >> 4) & 0xF0F0F0F) * 0x1010101) & 0xffffffff) >> 24

我們把這個(gè)實(shí)現(xiàn)的速度作為參考值，稱之為一倍速。

3.第一個(gè)改進(jìn)

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

這個(gè)改進(jìn)使得比較速度幾乎提高到了兩倍速。

4.使用 C++

此時(shí)，我認(rèn)為這段代碼沒辦法很容易擴(kuò)展到更大的曲庫上，因此我認(rèn)為 Bard 需要更好的實(shí)現(xiàn)。修改內(nèi)存很慢，而 C/C++ 可以實(shí)現(xiàn)更細(xì)粒度的底層優(yōu)化，但我并不想用 C++ 重寫整個(gè)應(yīng)用，因此我采用了Boost.Python（https://www.boost.org/doc/libs/1_65_0/libs/python/doc/html/index.html），僅把這個(gè)算法用 C++ 實(shí)現(xiàn)了，并從 Python 應(yīng)用中調(diào)用這個(gè)算法。不得不說，我發(fā)現(xiàn)在 Python 中集成 C++ 方法非常容易，因此我非常推薦使用 Boost.Python。

在新的 C++ 實(shí)現(xiàn)中，我使用了 STL 的 vector 來保存指紋，并且事先加入了最大的偏移量，這樣在算法中就無需修改向量中的元素，只需模擬位移即可。我還使用 STL 的 map，以歌曲的 ID 為索引來保存所有指紋。最后，我還添加了一個(gè)重要的優(yōu)化措施，通過 gcc 的__builtin_popcount（https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html#index-_005f_005fbuiltin_005fpopcount），利用 CPU 指令來計(jì)算字符。

這個(gè)算法最大的好處就是比較過程不會(huì)修改或復(fù)制任何指紋，這使得速度增加了 126.47 倍。此時(shí)我開始計(jì)算另一個(gè)度量：每秒鐘比較的歌曲數(shù)（別忘了每比較一對(duì)歌曲就要做 200 次指紋比較）。這個(gè)算法的平均速度是 580 首/秒?；蛘邠Q句話說，要想比較 1000 首歌，需要花費(fèi)大約 14 分 22 秒（注意原來的 Python 實(shí)現(xiàn)大約需要一天 6 小時(shí) 16 分 57 秒）。

5.首次并行算法嘗試

我運(yùn)行 Brad 的是一顆 i7 CPU，我總為我的程序只用了一個(gè) CPU 感到遺憾。由于比較兩個(gè)歌曲的算法并不會(huì)改變?nèi)魏螖?shù)據(jù)，我覺得可以嘗試使用并行算法，使它能在所有 8 個(gè)核心中一起運(yùn)行，并在每次迭代結(jié)束時(shí)合并結(jié)果。因此我開始研究怎樣實(shí)現(xiàn)，我發(fā)現(xiàn)每首歌與前面的所有歌進(jìn)行的比較是通過對(duì)包含所有已處理過的歌曲的 std::map 進(jìn)行循環(huán)實(shí)現(xiàn)的。那么，如果有個(gè) for-each 循環(huán)能在不同的線程上運(yùn)行每次迭代就好了。結(jié)果還真有！C++17 中的std::for_each（https://en.cppreference.com/w/cpp/algorithm/for_each）可以指定 ExecutionPolicy，通過它可以讓循環(huán)在不同的線程上執(zhí)行。然后是壞消息：這個(gè)標(biāo)準(zhǔn)還沒有被 gcc 完全支持。

所以我搜索了一些 for_each 的實(shí)現(xiàn)，最后在一個(gè) stackoverflow 的問題下（https://stackoverflow.com/questions/40805197/parallel-for-each-more-than-two-times-slower-than-stdfor-each）找到了一個(gè)。這個(gè)問題提到了一個(gè)從《C++Concurrency in Action》一書中的實(shí)現(xiàn)方案，我不確定這段代碼的版權(quán)如何，所以不能直接復(fù)制到 Brad 中，但我可以用它做一些測試以便進(jìn)行測量。

這個(gè)方法能把速度提高到 1897 倍，或者說大約 8700 首歌曲/秒（1000 首歌曲需要處理大約57秒。很不錯(cuò)，是吧?。?/p>

6.第二次并行嘗試

我需要找個(gè)我能用的并行版本的 for_each。幸運(yùn)的是，最終我發(fā)現(xiàn) gcc 包含了 C++ 標(biāo)準(zhǔn)庫中部分算法的實(shí)驗(yàn)性并行實(shí)現(xiàn)，其中包含了__gnu_parallel::for_each（https://gcc.gnu.org/onlinedocs/libstdc++/manual/parallel_mode_using.html，文檔頁面上還有更多的并行算法）。只需要鏈接 openmp 庫就可以了。

所以我修改了代碼，結(jié)果遇到一個(gè)問題：雖然我調(diào)用了 __gnu_parallel::for_each 但每次測試時(shí)發(fā)現(xiàn)它只會(huì)串行執(zhí)行！花了點(diǎn)功夫才找出原因，但閱讀 gcc 關(guān)于 __gnu_parallel::for_each 的實(shí)現(xiàn)后，我注意到它需要一個(gè)隨機(jī)訪問迭代器（http://www.cplusplus.com/reference/iterator/RandomAccessIterator/），但我讓它在 std::map 上迭代，而 map 結(jié)構(gòu)是雙向迭代器，不是隨機(jī)迭代器。

于是我修改了代碼，將指紋從 std::map<int,std::vector> 復(fù)制到 std:;vector<std::pair<int,std:vector>>，這樣 __gnu_parallel::for_each 就能用 8 個(gè)線程的線程池運(yùn)行了。

gcc 實(shí)現(xiàn)比 stackoverflow 上的實(shí)現(xiàn)更快，速度是 2442 倍，約 11200 首歌曲/秒，1000 首歌曲只需 44 秒。

7.很顯然我卻忘記了的重要改進(jìn)

在檢查 Bard 的編譯器時(shí)，我發(fā)現(xiàn)我沒有使用優(yōu)化速度的編譯器開關(guān)！于是我給編譯器加上了 -Ofast-march=native -mtune=native -funroll-loops，就這么簡單。猜猜發(fā)生了什么……

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

8.免費(fèi)得到的 Tumbleweed 的改進(jìn)

我開發(fā)所用的系統(tǒng)里運(yùn)行了 openSUSETumbleweed，你們估計(jì)知道，它是個(gè)非常好用的滾動(dòng)發(fā)布的 Linux 發(fā)行版。有一天我在做測試時(shí)，Tumbleweed 把編譯器從 gcc 7.3 更新到了 gcc8.1。所以我覺得我應(yīng)該再測試一下。

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

9.最終的優(yōu)化

我還沒做的一個(gè)非常明顯的優(yōu)化就是把 map 換成 vector，這樣就無需每次調(diào)用 for_each 之前進(jìn)行轉(zhuǎn)換了。而且，vector 能提前分配空間，由于我知道在整個(gè)算法結(jié)束時(shí) vector 的最終大小，因此我修改了代碼，以便事先分配空間。

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

結(jié)論

從這次經(jīng)歷中得到的一些值得記錄的經(jīng)驗(yàn)：

• 花點(diǎn)時(shí)間優(yōu)化代碼，會(huì)物有所值。

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