c++ - 缓存行中存储了多少数组？

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 block ？

据我了解，当某些内容当前不在缓存中时，就会发生缓存未命中。这是否也适用于缓存行？例如，我在 container[3] 上操作，然后我想向前跳到 container[100]，这会导致缓存未命中，因为它必须跳到 container[100] 所在的任何缓存行？

最后，假设我将 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

要事第一

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???

I've decided to try and learn about data localization and how to increase the utilization of the cache. Assuming the L1 cache is 64 KB, I am right to assume that the entire array of UIContainer will be loaded into cache, since 16KB is less than 64KB?

您的 UIContainer 是一个自动变量，元素没有构造函数，因此数组不会自动加载到缓存中。

• 如果它是全局的，容器或元素有一个构造函数，那么它就会被初始化，因此在初始化期间加载到缓存中。
• 如果它较早初始化，它也可能已被在初始化之后但在您的代码之前运行的代码从缓存中清除。

And if the cache line is 128 Bytes, that would be 8 UIContainer blocks per line?

• 如果你有一个 128 字节的缓存行
• 容器是 16 字节
• 和 它们与容器大小对齐，即。 16 字节

那么每个缓存行将有 8 个容器。

As I understand it, a cache miss happens when something is not currently in cache. Does this also apply for cache lines? For example, I am operating on container[3] and then I want to skip ahead to container[100], that would cause a cache miss because it has to skip to whatever cache line container[100] is located in?

缓存由缓存行组成，缓存行是主内存的拷贝。当您阅读有关加载缓存行的内容时，它实际上是将数据加载到 缓存行中，因为它们是缓存的物理部分。

• 缓存未命中是指缓存中没有缓存行包含所请求数据的地址。
• 缓存然后请求下一个较低的缓存或主内存转发数据。
• 带有 DDR3 的主内存通常会发送 8*8 字节，这也是典型的缓存行大小!具有 128 字节缓存行大小会导致它在连续地址上产生 2 个突发。
• 内存和低级缓存非常喜欢连续地址访问，从而提供最高的吞吐量。
• L1 缓存在随机访问方面的表现几乎与流媒体一样好。

假设只有您的程序在此处理器上运行:

• 您将得到最少的缓存强制未命中，等于接触的缓存行数。因为您的任何数据都不会在缓存中。
• 如果您访问的缓存行多于缓存可以容纳的数量，您将得到那么多容量未命中。
• 此外，如果您访问同一地址 % CacheLineSize 的次数超过缓存的关联次数，您将冲突未命中。对于您的 64K 缓存，您很可能有 8 路或 16 路缓存，因为缓存很可能分为页面大小(4096 字节) block ，在本例中为 16。

Would this cause cache misses? I wouldn't think it would, since _location[], _size[] and _color[] are all in the cache, and being accessed linearly? Or am I missing something?

您永远不知道缓存中有什么东西，但如果您最近访问过它，它存在的可能性就更高，这称为空间和时间局部性。

只有在测量/剖析它时，您才能说出哪个是最好的，然后可以对代码进行微小的更改来扭转它。

当你像上一个代码一样流式传输数据时，缓存通常很满意，但这里有一些问题

• 你正在获取 3 个不同的数据源(数组)，许多架构一次只支持 2 个预取流。
• 对于您的小示例，应该没有区别，一旦您的事件数据集的大小超过 L1 数据缓存大小，您将受到严重打击。
• 因为所有访问实际上都在不同缓存行级别(和内存)之间的缓存行大小中，使用一小部分缓存行的成本与使用全部缓存行的成本相同。
  • 在您的两个示例中，对较低级别缓存的任何访问都将是好的，因为程序将使用缓存行中的所有内容除了 ID，这可能成为第二个程序运行速度更快，因为它需要访问的缓存行减少 25%，但在最坏情况下进行测量之前您无法确定。
  • 使用数组而不是链表通常对任何程序都是一个很大的改进，所以不要改变它。

关于 caches 的更多细节

我还没有看到任何 128 字节的缓存行，但我又一次看到了 Intel 和 AMD。