代码之家 › 专栏 › 技术社区 › mmr

C++“小”优化行为怪异

optimization c++

mmr · 技术社区 · 15 年前

我正试图在我的一个项目上进行“小范围”优化。

有一系列单独很小的数组访问,但是分析显示这些数组访问是我的程序花费大量时间的地方。所以,时间使事情更快,因为程序运行大约需要一个小时。

我已移动了以下访问类型:

const float theValOld1 = image(x, y, z);
const float theValOld2 = image(x, y+1, z);
const float theValOld3 = image(x, y-1, z);
const float theValOld4 = image(x-1, y, z);

对于当前像素周围的28个访问。

在那里,图像突然出现

float image(const int x, const int y, const int z) const {
     return data[z*xsize*ysize + y*xsize + x];
}

我把它换成了

const int yindex = y*xsize;
const int zindex = z*xsize*ysize;
const float* thePtr = &(data[z*xsize*ysize + y*xsize + x]);
const float theVal1 = *(thePtr);
const float theVal2 = *(thePtr + yindex);
const float theVal3 = *(thePtr - yindex);
const float theVal4 = *(thePtr - 1);

对于相同数量的操作。

我希望,如果编译器非常棒的话,这种改变对速度没有任何影响。如果编译器不是很棒的,那么我会说第二个版本应该更快,如果只是因为我避免了[]thunk附带的隐式指针加法,以及删除y和z的乘法。

为了使它更加不平衡,我将z操作移动到了它们自己的部分,只有在zindex时才会被击中!=0,所以实际上,第二个版本只有9个访问权限。所以根据这个标准,第二个版本肯定会更快。

为了测量性能,我使用了QueryPerformanceCounter。

奇怪的是,操作顺序很重要!

如果我按照描述保留操作并比较计时(以及结果,以确保优化后计算出相同的值),则旧代码每像素大约需要45个滴答,新代码每像素需要10个滴答。如果我反转操作,那么旧代码每像素大约需要14个滴答,新代码每像素大约需要30个滴答(其中有很多噪声,这些平均值超过100个像素)。

为什么订单很重要?是否有缓存或发生了什么?变量的名称都不一样,所以我认为这没关系。如果有缓存发生,有没有什么方法可以利用它从一个像素到另一个像素?

推论:为了比较速度,我假设正确的方法是彼此独立地运行两个版本,然后比较不同运行的结果。我想把这两个比较放在一起是有意义的,但是这里显然有一些事情阻止了这一点。有没有一种方法可以挽救这个并排运行,从一次运行中获得一个合理的速度比较,所以我可以确保结果也是相同的(很容易)?

编辑:澄清。

我在同一个函数中有新代码和旧代码,所以我可以确保结果是相同的。

如果我先运行旧代码,然后运行新代码,新代码比旧代码运行得更快。如果我先运行新代码,然后运行旧代码,则旧代码比新代码运行得更快。

Z命中是数学所必需的,并且if语句不能被删除,并且两者都存在。对于新的代码,我刚将更多z特定的代码移到z部分,我使用的测试代码是100%2d。当我移到3d测试时,我肯定会看到更多的分支效果。

4 回复 | 直到 15 年前

Stack Overflow is garbage 15 年前

如果新版本和旧版本都在同一个数据数组上运行,那么是的,最后一次运行几乎肯定会由于缓存而减速。即使代码不同,它也将访问先前版本已经接触过的数据,因此根据数据大小, 可以在一级缓存中,可能在二级缓存中,如果存在三级缓存,几乎可以肯定。代码中可能还会有一些重叠,这意味着指令缓存将进一步提高第二个版本的性能。

基准测试的一种常见方法是先运行算法一次,而不对其进行计时,只需确保该算法将被缓存、缓存,然后在启用计时的情况下再次运行大量次。(不要相信一次执行,除非至少需要一两秒钟。否则,系统负载、缓存、操作系统中断或页面错误中的微小变化会导致测量的时间变化)。为了消除噪声,测量算法运行几次所用的组合时间,显然在这两次运行之间没有输出。事实上,你看到的峰值是平时的3倍,这意味着你测量的是方式粒度太细。这基本上让你的计时没用。

为什么订单很重要?是否有缓存或发生了什么?变量的名称都不一样,所以我认为这没关系。如果有缓存发生,有没有什么方法可以利用它从一个像素到另一个像素?

命名无关紧要。当代码被编译时,变量被转换成内存地址或寄存器ID。但是当您运行图像数组时,您将把它全部加载到CPU缓存中,这样下次运行它时可以更快地读取它。是的,你可以也应该利用它。

计算机很难利用空间和时间位置——也就是说,如果你在时间t访问一个内存地址x,它假设你很快就会需要地址x+1(空间位置),而且你可能还会再次需要x,时间t+1(时间位置)。它试图以各种可能的方式(主要是通过缓存)加速这些案例,因此您应该尝试利用它。

为了使它更加不平衡,我将z操作移动到了它们自己的部分,只有在zindex时才会被击中!=0,所以实际上,第二个版本只有9个访问权限。所以根据这个标准,第二个版本肯定会更快。

我不知道您将if语句放在哪里,但是如果它放在频繁评估的代码块中,那么分支的成本可能会比您节省的成本对您造成更大的伤害。分支机构可以价格昂贵,而且它们抑制了编译器和CPU重新排序和调度指令的能力。所以没有它你可能会过得更好。您可能应该将其作为一个单独的优化来完成,该优化可以单独进行基准测试。

