C++中双减法的优化

Question

我有以下代码用于计算两个向量之间的距离:

double dist(vector<double> & vecA, vector<double> & vecB){
    double curDist = 0.0;
    for (size_t i = 0; i < vecA.size(); i++){
        double dif = vecA[i] - vecB[i];
        curDist += dif * dif;
    }

    return curDist;
}

此功能是我应用程序中的主要瓶颈,因为它依赖于大量距离计算,在典型输入上占用超过60%的CPU时间.另外,以下行:

double dif = vecA[i] - vecB[i];

在此功能中负责超过77%的CPU时间.我的问题是:是否有可能以某种方式优化此功能？

笔记:

• 为了描述我的应用,我使用了Intel Amplifier XE;
• 减少距离计算的数量对我来说不是一个可行的解决方案;

Answer 1

我现在可以想到两个可能的问题:

• 此计算是内存绑定的.
• 有一个迭代到迭代依赖curDist.

此计算是内存绑定的.

您的数据集大于CPU缓存.因此,在这种情况下,除非您可以重构算法,否则任何优化量都无济于事.

有一个迭代到迭代依赖curDist.

你有依赖curDist.这将阻止编译器进行矢量化.(另外,不要总是将分析器编号信任到该行.它们可能不准确,尤其是在编译器优化之后.)

通常,编译器矢量化器可以将curDist多个部分和分割为循环并展开/向量化循环.但它不能在严格浮点行为下做到这一点.如果你还没有,你可以尝试放松你的浮点模式.或者您可以拆分总和并自行展开.

例如,这种优化是编译器可以对整数执行的操作,但不一定是浮点数:

double curDist0 = 0.0;
double curDist1 = 0.0;
double curDist2 = 0.0;
double curDist3 = 0.0;
for (size_t i = 0; i < vecA.size() - 3; i += 4){
    double dif0 = vecA[i + 0] - vecB[i + 0];
    double dif1 = vecA[i + 1] - vecB[i + 1];
    double dif2 = vecA[i + 2] - vecB[i + 2];
    double dif3 = vecA[i + 3] - vecB[i + 3];
    curDist0 += dif0 * dif0;
    curDist1 += dif1 * dif1;
    curDist2 += dif2 * dif2;
    curDist3 += dif3 * dif3;
}

//  Do some sort of cleanup in case (vecA.size() % 4 != 0)

double curDist = curDist0 + curDist1 + curDist2 + curDist3;