Last active
October 6, 2016 16:56
-
-
Save mburbea/d36918c64569b7a6d1d126cfbcd7e020 to your computer and use it in GitHub Desktop.
Redux test
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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); | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Results of latest version 10-6-2016:
Host Process Environment Information: