多線程讀內存變慢如何解決？

01-13

目前正在開發一個聽歌識曲的項目，但是遇到一個很嚴峻的問題：多線程檢索的速度下降了接近7倍！
首先說一下演算法流程：
從用戶獲取錄製的音頻（比如1秒長），然後計算提取指紋（幾千個指紋，每個指紋是一個int型數字）；
然後每一個指紋都訪問指紋庫（內存），指紋庫是一個倒排索引列表（key-value），索引key是每一個指紋，value是一個列表，列表每個元素是&<音樂id，該指紋在音樂中的出現位置&>；
訪問完指紋庫之後構造一個每首音樂的正排列表，存放指紋的出現時間；

最後對指紋進行排序，出現次數最多的那首音樂被認為是正確音樂。
ps
0、如果上述描述不清晰，請參考如下的問題模型（與上述問題相近）：
處理每個請求時，會涉及到數萬次查共享只讀表、改本線程的統計表（全部是內存表），不涉及鎖、磁碟IO。針對24核機器，如果啟動20個線程，每個線程處理單個請求時間變為原來的7倍。
1、所有數據都在內存，不涉及磁碟IO。
2、關於聽歌識曲，可參考：基於指紋的音樂檢索。
現在遇到的性能問題：

單線程測的時候實時率大約有0.3（即0.3秒處理完一個請求），最近用20線程進行單機的壓力測試（機器24核），結果實時率成了2（即每個請求需要2秒）！
我認為：
訪問指紋庫只是一個讀操作，用不到加鎖；除此之外每個線程都只訪問自己的內存空間，不應該會變得如此慢（0.3秒變2秒）。
目前初步分析的原因是內存帶寬太低和每個線程的亂序訪問，但是這兩個問題貌似都不容易解決。所以在此求教大家，是否有好的解決方案？
====================================================================
補充：
檢索過程其實和搜索引擎一樣，音樂指紋就和搜索引擎中的關鍵詞等價，指紋庫就等價於搜索引擎的後台網頁庫。指紋庫的構造和搜索引擎的網頁庫也是一樣，採用倒排索引形式。如下圖：

只不過指紋都是一個int型的整數（圖示只佔用了24位），包含的信息太少，所以需要提取很多個指紋完成一次匹配，大約是每秒幾千個的樣子。每獲得一個指紋都需要訪問指紋庫獲得對應的倒排列表，然後再根據音樂id構造一個正排列表，用來分析哪首音樂匹配上，如下圖：
最終的結果就是排序結果最高的音樂。
目前指紋庫大約60G，是對25w首歌提取指紋的結果。每一個指紋對應的倒排列表長度不固定，但是有上限5000。正排列表的音樂個數也是25w，每一首音樂對應的最長時間差個數為8192。單次檢索的時候會生成大約5000個左右的指紋（甚至更多）。
PS:昨天採用內存帶寬更高的伺服器進行測試,實時率降為1.2左右,但是還是無法和單線程的0.3匹配. 昨天看大家的回答和自己網上搜索,歸結為三個嘗試方向:1. 物理內存直接訪問,避免虛擬地址到物理地址的轉換;2. 大頁內存,將pagesize調高,減小頁表大小;3. 檢查線程是否會在不同核間切換. 目前本人對上述三種方法都不了解,還希望大家給指出一條明路……

目前已經測試通過修改線程親和性屬性來讓線程在固定核上運行，沒有效果。

補充：

不少人都提出一個可能的原因是False sharing，但是我認為不是這個原因。這是因為False sharing出現的原因在於多個線程訪問共享數據時可能出現一個寫一個讀，然後導致cache缺失。但是在我的項目中，多線程的目的只是為了響應更多用戶的請求，並沒有對共享數據進行修改操作。多線程之間唯一共享的就是指紋庫，但是也是只讀的，讀完之後每個線程都在自己的內存中進行操作，所以不存在False sharing問題。

採用內存帶寬更高的伺服器測試也可以說明這個問題，因為實時率由2.0變為1.2，說明瓶頸完全在帶寬上。

雖然不存在False sharing問題，但是cache命中率確實很低，這和該項目具體的實現流程相關，比較難以改進。

======================================================================

最近一直沒有停止對代碼進行優化，終於在上周獲得明顯改進。沒想到最影響性能的居然是-pg的編譯選項，多線程情況下去掉該選項會獲得大約5倍的性能提升。實在是對不住關注該問題的朋友了！在去掉-pg選項之後，再利用大頁內存進行優化，又可以獲得大約50%的性能提升，一個結果如下：

通過上述兩種方法的優化，性能終於達到要求。關於大頁內存的使用可參考：大頁內存(HugePages)在通用程序優化中的應用

查查false sharing？

或者你貼一個能復現現象的代碼。

感覺你做壓力測試的時候已經把內存帶寬撐滿了。一次請求查5000個指紋，每個指紋帶5000首歌的倒排表，那就是25M，每首歌8個位元組的話就是200MB。對這200MB進行排序的話，假設需要讀取3倍數據量，那就是600MB。讀完再對每首歌進行一次匹配，估計又用掉600MB左右，於是每個請求需要1~2GB的內存帶寬，10次請求就是20GB，這已經接近內存帶寬的極限了。

即使上面的估計有誤差，那也就是三五倍的差別，數量級應該是沒錯的，所以再怎麼優化也就是10 QPS到50 QPS的差距了。。。

單線程的時候3個請求每秒，20線程的時候變到0.5個每秒，很可能就是因為內存帶寬已經滿了，於是每個請求都需要等待更長的時間才能完成

這種問題光說演算法不行的，性能問題這種東西，有很可能是一個很小的問題就會引起性能下降。理論上如果請求都是讀請求而且讀請求之間沒有鎖的話，性能不會下降這麼多。感覺最大的可能就是請求之間有共享資源需要加鎖，如果是讀寫請求，很有可能false sharing，可以通過工具對比單線程與多CPU cache的命中率

如果是numa架構，可以嘗試線程跑在在固定的cpu上，盡量訪問local memory,減少remote memory的訪問

指紋庫是否提前讀取於內存當中否則在檢索的時候是否存在IO操作

如果是的話這塊將消耗大量的時間幾千個指紋 20個線程....