2009/11/15

配列やList<T>をIList<T>型のインデクサでアクセスするとパフォーマンスが悪い(don't use IList<T>'s indexer)

C#でのソートアルゴリズムのまとめ(sort algorithms in C#)とかIList<T>の走査処理の比較(インデクサ/GetEnumerator/foreach)で「配列の添字アクセスが遅い」とか書いたけどこれは間違い。「配列をIList<T>型にキャストしてインデクサでアクセスすると遅い」というのが正しい。
実際には配列をそのまま添字でアクセスする処理はList<T>のインデクサアクセスよりも速い。
それにList<T>もIList<T>型にキャストしてインデクサでアクセスすのは(List<T>のインデクサよりも)遅い。
インターフェースってこんなに影響するものなのか。配列やList<T>の特殊な最適化処理があったりしてそれが適用されなくなったりした影響なのかな。

測定した結果は次の通り。
int[]に対する配列の添字アクセスが最も速くてIList<T>のインデクサを通すとなぜか10倍弱の時間がかかるようになる。
List<T>のインデクサアクセスは配列の添字アクセスより遅いらしい。これもIList<T>のインデクサを通すと配列ほどじゃないけど遅くなる。
array: 662 (1.00)
(IList<T>)array: 6259 (9.45)
list: 1325 (2.00)
(IList<T>)list: 1592 (2.40)
IListArrayWrapper: 1166 (1.76)
ksksts / junk / source — bitbucket.org

IListArrayWrapperは値型の配列をラップしてポインタを使ったunsafeなインデクサを実装したクラス。
ジェネリックに実装しようとしたけどジェネリック引数の型のポインタを取得する方法が分からなかった。"where T : struct"の指定があればOKにしてもいいんじゃないかと思うけど、とりあえずできなかったからint型用のコードにした。

ダメだったコード:
public class IListArrayWrapper<T> where T : struct
    {
        public T[] Source { get; set; }
        unsafe public T this[int index]
        {
            get
            {
                fixed (T* p = &Source[0])
                    return *(p + index);
            }
            set
            {
                fixed (T* p = &Source[0])
                    *(p + index) = value;
            }
        }
        public IListArrayWrapper(IList<T> source)
        {
            Source = (T[])source;
        }
    }
ksksts / junk / source — bitbucket.org

まとめとしては、配列とIList<T>を実装したランダムアクセス可能なコレクションの両方を処理する&パフォーマンスを気にするコードを書く場合は分けたほうがいいみたい。

0 件のコメント: