私がテスト結果を公開した後、友达も他のテストをしました.テストではint配列を使っていましたが、分析してArray.がわかりました.Sortはint配列に対して特別な最適化がある.そこで、ある友人はいくつかの参照タイプの配列を使って並べ替え、Arrayを得た.Sortメソッドの性能はLINQソートに遅れている--テスト方式の問題のため、この結果と結論はあまり適切ではないが.しかし、議論の過程で、他の条件が変わらない場合、参照タイプのフィールドが多いほど、Array.Sortメソッドにかかる時間は長くなります.今回はこの問題について話し合いましょう.

パフォーマンステスト

フィールド数とソート時間の相関を表すために、まずEmitを使用して一定数のフィールドを生成する方法を構築します.

public abstract class TypeBase
{
    public int ID;
}

class Program
{
    public static ModuleBuilder moduleBuilder = null;

    static Program()
    {
        var assemblyName = new AssemblyName { Name = "SomeAssembly" };

        var domain = Thread.GetDomain();
        var asmBuilder = domain.DefineDynamicAssembly(
            assemblyName, AssemblyBuilderAccess.Run);

        moduleBuilder = asmBuilder.DefineDynamicModule("SomeModule");
    }

    static Type CreateType(int numberOfField)
    {
        var typeName = "TypeWith$" + numberOfField + "$Fields";
        var typeBuilder = moduleBuilder.DefineType(
            typeName, TypeAttributes.Class, typeof(TypeBase));

        for (int i = 0; i < numberOfField; i++)
        {
            typeBuilder.DefineField("Field$" + i, typeof(int), FieldAttributes.Public);
        }

        return typeBuilder.CreateType();
    }
}

便宜上、各ダイナミックタイプに統一されたTypeBaseクラスを継承させます.これにより、ソートのターゲットをTypeBase配列とすることができ、コンパレータとしてのTypeBaseComparerもIDフィールドに直接アクセスすることができます.次に、テスト用の方法を示します.

static void Main(string[] args)
{
    CodeTimer.Initialize();

    var random = new Random(DateTime.Now.Millisecond);
    var array = Enumerable.Repeat(0, 1000 * 500).Select(_ => random.Next()).ToArray();

    for (var num = 1; num <= 512; num *= 2)
    {
        var type = CreateType(num);
        var arrayToSort = new TypeBase[array.Length];

        for (var i = 0; i < array.Length; i++)
        {
            var instance = (TypeBase)Activator.CreateInstance(type);
            instance.ID = array[i];
            arrayToSort[i] = instance;
        }

        CodeTimer.Time(
            String.Format("Type with {0} fields (Array.Sort)", num),
            10, () => Sort(CloneArray(arrayToSort)));

        CodeTimer.Time(
            String.Format("Type with {0} fields (ArraySorter)", num),
            10, () => ArraySorter(CloneArray(arrayToSort)));
    }

    Console.ReadLine();
}

static void Sort(TypeBase[] array)
{
    Array.Sort(array, new TypeBaseComparer());
}

static void ArraySorter(TypeBase[] array)
{
    new ArraySorter<TypeBase>().OrderBy(a => a.ID).Sort(array);
}

比較では、1つのフィールドのタイプから、フィールドの数を512フィールドに倍増させるたびにテストします.獲得は誇張されていますが、実験にとって、差が明らかになることを望んでいます.アーリーと言った以上Sortの性能はオブジェクトの体積の影響を受けるのが比較的に明らかで、LINQの並べ替えは比較的に安定で、それでは私達はArrayを比較しにきます.SortやLINQソートと同様のArraySorterの実行時間を実現しましょう.2つのソート方法に加えて、同じ数、同じタイプ、同じ初期順序、および同じ「比較基準」の条件が完全に同じであることに注意してください.
テスト結果は次のとおりです.
グラフとして描画:
図から明らかな違いがわかる.フィールド数が少ない場合、Array.SortのパフォーマンスはArraySorterよりも高く、これまでのテスト結果と一致しています.しかし、フィールド数が4つを超えると、ArraySorterのパフォーマンスがリードし始め、フィールド数の増加に伴って両者の差が大きくなります.そのため、私たちの前の観点は正しいです.
これはなぜですか.以下の内容を読むときは、まず自分で考えたほうがいいですか?

