Redux test

DeBruijnBenchmark.cs

using BenchmarkDotNet.Attributes;
using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using System.Runtime.CompilerServices;
using System.Text;
using System.Threading;
using System.Threading.Tasks;
using BenchmarkDotNet.Configs;
using BenchmarkDotNet.Jobs;
using BenchmarkDotNet.Running;
using Xunit;
using System.Diagnostics;

namespace DeBruijnBenchmark
{
    public class Program
    {
        public static void Main()
        {
            if (System.Diagnostics.Debugger.IsAttached)
            {
                Debugger.Break();
                Console.WriteLine(FirstByteBenchmark.FindFirstByteMagic(ref FirstByteBenchmark._vectors[3]));
                Debugger.Break();
            }
            Console.WriteLine(Vector.IsHardwareAccelerated);
            if (!Vector.IsHardwareAccelerated) throw new ArgumentException();
            Console.WriteLine(FirstByteBenchmark._vectors[0]);
            BenchmarkRunner.Run<FirstByteBenchmark>();
        }
    }
    public class Config : ManualConfig
    {
        public Config()
        {
            // gets too slow otherwise
            Add(Job.Default
                    .WithLaunchCount(1) // benchmark process will be launched only once
                    .WithIterationTime(200) // 200ms per iteration
                    .WithWarmupCount(10) // 10 warmup iteration
                    .WithTargetCount(10) // 10 target iteration
            );
        }
    }

    [Config(typeof(Config))]
    public class FirstByteBenchmark
    {
        private static readonly int _vectorSpan = Vector<byte>.Count;
        private static readonly int _vectorUlongSpan = Vector<ulong>.Count;
        private static readonly int _bytesPerLong = _vectorSpan / _vectorUlongSpan;
        private static readonly bool _isLittleEndian = BitConverter.IsLittleEndian;
        private static bool jitted = JitConstants();
        const ulong Magic = 0x01020304050607ul;
        const ulong Magic2 = 0x01020304050608ul;

