Span<T>

module ReverseString

open System
open Microsoft.FSharp.NativeInterop

let reverse (input: string) =
    let memory = NativePtr.stackalloc<byte>(input.Length) |> NativePtr.toVoidPtr
    let span = Span<char>(memory, input.Length)

    for i in 0..input.Length - 1 do
        span[input.Length - 1 - i] <- input[i]

    span.ToString()

F# 4.5 introduced support for 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>:

let array = Array.zeroCreate<char>(input.Length)
let span = Span<char>(array)

for i in 0..input.Length - 1 do
    span[input.Length - 1 - i] <- input[i]

span.ToString()

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 [NativePtr.stackalloc]nativeptr.stackalloc. With stackalloc, we can assign a block of memory on the stack (whereas the array would be stored on the heap).

let memory = NativePtr.stackalloc<byte>(input.Length) |> NativePtr.toVoidPtr
let span = Span<char>(memory, 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.

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.