はじめに
今回は、前回 InlineArray を使った値型リストを作ってみる の記事の辞書版です。
関連
たまに 要素数が少ない（10 とか）軽量な辞書 が欲しい場面があります。C# でよく使う Dictionary<TKey,TValue> は参照型なのでヒープが発生します。殆どの場合、両者にパフォーマンス的な違いはありませんが、ヒープを回避できるなら回避したいのがプログラマの性です。
.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);
サンプルコード
InlineTable.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;
}
}
テストコード
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;
});
}
}
使い方
// 使い方
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 くらい使えそうなので、普通に使う分には問題なさそうです
Remove() の計算量は O(n)
Dictionary と明確に違う点です。これは Keys Values をメモリ連続、つまりスパンとして扱えるようにするためにこうしました。スパンとして扱いたい需要は自分的には結構あるため、Dictionary との差別化ポイントです。
nullable
キーに null を使用できるようにしました。HashSet のように null を使用したい場面もあるためです。
キーが null の場合は内部的にハッシュコードを 0 として扱っているのですが、何がベストなのかはよくわかりません。
- 0 だとなんかハッシュ衝突しそう、でも基本的に参照型であれば問題ない気もする
- レコード型の場合フィールドのハッシュコードはうまくビットシフトしてずらしてくれるため、0 になることはあまりない
- 最小バッファ長の末尾に来るようにする？（今回の場合は最小バッファ長が 17 なので 16 とか）
null 判定
null 判定には前回の記事の知見を活かしています。↓ のコードは一見すると不可解ですが、JIT コンパイル時の最適化により非常に高速になります。
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;
}
つまるところ、前回の記事は今回のための布石だったというわけですね。
おわりに
今回は概ね狙い通りの実装になりましたが、パフォーマンスがいまいち出ませんでした。
言い換えれば標準ライブラリのパフォーマンスの良さを改めて実感したところです。
パフォーマンスの改善はそのうちやろうと思います。