奇怪的执行时间

Question

问题是关于在各种输入大小的执行时间序列中获得一些不连续性.具体来说,我一直在尝试这段代码:

long double a[2000][2000];
int iter = 0;
int main(int argc, char const *argv[]){
    istringstream is(argv[1]);
    int N;
    is >> N;
    for(int i = 0; i <= N; ++i){
        for (int J = 0; J <= N; ++J){
            a[i][J]  = (rand()%3+1)*(rand()%4+1);
        }
    }
    clock_t clk= clock();
    for(int k = 0; k < N; ++k){
        for(int i = k+1; i < N; ++i){
            a[i][k] = a[i][k]/a[k][k];
        }
        for(int i = k+1; i < N; ++i){
            for(int j = k+1; j < N; ++j){
                iter++;
                a[i][j] = a[i][j] - a[i][k]*a[k][j];
            }
        }
    }
    clk = clock() - clk;
    cout << "Time: " << ((double)clk)/CLOCKS_PER_SEC << "\n";
    cout << iter << endl;
}

使用g ++ 5.4.1进行C++ 14编译.

我尝试了各种N值的代码.然而,在N = 500附近发生了一些非常奇怪的事情.下面列出了执行时间.(这些是N的各种值的代码输出.

N = 200 : 0.022136
N = 300 : 0.06792
N = 400 : 0.149622
N = 500 : 11.8341
N = 600 : 0.508186
N = 700 : 0.805481
N = 800 : 1.2062
N = 900 : 1.7092
N = 1000 : 2.35809

我尝试N = 500很多次,也在另一台机器上尝试获得类似的结果.

大约500我们有以下内容:

N = 494 : 0.282626
N = 495 : 0.284564
N = 496 : 11.5308
N = 497 : 0.288031
N = 498 : 0.289903
N = 499 : 11.9615
N = 500 : 12.4032
N = 501 : 0.293737
N = 502 : 0.295729
N = 503 : 0.297859
N = 504 : 12.4154
N = 505 : 0.301002
N = 506 : 0.304718
N = 507 : 12.4385

为什么会这样？

Answer 1

您的程序可能存在浮点溢出和运算，在某些情况下会导致 NaN（如果计算结果为无穷大/NaN，则它会为您的算法扩展，因此几乎所有数字都会变成无穷大/NaN。这取决于rand()\ 的输出. 如果您使用 更改种子srand()，则可能不会导致速度减慢N=500）。

\n\n

而且，因为您使用long double，所以编译的程序使用 FPU（如果您针对 FPU 而不是 SSE 进行编译，您也可以使用float或重现此内容）。double看起来，FPU 处理无限数的速度比正常数慢得多。

\n\n

您可以使用以下代码片段轻松重现此问题：

\n\n

int main() {\n    volatile long double z = 2;\n\n    for (int i=0; i<10000000; i++) {\n        z *= z;\n    }\n\n    return z;\n}\n

\n\n

如果你使用 2 z，这个程序运行缓慢（z会溢出）。如果你把它替换为1，它会变得很快（z不会溢出）。

\n\n

您可以在这里阅读更多相关信息：https://randomascii.wordpress.com/2012/05/20/thats-not-normalthe-performance-of-odd-floats/

\n\n

这是相关部分：

\n\n

\n

对 x87 FPU 的性能影响

\n\n

Intel\xe2\x80\x99s x87 单元在这些 NaN 和无穷大上的性能非常糟糕。[...] 即使在今天，在 SandyBridge 处理器上，x87 FPU\n 也会导致NaN 和无穷大的速度减慢约 370 比 1。

\n

\n