ArrayByteIndexIsSlow

program.cs

using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Runtime.CompilerServices;
using System.Text;

namespace ConsoleApplication1
{
    unsafe class Program
    {
        static readonly byte[] Debruijn64 =
        {
        0, 0, 0, 7, 0, 4, 7, 5, 3, 0, 2, 4, 0, 7, 1, 5,
        7, 3, 2, 0, 2, 2, 4, 2, 6, 1, 7, 4, 3, 1, 6, 4,
        7, 6, 3, 5, 3, 2, 0, 1, 7, 2, 1, 2, 6, 4, 3, 4,
        6, 5, 3, 1, 7, 1, 6, 4, 5, 3, 1, 6, 5, 6, 5, 5,
        };
        const long DEBRUIJN_SEQ64 = 0x26752B916FC7B0D;


        static IEnumerable<int> DelegateToEnumerable(Func<byte[], byte, int, int, int> finder, byte[] input, byte toFind)
        {
            int ix = 0;
            while ((ix = finder(input, toFind, ix, input.Length - ix)) != -1)
            {
                yield return ix;
                ix++;
            }
        }
        static int Naive(byte[] array, byte value, int startIndex, int count)
        {
            if (array == null) throw new ArgumentNullException("array");
            if ((startIndex < 0) || (startIndex > array.Length))
            {
                throw new ArgumentOutOfRangeException("startIndex");
            }
            if ((count < 0) || (count > (array.Length - startIndex)))
            {
                throw new ArgumentOutOfRangeException("count");
            }
            for (int i = startIndex; count > 0; i++, count--)
            {
                if (array[i] == value) return i;
            }
            return -1;
        }
        static int Unsafe(byte[] array, byte value,int startIndex, int count)
        {
            if (array == null) throw new ArgumentNullException("array");
            if ((startIndex < 0) || (startIndex > array.Length))
            {
                throw new ArgumentOutOfRangeException("startIndex");
            }
            if ((count < 0) || (count > (array.Length - startIndex)))
            {
                throw new ArgumentOutOfRangeException("count");
            }
            fixed(byte* src = array)
            {
                byte* pbyte = src + startIndex;
                while(((int)pbyte&7) != 0)
                {
                    if (count == 0)
                    {
                        return -1;
                    }
                    else if (*pbyte == value)
                    {
                        return (int)(pbyte - src);
                    }
                    count--;
                    pbyte++;
                }
               
                for (ulong comparer = 0x0101010101010101ul * value; count > 7; count -= 8, pbyte += 8)
                {
                    unchecked {
                        ulong t1 = *(ulong*)pbyte;
                        t1 ^= comparer;
                        t1 = (t1 - 0x0101010101010101) & ~t1;
                        if ((t1= (t1 & 0x8080808080808080)) != 0)
                        {
                            int foundIx = (int)(pbyte - src);
                            return foundIx + DebruijnFindByte((long)t1);
                        }
                    }
                }
                for (; count > 0; --count, pbyte++)
                {
                    if (*pbyte == value)
                        return (int)(pbyte - src);
                }
            }
            return -1;
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        static int DebruijnFindByte(long v)
        {
            return Debruijn64[((ulong)((v & -v) * DEBRUIJN_SEQ64)) >> 58];
        }

        //static int IndexOf_SIMD(byte[] array, byte value, int startIndex, int count)
        //{
        //    if (array == null) throw new ArgumentNullException("array");
        //    if ((startIndex < 0) || (startIndex > array.Length))
        //    {
        //        throw new ArgumentOutOfRangeException("startIndex");
        //    }
        //    if ((count < 0) || (count > (array.Length - startIndex)))
        //    {
        //        throw new ArgumentOutOfRangeException("count");
        //    }
        //    Vector<byte> comparer = new Vector<byte>(value);
        //    for (; count >= Vector<Byte>.Count; startIndex += Vector<Byte>.Count, count -= Vector<Byte>.Count)
        //    {
        //        var vect = new Vector<byte>(array, startIndex);
        //        var res = Vector.Equals<byte>(vect, comparer);

        //        var vl = Vector.AsVectorInt64(res);
        //        long v;
        //        if ((v = vl[0]) != 0) { }
        //        else if ((v = vl[1]) != 0) startIndex += 8;
        //        else continue;
        //        return startIndex + DebruijnFindByte(v);
        //    }
        //    for (; count > 0; --count, startIndex++)
        //    {
        //        if (array[startIndex] == value)
        //        {
        //            return startIndex;
        //        }
        //    }
        //    return -1;
        //}

        static readonly Tuple<int, int, int>[] _tests = new[]{Tuple.Create(2,3000,3500)
    ,Tuple.Create(  2,01,10),Tuple.Create(  1,01,10),Tuple.Create(  4,01,10),Tuple.Create(  8,01,10)
    ,Tuple.Create( 64,01,10),Tuple.Create(128,01,10),Tuple.Create(256,01,10),Tuple.Create(512,01,10)
    ,Tuple.Create( 16,01,10),Tuple.Create(  1,10,20),Tuple.Create(  2,10,20),Tuple.Create(  4,10,20)
    ,Tuple.Create(  8,10,20),Tuple.Create( 16,10,20),Tuple.Create( 32,10,20),Tuple.Create( 64,10,20)
    ,Tuple.Create(128,10,20),Tuple.Create(256,10,20),Tuple.Create(480,10,20),Tuple.Create(  1,20,30)
    ,Tuple.Create(  2,20,30),Tuple.Create(  4,20,30),Tuple.Create(  8,20,30),Tuple.Create( 16,20,30)
    ,Tuple.Create( 32,20,30),Tuple.Create( 64,20,30),Tuple.Create(128,20,30),Tuple.Create(256,20,30)
    ,Tuple.Create(290,20,30),Tuple.Create(  1,30,40),Tuple.Create(  2,30,40),Tuple.Create(  4,30,40)
    ,Tuple.Create(  8,30,40),Tuple.Create( 16,30,40),Tuple.Create( 32,30,40),Tuple.Create( 64,30,40)
    ,Tuple.Create(128,30,40),Tuple.Create(210,30,40),Tuple.Create(  1,40,50),Tuple.Create(  2,40,50)
    ,Tuple.Create(  4,40,50),Tuple.Create(  8,40,50),Tuple.Create( 16,40,50),Tuple.Create( 32,40,50)
    ,Tuple.Create( 64,40,50),Tuple.Create(128,40,50),Tuple.Create(165,40,50),Tuple.Create( 32,01,10)
    ,Tuple.Create(  1,90,99),Tuple.Create(  2,90,99),Tuple.Create(  4,90,99),Tuple.Create(  8,90,99)
    ,Tuple.Create( 16,90,99),Tuple.Create( 32,90,99),Tuple.Create( 64,90,99),Tuple.Create( 80,90,99)
    ,Tuple.Create(4000, 01, 01),Tuple.Create(2000,01,05),Tuple.Create(1150,01,10),Tuple.Create(1,8000,8000),};
        static readonly Random rand = new Random();
        static readonly byte[] _bytes = initBytes();
        static readonly Dictionary<string, object>[] results = new Dictionary<string, object>[_tests.Length];
        static byte[] initBytes()
        {
            var ret = new byte[8000];
            var l = new ulong[] { 0x0102030405060708, 0x090A010203040506, 0x0708090A01020304, 0x05060708090A0102, 0x030405060708090A,
                              0x0102030405060708, 0x090A010203040506, 0x0708090A01020304, 0x05060708090A0102, 0x030405060708090A,
                              0x0102030405060708, 0x090A010203040506, 0x0708090A01020304, 0x05060708090A0102, 0x030405060708090A,
                              0x0102030405};
            Buffer.BlockCopy(l, 0, ret, 0, 125);
            for (int i = 0, j = 125; i < 6; i++, j *= 2)
                Buffer.BlockCopy(ret, 0, ret, j, j);
            return ret;
        }
        public static byte[] BuildRow(int numElems, int minwidth, int maxWidth)
        {

            var l = Enumerable.Range(0, numElems).Select(x => minwidth + rand.Next(1 + maxWidth - minwidth)).ToArray();
            var b = new byte[l.Sum() + numElems - 1];
            var ix = 0;
            Buffer.BlockCopy(_bytes, 0, b, ix, l[0]);
            ix = l[0];
            for (var i = 1; i < l.Length; i++)
            {
                var e = l[i];
                b[ix] = 0x44;
                Buffer.BlockCopy(_bytes, 0, b, ix + 1, e);
                ix += e + 1;
            }
            return b;
        }
        public static byte[][] BuildTable(Tuple<int, int, int> specification)
        {
            return Enumerable.Range(0, 1000).Select(_ => BuildRow(specification.Item1, specification.Item2, specification.Item3)).ToArray();
        }
        public static void RunTests()
        {
            var sw = new Stopwatch();
            long k = 0;
            for (var i = 0; i < _tests.Length; i++)
            {
                var data = BuildTable(_tests[i]);
                results[i] = new Dictionary<string, object>();
                //results[i["data"]=data;
                results[i]["_numElem"] = _tests[i].Item1;
                results[i]["_minwidth"] = _tests[i].Item2;
                results[i]["_maxWidth"] = _tests[i].Item3;
                Func<byte[], int> selector = b => b.Length;
                results[i]["_minLength"] = data.Min(selector);
                results[i]["_maxLength"] = data.Max(selector);
                results[i]["_avgLength"] = data.Average(selector);
                for (var j = 0; j < _candidates.Length; j++)
                {
                    GC.Collect();
                    GC.WaitForPendingFinalizers();
                    GC.Collect();
                    sw.Start();

                    foreach (var x in data)
                    {
                        for (var z = 0; z < 10; z++)
                            k += DelegateToEnumerable(_candidates[j], x, 0x44).Sum(r => (long)r);
                    }
                    sw.Stop();
                    results[i][_candidates[j].Method.DeclaringType.Name + "_" + _candidates[j].Method.Name] = sw.ElapsedMilliseconds;
                    sw.Reset();
                }

            }
            Console.WriteLine(k);
        }

        static string WriteTestResults()
        {
            var sb = new StringBuilder(8000);
            sb.AppendLine("_" + "," + string.Join<String>(",", results[0].Keys));
            for (var i = 0; i < results.Length; i++)
            {
                sb.AppendLine(i + "," + string.Join<object>(",", results[i].Values));
            }
            return sb.ToString();
        }
        //static readonly Func<byte[], byte, int, int> memchr=Memchr;
        //static readonly Func<byte[], byte, int, int> arrayIndexOf=Array.IndexOf<byte>;
        static readonly Func<byte[], byte, int, int, int>[] _candidates = {
        //IndexOf_SIMD,
        Array.IndexOf<byte>,
        Naive,
        Unsafe,
        Delegate.CreateDelegate(typeof(Func<byte[],byte,int,int,int>),EqualityComparer<Byte>.Default,
            EqualityComparer<Byte>.Default.GetType().GetMethod(
                "IndexOf",
                System.Reflection.BindingFlags.NonPublic | System.Reflection.BindingFlags.Instance)
            ) as Func<byte[],byte,int,int,int>};

        static void Main(string[] args)
        {
            var testRow = BuildRow(32, 90, 100);
            var test = DelegateToEnumerable(_candidates[1], testRow, 0x44).ToArray(); //as IStructuralEquatable;
           
            foreach (var key in _candidates)
            {
                var other = DelegateToEnumerable(key, testRow, 0x44).ToArray();
                Debug.WriteLine(string.Join(",",other.Zip(test, (a, b) => a + "-" + b)));
                if (!(test as IStructuralEquatable).Equals(other, StructuralComparisons.StructuralEqualityComparer))
                    throw new InvalidOperationException(key.Method.Name);
            }
            RunTests();
            for (var i = 0; i < _candidates.Length; i++)
            {
                var key = _candidates[i].Method.DeclaringType.Name + "_" + _candidates[i].Method.Name;
                Console.WriteLine(key);
                Console.WriteLine("Average:" + results.Average(x => Convert.ToInt64(x[key])).ToString("n"));
                Console.WriteLine("Total:" + results.Sum(x => Convert.ToInt64(x[key])).ToString("n"));
            }
            System.IO.File.WriteAllText("testresults.csv", WriteTestResults());
        }
    }
}