操作数の増加に伴うパフォーマンスの低下

Question

次の問題があります。私のコードのパフォーマンスは、操作の数に依存します！どのようにすることができますか？

#define N_MAX 1000000 

typedef unsigned int uint; 

double a[N_MAX]; 
double b[N_MAX]; 
uint n; 

int main(){ 


    for (uint i=0; i<N_MAX; i++) { 
      a[i]=(double)rand()/RAND_MAX; 
    } 


    for (uint n=100000; n<500000; n+=5000) { 

     uint time1 = time(NULL); 

     for (uint i=0; i<n;++i) 
      for (uint j=0;j<n;++j) 
        b[j] = a[j]; 

     uint time2 = time(NULL); 

     double time = double(time2-time1); 

     printf("%5d ", n); 
     printf("%5.2f %.3f\n", time, ((double)n*n/time)/1e9); 

    } 

    return 0; 
} 

そして、ここでの結果のログです：

n回-GFLOPS（=）
ここ

は私のコードです（私はopenSUSEの11.1下のgcc V 4.3.2を使用します） 200000 23.00 1.739
205000 24.00 1.751
210000 25.00 1.764
215000 26.00 1.778
220000 27.00 1.793
225000 29.00 1.746
230000 30.00 1.763
235000 32.00 1.726
240000 32.00 1.800
245000 34.00 1.765
250000 36.00 1.736
255000 37.00 1.757
260000 38.00 1.779
265000 40.00 1.756
270000 42.00 1.736
275000 44.00 1.719
280000 46.00 1.704
285000 48.00 1.692
290000 49.00 1.716
295000 51.00 1.706
300000 54.00 1.667
305000 54.00 1.723
310000 59.00 1.629
315000 61.00 1.627
320000 66.00 1.552
325000 71.00 1.488
330000 76.00 1.433
335000 79.00 1.421
340000 84.00 1.376
345000 85.00 1.400
350000 89.00 1.376
355000 96.00 1.313
360000 102.00 1.271
365000 110.00 1.211
37万121.00 1.131
375000 143.00 0.983
380000 156.00 0.926
385000 163.00 0.909

画像もありますが、新しいユーザーの制限のために投稿できません。しかしここにはlog plotがあります。

この減速の理由は何ですか？ どのようにそれを取り除く？助けてください！

Answer 1

あなたの内部ループは、毎回反復回数を増やします。計算が増えれば、自分の仕事をするのに時間がかかることが予想されます。最初に実行される100k操作、2回目の105k操作などがあります。単に時間がかかるだけです。

EDIT：明確にするために、私はそれがスポルスキはShlemiel the painter's algorithm

Answer 2

が応答をたくさんありがとうございまし呼ばれるものに見えると言ってみました！

私の期待は、時間単位あたりの操作数は同じままでなければならないという考えに基づいています。したがって、演算回数を2回増やすと、演算時間も2倍になるので、演算回数と計算時間は一定でなければなりません。これは私が会わなかったものです。 ：