ListStructVsListBenchmark.cs

using System;
using System.Buffers;
using System.Collections.Generic;
using System.Linq;
using System.Runtime.CompilerServices;
using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Jobs;

namespace Benchmarks.CollectionBenchmarks;

[SimpleJob(RuntimeMoniker.Net80)]
[MeanColumn, MemoryDiagnoser]
public class ListStructVsListBenchmark
{
    [Params(5)] public int Length { get; set; }

    [Benchmark(Baseline = true)]
    public int JustList()
    {
        var list = new List<int>(Length);
        foreach (var value in _values)
        {
            list.Add(value);
        }

        return list.IndexOf(_lastValue);
    }

    [Benchmark]
    public int OldListStruct()
    {
        var list = new ListStruct<int>(Length);
        foreach (var value in _values)
        {
            list.Add(value);
        }

        return list.IndexOf(_lastValue);
    }

    [Benchmark]
    public int InlineArrayStruct()
    {
        var list = new ListInlineArray5<int>();
        for (var i = 0; i < _values.Length; i++)
        {
            list[i] = _values[i];
        }

        return list.IndexOf(_lastValue);
    }

    [Benchmark]
    public int MixListStructWithInlineArray()
    {
        var list = new ListStructMix<int>(Length);
        foreach (var value in _values)
        {
            list.Add(value);
        }

        return list.IndexOf(_lastValue);
    }

    private int _lastValue;
    private int[] _values = null!;

    [GlobalSetup]
    public void Config()
    {
        var random = Random.Shared;

        _values = Enumerable
            .Range(0, Length)
            .Select(_ => random.Next(0, 512))
            .ToArray();
        _lastValue = _values.Last();
    }
}

public struct ListStruct<T> where T : struct, IEquatable<T>
{
    private const int FieldCount = 5;

    public readonly int Length
    {
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        get => _length;
    }

    private int _length;

    private T _element0;
    private T _element1;
    private T _element2;
    private T _element3;
    private T _element4;

    private T[]? _array;

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public ListStruct(int capacity)
    {
        _array = null;
        _length = 0;
        _array = capacity > FieldCount
            ? ArrayPool<T>.Shared.Rent(capacity - FieldCount)
            : null;
    }

    // ReSharper disable once CognitiveComplexity
    public void Add(T value)
    {
        switch (_length)
        {
            case 0:
                _element0 = value;
                break;
            case 1:
                _element1 = value;
                break;
            case 2:
                _element2 = value;
                break;
            case 3:
                _element3 = value;
                break;
            case 4:
                _element4 = value;
                break;
            case FieldCount:
                _array ??= ArrayPool<T>.Shared.Rent(4);
                _array[0] = value;
                break;
            default:
                Insert(ref _array!, _length - FieldCount, in value);
                break;
        }

        _length++;
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public readonly T Get(int index) => index switch
    {
        0 => _element0,
        1 => _element1,
        2 => _element2,
        3 => _element3,
        4 => _element4,
        _ => _array![index - FieldCount]
    };

    public readonly int IndexOf(T value)
    {
        for (var i = 0; i < _length; i++)
        {
            if (Get(i).Equals(value)) return i;
        }

        return -1;
    }

    [MethodImpl(MethodImplOptions.NoInlining)]
    private static void Insert(ref T[] array, int index, in T element)
    {
        var arrayLength = array.Length;
        if (index < arrayLength) array[index] = element;
        else
        {
            var arrayPool = ArrayPool<T>.Shared;

            var newLength = arrayLength == 0 ? 2 : arrayLength * 2;
            var newArray = arrayPool.Rent(newLength);

            Array.Copy(array, newArray, arrayLength);
            arrayPool.Return(array);

            array = newArray;
            array[index] = element;
        }
    }
}

public struct ListStructMix<T>
    where T : struct, IEquatable<T>
{
    private const int FieldCount = 5;

    private ListInlineArray5<T> _inlineArray;
    private T[]? _array;
    private int _length;

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public ListStructMix(int capacity)
    {
        _array = null;
        _length = 0;
        _array = capacity > FieldCount
            ? ArrayPool<T>.Shared.Rent(capacity - FieldCount)
            : null;
    }

    public void Add(T value)
    {
        if (_length < FieldCount) _inlineArray[_length] = value;
        else Insert(ref _array, _length - FieldCount, in value);

        _length++;
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public readonly T Get(int index) => index < FieldCount
        ? _inlineArray[index]
        : _array![index - FieldCount];

    public readonly int IndexOf(T value)
    {
        for (var i = 0; i < _length; i++)
        {
            if (Get(i).Equals(value)) return i;
        }

        return -1;
    }

    [MethodImpl(MethodImplOptions.NoInlining)]
    private static void Insert(ref T[]? array, int index, in T element)
    {
        var arrayPool = ArrayPool<T>.Shared;
        array ??= arrayPool.Rent(2);

        var arrayLength = array.Length;
        if (index < arrayLength) array[index] = element;
        else
        {
            var newLength = arrayLength * 2;
            var newArray = arrayPool.Rent(newLength);

            Array.Copy(array, newArray, arrayLength);
            arrayPool.Return(array);

            array = newArray;
            array[index] = element;
        }
    }
}

[InlineArray(5)]
public struct ListInlineArray5<T>
    where T : struct, IEquatable<T>
{
    private T _element0;

    public int IndexOf(T value)
    {
        for (var i = 0; i < 6; i++)
        {
            if (this[i].Equals(value)) return i;
        }

        return -1;
    }
}