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

[tweet]Performance é uma feature. Escrever código de boa performance é um hábito.[/tweet] 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.

Compartilhe este insight:

14 respostas

  1. 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. 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. 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. 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. 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. Muito bom Elemar! Esta publicação me fez repensar o uso de Regex em caminhos críticos. Muito obrigado.

  5. 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. 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. 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.

      1. Olá Jonatan. Tenho algumas ressalvas sobre oque você escreveu no item 4: “10 segundos para um computador realmente é uma eternidade, para um ser humano ao longo do dia não significa nada”.

        Um pequeno exemplo:
        Imagine um cenário de operação crítica, como por exemplo um sistema de checkout de supermercado (existem vários outros cenários semelhantes). Onde a cada produto lançado, o atendente tenha que aguardar 10 segundos para o próximo lançamento, segurando o produto na mão.

        Faça um cálculo aproximado e tente levantar a quantidade de tempo perdido ao longo de um dia de trabalho. 10 segundos entre cada bipe do leitor de código de barras, e para uma simples estimativa, multiplique por 40 uns checkouts em um estabelecimento de grande porte.

        Sem falar no acúmulo de pessoas na fila do atendimento e o cansaço físico e mental deste atendente, tendo que esperar pelo processamento do sistema por intermináveis 10 segundos entre um lançamento e outro.

        Indo um pouco além, acho até que a sua afirmação: “fundamentação baseada apenas em um ponto de vista são geralmente frágeis” contradiz um pouco o que você escreveu (“10 segundos para um computador realmente é uma eternidade, para um ser humano ao longo do dia não significa nada”). Software é algo extremamente complexo, e basicamente tudo o que você escreve ou explica para alguém deveria estar devidamente contextualizado. Pois sempre poderá haver algum cenário que invalida parcial ou totalmente a sua afirmação.

  7. Melhorando a performance do EqualsIgnoringCase

    private const char space = (char)32;
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static bool EqualsIgnoringCase(this char c1, char c2)
    {
    return (
    c1 == c2 ||
    c1 == (c2 + space) ||
    c1 == (c2 – space)
    );
    }

Deixe um comentário

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

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:

Mais preocupante que o posicionamento do presidente é sua falta de constância. Há dois dias, uma medida provisória proposta pelo...
No meu tempo absolutamente livre – quando não estou trabalhando, estudando ou aproveitando com a família – tenho jogado Mario...
Superficialmente, direito e privilégio são conceitos que se aproximam e, eventualmente, se confundem. Mas, com um pouco de cuidado, ficam...
[tweet]Transformação Digital é sobre como o negócio será impactado (transformado) pela adoção de recursos digitais.[/tweet] Portanto, começando uma nova série...
If you are interested in performance, you need to know more about CUDA. From the official website: CUDA® is a...
Um servidor de identidades é um artefato de sofware que centraliza os dados de usuários, bem como o processo para...
× Precisa de ajuda?