对于非常接近零的值,双重计算运行速度要慢得多

Question

朋友要求我分享过去一段时间我偶然发现的事情.原帖是从这里获取的.问题陈述可以在这里找到.基本上是算法竞赛的网站.

我被解决了使用以下代码解决的算法问题:

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

这种奇怪行为的原因被证明是非正规数.将代码视为纯零的代码将代码极大地加到了我的代码上.

提示:在这种情况下,非正规数字是非常接近于零的数字(例如浮点数为10 ^-38 ;由于@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.

EDIT I also found this suggestion on SO how you can check if the number became denormal.