Efficient String Reversal In C#

Introduction

Reversing a string in C# might sound straightforward, but when efficiency matters, there are surprisingly many ways to do it. This complexity arises from the different definitions of efficiency, such as speed and memory usage, various ways characters are represented in different character sets, and different runtimes like Unity’s Mono.

In this post, I’ll explore several methods for reversing a string that are commonly found online. I’ll also provide some benchmark results for these methods in .NET 8. However, you shouldn’t rely solely on these benchmarks; it’s crucial to benchmark the algorithms yourself. The results can vary not only across different .NET versions but also on different hardware, especially since some of the more optimized methods depend on low-level hardware implementations. Additionally, the performance will vary depending on the size of the string you want to reverse, so make sure to benchmark these methods with strings that are similar in size to those you expect to work with.

Before diving into the examples, let’s define what we mean by efficiency and discuss some important nuances of the character set that C# uses.

Definition Of Efficiency

When I refer to efficiency in the context of string reversal in this post, I’m focusing on execution speed and heap memory allocation. General memory usage, such as temporary 16-bit local variables stored on the stack, is less of a concern since memory constraints are not as tight as they once were.

I’m also discussing the algorithm’s efficiency, not the programmer’s efficiency. Some of these algorithms can be challenging to understand if you’re not familiar with how they work, and more importantly, they can be difficult to modify if the requirements change—especially when dealing with characters outside the Basic Multilingual Plane. Generally, a programmer’s efficiency is more important than the program’s efficiency.

Unless your code is in a hot path, your string reversal is the bottleneck, or its execution time is significantly greater than other factors affecting performance in your code, the choice of algorithm should prioritize programmer efficiency. Specifically, consider how easy it is to modify, debug, and test your string reversal code.

Always benchmark your specific code on your target hardware, not only because different algorithms yield different results, but also because a more performant algorithm may have minimal or even no impact in your particular situation.

UTF16 Character Set

.NET uses the UTF-16 to store characters and strings. In UTF-16, characters require either one or two 16-bit words for representation, but a char in .NET is only 16 bits in length. This means some UTF-16 characters need two char values, known as surrogates. This has two implications for string handling:

1. The length of a string may not correspond to the actual number of characters it contains. Some strings may have a greater length than the number of characters due to the presence of surrogate pairs.
2. Since a single char is insufficient to represent a non-BMP (Basic Multilingual Plane) character, special care must be taken to treat two consecutive char values as a single character, rather than reversing each 16-bit word individually.

While this might sound complex, most programs can ignore these details because the majority of commonly used characters fall within the BMP. The BMP includes characters from many languages and over 30,000 Chinese characters. However, it doesn’t include characters from some ancient languages, musical notation symbols, or many emojis. You should assess your program’s requirements, and if non-BMP characters are needed, you can use the following static methods in the char type to detect non-BMP characters:

1. Char.IsSurrogate
2. Char.IsHighSurrogate
3. Char.IsLowSurrogate
4. Char.IsSurrogatePair

You can also use the following two char static methods to convert from a 32-bit value to two chars or the reverse:

1. string ConvertFromUtf32 (int utf32)
2. int ConvertToUtf32 (char highSurrogate, char lowSurrogate) or int ConvertToUtf32 (string s, int index)

For a more low-level approach, surrogates are easy to identify since each word falls within the range 0xD800 to 0xDFFF. However, using the IsSurrogate method on a span of characters is the most efficient way to handle them.

In the following string reversal algorithms, I do not account for surrogates. These algorithms assume that the input strings contain only characters within the BMP. This is not just because non-BMP characters are rare and a special case, but also because testing would be challenging—it would depend on the number of non-BMP characters relative to the string’s length.

Moreover, implementing logic to handle surrogate characters would significantly increase the complexity of some algorithms. While handling surrogates is relatively straightforward for algorithms that process individual char values, those that use the Reverse method of the internal SpanHelpers class in .NET internally, would require substantial modifications. This method relies on marshalling memory and utilizing hardware registers, so accommodating surrogates would transform a simple statement into a series of complex logic steps, severely impacting performance.

With that in mind, let’s start with the simplest approach and build from there.

Simple Reversals

Let’s start with the least performant ways, that are also the more convenient to use. These methods are slow, but are the easiest to understand and use classes that most commonly come to mind when we have to deal with strings.

Adding To A String

One of the simplest and less performant ways is the following:

public static string StringSimpleReversal(string text)
{
   string result = String.Empty;
   for (int i = text.Length - 1; i >= 0; i--)
   {
      result += text[i];
   }
   return result;
}

Anyone with basic knowledge of C#, knows about the string immutability and how they affect the garbage collector. There are many different ways that someone can use string addition, this is just one example, but in the end it will always be the least performant way.I’m including this method here solely as a reference point, to provide a baseline for comparing the performance of other methods.

This approach involves traversing the original string backward and appending each character to a result string that starts off as empty.

Using The Reverse Enumerable Extension Method

The next method, reverses a string by using the Enumerable.Reverse method. This method is simpler to understand than the previous, a little more performant too:

public static string ReverseEnumerable(string text) => new(text.Reverse().ToArray());

As simple as it gets, only one statement and easy to understand.

Using StringBuilder

The next method that comes to mind, when dealing with strings is to use the StringBuilder class:

public static string StringBuilderReverseMethod(string text)
{
   var result = new StringBuilder(text.Length);
   for (int i = text.Length - 1; i >= 0; i--)
   {
      result.Append(text[i]);
   }
   return result.ToString();
}

Works the same way as our first method, only now, we don’t have to deal with the garbage collector as much, because of the way StringBuilder handles strings. More performant than the previous two methods, but still pretty slow compared to the “fast” reversal methods below.

Using A Temporary Value For Swapping Characters

After covering the more straightforward methods for string reversal, let’s explore some more efficient techniques. In this method, we use a temporary char variable to swap the positions of two characters. The loop iterates through the string, swapping the first character with the last, the second with the second-to-last, and so on, until it reaches the middle of the string. At this point, all the characters in the string have been reversed.

public static string ReverseStringWithTemp(string value)
{
   Span<char> charSpan = value.ToCharArray();
   
   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 new string(charSpan);
}

Interestingly, this method is the one proposed from chatGTP as the most performant way to reverse a string in C#. HINT: It is not. It is pretty performant, but not the most performant and its performance deteriorates in comparison to other methods below, as our strings get bigger.

Same With The Use Of Deconstructor

A variation of the above method, is to use a deconstructor to handle the reversal of two chars:

public static string ReverseStringDeconstruct(string value)
{
   Span<char> charSpan = value.ToCharArray();
   int left = 0;
   int right = charSpan.Length - 1;
   while (left < right)
   {
      (charSpan[left], charSpan[right]) = (charSpan[right], charSpan[left]);
      left++;
      right--;
   }
   return new string(charSpan);
}

This is easier to read than the previous one, but a little slower. The difference in performance compared to the previous is negligible (a few nanoseconds), this happens because if we check the IL code, we have two temporary variables created from the deconstruction. Use whatever seems easier to read to you, between those two methods.

Using XOR

Another way to reverse a string is by using a loop to swap the string’s characters, but this time with a XOR-based approach.

A XOR-based reversal can be particularly useful when dealing with very restrictive memory requirements, as it doesn’t require any temporary variables to swap two characters. Although this method is slower than the previous one, it’s valuable to understand because it can be applied to swap any two values, regardless of their type.

The XOR approach is based on the principle that the XOR operation is its own inverse. For example, if we have two values, A and B, and perform a XOR operation, we get a result: A XOR B = Result. If we then XOR the result with A, we retrieve B, and if we XOR it with B, we retrieve A. This property can be applied to string reversal as follows:

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

Here’s how the XOR-based string reversal works: We take the character at the start of the string as A and the character at the end as B. First, we XOR them and store the result in A’s variable. Next, we XOR B with this result (now stored in A’s variable) and store this operation’s outcome in B’s variable. This gives us the original value of A in B’s variable, while A still holds the XOR result. Finally, we XOR the value now in A’s variable with the value now in B’s variable (which holds the original A). The result of this operation, which is the original value of B, is stored in A’s variable.

Using Array And Span Reverse

The following two methods, are based on the Reverse method of the internal SpanHelpers class in .NET, as this is the method that is eventually called to perform the reversal in every case. This is a highly optimized method, that uses aggressive inlining and checks what registers are supported by the hardware and uses them, depending on their availability. Their performance is about equal, they are the most performant methods from all the above and the bigger the strings we have the greater the differences in performance gains compared to the previous methods.

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

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

Don’t get confused about the choice between using the Array.Reverse and the charSpan.Reverse as both of those under the hood use the same method. The Reverse method of the internal SpanHelpers class, will use the Vector128 Vector256 or Vector512 structs depending on your hardware, and make the reversal by using the shuffle method of those classes, along with some low level optimizations for passing the data.

Using The String.Create Method

Finally, I left the most performant method for last:

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

This method is using the String.Create method. This method, creates a string faster and with no additional allocation, as it uses a Span and unsafe operations internally to get the raw string data and then uses the same reverse method from the internal SpanHelpers class as the two previous methods. The effect is that, we have less heap memory allocations and our reversal executes faster.

The last three methods presented here, that use the reverse method from the internal SpanHelpers class, are the fastest, but they will be really difficult to modify for use with non-BMP characters, as they reverse everything in chunks. We would need a way to create strings that don’t have surrogates, pass those strings to these methods and deal with the surrogates manually. This would be a problem that would increase both the complexity and the execution time of our program, so for strings that are expected to have surrogate characters, modifying one of the methods that deal directly with the char type is preferable.

Benchmark Results

Finally some benchmarks. As I mentioned, benchmarks will differ depending on the hardware used, the length of the provided strings, the runtime and the .NET version. These are just for informational purposes and it is recommended that you run your own benchmarks on your own environment to get a more accurate view of each method’s performance.

Conclusion

These are the different ways that I have found to perform string reversal in C#. As you can see, it is not that simple, as they don’t only depend on hardware and input length, as all benchmarks do, but we also have to take into account the characters those strings contain and more specifically if they belong in the Basic Multilingual Plane. Generally, if surrogate characters are of no concern, then the methods from the BCL that use the Reversal method of the internal SpanHelpers class are preferable, as it contains low level optimizations and will get upgrades over time if needed.

If you know more performant ways to reverse a string, or you get different benchmark results in your hardware I would love if you could leave a comment below. Thank you for reading, and as always, if you have any questions or comments you can use the comments section, or contact me directly via the contact form or by email. Also, if you don’t want to miss any of the new blog posts, you can subscribe to my newsletter or the RSS feed.