循环平铺。 如何选择块大小？
我正在尝试学习循环优化。 我发现循环平铺有助于使数组循环更快。 我尝试使用下面给出的两个代码块，有或没有循环阻塞，并测量两者的时间。 我大部分时间都没有发现明显的差异。 我测试了不同的块大小，但我不知道如何选择块大小。 如果我的方向错了，请帮助我。 实际上我发现没有块的循环工作速度快了很多倍。
一个。 随着阻止
int max = 1000000; int B = 100; for (i = 0; i < max; i += B) { for (j = i; j < (i + B); j++) { array[j] = 0; } } 湾 没有阻止
for (i = 0; i < max; i++) { array[i] = 0; }
所用时间：阻塞：经过时间 – 6997000 Nano Secs
没有阻止经过的时间 – 6097000 Nano Secs
正如这里所指出的，平铺是一种技术，用于在您处理缓存时将工作集保留在缓存中，以便享受内存延迟。 如果您在从未点击缓存后看到没有任何好处的情况下流式传输数据，那么平铺将没有用处。
您的示例循环以相同的顺序执行完全相同的工作，除了添加另一个分支并使分支模式稍微复杂一点（大多数预测器将能够应对它，它在任何方面都没有帮助）。
考虑以下示例 –
#include "stdlib.h" #include "stdio.h" #include #define MAX (1024*1024*32) #define REP 100 #define B (16*1024) int main() { int i,j,r; char array[MAX]; for (i = 0; i < MAX; i++) { // warmup to make things equal if array happens to fit in your L3 array[i] = 0; } clock_t t1 = clock(); // Tiled loop for (i = 0; i < MAX; i += B) { for (r = 0; r < REP; r++) { for (j = i; j < (i + B); j+=64) { array[j] = r; } } } clock_t t2 = clock(); // un-tiled loop for (r = 0; r < REP; r++) { for (i = 0; i < MAX; i+=64) { array[i] = r; } } clock_t t3 = clock(); printf ("Tiled: %f sec\n", (double)(t2 - t1) / CLOCKS_PER_SEC); printf ("Untiled: %f sec\n", (double)(t3 - t2) / CLOCKS_PER_SEC); printf ("array[0] = %d\n", array[0]); // to prevent optimizing out all the writes }
两个循环都在进行相同的访问（64byte跳转是通过使用每个缓存行一次来强调缓存，并防止IPC和指令调度成为瓶颈）。
平铺版本以块的forms重新排序这些访问，以便重复单个块可以重复访问缓存。 由于块大小设置为16k，因此它可能适合大多数L1缓存并获得非常好的延迟。 对于外循环的每次迭代，您将有1次迭代，其中您错过了所有缓存并进入内存（如果您的L3大于32M，只需更高地调用MAX以确保），以及从中飞过的REP-1迭代L1。
Untiled版本也会重复自己的REP时间，但每次重复都会从缓存中剔除所有数据，使所有访问都进入内存，累积到更高的整体延迟。
使用gcc 4.8.1（-O3）进行编译，我得到了Xeon 5670 @ 2.9GHz -
Tiled: 0.110000 sec Untiled: 0.450000 sec array[0] = 99
超过4倍:)
请注意，untiled版本仍然有一个好处 - 只有一个有序的流，因此HW预取器可以有效地为您提取数据，有点减轻内存延迟效应。 但是，如果添加以下内容，则可以帮助CPU在存储库版本中执行类似的操作：
for (i = 0; i < MAX; i += B) { for (r = 0; r < REP; r++) { for (j = i; j < (i + B); j+=64) { array[j] = r; if (r == REP - 2) // SW prefetching __builtin_prefetch(&array[j+B], 0); } } }
告诉CPU在完成当前块之前略微引入下一个块。 对于条件分支的价格（每个块有一些错误预测），您减少了下一个块上第一次迭代的执行时间 - 我从那里进一步减少到：
Tiled: 0.070000 sec