Optional<T>[] か、T[] + bit array か。

OptionalArray.cs

#define USE_BITARRAY64

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;
using System;
using System.Collections.Generic;
using System.Collections;

#if USE_BITARRAY64
using BitArray = BitArray64;
#else
using BitArray = System.Collections.BitArray;
#endif

/// <summary>
///  Method |     Mean |     Error |    StdDev |  Gen 0 | Allocated |
/// ------- |---------:|----------:|----------:|-------:|----------:|
///       A | 2.555 us | 0.0172 us | 0.0144 us | 0.2518 |    1072 B |
///       B | 2.605 us | 0.0126 us | 0.0118 us | 0.1602 |     688 B |
///
/// 思ったよりも <see cref="OptionalArray{T}"/> のペナルティなさそう？
/// ヒープ確保量は想定通り、ほぼ半減。
/// 
/// ちなみに、<see cref="BitArray64"/>をクラスに変更
///       B | 2.916 us | 0.0102 us | 0.0091 us | 0.1678 |     712 B |
///
/// <see cref="BitArray64"/>を<see cref="System.Collections.BitArray"/>に変更
///  Method |     Mean |     Error |    StdDev |  Gen 0 | Allocated |
///       B | 3.306 us | 0.0215 us | 0.0201 us | 0.1793 |     760 B |
/// ちょっとコスト高かなぁ…
///
/// それでも<see cref="OptionalArray{T}"/>のメリットは、配列の共変性をそのまま享受できる点。
/// <see cref="Optional{T}"/>の配列を作ると無理。
/// </summary>
class Program
{
    static void Main(string[] args)
    {
        BenchmarkRunner.Run<OptionalArrayBenchmark>();
    }
}

struct Optional<T>
{
    public bool HasValue { get; }
    private T _value;

    internal Optional(T value, bool hasValue)
    {
        _value = value;
        HasValue = hasValue;
    }
    public Optional(T value) : this(value, true) { }
    public static readonly Optional<T> None = default(Optional<T>);

    public T Value => HasValue ? _value : throw new NullReferenceException();
    public T GetValueOrDefault() => _value;
}

struct BitArray64
{
    long _bits;

    public bool this[int index]
    {
        get => (_bits & (1L << index)) != 0L;
        set
        {
            if (value) _bits |= (1L << index);
            else _bits &= ~(1L << index);
        }
    }
}

struct OptionalArray<T> : IReadOnlyList<Optional<T>>
{
    private T[] _array;
    private BitArray _hasValue;

    public OptionalArray(int length)
    {
        _array = new T[length];
#if USE_BITARRAY64
        _hasValue = new BitArray();
#else
        _hasValue = new BitArray(length);
#endif
    }

    public Optional<T> this[int index]
    {
        get => new Optional<T>(_array[index], _hasValue[index]);
        set
        {
            _array[index] = value.GetValueOrDefault();
            _hasValue[index] = value.HasValue;
        }
    }

    public int Length => _array.Length;
    int IReadOnlyCollection<Optional<T>>.Count => _array.Length;

    public OptionalArrayEnumerator GetEnumerator() => new OptionalArrayEnumerator(_array, _hasValue);
    IEnumerator<Optional<T>> IEnumerable<Optional<T>>.GetEnumerator() => GetEnumerator();
    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();

    public struct OptionalArrayEnumerator : IEnumerator<Optional<T>>
    {
        private T[] _array;
        private BitArray _hasValue;
        private int _index;

        public OptionalArrayEnumerator(T[] array, BitArray hasValue) : this()
        {
            _array = array;
            _hasValue = hasValue;
            _index = -1;
        }

        public Optional<T> Current => new Optional<T>(_array[_index], _hasValue[_index]);
        public bool MoveNext()
        {
            // 速度 >> 安全性 な実装
            _index++;
            return _index < _array.Length;
        }

        object IEnumerator.Current => Current;
        public void Dispose() { }
        public void Reset() => throw new NotImplementedException();
    }
}

[MemoryDiagnoser]
public class OptionalArrayBenchmark
{
    const int Seed = 12345678;
    const int Length = 48;

    [Benchmark]
    public double A()
    {
        var r = new Random();
        var array = new Optional<double>[Length];
        for (int i = 0; i < array.Length; i++)
        {
            array[i] = r.NextDouble() < 0.1 ? Optional<double>.None : new Optional<double>(r.NextDouble());
        }

        var sum = 0.0;

        for (int i = 0; i < array.Length; i++)
        {
            var x = array[i];
            if (x.HasValue) sum += x.GetValueOrDefault();
        }
        foreach (var x in array)
        {
            if (x.HasValue) sum += x.GetValueOrDefault();
        }
        return sum;
    }

    [Benchmark]
    public double B()
    {
        var r = new Random();
        var array = new OptionalArray<double>(Length);
        for (int i = 0; i < array.Length; i++)
        {
            array[i] = r.NextDouble() < 0.1 ? Optional<double>.None : new Optional<double>(r.NextDouble());
        }

        var sum = 0.0;

        for (int i = 0; i < array.Length; i++)
        {
            var x = array[i];
            if (x.HasValue) sum += x.GetValueOrDefault();
        }
        foreach (var x in array)
        {
            if (x.HasValue) sum += x.GetValueOrDefault();
        }
        return sum;
    }
}