Cases de Melhoria de Performance

NÃO utilize RegEx no caminho crítico

Expressões regulares são fantásticas. Entretanto, precisam ser utilizadas com moderação pois podem impactar de forma perceptível a performance.

A expressão regular do código abaixo (criado para esse post) estava no caminho crítico de execução do sistema de um cliente.

public static bool VersionWithRegex(string strToFind, string input)
{
    var regex = new Regex($".*({strToFind})[/.].*", RegexOptions.IgnoreCase);
    return regex.Match(input).Success;
}

Basicamente, essa expressão verifica se uma string, seguida por um “.” ou por uma “/” estão contidos em uma outra string, desconsiderando minúsculos e maiúsculos.

Para que possamos apenas ter “um cheiro” do peso de execução dessa expressão regular, criei um teste simples.

static void Main(string[] args)
{
    Func<string, string, bool> sut = VersionWithRegex;

    var g0 = GC.CollectionCount(0);
    var g1 = GC.CollectionCount(1);
    var g2 = GC.CollectionCount(2);

    var sw = new Stopwatch();
    sw.Start();


    for (int i = 0; i < 100_000; i++)
    {
        if (!sut("abc", "xptoABC.abc"))
            throw new Exception();

        if (!sut("abc", "xptoAbC/abc"))
            throw new Exception();

        if (!sut("abc", "xptoABC."))
            throw new Exception();

        if (!sut("abc", "xptoAbC/"))
            throw new Exception();

        if (!sut("abc", "ABC."))
            throw new Exception();

        if (!sut("abc", "AbC/"))
            throw new Exception();

        if (!sut("abc", "xptoabC.xpto"))
            throw new Exception();

        if (!sut("abc", "xptoabC/xpto"))
            throw new Exception();

        if (sut("abcd", "xptoabC/xpto"))
            throw new Exception();

        if (sut("abc/", "xptoabC/xpto"))
            throw new Exception();
    }

    Console.WriteLine($"Total time: {sw.ElapsedMilliseconds}ms.");
    Console.WriteLine($"Gen0: {GC.CollectionCount(0) - g0}.");
    Console.WriteLine($"Gen1: {GC.CollectionCount(1) - g1}.");
    Console.WriteLine($"Gen2: {GC.CollectionCount(2) - g2}.");
}

Resultado:

Pouco mais de nove segundos para verificar mais de 1_000_000 de strings não parece um tempo ruim. Entretanto, como sempre digo, 10s, para um computador, é muito tempo. Vejamos se conseguimos melhorar.

Primeira modificação: adeus Regex

Minha primeira proposta foi remover o Regex. Afinal, o teste não seria tão custo de implementar.

public static class Attempt1
{
    public static bool VersionWithoutRegex(string strToFind, string input)
    {

        return
            input.IndexOf($"{strToFind}/", StringComparison.InvariantCultureIgnoreCase) != -1 ||
            input.IndexOf($"{strToFind}.", StringComparison.InvariantCultureIgnoreCase) != -1;
    }
}

Resultado:

Surpreendente, não? O código acima é mais simples (na minha opnião) e ~22 vezes mais rápido. Aliás, interessante observar o número de coletas que o Regex provoca.

Essa performance já seria suficiente para o cliente. Mas, apenas por curiosidade, será que conseguimos melhorar?

Segunda modificação: Adeus GC

Sabemos que o GC impacta a performance da aplicação. Então, vamos ver se podemos ter algum ganho não alocando memória.

public static bool VersionWithoutRegex(string strToFind, string input) 
    => input.Contains(strToFind, '.') || 
       input.Contains(strToFind, '/');

