在緩存行中存儲了多少數組？

Question

#include <iostream> 
#include <stdint.h> 

using namespace std; 

struct UIContainer { 
    uint16_t x, y; //Position on the screen 
    uint16_t h, w; //Height and width of the UIContainer 
    uint16_t color; //Color, rgba such as 0xFF000000 & color is red, 0x00FF0000 is green, 0x0000FF00 is blue, 0x000000FF is alpha 
    uint16_t ID; //Unique ID of the ui container  
}; //16 bytes big 


void drawUI(UIContainer _container, SDL_Renderer* _renderer) { 
    SDL_Rect rect {.x = _container.x, .y = _container.y, .h = _container.h, .w = _container.w } 
    uint8_t r = color & 0xFF000000; 
    uint8_t g = color & 0x00FF0000; 
    uint8_t b = color & 0x0000FF00; 
    uint8_t a = color & 0x000000FF; 

    SDL_SetRenderDrawColor(_renderer, r, g, b, a); 
    SDL_RenderFillRect(_renderer, &rect); 
} 

int main() 
{ 
    UIContainer UIContainers[1024]; //16 * 1024 is 16384 bytes = 16 kilobytes 
    SDL_Renderer* renderer; //Pretend it is initialized 

    //Draw all the UI 
    int i = 0; 
    for(i; i < 1024; ++i) { 
     drawUI(_container, renderer); 
    } 

    return 0; 
} 

我決定嘗試瞭解數據本地化以及如何提高緩存的利用率。假設L1緩存爲64 KB，我認爲整個UIContainer陣列將被加載到緩存中是正確的，因爲16KB小於64KB？如果緩存行是128字節，那麼每行8個UIContainer塊？

據我所知，當緩存未命中時，會發生緩存未命中。這是否也適用於緩存行？例如，我在容器[3]上運行，然後我想跳到容器[100]，這會導致緩存未命中，因爲它必須跳至緩存行容器[100]所在的位置。

最後，假設我exctracted所有UIContainer的內部零件到自己單獨的陣列，這樣的代碼現在的樣子：

#include <iostream> 
#include <stdint.h> 

using namespace std; 

struct location { 
    uint16_t x, y; //Position on the screen 
}; //4 bytes 

struct size { 
    uint16_t h, w; //Height and width of the UIContainer 
}; //4 bytes 

struct color { 
    uint32_t color; //Color, rgba such as 0xFF000000 & color is red, 0x00FF0000 is green, 0x0000FF00 is blue, 0x000000FF is alpha 
} //4 bytes 

struct UIContainer { 
    uint32_t ID; //Unique ID of the ui container  
}; //4 bytes 


void drawUI(location l, size s, color c, SDL_Renderer* _renderer) { 
    SDL_Rect rect {.x = l.x, .y = l.y, .h = s.h, .w = s.w } 
    uint8_t r = c & 0xFF000000; 
    uint8_t g = c & 0x00FF0000; 
    uint8_t b = c & 0x0000FF00; 
    uint8_t a = c & 0x000000FF; 

    SDL_SetRenderDrawColor(_renderer, r, g, b, a); 
    SDL_RenderFillRect(_renderer, &rect); 
} 

int main() 
{ 
    UIContainer UIContainers[1024]; //4 * 1024 is 4048 bytes = 4 kilobytes 
    location _location[1024]; //4 KB 
    size _size[1024];   //4KB 
    color _color[1024];   //4KB 
    //////////////////////////////////////// 16 KB Total 



    SDL_Renderer* renderer; //Pretend it is initialized 

    //Draw all the UI 
    int i = 0; 
    for(i; i < 1024; ++i) { 
     drawUI(_location[i], _size[i], _color[i], renderer); 
    } 

    return 0; 
} 

這會導致高速緩存未命中？我不這麼認爲，因爲_location []，_size []和_color []都在緩存中，並且線性訪問？或者我錯過了什麼？

Answer 1

存儲在處理器緩存中的數組量取決於數組的大小（以字節爲單位）以及處理器的數據緩存和來自其他結構的任何剩餘數據的容量。

對不起，但沒有標準的數據高速緩存大小。就此而言，並不要求所有平臺都有數據緩存。

通常，對同一組數據執行許多數學運算時，數據緩存纔是重要的。例如，通過數組搜索不會證明數據緩存的使用是合理的。數據可能被加載並且只有一個通過。其他操作（如數據平滑，快速傅立葉變換和矩陣旋轉）涉及多個數據訪問。性能提升在數據的第一次傳遞之後進入。

最好的方法是分析你現在的代碼，寫下平均運行時間。更改您的代碼以更好地使用數據緩存。再次輪廓。將結果與第一個（原始執行）進行比較。

我在一個程序中更改了數據的佈局，以實現更多的數據緩存友好性，並將性能提高了30％。

編輯1：
爲了回答這個問題，每標題中，存儲在一個高速緩存線的數據的量是該程序正在訪問的量。一些處理器可能獲取更多，有些可能不會。取決於緩存中已有的內容，處理器的緩存加載算法，緩存行的容量以及數據緩存的容量。

Answer 2

第一

struct UIContainer { 
    uint16_t x, y; //Position on the screen 
    uint16_t h, w; //Height and width of the UIContainer 
    uint16_t color; //Color 
    uint16_t ID; //Unique ID of the ui container 
}; //16 bytes big 
static_assert(sizeof(struct UIContainer) == 12, "12 hmm not the case"); 
static_assert(sizeof(struct UIContainer) == 16, "16 hmm not the case"); // fails, because the last 2 should be uint32_t??? 

