3

誰かが私に質問しました: 以下の 2 つのシナリオの中でどちらが最速ですか:

ケース 1: int count = 0 と仮定します。

for (int i = 0; i < 10; i++)
{
    for (int j = 0; j < 5; j++)
    {
        count++;
    }
}

ケース 2: int count = 0 と仮定します。

for (int i = 0; i < 5; i++)
{
    for (int j = 0; j < 10; j++)
    {
        count++;
    }
}

どちらのシナリオでも、count の最終値は 50 になります。しかし、どちらが速いかわかりません。CASE IIの方が速いと思いますが、よくわかりません...

誰かがそれに光を当てることができれば素晴らしいことです。どちらが速いですか、そしてその理由は何ですか?

4

5 に答える 5

10

これは私が考えることができる唯一の例です。どの変数をどこで反復するかが重要です

int array[n][m];
//fast
for (int i=0;i<n;i++)
{ for(int j=0;j<m;j++)
  { count+=array[i][j];
  }
}
//slow
for (int i=0;i<m;i++)
{ for(int j=0;j<n;j++)
  { count+=array[j][i];
  }
}

2 番目の方法は、メモリ内の場所を順番に反復するのではなく、一度に場所ごとにジャンプするため、処理が遅くなりますm。プロセッサは、アクセスされた場所の直後に配置されたメモリ場所をキャッシュします。

于 2012-08-16T12:05:41.360 に答える
4

さて、私のシステムでこれをテストしました。完全な最適化により、コンパイラーは質問なしでカウント = 50 を作成しました。最適化を行わない場合、通常は 2 番目のバージョンがわずかに高速でしたが、まったく無視できる程度でした。

逆アセンブル: 両方のループのコードはまったく同じですが、比較が 100 で 1 回、50 で 1 回です (実行時間を長くできるように、数値を少し上げました)。

    for(int i = 0; i< 100; i++) {
00F9140B  mov         dword ptr [i],0  
00F91412  jmp         main+5Dh (0F9141Dh)  
00F91414  mov         eax,dword ptr [i]  
00F91417  add         eax,1  
00F9141A  mov         dword ptr [i],eax  
00F9141D  cmp         dword ptr [i],64h  
00F91421  jge         main+88h (0F91448h)  

        for(int j = 0; j< 50; j++)
00F91423  mov         dword ptr [j],0  
00F9142A  jmp         main+75h (0F91435h)  
00F9142C  mov         eax,dword ptr [j]  
00F9142F  add         eax,1  
00F91432  mov         dword ptr [j],eax  
00F91435  cmp         dword ptr [j],32h  
00F91439  jge         main+86h (0F91446h)  
        {
            count++;
00F9143B  mov         eax,dword ptr [count]  
00F9143E  add         eax,1  
00F91441  mov         dword ptr [count],eax  
        }
00F91444  jmp         main+6Ch (0F9142Ch)  
    }
00F91446  jmp         main+54h (0F91414h)

外側の大きなループ、内側の小さなループ、内側の小さなループ、外側の大きなループの唯一の違いは、ジャンプを行う頻度です。

00F91439  jge         main+86h (0F91446h)  
to
00F91446  jmp         main+54h (0F91414h)

そして、ループ変数の初期化:

00F91423  mov         dword ptr [j],0  
00F9142A  jmp         main+75h (0F91435h)

以下の部分をスキップしながら、新しいループごとに。

00F9142C  mov         eax,dword ptr [j]  
00F9142F  add         eax,1  
00F91432  mov         dword ptr [j],eax

内側のループの反復ごとに追加のコマンド: mov、add、mov、ただし mov / jmp はありません

初期化された各内部ループの追加コマンド: mov、jmp、および多くの場合、JGE を true にします。

したがって、内側のループを 50 回実行すると、その JGE は 50 回しか成立しないため、そこで 50 回のジャンプを行いますが、内側のループを 100 回実行すると、100 回ジャンプする必要があります。それがコードの唯一の違いです。この場合、それはほとんど違いがなく、ほとんどの場合、メモリアクセスがループの順序よりも多くの速度低下を引き起こしていることに遭遇します。唯一の例外: 分岐予測を回避するためにループを適切に並べ替えることができることがわかっている場合。したがって、ループをどちらかの方法で順序付けする価値があるのは、次の 2 つです。

-メモリアクセス

-分岐予測

それ以外の場合、影響はまったく無視できます。

于 2012-08-16T12:07:08.867 に答える
1

実際、そのような詳細について自分自身を最適化しようとすることは、一般的には良い考えではありません。ほとんどの場合、(アルゴリズムが変更されていない限り) コンパイラの方がはるかに優れているからです。

ループ数は同じです。

2 番目のループの初期化が 10 回ではなく 5 回しか行われないため、2 番目のループの方が少し速いかもしれませんが、実際に顕著な変化が得られるとは思えません。

最良の方法は、プロファイラーを使用することです。生成されたアセンブリ コードを分析することもできます。

于 2012-08-16T12:05:32.513 に答える
1

本当に知りたい場合は、外側のループを最大ループ数 (5 または 10) の単一パラメーターを持つ関数にし、内側のループを最大内側ループ数 (10 または 5) の単一パラメーターを取る関数にします。次に、最適化なしでコンパイルし、両方を100万回実行して、時間を計ります。

最適化を行うと、コンパイラは関数をインライン化し、ループを展開しcount、最適化プロセスの一部として計算します。私の推測では、両者はまったく同じ量の作業を行い、まったく同じ時間を見ることになるでしょう。

于 2012-08-16T12:05:52.297 に答える
1

実際に試してみましたか？

理論的には、ケース I の場合よりも外側のループにスタックベースの変数の作成/破棄が半分しかないため、ケース II の方がわずかに高速であると想定しますが、さらに優れた (そしてより明確な) ものは次のとおりです。

for(int k = 0; k < 50; k++)
{
     count++;
}

正確には、あなたの例は非常に抽象化されているため、答えはおそらくほとんど役に立ちません。それは文脈に大きく依存します。

于 2012-08-16T12:05:57.883 に答える