private static bool Contains(this string input, string strToFind, char suffix)
{
    var limit = input.Length - (strToFind.Length + 1);
    var c0 = char.ToUpperInvariant(strToFind[0]);

    for (int i = 0; i <= limit; i++)
    {
        if (char.ToUpperInvariant(input[i]) == c0)
        {
            bool success = true;

            for (int j = 1; j < strToFind.Length; j++)
            {
                if (char.ToUpperInvariant(input[i + j]) != char.ToUpperInvariant(strToFind[j]))
                {
                    success = false;
                    break;
                }
            }

            if (success && char.ToUpperInvariant(input[i + strToFind.Length]) == char.ToUpperInvariant(suffix))
            {
                return true;
            }
        }
    }

    return false;
}

Observe que, definitivamente, abraçamos alguma complexidade nesse código. Vejamos o resultado:

Terceira modifição: Comparando de forma mais inteligente

Reparei que estava usando uma “comparação” pesada demais para os caracteres, por isso, resolvi “aliviar”

public static bool VersionWithoutRegex(string strToFind, string input)
{

    return
        (input.Contains(strToFind, '.') || input.Contains(strToFind, '/'));
}
private static bool Contains(this string input, string strToFind, char suffix)
{
    var limit = input.Length - (strToFind.Length + 1);

    for (int i = 0; i <= limit; i++)
    {
        if (strToFind[0].EqualsIgnoringCase(input[i]))
        {
            bool success = true;

            for (int j = 1; j < strToFind.Length; j++)
            {
                if (input[i + j].EqualsIgnoringCase(strToFind[j]))
                {
                    success = false;
                    break;
                }
            }

            if (success && input[i + strToFind.Length].EqualsIgnoringCase(suffix))
            {
                return true;
            }
        }
    }

    return false;
}

[MethodImpl(MethodImplOptions.AggressiveInlining)]
private static bool EqualsIgnoringCase(this char c1, char c2)
{
    if (!char.IsLetter(c1))
    {
        return c1 == c2;
    }

    if (char.IsLower(c1))
    {
        return char.IsLower(c2) ? c1 == c2 : c1 == char.ToLowerInvariant(c2);
    }

    return char.IsUpper(c2) ? c1 == c2 : c1 == char.ToUpperInvariant(c2);
}

Resultado:

Quarta modifição: Comparando de forma AINDA mais inteligente

Minha abordagem anterior para comparar caracteres se mostrou mais inteligente (e mais performática). Vejamos outra ainda mais efetiva:

public static bool VersionWithoutRegex(string strToFind, string input)
{

    return
        (input.Contains(strToFind, '.') || input.Contains(strToFind, '/'));
}
private static bool Contains(this string input, string strToFind, char suffix)
{
    var limit = input.Length - (strToFind.Length + 1);

    for (int i = 0; i <= limit; i++)
    {
        if (strToFind[0].EqualsIgnoringCase(input[i]))
        {
            bool success = true;
            for (int j = 1; j < strToFind.Length; j++)
            {
                if (input[i + j].EqualsIgnoringCase(strToFind[j]))
                {
                    success = false;
                    break;
                }
            }

            if (success && input[i + strToFind.Length].EqualsIgnoringCase(suffix))
            {
                return true;
            }
        }
    }

    return false;
}

[MethodImpl(MethodImplOptions.AggressiveInlining)]
private static bool EqualsIgnoringCase(this char c1, char c2)
{
    return (
        (c1 - 'a') == (c2 - 'a') ||
        (c1 - 'a') == (c2 - 'A') ||
        (c1 - 'A') == (c2 - 'a') ||
        (c1 - 'A') == (c2 - 'A')
        );
}

Resultado:

Quinta (última) modificação: Adeus processamento em duplicidade

Percebi que meu código de “contido” rodava duas vezes – uma para cada sufixo. Vamos resolver isso.

public static bool VersionWithoutRegex(string strToFind, string input)
{

    return
        (input.Contains(strToFind, '.', '/'));
}
private static bool Contains(this string input, string strToFind, char suffix1, char suffix2)
{
    var limit = input.Length - (strToFind.Length + 1);

    for (int i = 0; i <= limit; i++)
    {
        if (strToFind[0].EqualsIgnoringCase(input[i]))
        {
            bool success = true;
            for (int j = 1; j < strToFind.Length; j++)
            {
                if (input[i + j].EqualsIgnoringCase(strToFind[j]))
                {
                    success = false;
                    break;
                }
            }

            if (success && input[i + strToFind.Length].EqualsIgnoringCase(suffix1) || input[i + strToFind.Length].EqualsIgnoringCase(suffix2))
            {
                return true;
            }
        }
    }

    return false;
}

