【C# .NET 9.0】InlineArray を使用した値型辞書を作ってみる

# はじめに

今回は、前回 [InlineArray を使った値型リストを作ってみる](https://qiita.com/abetakahiro123/items/d3a724dba68cb16ca722) の記事の辞書版です。

関連

- [【.NET 9.0】InlineArray を使った値型リストを作ってみる](https://qiita.com/abetakahiro123/items/d3a724dba68cb16ca722)
- [メモリ連続の辞書構造を作ってみる](https://qiita.com/abetakahiro123/items/0264be778c7c618d8245)
- [【C#】ジェネリックの null チェックでガベージを出さない方法を模索](https://qiita.com/abetakahiro123/items/636e1566d403958ebeb2)

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

.NET 8 で [`System.Runtime.CompilerServices.InlineArrayAttribute`](https://learn.microsoft.com/ja-jp/dotnet/api/system.runtime.compilerservices.inlinearrayattribute?view=net-8.0) が追加され、お手軽に構造体バッファを利用できるようになりました。今回はこれを利用して、内部バッファを持つ値型リストを作ってみます。

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

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

## サンプルコード

<details>
<summary>InlineTable.cs</summary>

```cs
using System.Diagnostics;
using System.Diagnostics.CodeAnalysis;
using System.Runtime.CompilerServices;

/// <summary>
/// メモリ連続の値型辞書
/// </summary>
/// <typeparam name="K"></typeparam>
/// <typeparam name="V"></typeparam>
internal struct InlineTable<K, V>
{
    // NOTE: インラインバッファの長さ。コンパイル定数
    // 大きくしすぎるとスタックオーバーフローの危険がある
    // 参考 x64: sizeof(InlineTable<string, string>) = (8 + 8 + 12) * 17 + 8 * 3 + 4 = 504 bytes
    private const int BufferLength = 17;

    [InlineArray(BufferLength)]
    private struct InlineKeyBuffer
    {
        internal K Value;
    }

    [InlineArray(BufferLength)]
    private struct InlineValueBuffer
    {
        internal V Value;
    }

    private record struct Entry
    {
        internal int Bucket;
        internal int HashCode;
        internal int Next;
    }

    [InlineArray(BufferLength)]
    private struct InlineEntryBuffer
    {
        internal Entry Value;
    }

    private InlineEntryBuffer _entryBuffer;
    private Entry[]? _entries;
    private readonly Span<Entry> EntrySpan
    {
        get
        {
            if (this._entries is not null)
                return this._entries;

            return SpanUtl<Entry>.AsSpan(in this._entryBuffer.Value, BufferLength);
        }
    }

    private InlineKeyBuffer _keyBuffer;
    private K[]? _keys;
    private readonly Span<K> KeySpan
    {
        get
        {
            if (this._keys is not null)
                return this._keys;

            return SpanUtl<K>.AsSpan(in this._keyBuffer.Value, BufferLength);
        }
    }

    private InlineValueBuffer _valueBuffer;
    private V[]? _values;
    private readonly Span<V> ValueSpan
    {
        get
        {
            if (this._values is not null)
                return this._values;

            return SpanUtl<V>.AsSpan(in this._valueBuffer.Value, BufferLength);
        }
    }

    /// <summary>
    /// キーのスパン
    /// </summary>
    public readonly ReadOnlySpan<K> Keys => this.KeySpan[..this._count];

    /// <summary>
    /// 値のスパン
    /// </summary>
    public readonly Span<V> Values => this.ValueSpan[..this._count];

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

    /// <summary>
    /// 容量
    /// </summary>
    public readonly int Capacity => this.EntrySpan.Length;

    /// <summary>
    /// 取得 キーが存在しない場合 default 値を追加 O(1)
    /// </summary>
    /// <param name="key"></param>
    /// <returns></returns>
    public ref V this[in K key] => ref this.Insert(key, false);

    /// <summary>
    /// 追加 O(1) 既にキーが存在する場合例外
    /// </summary>
    /// <param name="key"></param>
    /// <param name="value"></param>
    /// <exception cref="System.InvalidOperationException"></exception>
    public void Add(in K key, in V value) => this.Insert(key, true) = value;

    /// <summary>
    /// 追加 O(1) 既にキーが存在する場合例外
    /// </summary>
    /// <param name="key"></param>
    /// <returns></returns>
    /// <exception cref="System.InvalidOperationException"></exception>
    public ref V Add(in K key) => ref this.Insert(key, true);

    private void Resize() => this.Resize(HashUtl.ExpandPrime(this._count), false);

    private void Resize(int newSize, bool forceNewHashCodes)
    {
        var entries2 = new Entry[newSize];
        var entrySpan = this.EntrySpan;
        entrySpan.CopyTo(entries2);
        var span = entries2.AsSpan(0, entrySpan.Length);
        for (int n = 0; n < span.Length; ++n)
            span[n].Bucket = default;

        if (forceNewHashCodes)
        {
            for (int n = 0; n < this._count; n++)
            {
                ref var entry = ref entries2[n];
                if (entry.Next > 0)
                {
                    entry.HashCode = HashUtl.GetHashCodeKey(this.KeySpan[n]);
                }
            }
        }
        for (int n = 0; n < this._count; n++)
        {
            ref var entry = ref entries2[n];
            int num = entry.HashCode % newSize;
            ref var tmp = ref entries2[num];
            entry.Next = tmp.Bucket;
            tmp.Bucket = n + 1;
        }
        this._entries = entries2;

        var keys2 = new K[newSize];
        var keySpan = this.KeySpan[..this._count];
        keySpan.CopyTo(keys2);
        keySpan.Clear();
        this._keys = keys2;

        var values2 = new V[newSize];
        var valueSpan = this.Values[..this._count];
        valueSpan.CopyTo(values2);
        valueSpan.Clear();
        this._values = values2;
    }

    private ref V Insert(in K key, bool add, scoped ref bool exist)
    {
        int num = HashUtl.GetHashCodeKey(key);
        var entrySpan = this.EntrySpan;
        int num2 = num % entrySpan.Length;
        ref var entry2 = ref entrySpan[num2];
        var n = entry2.Bucket;
        while (n > 0)
        {
            ref var tmp = ref entrySpan[n - 1];
            if (tmp.HashCode == num && EqualityComparer<K>.Default.Equals(this.KeySpan[n - 1], key))
            {
                if (add)
                    throw new InvalidOperationException($"Exist key {key}");
                exist = true;
                return ref this.Values[n - 1];
            }
            n = tmp.Next;
        }
        if (this._count == entrySpan.Length)
        {
            this.Resize();
            num2 = num % entrySpan.Length;
            entrySpan = this.EntrySpan;
        }
        ref var entry22 = ref entrySpan[num2];
        int num4 = this._count;
        this._count++;
        ref var entry4 = ref entrySpan[num4];
        this.KeySpan[num4] = key;
        entry4.HashCode = num;
        entry4.Next = entry22.Bucket;

        entry22.Bucket = num4 + 1;
        exist = false;
        return ref this.Values[num4];
    }

    private ref V Insert(in K key, bool add)
    {
        bool dummy = false;
        return ref this.Insert(key, add, ref dummy);
    }

    /// <summary>
    /// 値を取得 O(1)
    /// キーは新たに作成されない、作成する場合 [] を使用
    /// </summary>
    /// <param name="key"></param>
    /// <param name="value"></param>
    /// <returns></returns>
    public readonly bool TryGetValue(in K key, out V value)
    {
        var entrySpan = this.EntrySpan;
        var valueSpan = this.ValueSpan;
        int num = HashUtl.GetHashCodeKey(key);
        int num2 = num % entrySpan.Length;
        ref var entry2 = ref entrySpan[num2];
        var n = entry2.Bucket;
        while (n > 0)
        {
            ref var tmp = ref entrySpan[n - 1];
            if (tmp.HashCode == num && EqualityComparer<K>.Default.Equals(this.KeySpan[n - 1], key))
            {
                value = valueSpan[n - 1];
                return true;
            }
            n = tmp.Next;
        }
        value = default!;
        return false;
    }

    /// <summary>
    /// キーが存在する場合 true O(1)
    /// </summary>
    /// <param name="key"></param>
    /// <returns></returns>
    public readonly bool ContainsKey(in K key) => this.TryGetValue(key, out _);

    /// <summary>
    /// 値を取得 O(1)
    /// キーを新たに作成、既に存在している場合 exist は true
    /// </summary>
    /// <param name="key"></param>
    /// <param name="exist"></param>
    /// <returns></returns>
    public ref V AddOrRef(in K key, out bool exist)
    {
        bool tmp = false;
        ref var result = ref this.Insert(key, false, ref tmp);
        exist = tmp;
        return ref result!;
    }

    /// <summary>
    /// クリア
    /// </summary>
    public void Clear()
    {
        if (this._count > 0)
        {
            this.EntrySpan.Clear();
            this.KeySpan[..this._count].Clear();
            this.Values[..this._count].Clear();
            this._count = 0;
        }
    }

    /// <summary>
    /// 要素を削除 O(n)
    /// </summary>
    /// <param name="key"></param>
    /// <returns></returns>
    public bool Remove(in K key)
    {
        var entrySpan = this.EntrySpan;
        int num = HashUtl.GetHashCodeKey(key);
        int num2 = num % entrySpan.Length;
        int num3 = 0;
        int n = entrySpan[num2].Bucket;
        var keySpan = this.KeySpan;
        var valueSpan = this.ValueSpan;
        while (n > 0)
        {
            var n2 = n - 1;
            ref var entry = ref entrySpan[n2];
            if (entry.HashCode == num && EqualityComparer<K>.Default.Equals(this.KeySpan[n2], key))
            {
                if (num3 is 0)
                    entrySpan[num2].Bucket = entry.Next;
                else
                    entrySpan[num3].Next = entry.Next;

                var rightIndex = this._count - 1;
                // コンパクション
                for (int m = n2; m < rightIndex; ++m)
                {
                    ref var left = ref entrySpan[m];
                    ref var right = ref entrySpan[m + 1];
                    var bucket = left.Bucket;
                    left = right;
                    left.Bucket = bucket;
                    keySpan[m] = keySpan[m + 1];
                    valueSpan[m] = valueSpan[m + 1];
                }
                for (int m = 0; m < entrySpan.Length; ++m)
                {
                    ref var left = ref entrySpan[m];
                    if (left.Bucket > n2)
                        --left.Bucket;
                    if (left.Next > n2)
                        --left.Next;
                }
                ref var last = ref entrySpan[rightIndex];
                var bucket2 = last.Bucket;
                last = default;
                last.Bucket = bucket2;
                keySpan[rightIndex] = default!;
                valueSpan[rightIndex] = default!;

                --this._count;
                return true;
            }
            num3 = n2;
            n = entry.Next;
        }
        return false;
    }
}

file class DebugView<K, V>
{
    private readonly (K, V)[] _values;

    public DebugView(InlineTable<K, V> value)
    {
        this._values = new (K, V)[value.Keys.Length];

        for (int n = 0; n < this._values.Length; ++n)
            this._values[n] = (value.Keys[n], value.Values[n]);
    }

    [DebuggerBrowsable(DebuggerBrowsableState.RootHidden)]
    public (K, V)[] Items => this._values;
}

file static class HashUtl
{
    private static bool IsPrime(int candidate)
    {
        if ((candidate & 1) != 0)
        {
            int num = (int)MathF.Sqrt(candidate);
            for (int i = 3; i <= num; i += 2)
                if (candidate % i == 0)
                    return false;
            return true;
        }
        return candidate == 2;
    }

    internal static int GetPrime(int min)
    {
        for (int j = min | 1; j < int.MaxValue; j += 2)
            if (IsPrime(j) && (j - 1) % 101 != 0)
                return j;
        return min;
    }

    internal static int ExpandPrime(int oldSize)
    {
        int num = 2 * oldSize;
        if (num > 2146435069 && 2146435069 > oldSize)
            return 2146435069;
        return GetPrime(num);
    }

    private static bool IsNull<T>([NotNullWhen(false)] in T value) where T : allows ref struct
    {
        if (typeof(T).IsValueType)
        {
            if (typeof(T).IsGenericType && typeof(T).GetGenericTypeDefinition() == typeof(Nullable<>))
            {
                return value is null;
            }
            return false;
        }
        return value is null;
    }

    internal static int GetHashCodeKey<T>(in T value)
    {
        if (IsNull(value)) return 0;
        return value.GetHashCode() & int.MaxValue;
    }
}

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

    internal static Span<T> AsSpan(scoped in T value, int length)
    {
        var result = new Span<T>(ref Unsafe.AsRef(in value));
        _length(ref result) = length;
        return result;
    }
}
```

</details>

<details>
<summary>テストコード</summary>

```cs
using System.Runtime.CompilerServices;
using Xunit;

public class _InlineTableTest
{
    [Fact]
    void HowToUse()
    {
        // 使い方
        var table = new InlineTable<int, string>();
        table.Add(1, "one");
        table.Add(5, "five");
        table.Add(3, "three");

        ReadOnlySpan<int> keys = table.Keys;
        Assert.Equal([1, 5, 3], keys);

        Span<string> values = table.Values;
        Assert.Equal(["one", "five", "three"], values);

        table.Clear();

        ref var refOne = ref table[1];
        refOne = "ONE";
        Assert.Equal("ONE", table[1]);

        ref var refTwo = ref table.AddOrRef(2, out var exist);
        if (!exist)
            refTwo = "TWO";
        Assert.Equal("TWO", table[2]);

        Assert.False(table.TryGetValue(3, out var three));
        Assert.Equal(default, three);

        table.Clear();
        table.Add(1, "one");
        table.Add(2, "two");
        table.Add(3, "three");
        table.Remove(2);

        Assert.Equal([1, 3], table.Keys);
        Assert.Equal(["one", "three"], table.Values);

        // 参照型は null を使用可能
        var table2 = new InlineTable<string, string>();
        table2.Add("one", "one");
        table2.Add(null!, null!);
        Assert.Equal(["one", null!], table2.Values);

        // null 許容値型は null を使用可能
        var table3 = new InlineTable<int?, int?>();
        table3.Add(1, 1);
        table3.Add(null, null);
        Assert.True(new int?[] { 1, null }.AsMemory().Span.SequenceEqual(table3.Values));
    }

    [Fact]
    void SizeOf()
    {
        Assert.Equal(504, Unsafe.SizeOf<InlineTable<string, string>>());
        Assert.Equal(392, Unsafe.SizeOf<InlineTable<string, bool>>());
        Assert.Equal(368, Unsafe.SizeOf<InlineTable<int, int>>());
        Assert.Equal(272, Unsafe.SizeOf<InlineTable<byte, byte>>());
        Assert.Equal(272, Unsafe.SizeOf<InlineTable<bool, bool>>());
    }

    [Fact]
    void Keys_Values_Count()
    {
        var dic = new InlineTable<int, string>();
        Assert.Equal(0, dic.Count);
        Assert.Equal([], dic.Keys);
        Assert.Equal([], dic.Values);

        dic.Add(1, "one");
        Assert.Equal(1, dic.Count);
        Assert.Equal([1], dic.Keys);
        Assert.Equal(["one"], dic.Values);

        dic.Add(2, "two");
        Assert.Equal(2, dic.Count);
        Assert.Equal([1, 2], dic.Keys);
        Assert.Equal(["one", "two"], dic.Values);
    }

    [Fact]
    void Indexer()
    {
        var dic = new InlineTable<int, string>();
        dic[1] = "one";
        Assert.Equal("one", dic[1]);

        dic[1] = "ONE";
        Assert.Equal("ONE", dic[1]);

        dic[2] = "two";
        Assert.Equal("two", dic[2]);

        dic[3] = "three";
        Assert.Equal("three", dic[3]);
    }

    [Fact]
    void Add_K_V()
    {
        Assert.Throws<InvalidOperationException>(() =>
        {
            var dic = new InlineTable<int, string>();
            dic.Add(1, "one");
            dic.Add(1, "one");
        });

        var dic = new InlineTable<int, string>();
        dic.Add(1, "one");
        Assert.Equal("one", dic[1]);

        dic.Add(2, "two");
        Assert.Equal("two", dic[2]);

        dic.Add(3, "three");
        Assert.Equal("three", dic[3]);
    }

    [Fact]
    void Add_K()
    {
        Assert.Throws<InvalidOperationException>(() =>
        {
            var dic = new InlineTable<int, string>();
            dic.Add(1) = "one";
            dic.Add(1) = "one";
        });

        var dic = new InlineTable<int, string>();
        dic.Add(1) = "one";
        Assert.Equal("one", dic[1]);

        dic.Add(2) = "two";
        Assert.Equal("two", dic[2]);

        dic.Add(3) = "three";
        Assert.Equal("three", dic[3]);
    }

    [Fact]
    void 容量が大きくなること()
    {
        var dic = new InlineTable<int, string>();
        var capacity = dic.Capacity;
        for (int n = 0; n < capacity + 1; ++n)
            dic.Add(n, n.ToString());

        Assert.True(dic.Capacity > capacity);
    }

    [Fact]
    void TryGetValue()
    {
        var dic = new InlineTable<int, string>();
        dic.Add(1, "one");

        Assert.True(dic.TryGetValue(1, out var one));
        Assert.Equal("one", one);

        Assert.False(dic.TryGetValue(2, out var two));
        Assert.Equal(default, two);
    }

    [Fact]
    void ContainsKey()
    {
        var dic = new InlineTable<int, string>();
        dic.Add(1, "one");

        Assert.True(dic.ContainsKey(1));
        Assert.False(dic.ContainsKey(2));
    }

    [Fact]
    void AddOrRef()
    {
        var dic = new InlineTable<int, string>();
        ref var one = ref dic.AddOrRef(1, out var exist);
        Assert.False(exist);
        one = "one";
        Assert.Equal("one", dic[1]);

        ref var one2 = ref dic.AddOrRef(1, out exist);
        Assert.True(exist);
        one2 = "ONE";
        Assert.Equal("ONE", dic[1]);
    }

    [Fact]
    void Clear()
    {
        var dic = new InlineTable<int, string>();
        dic.Add(1, "one");
        dic.Add(2, "two");
        dic.Add(3, "three");

        dic.Clear();
        Assert.Equal(0, dic.Count);
        Assert.Equal([], dic.Keys);
        Assert.Equal([], dic.Values);
    }

    [Fact]
    void Remove()
    {
        var dic = new InlineTable<int, string>();
        dic.Add(1, "one");
        dic.Add(2, "two");
        dic.Add(3, "three");

        Assert.True(dic.Remove(2));
        Assert.Equal([1, 3], dic.Keys);
        Assert.Equal(["one", "three"], dic.Values);

        Assert.False(dic.Remove(2));
        Assert.False(dic.Remove(4));
    }

    static (int key, int value)[] _testData;

    static _InlineTableTest()
    {
        // 固定乱数
        var rand = new Random(0);
        _testData = new (int, int)[1000];
        foreach (ref var n in _testData.AsSpan())
        {
            var num = rand.Next();
            n = (num, num * num);
        }
    }

    static void AddRandom10(Performance p)
    {
        p.AddTest("Dictionary", () =>
        {
            var dic = new Dictionary<int, int>();
            foreach (var (key, value) in _testData.AsSpan(0, 10))
                dic.Add(key, value);
        });

        p.AddTest("InlineTable", () =>
        {
            var table = new InlineTable<int, int>();
            foreach (var (key, value) in _testData.AsSpan(0, 10))
                table.Add(key, value);
        });
    }

    static void AddRandom100(Performance p)
    {
        p.AddTest("Dictionary", () =>
        {
            var dic = new Dictionary<int, int>();
            foreach (var (key, value) in _testData.AsSpan(0, 100))
                dic.Add(key, value);
        });

        p.AddTest("InlineTable", () =>
        {
            var table = new InlineTable<int, int>();
            foreach (var (key, value) in _testData.AsSpan(0, 100))
                table.Add(key, value);
        });
    }

    static void AddRandom1000(Performance p)
    {
        p.AddTest("Dictionary", () =>
        {
            var dic = new Dictionary<int, int>();
            foreach (var (key, value) in _testData.AsSpan(0, 1000))
                dic.Add(key, value);
        });

        p.AddTest("InlineTable", () =>
        {
            var table = new InlineTable<int, int>();
            foreach (var (key, value) in _testData.AsSpan(0, 1000))
                table.Add(key, value);
        });
    }

    static void RemoveRandom10(Performance p)
    {
        p.AddTest("Dictionary", () =>
        {
            var dic = new Dictionary<int, int>();
            foreach (var (key, value) in _testData.AsSpan(0, 10))
                dic.Add(key, value);
            foreach (var (key, _) in _testData.AsSpan(0, 10))
                dic.Remove(key);
        });

        p.AddTest("InlineTable", () =>
        {
            var table = new InlineTable<int, int>();
            foreach (var (key, value) in _testData.AsSpan(0, 10))
                table.Add(key, value);
            foreach (var (key, _) in _testData.AsSpan(0, 10))
                table.Remove(key);
        });
    }

    static void RemoveRandom100(Performance p)
    {
        p.AddTest("Dictionary", () =>
        {
            var dic = new Dictionary<int, int>();
            foreach (var (key, value) in _testData.AsSpan(0, 100))
                dic.Add(key, value);
            foreach (var (key, _) in _testData.AsSpan(0, 100))
                dic.Remove(key);
        });

        p.AddTest("InlineTable", () =>
        {
            var table = new InlineTable<int, int>();
            foreach (var (key, value) in _testData.AsSpan(0, 100))
                table.Add(key, value);
            foreach (var (key, _) in _testData.AsSpan(0, 100))
                table.Remove(key);
        });
    }

    static void RemoveRandom1000(Performance p)
    {
        p.AddTest("Dictionary", () =>
        {
            var dic = new Dictionary<int, int>();
            foreach (var (key, value) in _testData.AsSpan(0, 1000))
                dic.Add(key, value);
            foreach (var (key, _) in _testData.AsSpan(0, 1000))
                dic.Remove(key);
        });

        p.AddTest("InlineTable", () =>
        {
            var table = new InlineTable<int, int>();
            foreach (var (key, value) in _testData.AsSpan(0, 1000))
                table.Add(key, value);
            foreach (var (key, _) in _testData.AsSpan(0, 1000))
                table.Remove(key);
        });
    }

    static void ForeachValues(Performance p)
    {
        var dic = new Dictionary<int, int>(10000);
        for (int n = 0; n < 10000; ++n)
            dic.Add(n, n);
        p.AddTest("Dictionary", () =>
        {
            var sum = 0;
            foreach (var n in dic.Values)
                sum += n;
        });

        var table = new InlineTable<int, int>();
        for (int n = 0; n < 10000; ++n)
            table.Add(n, n);
        p.AddTest("InlineTable", () =>
        {
            var sum = 0;
            foreach (var n in table.Values)
                sum += n;
        });
    }
}
```

</details>

## 使い方

```cs
// 使い方
var table = new InlineTable<int, string>();
table.Add(1, "one");
table.Add(5, "five");
table.Add(3, "three");

ReadOnlySpan<int> keys = table.Keys;
Assert.Equal([1, 5, 3], keys);

Span<string> values = table.Values;
Assert.Equal(["one", "five", "three"], values);

table.Clear();

ref var refOne = ref table[1];
refOne = "ONE";
Assert.Equal("ONE", table[1]);

ref var refTwo = ref table.AddOrRef(2, out var exist);
if (!exist)
    refTwo = "TWO";
Assert.Equal("TWO", table[2]);

Assert.False(table.TryGetValue(3, out var three));
Assert.Equal(default, three);

table.Clear();
table.Add(1, "one");
table.Add(2, "two");
table.Add(3, "three");
table.Remove(2);

Assert.Equal([1, 3], table.Keys);
Assert.Equal(["one", "three"], table.Values);

// 参照型は null を使用可能
var table2 = new InlineTable<string, string>();
table2.Add("one", "one");
table2.Add(null!, null!);
Assert.Equal(["one", null!], table2.Values);

// null 許容値型は null を使用可能
var table3 = new InlineTable<int?, int?>();
table3.Add(1, 1);
table3.Add(null, null);
Assert.True(new int?[] { 1, null }.AsMemory().Span.SequenceEqual(table3.Values));
```

`Dictionary<TKey, TValue>` と異なる点

- キーに `null` を使用可能です
- 添字アクセス `[]` は **`ref` 参照**です
- 添字アクセス `[]` のとき要素が存在しない場合に例外にならず、デフォルト値が追加されます
  - 追加したくないときは `TryGetValue()` を使います

## パフォーマンス

|Test|Score|%|CG0|
|---|---:|---:|---:|
|AddRandom10 (2)||||
|Dictionary|378,447|100.0%|35|
|InlineTable|112,716|29.8%|0|
|AddRandom100 (2)||||
|Dictionary|56,227|100.0%|49|
|InlineTable|10,570|18.8%|7|
|AddRandom1000 (2)||||
|Dictionary|5,844|100.0%|51|
|InlineTable|1,147|19.6%|7|
|RemoveRandom10 (2)||||
|Dictionary|266,952|100.0%|24|
|InlineTable|30,019|11.2%|0|
|RemoveRandom100 (2)||||
|Dictionary|34,400|100.0%|30|
|InlineTable|622|1.8%|0|
|RemoveRandom1000 (2)||||
|Dictionary|4,726|100.0%|41|
|InlineTable|13|0.3%|0|
|ForeachValues (2)||||
|Dictionary|6,070|100.0%|0|
|InlineTable|14,626|241.0%|0|

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

- `InlineTable` は**全体的にパフォーマンスが悪い**です
- `Add()` で 20%、`Remove()` で **2%**程度です
- `Remove()` に関しては `Dictionary` が O(1) に対し、`InlineTable` は O(n) なので激遅です
- `foreach` 列挙に関してはパフォーマンスが良いです。これはメモリ連続のスパンをそのまま返しているためです

## 気になるところ

### バッファ長について

初期バッファ長をいくつにするかは悩ましい問題です。大きすぎるとスタックオーバーフローの危険だったり、使わないメモリの無駄が生じてしまったりします。一方で小さすぎても内部配列を作ることになり、ヒープ抑制の効果が小さそうです。

`Dictionary` の場合、初期バッファ長は 3 とかだったような気がします（厳密には最初は長さ 0 で、追加時に 3 に拡張）。この辺の仕様は最適化というか見直しが随時入るようで、フレームワークのバージョンによって変わる可能性があるようです。

辞書の場合、バッファ長はハッシュコードが衝突しにくいようにするため**素数**が良いとされます。

諸々を加味し、今回のバッファ長は **17** にしてみました。

- `InlineTable<string, string>` のサイズは 504 bytes（x64）
- 以前の検証で[スタックは 700KB くらい使えそう](https://qiita.com/abetakahiro123/items/d3a724dba68cb16ca722#%E3%82%B9%E3%82%BF%E3%83%83%E3%82%AF%E3%82%AA%E3%83%BC%E3%83%90%E3%83%BC%E3%83%95%E3%83%AD%E3%83%BC%E3%81%AB%E6%B3%A8%E6%84%8F)なので、普通に使う分には問題なさそうです

### `Remove()` の計算量は O(n)

`Dictionary` と明確に違う点です。これは `Keys` `Values` をメモリ連続、つまり**スパンとして扱えるようにする**ためにこうしました。スパンとして扱いたい需要は自分的には結構あるため、`Dictionary` との差別化ポイントです。

### nullable

キーに `null` を使用できるようにしました。`HashSet` のように `null` を使用したい場面もあるためです。

キーが `null` の場合は内部的にハッシュコードを 0 として扱っているのですが、何がベストなのかはよくわかりません。

- 0 だとなんかハッシュ衝突しそう、でも基本的に参照型であれば問題ない気もする
- [レコード型の場合フィールドのハッシュコードはうまくビットシフトしてずらしてくれる](https://qiita.com/abetakahiro123/items/3f3ca7f34ff7fbca52a3#%E6%B0%97%E3%81%AB%E3%81%AA%E3%82%8B%E3%81%A8%E3%81%93%E3%82%8D)ため、0 になることはあまりない
- 最小バッファ長の末尾に来るようにする？（今回の場合は最小バッファ長が 17 なので 16 とか）

### **null** 判定

`null` 判定には[前回の記事](https://qiita.com/abetakahiro123/items/636e1566d403958ebeb2#isnull-%E3%81%AE%E5%AE%9F%E8%A3%85)の知見を活かしています。↓ のコードは一見すると不可解ですが、JIT コンパイル時の最適化により非常に高速になります。

```cs
static bool IsNull<T>(T value) where T : allows ref struct
{
    if (typeof(T).IsValueType)
    {
        // null 許容構造体の場合は普通に null チェックする
        if (typeof(T).IsGenericType && typeof(T).GetGenericTypeDefinition() == typeof(Nullable<>))
        {
            return value is null;
        }
        return false;
    }
    return value is null;
}
```

つまるところ、前回の記事は今回のための布石だったというわけですね。

## おわりに

今回は概ね狙い通りの実装になりましたが、パフォーマンスがいまいち出ませんでした。  
言い換えれば標準ライブラリのパフォーマンスの良さを改めて実感したところです。

パフォーマンスの改善はそのうちやろうと思います。