原因分析

実はこれはやはり「局所性」に関する問題です.局所性は性能に影響を与える非常に主要な要素の一つであり、私もこれまでこの問題について何度も話したことがありません.では、ここでは、局所性がソート効率にどのように影響するのでしょうか.重要なのはコンパレータです.

public class TypeBaseComparer : IComparer<TypeBase>
{
    public int Compare(TypeBase x, TypeBase y)
    {
        return x.ID - y.ID;
    }
}

TypeBaseComparerの実装は非常に簡単で,2つのTypeBaseオブジェクトのID値を減算するだけである.明らかに、システムはこのプログラムを実行する時、xあるいはyのアドレスとIDフィールドのオフセット量から1つのアドレスを計算して、それからデータを読み出します.しかし、CPUは、あるアドレスのデータを読み込む際に、「1本」のデータを同時にロードしてキャッシュすることで、近くのデータを再び読み出す際により速く見えることがわかります.そこで考えてみると,CPUにとってキャッシュおよび各エントリのサイズは変わらないため,オブジェクトの体積が増えるにつれてキャッシュ中に同時に存在できるオブジェクトの数が少なくなり,読み出し回数は変わらないがキャッシュのヒット率は低下する.すると、オブジェクトのボリュームが大きくなり、ソートにかかる時間も増加します.
しかし、ArraySorterにとっては全く違います.ArraySorterの実装メカニズムによれば、keySelectorに基づいてまずソートフィールドが得られます.前例ではint値であり、IndexComparerはソート時にint配列を保存し、ソート時に使用します.したがって,オブジェクトのボリュームにかかわらず,ソート時にArraySorterは常に非常にコンパクトなint配列にアクセスしているだけである.ソートが終了すると、ArraySorterはオブジェクトのボリュームに関係なく、オブジェクトリファレンスを操作するだけです.ソートの他の条件は変わらないため、オブジェクトのボリュームが大きくなる(ローカル性が低下する)ことは、最終的にはkeySelectorが動作するときに速度が遅くなるだけで、他の部分は影響を受けません.当然ある時点からArraySorterの性能はArrayを上回る.Sort、そして両者の差はますます大きくなります.
今話している内容がよく分からない場合は、「局所性」に関する内容を理解し、LINQソートやArraySorterの実装方法を理解することができます.

まとめ

見えるよSortとArraySorterの性能の高低は一言でははっきり言えないが、実際の条件の下でどの方法を選ぶのがもっと優位であるかは容易に確定することではない.しかし、私たちは本当に性能をここまで追求する必要がありますか?実際、ほとんどの実際の開発過程で、この性能の差は微々たるものと言えると信じています.システムに付属するArray.SortメソッドおよびLINQソートは,実際には明らかな代替関係を持たない.実はある特定の时、あなたは実は両者の间にも1つの条件に合っていることに気づくことができます--あまり考えないで、使いましょう.
もちろん、いくつかの明らかな間違いは避ける必要があります.たとえば、コンパレータでデータベースに繰り返しアクセスすると、これが自分の問題です.
また、この文章はテストと分析に重点を置いていますが、「局所性」に関するデータを直感的に観察できれば、問題を説明できるのではないでしょうか.では、実験を通じてそれを証明する方法はありますか?この問題も実は大きくない.例えば、Visual Studio 2008のProfilerを使用する場合、L 2 Cacheの状況を同時に監視することができます.この実験の設計と実行はご自身にお任せしましょう.
このいくつかの文章を経て、あなたは正しいです.NETフレームワークのソートクラスライブラリには、何か疑問がありますか?
この文書のコード:http://gist.github.com/288765

関連記事

配列並べ替え方法の性能比較(1):注意事項及び試験

配列並べ替え方法の性能比較(2):Array.Sort実装解析

配列並べ替え方法の性能比較(3):LINQ並べ替え実現分析

配列並べ替え方法の性能比較(4):LINQ方式のArray並べ替え

配列並べ替え方法の性能比較(5):オブジェクトサイズと並べ替え性能