        private static bool JitConstants()
        {
            var x = _vectorUlongSpan + _vectorSpan + _bytesPerLong;
            if (x == 0) throw new ArgumentException();
            return true;
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        internal static int FindByteAndNegateMagic(long v)
        {
            ulong u = (ulong)(v & -v);
            return (int)(u * Magic >> 56);
        }


        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        internal static int FindByteXorMagic(ulong u)
        {
            u ^= u - 1;
            return (int)(u * Magic2 >> 57);
        }


        private static void ThrowInvalidOperationException()
        {
            throw new InvalidOperationException();
        }


        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        internal static int FindFirstByteNaive(byte[] bytes)
        {
            for (int i = 0; i < bytes.Length; i++)
            {
                if (bytes[i] != 0) return i;
            }
            return -1;
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private static int FindByteQuasiTree(long longValue)
        {
            return ((longValue & 0x00000000ffffffff) > 0
                           ? (longValue & 0x000000000000ffff) > 0
                               ? (longValue & 0x00000000000000ff) > 0 ? 0 : 1
                               : (longValue & 0x0000000000ff0000) > 0 ? 2 : 3
                           : (longValue & 0x0000ffff00000000) > 0
                               ? (longValue & 0x000000ff00000000) > 0 ? 4 : 5
                               : (longValue & 0x00ff000000000000) > 0 ? 6 : 7);
        }

        public static readonly Vector<byte>[] _vectors = InitVectors();

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static int FindFirstByteOld(ref Vector<byte> b)
        {
            var vector64 = Vector.AsVectorInt64(b);
            int i = 0;
            long l = 0;
            if ((l = vector64[0]) == 0)
            {
                i = 1;
                if ((l = vector64[1]) == 0)
                {
                    i = 2;
                    if (_vectorUlongSpan < 4 || (l = vector64[2]) == 0)
                    {
                        i = 3;
                        l = vector64[3];
                    }
                }
            }
            var ix = (l & 0x00000000ffffffff) > 0
           ? (l & 0x000000000000ffff) > 0
               ? (l & 0x00000000000000ff) > 0 ? 0 : 1
               : (l & 0x0000000000ff0000) > 0 ? 2 : 3
           : (l & 0x0000ffff00000000) > 0
               ? (l & 0x000000ff00000000) > 0 ? 4 : 5
               : (l & 0x00ff000000000000) > 0 ? 6 : 7;
            return i * 8 + ix;
        }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static int FindFirstByteMagic(ref Vector<byte> b)
        {
            var vector64 = Vector.AsVectorInt64(b);
            int i = 0;
            long l = 0;
            if ((l = vector64[0]) == 0)
            {
                i = 1;
                if ((l = vector64[1]) == 0)
                {
                    i = 2;
                    if (_vectorUlongSpan < 4 || (l = vector64[2]) == 0)
                    {
                        i = 3;
                        l = vector64[3];
                    }
                }
            }
            ulong u = (ulong)(l & -l);
            var ix = (int)(u * Magic >> 56);
            return i * 8 + ix;
        }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static int FindFirstByteXorMagic(ref Vector<byte> b)
        {
            var vector64 = Vector.AsVectorUInt64(b);
            int i = 0;
            ulong u = 0;
            if ((u = vector64[0]) == 0)
            {
                i = 1;
                if ((u = vector64[1]) == 0)
                {
                    i = 2;
                    if (_vectorUlongSpan < 4 || (u = vector64[2]) == 0)
                    {
                        i = 3;
                        u = vector64[3];
                    }
                }
            }

            u ^= u - 1;
            var ix = (int)(u * Magic2 >> 57);
            return i * 8 + ix;
        }
        //static byte[][] InitVectors()
        //{
        //    int vbCount = Vector<byte>.Count;
        //    var vectors = new byte[vbCount][];
        //    for (int i = 0; i < vectors.Length; i++)
        //    {
        //        byte[] vectorData = new byte[vbCount];
        //        vectorData[i] = 1;
        //        vectors[i] = vectorData;
        //    }
        //    return vectors;
        //}


        static Vector<byte>[] InitVectors()
        {
            int vbCount = Vector<byte>.Count;
            var vectors = new Vector<byte>[vbCount];
            for (int i = 0; i < vectors.Length; i++)
            {
                byte[] vectorData = new byte[vbCount];
                vectorData[i] = 255;
                vectors[i] = new Vector<byte>(vectorData);
            }
            return vectors;
        }




        [Params(27, 19, 11, 3)]
        public int ByteSet { get; set; }


        [Benchmark]
        public int FirstByteVector()
        {
            var vector = _vectors[ByteSet];
            return FindFirstByteOld(ref vector);
        }


        [Benchmark]
        public int FirstByteXorMagic()
        {
            var vector = _vectors[ByteSet];
            return FindFirstByteXorMagic(ref vector);
        }

        [Benchmark]
        public int FirstByteMagic()
        {
            var vector = _vectors[ByteSet];
            return FindFirstByteMagic(ref vector);
        }

        [Theory]
        [InlineData(0)]
        [InlineData(1)]
        [InlineData(2)]
        [InlineData(3)]
        [InlineData(4)]
        [InlineData(5)]
        [InlineData(6)]
        [InlineData(7)]
        [InlineData(8)]
        [InlineData(9)]
        [InlineData(10)]
        [InlineData(11)]
        [InlineData(12)]
        [InlineData(13)]
        [InlineData(14)]
        [InlineData(15)]
        public void AssertFirstByte(int b)
        {
            var bytes = new byte[Vector<byte>.Count];

            var vvalue = _vectors[b];
            vvalue.CopyTo(bytes);
            int dbPos = FindFirstByteOld(ref vvalue);
            int vPos = FindFirstByteOld(ref vvalue);
            int dbxPos = FindFirstByteXorMagic(ref vvalue);
            int pos = FindFirstByteNaive(bytes);
            Assert.Equal(b, dbPos);
            Assert.Equal(b, vPos);
            Assert.Equal(b, dbxPos);
            Assert.Equal(b, pos);
        }
    }
}

Results of latest version 10-6-2016:
Host Process Environment Information:

BenchmarkDotNet.Core=v0.9.9.0
OS=Microsoft Windows NT 6.2.9200.0
Processor=Intel(R) Core(TM) i5-5300U CPU 2.30GHz, ProcessorCount=4
Frequency=2240905 ticks, Resolution=446.2483 ns, Timer=TSC
CLR=MS.NET 4.0.30319.42000, Arch=64-bit RELEASE [RyuJIT]
GC=Concurrent Workstation
JitModules=clrjit-v4.6.1586.0

Type=FirstByteBenchmark  Mode=Throughput  LaunchCount=1
WarmupCount=10  TargetCount=10

Method	ByteSet	Median	StdDev
FirstByteVector	3	2.5600 ns	0.0417 ns
FirstByteXorMagic	3	1.0162 ns	0.0292 ns
FirstByteMagic	3	1.1078 ns	0.0200 ns
FirstByteVector	11	2.5268 ns	0.0195 ns
FirstByteXorMagic	11	1.3804 ns	0.0232 ns
FirstByteMagic	11	1.4678 ns	0.0242 ns
FirstByteVector	19	3.0000 ns	0.0231 ns
FirstByteXorMagic	19	1.6427 ns	0.0316 ns
FirstByteMagic	19	1.8332 ns	0.0305 ns
FirstByteVector	27	2.2035 ns	0.0284 ns
FirstByteXorMagic	27	1.7401 ns	0.0170 ns
FirstByteMagic	27	3.0610 ns	0.0271 ns