430
由一道淘寶麵試題到False sharing問題
今天在看淘寶之前的一道麵試題目，內容是
在高性能服務器的代碼中經常會看到類似這樣的代碼：
typedef union
{
erts_smp_rwmtx_t rwmtx;
byte cache_line_align_[ERTS_ALC_CACHE_LINE_ALIGN_SIZE(sizeof(erts_smp_rwmtx_t))];
}erts_meta_main_tab_lock_t;
erts_meta_main_tab_lock_t main_tab_lock[16];
請問其中用來填充的cache_line_align的作用是？
之前有學習到c語言中宏align是內存補齊的作用，那這個不就是cache line補齊？但是啥是cache line？？為啥有這麼一步？
1.首先，什麼是cache line？
CPU處理指令時，由於“Locality of Reference”原因，需要決定哪些數據需要加載到CPU的緩存中，以及如何預加載。因為不同的處理器有不同的規範，導致這部分工作具有不確定性。在加載的過程中，涉及到一個非常關鍵的術語：cache line。
cache line是能被cache處理的內存chunks，chunk的大小即為cache line size，典型的大小為32，64及128 bytes. cache能處理的內存大小除以cache line size即為cache line。
了解了cache line，然後再熟悉一下cpu上cache的一些策略
2.cpu上cache的策略
cache entry (cache條目)
包含如下部分
1) cache line : 從主存一次copy的數據大小)
2) tag : 標記cache line對應的主存的地址
3) falg : 標記當前cache line是否invalid, 如果是數據cache, 還有是否dirty
cpu訪問主存的規律
1) cpu從來都不直接訪問主存, 都是通過cache間接訪問主存
2) 每次需要訪問主存時, 遍曆一遍全部cache line, 查找主存的地址是否在某個cache line中.
3) 如果cache中沒有找到, 則分配一個新的cache entry, 把主存的內存copy到cache line中, 再從cache line中讀取.
cache中包含的cache entry條目有限, 所以, 必須有合適的cache淘汰策略
一般使用的是LRU策略.
將一些主存區域標記為non-cacheble, 可以提高cache命中率, 降低沒用的cache
回寫策略
cache中的數據更新後,需要回寫到主存, 回寫的時機有多種
1) 每次更新都回寫. write-through cache
2) 更新後不回寫,標記為dirty, 僅當cache entry被evict時才回寫
3) 更新後, 把cache entry送如回寫隊列, 待隊列收集到多個entry時批量回寫.
cache一致性問題
有兩種情況可能導致cache中的數據過期
1) DMA, 有其他設備直接更新主存的數據
2) SMP, 同一個cache line存在多個CPU各自的cache中. 其中一個CPU對其進行了更新.
3.為啥需要cache line 補齊呢？
讓我們先看一個例子，
舉例:
// 如下代碼在SMP環境下存在cache頻繁刷新問題
double sum=0.0, sum_local[NUM_THREADS];
#pragma omp parallel num_threads(NUM_THREADS)
{
int me = omp_get_thread_num();
sum_local[me] = 0.0;
#pragma omp for
for (i = 0; i < N; i++)
sum_local[me] += x[i] * y[i];
#pragma omp atomic
sum += sum_local[me];
}
在做多線程程序的時候,為了避免使用鎖,我們通常會采用這樣的數據結構:根據線程的數目,安排一個數組, 每個線程一個項,互相不衝突. 從邏輯上看這樣的設計無懈可擊,但是實踐的過程我們會發現這樣並沒有提高速度. 問題在於cpu的cache line. 我們在讀主存的時候,數據同時被讀到L1,L2中去,而且在L1中是以cache line(通常64)字節為單位的. 每個Core都有自己的L1,L2,所以每個線程在讀取自己的項的時候, 也把別人的項讀進去, 所以在更新的時候,為了保持數據的一致性, core之間cache要進行同步, 這個會導致嚴重的性能問題. 這就是所謂的False sharing問題, 有興趣的同學可以wiki下.
解決方法很簡單:
把每個項湊齊cache line的長度,實現隔離.
|
1
2
3
4
5
6
7
8
|
typedef
union
{
erts_smp_rwmtx_t
rwmtx;
byte
cache_line_align__[ERTS_ALC_CACHE_LINE_ALIGN_SIZE(
sizeof(erts_smp_rwmtx_t))];
}
erts_meta_main_tab_lock_t;
或者
_declspec
(align(64)) int
thread1_global_variable;
__declspec
(align(64)) int
thread2_global_variable;
|
這就是為什麼在高性能服務器中到處看到cache_line_align, 號稱是避免cache的trash.
類似valgrind和intel vtune的工具可以做這個層次的性能微調.
最後更新：2017-04-03 16:49:04