First メソッドのパフォーマンス特性

Tweet

はじめに

この記事は Deep Dive into LINQ シリーズの第4回目の記事です。 Deep Dive into LINQ シリーズでは、 LINQ の内部実装やパフォーマンス特性について基本的なことから調べていきます。

前回に引き続き LINQ の First メソッドについて研究していきます。

前回の記事 では、First メソッドの実装をざっと眺めました。 今回はいろいろなコレクションに対して、First メソッドのパフォーマンスがどのようになるか調べてみます。

ベンチマーク概要

今回のベンチマークではいろいろなコレクションの型に対して、複数の方法で「最初の要素」を取得する速度を計測します。

対象のコレクション型

今回の調査対象は以下の型です。

• int[]
• List<int>
• ImmutableList<int>
• ImmutableArray<int>
• ReadOnlyCollection<int>
• ConcurrentBag<int>
• IEnumerable<int>

int[] から ConcurrentBag<int> までのコレクションには、それぞれ 1 から 100 までの連続した整数が格納されたコレクションを使用しました。

private readonly int[] _array = Enumerable.Range(1, 100).ToArray();
private readonly List<int> _list = Enumerable.Range(1, 100).ToList();
private readonly ImmutableList<int> _immutableList = Enumerable.Range(1, 100).ToImmutableList();
private readonly ImmutableArray<int> _immutableArray = Enumerable.Range(1, 100).ToImmutableArray();
private readonly ReadOnlyCollection<int> _readOnlyCollection = Enumerable.Range(1, 100).ToList().AsReadOnly();
private readonly ConcurrentBag<int> _concurrentBag = new ConcurrentBag<int>(Enumerable.Range(1, 100));

IEnumerable<int> には最適化のかからない素の IEnumerable<int> を検証したいため、 以下のような正の整数を列挙する MyEnumerable という型を使用しました。

private sealed class MyEnumerable : IEnumerable<int>
{
    public IEnumerator<int> GetEnumerator()
    {
        return new MyEnumerator();
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }

    private sealed class MyEnumerator : IEnumerator<int>
    {
        public bool MoveNext()
        {
            Current++;
            return true;
        }

        public void Reset()
        {
            Current = 0;
        }

        public int Current { get; private set; }

        object IEnumerator.Current => Current;

        public void Dispose()
        {
        }
    }
}

対象の実装

計測対象とする実装としては、下記の 3 種類を試しました。

• LINQ の First メソッド
• （インデクサが使用可能な型に対して）0 番目の要素をインデクサで取得
• 前々回の記事 で実装した MyFirst メソッド

ベンチマークのコードは下記のようになります。 （

[Benchmark]
public int LinqFirstOfArray() => _array.First();

[Benchmark]
public int LinqFirstOfList() => _list.First();

[Benchmark]
public int LinqFirstOfImmutableList() => _immutableList.First();

[Benchmark]
public int LinqFirstOfImmutableArray() => _immutableArray.First();

[Benchmark]
public int LinqFirstOfReadOnlyCollection() => _readOnlyCollection.First();

[Benchmark]
public int LinqFirstOfConcurrentBag() => _concurrentBag.First();

[Benchmark]
public int LinqFirstOfEnumerable() => _enumerable.First();

[Benchmark]
public int IndexAccessArray() => _array[0];

[Benchmark]
public int IndexAccessOfList() => _list[0];

[Benchmark]
public int IndexAccessOfImmutableList() => _immutableList[0];

[Benchmark]
public int IndexAccessOfImmutableArray() => _immutableArray[0];

[Benchmark]
public int IndexAccessOfReadOnlyCollection() => _readOnlyCollection[0];

[Benchmark]
public int MyFirstOfArray() => _array.MyFirst();

[Benchmark]
public int MyFirstOfList() => _list.MyFirst();

[Benchmark]
public int MyFirstOfImmutableList() => _immutableList.MyFirst();

[Benchmark]
public int MyFirstOfImmutableArray() => _immutableArray.MyFirst();

[Benchmark]
public int MyFirstOfReadOnlyCollection() => _readOnlyCollection.MyFirst();

[Benchmark]
public int MyFirstOfConcurrentBag() => _concurrentBag.MyFirst();

[Benchmark]
public int MyFirstOfEnumerable() => _enumerable.MyFirst();

ベンチマーク結果

