A Faster Way To Reverse A String?

Question

Below is the fastest code I could create for reversing a String

public static void ReverseFast(string x)
{
    string text = x;
    StringBuilder reverse = new StringBuilder();

    for (int i = text.Length - 1; i >= 0; i--)
    {
        reverse.Append(text[i]);
    }
      Console.WriteLine(reverse);
}

I want to address every bottleneck in this equation to make it as fast as possible. The only one I can find so far is the Array Bounds check which I only partially understand. Is there anyway to disable this as I understand it if you use .Length the compiler decides not to check the bounds but if you are decrementing as I am in the for loop it still does the boundary check? Can someone convert this to use pointers for me which would avoid the boundary check, I would like to test the speed difference for strings in the range of 100k+ characters.

Based on the comments and posts below this is what I have come up with so far.

public static void ReverseFast(string x)
{
    StringBuilder reverse = new StringBuilder(x.Length);
    for (int i = x.Length - 1; i >= 0; i--)
    {
        reverse.Append(x[i]);
    }
    Console.WriteLine(reverse);
}

This above solution is way faster than the suggested duplicate question answer. This question is really addressing reversal in the range of 5000 * 26 characters +. I would still like to test this out using pointers to really see if there is no bottleneck especially with such large amount of characters.

Answer 1

var arr = x.ToCharArray();
Array.Reverse(arr);
return new string(arr);

Note, however, that this will reverse any unicode modifier characters (accents, etc).

Benchmark:

Array.Reverse: 179ms
StringBuilder: 475ms

With:

static void Main()
{
    string text = new string('x', 100000);
    GC.Collect();
    GC.WaitForPendingFinalizers();
    var watch = Stopwatch.StartNew();
    const int LOOP = 1000;
    for (int i = 0; i < LOOP; i++)
    {
        var arr = text.ToCharArray();
        Array.Reverse(arr);
        string y = new string(arr);
    }
    watch.Stop();
    Console.WriteLine("Array.Reverse: {0}ms", watch.ElapsedMilliseconds);

    GC.Collect();
    GC.WaitForPendingFinalizers();
    watch = Stopwatch.StartNew();
    for (int i = 0; i < LOOP; i++)
    {
        var reverse = new StringBuilder(text.Length);
        for (int j = text.Length - 1; j >= 0; j--)
        {
            reverse.Append(text[j]);
        }
        string y = reverse.ToString();
    }
    watch.Stop();
    Console.WriteLine("StringBuilder: {0}ms", watch.ElapsedMilliseconds);
}

If we try a string of length 500 and loop 500000 times:

Array.Reverse: 480ms
StringBuilder: 1176ms

I also tried adding unsafe into that, i.e.

fixed (char* c = text)
{
    for (int j = text.Length - 1; j >= 0; j--)
    {
        reverse.Append(c[j]);
    }
}

this made no difference whatsoever.

And I added in JeffRSon's answer too; I get:

Array.Reverse: 459ms
StringBuilder: 1092ms
Pointer: 513ms

(for the 500 length x 5000 iterations test)

Answer 2

Here's a pointer based solution:

unsafe String Reverse(String s)
        {
            char[] sarr = new char[s.Length];
            int idx = s.Length;
            fixed (char* c = s)
            {
                char* c1 = c;
                while (idx != 0)
                {
                    sarr[--idx] = *c1++;
                }
            }

            return new String(sarr);
        }

Getting rid of the array index (sarr[--idx]) the following might be faster:

unsafe String Reverse(String s)
        {
            char[] sarr = new char[s.Length];
            fixed (char* c = s)
            fixed (char* d = sarr)
            {
                char* c1 = c;
                char* d1 = d + s.Length;
                while (d1 > d)
                {
                    *--d1 = *c1++;
                }
            }

            return new String(sarr);
        }

Answer 3

Set the capacity when you create the StringBuilder, that way it doesn't have to grow during the loop and allocate more memory. Assigning the parameter to a local variable is an unnecessary step, as the parameter is already a local variable.

public static void ReverseFast(string text) {
  StringBuilder reverse = new StringBuilder(text.Length);
  for (int i = text.Length - 1; i >= 0; i--) {
    reverse.Append(text[i]);
  }
}

That is just the basic steps to remove any unneccesary work. If you really have a performance problem with the code, you would need to analyse what the generated code does, and possibly create different versions that do different things depending on the current framework and hardware.