ノートの端の書き残し

UnityやらC#やら。設計が得意かもしれない。

僕はLinqのことを何もわかっていなかった

Linq

コレクションのイテレーションを気軽に回せる処理。

var intEnumerable = Enumerable.Range(0, 10);
var intList = intEnumerable.ToList(); // 0, 1, 2, ... , 8, 9
var oddList = intEnumerable.Where(value => value % 2 == 1).ToList(); // 1, 3, 5, 7, 9

ここ数年でLinqに最適化が入っている

という話は知っていました。ただ、具体的にどうなのというのをちゃんと見たことがありませんでした。

IPartition<T>, IIListProvider<T>

Linqと言えばIEnumerable、というイメージを持っていました。もちろん、MoveNextしてCurrentを取ってくるのが基本ですからそれは間違いではないんですが、現在では特定の状況でパフォーマンス改善を図るためのより細かいインターフェースがありました。

IIListProvider<T>

source.dot.net

using System.Collections.Generic;
 
namespace System.Linq
{
    internal interface IIListProvider<TElement> : IEnumerable<TElement>
    {
        TElement[] ToArray();
 
        List<TElement> ToList();

        int GetCount(bool onlyIfCheap);
    }
}

つまり、これは直後にToArrayToListが来た場合に最適化するためのインターフェースと言えます。
何も考えずにIEnumerableからToListをしてしまうと、だいたいこういう処理になります。

var list = new List<T>();
foreach (var element in enumerable) { list.Add(element) };

enumerableの数が多いと、Listの内部配列の再配置が頻発して酷く無駄なヒープアロケーションが発生します。なので、事前に要素数がわかるなら先に必要十分な配列長を確保したい気持ちがあります。それを独自に実装して呼び出させるためのインターフェース、ということですね。
例えば、OrderByで生成されうるイテレータクラスのToListを見てみます。

OrderedEnumerableIterator.ToList

source.dot.net

public List<TElement> ToList()
{
    Buffer<TElement> buffer = new Buffer<TElement>(_source);
    int count = buffer._count;
    List<TElement> list = new List<TElement>(count);
    if (count > 0)
    {
        int[] map = SortedMap(buffer);
        for (int i = 0; i != count; i++)
        {
            list.Add(buffer._items[map[i]]);
        }
    }
 
    return list;
}

確かにListのキャパシティを指定して生成していますね。

IPartition<T>

source.dot.net

using System.Diagnostics.CodeAnalysis;
 
namespace System.Linq
{
    /// <summary>
    /// An iterator that supports random access and can produce a partial sequence of its items through an optimized path.
    /// </summary>
    internal interface IPartition<TElement> : IIListProvider<TElement>
    {
        IPartition<TElement> Skip(int count);
 
        IPartition<TElement> Take(int count);
 
        TElement? TryGetElementAt(int index, out bool found);
 
        TElement? TryGetFirst(out bool found);
 
        TElement? TryGetLast(out bool found);
    }
}

コレクションを全部見る必要が無いと思われる場合に最適化するためのインターフェースと考えられます。例えばIList<T>型のインスタンスSelectを使うと生成されうるイテレータクラスのElementAtを見てみましょう。

source.dot.net

public TResult? TryGetElementAt(int index, out bool found)
{
    if ((uint)index <= (uint)(_maxIndexInclusive - _minIndexInclusive) && index < _source.Count - _minIndexInclusive)
    {
        found = true;
        return _selector(_source[_minIndexInclusive + index]);
    }
 
    found = false;
    return default;
}

sourceがIList型だと知っているので、直接インデックスを渡して取得しているのがわかりますね。

終わり

C#を学び始めるとLinqは遅いと習ってしまいがちです。確かにListを回すならfor、配列ならforeachで良いですが、とはいえ、Linqには圧倒的な可読性、変更容易性の高さがあります。見てきたように、実は今ではLinqは可能なら無駄な処理を行わないように、という最適化もしっかり入っているので、Linqは遅いんだ、という先入観は卒業してもよいかもしれません。