Skip to content

Instantly share code, notes, and snippets.

@benaadams

benaadams/DeBruijnBenchmark.cs

Forked from mburbea/DeBruijnBenchmark.cs
Created October 2, 2016 04:37
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save benaadams/3e65fb08d494828575c714d4a83f1841 to your computer and use it in GitHub Desktop.
Save benaadams/3e65fb08d494828575c714d4a83f1841 to your computer and use it in GitHub Desktop.
Download ZIP
Redux test
Raw
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;
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