Go to Qiita Advent Calendar 2024 Top
LoginSignup
7
4

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@abetakahiro123

【.NET 9.0】InlineArray を使った値型リストを作ってみる

Last updated at Posted at 2024-09-24

はじめに

たまに 要素数が少ない（10 とか）軽量なリスト が欲しい場面があります。C# でよく使う List<T> は参照型なのでヒープが発生します。殆どの場合、両者にパフォーマンス的な違いはありませんが、ヒープを回避できるなら回避したいのがプログラマの性です。

.NET 8 で System.Runtime.CompilerServices.InlineArrayAttribute が追加され、お手軽に構造体バッファを利用できるようになりました。今回はこれを利用して、内部バッファを持つ値型リストを作ってみます。

// インラインバッファの長さ
// 大きくしすぎるとスタックオーバーフローの危険がある
[InlineArray(10)]
struct InlineBuffer<T>
{
    internal T _value;
}

var buffer = new InlineBuffer<int>();
Span<int> span = buffer;
Assert.Equal(10, span.Length);

サンプルコード

InlineList コード 
using System.ComponentModel;
using System.Diagnostics;
using System.Diagnostics.CodeAnalysis;
using System.Runtime.CompilerServices;

/// <summary>
/// 要素をインラインで保持する値型リスト
/// </summary>
/// <typeparam name="T"></typeparam>
[CollectionBuilder(typeof(InlineListBuilder), nameof(InlineListBuilder.Create))]
[DebuggerDisplay("Count = {Count}")]
[DebuggerTypeProxy(typeof(DebugView<>))]
internal struct InlineList<T> : IEquatable<InlineList<T>>
{
    // NOTE: インラインバッファの長さ。コンパイル定数
    // 大きくしすぎるとスタックオーバーフローの危険がある
    private const int BufferLength = 10;

    [InlineArray(BufferLength)]
    private struct InlineBuffer
    {
        internal T _value;
    }

    [UnsafeAccessor(UnsafeAccessorKind.Field, Name = "_length")]
    private static extern ref int _length(ref Span<T> span);

    private InlineBuffer _buffer;
    private T[]? _array;
    private int _count;

    /// <summary>
    /// 要素数
    /// </summary>
    public readonly int Count => this._count;

    /// <summary>
    /// 容量
    /// </summary>
    public readonly int Capacity => this._array is not null ? this._array.Length : BufferLength;

    /// <summary>
    /// 要素のスパン
    /// </summary>
    public readonly Span<T> Span
    {
        get
        {
            if (this._array is not null)
                return this._array.AsSpan(0, this._count);

            var result = new Span<T>(ref Unsafe.AsRef(in this._buffer._value));
            _length(ref result) = this._count;

            return result;
        }
    }

    /// <summary>
    /// コンストラクタ
    /// </summary>
    /// <param name="capacity"></param>
    /// <exception cref="ArgumentOutOfRangeException"></exception>
    public InlineList(int capacity)
    {
        ArgumentOutOfRangeException.ThrowIfNegative(capacity);

        if (capacity > BufferLength)
            this._array = new T[capacity];
        this._count = 0;
    }

    /// <summary>
    /// コンストラクタ
    /// </summary>
    /// <param name="values"></param>
    public InlineList(ReadOnlySpan<T> values)
    {
        if (values.Length > BufferLength)
            this._array = new T[values.Length];

        Span<T> span = this._array is not null ? this._array.AsSpan() : this._buffer;
        values.CopyTo(span);
        this._count = values.Length;
    }

    private void SizeUp(int min = 0)
    {
        Span<T> span = this._array is not null ? this._array.AsSpan() : this._buffer;
        var newArray = new T[Math.Max(span.Length * 2, min)];
        span.CopyTo(newArray);
        this._array = newArray;
    }

    /// <summary>
    /// 要素を追加
    /// </summary>
    /// <param name="value"></param>
    public void Add(in T value)
    {
        if (this._count is BufferLength)
            this.SizeUp();

        Span<T> span = this._array is not null ? this._array.AsSpan() : this._buffer;
        span[this._count] = value;
        ++this._count;
    }

    /// <summary>
    /// 複数の要素を追加
    /// </summary>
    /// <param name="values"></param>
    public void AddRange(ReadOnlySpan<T> values)
    {
        if (this._count + values.Length > BufferLength)
            this.SizeUp(this._count + values.Length);
        Span<T> span = this._array is not null ? this._array.AsSpan() : this._buffer;
        values.CopyTo(span.Slice(this._count));
        this._count += values.Length;
    }

