LoginSignup
11
10

More than 1 year has passed since last update.

@IShix

【Unity】Listから複数要素取り出しを0Allocで実現する挑戦

Last updated at Posted at 2023-01-03

List<T>から該当する複数要素を取り出す事ってありませんか？
新しいList<T>を作って返すのが直感的ですが、パフォーマンスの事を考えると躊躇してしまいます。という事で、今回は0Allocへの挑戦を記事にしたいと思います。

始まりのコード

C#
List<int> TestNew(int max)
{
    var result = new List<int>();
    foreach (var num in _list)
    {
        if (num <= max)
        {
            result.Add(num);
        }
    }
    return result;
}

環境

  • Unity : 2021.3.15f1
  • プラットフォーム : Unity Editor(Silicon)で再生し確認
  • パフォーマンスの確認 : Unity Profiler
  • ILコードの確認 : Rider の IL viewer

何はともあれパフォーマンスチェック

パターンを出してパフォーマンスチェックしました。
やはり新しいリストを作るのは止めた方が良さそう。ヒープへの割り当ても一番多いし処理時間も長いです。IEnumerable<int> forが割り当ても少なくて良さそうです。

GC Alloc Time
List<int> new 248 B 0.02 ms
IEnumerable<int> LINQ 220 B 0.02 ms
IEnumerable<int> foreach 72 B 0.01 ms
IEnumerable<int> for 56 B 0.01 ms
テストコード
C#
using System.Collections.Generic;
using System.Linq;
using UnityEngine;
using UnityEngine.Profiling;

public sealed class ListSearchTest : MonoBehaviour
{
	List<int> _list;

	void Awake()
	{
		_list = new List<int>(100);
		for (var num = 1; num <= 100; num++)
		{
			_list.Add(num);
		}
	}

	void Update()
	{
		Profiler.BeginSample("List search - New");
		foreach (var num in TestNew(10)){}
		Profiler.EndSample();
        
		Profiler.BeginSample("List search - Linq");
		foreach (var num in TestLinq(10)){}
		Profiler.EndSample();
        
		Profiler.BeginSample("List search - IEnumerable foreach");
		foreach (var num in TestIEnumerableForeach(10)){}
		Profiler.EndSample();
        
		Profiler.BeginSample("List search - IEnumerable for");
		foreach (var num in TestIEnumerableFor(10)){}
		Profiler.EndSample();
	}

	List<int> TestNew(int max)
	{
		var result = new List<int>();
		foreach (var num in _list)
		{
			if (num <= max)
			{
				result.Add(num);
			}
		}
		return result;
	}
    
	IEnumerable<int> TestLinq(int max) => _list.Where(x => x <= max);
    
	IEnumerable<int> TestIEnumerableForeach(int max)
	{
		foreach (var num in _list)
		{
			if (num <= max)
			{
				yield return num;
			}
		}
	}
    
	IEnumerable<int> TestIEnumerableFor(int max)
	{
		for (var i = 0; i < _list.Count; i++)
		{
			var num = _list[i];
			if (num <= max)
			{
				yield return num;
			}
		}
	}
}

IEnumerable<int> foreachメソッドのメモリ割り当てを調査する

テスト結果からIEnumerable<int> foreachを改造して、0Allocを目指したいと思います。何かを生成した訳では無いのに、72Bのアロケーションが発生するのは何故でしょうか？気が進みませんがILコードに解決の糸口がありそうです。

C#
IEnumerable<int> TestIEnumerableForeach(int max)
{
    foreach (var num in _list)
    {
        if (num <= max)
        {
            yield return num;
        }
    }
}

ILから原因を探る

IL上でクラスが自動実装されていて、そのクラスを利用する為に発生したメモリアロケーションである事が分かりました。

IL
IL_0002: newobj  instance void TestClass/'<TestIEnumerableForeach>d__2'::.ctor(int32)

スクリーンショット 2023-01-05 14.52.43.png

structを使う

