【ツール】社内ShaderEditorの高速化をやってみた その2

/// <summary>
/// 最大サイズが固定された一意な値を先頭に追加する連結リストを表します.
/// </summary>
/// <remarks>
/// 基本的に削除はできず、先頭への追加(既に含まれる場合は先頭へ移動)のみが可能です.<br/>
/// 最初に確保したサイズ以上の要素を追加しようとした場合、例外が発生します.
/// </remarks>
/// <typeparam name="T">リストの要素の型.</typeparam>
public class FixedSizeRecentSet<T> : IEnumerable<T>
{
    private readonly int _maxSize;
    private readonly int[] _buckets;
    private readonly Entry[] _entries;
    private readonly ulong _fastModMultiplier;
    internal FixedSizeRecentSetNode<T>? _head;
    private int _count;
    private int _version;
 
 
    /// <summary>
    /// 最大サイズ.
    /// </summary>
    public int MaxSize => _maxSize;
 
    /// <summary>
    /// リスト内の要素の数.
    /// </summary>
    public int Count => _count;
 
    /// <summary>
    /// 先頭のノード.
    /// </summary>
    public FixedSizeRecentSetNode<T>? Head => _head;
 
    /// <summary>
    /// 末尾のノード.
    /// </summary>
    public FixedSizeRecentSetNode<T>? Tail => _head?._prev;
 
 
    /// <summary>
    /// 初期化します.
    /// </summary>
    /// <param name="maxSize">最大サイズ.</param>
    public FixedSizeRecentSet(int maxSize)
    {
        var size = HashHelper.GetPrime(maxSize);
        _maxSize = maxSize;
        _buckets = new int[size];
        _entries = new Entry[size];
        _fastModMultiplier = HashHelper.GetFastModMultiplier((uint)size);
    }
 
 
    /// <summary>
    /// 先頭に要素を追加します.
    /// </summary>
    /// <param name="item">追加する要素.</param>
    /// <returns>生成されたノードが返ります.</returns>
    public FixedSizeRecentSetNode<T> AddHead(T item)
    {
        var node = FindNode(item);
        if (node is null)
        {
            node = Allocate();
            node._list = this;
            node._item = item;
            TryEntryInsert(node);
        }
 
        if (_head is null)
        {
            InternalInsertNodeToEmptyList(node);
        }
        else
        {
            InternalRemoveNode(node);
            InternalInsertNodeBefore(_head, node);
            _head = node;
        }
 
        return node;
    }
 
 
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    private void InternalInsertNodeToEmptyList(FixedSizeRecentSetNode<T> node)
    {
        node._next = node;
        node._prev = node;
        _head = node;
        _version++;
    }
 
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    private void InternalInsertNodeBefore(FixedSizeRecentSetNode<T> point, FixedSizeRecentSetNode<T> node)
    {
        node._next = point;
        node._prev = point._prev;
        point._prev!._next = node;
        point._prev = node;
        _version++;
    }
 
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    private void InternalRemoveNode(FixedSizeRecentSetNode<T> node)
    {
        if (node._next is null &&
            node._prev is null)
            return;
 
        if (node._next == node)
        {
            _head = null;
        }
        else
        {
            node._next!._prev = node._prev;
            node._prev!._next = node._next;
            if (_head == node)
                _head = node._next;
        }
 
        node._next = null;
        node._prev = null;
        _version++;
    }
 
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    private ref int GetBucket(uint hashCode)
    {
        var buckets = _buckets;
        return ref buckets[HashHelper.FastMod(hashCode, (uint)buckets.Length, _fastModMultiplier)];
    }
 
    /// <summary>
    /// 指定したノードをエントリーに追加します.
    /// </summary>
    /// <param name="node">追加するノード.</param>
    /// <returns>エントリーへの登録が行われた場合は true、それ以外は false が返ります.</returns>
    private bool TryEntryInsert(FixedSizeRecentSetNode<T> node)
    {
        var entries = _entries;
        var c = EqualityComparer<T>.Default;
        var hashCode = (uint)c.GetHashCode(node._item!);
        var collisionCount = 0u;
        ref var bucket = ref GetBucket(hashCode);
        var i = bucket - 1;
 
        while ((uint)i < (uint)entries.Length)
        {
            if (entries[i].HashCode == hashCode && c.Equals(entries[i].Node!._item, node._item))
            {
                return false;
            }
 
            i = entries[i].Next;
 
            ++collisionCount;
            if (collisionCount > (uint)entries.Length)
            {
                return false;
            }
        }
 
        var index = _count;
        _count = index + 1;
        if ((uint)index == (uint)entries.Length)
        {
            return false;
        }
 
        ref var entry = ref entries[index];
        entry.HashCode = hashCode;
        entry.Next = bucket - 1;
        entry.Node = node;
        bucket = index + 1;
        return true;
    }
 
