An immutable array class that uses multi-levels of arrays to speed up copying

Benchmarks.cs

// Benchmarks
using BenchmarkDotNet.Attributes;
using LanguageExt;
using System.Collections.Immutable;

namespace MyImmutableArray;

[MemoryDiagnoser]
public class Benchmarks
{
	private const int Iterations = 100_000;

	[Benchmark]
	public void ImmutableArray_Add()
	{
		var x = ImmutableArray.Create<int>();
		for (int i = 0; i < Iterations; i++)
			x = x.Add(i);
		if (x.Length != Iterations)
			throw new InvalidOperationException();
	}

	[Benchmark]
	public void List_Add()
	{
		var x = new List<int>();
		for (int i = 0; i < Iterations; i++)
			x.Add(i);
		if (x.Count != Iterations)
			throw new InvalidOperationException();
	}

	[Benchmark]
	public void ImmutableBlockArray_Add()
	{
		var x = ImmutableBlockArray<int>.Empty;
		for (int i = 0; i < Iterations; i++)
			x = x.Add(i);
		if (x.Length != Iterations)
			throw new InvalidOperationException();
	}

	[Benchmark]
	public void LanguageExtLst_Add()
	{
		var x = new Lst<int>();
		for (int i = 0; i < Iterations; i++)
			x = x.Add(i);
		if (x.Count != Iterations)
			throw new InvalidOperationException();
	}
}

ImmutableBlockArray.cs

using System.Collections;

namespace MyImmutableArray;

public abstract class ImmutableBlockArray<T> : IEnumerable<T>
{
	public static readonly ImmutableBlockArray<T> Empty = new ImmutableBlockArrayBranch<T>(0);

	public abstract ImmutableBlockArray<T> Add(T value);
	public abstract IEnumerator<T> GetEnumerator();
	public abstract int Length { get; }
	
	internal abstract bool IsFull { get; }
	protected const int NumberOfSlots = 10;

#if DEBUG
	public string BuildDebugString()
	{
		var builder = new System.Text.StringBuilder();
		BuildDebugString(0, builder);
		return builder.ToString();
	}

	internal abstract void BuildDebugString(int indentLevel, System.Text.StringBuilder builder);
#endif

	IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
}

ImmutableBlockArrayBranch.cs

using System.Runtime.CompilerServices;

namespace MyImmutableArray;

internal sealed class ImmutableBlockArrayBranch<T> : ImmutableBlockArray<T>
{
	public override int Length => _length;

	internal override bool IsFull => _isFull;

	private bool _isFull;
	private readonly int _length;
	private readonly int SlotIndex = 0;
	private readonly int Depth = 0;
	private readonly ImmutableBlockArray<T>[] Slots = new ImmutableBlockArray<T>[NumberOfSlots];
	
	private bool CheckIsFull() => Slots[NumberOfSlots - 1]?.IsFull == true;

	internal ImmutableBlockArrayBranch(int depth)
	{
		Depth = depth;
	}

	private ImmutableBlockArrayBranch(ImmutableBlockArrayBranch<T> source)
	{
		Slots[0] = source;
		SlotIndex = 1;
		Depth = source.Depth + 1;
		_length = source.Length;
	}

	internal ImmutableBlockArrayBranch(ImmutableBlockArrayLeaf<T> source, T value)
	{
		Slots[0] = source;
		SlotIndex = 1;
		Slots[1] = Empty.Add(value);
		_length = source.Length + 1;
		_isFull = CheckIsFull();
	}

	private ImmutableBlockArrayBranch(ImmutableBlockArrayBranch<T> source, T value)
	{
		SlotIndex = source.SlotIndex;
		Depth = source.Depth;
		Array.Copy(source.Slots, Slots, SlotIndex + 1);

		if (Slots[SlotIndex] is null)
			Slots[SlotIndex] = CreateChild(Depth);

		if (Slots[SlotIndex].IsFull)
		{
			SlotIndex++;
			Slots[SlotIndex] = CreateChild(Depth);
		}
		Slots[SlotIndex] = Slots[SlotIndex].Add(value);
		_length = source.Length + 1;
		_isFull = CheckIsFull();
	}

	public override ImmutableBlockArray<T> Add(T value)
	{
		if (!IsFull)
			return new ImmutableBlockArrayBranch<T>(this, value);
		return new ImmutableBlockArrayBranch<T>(this).Add(value);
	}

	public override IEnumerator<T> GetEnumerator()
	{
		for (int o = 0; o <= Math.Min(SlotIndex, NumberOfSlots - 1); o++)
		{
			ImmutableBlockArray<T>? slot = Slots[o];
			if (slot is not null)
			{
				foreach (T value in slot)
					yield return value;
			}
		}
	}

	[MethodImpl(MethodImplOptions.AggressiveInlining)]
	private static ImmutableBlockArray<T> CreateChild(int depth) =>
		depth == 0
		? ImmutableBlockArrayLeaf<T>.LeafEmpty
		: new ImmutableBlockArrayBranch<T>(depth - 1);

#if DEBUG
	internal override void BuildDebugString(int indentLevel, System.Text.StringBuilder builder)
	{
		builder.AppendLine($"{new string('=', indentLevel)}(Length {Length})");
		foreach (var slot in Slots)
			if (slot is not null)
				slot.BuildDebugString(indentLevel + 1, builder);
	}
#endif
}

ImmutableBlockArrayLeaf.cs

namespace MyImmutableArray;

internal sealed class ImmutableBlockArrayLeaf<T> : ImmutableBlockArray<T>
{
	public static readonly ImmutableBlockArrayLeaf<T> LeafEmpty = new();
	public override int Length => _length;

	internal override bool IsFull => _isFull;

	private bool _isFull;
	private int SlotIndex = 0;
	private readonly int _length = 0;
	private readonly T[] Slots = new T[NumberOfSlots];

	internal ImmutableBlockArrayLeaf()
	{
	}

	private ImmutableBlockArrayLeaf(ImmutableBlockArrayLeaf<T> source, T value)
	{
		Array.Copy(source.Slots, Slots, source.SlotIndex);
		Slots[source.SlotIndex] = value;
		SlotIndex = source.SlotIndex + 1;
		_length = source.Length + 1;
		_isFull = SlotIndex == NumberOfSlots;
	}


	public override ImmutableBlockArray<T> Add(T value)
	{
		if (IsFull)
			throw new InvalidOperationException();
		return new ImmutableBlockArrayLeaf<T>(this, value);
	}

	public override IEnumerator<T> GetEnumerator()
	{
		for(int o = 0; o <= Math.Min(SlotIndex - 1, NumberOfSlots - 1); o++)
			yield return Slots[o];
	}

#if DEBUG
	internal override void BuildDebugString(int indentLevel, System.Text.StringBuilder builder)
	{
		string indent = new('.', indentLevel);
		for(int o = 0; o <= Math.Min(SlotIndex - 1, NumberOfSlots - 1); o++)
			builder.AppendLine($"{indent}{Slots[o]}");
	}
#endif
}

Program.cs

using BenchmarkDotNet.Running;
using MyImmutableArray;

BenchmarkRunner.Run<Benchmarks>();