Crie uma alocação baixa e StringBuilder mais rápida - Span na prática

Imagem de capa Crie uma alocação baixa e StringBuilder mais rápida - Span na prática

Crie uma alocação baixa e StringBuilder mais rápida - Span na prática

A estrutura .NET é uma estrutura de propósito geral. Oferece classes e estruturas para uso diário. Um desses exemplos é o StringBuilder. A ideia por trás é simples: sempre que precisamos concatenar muitas cordas, podemos aproveitar o StringBuilder, que é mais rápido do que concatenar todas as cordas entre si. Mas nós podemos fazer melhor. Podemos criar um StringBuilder que pode funcionar mais rápido para cordas (strings) menores e usa menos alocações! Faremos isso com a ajuda de Span, um tipo introduzido com o .NET Core 2.1.

Primeiro vamos responder: Por que a concatenação de strings é lenta e requer muitas alocações. A única razão é a imutabilidade. strings são imutáveis. Isso significa que se você deseja alterar uma string ou anexar outra string à nossa string, você precisa criar uma nova. Esta é uma decisão de design consciente da equipe C#. Outras linguagens como **Swift ** ou C/C++ possuem strings mutáveis! Java também tem strings imutáveis! Strings ou restrições imutáveis em geral têm a vantagem de reduzir o uso e prever melhor o que está acontecendo. Para strings temos o internamento de strings. Basicamente, se duas strings têm o mesmo valor, geralmente elas compartilham o mesmo endereço de memória.

var text1 = "Hello";
var text2 = "Hello";
var sameAddress = text1.ReferenceEquals(text2); // is true

É daqui que estamos vindo. Agora um rápido passeio para o StringBuilder. O StringBuilder não usa strings internamente. Ele usa um variedade e o redimensiona se precisarmos de mais espaço. Mas exatamente esse redimensionamento alocará nova memória. E é aqui que queremos resolver o problema! Queremos ter um StringBuilder de baixa alocação que deve pelo menos executar o mesmo e tudo em um contexto seguro. E podemos fazê-lo. Faremos isso com a ajuda de Span.

Span para o resgate

Span foi introduzido no .net core 2.1 e a ideia é muito simples:

Span representa uma fatia de memória contígua. Você pode simplificar demais o Span da seguinte forma:

public  readonly  ref  struct Span<T>
{
   private  readonly  ref T _pointer;
   private  readonly  int _length;
   ...
}

Há algumas coisas importantes que precisamos resolver para entender por que isso está nos ajudando:

  1. Span é uma estrutura de referência somente leitura que significa que vive na pilha, sempre. Como sempre fica na pilha, não podemos usá-lo em todos os lugares onde quisermos. Basicamente toda vez que teríamos que colocar um tipo de valor na pilha , ele não funcionaria! Um exemplo simples seria que você não pode ter uma estrutura de referência como um campo em sua classe, pois isso significaria que a estrutura precisa ter uma referência na pilha. O compilador impõe essa restrição, mas também obtemos benefícios de desempenho com isso! Como sempre uma troca.
  2. O objeto Span contém um ponteiro para nosso objeto mais seu comprimento. Com isso, podemos modelar uma fatia de memória onde podemos iterar.
  3. Isso também significa que nosso referência T está na pilha. Vemos que é uma estrutura muito especializada destinada ao desempenho!

Se você quiser saber mais sobre Span, aqui está um link para a documentação oficial da Microsoft.

Construtor de string de valor

Agora, com essas informações, queremos construir um StringBuilder que use muito menos alocações e deve pelo menos executar o mesmo ou melhor e determinados cenários. Outro requisito: Nenhum código inseguro!. Eu não quero lidar com ponteiros, caso contrário eu teria escrito essa coisa diretamente em C/C++. Eu sei que existem implementações inseguras na natureza, mas podemos fazer melhor! melhor é muito subjetivo aqui, mas espero que você entenda o que quero dizer ??

Você pode encontrar o código-fonte na seção Recursos abaixo se quiser pular diretamente para o código.

