c# - ソート済み/未ソートの異なるサイズの配列での分岐予測

Question

私はずっと前にこの質問に出くわしました

並べ替えられた配列の処理が、並べ替えられていない配列の処理よりも速いのはなぜですか?

自分で試してみたいと思いました。さまざまな配列サイズを試してみると、驚くべき結果が得られました。

これがテストコードです。(Microsoftコンパイラを使用したC#、他の言語はテストしていません)

static void Main(string[] args)
{
    var rand = new Random();
    Time(rand, true, 1000, 100000);
    Time(rand, false, 1000, 100000);
    Time(rand, true, 1000000, 100);
    Time(rand, false, 1000000, 100);
    Console.ReadKey(true);
}

static void Time(Random rand, bool sort, int arraysize, int loopsize)
{
    var stopwatch = new Stopwatch();

    var array = new int[arraysize];
    array = Array.ConvertAll(array, _ => (int)(rand.NextDouble() * int.MaxValue));

    if (sort)
        Array.Sort(array);

    stopwatch.Start();

    var count = 0;
    for (var j = 0; j < loopsize; j++)
        for (var i = 0; i < array.Length; i++)
            if (array[i] > int.MaxValue / 2)
                count++;

    stopwatch.Stop();

    Console.WriteLine("{0} ticks, {1}ms, sort {2}, arraysize {3}, loopsize {4}",
        stopwatch.ElapsedTicks, stopwatch.ElapsedMilliseconds, sort, arraysize, loopsize);
}

これが出力です。

614149 ticks, 262ms, sort True, arraysize 1000, loopsize 100000
630096 ticks, 269ms, sort False, arraysize 1000, loopsize 100000
634562 ticks, 271ms, sort True, arraysize 1000000, loopsize 100
1840846 ticks, 787ms, sort False, arraysize 1000000, loopsize 100

相対的な結果のタイミングは、通常、リリース モードとデバッグ モードで同じです (デバッグは約 2 倍遅くなります)。

最後の 2 つの結果は、私にとっては理にかなっています。上記でリンクした質問のロジックに従い、ソートされたものは、分岐予測であると想定しているため、より高速に実行されます。ただし、最初の 2 つの結果には混乱しています。なぜほぼ同じ時間なのですか？また、最後の 2 つよりも大幅に高速ではないのはなぜですか? 配列が小さいほど、より近いキャッシュに配置されるため、全体がより高速に実行されると思います。(ループ サイズ * 配列サイズ = 最初の 2 つと最後の 2 つの間で一定であるため、内側の反復回数は同じです)