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.

Compartilhe este insight:

Elemar Júnior

Sou fundador e CEO da EximiaCo e atuo como tech trusted advisor ajudando diversas empresas a gerar mais resultados através da tecnologia.

Elemar Júnior

Sou fundador e CEO da EximiaCo e atuo como tech trusted advisor ajudando diversas empresas a gerar mais resultados através da tecnologia.

Mais insights para o seu negócio

Veja mais alguns estudos e reflexões que podem gerar alguns insights para o seu negócio:

Retomar em plenitude todas as atividades econômicas, aumentando o risco de contágio pelo novo coronavírus e, eventualmente, sacrificar uma parcela...
This one comes from Ayende’s book about RavenDB. If you want to learn RavenDB basics, I would recommend you to...
In this post, I will show how to do your first steps with OpenCV quickly using Visual Studio 2017 and...
Eu sei que sou privilegiado, em última instância, por poder oferecer, através do meu trabalho, algo que a sociedade valoriza....
Em minhas consultorias, quando questionado sobre escalabilidade, recorro sempre ao scale cube, compartilhado no excelente livro “The Art of Scalability”,...
Sabemos que é  inevitável que diferentes áreas da empresa busquem e utilizem mais de uma solução de software, com frequência...

Crie sua conta

Preencha os dados para iniciar o seu cadastro no plano anual do Clube de Estudos:

Crie sua conta

Preencha os dados para iniciar o seu cadastro no plano mensal do Clube de Estudos:

× Precisa de ajuda?