    /// <summary>
    /// ノードを生成します.
    /// </summary>
    /// <returns>生成したノードのインスタンスが返ります.</returns>
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    private FixedSizeRecentSetNode<T> Allocate()
    {
        if (_count == _maxSize)
            throw new InvalidOperationException("Cannot allocate more than the maximum size.");
 
        return new FixedSizeRecentSetNode<T>();
    }
 
    /// <summary>
    /// 指定した要素のノードを検索します.
    /// </summary>
    /// <param name="item">検索する要素.</param>
    /// <returns>要素のノードが見つかった場合はそのインスタンス、それ以外は null が返ります.</returns>
    private FixedSizeRecentSetNode<T>? FindNode(T item)
    {
        var entries = _entries;
        var c = EqualityComparer<T>.Default;
        var hashCode = (uint)c.GetHashCode(item!);
        ref var bucket = ref GetBucket(hashCode);
        var i = bucket - 1;
        var collisionCount = 0u;
        do
        {
            if ((uint)i >= (uint)entries.Length)
            {
                break;
            }
 
            ref var entry = ref entries[i];
            if (entry.HashCode == hashCode && c.Equals(entry.Node!._item, item))
            {
                return entry.Node;
            }
 
            i = entry.Next;
            ++collisionCount;
 
        } while (collisionCount <= (uint)entries.Length);
 
        return null;
    }
 
 
    /// <summary>
    /// コレクションを反復処理する列挙子を返します.
    /// </summary>
    /// <returns>コレクションの反復処理に使用できる列挙子が返ります.</returns>
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public IEnumerator<T> GetEnumerator()
    {
        return new Enumerator(this);
    }
 
    /// <summary>
    /// コレクションを反復処理する列挙子を返します.
    /// </summary>
    /// <returns>コレクションの反復処理に使用できる列挙子が返ります.</returns>
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
 
 
    private struct Entry
    {
        public int Next;
        public uint HashCode;
        public FixedSizeRecentSetNode<T>? Node;
    }
 
    internal struct Enumerator : IEnumerator<T>
    {
        private readonly FixedSizeRecentSet<T> _list;
        private readonly int _version;
        private FixedSizeRecentSetNode<T>? _node;
        private T? _current;
        private int _index;
 
 
        public T Current => _current!;
 
        object? IEnumerator.Current
        {
            [MethodImpl(MethodImplOptions.AggressiveInlining)]
            get
            {
                if (_index == 0 || _index == _list._count + 1)
                {
                    throw new InvalidOperationException("Enumeration has either not started or has already finished.");
                }
 
                return Current;
            }
        }
 
        internal Enumerator(FixedSizeRecentSet<T> list)
        {
            _list = list;
            _version = list._version;
            _node = list._head;
            _current = default;
            _index = 0;
        }
 
        public bool MoveNext()
        {
            if (_version != _list._version)
            {
                throw new InvalidOperationException("Collection was modified after the enumerator was instantiated.");
            }
 
            if (_node is null)
            {
                _index = _list._count + 1;
                return false;
            }
 
            ++_index;
            _current = _node._item;
            _node = _node._next;
            if (_node == _list._head)
            {
                _node = null;
            }
 
            return true;
        }
 
        public void Reset()
        {
            if (_version != _list._version)
            {
                throw new InvalidOperationException("Collection was modified after the enumerator was instantiated.");
            }
 
            _current = default;
            _node = _list._head;
            _index = 0;
        }
 
        public void Dispose()
        {
             
        }
    }
}

