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:

Há muitos anos, tinha o hábito de fazer elogios públicos a tudo que achava que estava sendo bem-feito. Achava honestamente...
The following works as expected when building in Debug – the execution is done after three seconds. But, for some...
In this post, I’m going to share with you one of the RavenDB 4 features that I like the most:...
Nesses últimos tempos, com a pandemia, inaugurei novos hábitos e aposentei outros. Estou trabalhando muito mais, mas também, agora que...
In this post, I would like to share my current reading list. If you are reading some of these books,...
Como você pode se considerar um profissional se você não sabe se todo seu código funciona? Como você pode saber...
Oferta de pré-venda!

Mentoria em
Arquitetura de Software

Práticas, padrões & técnicas para Arquitetura de Software, de maneira efetiva, com base em cenários reais para profissionais envolvidos no projeto e implantação de software.

× Precisa de ajuda?