由于if语句，C++性能严重下降

Question

我正在4个线程中运行while循环，在循环中评估函数并逐步增加计数器。

while(1) {
    int fitness = EnergyFunction::evaluate(sequence);

    mutex.lock();
    counter++;
    mutex.unlock();
}

当我运行这个循环时，如我在4个运行线程中所说的那样，我每秒得到大约20,000,000次的评估。

while(1) {
    if (dist(mt) == 0) {
        sequence[distDim(mt)] = -1;
    } else {
        sequence[distDim(mt)] = 1;
    }
    int fitness = EnergyFunction::evaluate(sequence);

    mainMTX.lock();
    overallGeneration++;
    mainMTX.unlock();
}

如果我为这个序列添加一些随机突变，我可以获得每秒约13,000,000次的评估。

while(1) {
    if (dist(mt) == 0) {
        sequence[distDim(mt)] = -1;
    } else {
        sequence[distDim(mt)] = 1;
    }
    int fitness = EnergyFunction::evaluate(sequence);

    mainMTX.lock();
    if(fitness < overallFitness)
        overallFitness = fitness;

    overallGeneration++;
    mainMTX.unlock();
}

但是，当我添加一个简单的if语句去检查新的适应度是否比旧的适应度更小，如果是，则用新的适应度替换旧的适应度。

但是性能损失非常大！现在我每秒只能得到约20,000次评估。如果我删除随机变异部分，那么我也可以得到约20,000次评估每秒。

变量overallFitness被声明为

extern int overallFitness; 

我遇到了麻烦，无法弄清楚导致性能大幅度下降的问题是什么。比较两个int是否会花费很长时间？

此外，我不认为这与互斥锁有关。

更新

这个性能问题不是因为分支预测，而是编译器忽略了这个调用int fitness = EnergyFunction::evaluate(sequence);。

现在我添加了volatile，编译器不再忽略该调用。

同时感谢您指出了分支误判和atomic<int>，我之前不知道它们！

由于使用了原子性，我也删除了互斥部分，所以最终代码如下：

while(1) {
    sequence[distDim(mt)] = lookup_Table[dist(mt)];
    fitness = EnergyFunction::evaluate(sequence);
    if(fitness < overallFitness)
       overallFitness = fitness;
    ++overallGeneration;
}

现在我每秒获得约25,000个评估。

- TomazStoiljkovic

---

可能的原因之一是分支预测失败。 - R_Kapp

atomic<int> 可能会有帮助。 - Jarod42

实际上，编写 .lock() 和 .unlock() 是一种反模式 - 使用 lock_guard。 - Barry

@R_Kapp 实际上这可能有些相关。主要问题当然在于跨线程访问模式：不仅是读取而且实际上是写入全局变量并将更新推送到所有缓存，这只是一个性能杀手。但事实上，这比无条件更新慢得多可能与指令如何可以或不能根据该值缓存有关。 - Konrad Rudolph

如果问题根源是写全局变量（正如KonradRudolph所提到的，这非常可能），你可以通过在循环中存储本地最佳适应度，并仅在循环后更新全局适应度（如果它高于本地适应度）来解决它。 - king_nak

Answer 1

您需要运行性能分析器来找出问题的根源。在Linux上，请使用perf。

我的猜测是EnergyFunction::evaluate()被完全优化掉了，因为在前面的例子中，您没有使用结果。所以编译器可以舍弃整个函数。您可以尝试将返回值写入一个volatile变量，这应该会强制编译器或链接器不要优化调用。1000倍的速度提升绝对不是简单比较所能说明的。

- Mark Lakata

---

这可能就是原因，gcc没有使用O1或更高级别的优化选项，只是将该函数调用优化掉了。 - fireant

@Peter 对不起，Peter。我刚刚错过了你的回答 :) 我也会在我的回答中将你加入到致谢名单中。无论如何，你做得很好！ - Alex Lop.

Answer 2

实际上，有一种原子操作可以使int增加1。因此，聪明的编译器可能能够完全删除互斥锁，尽管如果它这样做我会感到惊讶。你可以通过查看汇编或删除互斥锁并将overallGeneration的类型更改为atomic ，然后检查它仍然有多快来测试这一点。在您的最后一个缓慢的示例中，此优化不再可行。

此外，如果编译器可以看到evaluate对全局状态没有影响，并且结果没有被使用，则可以跳过对evaluate的整个调用。您可以通过查看汇编或删除对EnergyFunction :: evaluate（sequence）的调用并查看计时来确定是否是这种情况-如果速度没有提高，则根本没有调用该函数。通过在不同的对象文件（其他cpp或库）中定义函数并禁用链接时间优化，应该能够防止编译器不执行EnergyFunction :: evaluate（sequence）。

