246

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

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

ランダムな配列を生成し、ランダムに生成された の値を 100 個検索するとx、検索は約 4 秒で完了します。しかし、並べ替えが検索にもたらすすばらしい驚異を知っていたので、100 回の検索を実行する前に、最初にItem1で、次にItem2で、最後に で、データを並べ替えることにしました。Item3分岐予測のおかげで、ソートされたバージョンの方が少し速く実行されると思っていました。私の考えでは、 のポイントに到達すると、Item1 == xそれ以降のすべてのチェックでt.Item1 <= x分岐が「ノーテイク」として正しく予測され、テール部分が高速化されます。探す。驚いたことに、ソートされた配列では検索に 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)
4

2 に答える 2

280

ソートされていないリストを使用している場合、すべてのタプルはmemory-orderでアクセスされます。それらは RAM に連続して割り当てられています。CPU は、次のキャッシュ ラインを投機的に要求できるため、必要なときに常に存在するように、メモリに順次アクセスするのが大好きです。

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

これは、 GC メモリ管理の特定の利点の良い例です。一緒に割り当てられ、一緒に使用されるデータ構造は非常にうまく機能します。彼らは参照の大きな局所性を持っています。

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

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

Chris Sinclair はコメントで、「TotalCount が約 10,000 以下の場合、ソートされたバージョンの方が高速に実行される」と述べています。これは、小さなリストが CPU キャッシュに完全に収まるためです。メモリ アクセスは予測できない場合がありますが、ターゲットは常にキャッシュにあります。キャッシュからのロードでも数サイクルかかるため、まだわずかなペナルティがあると思います。しかし、 CPU は複数の未処理の負荷を処理できるため、問題にはならないようです。これにより、スループットが向上します。CPU がメモリの待機に到達するたびに、命令ストリームを先に進めて、できるだけ多くのメモリ操作を待ち行列に入れます。この手法は、レイテンシを隠すために使用されます。

この種の動作は、最新の CPU のパフォーマンスを予測することがいかに難しいかを示しています。シーケンシャル メモリ アクセスからランダム メモリ アクセスに移行する場合に2 倍しか遅くないという事実は、メモリ レイテンシを隠すために内部でどれだけのことが行われているかを示しています。メモリ アクセスは、CPU を 50 ～ 200 サイクル停止させる可能性があります。まず、ランダム メモリ アクセスを導入すると、プログラムが 10 倍以上遅くなることが予想されます。

于 2012-12-24T17:37:34.120 に答える
4

LINQ は、リストが並べ替えられているかどうかを認識していません。

述語パラメータを持つカウントはすべての IEnumerables の拡張メソッドであるため、効率的なランダム アクセスでコレクションを実行しているかどうかもわからないと思います。したがって、すべての要素を単純にチェックし、Usrはパフォーマンスが低下した理由を説明しました。

ソートされた配列 (二分探索など) のパフォーマンス上の利点を活用するには、もう少しコーディングを行う必要があります。

于 2012-12-25T15:43:35.543 に答える