    /// <summary>
    /// 指定した値を削除<br/>
    /// 削除に成功した場合 true、それ以外は false を返す
    /// </summary>
    /// <param name="value"></param>
    /// <returns></returns>
    public bool Remove(in T value)
    {
        Span<T> span = this._array is not null ? this._array.AsSpan() : this._buffer;
        var span2 = span.Slice(0, this._count);
        for (int n = 0; n < span2.Length; n++)
        {
            if (EqualityComparer<T>.Default.Equals(span2[n], value))
            {
                this.RemoveAt(n);
                return true;
            }
        }

        return false;
    }

    /// <summary>
    /// 指定したインデックスの要素を削除
    /// </summary>
    /// <param name="index"></param>
    /// <exception cref="ArgumentOutOfRangeException"></exception>
    public void RemoveAt(int index)
    {
        ArgumentOutOfRangeException.ThrowIfNegative(index);
        ArgumentOutOfRangeException.ThrowIfGreaterThanOrEqual(index, this._count);

        Span<T> span = this._array is not null ? this._array.AsSpan() : this._buffer;
        --this._count;
        span.Slice(index + 1, this._count - index).CopyTo(span.Slice(index, this._count - index));
        span[this._count] = default!;
    }

    /// <summary>
    /// 全ての要素を削除
    /// </summary>
    public void Clear() => this._count = 0;

    /// <summary>
    /// 要素を列挙
    /// </summary>
    /// <returns></returns>
    // NOTE: メンバーを候補に表示しないようにする属性
    // 同じアセンブリからアクセスする場合は表示される
    [EditorBrowsable(EditorBrowsableState.Never)]
    [Obsolete("Span を使用してください。")]
    public readonly Span<T>.Enumerator GetEnumerator() => this.Span.GetEnumerator();

    /// <summary>
    /// 同値性を取得
    /// </summary>
    /// <param name="obj"></param>
    /// <returns></returns>
    public readonly override bool Equals([NotNullWhen(true)] object? obj) => obj is InlineList<T> other && this.Equals(other);

    /// <summary>
    /// 同値性を取得
    /// </summary>
    /// <param name="other"></param>
    /// <returns></returns>
    /// <exception cref="NotImplementedException"></exception>
    public readonly bool Equals(InlineList<T> other) => this.Span.SequenceEqual(other.Span);

    /// <summary>
    /// ハッシュコードを取得
    /// </summary>
    /// <returns></returns>
    public override int GetHashCode()
    {
        var hashCode = new HashCode();
        var span = this.Span;
        foreach (var n in span.Slice(Math.Max(0, span.Length - 10)))
            hashCode.Add(n);

        return hashCode.ToHashCode();
    }

    /// <summary>
    /// 文字列を取得
    /// </summary>
    /// <returns></returns>
    public readonly override string ToString() => $"Count: {this.Count}";

    /// <summary>
    /// Span に暗黙的変換
    /// </summary>
    /// <param name="list"></param>
    public static implicit operator Span<T>(in InlineList<T> list) => list.Span;

    /// <summary>
    /// ReadOnlySpan に暗黙的変換
    /// </summary>
    /// <param name="list"></param>
    public static implicit operator ReadOnlySpan<T>(in InlineList<T> list) => list.Span;
}

/// <summary>
/// InlineList のビルダー
/// </summary>
file static class InlineListBuilder
{
    public static InlineList<T> Create<T>(ReadOnlySpan<T> values) => new InlineList<T>(values);
}

/// <summary>
/// デバッグビュー
/// </summary>
/// <typeparam name="T"></typeparam>
file class DebugView<T>
{
    private readonly T[] _array;

    public DebugView(InlineList<T> value) => this._array = value.Span.ToArray();

    [DebuggerBrowsable(DebuggerBrowsableState.RootHidden)]
    public T[] Items => this._array;
}
テストコード 
using System.Runtime.CompilerServices;
using Xunit;

public class _InlineListTest
{
    [Fact]
    void HowToUse()
    {
        var numbers = new InlineList<int>();
        numbers.Add(1);
        numbers.Add(2);
        numbers.Add(3);
        Assert.Equal([1, 2, 3], numbers);

        numbers.Remove(2);
        Assert.Equal([1, 3], numbers);

        numbers.Clear();
        Assert.Equal([], numbers);

        // 内部バッファを超える場合は自動で拡張される
        numbers.AddRange([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]);
        Assert.Equal([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11], numbers);

        // 参照型も可
        // コレクション式も使える
        InlineList<string> texts = ["a", "b", "c"];
        var got = new InlineList<string>();
        foreach (var text in texts.Span)
            got.Add(text);
        Assert.Equal(["a", "b", "c"], got.Span);
    }