我不知道你要实现哪种算法,但我猜你需要对每个像素都这样做? 如果是这样,您应该尝试缓存查找。一旦你得到 image(x, y, z) ,这将是下一个像素的 image(x+1, y, z) ,所以将它缓存在循环中,这样下一个像素就不必从头开始查找它了。这可能会使您将X/Y平面中的9个访问减少到3个(使用上次迭代中的3个缓存值、之前迭代中的3个缓存值以及本次迭代中刚加载的3个缓存值)。

如果您正在更新每个像素的值作为其相邻值的结果,一个更好的方法可能是以棋盘模式运行算法。在第一次迭代中,只使用邻居的值(您不更新这些值),更新其他像素,然后运行第二个步骤,根据之前更新的像素值更新之前读取的像素。这样可以消除相邻像素之间的依赖关系,从而有效地对其评估进行流水线和并行处理。

在执行所有查找的循环中,将其展开几次,并尝试将所有内存读取放在顶部,并将所有计算放在较低的位置,以使CPU有机会重叠这两个位置(由于数据读取速度较慢,请启动它们,当它们运行时,CPU将尝试查找它可以评估的其他指令)。

对于任何常量值,请尝试尽可能地预计算它们。(而不是 z*xsize*ysize 预计算 xsize*ysize ,并将z乘以结果。

另一件事是可以帮助是首选局部变量而不是全局变量或类成员。在函数开始时,只需制作您需要的类成员的本地副本,就可以获得一些东西。如果编译器愿意的话,它总是可以再次优化多余的变量,但是您要清楚地表明,它不应该担心对象状态的底层更改(否则,每次访问成员时都会强制它重新加载成员)。

最后,对生成的装配进行了详细的研究。查看它在何处执行不必要的存储/加载,在何处重复操作,即使它们可以被缓存,以及指令的排序效率低下,或者编译器未能如您所希望的那样内联。

不过,老实说,我不希望您对查找函数所做的更改有多大影响。数组访问 operator[] 很容易转换成等价的指针算法,并且编译器可以非常有效地优化它,只要您添加的偏移量不变。

通常,低级优化的关键是,有点讽刺的是, 不查看单独的代码行,但查看整个函数和循环。您需要在一个块中有一定数量的指令,这样您就可以处理一些事情,因为许多优化处理打破指令链之间的依赖关系,重新排序以隐藏指令延迟,以及缓存单个值以避免内存加载/存储。这在单个数组查找中几乎是不可能做到的,但是如果一次考虑几个像素,几乎可以肯定会得到很多。

当然,就像几乎所有的微优化一样,没有 永远真实 答案。上面的一些可能对您有用,或者它们可能不有用。

如果您告诉我们更多关于访问模式的信息(您正在访问哪些像素,是否有任何所需的顺序,您只是在读还是在写?如果正在写入,何时何地使用更新的值?)

如果你给我们更多的信息,我们将能够提供更具体的(并且可能是有效的)建议。

leander 15 年前

你可以 (可能)遇到某种预读或缓存线边界问题。一般来说,当您加载一个值并且它不是“热”(在缓存中)时,CPU将拉入一条缓存线(32、64或128字节非常典型,取决于处理器)。对同一行的后续读取将快得多。

如果更改操作顺序,可能会看到由于如何加载和收回行而暂停。

解决这类问题的最佳方法是打开“反汇编”视图,并在处理器的参考手册上花费一些时间。

如果幸运的话,代码重新排序导致的更改将是显而易见的(编译器可能会生成额外的指令或分支)。不太幸运的是,它会在处理器的某个地方暂停——在解码过程中或由于内存获取…

一个可以计算暂停和缓存未命中的好的探查器在这里也有帮助(AMD已经 CodeAnalyst 例如。

如果你不在时间紧迫的情况下,那就真的值得陷入混乱之中——至少,你最终可能会学到一些你以前不知道的东西,比如你的CPU、机器体系结构、编译器、库等等是如何工作的。(我在学习歧义时几乎总是“啊”的。)

Indy9000 15 年前

在优化时,检查数据访问模式至关重要。

例如:

假设宽度为240

像素为 <x,y,z> 10,10,0

使用原始访问模式,您可以:

a. data[0+ 10*240 + 10] -> data[2410]
b. data[0+ 11*240 + 10] -> data[2650]
c. data[0+  9*240 + 10] -> data[2170]
d. data[0+ 10*240 +  9] -> data[2409]

注意索引的顺序是任意的。

内存控制器对主内存进行对齐访问以填充缓存线。如果您对操作进行排序,以便访问到递增的内存地址 (例如) c,d,a,b )然后内存控制器将能够将数据流传输到缓存线。

读取时丢失缓存会很昂贵,因为它必须搜索缓存到主内存的层次结构。主内存访问速度可能比隐藏物。最小化主内存访问将提高操作速度。

Community kfsone 7 年前

为了使它更加不平衡,我将z操作移动到了它们自己的部分,只有在zindex时才会被击中!=0,所以实际上,第二个版本只有9个访问权限。所以根据这个标准,第二个版本肯定会更快。

你真的测量过吗?因为如果那是真的,我会很惊讶的。安 if 程序内部循环中的语句可能会增加惊人的开销——请参见 Is "IF" expensive? . 我敢打赌,额外乘法的开销要比分支的开销小得多,除非 z 刚好是99%的时间。

奇怪的是,操作顺序很重要!

什么操作的顺序?我不清楚你在这里重新订购什么。请再给我一些你想做的事情的片段。