如何利用已知的瓶颈优化计算密集型C++程序？

Question

我正在为我的大学开发一些科学软件.它是用Windows(VS2008)的C++编写的.该算法必须为大量矩阵对计算一些值,也就是说,在核心处存在迭代矩阵的循环,收集一些数据,例如:

sumA = sumAsq = sumB = sumBsq = diffsum = diffsumsq = return = 0;
for (int y=0; y < height; ++y)
{
    for (int x=0; x < width; ++x)
    { 
        valA = matrixA(x,y);
        valB = matrixB(x,y);
        sumA+=valA;
        sumAsq+=valA*valA;
        sumB+=valB;
        sumBsq+=valB*valB;
        diffsum+=valA-valB;
        diffsumsq+=(valA-valB)*(valA-valB);
    }
}
return = sumA + sumB / sumAsq + sumBsq * diffsum * diffsumsq

对于不同的matrixA,matrixB对,该例程被执行数百万次.我的问题是这个程序非常慢,在发布模式下编译,激活了所有优化.使用"busy-busy-and-inspect"调试器技术,我确定程序几乎每次都在这个循环中,尽管如你所料,这个例程被一大堆条件和控制分支所包围.令我最困惑的是,在基于Xeon的双处理器系统上执行时,该程序使用了4个内核中的一个(毫不奇怪,现在它是单线程的)但只有最多约25%的限制并且具有相对较大的振荡,在程序终止之前我会期望稳定,100%负载.

当前版本实际上是一个重写,在优化性能时创建.当我发现它实际上比原来慢时,我感到很沮丧.之前的版本使用了Boost矩阵,我将其替换为OpenCV矩阵,在比较两个1000x100矩阵乘法的执行时间后,它们的速度提高了10倍.我通过手动取消引用指向其数据的原始指针来访问矩阵,我希望这会获得一些性能.我使计算例程成为一个多行#define宏来强制执行其内联并避免函数调用和返回.我改进了计算背后的数学运算,以便在单次通过矩阵时计算最终值(旧版本需要两次通过).我希望获得巨大的收益,但事实恰恰相反.一世'

我想知道它是否与矩阵数据是8位字符有关,我曾经看到对浮点数的访问实际上比在我的旧程序中加倍要快,因为处理器在32中检索数据时字符甚至更慢比特块(这个Xeon可能甚至可以抓取64位).我还考虑将矩阵转换为向量以避免循环内循环结构,以及某种形式的向量化,例如在单个循环迭代中计算4个(更少？更多？)连续矩阵单元的数据.还有其他想法吗？

编辑:基于OpenCV的新版本中的实际代码:

const char *Aptr, *Bptr;
double sumA = 0, sumB = 0, sumAsq = 0, sumBsq = 0, diffsum = 0, diffsumsq = 0;
char Aval, Bval;

for (int y=0; y < height; ++y)
{
    Aptr = (char*)(AMatrix.imageData + AMatrix.widthStep * y);
    Bptr = (char*)(BMatrix.imageData + BMatrix.widthStep * y);
    for (int x=0; x < width; ++x)
    {
        Aval = Aptr[x];
        Bval = Bptr[x];

        sumA+=Aval;
        sumB+=Bval;
        sumAsq+=Aval*Aval;
        sumBsq+=Bval*Bval;
        diffsum+=Aval-Bval;
        diffsumsq+=(Aval-Bval)*(Aval-Bval);
    }
}

Answer 1

如果您使用“暂停”技术，它应该告诉您的不仅仅是您处于该循环中。它应该告诉你循环的位置。

永远不要猜测什么时候你就能找到答案。也就是说，这是我的猜测:-) 您正在浮点变量中进行所有求和，但将原始数字作为整数字符获取，对吧？然后，您可以预期从 int 到 double 的转换需要一些时间，如果是这样，您会看到这些指令大部分时间都发生暂停。所以基本上我想知道为什么你不用整数算术来完成这一切。

你说利用率永远不会超过25%。难道是因为它只使用了 4 个核心之一？

你说利用率经常低于25%。这表明该线程可能正在阻塞执行文件 I/O。如果是这样，你的停顿应该抓住它并确认它。如果是这样，您也许可以通过使用更大的块或减少打开/关闭的频率来加速 I/O。请注意，对内部循环的改进将减少该循环所花费的时间，但不会减少 I/O 所花费的时间，因此 I/O 时间百分比将会增加（导致利用率明显下降） ，直到你也缩小它。

利用率实际上并不是一个非常有用的数字。它实际上只是 CPU/IO 分配的一个指标，并且根本不会告诉您是否对其中任何一个执行了太多操作。

正如@renick 所说，摆脱地址计算。您应该能够在汇编语言级别单步执行此循环，并看到它执行的操作与您戴上“大师”帽子并自己编写程序集所做的操作一样。

无论如何，矢量化可能是一个巨大的胜利。