    [Fact]
    void Count()
    {
        var list = new InlineList<int>(10);
        Assert.Equal(0, list.Count);

        list.Add(1);
        list.Add(2);
        list.Add(3);
        Assert.Equal(3, list.Count);
    }

    [Fact]
    void Capacity()
    {
        Assert.Equal(10, new InlineList<int>(0).Capacity);
        Assert.Equal(10, new InlineList<int>(10).Capacity);
        Assert.Equal(20, new InlineList<int>(20).Capacity);
    }

    [Fact]
    void Span()
    {
        var list = new InlineList<int>(10);
        Assert.Equal([], list.Span);

        list.Add(1);
        list.Add(2);
        list.Add(3);
        Assert.Equal([1, 2, 3], list.Span);
    }

    [Fact]
    void Span_ReferenceType()
    {
        var list = new InlineList<string>(10);
        Assert.Equal([], list.Span);

        list.Add("1");
        list.Add("2");
        list.Add("3");
        Assert.Equal(["1", "2", "3"], list.Span);
    }

    [Fact]
    void Constructor()
    {
        Assert.Throws<ArgumentOutOfRangeException>(() => new InlineList<int>(-1));

        var list = new InlineList<int>([1, 2, 3]);
        Assert.Equal([1, 2, 3], list.Span);
    }

    [Fact]
    void Add()
    {
        var list = new InlineList<int>();
        list.Add(1);
        list.Add(2);
        list.Add(3);
        Assert.Equal([1, 2, 3], list.Span);

        list.Add(4);
        list.Add(5);
        list.Add(6);
        list.Add(7);
        list.Add(8);
        list.Add(9);
        list.Add(10);
        list.Add(11);
        Assert.Equal([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11], list.Span);
        Assert.True(list.Capacity > 10);
    }

    [Fact]
    void AddRange()
    {
        var list = new InlineList<int>();
        list.AddRange([1, 2, 3]);
        Assert.Equal([1, 2, 3], list.Span);

        list.AddRange([4, 5, 6, 7, 8, 9, 10, 11]);
        Assert.Equal([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11], list.Span);

        var list2 = new InlineList<int>(stackalloc int[10]);
        list2.AddRange(stackalloc int[100]);

        Assert.Equal(110, list2.Count);
    }

    [Fact]
    void Remove()
    {
        var list = new InlineList<int>([1, 2, 3, 4, 5]);
        Assert.True(list.Remove(4));
        Assert.Equal([1, 2, 3, 5], list.Span);

        Assert.False(list.Remove(4));

        Assert.True(list.Remove(5));
        Assert.Equal([1, 2, 3], list.Span);

        Assert.True(list.Remove(1));
        Assert.Equal([2, 3], list.Span);
    }

    [Fact]
    void RemoveAt()
    {
        var list = new InlineList<int>([1, 2, 3, 4, 5]);
        Assert.Throws<ArgumentOutOfRangeException>(() => list.RemoveAt(-1));
        Assert.Throws<ArgumentOutOfRangeException>(() => list.RemoveAt(5));

        list.RemoveAt(2);
        Assert.Equal([1, 2, 4, 5], list.Span);

        list.RemoveAt(0);
        Assert.Equal([2, 4, 5], list.Span);

        list.RemoveAt(2);
        Assert.Equal([2, 4], list.Span);
    }

    [Fact]
    void Clear()
    {
        var list = new InlineList<int>([1, 2, 3, 4, 5]);
        list.Clear();
        Assert.Equal([], list.Span);
    }

    [Fact]
    void GetEnumerator()
    {
        var list = new InlineList<int>([1, 2, 3]);
        var got = new InlineList<int>();
        // GetEnumerator が警告になること
#pragma warning disable CS0618
        foreach (var n in list)
#pragma warning restore CS0618
            got.Add(n);

        Assert.Equal([1, 2, 3], got.Span);
    }

    [Fact]
    void EqualsTest()
    {
        var list1 = new InlineList<int>([1, 2, 3]);
        var list2 = new InlineList<int>([1, 2, 3]);
        var list3 = new InlineList<int>([1, 2, 4]);

        Assert.True(list1.Equals(list2));
        Assert.False(list1.Equals(list3));
    }

    [Fact]
    void Equals_ObjectTest()
    {
        object list1 = new InlineList<int>([1, 2, 3]);
        object list2 = new InlineList<int>([1, 2, 3]);
        object list3 = new InlineList<int>([1, 2, 4]);

        Assert.True(list1.Equals(list2));
        Assert.False(list1.Equals(list3));
    }

