Reverse String in Efficient Way

Unity Engine
, , , ,
1

Hi there,

What is the current way of reversing a string efficiently? I have to reverse a lot of strings for RTL language handling, and googling returns old links and following code is generated by GPT and not sure if this is right or provide any benefit?

public static string ReverseString(string value)
    {
        // Convert the string to a Span<char> to avoid extra allocations
        Span<char> charSpan = value.ToCharArray();

        // Use two-pointer technique to reverse the string in place
        int left = 0;
        int right = charSpan.Length - 1;
        while (left < right)
        {
            char temp = charSpan[left];
            charSpan[left] = charSpan[right];
            charSpan[right] = temp;

            left++;
            right--;
        }

        // Return the reversed string by creating a new string from the span
        return new string(charSpan);
    }

Please advise

2

There’s a way to get chars from string directly without allocations via unsafe fixed(char *chars = value) note: that will mutate existing string.
To then efficiently reverse the string in place you can use different algorihms, including reading in larger chunks (say 4 bytes or 8, or even more), this can help if the string is really long.

1 Like
3

If I understand the question correctly, the following code should work:

    public string ReverseString(string stringToReverse)
    {
        string reversedString = "";

        for(int i = stringToReverse.Length - 1; i >= 0; i--)
        {
            reversedString += stringToReverse[i];
        }

        return reversedString;
    }
1 Like
4

If you are asking if the chatGTP answer is efficient, then sure, yes it is. If you are asking what is the most efficient way to reverse a string then the answer is very, very, very complicated. It is like asking what is the best way to implement an inventory system in a game, it is a very broad question and depends on many factors.

What is you target hardware? how long will those strings be? Efficiency means speed? Memory? Garbage collection? Also what kind of strings? In what .Net and C# version? Are we talking about Unity with Mono? All these questions can give different solutions.

