堆分配如何傷害硬件緩存命中率？

Question

我已經做了一些測試來調查堆分配和硬件緩存行爲之間的關係。實證結果具有啓發性，但也可能具有誤導性，特別是在不同的平臺和複雜/不確定性用例之間。

我感興趣的有兩種情況：批量分配（實現自定義內存池）或隨後的分配（信任os）。

下面是C++

//Consequent allocations 
for(auto i = 1000000000; i > 0; i--) 
    int *ptr = new int(0); 
    store_ptr_in_some_container(ptr); 

////////////////////////////////////// 

//Bulk allocation 
int *ptr = new int[1000000000]; 
distribute_indices_to_owners(ptr, 1000000000); 

我的問題是這兩個例子分配測試：

• 當我遍歷所有的人都爲只讀操作，如何將緩存中 內存CPU可能會自行劃分？儘管經驗性的結果（通過批量提供可見的性能提升），但當其他一些相對非常小的批量分配覆蓋了先前分配的緩存時會發生什麼？

• 爲了避免代碼膨脹並保持代碼的可讀性，將二者混合起來是否合理？

• std::vector,std::list,std::map,std::set哪裏有這些概念？

Answer 1

通用堆分配器有一組難題需要解決。它需要確保釋放的內存可以被回收，必須支持任意大小的分配並強烈避免堆碎片。

這將始終包括額外開銷爲每個分配，簿記分配器需要。至少它必須存儲塊的大小，以便在分配釋放時可以正確回收它。幾乎總是一個偏移量或指向堆段中下一個塊的指針，分配大小通常比請求的大，以避免分段問題。

這個開銷當然會影響緩存效率，當元素很小時，即使你從不使用它，你也無法幫助它進入L1緩存。當你在一個大的分量中分配數組時，你有每個數組元素的開銷零開銷。而且你很難保證每個元素都在內存中相鄰，所以按順序迭代陣列的速度將與內存子系統所能支持的速度一樣快。

不是通用分配器的情況，分配非常少，開銷可能是100％到200％。當程序運行一段時間並重新分配數組元素時，不能保證順序訪問。值得注意的是你的大數組無法支持的操作，所以要小心，不要自動假定分配長時間不能釋放的巨型數組一定更好。

所以是的，在這種人爲的情況下，你很可能會在大陣中處於領先地位。

從引用的集合類列表中劃去std :: list，它的緩存效率非常差，因爲下一個元素通常位於內存中的完全隨機位置。std :: vector是最好的，只是一個引擎蓋下的數組。 std :: map通常用紅黑樹完成，儘可能合理地完成，但你使用的訪問模式當然重要。 std :: set也一樣。