应用程序的缓存友好设计
Cache Friendly Design of Applications
我已经完成了用 C++ 编写的 application，现在我必须深入研究代码并使其成为 cache-friendly。
阅读 presentation by Tony Albrecht 后，我很快意识到，我可以通过简单地应用设计阶段的原则，一次就把它做好。
另一篇由 Ulrich Drepper 撰写的标题为 What Every Programmer Should Know About Memory 的论文有很多要点，基本上告诉像我这样的开发人员要注意编写正确的内存布局以实现缓存友好。
但是，这感觉违反直觉，因为：
- 一般来说，从内存布局的角度思考并不自然。
- 根据集合和行来布置代码和数据并不自然。
- 根据具有属性和操作的 object 来思考是很自然的。
一个很好的例子，当我坐下来写一个自定义分配器时，我很快就会遇到这个例子，有两个结构将由分配器处理，如下所示。
另请注意，一旦线程工作者释放了一个元素，就必须使用相同的元素，如此继续下去。
typedef struct
{
OVERLAPPED Overlapped;
WSABUF DataBuf;
CHAR Buffer[DATA_BUFSIZE];
byte *LPBuffer;
vector<byte> byteBuffer;
DWORD BytesSEND;
DWORD BytesRECV;
} PER_IO_OPERATION_DATA, *LPPER_IO_OPERATION_DATA;
typedef struct
{
SOCKET Socket;
} PER_HANDLE_DATA, *LPPER_HANDLE_DATA;
请注意 WSABUF.buf 和 vector 可能是一个挑战，它们将如何在内存中布局。 WSABUF.buf 并且向量缓冲区分配是动态的，不适合固定大小的连续布局。我想必须为这种情况创建一个单独的分配器。
PER_HANDLE_DATA 很简单，可以很容易地以连续的方式布置。
我必须设置另一个用于存储 IsActive 的结构，以便将其放置在一个连续的块中，与 PER_IO_OPERATION_DATA 分开。
typedef struct {
bool isActive;
} IODATA_STAT, *LPIODATA_STAT
无论如何，我只是想得到一些反馈，为什么你必须在开始时知道缓存什么时候可以在编写应用程序后完成？
此外，关于 dynamic/fixed 缓冲区大小和指针，您对重组数据有何看法？
优化
关于过早的优化，我认为如果您可以在事后应用优化以响应探查器而无需在您的代码库中进行一系列级联更改，则为时过早。您必须在本地和非侵入性地公平地交换表示的喘息空间越大，您第一次就应该越少担心获得最佳表示。
因此，您首先要关注的关键是 界面设计 而不是实现，尤其是在构建大型软件时。在适当的抽象级别建模的良好、稳定的界面将允许您分析代码并将热点优化到碎片，而不会在整个代码中造成级联破坏：理想情况下只需对源文件进行一些调整。
生产力和可维护性仍然是开发人员最有价值的特征，除了最低级别的核心之外，绝大多数代码库都将取决于这些特征，而不是实现微观高效设计的能力更不用说任务的最佳算法了。现在的编程世界非常饱和且竞争激烈，能够快速开发出可维护应用程序的人通常是那些获胜并幸存下来以优化另一天的人。
如果您不使用探查器并且担心的不仅仅是广泛的算法复杂性，那么您绝对首先需要一个探查器。测量两次，优化一次。分析器会让您进行选择性的、离散的优化，这很重要，不仅可以让您第一次以更有价值的方式花费时间，而且可以确保您不会将整个代码库降级为维护噩梦.
内存布局
但撇开这个警告不谈：
1.一般来说，从内存布局的角度思考并不自然。
这里我推荐一点类C的思路。当你在职业生涯中面临更多热点时，它会自然而然地到来。在您的示例中，变长结构技巧变得非常有效。
struct PER_IO_OPERATION_DATA
{
...
byte byteBuffer[]; // size N
};
只需使用 malloc（或您自己的分配器）获取 PER_IO_OPERATION_DATA* 结构大小 + 使 byteButter 边足够大所需的额外 N 字节。由于您拥有 C++，您可以使用这种低级结构作为符合 RAII 的安全 class 背后的实现细节，在调试版本中应用必要的边界检查断言，具有异常安全性，等等向前。在 C++ 中，至少要尝试这样做：如果您在任何地方都需要不安全的低级位和字节操作代码，请将其设为隐藏在 public 接口之外的非常私有的实现细节。
这通常是内存局部性的第一步：使用堆识别对象的运行时大小的聚合成员，并将它们与对象本身融合到一个连续的块中。
当您尝试针对局部性进行优化（以及消除 new/delete/malloc/free 热点）时，标准中缺少的另一种有用的通用容器类型类似于 std::vector，具有静态已知的 "common case"尺寸。基本示例：
struct Usually32ElementsOrLess
{
char buf[32];
char* ptr;
int num_elements;
};
初始化结构使 ptr 指向 buf 除非元素数超过固定大小 (32)。在这种极少数情况下，使 ptr 指向堆分配的动态数组。通过 ptr 而不是 buf 访问结构，并确保实现正确的复制构造函数。
使用 C++，如果您喜欢使用模板参数来确定固定大小，您可以将它变成一个通用的 STL 兼容容器，如果您将成员引入到除了大小之外，还要跟踪当前内存容量。
拥有这种经过充分测试的结构，尤其是成熟的通用 STL 形式，将真正帮助您更多地利用堆栈并从日常代码中获得更多的内存局部性，而无需比使用 std::vector 更耗时或更冒险的事情。它适用于大多数情况下，数据大小在常见情况下有上限，而堆保留用于那些罕见情况下的异常情况。
2。根据集合和行来布置代码和数据并不自然。
确实，从组织聚合和访问模式以对齐和适合缓存行的角度来看，这是非常不自然的。我建议你只把这种想法留给最关键的关键热点。
3。从具有属性和行为的对象的角度来思考是很自然的。
这不会妨碍其他两件事。那是 public 界面设计，您理想的 public 界面不会将这些低级优化细节泄漏到使用该界面的客户端（除非它只是用作构建块的低级数据结构用于更高级别的设计）。
回到界面设计，如果你想在不破坏界面设计的情况下为高效的表现形式优化留出更多空间，跨步设计将大有帮助。查看 OpenGL API 以及它如何支持各种传递事物表示的方式。例如，它不假设顶点位置存储在与顶点法线分开的连续内存块中。因为它在设计中使用了步幅，所以顶点法线可以与顶点位置交错，也可能不交错。这无关紧要，也不需要更改界面，因此它为试验内存布局留出了空间，而不会破坏任何东西。
在 C++ 中，您甚至可以创建类似 StrideIterator<T>(ptr, stride_size) 的内容，以便更轻松地传递事物，并且 return 在设计中可以从更改传递事物的内存布局中获益，并且 return return四处转转。
更新（固定分配器）
既然你对自定义分配器感兴趣，试试这个大小：
#include <iostream>
#include <cassert>
#include <ctime>
using namespace std;
class Pool
{
public:
Pool(int element_size, int num_reserve)
{
if (sizeof(Chunk) > element_size)
element_size = sizeof(Chunk);
// This should use an aligned malloc.
mem = static_cast<char*>(malloc((num_reserve+1) * element_size));
char* ptr = static_cast<char*>(mem);
free_chunk = reinterpret_cast<Chunk*>(ptr);
free_chunk->next = 0;
Chunk* last_chunk = free_chunk;
for (int j=1; j < num_reserve+1; ++j)
{
ptr += element_size;
Chunk* chunk = reinterpret_cast<Chunk*>(ptr);
chunk->next = 0;
last_chunk->next = chunk;
last_chunk = chunk;
}
}
~Pool()
{
// This should use an aligned free.
free(mem);
}
void* allocate()
{
assert(free_chunk && free_chunk->next && "Reserve memory exhausted!");
Chunk* chunk = free_chunk;
free_chunk = free_chunk->next;
return chunk->mem;
}
void deallocate(void* mem)
{
Chunk* chunk = static_cast<Chunk*>(mem);
chunk->next = free_chunk;
free_chunk = chunk;
}
template <class T>
T* create(const T& other)
{
return new(allocate()) T(other);
}
template <class T>
void destroy(T* mem)
{
mem->~T();
deallocate(mem);
}
private:
union Chunk
{
Chunk* next;
// This should be max aligned.
char mem[1];
};
char* mem;
Chunk* free_chunk;
};
static double sys_time()
{
return static_cast<double>(clock()) / CLOCKS_PER_SEC;
}
int main()
{
enum {num = 20000000};
Pool alloc(sizeof(int), num);
// 'Touch' the array to reduce bias in the testing.
int** elements = new int*[num];
for (int j=0; j < num; ++j)
elements[j] = 0;
for (int k=0; k < 5; ++k)
{
// new/delete (malloc/free)
{
double start_time = sys_time();
for (int j=0; j < num; ++j)
elements[j] = new int(j);
for (int j=0; j < num; ++j)
delete elements[j];
cout << (sys_time() - start_time) << " seconds for new/delete" << endl;
}
// Branchless Fixed Alloc
{
double start_time = sys_time();
for (int j=0; j < num; ++j)
elements[j] = alloc.create(j);
for (int j=0; j < num; ++j)
alloc.destroy(elements[j]);
cout << (sys_time() - start_time) << " seconds for branchless alloc" << endl;
}
cout << endl;
}
delete[] elements;
}
我机器上的结果：
1.711 seconds for new/delete
0.066 seconds for branchless alloc
1.681 seconds for new/delete
0.058 seconds for branchless alloc
1.668 seconds for new/delete
0.06 seconds for branchless alloc
1.68 seconds for new/delete
0.057 seconds for branchless alloc
1.663 seconds for new/delete
0.065 seconds for branchless alloc
这是一个无分支池分配器。不安全但疯狂的快。它要求您提前预留最大内存量，因此最好将其用作分配器的构建块，分配器会进行分支并动态创建多个这些预留池。
我已经完成了用 C++ 编写的 application，现在我必须深入研究代码并使其成为 cache-friendly。
阅读 presentation by Tony Albrecht 后，我很快意识到，我可以通过简单地应用设计阶段的原则，一次就把它做好。
另一篇由 Ulrich Drepper 撰写的标题为 What Every Programmer Should Know About Memory 的论文有很多要点，基本上告诉像我这样的开发人员要注意编写正确的内存布局以实现缓存友好。
但是，这感觉违反直觉，因为：
- 一般来说，从内存布局的角度思考并不自然。
- 根据集合和行来布置代码和数据并不自然。
- 根据具有属性和操作的 object 来思考是很自然的。
一个很好的例子，当我坐下来写一个自定义分配器时，我很快就会遇到这个例子，有两个结构将由分配器处理，如下所示。
另请注意，一旦线程工作者释放了一个元素，就必须使用相同的元素，如此继续下去。
typedef struct
{
OVERLAPPED Overlapped;
WSABUF DataBuf;
CHAR Buffer[DATA_BUFSIZE];
byte *LPBuffer;
vector<byte> byteBuffer;
DWORD BytesSEND;
DWORD BytesRECV;
} PER_IO_OPERATION_DATA, *LPPER_IO_OPERATION_DATA;
typedef struct
{
SOCKET Socket;
} PER_HANDLE_DATA, *LPPER_HANDLE_DATA;
请注意 WSABUF.buf 和 vector 可能是一个挑战，它们将如何在内存中布局。 WSABUF.buf 并且向量缓冲区分配是动态的，不适合固定大小的连续布局。我想必须为这种情况创建一个单独的分配器。
PER_HANDLE_DATA 很简单，可以很容易地以连续的方式布置。
我必须设置另一个用于存储 IsActive 的结构，以便将其放置在一个连续的块中，与 PER_IO_OPERATION_DATA 分开。
typedef struct {
bool isActive;
} IODATA_STAT, *LPIODATA_STAT
无论如何，我只是想得到一些反馈，为什么你必须在开始时知道缓存什么时候可以在编写应用程序后完成？
此外，关于 dynamic/fixed 缓冲区大小和指针，您对重组数据有何看法？
优化
关于过早的优化，我认为如果您可以在事后应用优化以响应探查器而无需在您的代码库中进行一系列级联更改，则为时过早。您必须在本地和非侵入性地公平地交换表示的喘息空间越大，您第一次就应该越少担心获得最佳表示。
因此，您首先要关注的关键是 界面设计 而不是实现，尤其是在构建大型软件时。在适当的抽象级别建模的良好、稳定的界面将允许您分析代码并将热点优化到碎片，而不会在整个代码中造成级联破坏：理想情况下只需对源文件进行一些调整。
生产力和可维护性仍然是开发人员最有价值的特征，除了最低级别的核心之外，绝大多数代码库都将取决于这些特征，而不是实现微观高效设计的能力更不用说任务的最佳算法了。现在的编程世界非常饱和且竞争激烈，能够快速开发出可维护应用程序的人通常是那些获胜并幸存下来以优化另一天的人。
如果您不使用探查器并且担心的不仅仅是广泛的算法复杂性，那么您绝对首先需要一个探查器。测量两次，优化一次。分析器会让您进行选择性的、离散的优化，这很重要，不仅可以让您第一次以更有价值的方式花费时间，而且可以确保您不会将整个代码库降级为维护噩梦.
内存布局
但撇开这个警告不谈：
1.一般来说，从内存布局的角度思考并不自然。
这里我推荐一点类C的思路。当你在职业生涯中面临更多热点时，它会自然而然地到来。在您的示例中，变长结构技巧变得非常有效。
struct PER_IO_OPERATION_DATA
{
...
byte byteBuffer[]; // size N
};
只需使用 malloc（或您自己的分配器）获取 PER_IO_OPERATION_DATA* 结构大小 + 使 byteButter 边足够大所需的额外 N 字节。由于您拥有 C++，您可以使用这种低级结构作为符合 RAII 的安全 class 背后的实现细节，在调试版本中应用必要的边界检查断言，具有异常安全性，等等向前。在 C++ 中，至少要尝试这样做：如果您在任何地方都需要不安全的低级位和字节操作代码，请将其设为隐藏在 public 接口之外的非常私有的实现细节。
这通常是内存局部性的第一步：使用堆识别对象的运行时大小的聚合成员，并将它们与对象本身融合到一个连续的块中。
当您尝试针对局部性进行优化（以及消除 new/delete/malloc/free 热点）时，标准中缺少的另一种有用的通用容器类型类似于 std::vector，具有静态已知的 "common case"尺寸。基本示例：
struct Usually32ElementsOrLess
{
char buf[32];
char* ptr;
int num_elements;
};
初始化结构使 ptr 指向 buf 除非元素数超过固定大小 (32)。在这种极少数情况下，使 ptr 指向堆分配的动态数组。通过 ptr 而不是 buf 访问结构，并确保实现正确的复制构造函数。
使用 C++，如果您喜欢使用模板参数来确定固定大小，您可以将它变成一个通用的 STL 兼容容器，如果您将成员引入到除了大小之外，还要跟踪当前内存容量。
拥有这种经过充分测试的结构，尤其是成熟的通用 STL 形式，将真正帮助您更多地利用堆栈并从日常代码中获得更多的内存局部性，而无需比使用 std::vector 更耗时或更冒险的事情。它适用于大多数情况下，数据大小在常见情况下有上限，而堆保留用于那些罕见情况下的异常情况。
2。根据集合和行来布置代码和数据并不自然。
确实，从组织聚合和访问模式以对齐和适合缓存行的角度来看，这是非常不自然的。我建议你只把这种想法留给最关键的关键热点。
3。从具有属性和行为的对象的角度来思考是很自然的。
这不会妨碍其他两件事。那是 public 界面设计，您理想的 public 界面不会将这些低级优化细节泄漏到使用该界面的客户端（除非它只是用作构建块的低级数据结构用于更高级别的设计）。
回到界面设计，如果你想在不破坏界面设计的情况下为高效的表现形式优化留出更多空间，跨步设计将大有帮助。查看 OpenGL API 以及它如何支持各种传递事物表示的方式。例如，它不假设顶点位置存储在与顶点法线分开的连续内存块中。因为它在设计中使用了步幅，所以顶点法线可以与顶点位置交错，也可能不交错。这无关紧要，也不需要更改界面，因此它为试验内存布局留出了空间，而不会破坏任何东西。
在 C++ 中，您甚至可以创建类似 StrideIterator<T>(ptr, stride_size) 的内容，以便更轻松地传递事物，并且 return 在设计中可以从更改传递事物的内存布局中获益，并且 return return四处转转。
更新（固定分配器）
既然你对自定义分配器感兴趣，试试这个大小：
#include <iostream>
#include <cassert>
#include <ctime>
using namespace std;
class Pool
{
public:
Pool(int element_size, int num_reserve)
{
if (sizeof(Chunk) > element_size)
element_size = sizeof(Chunk);
// This should use an aligned malloc.
mem = static_cast<char*>(malloc((num_reserve+1) * element_size));
char* ptr = static_cast<char*>(mem);
free_chunk = reinterpret_cast<Chunk*>(ptr);
free_chunk->next = 0;
Chunk* last_chunk = free_chunk;
for (int j=1; j < num_reserve+1; ++j)
{
ptr += element_size;
Chunk* chunk = reinterpret_cast<Chunk*>(ptr);
chunk->next = 0;
last_chunk->next = chunk;
last_chunk = chunk;
}
}
~Pool()
{
// This should use an aligned free.
free(mem);
}
void* allocate()
{
assert(free_chunk && free_chunk->next && "Reserve memory exhausted!");
Chunk* chunk = free_chunk;
free_chunk = free_chunk->next;
return chunk->mem;
}
void deallocate(void* mem)
{
Chunk* chunk = static_cast<Chunk*>(mem);
chunk->next = free_chunk;
free_chunk = chunk;
}
template <class T>
T* create(const T& other)
{
return new(allocate()) T(other);
}
template <class T>
void destroy(T* mem)
{
mem->~T();
deallocate(mem);
}
private:
union Chunk
{
Chunk* next;
// This should be max aligned.
char mem[1];
};
char* mem;
Chunk* free_chunk;
};
static double sys_time()
{
return static_cast<double>(clock()) / CLOCKS_PER_SEC;
}
int main()
{
enum {num = 20000000};
Pool alloc(sizeof(int), num);
// 'Touch' the array to reduce bias in the testing.
int** elements = new int*[num];
for (int j=0; j < num; ++j)
elements[j] = 0;
for (int k=0; k < 5; ++k)
{
// new/delete (malloc/free)
{
double start_time = sys_time();
for (int j=0; j < num; ++j)
elements[j] = new int(j);
for (int j=0; j < num; ++j)
delete elements[j];
cout << (sys_time() - start_time) << " seconds for new/delete" << endl;
}
// Branchless Fixed Alloc
{
double start_time = sys_time();
for (int j=0; j < num; ++j)
elements[j] = alloc.create(j);
for (int j=0; j < num; ++j)
alloc.destroy(elements[j]);
cout << (sys_time() - start_time) << " seconds for branchless alloc" << endl;
}
cout << endl;
}
delete[] elements;
}
我机器上的结果：
1.711 seconds for new/delete
0.066 seconds for branchless alloc
1.681 seconds for new/delete
0.058 seconds for branchless alloc
1.668 seconds for new/delete
0.06 seconds for branchless alloc
1.68 seconds for new/delete
0.057 seconds for branchless alloc
1.663 seconds for new/delete
0.065 seconds for branchless alloc
这是一个无分支池分配器。不安全但疯狂的快。它要求您提前预留最大内存量，因此最好将其用作分配器的构建块，分配器会进行分支并动态创建多个这些预留池。