C# Advent Calendar 2016 16日目の記事です。
http://qiita.com/advent-calendar/2016/csharp

Listと配列のコピー速度について、何度も記事が出ていますが、自分でもやってみました。

.NETのヒープとスタック、クラスと構造体の関係は扱いやすい反面、実行してみないとわからないこともあり、速度面での挙動を感覚的につかんでおくことは重要だと思います。サンプルコードはまとめてGistにあげているので、良かったら使ってください。個別の環境で実行してみると体感出来ると思います。

以下の結果は、.NET Framwork 4.5.2、Visual Studio 2015、AnyCPU(32bit優先OFF)　Releaseモードで計測しています。

サンプル型の用意

以下のクラスと構造体を用意しました。X, Y, Zの3つのプロパティがあるだけの単純な型です。

public class CoordinateClass
{
    public double X { get; set; }
    public double Y { get; set; }
    public double Z { get; set; }

    public CoordinateClass Clone()
    {
        return new CoordinateClass()
        {
            X = this.X,
            Y = this.Y,
            Z = this.Z,
        };
    }
}

public struct CoordinateStruct
{
    public double X { get; set; }
    public double Y { get; set; }
    public double Z { get; set; }
}

コピー速度(時間)の測定

まず、コピー速度です。List と List<構造体の型>と、classの型[] と構造体の型[] のコピーではどれが一番速いのでしょうか。
コピーはDeep Copyを想定しています。参照だけコピーするならクラスが一番早いに決まっているので。

テスト条件

大きな配列を作成して、何回かループして時間を計測し平均を取ります。

static void Main(string[] args)
{
    // 配列数
    int num = 1000000;
    // 繰り返し回数
    int loop = 10;

    Random rand = new Random(1234567);

    List<CoordinateClass> list1 = new List<CoordinateClass>();
    for (int i = 0; i < num; i++)
        list1.Add(new CoordinateClass()
        {
            X = rand.NextDouble(),
            Y = rand.NextDouble(),
            Z = rand.NextDouble(),
        });
    Action action = () =>
    {
        List<CoordinateClass> copiedList = new List<CoordinateClass>();
        foreach (var item in list1)
            copiedList.Add(item.Clone());
    }:


    Stopwatch sw = new Stopwatch();

    for (int i = 0; i < loop; i++)
    {
        sw.Start();
        action();
        sw.Stop();

        System.Threading.Thread.Sleep(10);
    }

    Console.WriteLine("{0, -20} : {1} msec.", "List<class>", sw.ElapsedMilliseconds / loop);
}

このような形で、4パターン試します。
1. List<クラスの型>, List<class>
2. クラスの型の配列, class[]
3. List<構造体の型>, List<struct>
4. 構造体の型の配列, struct[]

コード全体はココに置きました。
https://gist.github.com/leetmikeal/e4b1ab9bfff2af245a996bb00bed1f38

結果

要素の数が10,000 (約240kB+α)、試行回数100回でやってみました。

クラスはClone()メソッドでコピーしていることや余計なメモリを使うので、予想通り構造体の方が明らかに早いですね。List<T>と配列では配列の方が高速です。

構造体だとあまり変わらない、もしくは配列の方が遅くなるようです。何度やっても大体このような結果でした。構造体の場合は中身もそのままコピー出来るので、

List<CoordinateStruct> copiedList = new List<CoordinateStruct>(list2);

のように簡潔に書けます。
そこで、中の挙動を知るためにソースコードを見てみます。

        public List(IEnumerable<T> collection) {
            if (collection==null)
                ThrowHelper.ThrowArgumentNullException(ExceptionArgument.collection);
            Contract.EndContractBlock();

            ICollection<T> c = collection as ICollection<T>;
            if( c != null) {
                int count = c.Count;
                if (count == 0)
                {
                    _items = _emptyArray;
                }
                else {
                    _items = new T[count];
                    c.CopyTo(_items, 0);
                    _size = count;
                }
            }    
            else {                
                _size = 0;
                _items = _emptyArray;
                // This enumerable could be empty.  Let Add allocate a new array, if needed.
                // Note it will also go to _defaultCapacity first, not 1, then 2, etc.

                using(IEnumerator<T> en = collection.GetEnumerator()) {
                    while(en.MoveNext()) {
                        Add(en.Current);                                    
                    }
                }
            }
        }

ICollection<T>かどうかをチェックして処理を分けています。CopyToを使用して内部で持っている配列を更新しています。

で、今回のテストプログラムで比較対象の配列はどうコピーしているかというと、

CoordinateStruct[] copiedList = new CoordinateStruct[list4.Length];
list4.CopyTo(copiedList, 0);

なので、全く同じはずですが、なぜかListが微妙に早くなります。メモリの扱いの問題なのでしょうか…。何かわかったら追記したいと思います。

List<T>と配列の相互変換

もう一つ、試してみたかったのがリストと配列の相互変換です。可変データを扱うとき、配列で扱ったほうがいいのか、Listで扱ったほうがいいのか、相互変換の頻度はなるべく少ないように考慮すべきなのか、よくわかっていませんでした。LINQでToArray()やToList()を行う頻度を少なくするべきなのはわかっていますが、複雑巨大なシステムでは各方面の都合でListだったり配列だったりと、扱いが統一出来ていない場合もあり、そのコストは見積もっておきたいと考えていました。

テスト

List -> List
List -> 配列
配列 -> List
配列 -> 配列

クラスの型について、この4パターンを速度計測しました。サンプルコードは先ほどのものを使用して予めリストと配列を作成した後に、LINQでToArray()とToList()を行っています。

コピーはShallow Copyを想定しています。計測するのは4パターンですが、必ず最初のケースが遅延するので、実際にテストする際はダミーで1回多く回しています。

コード全体はココに置きました。
https://gist.github.com/leetmikeal/7c3fd61e5affeb0cd7e64ba7f9a13757

結果

はい。差がありません。変換やShallow Copyのことを気にしてListか配列かを判断しなくても良いということです。

要素サイズとListと配列のDeep Copy速度比較

最初のテストで行った、Deep Copyの比較を、Listや配列のサイズを変えていったらどのようになるのかを確かめてみました。

テスト

要素数10から初めて、10刻みで10000まで増やして計算しました。繰り返し回数は10回です。

コード全体はココに置きました。
https://gist.github.com/leetmikeal/69d6d18caed6ba52a4d478a5c01a3c38

結果

不思議な形になりました。Listの結果がばらついています。常に構造体の方が早いのは当然ですが、要素数が大きくなるとListと並ぶこともあるようです。

ただし、構造体は3000要素辺りまでは明らかに高速です。それより多くなると急にListと同じ程度になりました。LOHの影響？上手い説明が思いつかず。

まとめ

大方は予想通りの結果でしたが定量的に説明できるようになると安心感があります。ただ「？」な部分もあるので、標準ライブラリの中身の挙動やGCの影響など、まだまだ理解しなければならないことがありそうです。余裕があれば都度このような簡単なテストプログラムでパフォーマンス評価を続けて行きたいです。あとは高速な処理はC++/CLIでやるべし。

List<T> vs 配列[], クラス vs 構造体 のコピー速度比較

サンプル型の用意

コピー速度(時間)の測定

テスト条件

結果

List<T>と配列の相互変換

テスト

結果

要素サイズとListと配列のDeep Copy速度比較

テスト

結果

まとめ

List<T> vs 配列[], クラス vs 構造体のコピー速度比較