Rob*_*rto 7 c++ performance benchmarking loops
我一直有这个想法,减少迭代次数是的方式来使程序更加高效.由于我从未真正确认过,我开始测试这个.
我制作了以下C++程序来测量两个不同函数的时间:
完整的测试代码:
#include <iostream>
#include <chrono>
using namespace std;
int* list1; int* list2;
int* list3; int* list4;
int* list5; int* list6;
int* list7; int* list8;
int* list9; int* list10;
const int n = 1e7;
// **************************************
void myFunc1()
{
for (int i = 0; i < n; i++)
{
list1[i] = 2;
list2[i] = 4;
list3[i] = 8;
list4[i] = 16;
list5[i] = 32;
list6[i] = 64;
list7[i] = 128;
list8[i] = 256;
list9[i] = 512;
list10[i] = 1024;
}
return;
}
// **************************************
void myFunc2()
{
for (int i = 0; i < n; i++)
{
list1[i] = 2;
}
for (int i = 0; i < n; i++)
{
list2[i] = 4;
}
for (int i = 0; i < n; i++)
{
list3[i] = 8;
}
for (int i = 0; i < n; i++)
{
list4[i] = 16;
}
for (int i = 0; i < n; i++)
{
list5[i] = 32;
}
for (int i = 0; i < n; i++)
{
list6[i] = 64;
}
for (int i = 0; i < n; i++)
{
list7[i] = 128;
}
for (int i = 0; i < n; i++)
{
list8[i] = 256;
}
for (int i = 0; i < n; i++)
{
list9[i] = 512;
}
for (int i = 0; i < n; i++)
{
list10[i] = 1024;
}
return;
}
// **************************************
int main()
{
list1 = new int[n]; list2 = new int[n];
list3 = new int[n]; list4 = new int[n];
list5 = new int[n]; list6 = new int[n];
list7 = new int[n]; list8 = new int[n];
list9 = new int[n]; list10 = new int[n];
auto start = chrono::high_resolution_clock::now();
myFunc1();
auto elapsed = chrono::high_resolution_clock::now() - start;
long long microseconds = chrono::duration_cast<chrono::microseconds>(elapsed).count();
cout << "Time taken by func1 (micro s):" << microseconds << endl << endl;
//
start = chrono::high_resolution_clock::now();
myFunc2();
elapsed = chrono::high_resolution_clock::now() - start;
microseconds = chrono::duration_cast<chrono::microseconds>(elapsed).count();
cout << "Time taken by func2 (micro s):" << microseconds << endl << endl;
delete[] list1; delete[] list2; delete[] list3; delete[] list4;
delete[] list5; delete[] list6; delete[] list7; delete[] list8;
delete[] list9; delete[] list10;
return 0;
}
现在我有了相互矛盾的假设:一方面,两个函数的操作量都相同,只是设置了一些变量.虽然另一方面,第二个功能经历了10倍以上的循环,因此(也许)也需要10倍的时间.
该结果是令人吃惊的.在我的电脑上,func1()大约需要280毫秒,func2()大约需要180毫秒,第一个功能实际上更慢而不是更快.
现在提出问题:我的测试是否正确？合并for循环以最小化迭代总数甚至有用吗？人们有不同的经历吗？
编辑:我编译了所有禁用的优化,用于测试. 编辑:更改函数调用的顺序给出相同的结果.此外,测量的时间变化非常小,因此我没有费心去取平均值.
编辑:我通过-O3优化再次尝试了所有这些.虽然确切的测量值当然不同,但结果确实保持不变.
这里有三件重要的事情：
1）没有优化的基准测试是没有意义的。事实证明，在这种情况下会产生真正的效果，而这种效果不会随着优化而消失。事实上，在将循环计数器存储在内存中的额外成本（将循环计数器限制为每6个时钟1个对每个时钟1个）的反作用下，反优化的调试版本掩盖了很多差异，并且没有自动向量化存储循环。
如果您还不知道为什么有速度差异的asm + CPU微体系结构详细信息，那么在禁用优化的情况下对其进行测量既不安全也不有用。
2）缓存冲突未命中（如果所有数组相对于页面边界对齐的位置相同）。 相对于彼此倾斜阵列会很有帮助。这取决于它们的分配方式，即使它们的大小不是2的大幂，也可以自然发生。
这些数组很大，并且分别用分配new，因此它们可能都是页面对齐的（或者在将某些信息（例如大小）放在对象之前的实现中，它们从页面边界偏移16B）。在Linux上，glibc malloc / new通常通过以下方式处理大量分配：通过从OS分配新页面mmap()（并使用前16个字节作为该块的簿记），而不是移动brk()。
4k别名意味着它们都进入典型的L1d高速缓存中的同一集合，在典型的x86 CPU上，这是8路关联的。 为什么在大多数处理器中，L1高速缓存的大小小于L2高速缓存的大小？解释了为什么64集* 64B /行= 4096B页面大小（时间8路= 32kiB）不是巧合，因为这使VIPT L1d缓存像PIPT一样工作而没有同音/同义词问题。另请参阅Intel Core i7处理器中使用了哪种缓存映射技术？
第9个存储区将从第一个存储区中移出缓存行，因此每个存储区将逐出一次行，而不像在连续情况下那样完全写入。（除非编译器自动向量化，然后在继续之前将整个存储行缓存到一个阵列中。）x86的强排序内存模型需要按照程序顺序将存储缓冲区中的存储提交到L1d，因此无法合并提交之前，将不相邻的同一行存储到同一行中；如果行不连续，则在行进入时提交多个未完成的存储。
（替换策略是伪LRU，不是真正的LRU，因此有时您可能会发现在同一组中驱逐8或9次后，线路仍然很热。）
提醒：以上仅适用于所有数组相对于page对齐的情况。过度分配和执行ptr = 128 + malloc(128 + size)其中一个指针可能会使它相对于其他指针产生偏差，这有时是值得做的。
您说您有一台PC，所以我猜是Intel CPU。（Ryzen的L1d具有相同的几何形状，但推土机家族则没有。）
（英特尔优化手册节3.6.10写入合并建议循环分裂为写超过4个输出流的循环这个建议是在约新台币商店和WC内存部分，它可能只打算适用于这种情况。 无论哪种方式4 ISN除非您保守地考虑其他超线程，否则对于现代Intel来说，它不是正确的数字。
（英特尔的）汇编/编译器编码规则58。（对H的影响，对L的通用性）如果一个内部循环写入四个以上的数组（四个不同的缓存行），请应用循环裂变来拆分循环主体，以便仅四个数组在每个结果循环的每次迭代中写入。
TL：DR：对于NT存储（绕过缓存），在Skylake和更高版本上最多可以有12条输出流，在Broadwell / Haswell和更旧版本上最多可以有10条输出流。（如果您同时读取任何内存，则更少。）那就是这些CPU上的LFB（行填充缓冲区）的数量。较早的CPU（在Nehalem之前）少于10个，也许不能将它们全部用于NT存储。（写合并缓冲区在哪里？x86）LFB用于所有往返L1d的线路传输，因此，例如，挂起的负载丢失需要分配一个LFB来等待L2d的那条线路。
（使用超线程时，请记住，另一个超线程正在竞争同一物理核心上的LFB，因此除非您可以禁用HT，否则不要依赖于使用所有12个LFB。）
但是您没有在NT商店。
在传统的智慧 为这4输出效率限制施加到正常（非NT）存储到存储器WB为好，但也就是不现代英特尔的情况。碰巧的是，正常（WB =写回）存储的性能下降的输出流数量与NT存储的数量相同。那篇机械同情的文章猜测了原因，但是我们很确定他们听起来不正确。
有关某些微基准，请参见https://github.com/Kobzol/hardware-effects/issues/1。（并查看我自己，BeeOnRope和Hadi Brais之间关于LFB的讨论，提出了此4输出准则：https ://chat.stackoverflow.com/transcript/message/45474939#45474939，该内容以前在存储缓冲区大小下的注释中在Intel硬件上，什么是存储缓冲区？
@BeeOnRope还发布了一个条形图，用于在Skylake 上将常规（非NT）商店交错到1到15个输出流。 对于在Skylake上最多约6个的任何数量的流，性能在某种程度上是恒定的，然后在7和8时性能开始变差（如果阵列都以相同的方式对齐，则可能是由于L1d冲突未命中），而从9以后则更显着直到接近13到15的稳定水平为止（大约是1到6个流情况下的性能的1/3）。
同样，借助超线程，如果另一个逻辑核心完全运行，则几乎可以肯定会生成一些内存流量，因此，保守的限制（例如4个输出流）并不是一个坏计划。 但是性能并不会下降到7或8，因此如果花费更多的总精力，就不必裂开循环。
另请参阅memcpy的Enhanced REP MOVSB，以了解有关常规RFO存储与no-RFO NT存储的更多信息，以及许多x86内存带宽问题。（特别是内存/ L3缓存延迟限制了大多数CPU上的单核带宽，但在多核Xeons上更糟：它们令人惊讶地具有比四核台式机更低的单核内存带宽。当有足够多的核忙时，您可以饱和它们来自四通道或6通道内存控制器的高聚合带宽；这是针对它们进行优化的情况。）
2.5）DRAM页面局部性：当最终从L3（最后一级缓存）中逐出数据时，会发生向存储器的写回操作。脏的缓存行被发送到内存控制器，后者可以缓冲并将它们成批分组，但是仍然存在混合存储（和RFO加载）到所有10个阵列。双通道内存控制器不能一次打开10个DRAM页。（我认为每个通道只有1个通道，但我不是DRAM时序专家。请参阅Ulrich Drepper的《每个程序员应该了解的内存知识》，其中有一些详细信息。） https://pubweb.eng.utah.edu/~cs6810 /pres/12-6810-15c.pdf提到了针对流存储与分散存储的DRAM打开/关闭页面策略。
最重要的是，即使高速缓存可以处理许多输出流，DRAM也可能会更少一些而更快乐。请注意，DRAM“页面”的大小与虚拟内存页面（4k）或大页面（2M）的大小不同。
说到虚拟内存，TLB应该可以有10个输出流：现代的x86 CPU拥有10个以上的L1dTLB条目。希望它们具有足够的关联性，或者条目不是全部别名，因此我们不会在每家商店都遇到TLB遗漏！
@RichardHodges发现了这个）
您的大型组合循环不会使用gcc或clang自动矢量化。他们无法证明事实list1[10]并非list4[9]如此，因此无法list1[8..11]使用单个16字节存储区进行存储。
但是单阵列循环可以轻松地通过SSE或AVX自动矢量化。（令人惊讶的不是一个wmemset电话什么的，只是普通的自动向量化只gcc -O3，或者clang -O2，这可以切换到NT商店的大尺寸，这将有助于最如果有多个内核针对内存带宽的竞争。memset的模式识别为/即使没有自动矢量化也将很有用。）
这里唯一需要进行的别名分析是为了证明list1[i] = 2不会修改list1指针值本身（因为该函数在循环内读取全局值，而不是将值复制到局部值）。基于类型的别名分析（-fstrict-aliasing默认情况下处于启用状态）使编译器能够证明和/或如果list1指向自身，则可能会在以后的循环迭代中访问对象外部而产生未定义的行为。
在某些情况下（例如，输出数组相对于输入数组），如果您不使用__restrict关键字（由C的限制所导致的几个编译器借用），则智能编译器可以并且确实会检查重叠情况。如果存在重叠，它们将退回到安全的标量循环。
但这在这种情况下不会发生：gcc和clang根本不会生成矢量化循环，它们只是在中执行标量myFunc1。如果每个存储区都在L1d中导致冲突未命中，那么这将比您为编译器提供足够的信息来完成其工作更糟4倍。（或8x和AVX一起用于32字节存储）。通常，当主内存带宽成为瓶颈（不是L1d高速缓存）时，16B与32B存储之间的差异很小，但是在这里，这可能会很重要，因为如果10个输出流全部都是别名，则会破坏L1d的写合并效果。
顺便说一句，制作全局变量static int *__restrict line1等等确实允许gcc自动向量化中的商店myFunc1。但是，它不会分裂循环。（可以这样做，但是我想它不是在寻找这种优化。这取决于程序员。）
// global modifier allows auto-vec of myFunc1
#define GLOBAL_MODIFIER __restrict
#define LOCAL_MODIFIER __restrict // inside myFunc1
static int *GLOBAL_MODIFIER list1, *GLOBAL_MODIFIER list2,
*GLOBAL_MODIFIER list3, *GLOBAL_MODIFIER list4,
*GLOBAL_MODIFIER list5, *GLOBAL_MODIFIER list6,
*GLOBAL_MODIFIER list7, *GLOBAL_MODIFIER list8,
*GLOBAL_MODIFIER list9, *GLOBAL_MODIFIER list10;
我将您的代码放在带有gcc8.1和clang6.0的Godbolt编译器浏览器上，进行了更改+一个从一个数组中读取的函数，以阻止它们完全优化（这是因为我制作了它们static。）
然后我们得到这个内部循环，它可能比做相同事情的标量循环快4倍。
.L12: # myFunc1 inner loop from gcc8.1 -O3 with __restrict pointers
movups XMMWORD PTR [rbp+0+rax], xmm9 # MEM[base: l1_16, index: ivtmp.87_52, offset: 0B], tmp108
movups XMMWORD PTR [rbx+rax], xmm8 # MEM[base: l2_17, index: ivtmp.87_52, offset: 0B], tmp109
movups XMMWORD PTR [r11+rax], xmm7 # MEM[base: l3_18, index: ivtmp.87_52, offset: 0B], tmp110
movups XMMWORD PTR [r10+rax], xmm6 # MEM[base: l4_19, index: ivtmp.87_52, offset: 0B], tmp111
movups XMMWORD PTR [r9+rax], xmm5 # MEM[base: l5_20, index: ivtmp.87_52, offset: 0B], tmp112
movups XMMWORD PTR [r8+rax], xmm4 # MEM[base: l6_21, index: ivtmp.87_52, offset: 0B], tmp113
movups XMMWORD PTR [rdi+rax], xmm3 # MEM[base: l7_22, index: ivtmp.87_52, offset: 0B], tmp114
movups XMMWORD PTR [rsi+rax], xmm2 # MEM[base: l8_23, index: ivtmp.87_52, offset: 0B], tmp115
movups XMMWORD PTR [rcx+rax], xmm1 # MEM[base: l9_24, index: ivtmp.87_52, offset: 0B], tmp116
movups XMMWORD PTR [rdx+rax], xmm0 # MEM[base: l10_25, index: ivtmp.87_52, offset: 0B], tmp117
add rax, 16 # ivtmp.87,
cmp rax, 40000000 # ivtmp.87,
jne .L12 #,
（当然，这是为x86-64编译的。x8632位没有足够的寄存器来将所有指针保留在regs中，因此您会有一些负载。但是这些负载会进入L1d缓存中，而实际上并不会吞吐量瓶颈很大：在每个时钟瓶颈1个存储的情况下，在仅存储常量的情况下，有足够的吞吐量来完成更多工作。）
这种优化就像展开循环4x并重新排列以将4个存储分组到每个数组一样。这就是为什么如果编译器不知道它们是非重叠的，则无法完成的原因。__restrict不幸的是，clang甚至都没有这样做。__restrict保证不重叠的通常用法是在函数args上，而不是在本地变量或全局变量上，但我没有尝试过。
使用全局数组而不是全局指针，编译器将知道它们没有重叠（并且不会在内存中的任何位置存储指针值；数组地址将是链接时常量。）在您的版本中，数组本身具有动态存储，只有指向它们的指针才具有静态存储。
如果myFunc1在继续前进到下一个数组之前将64个字节存储到一个数组中怎么办？然后，您的编译器可以安全地将其每次迭代每个数组编译为4（SSE），2（AVX）或1（AVX512）向量存储，覆盖整个64个字节。
如果将指针按64对齐（或者如果编译器进行了一些别名分析并到达每个输出数组的第一个64字节边界），则每个存储块将完全写入一个缓存行，而我们不会碰它稍后再试。
这样可以避免L1d冲突失败，对吗？也许可以，但是除非您使用NT商店来避免RFO，否则硬件预取程序需要先将线拉到L2，然后再拉到L1d，然后再尝试提交存储。因此，这并不像您想的那么简单，但是将存储合并到尚未到达的行的写合并缓冲区会有所帮助。
Intel CPU中的L2流媒体预取器可以跟踪每页1个正向访问和1个向后访问，因此应该没问题（如果阵列在L2中没有别名）。最大的问题是L1d预取。
仍然会大大减少往返于L2的高速缓存行的数量。 如果您有一个无法轻易分裂为多个循环的循环，请至少展开该循环，以便在继续之前编写完整的缓存行
AVX512可能有所作为；如果将vmovdqa64 [mem], zmm0Skylake-AVX512上的对齐方式对齐，则IDK 可能会在使高速缓存行进入MESI Modified状态时跳过加载旧值，因为它知道它会覆盖整个高速缓存行。（如果完成时没有合并掩码）。
即使使用AVX512，gcc8.1也不麻烦对齐输出指针。对于类似这样的简单情况（两次写相同的内存都不是问题）的简单情况，可能重叠的第一个和最后一个向量可能是一个不错的策略。（与Skylake硬件上的AVX2相比，对齐对AVX512的影响更大。）
4）在Intel Skylake上，存储循环的出乎意料的差和奇怪的双峰性能表明，对于L1d / L2带宽，将伪写入（到同一位置）与存储流交错会使其比1个连续流更糟。
可能是因为在提交到L1d缓存之前，存储缓冲区中发生了存储合并/合并。但是，仅对于同一高速缓存行的相邻存储（因为x86的强排序内存模型不能允许存储无序地提交给L1d）。
该测试不会遭受缓存冲突问题的困扰。但是连续编写一条整个缓存行也应该对此有所帮助。
如果我不得不冒险猜测我会说你看到的是第一个函数中更频繁的内存缓存未命中的结果.
myFunc1() 实质上是以随机访问方式执行10e8内存写入.
myFunc2() 正在执行10个7字的10倍顺序存储器写入.
在现代内存架构上,我希望第二种更高效.
| 归档时间： |
|
| 查看次数： |
851 次 |
| 最近记录： |