还有其他影响在这里创建性能差异，但我看不到其他影响可以解释1000倍的差异。 1000倍通常意味着编译器在先前的测试中作弊，而现在的更改则防止其作弊。

- Peter

---

原子指令在这里并没有帮助（至少不是根本性的），因为更新变量仍然需要使本地核心缓存失效并将值广播到所有核心。而且这仍然是低效的（如果我记得正确，大约比本地变量读取慢1000倍）。 - Konrad Rudolph

@KonradRudolph 原子增量指令的成本可能比等待已锁定的互斥锁便宜几个数量级，后者可能是原子比较交换，然后是内核调用 - 这将根据互斥锁的实现而异。问题更多的是编译器非常小心地围绕内存屏障进行优化，因此它们很不可能触及互斥锁代码。因此，我建议的第二个选项更有可能是原因。 - Peter

所有的都是正确的，但这段代码在线程之间存在这种依赖关系的事实是一个更大的问题，在我看来，应该通过算法来解决。也就是说，通过重构代码，你可以节省更多的时间，而不仅仅是为了使用原子操作而摆脱单个互斥锁。你似乎知道自己在做什么，但很多人期望原子操作能够执行魔法，而实际上它们更像是非常便宜的互斥锁。它们并不能真正解决计算依赖关系。 - Konrad Rudolph

@KonradRudolph，你正在讨论如何优化代码的问题。问题是为什么性能会发生变化。我猜我们都同意，一个没有拥塞的互斥锁应该花费大约2个原子操作来锁定和解锁，而一个拥塞的互斥锁则要花费更多的时间，而且一个良好的设计不应该有拥塞的互斥锁。 - Peter

Answer 3

我不确定我的答案是否能解释如此剧烈的性能下降，但它肯定会对其产生影响。

在第一个情况中，您将分支添加到非关键区域：

if (dist(mt) == 0) {
    sequence[distDim(mt)] = -1;
} else {
    sequence[distDim(mt)] = 1;
}

在这种情况下，CPU（至少是IA）将执行分支预测，如果分支预测失误，则会导致性能下降-这是已知的事实。

现在关于第二个附加项，您在关键区域添加了一个分支：

mainMTX.lock();
if(fitness < overallFitness)
    overallFitness = fitness;

overallGeneration++;
mainMTX.unlock();

这反过来增加了在该区域执行的代码量，除了“错误预测”惩罚外，从而增加了其他线程需要等待 mainMTX.unlock(); 的概率。

注意

请确保所有的全局/共享资源都定义为volatile。否则编译器可能会将它们优化掉（这可能解释了在开始时如此高的评估数量）。

对于overallFitness，它可能不会被优化掉，因为它声明为extern，但overallGeneration可能会被优化掉。如果是这种情况，则可以解释在关键区域添加“真正”的内存访问后出现性能下降。

注意2

我仍然不确定我提供的解释是否可以解释如此显著的性能下降。因此，我认为代码中可能有一些实现细节你没有发布（例如volatile）。

编辑

正如Peter（@Peter）和Mark Lakata（@MarkLakata）在单独的答案中所述，并且我倾向于同意他们，最可能的原因是在第一种情况下fitness从未被使用，因此编译器优化了该变量和函数调用。而在第二种情况下，fitness被使用，因此编译器没有将其优化。Peter和Mark发现得很好！我只是错过了那一点。

- Alex Lop.

---

请确保所有全局/共享资源都被定义为volatile。互斥锁应该已经处理了这个问题，它引入了内存屏障。 - JAB

@JAB 不，互斥锁只保护共享资源，但编译器可能会将该资源从内存移动到寄存器中并进行操作。Volatile 告诉编译器不要优化该变量，并且每次访问它时，访问应在内存上执行。 - Alex Lop.

Answer 4

我意识到这不是对问题的严格回答，而是对问题的替代方案。
在代码运行时是否使用overallGeneration？也就是说，它可能用于确定何时停止计算吗？如果没有使用，您可以放弃同步全局计数器，并为每个线程设置一个计数器，在计算完成后将所有每个线程的计数器总和为总数。同样地，对于overallFitness，您可以跟踪每个线程的maxFitness，并在计算结束后选择四个结果中的最大值。
完全没有线程同步将使您获得100％的CPU利用率。

- screwnut