ベンチマーク結果は下記のようになりました。

Method	Mean	Error	StdDev	Gen 0	Allocated
LinqFirstOfArray	16.6237 ns	0.8944 ns	0.0490 ns	-	-
LinqFirstOfList	10.8263 ns	1.6585 ns	0.0909 ns	-	-
LinqFirstOfImmutableList	16.0653 ns	0.4098 ns	0.0225 ns	-	-
LinqFirstOfImmutableArray	0.2549 ns	0.0680 ns	0.0037 ns	-	-
LinqFirstOfReadOnlyCollection	13.4728 ns	0.2157 ns	0.0118 ns	-	-
LinqFirstOfConcurrentBag	153.4005 ns	14.9066 ns	0.8171 ns	0.2179	456 B
LinqFirstOfEnumerable	17.4152 ns	1.7975 ns	0.0985 ns	0.0115	24 B
IndexAccessArray	0.2492 ns	0.1076 ns	0.0059 ns	-	-
IndexAccessOfList	0.2545 ns	0.0052 ns	0.0003 ns	-	-
IndexAccessOfImmutableList	5.1818 ns	0.9029 ns	0.0495 ns	-	-
IndexAccessOfImmutableArray	0.2516 ns	0.1081 ns	0.0059 ns	-	-
IndexAccessOfReadOnlyCollection	1.2690 ns	0.3423 ns	0.0188 ns	-	-
MyFirstOfArray	14.5942 ns	3.6290 ns	0.1989 ns	0.0153	32 B
MyFirstOfList	18.6390 ns	1.8646 ns	0.1022 ns	0.0191	40 B
MyFirstOfImmutableList	172.5793 ns	2.8378 ns	0.1555 ns	0.0343	72 B
MyFirstOfImmutableArray	20.9324 ns	8.4283 ns	0.4620 ns	0.0268	56 B
MyFirstOfReadOnlyCollection	23.1343 ns	11.5534 ns	0.6333 ns	0.0191	40 B
MyFirstOfConcurrentBag	144.4622 ns	16.0557 ns	0.8801 ns	0.2179	456 B
MyFirstOfEnumerable	11.6135 ns	2.4666 ns	0.1352 ns	0.0115	24 B

LINQ の First メソッドを使った実装では、実行時間がおおむね 10 ns 台に抑えられています。 例外は ImmutableArray と ConcurrentBag で、 ImmutableArray はダントツで速く 0.25 ns、 ConcurrentBag は遅く 153 ns かかっています。

インデクサを使ったアクセスは流石に速いです。配列、 List<int>、 ImmutableArray<int> はどれも 0.25 ns 程度で処理できています。 少し時間がかかったのは ImmutableList と ReadOnlyCollection ですが、 これも ImmutableList に関しては LINQ の 1/3 未満、 ReadOnlyCollection に関しては 1/11 未満の処理時間になっていて、 いずれも 5 ns 以下で十分速いです。

最後に前々回の記事で作った最適化を入れていない単純な実装では、おおむね LINQ よりも遅いという当然の結果になりました。 例外は配列と純粋な IEnumerable<int> で、こちらは最適化しない実装のほうが速くなりました。

ImmutableArray<T> の LINQ がめちゃくちゃ速い

ImmutableArray<T> がインデクサを直接扱うような実装とほとんど変わらないパフォーマンスを出していたのはなぜでしょうか？ 実は ImmutableArray<T> の場合、ふつうの LINQ の実装は使われません。 ImmutableArray<T> には専用の LINQ 実装が用意されており、普通に _immutableArray.First() のように書いた場合はそちらのメソッドが使われます。

ImmutableArray<T> 用の First メソッドの実装は下記のようになっています。 （このメソッドの全文は GitHub で読めます。）

public static T First<T>(this ImmutableArray<T> immutableArray)
{

    return immutableArray.Length > 0
        ? immutableArray[0]
        : Enumerable.First(immutableArray.array!);
}

このように、無駄な型スイッチなどを一切挟まず、いきなり 0 番目の要素をとるという実装にできるため大変速くなっています。

配列の LINQ パフォーマンスがあまり良くない

一方、配列 + LINQ の場合は List<T> や自前の最適化なしの実装に比べても遅い、という結果になりました。 最適化なしの実装のほうが速いというのはなんとも悲しい事実ですが、原因として配列のキャストや IList<T> 抽象が遅いということがあるようです。