原因は分かりました。クラスは参照型なのでメモリアロケーションが発生して当たり前です。
自動実装されるクラスを自前のstructに差し替えればうまくいく気がします。念の為、structの生成が0Allocなのかを確認しました。

GC Alloc Time
class 16 B 0.00 ms
struct 0 B 0.00 ms
C#
using UnityEngine;
using UnityEngine.Profiling;

public sealed class ListSearchTest : MonoBehaviour
{
    void Update()
    {
        Profiler.BeginSample("class");
        new TestClass();
        Profiler.EndSample();
        
        Profiler.BeginSample("struct");
        new TestStruct();
        Profiler.EndSample();
    }

    class TestClass{}
    struct TestStruct{}
}

struct IEnumerable<int>の実装失敗

さっそく実装して確認すると、72 Bの割り当てが発生しました。失敗です。なんでー
ILを見ても自動実装されていないし、しばらく検証します。

GC Alloc Time
IEnumerable<int> struct 72 B 0.01 ms
C#
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using UnityEngine.Profiling;

public sealed class ListSearchTest : MonoBehaviour
{
    List<int> _list;

    void Awake()
    {
        _list = new List<int>(100);
        for (var num = 1; num <= 100; num++)
        {
            _list.Add(num);
        }
    }

    void Update()
    {
        Profiler.BeginSample("List search - struct");
        foreach (var num in TestStructEnumerable(10)) {}
        Profiler.EndSample();
    }

    IEnumerable<int> TestStructEnumerable(int max) => new Enumerable(_list, max);

    readonly struct Enumerable : IEnumerable<int>
    {
        readonly IReadOnlyList<int> _list;
        readonly int _max;

        public Enumerable(IReadOnlyList<int> list, int max)
        {
            _list = list;
            _max = max;
        }
        
        IEnumerator<int> IEnumerable<int>.GetEnumerator() => new Enumerator(_list, _max);

        IEnumerator IEnumerable.GetEnumerator() => new Enumerator(_list, _max);

        struct Enumerator : IEnumerator<int>
        {
            readonly IReadOnlyList<int> _list;
            readonly int _max;
            int _current;
            int _index;

            public Enumerator(IReadOnlyList<int> list, int max)
            {
                _list = list;
                _max = max;
                _current = 0;
                _index = 0;
            }
        
            public int Current => _current;
            object IEnumerator.Current => _current;
            public bool MoveNext()
            {
                while (_index < _list.Count)
                {
                    var current = _list[_index];
                    _index++;
                    if (current <= _max)
                    {
                        _current = current;
                        return true;   
                    }
                }
                return false;
            }
            public void Reset() {}
            public void Dispose() {}
        }
    }
}

struct IEnumerable<int>　原因が判明

ボックス化が原因でした。
EnumerableからIEnumerable<int>への自動キャスト(暗黙的な型変換)の影響でした。

C#
IEnumerable<int> TestStructEnumerable(int max) => new Enumerable(_list, max);
IL
IL_000c: box  TestClass/Enumerable

スクリーンショット 2023-01-03 20.09.31.png

struct IEnumerable<int>の完成

ボックス化を2点修正し無事0Alloc達成。
ただ、書くコードが多いのでそんなに実用的ではなさそう。。。使い所としては、Update()など、フレーム単位で実行が必要な場合に使えるかなと思いました。基本は、IEnumerable<int>を返すforで十分です。

GC Alloc Time
IEnumerable<int> struct 0 B 0.01 ms
List<int> new 248 B 0.02 ms
IEnumerable<int> LINQ 220 B 0.02 ms
IEnumerable<int> foreach 72 B 0.01 ms
IEnumerable<int> for 56 B 0.01 ms
C#
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using UnityEngine.Profiling;

public sealed class ListSearchTest : MonoBehaviour
{
    List<int> _list;

    void Awake()
    {
        _list = new List<int>(100);
        for (var num = 1; num <= 100; num++)
        {
            _list.Add(num);
        }
    }

