C’小’优化表现奇怪

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,z);

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);

如果新版本和旧版本都在同一个数据阵列上运行,那么是的,最后一次运行几乎肯定会因缓存而加速.即使代码不同,它也将访问先前版本已经触及的数据,因此根据数据大小,它可能位于L1缓存中,可能位于L2缓存中,如果存在L3缓存,则几乎当然在那.代码中可能还会有一些重叠,这意味着指令缓存将进一步提升第二版的性能.

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

Why should the order matter? Is there caching or something happening? The variables are all named different things,so I wouldn’t think that would matter. If there is some caching happening,is there any way I can take advantage of it from pixel to pixel?

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

计算机非常努力地利用空间和时间局部性 – 也就是说,如果你在时间T访问一个内存地址X,它假定你很快就需要地址X 1(空间局部性),并且你’在时间T 1(时间局部性)可能还需要X.它试图以各种可能的方式加速这些情况(主要是通过缓存),所以你应该尝试利用它.

To make it even more lopsided,I’ve moved the z operations into their own section that only gets hit if zindex != 0,so effectively,the second version only has 9 accesses. So by that metric,the second version should definitely be faster.

我不知道你把if语句放在哪里,但是如果它在经常被评估的代码块中,那么分支的成本可能会比你保存更多地伤害你.分支可能很昂贵,并且它们会抑制编译器和CPU重新排序和调度指令的能力.没有它你可能会更好.您可能应该将此作为单独的优化,可以单独进行基准测试.

我不知道你正在实现哪种算法,但我猜你需要为每个像素执行此操作？
如果是这样,您应该尝试缓存查找.一旦你得到了图像(x,z),那将是下一个像素的图像(x 1,所以将它缓存在循环中,这样下一个像素就不必从中查找刮.这可能会允许您将X / Y平面中的9次访问减少到3次(使用上次迭代中的3个缓存值,前一次使用3次缓存,以及我们刚刚在此次迭代中加载3次)

如果由于其邻居值而更新每个像素的值,则更好的方法可能是以棋盘图案运行算法.在第一次迭代中更新每个其他像素,仅使用其邻居中的值(您没有更新),然后运行第二次传递,根据您之前更新的像素值更新之前读取的像素.这允许您消除相邻像素之间的依赖关系,因此可以有效地对其评估进行流水线化和并行化.

在执行所有查找的循环中,将其展开几次,并尝试将所有内存读取放在顶部,并将所有计算进一步放下,以使CPU有机会重叠两个(因为数据读取是一个慢一点,让它们启动,当它们运行时,CPU会尝试找到它可以评估的其他指令).

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

可能有帮助的另一件事是优先选择局部变量而不是全局变量或类成员.在函数开始时,您可以简单地获得一些东西,制作您将需要的类成员的本地副本.编译器总是可以根据需要再次优化额外的变量,但是你明确表示它不应该担心对象状态的底层更改(否则可能会强制它在每次访问时重新加载成员)

最后,详细研究生成的装配.查看它执行不必要的存储/加载的位置,即使它们可以被缓存,也可以重复操作,以及指令的排序效率低下,或者编译器无法按照您的希望进行内联.

老实说,我不希望你对查找功能的更改产生很大影响.使用operator []的数组访问很容易转换为等效的指针算法,只要你添加的偏移不改变,编译器就可以非常有效地优化它.

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

当然,与几乎所有的微观优化一样,并不总是真正的答案.以上某些内容可能对您有用,或者可能不适用.

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

如果您向我们提供更多信息,我们将能够提供更具体(可能更有效)的建议