LINQ の First メソッドの中身（TryGetFirst メソッド）を見てみましょう。

private static TSource? TryGetFirst<TSource>(this IEnumerable<TSource> source, out bool found)
{
    if (source == null)
    {
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.source);
    }

    if (source is IPartition<TSource> partition)
    {
        return partition.TryGetFirst(out found);
    }

    if (source is IList<TSource> list)
    {
        if (list.Count > 0)
        {
            found = true;
            return list[0];
        }
    }
    else
    {
        using (IEnumerator<TSource> e = source.GetEnumerator())
        {
            if (e.MoveNext())
            {
                found = true;
                return e.Current;
            }
        }
    }

    found = false;
    return default;
}

配列の場合は IPartition ではなく IList なので、やっている処理としては

• 型チェックが 2 回
• Count の呼び出しが 1 回
• インデクサ（これは配列のインデクサそのままではなく IList インターフェースを介したインデクサ呼び出しです）が 1 回

という形になっています。 この型チェック部分などに少し時間がかかるようで、配列と List では is による型判定と Count の取得に下記のような差がありました。

Method	Mean	Error	StdDev	Median	Allocated
IsArrayIList	8.8117 ns	0.1659 ns	0.0091 ns	8.8134 ns	-
GetArrayCount	1.5226 ns	0.3266 ns	0.0179 ns	1.5154 ns	-
GetArrayLength	0.0005 ns	0.0172 ns	0.0009 ns	0.0000 ns	-
IsListIList	1.7863 ns	0.0973 ns	0.0053 ns	1.7851 ns	-
GetListCount	0.0000 ns	0.0000 ns	0.0000 ns	0.0000 ns	-

特に配列の型チェックのコストが無視できないほど大きいため、最適化が逆効果となり配列のパフォーマンスが落ちたようです。

ベンチマークのコードは下記を利用しました。

public class MyBenchmark2
{
    private int[] _array;
    private IList<int> _arrayAsIList;
    private IEnumerable<int> _arrayAsIEnumerable;
    private List<int> _list;
    private IEnumerable<int> _listAsIEnumerable;

    [GlobalSetup]
    public void GlobalSetup()
    {
        _array = Enumerable.Range(1, 100).ToArray();
        _arrayAsIList = _array;
        _arrayAsIEnumerable = _array;
        _list = _array.ToList();
        _listAsIEnumerable = _list;
    }

    [Benchmark]
    public bool IsArrayIList() => _arrayAsIEnumerable is IList<int>;

    [Benchmark]
    public int GetArrayCount() => _arrayAsIList.Count;

    [Benchmark]
    public int GetArrayLength() => _array.Length;

    [Benchmark]
    public bool IsListIList() => _listAsIEnumerable is IList<int>;

    [Benchmark]
    public int GetListCount() => _list.Count;
}

LINQ の実装ではアロケーションが適切に抑えられている

LINQ の実装では、アロケーションがほとんど発生していないということも注目すべきでしょう。 自前実装では必ずアロケーションが発生していますが、これは GetEnumerator の呼び出しによって IEnumerator<T> のインスタンスが生成されるためです。 アロケーションを避けるというのはパフォーマンス向上のための常套手段であり、 LINQ の実装は IList<T> や IPartition<T> の場合には IEnumerator<T> のインスタンスを作らないようになっているため、 アロケーションを適切に避けることができています。

まとめ

今回は First メソッドのパフォーマンスを調査してみました。 特に配列に関しては意外な結果が得られ、配列の型判定などは予想以上にコストがかかるということもわかりました。

やはり LINQ を使うという時点である程度のオーバーヘッドは覚悟しなければなりませんが、 いろいろなコレクションに対して一貫した記法が得られるのと、 最低限の品質が保証されていて、それなりに安定したパフォーマンスが得られるというのは捨てがたいメリットではないでしょうか。 LINQ はそのあたりのバランスが良い選択肢であるともいえます。

具体的なコレクションの型が確定していて、かつパフォーマンスにどこまでもこだわりたいという場合は、 配列専用の実装やリスト専用の実装などを用意しても面白いかもしれません。

ライセンス

今回紹介した LINQ の実装コードは MIT ライセンスで公開されている .NET 6 の実装の引用です。

ライセンス全文はこちらからご確認いただけます。