    void Update()
    {
        Profiler.BeginSample("List search - struct");
        foreach (var num in TestStructEnumerable(10)) {}
        Profiler.EndSample();
    }

-   IEnumerator<int> TestStructEnumerable(int max) => new Enumerable(_list, max);
+   Enumerable TestStructEnumerable(int max) => new Enumerable(_list, max);

    readonly struct Enumerable : IEnumerable<int>
    {
        readonly IReadOnlyList<int> _list;
        readonly int _max;

        public Enumerable(IReadOnlyList<int> list, int max)
        {
            _list = list;
            _max = max;
        }

+       public Enumerator GetEnumerator() => new Enumerator(_list, _max);

-       IEnumerator<int> IEnumerable<int>.GetEnumerator() => new Enumerator(_list, _max);
+       IEnumerator<int> IEnumerable<int>.GetEnumerator() => GetEnumerator();

-       IEnumerator IEnumerable.GetEnumerator() => new Enumerator(_list, _max);
+       IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();

        public struct Enumerator : IEnumerator<int>
        {
            readonly IReadOnlyList<int> _list;
            readonly int _max;
            int _current;
            int _index;

            public Enumerator(IReadOnlyList<int> list, int max)
            {
                _list = list;
                _max = max;
                _current = 0;
                _index = 0;
            }
        
            public int Current => _current;
            object IEnumerator.Current => _current;
            public bool MoveNext()
            {
                while (_index < _list.Count)
                {
                    var current = _list[_index];
                    _index++;
                    if (current <= _max)
                    {
                        _current = current;
                        return true;   
                    }
                }
                return false;
            }
            public void Reset() {}
            public void Dispose() {}
        }
    }
}

感想

実用的かは置いておいて勉強になったので挑戦して良かったです。
普段無意識に書いてるコードも、プログラマーの代わりにコンパイラが自動実装などを駆使して頑張ってくれてるんだなと思うとC#がますます好きになりました。いつもありがとうC#。

今回ILコードを見るのにRiderのIL viewerを使いましたやりたい事があればほぼ対応しているRiderはマジで神エディタです。Unityの標準エディタにして欲しい。

現在、Rider上でビルドする事で確認できるILコードは、Unityより出力されたILコードとは異なりますが、近い将来確認できるようになるとの事です。楽しみですね。

[追記] 内部で使うListを取得側に要求する

メモリ管理を取得側に委ねるパターンです。
取得側で結果を保存するList<int>を用意して渡す必要があります。

C#
List<int> TestRef(int max, List<int> result)
{
    result.Clear();

    foreach (var num in _list)
    {
        if (num <= max)
        {
            result.Add(num);
        }
    }
    return result;
}
GC Alloc Time
List<int> ref 0 B 0.01 ms
IEnumerable<int> struct 0 B 0.01 ms
List<int> new 248 B 0.02 ms
IEnumerable<int> LINQ 220 B 0.02 ms
IEnumerable<int> foreach 72 B 0.01 ms
IEnumerable<int> for 56 B 0.01 ms
テストコード全文
C#
using System.Collections.Generic;
using UnityEngine;
using UnityEngine.Profiling;

public class ListSearchTest : MonoBehaviour
{
    List<int> _list;
    List<int> _result = new ();
    
    void Awake()
    {
        _list = new List<int>(100);
        for (var num = 1; num <= 100; num++)
        {
            _list.Add(num);
        }
    }

    void Update()
    {
        Profiler.BeginSample("List search - ref");
        foreach (var num in TestRef(10, _result)) {}
        Profiler.EndSample();
    }

    List<int> TestRef(int max, List<int> result)
    {
        result.Clear();
        
        foreach (var num in _list)
        {
            if (num <= max)
            {
                result.Add(num);
            }
        }
        return result;
    }
}

以上となります。
最後まで読んでいただきありがとうございました！

11
10
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
11
10