Implementing faster StringBuilder that only works with ASCII strings

Question

I wrote a StringBuilder that works only with ASCII strings. the current append performance is almost identical to BCL StringBuilder append performance. I want some tips on how to make it faster, and general tips about the code. I did this for educational purposes.

Implementation:

public sealed class FastStringBuilder
{
    private byte[] chars;

    public int Length { get; private set; }

    public FastStringBuilder(int capacity)
    {
        chars = new byte[capacity];
    }

    public FastStringBuilder()
    {
        chars = new byte[16];   
    }

    private void GrowBy(int length)
    {
        var temp = chars;
        chars = new byte[length];
        Array.Copy(temp, 0, chars, 0, Length);
    }

    public unsafe void Append(string str)
    {
        if (str.Length + Length >= chars.Length)
            GrowBy((str.Length + Length) * 4);
        else if(Length == chars.Length)
            GrowBy(chars.Length*2);


        fixed (char* p = str)
        {
            for (int i = 0; i < str.Length; i++)
                chars[Length++] = (byte)(p + i);
        }
    }

    public override string ToString()
    {
        unsafe
        {
            fixed (byte* bp = chars)
            {
                return new string((sbyte*)bp,0,Length);
            }
        }
    }
}

Performance tests spec:

public static void StringBuilderTest()
{
    Stopwatch sw = Stopwatch.StartNew();

    StringBuilder builder = new StringBuilder();

    for (int i = 0; i < 1000000; i++)
    {
        builder.Append("F0000000000000000000000000000000000000000000000000000" );
    }

    var result = builder.ToString();

    Console.WriteLine(sw.Elapsed);
}

Results:

Compiled in release mode.

• FastStringBuilder: ~0.36 seconds
• StringBuilder: ~0.27 seconds
• FasterStringBuilder (ChrisWue's implementation): ~0.17 seconds

EDIT

mjolka spotted that FastStringBuilder had a bug.

this code was causing the bug:

    fixed (char* p = str)
    {
        for (int i = 0; i < str.Length; i++)
            chars[Length++] = (byte)(p + i);
    }

I've fixed it.

public sealed class FastStringBuilder
{
    private byte[] chars;

    public int Length { get; private set; }

    public FastStringBuilder(int capacity)
    {
        chars = new byte[capacity];
    }

    public FastStringBuilder()
    {
        chars = new byte[16];
    }

    private void GrowBy(int length)
    {
        var temp = chars;
        chars = new byte[length];
        Array.Copy(temp, 0, chars, 0, Length);
    }

    public unsafe void Append(string str)
    {
        if (str.Length + Length >= chars.Length)
            GrowBy((str.Length + Length)*4);
        else if (Length == chars.Length)
            GrowBy(chars.Length*2);



        for (int i = 0; i < str.Length; i++)
            chars[Length++] = (byte) str[i];
    }

    public override string ToString()
    {
        unsafe
        {
            fixed (byte* bp = chars)
            {
                return new string((sbyte*) bp, 0, Length);
            }
        }
    }
}

Answer 1

This is very, very buggy. This is the most reliable way I could find to reproduce the bug.

static void Main(string[] args)
{
    var sb = new FastStringBuilder();
    var chars = new[] { 'a', 'b', 'e', 'd' };
    sb.Append(new string(chars));
    Console.WriteLine(sb.ToString());
}

Note how args is not used. Now run the program with different arguments:

$ ./Test
dfhj
$ ./Test abc
OZ?'
$ ./Test abcdef
"-~s

Answer 2

Well apart from the fact that you never ever really wanted to use this in any maintainable production code I have managed to get a speed up by using the internal Memcpy method of the Buffer class (inspired by this SO answer). It requires some reflection magic as it's an internal method (Reflector or dotPeek or ILSpy are your friends to find out about these kind of things):

unsafe delegate void MemCpyImpl(byte* src, byte* dest, int len);

public sealed class FastStringBuilder
{
    private byte[] chars;

    public int Length { get; private set; }

    static MemCpyImpl memcpyimpl = (MemCpyImpl)Delegate.CreateDelegate(
        typeof(MemCpyImpl), 
        typeof(Buffer).GetMethod("Memcpy", BindingFlags.Static | BindingFlags.NonPublic, null, 
                                new [] { typeof(byte*), typeof(byte *), typeof(int) }, null));

    public FastStringBuilder(int capacity)
    {
        chars = new byte[capacity];
    }

    public FastStringBuilder()
    {
        chars = new byte[16];   
    }

    private void GrowBy(int length)
    {
        var temp = chars;
        chars = new byte[length];
        Array.Copy(temp, 0, chars, 0, Length);
    }

    public unsafe void Append(string str)
    {
        if (str.Length + Length >= chars.Length)
            GrowBy((str.Length + Length) * 4);
        else if(Length == chars.Length)
            GrowBy(chars.Length*2);


        fixed (byte *dst = &chars[Length])
        fixed (char* src = str)
        {
            // chars are 2 bytes due to utf-16 encoding
            memcpyimpl((byte *)src, dst, str.Length * 2);
            Length += str.Length;
        }
    }

    public override string ToString()
    {
        unsafe
        {
            fixed (byte* bp = chars)
            {
                return new string((sbyte*)bp,0,Length);
            }
        }
    }
}

Note that this implementation can break any time due to the Memcpy method being renamed or removed. You could use any of the available disassembler tools and look at the Memcpy implementation and copy it though. As you will note the original SO answer tried to use a method called memcpyimpl which no longer exists in .NET 4.5 so it has been changed in the past.

The speedup is better when you append longer strings. Right now you only append simple numbers turned into strings so the appended strings are very short. If you change the append to something like this:

builder.Append("F00000000000000000000000000000000000000000000000000000000000000000000000000000000000000" + i);

then the Memcpy version runs in about half the time of your original implementation.

The advantage with the Memcpy is that we copy all bytes hence it should work for non-ascii strings just as well.