FindBytesBench

using System.Numerics;
using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;

namespace FindBytesBench;

public class Program
{
    private const int ArraySize = 1_000_000;
    private const byte TargetValue = 0x55;

    private static readonly byte[] bytes = new byte[ArraySize];

    [Benchmark]
    public List<int> SequentialTest()
    {
        var result = new List<int>();
        for (var i = 0; i < ArraySize; i++)
        {
            if (bytes[i] == TargetValue) result.Add(i);
        }
        return result;
    }

    [Benchmark]
    public List<int> LINQTest()
        => bytes
            .Select((b, i) => (b, i))
            .Where(t => t.b == TargetValue)
            .Select(t => t.i)
            .ToList();

    [Benchmark]
    public List<int> VectorTest()
    {
        var result = new List<int>();
        var vectorSize = Vector<byte>.Count;
        var targetVector = new Vector<byte>(TargetValue);
        var i = 0;
        for (; i <= ArraySize - vectorSize; i += vectorSize)
        {
            var chunk = new Vector<byte>(bytes, i);
            var comparison = Vector.Equals(targetVector, chunk);
            if (comparison != Vector<byte>.Zero)
            {
                for (var j = 0; j < vectorSize; j++)
                {
                    if (comparison[j] != 0) result.Add(i + j);
                }
            }
        }
        for (; i < ArraySize; i++)
        {
            if (bytes[i] == TargetValue) result.Add(i);
        }
        return result;
    }

    [Benchmark]
    public List<int> ParallelTest()
    {
        var vectorSize = Vector<byte>.Count;
        var targetVector = new Vector<byte>(TargetValue);
        var partitionCount = ArraySize / vectorSize;
        var results = new List<int>();
        Parallel.For(0, partitionCount, () => new List<int>(), (i, _, localList) =>
        {
            var start = i * vectorSize;
            var chunk = new Vector<byte>(new ReadOnlySpan<byte>(bytes, start, vectorSize));
            var comparison = Vector.Equals(targetVector, chunk);
            if (comparison != Vector<byte>.Zero)
            {
                for (var j = 0; j < vectorSize; j++)
                {
                    if (comparison[j] != 0) localList.Add(start + j);
                }
            }
            return localList;
        }, localList =>
        {
            lock (results)
            {
                results.AddRange(localList);
            }
        });
        for (var i = partitionCount * vectorSize; i < ArraySize; i++)
        {
            if (bytes[i] == TargetValue) results.Add(i);
        }
        return results;
    }

    [Benchmark]
    public List<int> IndexOfTest()
    {
        var result = new List<int>();
        var i = -1;
        while (true)
        {
            i = Array.IndexOf(bytes, TargetValue, i + 1);
            if (i is -1) break;
            result.Add(i);
        }
        return result;
    }

    [Benchmark]
    public List<int> SpanTest()
    {
        var result = new List<int>();
        var i = 0;
        while (bytes.AsSpan(i).IndexOf(TargetValue) is var di and >= 0)
        {
            result.Add(i + di);
            i += di + 1;
        }
        return result;
    }

    static void Main()
    {
        for (var i = 0; i < ArraySize - 1; i++) bytes[i] = (byte)i;
        bytes[ArraySize - 1] = TargetValue;
        Validate();
        _ = BenchmarkRunner.Run<Program>();

        static void Validate()
        {
            var program = new Program();
            var sequentialResult = program.SequentialTest();
            var linqResult = program.LINQTest();
            var vectorResult = program.VectorTest();
            var parallelResult = program.ParallelTest();
            var indexOfResult = program.IndexOfTest();
            var spanResult = program.SpanTest();
            CompareResults(sequentialResult, linqResult, vectorResult, parallelResult, indexOfResult, spanResult);

            static void CompareResults(params List<int>[] lists)
            {
                if (lists.Length is 0) return;
                var a = lists[0];
                if (a.Count is 0) throw new Exception();
                var aSet = new HashSet<int>(a);
                if (a.Count != aSet.Count) throw new Exception();
                for (var i = 1; i < lists.Length; i++)
                {
                    var b = lists[i];
                    if (a.Count != b.Count) throw new Exception();
                    var bSet = new HashSet<int>(b);
                    if (!aSet.SetEquals(bSet)) throw new Exception();
                }
            }
        }
    }
}