    [Fact]
    void GetHashCodeTest()
    {
        var list1 = new InlineList<int>([1, 2, 3]);
        var list2 = new InlineList<int>([1, 2, 3]);
        var list3 = new InlineList<int>([1, 2, 4]);
        var list4 = new InlineList<int>([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]);

        Assert.Equal(list1.GetHashCode(), list2.GetHashCode());
        Assert.NotEqual(list1.GetHashCode(), list3.GetHashCode());
        Assert.NotEqual(list1.GetHashCode(), list4.GetHashCode());
    }

    [Fact]
    void Operator()
    {
        InlineList<int> list = [1, 2, 3];
        Span<int> span = list;
        Assert.Equal([1, 2, 3], span);

        ReadOnlySpan<int> readOnlySpan = list;
        Assert.Equal([1, 2, 3], readOnlySpan);
    }

    [Fact]
    void CollectionBuilder()
    {
        InlineList<int> list = [1, 2, 3];
        Assert.Equal([1, 2, 3], list.Span);
    }

    // [Fact]
    // void StackOverflow()
    // {
    //     var want = Unsafe.SizeOf<int>() * 10 + Unsafe.SizeOf<int[]?>() + Unsafe.SizeOf<int>();
    //     want += want % Unsafe.SizeOf<IntPtr>();
    //     var got = Unsafe.SizeOf<InlineList<int>>();
    //     Assert.Equal(want, got); // 48 or 56

    //     var count = 13734;
    //     // x64 だとスタック領域は 769,104 byte 程度（実行環境依存）
    //     void Call(ref InlineList<int> list)
    //     {
    //         if (--count <= 0)
    //             return;
    //         var list2 = new InlineList<int>();
    //         Call(ref list2);
    //     }

    //     var list = new InlineList<int>();
    //     Call(ref list);
    // }

    [Fact]
    void PassByValue()
    {
        InlineList<int> list = [1, 2, 3];

        void ClearPassByValue(InlineList<int> list)
        {
            list.Span.Clear();
        }
        ClearPassByValue(list);
        // 内部バッファの場合は書き換えられない
        Assert.Equal([1, 2, 3], list.Span);

        InlineList<int> list2 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11];
        ClearPassByValue(list2);
        // 内部バッファが配列の場合は書き換えられる
        Assert.Equal(stackalloc int[11], list2.Span);
    }

    [Fact]
    void PassByIn()
    {
        InlineList<int> list = [1, 2, 3];

        void ClearPassByValue(in InlineList<int> list)
        {
            list.Span.Clear();
        }
        ClearPassByValue(list);
        // 参照のため書き換えられる
        Assert.Equal([0, 0, 0], list.Span);

        // 内部バッファが配列の場合も書き換えられる
        InlineList<int> list2 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11];
        ClearPassByValue(list2);
        Assert.Equal(stackalloc int[11], list2.Span);
    }

    static void Foreach(Performance p)
    {
        var inlineList = new InlineList<int>();
        p.AddTest("GetEnumerator", () =>
        {
            for (var i = 0; i < 10000; i++)
            {
#pragma warning disable CS0618
                foreach (var n in inlineList)
#pragma warning restore CS0618
                    n.GetHashCode();
            }
        });

        p.AddTest("Span", () =>
        {
            for (var i = 0; i < 10000; i++)
            {
                foreach (var n in inlineList.Span)
                    n.GetHashCode();
            }
        });
    }

    static void CopyCost(Performance p)
    {
        // コンパイラの最適化でメソッド呼び出しが削除されないようにする
        [MethodImpl(MethodImplOptions.NoInlining)]
        void PassByValueList(List<int> list)
        { }
        p.AddTest("List<T>", () =>
        {
            var list = new List<int>();
            for (var i = 0; i < 10000; i++)
                PassByValueList(list);
        });

        // コンパイラの最適化でメソッド呼び出しが削除されないようにする
        [MethodImpl(MethodImplOptions.NoInlining)]
        void PassByValueInlineList(InlineList<int> list)
        { }
        p.AddTest("InlineList<T>", () =>
        {
            var list = new InlineList<int>();
            for (var i = 0; i < 10000; i++)
                PassByValueInlineList(list);
        });
    }

    static void AddValue(Performance p)
    {
        p.AddTest("List<T>", () =>
        {
            for (var i = 0; i < 10000; i++)
            {
                var list = new List<int>();
                list.Add(1);
                list.Add(2);
                list.Add(3);
            }
        });

        p.AddTest("InlineList<T>", () =>
        {
            for (var i = 0; i < 10000; i++)
            {
                var list = new InlineList<int>();
                list.Add(1);
                list.Add(2);
                list.Add(3);
            }
        });
    }
}

