Skip to content

Instantly share code, notes, and snippets.

/EtagParsingBench.cs
Created Jan 21, 2015

Embed
What would you like to do?
using System;
using System.Text;
using System.Linq;
using System.Diagnostics;
using System.Runtime.CompilerServices;
namespace TryOuts
{
public class Etag
{
public Etag() { }
public Etag(long restarts, long changes)
{
this.restarts = restarts;
this.changes = changes;
}
public long restarts;
public long changes;
public override bool Equals(object obj)
{
if (ReferenceEquals(this, obj))
return true;
Etag other = obj as Etag;
if (ReferenceEquals(other, null))
return false;
return restarts == other.restarts && changes == other.changes;
}
public override int GetHashCode()
{
return (restarts.GetHashCode() ^ changes.GetHashCode());
}
public override string ToString()
{
return string.Format("({0}, {1})", restarts, changes);
}
}
static class EtagParsingUtil
{
private readonly static int[] _asciisOfHexToNum = CreateHexCharsToNumsTable();
private static int[] CreateHexCharsToNumsTable()
{
var c = new int['z' + 1];
for (var i = '0'; i <= '9'; i++)
{
c[i] = (char)(i - '0');
}
for (var i = 'A'; i <= 'Z'; i++)
{
c[i] = (char)((i - 'A') + 10);
}
for (var i = 'a'; i <= 'z'; i++)
{
c[i] = (char)((i - 'a') + 10);
}
return c;
}
public unsafe static Etag Parse(string str)
{
if (str == null || str.Length != 36)
throw new ArgumentException("str cannot be empty or null");
fixed (char* input = str)
{
var etag = new Etag();
int fst = ((byte)(_asciisOfHexToNum[input[0]] * 16 + _asciisOfHexToNum[input[1]])) << 24 |
((byte)(_asciisOfHexToNum[input[2]] * 16 + _asciisOfHexToNum[input[3]])) << 16 |
((byte)(_asciisOfHexToNum[input[4]] * 16 + _asciisOfHexToNum[input[5]])) << 8 |
((byte)(_asciisOfHexToNum[input[6]] * 16 + _asciisOfHexToNum[input[7]]));
int snd = ((byte)(_asciisOfHexToNum[input[9]] * 16 + _asciisOfHexToNum[input[10]])) << 24 |
((byte)(_asciisOfHexToNum[input[11]] * 16 + _asciisOfHexToNum[input[12]])) << 16 |
((byte)(_asciisOfHexToNum[input[14]] * 16 + _asciisOfHexToNum[input[15]])) << 8 |
((byte)(_asciisOfHexToNum[input[16]] * 16 + _asciisOfHexToNum[input[17]]));
etag.restarts = (uint)snd | ((long)fst << 32);
fst = ((byte)(_asciisOfHexToNum[input[19]] * 16 + _asciisOfHexToNum[input[20]])) << 24 |
((byte)(_asciisOfHexToNum[input[21]] * 16 + _asciisOfHexToNum[input[22]])) << 16 |
((byte)(_asciisOfHexToNum[input[24]] * 16 + _asciisOfHexToNum[input[25]])) << 8 |
((byte)(_asciisOfHexToNum[input[26]] * 16 + _asciisOfHexToNum[input[27]]));
snd = ((byte)(_asciisOfHexToNum[input[28]] * 16 + _asciisOfHexToNum[input[29]])) << 24 |
((byte)(_asciisOfHexToNum[input[30]] * 16 + _asciisOfHexToNum[input[31]])) << 16 |
((byte)(_asciisOfHexToNum[input[32]] * 16 + _asciisOfHexToNum[input[33]])) << 8 |
((byte)(_asciisOfHexToNum[input[34]] * 16 + _asciisOfHexToNum[input[35]]));
etag.changes = (uint)snd | ((long)fst << 32);
return etag;
}
}
private const UInt64 packed64_0x40 = ((byte)0x40) * 0x0101010101010101;
private const UInt64 packed64_0x0f = ((byte)0x0f) * 0x0101010101010101;
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static unsafe UInt16 parse_4_chars(char* c)
{
// 1. Get 4 input characters as 16 bit chars.
UInt64 input = *(UInt64*)c;
// 2. Isolate bit for ['a'..'f', 'A'..'F']
UInt64 isAToF = input & packed64_0x40;
// 3. Convert it to 0 for ['0'..'9'] and to 9 for ['a'..'f','A'..'F']
UInt64 shift = isAToF >> 3 | isAToF >> 6;
// 4. Get merged bytes.
UInt64 merged = (input & packed64_0x0f) /* mask nibbles */ + shift /* add 9 or 0 */;
// 5. Repack nibbles in 16 bit value & reverse byte order.
UInt16 result = (UInt16)(((merged & 0x000000000000000F) << 12) |
((merged & 0x00000000000F0000) >> 8) |
((merged & 0x0000000F00000000) >> 28) |
((merged & 0x000F000000000000) >> 48));
return result;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static unsafe UInt32 parse_8_chars(char* c1, char* c2)
{
// 1. Get 8 input characters as 8 bit chars
// (interleaving c1 and c2 at 8 bit offsets).
UInt64 input = *(UInt64*)c1 | (*(UInt64*)c2 << 8);
// 2. Isolate bit for ['a'..'f', 'A'..'F']
UInt64 isAToF = input & packed64_0x40;
// 3. Convert it to 0 for ['0'..'9'] and to 9 for ['a'..'f','A'..'F']
UInt64 shift = isAToF >> 3 | isAToF >> 6;
// 4. Get merged bytes.
UInt64 merged = (input & packed64_0x0f) /* mask nibbles */ + shift /* add 9 or 0 */;
// 5. Repack nibbles in 32 bit, reverse byte order and demux
// c2 from c1 (i.e place nibbles in their correct spot).
// 0x12345678
UInt32 result = (UInt32)(((merged & 0x000000000000000F) << 28) |
((merged & 0x00000000000F0000) << 8) |
((merged & 0x0000000F00000000) >> 12) |
((merged & 0x000F000000000000) >> 32) |
((merged & 0x0000000000000F00) << 4) |
((merged & 0x000000000F000000) >> 16) |
((merged & 0x00000F0000000000) >> 36) |
((merged & 0x0F00000000000000) >> 56));
return result;
}
public unsafe static Etag ParseParallelBits(string str)
{
if (str == null || str.Length != 36)
throw new ArgumentException("str cannot be empty or null");
fixed (char* input = str)
{
var etag = new Etag();
int fst = parse_4_chars(input) << 16 | parse_4_chars(&input[4]);
int snd = parse_4_chars(&input[9]) << 16 | parse_4_chars(&input[14]);
etag.restarts = (uint)snd | ((long)fst << 32);
fst = parse_4_chars(&input[19]) << 16 | parse_4_chars(&input[24]);
snd = parse_4_chars(&input[28]) << 16 | parse_4_chars(&input[32]);
etag.changes = (uint)snd | ((long)fst << 32);
return etag;
}
}
public unsafe static Etag ParseParallelBits8(string str)
{
if (str == null || str.Length != 36)
throw new ArgumentException("str cannot be empty or null");
fixed (char* input = str)
{
var etag = new Etag();
UInt32 fst = parse_8_chars(input, &input[4]);
UInt32 snd = parse_8_chars(&input[9], &input[14]);
etag.restarts = (uint)snd | ((long)fst << 32);
fst = parse_8_chars(&input[19], &input[24]);
snd = parse_8_chars(&input[28], &input[32]);
etag.changes = (uint)snd | ((long)fst << 32);
return etag;
}
}
}
static class EtagParsingBench
{
public static void Run(int nIters, int nRepreats)
{
var guids = Enumerable.Range(0, 1000).Select(x => Guid.NewGuid().ToString()).ToArray();
// sanity check.
if (!EtagParsingUtil.Parse(guids[0]).Equals(EtagParsingUtil.ParseParallelBits(guids[0])))
throw new Exception(string.Format("Dodgy implementation: expected {0} was {1}", EtagParsingUtil.Parse(guids[0]), EtagParsingUtil.ParseParallelBits(guids[0])));
if (!EtagParsingUtil.Parse(guids[0]).Equals(EtagParsingUtil.ParseParallelBits8(guids[0])))
throw new Exception(string.Format("Dodgy implementation: expected {0} was {1}", EtagParsingUtil.Parse(guids[0]), EtagParsingUtil.ParseParallelBits8(guids[0])));
var length = guids.Length;
var etag = new Etag();
var sp = new Stopwatch();
var elapsedParse = 0L;
var elapsedBitsParse = 0L;
var elapsedBits8Parse = 0L;
for (var n = 0; n < nRepreats; n++)
{
sp.Restart();
for (int i = 0; i < nIters; i++)
EtagParsingUtil.Parse(guids[i % length]);
elapsedParse += sp.ElapsedMilliseconds;
sp.Restart();
for (int i = 0; i < nIters; i++)
EtagParsingUtil.ParseParallelBits(guids[i % length]);
elapsedBitsParse += sp.ElapsedMilliseconds;
sp.Restart();
for (int i = 0; i < nIters; i++)
EtagParsingUtil.ParseParallelBits8(guids[i % length]);
elapsedBits8Parse += sp.ElapsedMilliseconds;
if (n < nRepreats - 1)
guids = Enumerable.Range(0, 1000).Select(x => Guid.NewGuid().ToString()).ToArray();
}
var total = nRepreats * nIters;
var factor = (double)elapsedBitsParse / elapsedParse;
var factor8 = (double)elapsedBits8Parse / elapsedParse;
Console.WriteLine("Parse : {0} ms, {1:0.0} etags/ms", elapsedParse, total / (double)elapsedParse);
Console.WriteLine("ParseParallelBits : {0} ms, {1:0.0} etags/ms", elapsedBitsParse, total / (double)elapsedBitsParse);
Console.WriteLine("ParseParallelBits8 : {0} ms, {1:0.0} etags/ms", elapsedBits8Parse, total / (double)elapsedBits8Parse);
Console.WriteLine();
Console.WriteLine("ParseParallelBits is {0} than Parse at a factor of {1:0.000}", factor > 1.0d ? "slower" : "faster", factor);
Console.WriteLine("ParseParallelBits8 is {0} than Parse at a factor of {1:0.000}", factor8 > 1.0d ? "slower" : "faster", factor8);
}
}
}
Parse : 1020 ms, 29411.8 etags/ms
ParseParallelBits : 1167 ms, 25706.9 etags/ms
ParseParallelBits8 : 1050 ms, 28571.4 etags/ms
ParseParallelBits is slower than Parse at a factor of 1.144
ParseParallelBits8 is slower than Parse at a factor of 1.029
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.