首先第一件事情我已經決定嘗試和學習有關數據本地化，以及如何 增加緩存的利用率。假設L1緩存爲64 KB， 我認爲整個UIContainer陣列將被加載到緩存中是不對的，因爲16KB小於64KB？

您的UIContainer是一個自動變量，元素沒有構造函數，因此數組不會自動加載到緩存中。

• 如果它是全局的，容器或元素有一個構造函數，那麼它將被初始化，因此在初始化過程中被加載到緩存中。
• 如果它已經被初始化了，它可能已經被初始化之後但是在你的代碼之前運行的代碼衝出緩存。

而且，如果高速緩存行是128字節，這將是每行8個UIContainer塊？

• 如果你有一個128個字節的緩存行
• 的容器是16個字節
• 和它們對齊到容器的大小，即。 16字節

那你每個緩存行就有8個容器。

據我所知，當某些東西不是 目前在緩存中發生緩存未命中。這是否也適用於緩存行？ 例如，我正在容器[3]上運行，然後我想跳到容器[100]的 ，這會導致緩存未命中，因爲它必須跳過 到緩存行容器[100]所在的位置。

緩存由緩存行組成，緩存行是主內存的副本。當你閱讀關於加載緩存行的信息時，它確實將數據加載到緩存行中，因爲它們是緩存的物理部分。

• 緩存缺失是指緩存中沒有緩存行包含請求數據的地址。
• 緩存然後請求下一個較低的緩存或主內存轉發數據。
• 使用DDR3的主內存通常會發送8 * 8個字節，這也是典型的緩存行大小！具有128字節的高速緩存行大小會導致它在連續地址上產生2個突發。
• 內存和更低的緩存真的很喜歡連續的地址訪問，它提供了最高的通過量。
• L1緩存在隨機訪問方面與流媒體一樣好。

假設只有你的程序運行在這個處理器上：

• 你會得到一個最小緩存強制缺失等於觸及的高速緩存行的數量。因爲你的數據都不會在緩存中。
• 如果您訪問的緩存行數超過緩存容量，您將獲得很多容量錯失。
• 此外，如果您訪問相同的地址％CacheLineSize超過緩存時間的關聯性，您將獲得衝突錯過。爲了您的64K緩存，你將最有可能有8方式或16的方式作爲緩存是最有可能分爲頁面大小（4096個字節）件，在這種情況下，16

這會導致高速緩存未命中？我不認爲它會，因爲 _location []，_size []和_color []都在緩存中，並被線性訪問？或者我錯過了什麼？

你從未知道的東西在緩存中，但如果你最近訪問它，它是有更高的可能性，這就是所謂的空間和時間局部性。

如果您測量/分析它，那麼您只能說哪一個是最好的，然後可以在代碼中做一些細微的改變。

當你流的數據就像在過去的代碼，緩存一般是幸福的，但這裏有一些疑難雜症

• 你正在服用3個不同的數據源（陣列），許多架構只支持2預取一次流。
• 對於您的小例子，應該沒有區別，一旦您的活動數據集的大小超過L1數據緩存大小，您將受到嚴重打擊。
• 由於所有的訪問實際上是在不同高速緩存行級別（和內存）之間的高速緩存行大小，因此使用一小部分高速緩存行成本與全部使用它相同。 在您的兩個例子
  • 到較低級高速緩存的任何訪問將是很好的方案將在高速緩存行，用一切除了的ID，這可能使第二次程序運行速度更快，因爲它需要訪問25緩存行少了百分之幾，但在最惡劣的情況下對其進行測量之前無法確定。
  • 使用數組而不是鏈接列表通常對任何程序都有很大的改進，所以不要改變它。

上caches

更多血淋淋的細節我還沒有看到任何128個字節的緩存行，但後來我又看到大多英特爾和AMD。

Answer 3

當您第一次訪問數據時，您總會遇到緩存未命中。之後，如果數據仍在緩存中，則取決於緩存的特性（緩存和緩存行大小，關聯性等）和內存訪問模式（線性，隨機等）。一般來說，最好將讀取的數據彼此靠得很近，以便儘可能在一個緩存行中讀取儘可能多的有用數據。例如，您可以線性訪問3個數組（_location，_size，_color），但從高速緩存的角度來看，使用交錯數據格式會更有效，在這種格式中，您有一個位置，大小和顏色數據交錯排列的單個數組其他。理論上講，在非交錯和交錯的情況下，你應該得到相同數量的高速緩存未命中，你的drawUI（）函數可能會導致一些數據從高速緩存中被驅逐出來，或者一些其他在後臺運行的進程可能會刷新數據從緩存中。另外需要記住的一點是，處理器會嘗試預測您的訪問模式並預取數據以緩存以避免內存停頓。這就是說，你需要考慮增加緩存一致性的潛在增加的複雜性是否真的值得。如果你有一些非常高的性能循環，對性能有很大的影響，當然。但在很多情況下，它並沒有給你帶來太多的收益，不值得付出的努力和增加的複雜性來擔憂太多。有些人會告訴你配置文件，然後決定如果看起來有必要優化緩存。然而，我們在現實世界中開發軟件的許多人並沒有多次寫相同的算法，並且根據我們的經驗不得不根據教育猜測來決定它的重要性。所以雖然過早的優化是萬惡的根源，但遲來的悲觀是不好的。