21

私のC＃アプリケーションのプロファイリングは、にかなりの時間が費やされていることを示しましたList<T>.AddRange。Reflectorを使用してこのメ​​ソッドのコードを確認すると、List<T>.InsertRange次のように実装されたコードが呼び出されることがわかりました。

public void InsertRange(int index, IEnumerable<T> collection)
{
    if (collection == null)
    {
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.collection);
    }
    if (index > this._size)
    {
        ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_Index);
    }
    ICollection<T> is2 = collection as ICollection<T>;
    if (is2 != null)
    {
        int count = is2.Count;
        if (count > 0)
        {
            this.EnsureCapacity(this._size + count);
            if (index < this._size)
            {
                Array.Copy(this._items, index, this._items, index + count, this._size - index);
            }
            if (this == is2)
            {
                Array.Copy(this._items, 0, this._items, index, index);
                Array.Copy(this._items, (int) (index + count), this._items, (int) (index * 2), (int) (this._size - index));
            }
            else
            {
                T[] array = new T[count];          // (*)
                is2.CopyTo(array, 0);              // (*)
                array.CopyTo(this._items, index);  // (*)
            }
            this._size += count;
        }
    }
    else
    {
        using (IEnumerator<T> enumerator = collection.GetEnumerator())
        {
            while (enumerator.MoveNext())
            {
                this.Insert(index++, enumerator.Current);
            }
        }
    }
    this._version++;
}

private T[] _items;

インターフェイスの単純さ（InsertRangeのオーバーロードが1つしかない）は、ランタイムタイプのチェッキングとキャストのパフォーマンスオーバーヘッドを正当化すると主張することができます。しかし、私が示した3つの線の背後にある理由は何(*)でしょうか？私はそれをより速い代替案に書き直すことができると思います：

is2.CopyTo(this._items, index);

この単純で明らかに高速な代替手段を使用しない理由はありますか？

編集：

答えてくれてありがとう。したがって、コンセンサスの意見は、これは、CopyToを欠陥のある/悪意のある方法で実装する入力コレクションに対する保護手段であるというものです。私には、1）ランタイムタイプチェック2）一時配列の動的割り当て3）コピー操作を2倍にするという代償を絶えず支払うのはやり過ぎのように思えますが、InsertRangeの2つ以上のオーバーロードを定義することでこれをすべて節約できたはずです、1つIEnumerableは現在のように取得し、2つ目は取得しList<T>、3つ目は取得しT[]ます。後の2つは、現在の場合の2倍の速度で実行するように実装できます。

編集2：

T []引数を取るAddRangeのオーバーロードも提供することを除いて、Listと同じクラスFastListを実装しました。この過負荷は、動的な型の検証や要素の二重コピーを必要としません。最初は空だったリストに4バイト配列を1000回追加することにより、このFastList.AddRangeをList.AddRangeに対してプロファイリングしました。私の実装は、標準のList.AddRangeの速度を9倍（9！）で上回っています。List.AddRangeは、アプリケーションの重要な使用シナリオの1つでランタイムの約5％を占めます。リストを、より高速なAddRangeを提供するクラスに置き換えると、アプリケーションのランタイムが4％向上する可能性があります。

4

3 に答える 3

12

それらは、実装がICollection<T>挿入の範囲外の宛先リストのインデックスにアクセスすることを妨げています。上記の実装はIndexOutOfBoundsException、の障害のある（または「操作的な」）実装CopyToが呼び出された場合に発生します。

T[].CopyToこれは文字通り内部的にとして実装されてmemcpyいるため、その行を追加することによるパフォーマンスのオーバーヘッドはわずかであることに注意してください。膨大な数の通話に安全性を追加するコストが非常に低い場合は、そうすることをお勧めします。

編集：私が奇妙だと思う部分は、への呼び出しICollection<T>.CopyTo（一時配列へのコピー）がへの呼び出しの直後に発生しないという事実ですEnsureCapacity。その場所に移動された場合、同期例外の後、リストは変更されません。現状では、この条件は、リストの最後に挿入が行われた場合にのみ成立します。ここでの理由は次のとおりです。

  • リスト要素を変更する前に、必要なすべての割り当てが行われます。
  • の呼び出しArray.Copyは失敗することはありません。
    • メモリはすでに割り当てられています
    • 境界はすでにチェックされています
    • ソース配列と宛先配列の要素タイプが一致する
    • C++のように使用される「コピーコンストラクタ」はありません-それは単なるmemcpyです
  • 例外をスローできる唯一の項目はICollection.CopyTo、リストのサイズ変更と一時配列の割り当てに必要な外部呼び出しと割り当てです。挿入のために要素を移動する前にこれらの3つすべてが発生した場合、リストを変更するトランザクションは同期例外をスローできません。
  • 最後の注意：これは厳密に例外的な動作に対処します-上記の理論的根拠はスレッドセーフを追加しません。

編集2（OPの編集への応答）：これをプロファイルしましたか？あなたは、Microsoftがより複雑なAPIを選択すべきだったという大胆な主張をしているので、現在の方法が遅いという主張が正しいことを確認する必要があります。のパフォーマンスに問題があったことは一度もありません。InsertRange誰かが直面するパフォーマンスの問題は、動的リストを再実装するよりも、アルゴリズムを再設計する方がうまく解決されると確信しています。私をネガティブな方法で過酷だと思わないように、次の点に注意してください。

  • 四角い車輪を再発明したい開発チームの人々に耐えられないようにしたくありません。
  • チームのメンバーに潜在的なパフォーマンスの問題を気にかけ、コードが持つ可能性のある副作用について質問してもらいたいと思います。この点は、存在する場合に勝ちますが、人々が質問をしている限り、私は彼らに彼らの質問を確かな答えに変えるように駆り立てます。最初は悪い考えのように見えることによって、アプリケーションが大きな利点を得ることができることを私に示すことができれば、それは時々物事が進む方法です。
于 2010-01-23T15:37:56.973 に答える
2

それは良い質問です、私は理由を思い付くのに苦労しています。リファレンスソースにはヒントはありません。1つの可能性は、ICollection <>。CopyTo（）メソッドオブジェクトを実装するクラスが0以外の開始インデックスにコピーしない場合に問題を回避しようとすることです。または、セキュリティ対策として、コレクションが配列要素と干渉するのを防ぎます。アクセスできないようにする必要があります。

もう1つは、コレクションがスレッドセーフでない方法で使用された場合の対策です。アイテムが別のスレッドによってコレクションに追加された場合、失敗するのはコレクションクラスのCopyTo（）メソッドであり、Microsoftコードではありません。適切な人がサービスコールを受けます。

これらは素晴らしい説明ではありません。

于 2010-01-23T13:39:28.570 に答える
0

少し考えてみると、ソリューションに問題があります。そのようにコードを変更すると、基本的に、追加する必要のあるコレクションに内部データ構造へのアクセスを許可することになります。

これは良い考えではありません。たとえば、Listデータ構造の作成者が、配列よりもデータを格納するためのより優れた基本構造を見つけた場合、すべてのコレクションがCopyTo関数への配列を期待しているため、Listの実装を変更する方法はありません。 。

本質的には、オブジェクト指向プログラミングでは、データ構造の内部実装は他のコードを壊すことなく変更できるものでなければならないと言われていても、Listクラスの実装を強化することになります。

于 2010-01-23T14:49:38.153 に答える