使い方

var numbers = new InlineList<int>();
numbers.Add(1);
numbers.Add(2);
numbers.Add(3);
Assert.Equal([1, 2, 3], numbers);

numbers.Remove(2);
Assert.Equal([1, 3], numbers);

numbers.Clear();
Assert.Equal([], numbers);

// 内部バッファを超える場合は自動で拡張される
numbers.AddRange([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]);
Assert.Equal([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11], numbers);

// 参照型も可
// コレクション式も使える
InlineList<string> texts = ["a", "b", "c"];
var got = new InlineList<string>();
foreach (var text in texts.Span)
    got.Add(text);
Assert.Equal(["a", "b", "c"], got.Span);
  • List<T> のような感覚で使えるようにしてみました
  • 要素を追加したときに内部バッファを超える場合は自動で拡張されます
  • コレクション式 [1, 2, 3] に対応しています
  • foreach するときはパフォーマンス上 InlineList<T>.Span を使用するのがよさげです

スパンのラップクラスのような位置づけのため、多態性は持たせず IEnumerable<T> は継承していません。
基本的に Span<T> へのつなぎに使う想定です。

スタックオーバーフローに注意

var want = Unsafe.SizeOf<int>() * 10 + Unsafe.SizeOf<int[]?>() + Unsafe.SizeOf<int>();
want += want % Unsafe.SizeOf<IntPtr>();
var got = Unsafe.SizeOf<InlineList<int>>();
Assert.Equal(want, got); // 48 or 56

var count = 13734;
// x64 だとスタック領域は 769,104 byte 程度（実行環境依存）
void Call(ref InlineList<int> list)
{
    if (--count <= 0)
        return;
    var list2 = new InlineList<int>();
    Call(ref list2);
}

var list = new InlineList<int>();
Call(ref list);

スタックにバッファを取るため、StackOverflowException には気をつけたいところです。↑ の例では再帰呼び出しの回数を検証してみました。実行環境やメソッドの呼び出し階層に依存しますが、だいたい 700KB 程度でスタックを使い切るようです。
特に T が値型の場合は、その大きさに注意が必要です。殆どの場合は問題ないと思いますが、インラインリストを入れ子で使うのは避けたほうがよさそうです。

アンセーフなところ

/// <summary>
/// 要素のスパン
/// </summary>
public readonly Span<T> Span
{
    get
    {
        if (this._array is not null)
            return this._array.AsSpan(0, this._count);

        var result = new Span<T>(ref Unsafe.AsRef(in this._buffer._value));
        _length(ref result) = this._count;

        return result;
    }
}
  • 参照（スパン）を返しているプロパティで、読み取り専用実装なのですが書き換え可能な参照を返しています
  • これは値渡ししたときにおかしな挙動をするので注意が必要です
  • この型はバッファとして使うことを想定しているため、値渡しで使うのは非推奨です。パフォーマンスもあまり良くありません（後述）
InlineList<int> list = [1, 2, 3];

void ClearPassByValue(InlineList<int> list)
{
    list.Span.Clear();
}
ClearPassByValue(list);
// 内部バッファの場合は書き換えられない
Assert.Equal([1, 2, 3], list.Span);

InlineList<int> list2 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11];
ClearPassByValue(list2);
// 内部バッファが配列の場合は書き換えられる
Assert.Equal(stackalloc int[11], list2.Span);

パフォーマンス比較

Test Score % CG0
Foreach (2)
GetEnumerator 5,307 100.0% 0
Span 10,682 201.3% 0
CopyCost (2)
List 5,786 100.0% 0
InlineList 5,328 92.1% 0
AddValue (2)
List 658 100.0% 56
InlineList 1,092 166.0% 0

実行環境: Windows11 x64 .NET Runtime 9.0.0
Score は高いほどパフォーマンスがよいです。
GC0 はガベージコレクション回数を表します（少ないほどパフォーマンスがよい）。

  • foreach(list) より foreach(list.Span) のほうがパフォーマンスが良いです
  • 値コピーは非常にパフォーマンスが悪い・・・わけでもなさそうです。x86 x64 でこのあたりは違うかもしれません
  • よく使いそうなパターンの new() Add() のパターンでは、List<T> と比較してヒープがなく、パフォーマンスも良さそうです

おわりに

今回は概ね狙いどおりの実装ができました。しかし挙動が曖昧なところがあるので、使い所を選びそうです。

7
4
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
7
4

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?