2020.03.06

【Unity, C#】foreach の GC Alloc 条件を調べてみた

こんにちは。クライアント開発の taraba_ です。
今日は、Unity 上で .NET の System.Collections.Generic 名前空間にある IEnumerable<T> 実装コレクション（と配列）を foreach にかけた際に、GC Alloc が発生する条件を調べました。
調査環境は Unity 2018.4.14f1 です。
（2020.1.0a24 でも同様の結果でした）

まずは以下の疑似コードとプロファイル結果をご覧ください。

    // 直接持つ
    private int[] _array = new[] {1, 2, 3, 4};

    private List<int> _list = new List<int>() {1, 2, 3, 4};

    private Dictionary<int, int> _dictionary = new Dictionary<int, int> {{1, 2}, {3, 4}};

    // インターフェースとして持つ
    private IList<int> _interfacedArray = new[] {1, 2, 3, 4};

    private IList<int> _interfacedList = new List<int> {1, 2, 3, 4};

    private IReadOnlyDictionary<int, int> _interfacedDictionary = new Dictionary<int, int> {{1, 2}, {3, 4}};

    private void Update()
    {
        Profiler.BeginSample("AllocCheck: Array");
        foreach (var _ in _array) { }
        Profiler.EndSample();

        Profiler.BeginSample("AllocCheck: List");
        foreach (var _ in _list) { }
        Profiler.EndSample();

        Profiler.BeginSample("AllocCheck: Dictionary");
        foreach (var _ in _dictionary) { }
        Profiler.EndSample();

        Profiler.BeginSample("AllocCheck: InterfacedArray");
        foreach (var _ in _interfacedArray) { }
        Profiler.EndSample();

        Profiler.BeginSample("AllocCheck: InterfacedList");
        foreach (var _ in _interfacedList) { }
        Profiler.EndSample();

        Profiler.BeginSample("AllocCheck: InterfacedDictionary");
        foreach (var _ in _interfacedDictionary) { }
        Profiler.EndSample();
    }

// 直接持つ

private int[] _array = new[] {1, 2, 3, 4};

private List<int> _list = new List<int>() {1, 2, 3, 4};

private Dictionary<int, int> _dictionary = new Dictionary<int, int> {{1, 2}, {3, 4}};

// インターフェースとして持つ

private IList<int> _interfacedArray = new[] {1, 2, 3, 4};

private IList<int> _interfacedList = new List<int> {1, 2, 3, 4};

private IReadOnlyDictionary<int, int> _interfacedDictionary = new Dictionary<int, int> {{1, 2}, {3, 4}};

private void Update()

{

Profiler.BeginSample("AllocCheck: Array");

foreach (var _ in _array) { }

Profiler.EndSample();

Profiler.BeginSample("AllocCheck: List");

foreach (var _ in _list) { }

Profiler.EndSample();

Profiler.BeginSample("AllocCheck: Dictionary");

foreach (var _ in _dictionary) { }

Profiler.EndSample();

Profiler.BeginSample("AllocCheck: InterfacedArray");

foreach (var _ in _interfacedArray) { }

Profiler.EndSample();

Profiler.BeginSample("AllocCheck: InterfacedList");

foreach (var _ in _interfacedList) { }

Profiler.EndSample();

Profiler.BeginSample("AllocCheck: InterfacedDictionary");

foreach (var _ in _interfacedDictionary) { }

Profiler.EndSample();

}

現在、コレクションを直接 foreach にかけた場合 GC Alloc は発生しなくなっています。
しかし、IList<T> など IEnumerable<T> 継承インターフェースとして保持し、foreach にかけた場合には発生しています。

Unity 5.4 以前は List<T> など配列以外のコレクションに対して foreach を行うと、展開されたコードで構造体の IDisposable へのキャストが発生し、Boxing （による GC Alloc）が起きていました。
（GC Alloc のサイズの根拠と実際の展開については、 http://neue.cc/2016/08/05_537.html が詳しいです。）

現在そのコンパイラの問題は解決していますが、インターフェースとして foreach を呼んだ際、同等の GC Alloc が発生しているように見えます。

GC Alloc 発生元

Deep Profiling で見てみると、この GC Alloc は GetEnumerator() 段階で発生しています。

各コレクションの代表として List<T> を例に挙げます。

List<T>.GetEnumerator() で返される List<T>.Enumerator は、クラスライブラリ側で最適化のため各々のコレクション専用に用意された構造体です。
https://docs.microsoft.com/ja-jp/dotnet/api/system.collections.generic.list-1.enumerator?view=netframework-4.8
（System.Collections.Generic 名前空間のコレクションには全て同様の専用構造体が用意されています）

そのため、直接 GetEnumerator() を呼んだ場合は GC Alloc が起きません。

一方、IList<T>.GetEnumerator() など IEnumerable<T> の継承インターフェースは IEnumerator<T> を返します。

List.cs を覗いてみると、IEnumerable<T>.GetEnumerator() の実装は

        IEnumerator<T> IEnumerable<T>.GetEnumerator() 
        {
            return new Enumerator(this);
        }

IEnumerator<T> IEnumerable<T>.GetEnumerator()

{

return new Enumerator(this);

}

https://referencesource.microsoft.com/#mscorlib/system/collections/generic/list.cs,574
となっており、暗黙的にインターフェースへのキャストが発生しています。
（省略せずに書いた場合以下になります）

return (IEnumerator<T>) new List<T>.Enumerator(this)

1	return (IEnumerator<T>) new List<T>.Enumerator(this)

この Boxing が、コレクションをインターフェースとして保持し、foreach にかけた場合の GC Alloc になっています。

IEnumerator<T> は IDisposable を継承しており、コンパイラ仕様に不具合があったころのように IDiposable へのキャストによる Boxing は発生していません。
（同サイズの Boxing が発生しているため同じに見えますが）