/// <summary>
/// 最大サイズが固定された一意な値を先頭に追加する連結リストのノードを表します.
/// </summary>
/// <typeparam name="T">リストの要素の型.</typeparam>
public sealed class FixedSizeRecentSetNode<T>
{
    internal T? _item;
    internal FixedSizeRecentSetNode<T>? _next;
    internal FixedSizeRecentSetNode<T>? _prev;
    internal FixedSizeRecentSet<T>? _list;
 
 
    /// <summary>
    /// このノードの要素.
    /// </summary>
    public T? Value
    {
        get => _item;
        set => _item = value;
    }
 
    /// <summary>
    /// 次のノード.
    /// </summary>
    public FixedSizeRecentSetNode<T>? Next => _next is null || _next == _list!._head ? null : _next;
 
    /// <summary>
    /// 前のノード.
    /// </summary>
    public FixedSizeRecentSetNode<T>? Previous => _prev is null || this == _list!._head ? null : _prev;
 
    /// <summary>
    /// 属するリスト.
    /// </summary>
    public FixedSizeRecentSet<T> List => _list!;
}

/// <summary>
/// ハッシュに関するヘルパークラスを提供します.
/// </summary>
public static class HashHelper
{
    internal const int HashPrime = 101;
  
    internal static ReadOnlySpan<int> Primes =>
    [
        3, 7, 11, 17, 23, 29, 37, 47, 59, 71, 89, 107, 131, 163, 197, 239, 293, 353, 431, 521, 631, 761, 919,
        1103, 1327, 1597, 1931, 2333, 2801, 3371, 4049, 4861, 5839, 7013, 8419, 10103, 12143, 14591,
        17519, 21023, 25229, 30293, 36353, 43627, 52361, 62851, 75431, 90523, 108631, 130363, 156437,
        187751, 225307, 270371, 324449, 389357, 467237, 560689, 672827, 807403, 968897, 1162687, 1395263,
        1674319, 2009191, 2411033, 2893249, 3471899, 4166287, 4999559, 5999471, 7199369
    ];
 
 
    /// <summary>
    /// 指定した値が素数かどうかを判定します.
    /// </summary>
    /// <param name="candidate">候補となる値.</param>
    /// <returns>素数である場合は true、そうでない場合は false が返ります.</returns>
    public static bool IsPrime(int candidate)
    {
        if ((candidate & 1) == 0)
            return candidate == 2;
 
        var limit = (int)Math.Sqrt(candidate);
        for (var divisor = 3; divisor <= limit; divisor += 2)
        {
            if ((candidate % divisor) == 0)
                return false;
        }
        return true;
    }
 
    /// <summary>
    /// 指定した値以上の最小の素数を返します.
    /// </summary>
    /// <param name="min">最小の値.</param>
    /// <returns>最小の素数が返ります.</returns>
    public static int GetPrime(int min)
    {
        if (min < 0)
            throw new ArgumentException("Hashtable's capacity overflowed and went negative. Check load factor, capacity and the current size of the table.");
  
        foreach (ref readonly var prime in Primes)
        {
            if (prime >= min)
                return prime;
        }
  
        for (var i = (min | 1); i < int.MaxValue; i += 2)
        {
            if (IsPrime(i) && ((i - 1) % HashPrime != 0))
                return i;
        }
        return min;
    }
 
    /// <summary>
    /// 除数の近似逆数を返します: ceil(2**64 / 除数).
    /// </summary>
    /// <param name="divisor">除数.</param>
    /// <returns>除数の近似逆数が返ります.</returns>
    public static ulong GetFastModMultiplier(uint divisor) => ulong.MaxValue / divisor + 1;
 
    /// <summary>
    /// <see cref="GetFastModMultiplier"/> で事前に計算された乗数を使用して mod 演算を実行します.
    /// </summary>
    /// <param name="value">値.</param>
    /// <param name="divisor">除数.</param>
    /// <param name="multiplier">除数の近似逆数.</param>
    /// <returns>mod 演算の結果が返ります.</returns>
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static uint FastMod(uint value, uint divisor, ulong multiplier)
    {
        Debug.Assert(divisor <= int.MaxValue);
  
        var highBits = (uint)(((((multiplier * value) >> 32) + 1) * divisor) >> 32);
  
        Debug.Assert(highBits == value % divisor);
        return highBits;
    }
}

Fuzz.PartialRatio