[解決済み】ソートされた配列の処理が、ソートされていない配列より遅いのはなぜですか？

質問

500000個のランダムに生成されたリストがあります。 Tuple<long,long,string> オブジェクトに対して、単純な "between" 検索を実行します。

var data = new List<Tuple<long,long,string>>(500000);
...
var cnt = data.Count(t => t.Item1 <= x && t.Item2 >= x);

ランダムな配列を生成し、ランダムに生成された100個の値に対して検索を実行すると x の場合、4秒程度で検索が完了します。を知っていること ソートが検索に与える大きな効果 しかし、私はデータをソートすることにしました。 Item1 で、次に Item2 であり、最後に Item3 - を実行する前に、100回の検索を行いました。分岐予測により、ソートされたバージョンの方が少し速く実行されると予想していました。 Item1 == x をチェックし、さらに t.Item1 <= x は、そのブランチを正しく "no take" と予測し、探索の末尾部分を高速化します。驚いたことに ソートされた配列の場合、検索にかかる時間は2倍になります。 !

実験の順番を入れ替えたり、乱数生成器の種を変えてみたりしましたが、効果は同じでした。ソートされていない配列での検索は、ソートされている同じ配列での検索の約2倍の速さで走りました

この不思議な効果について、どなたか良い説明をお持ちの方はいらっしゃいませんか？私のテストのソースコードは以下の通りです。.NET 4.0を使用しています。

private const int TotalCount = 500000;
private const int TotalQueries = 100;
private static long NextLong(Random r) {
    var data = new byte[8];
    r.NextBytes(data);
    return BitConverter.ToInt64(data, 0);
}
private class TupleComparer : IComparer<Tuple<long,long,string>> {
    public int Compare(Tuple<long,long,string> x, Tuple<long,long,string> y) {
        var res = x.Item1.CompareTo(y.Item1);
        if (res != 0) return res;
        res = x.Item2.CompareTo(y.Item2);
        return (res != 0) ? res : String.CompareOrdinal(x.Item3, y.Item3);
    }
}
static void Test(bool doSort) {
    var data = new List<Tuple<long,long,string>>(TotalCount);
    var random = new Random(1000000007);
    var sw = new Stopwatch();
    sw.Start();
    for (var i = 0 ; i != TotalCount ; i++) {
        var a = NextLong(random);
        var b = NextLong(random);
        if (a > b) {
            var tmp = a;
            a = b;
            b = tmp;
        }
        var s = string.Format("{0}-{1}", a, b);
        data.Add(Tuple.Create(a, b, s));
    }
    sw.Stop();
    if (doSort) {
        data.Sort(new TupleComparer());
    }
    Console.WriteLine("Populated in {0}", sw.Elapsed);
    sw.Reset();
    var total = 0L;
    sw.Start();
    for (var i = 0 ; i != TotalQueries ; i++) {
        var x = NextLong(random);
        var cnt = data.Count(t => t.Item1 <= x && t.Item2 >= x);
        total += cnt;
    }
    sw.Stop();
    Console.WriteLine("Found {0} matches in {1} ({2})", total, sw.Elapsed, doSort ? "Sorted" : "Unsorted");
}
static void Main() {
    Test(false);
    Test(true);
    Test(false);
    Test(true);
}

Populated in 00:00:01.3176257
Found 15614281 matches in 00:00:04.2463478 (Unsorted)
Populated in 00:00:01.3345087
Found 15614281 matches in 00:00:08.5393730 (Sorted)
Populated in 00:00:01.3665681
Found 15614281 matches in 00:00:04.1796578 (Unsorted)
Populated in 00:00:01.3326378
Found 15614281 matches in 00:00:08.6027886 (Sorted)

解決方法は？

ソートされていないリストを使用する場合、すべてのタプルにアクセスするのは メモリオーダー . これらはRAM上に連続的に割り当てられています。CPU はメモリに順次アクセスするのが好きです。なぜなら、次のキャッシュラインを推測で要求することができるので、必要なときに常に存在することになるからです。

リストをソートするときは、リストを ランダムオーダー なぜなら、ソートキーはランダムに生成されるからです。これは、タプルのメンバーへのメモリアクセスが予測不可能であることを意味します。CPUはメモリをプリフェッチできないので、タプルへのアクセスはほとんどすべてキャッシュミスになります。

の具体的な利点がよくわかる例です。 GCメモリ管理 一緒に割り当てられ、一緒に使用されるデータ構造は、非常にうまく機能します。これらは素晴らしい <強い 参照の局所性 .

キャッシュミスによるペナルティ 保存された分岐予測のペナルティを上回る この場合

に切り替えてみてください。 struct -タプルです。これにより、タプルのメンバにアクセスするために実行時にポインタを参照する必要がなくなるため、パフォーマンスが回復します。

Chris Sinclairは、コメントで次のように指摘しています。 TotalCountが10,000以下の場合、ソートされたバージョンはより高速に処理されます。 となります。これは、小さなリスト CPUキャッシュに完全に収まる . メモリアクセスは予測できないかもしれませんが、ターゲットは常にキャッシュの中にあります。キャッシュからのロードにもサイクルがかかるので、若干のペナルティはあると思います。しかし、これは問題ではないようです。 CPUは複数の未解決のロードを処理できる その結果、スループットが向上しました。CPUはメモリ待ちの状態になると、できるだけ多くのメモリ操作をキューに入れるために、命令ストリームを先に進めます。この技術は、レイテンシーを隠すために使用されます。

このような動作は、最近のCPUの性能を予測することがいかに難しいかを物語っています。という事実があります。 わずか2倍遅くなる シーケンシャルメモリからランダムメモリにアクセスするとき、メモリレイテンシを隠すためにどれだけのことが隠されているのかがわかります。メモリアクセスは、50～200サイクルの間、CPUをストールさせることができます。この数字を考えると、ランダムメモリアクセスを導入した場合、プログラムは10倍遅くなることが予想されます。