List<T>.AddRange 実装が最適ではない

https://stackoverflow.com/questions/2123161

22-09-2019
|

質問

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% を占めますが、List をより高速な AddRange を提供するクラスに置き換えると、アプリケーションのランタイムが 4% 改善される可能性があります。

解決

彼らはの実装を妨げています ICollection<T> 挿入範囲外の宛先リストのインデックスにアクセスしないようにします。上記の実装では、次のようになります。 IndexOutOfBoundsException 欠陥のある（または「操作的な」）実装があった場合、 CopyTo と呼ばれます。

それを念頭に置いて T[].CopyTo 文字通り内部的には次のように実装されます memcpy, したがって、その行を追加することによるパフォーマンスのオーバーヘッドはわずかです。非常に低コストで膨大な数の通話に安全性を追加できるのであれば、そうするほうがよいでしょう。

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

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

編集 2 (OP の編集への応答): これをプロファイリングしましたか?Microsoft はもっと複雑な API を選択するべきだったという大胆な主張をしているので、現在のメソッドが遅いという主張が正しいことを確認する必要があります。のパフォーマンスに問題があったことはありません InsertRange, そして、誰かが直面するパフォーマンス上の問題は、動的リストを再実装するよりもアルゴリズムを再設計した方がうまく解決できると私は確信しています。私のことをネガティブな意味で厳しいと受け取らないように、次のことに留意してください。

私 ~~欲しくない~~ 私の開発チームの人々がこんなことをするのが許せない四角い車輪を再発明する.
私 絶対に 私のチームには、潜在的なパフォーマンスの問題に関心を持ち、コードが引き起こす可能性のある副作用について質問できる人材が必要です。この点は、存在する場合には優先されますが、人々が質問している限り、私は彼らの質問を確かな答えに変えるよう促します。最初は悪いアイデアのように見えたアイデアによってアプリケーションが大きな利点を得ることができるのであれば、それは単に物事がうまくいく場合があるということです。

他のヒント

良い質問ですね、理由を考えるのに苦労しています。参照元にはヒントがありません。可能性の 1 つは、ICollection<>.CopyTo() メソッドを実装するクラスが 0 以外の開始インデックスへのコピーに対してオブジェクトを実行するときに問題を回避しようとしている可能性があります。または、セキュリティ対策として、コレクションがアクセスすべきではない配列要素を操作するのを防ぎます。

もう 1 つは、これはコレクションがスレッドアンセーフな方法で使用される場合の対策であるということです。項目が別のスレッドによってコレクションに追加された場合、失敗するのは Microsoft コードではなく、コレクションクラスの CopyTo() メソッドです。適切な担当者がサービスコールを受けられます。

これらはあまり良い説明ではありません。

あなたは分間考えてみれば、あなたは基本的に内部データ構造へのアクセスを追加すべきコレクションを与えていることのようにコードを変更する場合は、

は、あなたのソリューションに問題があります。

優れた基本的な構造アウトリストのデータ構造の数値の作者は、データを格納する場合は、

これは、すべてのコレクションはに、配列を期待しているので、リストの実装を変更する方法がない配列よりも、例えば、良いアイデアではありませんCopyToの機能ます。

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

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow

List<T>.AddRange 実装が最​​適ではない

List<T>.AddRange 実装が最適ではない