C# Unexpected performance results for different methods of parsing byte[] as hex string

Question

I have created 3 different methods for converting a byte[] into a hex string using the following format: { 0xx2, ... } (Working Demo)

using System;
using System.Diagnostics;
using System.Text;

public class Program
{
    public delegate string ParseMethod(byte[] Msg);
    public class Parser 
    {
        public string Name { get; private set;}
        public ParseMethod Handler { get; private set; }

        public Parser(string name, ParseMethod method)
        {
            Name = name;
            Handler = method;
        }
    }

    public static void Main()
    {
        Parser HexA = new Parser("ToHexA", ToHexA);
        Parser HexB = new Parser("ToHexB", ToHexB);
        Parser HexC = new Parser("ToHexC", ToHexC);

        TestCorrectness(HexA);
        TestCorrectness(HexB);
        TestCorrectness(HexC);

        Console.WriteLine("Small Message Performance:");
        TestPerformance(HexA, MsgSize: 10, Iterations: 1000000);
        TestPerformance(HexB, MsgSize: 10, Iterations: 1000000);
        TestPerformance(HexC, MsgSize: 10, Iterations: 1000000);
        Console.WriteLine();

        Console.WriteLine("Large Message Performance:");
        TestPerformance(HexA, MsgSize: 500, Iterations: 1000000);
        TestPerformance(HexB, MsgSize: 500, Iterations: 1000000);
        TestPerformance(HexC, MsgSize: 500, Iterations: 1000000);
        Console.WriteLine();
    }

    private static void TestCorrectness(Parser parser)
    {
        Console.WriteLine("Testing Correctness of \"{0}(byte[] Msg)\"", parser.Name);
        Console.WriteLine("\"{0}\"", parser.Handler(new byte[]{}));
        Console.WriteLine("\"{0}\"", parser.Handler(new byte[]{ 97 }));
        Console.WriteLine("\"{0}\"", parser.Handler(new byte[]{ 97, 98, 99, 0, 100 }));
        Console.WriteLine();
    }

    private static void TestPerformance(Parser parser, int MsgSize, int Iterations)
    {
        Stopwatch sw = new Stopwatch();
        sw.Reset();

        byte[] Msg = new byte[MsgSize];

        sw.Start();
        for (uint i = 0; i < Iterations; ++i)
        {
            parser.Handler(Msg);
        }
        sw.Stop();

        Console.WriteLine("Performance for \"{0}\", {1}", parser.Name, sw.Elapsed);
    }

    private static string ToHexA(byte[] buffer)
    {
        return
            (
                "{ 0x" +
                    BitConverter.ToString(buffer).ToLower()
                        .Replace("-", ", 0x") +
                " }"
            )
            .Replace(" 0x }", "}");
    }

    private static string ToHexB(byte[] buffer)
    {
        if (buffer.Length == 0) { return "{}"; }

        const string Preamble = "{ 0x";
        const string Delimiter = ", 0x";
        const string Epilogue = " }";

        string Msg = Preamble + buffer[0].ToString("x2");
        for (int i = 1; i < buffer.Length; ++i)
        {
            Msg += Delimiter + buffer[i].ToString("x2");
        }

        return Msg += Epilogue;
    }

    private static string ToHexC(byte[] buffer)
    {
        if (buffer.Length == 0) { return "{}"; }

        const string Preamble = "{ 0x";
        const string Delimiter = ", 0x";
        const string Epilogue = " }";

        StringBuilder HexOut = new StringBuilder(
            Preamble.Length +
            (Delimiter.Length * (buffer.Length - 1)) +
            (2 * buffer.Length) +
            Epilogue.Length
        );

        HexOut.Append(Preamble);
        HexOut.Append(buffer[0].ToString("x2"));
        for (int i = 1; i < buffer.Length; ++i)
        {
            HexOut.Append(Delimiter);
            HexOut.Append(buffer[i].ToString("x2"));
        }
        HexOut.Append(Epilogue);

        return HexOut.ToString();
    }
}

Running this code I get the following performance statistics

Small Message Performance:
Performance for "ToHexA", 00:00:01.3078387
Performance for "ToHexB", 00:00:01.6939201
Performance for "ToHexC", 00:00:01.2997903