要素が struct（primitive）であるか、class であるかは GC Alloc の発生には無関係でした。
また、後述の Sorted コレクション以外、要素数と GC Alloc の発生は無関係でした。

例外1: 配列

配列（と Span<T>）に対する foreach は、コンパイラが見つけ次第 for 文と同等のコードに変換してくれます。
しかし、配列をインターフェースとして持つ場合にはコンパイラが判断できず、そのほかのコレクション同様に展開され GetEnumerator() が呼ばれることになります。

配列は System.Collections.Generic 名前空間のライブラリ内ではなく、言語仕様として存在しています。
そのためか、 GetEnumerator() で返される専用の構造体は用意されておらず、Array.GetEnumerator() 内部ではクラスが new され、IEnumerator として返されます（int[] の場合 32B の GC Alloc が発生します）。
例外としたのは、 Boxing による GC Alloc ではなく他のコレクションに比べるとコストが安いのと、直接 Array.GetEnumerator() を呼んだだけでも GC Alloc が発生するためです。

例外2: Sorted コレクション

代表として SortedDictionary<TKey, TValue> を例に挙げます。

SortedDictionary<> にも GetEnumerator() 用に専用の構造体が用意されています。
しかし、 GetEnumerator() を呼んだ時点で GC Alloc が発生し、登録されている KeyValuePair が多いほど GC Alloc 量も 16B 刻みで増えていきます。
インターフェイスとして保持し GetEnumerator() を呼ぶとさらに追加で 64B 分の Boxing が発生します。
Sorted コレクション内部の深追いはこの記事では避けますが、以下に計測用スクリプトと DeepProfiling 結果を置いておきます。

    private SortedDictionary<int, int> _sortedDictionary = new SortedDictionary<int, int>(){{1,1}};

    private IDictionary<int, int> _interfacedSortedDictionary = new SortedDictionary<int, int>(){{1,1}};

    private SortedDictionary<int, int> _sortedDictionary20 = new SortedDictionary<int, int>()
    {
        {1, 2}, {3, 4}, {5, 6}, {7, 8}, {9, 10}, {11, 21}, {31, 41}, {51, 6}, {71, 8}, {91, 10},
        {331, 2}, {33333, 4}, {55555555, 6}, {323332327, 8}, {462229, 10}, {122221, 21}, {3322, 41}, {2251, 6},
        {2323271, 8}, {93331, 10}
    };

    private void Update()
    {
        Profiler.BeginSample("AllocCheck: SortedDictionaryEnumerator");
        _sortedDictionary.GetEnumerator();
        Profiler.EndSample();

        Profiler.BeginSample("AllocCheck: InterfacedSortedDictionaryEnumerator");
        _interfacedSortedDictionary.GetEnumerator();
        Profiler.EndSample();

        Profiler.BeginSample("AllocCheck: SortedDictionaryEnumerator20");
        _sortedDictionary20.GetEnumerator();
        Profiler.EndSample();
    }

private SortedDictionary<int, int> _sortedDictionary = new SortedDictionary<int, int>(){{1,1}};

private IDictionary<int, int> _interfacedSortedDictionary = new SortedDictionary<int, int>(){{1,1}};

private SortedDictionary<int, int> _sortedDictionary20 = new SortedDictionary<int, int>()

{

{1, 2}, {3, 4}, {5, 6}, {7, 8}, {9, 10}, {11, 21}, {31, 41}, {51, 6}, {71, 8}, {91, 10},

{331, 2}, {33333, 4}, {55555555, 6}, {323332327, 8}, {462229, 10}, {122221, 21}, {3322, 41}, {2251, 6},

{2323271, 8}, {93331, 10}

};

private void Update()

{

Profiler.BeginSample("AllocCheck: SortedDictionaryEnumerator");

_sortedDictionary.GetEnumerator();

Profiler.EndSample();

Profiler.BeginSample("AllocCheck: InterfacedSortedDictionaryEnumerator");

_interfacedSortedDictionary.GetEnumerator();

Profiler.EndSample();

Profiler.BeginSample("AllocCheck: SortedDictionaryEnumerator20");

_sortedDictionary20.GetEnumerator();

Profiler.EndSample();

}

（↑の雑な内訳）

<int, int> の場合で
要素1: 104B
インターフェイス経由で要素1: 104 + 64 = 168B
要素20 : 152B （104 + 16 * 3）

<int, int> の場合で

要素1: 104B

インターフェイス経由で要素1: 104 + 64 = 168B

要素20 : 152B （104 + 16 * 3）

まとめ

コレクションをインターフェースとして保持すると、foreach 時に GC Alloc が発生する
- 配列: 普通の Heap Allocation が起きる
- System.Collections.Generic 下のコレクション: Boxing が起きる
Sorted コレクションはそのまま foreach にかけるだけで GC Alloc が発生する

どう対処すればいいか

クラス内部に閉じたコレクションはインターフェース化せずに保持する
- VirtualCast のクライアント開発ではこの方針にしています
- クラス外に公開するコレクションは用途に応じてインターフェースとして公開する場合もありますが、毎フレーム foreach するものは許容しません
Rider の possible object allocation 警告が出ている場所をさらう
Rider や ReShaper を使用している時限定ですが、以下の警告が出ている場所の参照コレクションをたどると見つけやすいと思われます。

※ SortedList<> を foreach にかけようとすると警告が出ましたが、SortedSet<>, SortedDictionary<> では出なかったので参考程度に
Sorted コレクションは foreach にかけない

他参考にした記事

https://ufcpp.net/blog/2018/12/howtoenumerate/
https://ufcpp.net/blog/2018/12/devirtualization/

Category
taraba_ /
技術