[MethodImpl(MethodImplOptions.AggressiveInlining)]
private static bool EqualsIgnoringCase(this char c1, char c2)
{
    return (
        (c1 - 'a') == (c2 - 'a') ||
        (c1 - 'a') == (c2 - 'A') ||
        (c1 - 'A') == (c2 - 'a') ||
        (c1 - 'A') == (c2 - 'A')
        );
}

Resultado:

22ms!

Comparando a performance de forma mais “profissional”

Nosso código, que originalmente consumia quase 10 segundos, agora performa em ~22ms. Vejamos uma análise mais qualificada com o BenchmarkDotNet.

Conclusão

Performance é uma feature. Escrever código de boa performance é um hábito. Código que performa melhor pode, eventualmente, ficar mais complexo. Entretanto, dependendo da demanda, essa complexidade é compensada.

O primeiro código desse post, que está em produção hoje em uma grande empresa, provavelmente é o mais simples. Também é ~440x mais lento que o último código.

No próximo dia 29, irei falar, de forma gratuita, para o Canal.NET sobre como escrever código com performance ótima.  Faça sua inscrição.

Mais posts da série Cases de Melhoria de Performance

11 Comentários
  1. Antonio Maniero

    Falei disso na minha palestra no MVPConf, Quase sempre RegEx é criminoso pra performance. E sempre ótimo artigo! Pena não ter levado todo esse conhecimento pra gente lá no evento, quem sabe ano que vem.

    1. Alexandre Silva

      Eu assisti sua palestra, muito show, e exatamente hoje tive um problema com regex, o pessoal do grupo DotNet Brasil (telegram) me passou esse link do Elemar, cara, era tudo o que eu precisava para resolver meu problema…

  2. Murilo Gibim

    O método do último exemplo @EqualsIgnoringCase poderia ser simplificado (talvez ganhando um pouco de performance nos casos em que o case ajuda) conforme abaixo, se entendi corretamente.

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    private static bool EqualsIgnoringCase(this char c1, char c2)
    {
        return c1 == c2 ||
            (c1 - 'a') == (c2 - 'A') ||
            (c1 - 'A') == (c2 - 'a');
    }
    
  3. Ricardo CF

    Artigo fantástico, abre nossos olhos!
    Uma curiosidade: Quanto ao consumo de memória, tem a mesma relevância? Ou a diferença de consumo de memória não foi citada pq não chega a ser relevante?

    1. Elemar Júnior

      O número de acionamentos do GC indica alocação de memória. Entretanto, não me parece ser algo definitivo ou impactante no longo prazo.

      🙂

  4. Róger Formagio Lopes

    Muito bom Elemar! Esta publicação me fez repensar o uso de Regex em caminhos críticos. Muito obrigado.

  5. Ahmed Alejo

    Primeiramente, se a tua expressão regular pode ser substituído por um simples ”IndexOf” então o teu Regex apenas deveria servir de documentação (O exemplo é trivial)

    Otimizando uma automata na mão sempre é mais rápido mas por sua vez lenta (imagina ótima mais isto depois por um terceiro) requere Teste unitários a mais.

    Segundo, poderia ter sugerido a ré-utilização da instância do Regex também como uma versão “Compiled” do mesmo.

    Terceiramente, tente utilizar BenchmarkDotNet para seus micro-análise o chamado “micro-profiling” ajuda a padronizar os seus conclusões.

    Belo post na série GC

  6. Jonatan

    Bom eu consideraria vários fatores sobre o assunto:

    1 – Legibilidade do código foi extremamente comprometida no processo, apesar de mais performático, haja cognição pra tentar entender o que foi feito. Lembre-se, pessoas são e sempre serão o componente mais caro de qualquer negócio.
    2 – A esmagadora parte dos projetos são feitas por times sejam eles grandes/médios/pequenos, provavelmente outro desenvolvedor vai olhar seu código e pensar “uma expressão regular resolveria”. A probabilidade desse trecho voltar a ser o que era é gigantesca.
    3 – Escalas em que isso faz sentido, dificilmente serão alcançadas, a esmagadora parte dos sistemas em nosso país são pequenos/médios. Brasil só aparece na 32ª posição em sites mais acessados do mundo.
    4 – 10 segundos para um computador realmente é uma eternidade, para um ser humano ao longo do dia não significa nada, fundamentação baseada apenas em um ponto de vista são geralmente frágeis. Já vi casos de queries de checkout “select 1 from dual” consumirem 1 dia de CPU no total semanal. Sabe qual era o impacto disso no software na escala que operava ? ZERO.
    5- Não se resolve problemas de performance antes que eles aconteçam.

    É indiscutível que praticar performance como requisito não funcional, faz bem pra saúde, agora vale ressaltar que nem tudo pode ser feito em nome de performance. Criar monstrengos como esses, podem gerar mais dor de cabeça do que resultados.

    1. Elemar Júnior

      Olá Jonatan. Obrigado por comentar.

      Deixa eu te apresentar alguns contra-pontos.

      Para o ponto 1:
      * A expressão regular, utilizada no exemplo, foi retirada de um cenário de produção. Você realmente a acha clara? Veja que ela está mal-escrita. Além disso, no time que dava manutenção nesse código ninguém sabia dizer exatamente qual o propósito dela (pessoas não escrevem Regex todos os dias, Jonatan).
      * Quanto pessoas serem a parte mais cara do processo, você está errado, amigo. O código que inspirou esse post vem de um e-commerce de alto volume. O custo mais caro para eles, era o custo de não vender. Aliás, esse cenário passa longe de incomum. Tenho outro cliente que justificou performance financeira negativa em um trimestre com problemas de performance de software nas vendas de loja.

      Para o ponto 2:
      * Você está certo. Infelizmente, no Brasil, temos um “ranço” que associa documentação com perda de agilidade. Escrevemos sistemas como bons “amadores remunerados”. Um pouco de documentação justificando esta escolha e a implementação de um teste de validação ajudaria as pessoas a entender o propósito.
      RECOMENDAÇÃO: Veja o código-fonte do Roslyn e veja como um padrão de comentário com “PERF:” foi suficiente para resolver o problema que está indicando.

      Para o número 3:
      * Discordo, novamente. Veja que menciono caminho crítico no título desse post. Há uma grande instituição financeira que executa processos de importação em Batch diariamente que demandam processamento em C#. Você ficaria surpreso com o impacto que não cumprir uma “janela de processamento” tem naquele negócio.

      Para o número 4:
      * Você está certo.

      Para o número 5:
      * É uma forma de pensar. Mas, podemos concordar em discordar. Certo? É função de arquitetura mapear os riscos de cada implementação e impedir que prejuízos ao negócio ocorram.

      Para o fechamento:
      Concordamos: RESULTADOS em primeiro lugar, sempre! Embora, a primeira melhoria passe longe de ser “monstrengo” e acho até mais clara que a Regex, entendo e concordo com a observação para os últimos códigos. Importante ressaltar, que eles estão aqui por didática.

  7. Fabio Rodrigues e Souza

    Boa!
    Eu só acrescentaria uma informação:
    Não crie a regex sempre em cada chamada, use uma regex compilada, isso reduziria drasticamente o rastro da regex no desempenho.
    https://docs.microsoft.com/pt-br/dotnet/standard/base-types/best-practices

    1. Elemar Júnior

      Perceba que no contexto no post isso não seria possível.

Deixe uma resposta

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *