-
-
Save benaadams/3e65fb08d494828575c714d4a83f1841 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; | |
namespace DeBruijnBenchmark | |
{ | |
public class Program | |
{ | |
public static void Main() | |
{ | |
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 byte[] Debruijn64Xor = | |
{ | |
0, 5, 0, 7, 6, 3, 0, 7, | |
7, 6, 5, 4, 3, 2, 0, 7, | |
6, 7, 4, 6, 6, 5, 2, 5, | |
4, 4, 3, 2, 2, 1, 0, 7, | |
5, 6, 3, 7, 5, 4, 1, 6, | |
4, 6, 2, 5, 3, 2, 1, 5, | |
3, 4, 1, 4, 2, 3, 1, 3, | |
1, 2, 1, 1, 0, 0, 0, 7, | |
}; | |
private static readonly byte[] Debruijn64Long = | |
{ | |
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 ulong DEBRUIJN_SEQ64 = 0x03f79d71b4cb0a89; | |
const long DEBRUIJN_SEQ64L = 0x26752B916FC7B0D; | |
[MethodImpl(MethodImplOptions.AggressiveInlining)] | |
private static int DebruijnFindByteXor(ulong v) | |
{ | |
return Debruijn64Xor[((v ^ (v - 1)) * DEBRUIJN_SEQ64) >> 58]; | |
} | |
[MethodImpl(MethodImplOptions.AggressiveInlining)] | |
private static int DebruijnFindByte(long v) | |
{ | |
return Debruijn64Long[(ulong)((v & -v) * DEBRUIJN_SEQ64L) >> 58]; | |
} | |
[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); | |
} | |
/// <summary> | |
/// Find first byte | |
/// </summary> | |
/// <param name="byteEquals"></param > | |
/// <returns>The first index of the result vector</returns> | |
/// <exception cref="InvalidOperationException">byteEquals = 0</exception> | |
[MethodImpl(MethodImplOptions.AggressiveInlining)] | |
private static int FindFirstEqualByteOld(ref Vector<byte> byteEquals) | |
{ | |
var vector64 = Vector.AsVectorInt64(byteEquals); | |
long u; | |
if ((u = vector64[0]) != 0) return FindByteQuasiTree(u); | |
if ((u = vector64[1]) != 0) return 8 + FindByteQuasiTree(u); | |
if (Vector<long>.Count == 2) return -1; | |
if ((u = vector64[2]) != 0) return 16 + FindByteQuasiTree(u); | |
if ((u = vector64[3]) != 0) return 24 + FindByteQuasiTree(u); | |
if (Vector<long>.Count == 4) return -1; | |
if ((u = vector64[4]) != 0) return 32 + FindByteQuasiTree(u); | |
if ((u = vector64[5]) != 0) return 40 + FindByteQuasiTree(u); | |
if ((u = vector64[6]) != 0) return 48 + FindByteQuasiTree(u); | |
if ((u = vector64[7]) != 0) return 56 + FindByteQuasiTree(u); | |
return -1; | |
} | |
/// <summary> | |
/// Find first byte | |
/// </summary> | |
/// <param name="byteEquals"></param > | |
/// <returns>The first index of the result vector</returns> | |
/// <exception cref="InvalidOperationException">byteEquals = 0</exception> | |
[MethodImpl(MethodImplOptions.AggressiveInlining)] | |
internal static int FindFirstEqualByteDeBrujinXor(ref Vector<byte> byteEquals) | |
{ | |
var vector64 = Vector.AsVectorUInt64(byteEquals); | |
ulong u; | |
if ((u = vector64[0]) != 0) return DebruijnFindByteXor(u); | |
if ((u = vector64[1]) != 0) return 8 + DebruijnFindByteXor(u); | |
if (Vector<long>.Count == 2) return -1; | |
if ((u = vector64[2]) != 0) return 16 + DebruijnFindByteXor(u); | |
if ((u = vector64[3]) != 0) return 24 + DebruijnFindByteXor(u); | |
if (Vector<long>.Count == 4) return -1; | |
if ((u = vector64[4]) != 0) return 32 + DebruijnFindByteXor(u); | |
if ((u = vector64[5]) != 0) return 40 + DebruijnFindByteXor(u); | |
if ((u = vector64[6]) != 0) return 48 + DebruijnFindByteXor(u); | |
if ((u = vector64[7]) != 0) return 56 + DebruijnFindByteXor(u); | |
return -1; | |
} | |
/// <summary> | |
/// Find first byte | |
/// </summary> | |
/// <param name="byteEquals"></param > | |
/// <returns>The first index of the result vector</returns> | |
/// <exception cref="InvalidOperationException">byteEquals = 0</exception> | |
[MethodImpl(MethodImplOptions.AggressiveInlining)] | |
internal static int FindFirstEqualByteDeBrujin(ref Vector<byte> byteEquals) | |
{ | |
var vector64 = Vector.AsVectorInt64(byteEquals); | |
long u; | |
if ((u = vector64[0]) != 0) return DebruijnFindByte(u); | |
if ((u = vector64[1]) != 0) return 8 + DebruijnFindByte(u); | |
if (Vector<long>.Count == 2) return -1; | |
if ((u = vector64[2]) != 0) return 16 + DebruijnFindByte(u); | |
if ((u = vector64[3]) != 0) return 24 + DebruijnFindByte(u); | |
if (Vector<long>.Count == 4) return -1; | |
if ((u = vector64[4]) != 0) return 32 + DebruijnFindByte(u); | |
if ((u = vector64[5]) != 0) return 40 + DebruijnFindByte(u); | |
if ((u = vector64[6]) != 0) return 48 + DebruijnFindByte(u); | |
if ((u = vector64[7]) != 0) return 56 + DebruijnFindByte(u); | |
return -1; | |
} | |
[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; | |
} | |
public static readonly Vector<byte>[] _vectors = InitVectors(); | |
//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] = 1; | |
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 FindFirstEqualByteOld(ref vector); | |
} | |
[Benchmark] | |
public int FirstByteDeBruijnXor() | |
{ | |
var vector = _vectors[ByteSet]; | |
return FindFirstEqualByteDeBrujinXor(ref vector); | |
} | |
[Benchmark] | |
public int FirstByteDeBruijnClassic() | |
{ | |
var vector = _vectors[ByteSet]; | |
return FindFirstEqualByteDeBrujin(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 = FindFirstEqualByteDeBrujin(ref vvalue); | |
int vPos = FindFirstEqualByteOld(ref vvalue); | |
int dbxPos = FindFirstEqualByteDeBrujinXor(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