public static class ReverseString
{
public static string Reverse(string input)
{
Span<char> chars = stackalloc[input.Length];
for (var i = 0; i < input.Length; i++)
{
chars[input.Length - 1 - i] = input[i];
}
return new string(chars);
}
}
C# 7.2. introduced the Span<T>
class, which was specifically designed to allow performant iteration/mutation of array-like objects.
The Span<T>
class helps improve performance by always being allocated on the stack, and not the heap.
As objects on the stack don't need to be garbage collected, this can help improve performance (check this blog post for more information).
How can we leverage Span<T>
to reverse our string
?
The string
class has an AsSpan()
method, but that returns a ReadOnlySpan<char>
, which doesn't allow mutation (otherwise we'd be able to indirectly modify the string
).
We can work around this by manually allocating a char[]
and assigning to a Span<char>
:
Span<char> chars = new char[input.Length];
for (var i = 0; i < input.Length; i++)
{
chars[input.Length - 1 - i] = input[i];
}
return new string(chars);
After creating Span<char>
, we use a regular for
-loop to iterate over the string's characters and assign them to the right position in the span.
Finally, we can use the string
constructor overload that takes a Span<char>
to create the string
.
However, this is basically the same approach as the Array.Reverse()
approach, but with us also having to manually write a for
-loop.
We can do one better though, and that is to use stackalloc
.
With stackalloc
, we can assign a block of memory on the stack (whereas the array would be stored on the heap).
Span<char> chars = stackalloc char[input.Length];
With this version, the memory allocated for the Span<char>
is all on the stack and no garbage collection is needed for that data.
The stack has a finite amount of memory.
This means that for large strings, the above code will result in a StackOverflowException
being thrown.
So what is the limit for the amount of memory we can allocate?
Well, this depends on how memory has already been allocated on the stack.
That said, a small test program successfully stack-allocated memory for 750_000
characters, so you might be fine.
Alternative
It is possible to use an alternative span-based implementation that is more readable, but has the downside of being about twice as slow:
Span<char> chars = stackalloc char[input.Length];
input.AsSpan().CopyTo(chars);
chars.Reverse();
return new string(chars);
Performance
If you're interested in how this approach's performance compares to other approaches, check the performance approach.