我正在尝试在我的项目中优化'小'.
有一系列的数组访问虽然很小,但是分析表明这些数组访问是我的绝大多数程序花费时间的地方.所以,时间更快,因为程序需要大约一个小时才能运行.
我已经移动了以下类型的访问:
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次访问.
图像thunks到哪里
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附带的implict指针添加,以及删除y和z的乘法的indeces.
为了使它更加不平衡,我已经将z操作移动到它们自己的部分中,只有在zindex!= 0时才会被击中,所以实际上,第二个版本只有9次访问.因此,通过该指标,第二个版本肯定会更快.
为了衡量性能,我使用的是QueryPerformanceCounter.
对我来说奇怪的是操作顺序很重要!
如果我按照描述离开操作并比较时间(以及结果,以确保在优化后计算相同的值),那么旧代码每个像素大约需要45个刻度,新代码每个像素需要10个刻度.如果我反向操作,那么旧代码每个像素需要大约14个滴答,并且新代码每个像素需要大约30个滴答(其中有大量噪声,这些是大约100个像素的平均值).
为什么订单很重要？是否有缓存或发生的事情？变量都被命名为不同的东西,所以我认为这不重要.如果有一些缓存发生,有什么办法可以从像素到像素利用它吗？
推论:为了比较速度,我假设正确的方法是彼此独立地运行两个版本,然后比较不同运行的结果.我希望彼此相邻的两个比较是有道理的,但显然这里发生了一些阻止它的事情.有没有办法挽救这种并排运行以从单次运行中获得合理的速度比较,所以我可以确保结果也相同(轻松)？
编辑:澄清.
我在同一个函数中有新旧代码,所以我可以确保结果是相同的.
如果我运行旧代码然后运行新代码,新代码运行速度比旧代码快.如果我运行新代码然后运行旧代码,旧代码运行速度比新代码快.
数学需要z命中,并且if语句不能被删除,并且两者都存在.对于新代码,我只是将更多特定于z的代码移动到z部分,而我使用的测试代码是100%2D.当我进行3D测试时,我确信我会看到更多的分支效果.
您可能(可能)遇到某种预读或高速缓存行边界问题.一般来说,当您加载单个值并且它不是"热"(在缓存中)时,CPU将拉入缓存行(32,64或128字节非常典型,具体取决于处理器).对同一行的后续读取将更快.
如果你改变了操作的顺序,你可能会看到由于线路的加载和驱逐方式而导致的停顿.
想出这样的事情的最好方法是打开"反汇编"视图,并在处理器的参考手册上花一些时间.
如果幸运的话,代码重新排序导致的更改将是显而易见的(编译器可能正在生成额外的指令或分支).不太幸运,它将在处理器的某个地方 - 在解码管道期间或由于内存提取...
一个可以计算停顿和缓存未命中的好的分析器也可能有帮助(例如,AMD有CodeAnalyst).
如果你没有时间紧迫,那么深入研究这种挫折是非常值得的 - 至少,你可能最终会学到一些你以前不知道的关于你的CPU,机器架构,编译器,库的知识.等工作.(在研究痉挛时,我几乎总是"胡说".)
如果新版本和旧版本都在同一个数据阵列上运行,那么是的,最后一次运行几乎肯定会因缓存而加速.即使代码不同,它也将访问之前版本已经触及的数据,因此根据数据大小,它可能位于L1缓存中,可能位于L2缓存中,如果存在L3缓存,则几乎当然在那.代码中可能还会有一些重叠,这意味着指令缓存将进一步提升第二版的性能.
一种常见的基准测试方法是首先运行算法,而不对其进行计时,只是为了确保缓存,缓存,然后在启用计时的情况下再次运行它.(不要相信一次执行,除非至少花费一两秒钟.否则系统负载,缓存,操作系统中断或页面错误的微小变化都会导致测量时间变化).为了消除噪声,测量算法的几次运行所花费的总时间,显然两者之间没有输出.事实上,你看到平时达到3倍的峰值意味着你的测量方式太精细了.这基本上使你的时间无用.
为什么订单很重要？是否有缓存或发生的事情？变量都被命名为不同的东西,所以我认为这不重要.如果有一些缓存发生,有什么办法可以从像素到像素利用它吗？
命名无关紧要.编译代码时,变量将转换为内存地址或寄存器ID.但是当你运行你的图像数组时,你将它全部加载到CPU缓存中,因此下次运行它时可以更快地读取它.是的,你可以而且应该利用它.
计算机非常努力地利用空间和时间局部性 - 也就是说,如果你在时间T访问一个内存地址X,它假定你很快就需要地址X + 1(空间局部性),而你在时间T + 1(时间局部性),可能还需要X. 它试图以各种可能的方式加速这些情况(主要是通过缓存),所以你应该尝试利用它.
为了使它更加不平衡,我已经将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[]可以轻松转换为等效的指针算法,只要你添加的偏移不改变,编译器就可以非常有效地优化它.
通常,具有讽刺意味的是,低级优化的关键是不要查看单独的代码行,而是查看整个函数和循环.您需要一定量的指令块,所以你有一些帮助,因为很多的优化处理的指示,重新排序隐藏指令延迟链之间打破依赖和缓存单个值,以避免内存负载/存储.这对于单个数组查找几乎是不可能的,但如果你一次考虑几个像素,几乎可以肯定会有很多.
当然,与几乎所有的微观优化一样,并不总是真正的答案.以上某些内容可能对您有用,或者可能不适用.
如果你告诉我们更多关于访问模式的信息(你访问哪些像素,是否有任何所需的顺序,你只是阅读,还是写作？如果写,何时何地使用更新值？)
如果您向我们提供更多信息,我们将能够提供更具体(可能更有效)的建议