Usaremos os mesmos princípios do StringBuilder que vem com o próprio .NET. Mas vamos adotá-lo:

  1. Usaremos uma variedade interna para armazenar os caracteres que são anexados
  2. Se o buffer interno atual for muito pequeno, duplicaremos o tamanho e copiaremos o conteúdo antigo para o novo buffer
  3. ToString() nos dará a string inteira
  4. Vamos oferecer um indexador que nos dá o caractere em uma posição arbitrária
public  ref  struct ValueStringBuilder
{
    private  int _bufferPosition;
    private Span<char> _buffer;

    public  ValueStringBuilder()
    {
        _bufferPosition = 0;
        _buffer = new  char[32];
    }

    public  ref  char  this[int index] => ref _buffer[index];

Esse é o nosso esquema geral! Huh? temos um campo Span as embora eu tenha falado que não está funcionando. Bem, não está funcionando para uma classe, mas se o seu escopo de retenção for uma estrutura de referência , então tudo bem. Claro que isso vem com compensações no uso que mostrarei mais tarde. Basicamente, temos um pequeno estado que consiste em nosso buffer interno _buffer e a posição atual em nosso buffer _bufferPosition. Isso é importante porque nosso buffer é dimensionado estaticamente e pode ser maior do que a string que ele realmente representa. O indexador também é muito fácil de modelar: basta devolver o char na posição específica. Feito!

A próxima coisa fácil é o método ToString():

public override string ToString() => new(_buffer[.._bufferPosition]);

Estamos fatiando nosso _buffer desde o início até _bufferPosition. É isso. Agora só falta preencher o buffer interno ??. Também aqui podemos começar com o fácil, anexando um único caractere:

public  void  Append(char c)
{
    if (_bufferPosition == _buffer.Length - 1)
    {
       Grow();
    }

    _buffer[_bufferPosition++] = c;
}

Temos uma verificação básica se nosso buffer ainda tem espaço suficiente para outro caractere, caso contrário temos que crescer nossa variedade. Como isso acontece, mostraremos mais adiante. Se o elemento (então) se encaixar, basta definir o novo caractere no final do _bufferPosition.

Antes de chegarmos ao ponto de como o Grow funciona, vamos dar uma olhada em anexar uma estrutura inteira:

public  void  Append(ReadOnlySpan<char> str)
{
    var newSize = str.Length + _bufferPosition;
    if (newSize > _buffer.Length)
        Grow(newSize * 2);

     str.CopyTo(_buffer[_bufferPosition..]);
     _bufferPosition += str.Length;
}

public  void  AppendLine(ReadOnlySpan<char> str)
{
     Append(str);
     Append(Environment.NewLine);
}

Agora primeiro: ReadOnlySpan tem uma conversão implícita de string para que o chamador possa apenas passar strings "normais". Mas os Spans são mais rápidos de operar. A diferença entre Span e ReadOnlySpan é que, como o nome sugere, não permite alterar a fatia de memória representada por ReadOnlySpan. Também poderíamos usar a palavra-chave in, mas não encontrei nenhum ganho de desempenho, mas às vezes era ainda mais lento. Agora a mágica, além de Grow() aqui é esta:

str.CopyTo(_buffer[_bufferPosition..]); // Copy the str into _buffer beginning from _bufferPosition
_bufferPosition += str.Length; // Our internal buffer is now str.Length longer

Agora a parte final: Grow()

private  void  Grow(int capacity = 0)
{
   var currentSize = _buffer.Length;
   var newSize = capacity > 0 ? capacity : currentSize * 2;
   var rented = ArrayPool<char>.Shared.Rent(newSize);
   _buffer.CopyTo(rented);
   _buffer = rented;
   ArrayPool<char>.Shared.Return(rented);
}

Se não especificarmos a capacidade, apenas dobramos o tamanho do buffer interno atual. Atualmente estou brincando em torno de qual tamanho de crescimento seria bom. Temos que encontrar um bom equilíbrio entre não reservar muito espaço, mas também não redimensionar nossa variedade com muita frequência. Por enquanto *2 é suficiente.

A próxima parte é um pouco complicada. Usaremos um ArrayPool compartilhado. Não vou entrar muito em detalhes. Aqui está um post muito legal que explica melhor do que eu poderia fazer ??. A ideia básica é agruparmos o buffer. Então, compartilhamos esse buffer com outras pessoas se não precisarmos mais dele. Como carona! A vantagem é que não temos que alocar novos objetos o tempo todo, o que a) custa tempo eb) aloca coisas que não queremos! Então, pegamos essa variedade do pool com o novo tamanho, copiamos e atribuímos nosso conteúdo antigo nele e retornamos a variedade alugada. Especialmente para matrizes maiores. Eu poderia construir uma biblioteca a partir disso que parece um pouco mais detalhadamente como ajustar isso. De qualquer forma estamos bem por enquanto!

