EtagParsingBench.cs

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);
        }
    }
}

results.txt

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