Span<T>

Reverse String
Reverse String in C#
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.

Caution

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.

20th Nov 2024 · Found it useful?