c++ - 对于非常接近于零的值，双重计算运行得更慢

Question

一个 friend 要求我分享我过去一段时间偶然发现的东西。原帖摘自here .问题陈述可见here .基本上是一个算法竞赛网站。

我遇到了一个算法问题，我使用以下代码解决了这个问题:

double dp[80002][50];
class FoxListeningToMusic {
public:
    vector <double> getProbabilities(vector <int> length, int T)  {    
        memset(dp, 0, sizeof(dp));
        int n = length.size();
        for(int i = 0; i < n; i++)
            dp[0][i] = 1.0 / (double)n;

        double mul = 1.0 / (double)n;
        int idx ;
        for(int i = 1; i <= T; i++) {
            for(int j = 0; j < n; j++)  {
                idx = i - length[j];
                if(idx >= 0)  {
                    for(int k = 0; k < n; k++)
                        dp[i][k] += mul * dp[idx][k];
                }
                else
                    dp[i][j] += mul;
                }
            }
        }

        vector<double> v(n);
        for(int i = 0; i < n; i++)
            v[i] = dp[T][i];
        return v;
    }

};

代码是否以正确答案解决问题并不重要，至少对于我将要讨论的内容而言。事实是我对这段代码有时间限制(这意味着它在某些测试用例上执行了超过 2 秒)。这是意料之中的，因为这里的复杂度是 O(T * length.size() ^ 2)，如果我们考虑问题约束，它会变为 2 * 10⁸。然而，有趣的是我特别在时间限制内测试了我的解决方案。我使用的情况似乎是我的解决方案的“最坏情况”:长度为 50 个 1，T = 80000。代码运行了 0.75 秒。这远低于 2 秒的时间限制。

我说我使用的情况是最坏的情况，因为将要执行的指令数仅取决于内部 for 中的分支条件 idx >= 0。如果为真，则再执行一个循环(该循环的复杂度为 O(n))。在另一种情况下，只会执行单个操作 O(1)。正如您所看到的，元素的长度越少，这种情况出现的次数就越多。

尽管有这种推理，但在测试以下情况后我的问题还是失败了:

length = {1, 1, 1, 1, 3, 3, 3, 3, 1, 3, 3, 2, 3, 2, 3, 3, 1, 2, 3, 1, 2, 3, 2,
          1, 3, 1, 1, 1, 2, 3, 2, 3, 2, 2, 1, 3, 1, 1, 3, 1, 3, 1, 3, 2, 3, 1,
          1, 3, 2, 76393} T= 77297.
For this case my program runs for 5.204000 seconds.

我的第一个假设是，运行时测量值出现这种意外比率的原因(只要我们应该预期在第一种情况下要执行的处理器指令要少得多)是处理器以某种方式缓存了类似的计算:在我的例如，计算关于长度的所有元素是对称的，真正聪明的处理器可以使用它来避免重复相同的指令序列。所以我尝试编写另一个示例:这次在长度数组中使用不同的值:

length = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
          21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38,
          39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 77943}
T=80000 runs for  0.813000 seconds. 

在这个例子之后，我不能再说这些时间测量是怎么来的——我的第二个例子似乎需要比我失败的测试更多的处理器指令，并且不允许我认为在第一个例子中发生的缓存。实际上我还不能确定这种行为的原因，但我很确定它应该与处理器缓存或传送带有关。我很好奇这些实验在不同芯片组上的表现如何，请随时在这里发表评论。

此外，如果有人比我更了解硬件并且他/她可以解释这种行为，我们将不胜感激。

在那之前，我应该为自己做一个笔记 - 在估计算法复杂性时不要低估处理器优化。有时，它们似乎会显着降低/提高特定示例的摊销速度。

Answer 1

这种奇怪行为的原因原来是 denormal numbers .使用代码将此类数字视为纯零可以极大地加快我在此类极端情况下的代码速度。

提示:在这种情况下，非正规数是非常接近于零的数字(例如，10^-38 表示 float ；由@PascalCuoq 修正)。对于这样的数字，处理器的处理速度会变慢很多，因为:(取自维基百科):

Some systems handle denormal values in hardware, in the same way as normal values. Others leave the handling of denormal values to system software, only handling normal values and zero in hardware. Handling denormal values in software always leads to a significant decrease in performance.

编辑 我还发现了this suggestion关于如何检查数字是否异常。