Large Message Performance:
Performance for "ToHexA", 00:00:32.5230253
Performance for "ToHexB", 00:04:23.4798762
Performance for "ToHexC", 00:00:56.2404684

I find it surprising that ToHexA (relative to ToHexC) executes faster with a longer message but slower with a shorter message. As I understand it, Replace(), +, and ToLower() all have to perform a create/copy operation because strings are immutable.

At the same time, I suspected the overhead for StringBuilder might make it less suitable for shorter messages yet it executes faster than ToHexA in this situation.

The only thing I expected was the performance hit associated with ToHexB which is kind of an in between worst of both worlds scenario...

So, what is going on with these two methods and their performance characteristics?

Edit to make my intentions with this question more clear

I am not particularly interested in exact performance characteristics of two methods that are closely performant. I am aware this will be different on different devices, architectures, background processes, etc etc. and better testing methods exist to control variables and what not

My purpose in asking this question was to better understand why two noticeably dissimilar (in terms of performance) approaches stack up the way they do. The accepted answer explains the mechanics of ToString in a way that satisfies this question.

One constraint of this question the exact formatting of the output was specific and (we can only muse why, I think it's pretty standard) for some reason not one of the standard output formats in C#/.NET; it was this unique format that led to the question: stacking multiple replace and concatenation operations against StringBuilder

Answer 1

Your approach C is going to be the fastest approach to concatenation, however you're still generating garbage with each call to ToString("x2").

In addition to that, the ToString overloads that take a format string are miserably slow for something like this, because they first have to process the format string before they can do actual work, and this format string processing gets repeated many many times. Too bad there isn't a Converter<byte, string> GetToString(string format) that processes the format string once and returns a stateful conversion object.

In any case, byte.ToString() is very easy to avoid here.

static readonly char[] digits = "0123456789abcdef".ToCharArray();
private static string ToHexD(byte[] buffer)
{
    if (buffer.Length == 0) { return "{}"; }

    const string Preamble = "{ 0x";
    const string Delimiter = ", 0x";
    const string Epilogue = " }";

    int expectedLength = 
        Preamble.Length +
        (Delimiter.Length * (buffer.Length - 1)) +
        (2 * buffer.Length) +
        Epilogue.Length;
    StringBuilder HexOut = new StringBuilder(expectedLength);

    HexOut.Append(Preamble);
    HexOut.Append(digits[buffer[0] >> 4]).Append(digits[buffer[0] & 0x0F]);
    for (int i = 1; i < buffer.Length; ++i)
    {
        HexOut.Append(Delimiter);
        HexOut.Append(digits[buffer[i] >> 4]).Append(digits[buffer[i] & 0x0F]);
    }
    HexOut.Append(Epilogue);

    return HexOut.ToString();
}

Two calls to Append(char) should also be faster than one to Append(string), though this is much less important than saving the time on format strings.

As expected, this beats the BitConverter-then-Replace() approach handily at all sizes (by just about a factor of two).

For a tiny bit of further increase in speed, the calculations buffer[i] >> 4 and buffer[i] & 0x0f can both be avoided by preparing lead-digit and tail-digit lookup tables of length 256 each. But bitwise operations are incredibly fast; on many microcontrollers lacking a large L1 data cache, increasing the size of the lookup tables would cost more performance than the bitwise ops.

Answer 2

As discussed, here is a highly tuned function that is specialized for this requested output. Please forgive the "magic values" :), I threw this together as a POC :), but it is extremely fast which was the point. It avoids all string operations, StringBuilder, calling additional methods, etc.

private unsafe static string ToHexA2(byte[] buffer)
{
    int length = buffer.Length;
    int num = (length * 6) + 2;
    char[] array = new char[num];
    int num2 = 0;

    fixed (char* ptr = array)
    {
        *(long*)ptr = 0x0020007B;

        for (int i = 2; i < num; i += 6)
        {
            byte b = buffer[num2++];
            *(long*)(ptr + i) = 0x00780030;
            *(long*)(ptr + i + 2) = digits[b >> 4] | (digits[b & 0x0F] << 16);
            *(long*)(ptr + i + 4) = 0x0020002C;
        }

        *(long*)(ptr + num - 2) = 0x007D0020;
    }

    return new string(array, 0, array.Length);
}