Inversão de Strings

Há algum tempo aponto o “abuso” do GC é uma das principais causa para problemas de performance em produção.

Nesse post, discuto formas eficientes (e não eficientes) para inverter strings. (SPOILER: Vamos obter um ganho de 18x)

Este post é baseado em uma excelente apresentação do Ayende, ainda não disponível em vídeo.

Usando LINQ

A forma mais simples de se inverter uma string, acredito, em C# é usando LINQ.

public static string NaiveRerverseString(string input) =>
    new string(input.Reverse().ToArray());

O problema dessa abordagem é que ela faz três alocações.

1. o new string para gerar o valor de retorno
2. a função Reverse que aloca um enumerator de chars
3. a função ToArray que cria um array da enumeração de chars gerada pela Reverse.

Estamos gerando pressão para o GC e isso não é uma coisa boa.

Dispensando LINQ

Minha primeira abordagem para melhorar a performance da função seria dispensar LINQ (que não está agregando tanto valor aqui). Vejamos:

public static string CharReverseString(string input)
{
    var reversedCharArray = new char[input.Length];
    for (
        int i = input.Length - 1, destIndex = 0; 
        i >= 0; 
        i--, destIndex++
        )
    {
        reversedCharArray[destIndex] = input[i];
    }
    return new string(reversedCharArray);
}

Esta abordagem é sim um pouco mais complexa (e complexidade é custo!). Mas, remove o LINQ da solução e, consequentemente, algumas alocações.

Usando Stack no lugar da Heap

Sempre que possível é interessante usar estruturas na Stack no lugar da Heap. Isso alivia o GC, pois o Stack não é gerenciado pelo Garbage Collector. Infelizmente, essa solução exige adoção de códigos unsafe.

public static unsafe string StackAllocReverseString(string input)
{
    var reversedCharArray = stackalloc char[input.Length];
    for (
        int i = input.Length - 1, destIndex = 0;
        i >= 0;
        i--, destIndex++
    )
    {
        reversedCharArray[destIndex] = input[i];
    }
    return new string(reversedCharArray);
}

Na primeira linha, uso stackalloc para alocar o array de caracteres na stack no lugar de usar a heap. Entrentanto, tome cuidado com essa abordagem. Lembre-se que StackOverflowException é uma das exceptions que não podem ser tratadas e que encerram o processo.

Ponteiros! Unsafe.

Códigos marcados como unsafe costumam assustar programadores menos experientes. Geralmente, esse medo não é justificado. Vejamos:

public static unsafe string UnsafeReverseString(string input)
{
    var result = new string(' ', input.Length);
    fixed (char* source = input)
    fixed (char* dest = result)
    {
        for (
            int i = input.Length - 1, destIndex = 0;
            i >= 0;
            i--, destIndex++
        )
        {
            dest[destIndex] = source[i];
        }
    }
    return result;
}

Aqui, temos agora apenas a alocação da string que será gerada como retorno. É a versão com menor “peso” para o GC e sem riscos para a Stack.

Teoricamente, essa seria a nossa versão mais rápida.

Usando Span<T>

.NET agora oferece uma forma nova e excitante de manipular memória com menos alocações. Trata-se da classe Span<T>. Vejamos:

public static string SpanReverseString(string input) =>
    string.Create(input.Length, input, (span, s) =>
    {
        var index = 0;
        for (var i = s.Length - 1; i >= 0; i--)
        {
            span[index] = s[i];
            index++;
        }
    });

A vantagem desse código é que ele também não gera alocações desnecessárias e… não é unsafe.

Comparando performance

Usei BenchmarkDotNet para fazer a comparação de performance dessas versões. Aqui está o resultado:

                  Method |      Mean |     Error |     StdDev |
------------------------ |----------:|----------:|-----------:|
       LinqReverseString | 506.18 ns | 9.8646 ns | 13.8288 ns |
       CharReverseString |  40.80 ns | 0.8386 ns |  1.4466 ns |
 StackAllocReverseString |  39.00 ns | 0.7961 ns |  1.1160 ns |
     UnsafeReverseString |  27.97 ns | 0.5840 ns |  0.9092 ns |
       SpanReverseString |  33.40 ns | 0.7612 ns |  1.0670 ns |

Como você pode constatar, chegamos a uma melhoria de 18x (nada mal). O que fizemos foi “reconhecer e respeitar” o GC.

Concluindo

Seguramente, inversão de strings não é a grande “ofensora” do que trata de performance para sua aplicação. Meu ponto é que o desenvolvedor costuma ignorar o GC em todo o código e, a soma de pequenos prejuízos resulta uma aplicação lenta.

Seguramente, a versão com LINQ é a mais declarativa e, seguramente, a mais expressiva. Porém, ela também é a mais lenta. Temos que considerar esse tradeoff na hora de escrever nosso código.

Por fim, temos recursos novos para melhorar a performance de nossas aplicações. A classe Span pode representar uma revolução permitindo que escrevamos códigos muito mais rápidos (e economicos) sem ter de recorrer a blocos unsafe. Recomendo que você a estude com carinho.