Here are some examples that may or may not help you depending on your situation. Be careful, these examples as with the GTP example, suppose that you are using the UTF16 characters that belong in the Basic Multilingual Plane (see: https://en.wikipedia.org/wiki/Plane_(Unicode), for surrogates in UTF-16 (see: https://learn.microsoft.com/en-us/windows/win32/intl/surrogates-and-supplementary-characters you will need different implementations that take this characters into account and how the reversal is done, and that will change their performance.

Here are some performant methods that reverse a string in C#:

You can use the chatGTP example but change the exchange of characters inside the loop, with the use of a deconstructor, like this: (charSpan[left], charSpan[right]) = (charSpan[right], charSpan[left]);.

You can use a Xor based approach that will do a bitwise operation like this:

public static string ReverseXor(string s)
   {
      char[] charArray = s.ToCharArray();
      int len = s.Length - 1;

      for (int i = 0; i < len; i++, len--)
      {
         charArray[i] ^= charArray[len];
         charArray[len] ^= charArray[i];
         charArray[i] ^= charArray[len];
      }

      return new string(charArray);
   }

You can use the Reverse method of the array, after creating an array of chars like this:

public static string ReverseArray(string text)
   {
      char[] array = text.ToCharArray();
      Array.Reverse(array);
      return new string(array);
   }

or you can try the same with the span reverse method, like this:

public static string ReverseSpan(string text)
   {
      Span<char> charSpan = text.ToCharArray();
      charSpan.Reverse();
      return charSpan.ToString();
   }

The results will be different, depending on the length of the string, here are some benchmarks, that use the .NET 8:

Benchmarks results

String 1

Method Mean Error StdDev Gen0 Allocated
ReverseStringGtp 23.39 ns 0.503 ns 0.470 ns 0.0179 56 B
ReverseStringDeconstruct 22.78 ns 0.208 ns 0.173 ns 0.0179 56 B
ReverseStringXor 22.24 ns 0.258 ns 0.229 ns 0.0179 56 B
ReverseStringArray 23.37 ns 0.205 ns 0.171 ns 0.0179 56 B
ReverseStringSpan 25.95 ns 0.212 ns 0.188 ns 0.0179 56 B

String 5

Method Mean Error StdDev Gen0 Allocated
ReverseStringGtp 27.32 ns 0.213 ns 0.189 ns 0.0229 72 B
ReverseStringDeconstruct 27.87 ns 0.516 ns 0.457 ns 0.0229 72 B
ReverseStringXor 29.08 ns 0.165 ns 0.129 ns 0.0229 72 B
ReverseStringArray 29.05 ns 0.383 ns 0.359 ns 0.0229 72 B
ReverseStringSpan 31.50 ns 0.438 ns 0.410 ns 0.0229 72 B

String 10

Method Mean Error StdDev Gen0 Allocated
ReverseStringGtp 32.81 ns 0.309 ns 0.289 ns 0.0306 96 B
ReverseStringDeconstruct 34.18 ns 0.518 ns 0.485 ns 0.0306 96 B
ReverseStringXor 38.62 ns 0.122 ns 0.096 ns 0.0306 96 B
ReverseStringArray 35.08 ns 0.494 ns 0.438 ns 0.0306 96 B
ReverseStringSpan 37.67 ns 0.261 ns 0.231 ns 0.0306 96 B

String 20

Method Mean Error StdDev Gen0 Allocated
ReverseStringGtp 41.05 ns 0.353 ns 0.313 ns 0.0408 128 B
ReverseStringDeconstruct 42.14 ns 0.605 ns 0.536 ns 0.0408 128 B
ReverseStringXor 53.56 ns 1.069 ns 1.000 ns 0.0408 128 B
ReverseStringArray 38.86 ns 0.809 ns 1.080 ns 0.0408 128 B
ReverseStringSpan 39.14 ns 0.557 ns 0.521 ns 0.0408 128 B

String 30

Method Mean Error StdDev Gen0 Allocated
ReverseStringGtp 51.31 ns 1.004 ns 0.890 ns 0.0561 176 B
ReverseStringDeconstruct 51.84 ns 0.331 ns 0.259 ns 0.0561 176 B
ReverseStringXor 67.57 ns 0.373 ns 0.331 ns 0.0560 176 B
ReverseStringArray 44.13 ns 0.518 ns 0.433 ns 0.0561 176 B
ReverseStringSpan 42.47 ns 0.788 ns 0.737 ns 0.0561 176 B

String 40

Method Mean Error StdDev Gen0 Allocated
ReverseStringGtp 62.45 ns 0.413 ns 0.366 ns 0.0663 208 B
ReverseStringDeconstruct 62.17 ns 0.253 ns 0.211 ns 0.0663 208 B
ReverseStringXor 84.76 ns 0.837 ns 0.699 ns 0.0663 208 B
ReverseStringArray 46.27 ns 0.554 ns 0.492 ns 0.0663 208 B
ReverseStringSpan 48.64 ns 0.529 ns 0.495 ns 0.0663 208 B

String 50

Method Mean Error StdDev Gen0 Allocated
ReverseStringGtp 71.21 ns 0.804 ns 0.713 ns 0.0815 256 B
ReverseStringDeconstruct 74.21 ns 0.690 ns 0.576 ns 0.0815 256 B
ReverseStringXor 102.18 ns 1.449 ns 1.285 ns 0.0815 256 B
ReverseStringArray 52.31 ns 0.222 ns 0.173 ns 0.0816 256 B
ReverseStringSpan 55.29 ns 0.197 ns 0.165 ns 0.0816 256 B

String 200

Method Mean Error StdDev Gen0 Allocated
ReverseStringGtp 238.5 ns 1.51 ns 1.34 ns 0.2699 848 B
ReverseStringDeconstruct 240.8 ns 3.45 ns 3.06 ns 0.2699 848 B
ReverseStringXor 342.3 ns 4.04 ns 3.37 ns 0.2699 848 B
ReverseStringArray 129.3 ns 0.99 ns 0.92 ns 0.2701 848 B
ReverseStringSpan 133.4 ns 1.21 ns 1.01 ns 0.2701 848 B

String 500

Method Mean Error StdDev Gen0 Allocated
ReverseStringGtp 568.2 ns 11.02 ns 14.71 ns 0.6523 2 KB
ReverseStringDeconstruct 571.6 ns 3.79 ns 3.36 ns 0.6523 2 KB
ReverseStringXor 829.3 ns 6.44 ns 6.02 ns 0.6523 2 KB
ReverseStringArray 316.4 ns 4.63 ns 3.86 ns 0.6523 2 KB
ReverseStringSpan 306.4 ns 2.49 ns 2.21 ns 0.6523 2 KB

As you can see from the benchmarks, the chat GTP solution is more performant for smaller strings, but looses performance compared to the Reverse methods as the strings get bigger.

The deconstruct method, will always be a little slower, but easier to read and the difference is negligible, because by looking at the lowered C# code one more local variable is introduced.

The Reverse array method will call the SpanHelpers.Reverse method so its performance will be comparable to the span reverse method, but there are some other things that we have to take into account and that is the target hardware, the .Net version and the compiler used.

By looking at the implementation of the SpanHelpers.Reverse method in .NET 8, we will see that it depends on the hardware that is available and specifically if the target hardware has 128, 256 and 512 bit registers.

After all these, you can understand that there is no “current way of reversing a string efficiently”. Even with those benchmarks, you will get different results depending on hardware and string length and only for the “normal” characters of the UTF16. You will get different results even for different .NET versions and compilers, let alone the Unity’s Mono environment, the slower Span version etc.

The only answer is that you should benchmark yourself, in your target hardware, with the character set that will be used, by taking into account the average length of the expected strings. Will you reverse one word at a time or a whole paragraph?

Finally, even at 500 length strings the difference is about 250 ns. I would argue that for any performance that differences of a few microseconds or less are important, then C# is not the language that should be used.

So use, what is more readable and easier to understand for you and whoever else is going to read the code.

Hope this helps somehow.

1 Like
5

Thank you for your detailed answer,
As I’ll be using Unity for targeting multiple platforms (or atleast hoping :wink: ) so should you recommend i stick to Span based? as atleat its more future proof and whenever .net gets better; underlying code also become better rather than writing gpt approach which might never get the optimization right

6

If the few nanoseconds difference in performance for small strings don’t matter and you characters belong to the BMP, I would go with the span reversal for the reasons you mentioned.

But that still depends on Unity version, my benchmark was with .NET 8 not with the current Unity mono runtime. I’m sure the current Unity implementation of reverse will have differences in speed as Unity still uses the slower span version.

Every example will also work for multiple platforms except if you use unsafe code. I believe it is better to depend on the BCL as it gets upgrades over time and low level optimizations, with the condition that Unity will update eventually to .NET from mono.

2 Likes
7

As I was taking a look at this problem again for my blog, the following method seems to be faster from all others (2X -3X times faster) and with half the allocations (tested in .NET 8 like the previous methods), the only problem as with any method that doesn’t handle individual chars is that it is not suitable for checking and handling non-BMP characters. I add this to my previous answer for completeness:

public static string StringReverseWithCreate(string text)
{
   return string.Create(text.Length, text, (chars, text) =>
   {
      text.AsSpan().CopyTo(chars);
      chars.Reverse();
   });
 }