É isso. O uso é bastante trivial:

var stringBuilder = new StringBuilder();
stringBuilder.AppendLine("Hello");
stringBuilder.AppendLine("World");

Console.Write(stringBuilder.ToString();

prints:

Hello World

Duas restrições que temos em contraste com o StringBuilder "normal":

  1. Não podemos usá-lo como um campo em uma classe! Isso pode ser um problema no seu caso de uso.
  2. Não temos a notação fluente como o StringBuilder tem.

Com a versão .net você pode fazer isso: _novo _ StringBuilder().AppendLine("").AppendLine("").ToString(); que não funciona com a nossa versão. A razão é que temos uma estrutura. Claro que podemos torná-lo fluente, mas isso significa que temos muita alocação em andamento e possíveis bugs, dependendo de qual versão você usa. Por isso decidi não fazer isso.

Desempenho e alocações

A seguinte configuração:

[MemoryDiagnoser]
public  class  Benchi
{
    [Benchmark(Baseline = true)]
    public string DotNet()
    {
        var reference = new StringBuilder();
        return reference
             .AppendLine("Hello World")
             .AppendLine("Here some other text")
             .AppendLine("And again some other text as well for good measure")
             .AppendLine("You are still here?")
             .AppendLine("Hmmm.")
             .AppendLine("I wish you a very nice day and all the best.")
             .AppendLine("Sincerly Steven")
             .ToString();
     }

     [Benchmark]
     public  string  Fast()
     {
         var fast = new ValueStringBuilder();
         fast.AppendLine("Hello World");
         fast.AppendLine("Here some other text");
         fast.AppendLine("And again some other text as well for good measure");
         fast.AppendLine("You are still here?");
         fast.AppendLine("Hmmm.");
         fast.AppendLine("I wish you a very nice day and all the best.");
         fast.AppendLine("Sincerly Steven");
         return fast.ToString();
     }
}

Agora, finalmente, quão bem nossa nova implementação legal?

BenchmarkDotNet=v0.13.1, OS=Windows 10.0.19043.1586 (21H1/May2021Update) Intel Core i7-7820HQ CPU 2.90GHz (Kaby Lake), 1 CPU, 8 logical and 4 physical cores .NET SDK=6.0.201 [Host]: .NET 6.0.3 (6.0.322.12309), X64 RyuJIT DefaultJob: .NET 6.0.3 (6.0.322.12309), X64 RyuJIT

| Método | Quer dizer |     Erro |   StdDev | Razão | RatioSD | Gen 0  | Alocado |
|------- |-----------:|---------:|---------:|------:|--------:|-------:|--------:|
| DotNet |  474.1 ns  |  9.49 ns | 25.67 ns |  1.00 |    0.00 | 0.3076 | 1,288 B |
|   Fast |  265.3 ns  |  8.30 ns | 23.80 ns |  0.56 |    0.06 | 0.1090 |   456 B |

Wow quase 50% mais rápido por apenas 33% das alocações! Isso é massa! Agora podemos ver por que a equipe .NET está usando esses tipos com mais frequência dentro da própria estrutura para aumentar o desempenho.

Conclusão

Isso foi muito bom. Usamos alguns recursos avançados do C# para construir nosso próprio StringBuilder. Esta versão é muito simplista e pode precisar de muito polimento. Então: Deixe-me saber se eu deveria fazer uma biblioteca com isso no nuget. Isso significa mais otimização e funções um pouco mais convenientes adicionadas, além, é claro, de testes! Me bata com uma mensagem aqui, dê um like ou me chame no LinkedIn para isso.

Recursos

  • O código para esta postagem de blog no GitHub
  • Todos os meus exemplos para este blog encontrados aqui
  • O Value StringBuilder completo pode ser encontrado aqui.