2009/11/04

IList<T>の走査処理の比較(インデクサ/GetEnumerator/foreach)

twitterで「IList<t>を走査する場合でforとforeachとで意外に差が出た」とか書いたら「IListの内部実装にもよりますけど、結構変わったりしますよねー」とRTがあった。
それで処理速度を計測するコードを書いてみたらよく分からない結果になった。
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;

namespace IListEnumerationBenchmark
{
    class Program
    {
        static void Main(string[] args)
        {
            var size = 1000000;
            var count = 10;
            var sw = new Stopwatch();

            Action<IList<int>> run = list =>
            {
                var useIndexerTicks = 0L;
                var useEnumeratorTicks = 0L;
                var useForeachTicks = 0L;

                for (var c = 0; c < count; c++)
                {
                    var random = new Random(c);
                    for (var n = 0; n < list.Count; n++)
                        list[n] = random.Next(int.MinValue, int.MaxValue);

                    // use indexer
                    sw.Reset();
                    sw.Start();
                    var useIndexerResult = UseIndexer(list);
                    sw.Stop();
                    useIndexerTicks += sw.ElapsedTicks;

                    // use enumerator
                    sw.Reset();
                    sw.Start();
                    var useEnumeratorResult = UseEnumerator(list);
                    sw.Stop();
                    useEnumeratorTicks += sw.ElapsedTicks;

                    // use foreach
                    sw.Reset();
                    sw.Start();
                    var useForeachResult = UseForeach(list);
                    sw.Stop();
                    useForeachTicks += sw.ElapsedTicks;

                    // correctness
                    if (useIndexerResult != useForeachResult)
                        Console.WriteLine("useIndexerResult: {0}, useForeachResult: {1}", useIndexerResult, useForeachResult);
                    if (useEnumeratorResult != useForeachResult)
                        Console.WriteLine("useEnumeratorResult: {0}, useForeachResult: {1}", useEnumeratorResult, useForeachResult);
                }

                Console.WriteLine("use indexer: {0} ({1:F})", useIndexerTicks / count, useIndexerTicks / (double)useForeachTicks);
                Console.WriteLine("use enumerator: {0} ({1:F})", useEnumeratorTicks / count, useEnumeratorTicks / (double)useForeachTicks);
                Console.WriteLine("use foreach: {0} ({1:F})", useForeachTicks / count, useForeachTicks / (double)useForeachTicks);
                Console.WriteLine();
            };

            // int[]
            {
                Console.WriteLine("int[]: ");
                var array = new int[size];
                run(array);
            }

            // List<int>
            {
                Console.WriteLine("List<int>: ");
                var list = new List<int>();
                for (var n = 0; n < size; n++)
                    list.Add(0);
                run(list);
            }
        }

        static int UseIndexer(IList<int> list)
        {
            var result = 0;
            for (var n = 0; n < list.Count; n++)
                result = unchecked(result + list[n]);
            return result;
        }

        static int UseEnumerator(IList<int> list)
        {
            var result = 0;
            var e = list.GetEnumerator();
            while (e.MoveNext())
                result = unchecked(result + e.Current);
            return result;
        }

        static int UseForeach(IList<int> list)
        {
            var result = 0;
            foreach (var x in list)
                result = unchecked(result + x);
            return result;
        }
    }
}
ksksts / junk / source — bitbucket.org

結果は次の通り。
配列ではインデクサでのアクセスがforeachより遅いのにList<t>では逆になるのが意味が分からない。あと両方でGetEnumeratorでのアクセスがforeachよりも速いのも意味が分からない(foreachの方が最適化する余地があるんじゃないかと思う)。
こんな処理にフォーカスした速度なんかほとんどのケースで無視していいだろうから、インデクサでのアクセスが必要じゃない処理では常にforeachを使うけど。
書きながらList<t>.ForEachを思い出した(IList<t>には無い)。使える場合ならforeachよりもそれを使うと思う。ILとかコンパイル後のコードはたぶん見ない。
int[]:
use indexer: 578500 (5.57)
use enumerator: 87133 (0.84)
use foreach: 103895 (1.00)

List<int>:
use indexer: 132922 (0.76)
use enumerator: 154705 (0.89)
use foreach: 174277 (1.00)
追記: 上の結果はIList<T>を通した結果だから不正確。ksksts's blog: 配列やList<T>をIList<T>型のインデクサでアクセスするとパフォーマンスが悪い(don't use IList<T>'s indexer)を参照。

0 件のコメント:

コメントを投稿