Eclesiastes

Ícone

Sobre o que é este blog? O.o

PCRE Performance

NOTA: O texto abaixo é uma tradução minha da PCRE Man Pages – PCREPERFORM(3).

Dois aspectos de performance são discutivos abaixo: memória utilizada e tempo de processamento. O modo como você faz seu padrão com uma expressão regular pode afetar ambos.

Memória utilizada

Padrões são compiladas pela PCRE para razoável byte code, então o mais simples padrão não usa muita memória. Contudo, há um caso onde memória usada pode ser inexperavelmente grande. Quando um subpadrão entre parênteses tem um quantificador indicando como o mínimo maior que 1 e/ou uma quantidade máxima limitada, todo o subpadrão é repetido no código compilado. Por exemplo, o padrão

(abc|def){2,4}

é compilado com se fosse

(abc|def)(abc|def)((abc|def)(abc|def)?)?

(Tecnicamente à parte: É feito desta maneira de modo que cada ponto de backtrack dentro de cada uma das repetições possa independentemente ser mantido.)

Para aquelas expressão regulares cuja quantificadores usa somente pequenos números, isto não é um problema. Contudo, se o número for grande, e particularmente se cada repetição for aninhada, a memória usada pode tornar embaraçosa. Por exemplo, um padrão muito simples

((ab){1,1000}c){1,3}

utiliza 51K bytes quando compilado. Quando PCRE é compilada com o tamanho do ponteiro interno padrão de 2 bytes, o tamanho limite de um padrão compilado é 64K, e isto é alcançado com o padrão acima se a repetição externa é acrescentada de 3 para 4. PCRE pode ser compilada para usar ponteiros maiores e assim manusear padrões compilados maiores, mas é melhor tentar reescrever seu padrão para usar menos memória se você puder.

Um caminho para redução de uso de memória para cada padrão é fazer uso das “subrotinas” da PCRE. Reescrevendo o padrão acima como

((ab)(?2){0,999}c)(?1){0,2}

reduz a memória requerida para 18K, e realmente permanece abaixo de 20K até mesmo com a repetição externa acrescida para 100. Contudo, este padrão não será exatamente equivalente, porque as chamadas “subrotinas” são tratadas como grupos atômicos que não faz backtracking se uma subseqüente combinação falhar. Portanto, PCRE não faz este tipo de reescrita automaticamente. Além disso, há perceptível perda de velocidade quando executado o padrão modificado. Apesar disso, se o grupo atômico não for um problema e a perda de velocidade for aceitável, este tipo de reescrita irá permitir você processar padrões que PCRE de outra forma não faça.

Tempo de processamento

Certos itens na expressão regular são processados mais eficientemente que outros. É mais eficiente usar uma classe de caracteres como [aeiou] que um conjuto de simples caracteres alternativos como (a|e|i|o|u). No geral, a simples construção que provê o comportamento desejado é usualmente o mais eficiente. Jeffrey Friedl´s book contém várias discussões proveitosas sobre expressões regulares otimizadas para eficientes performances. Este documento contém muitas observações sobre PCRE.

Usar caracteres de propriedades Unicode (o \p, \P e \X) é lento, porque PCRE tem que varrer a estrutura que contém informações sobre 15.000 caracteres sempre que ele necessitar de um caractere de propriedade. Se você pode encontrar um padrão alternativo que não use caracteres de propriedade, será provavelmente mais rápido.

Quando um padrão inicia com .* sem parênteses, ou em parênteses que não faz backreference, e a opção PCRE_DOTALL é definida, o padrão é implicitamente ancorada pela PCRE, desde que possa combinar somente no começo da string. Contudo, se PCRE_DOTALL não é definida, PCRE não pode fazer esta otimização, porque o metacaractere . não combina então uma newline, e se a string contém newlines, o padrão pode combinar imediatamente de um caractere seguinte dele em vez de muitos inícios. Por exemplo, o padrão

.*second

combina a string “first\nand second” (onde \n sendo uma newline), com a combinação iniciando no sétimo caractere. Nesta ordem para fazer isto, PCRE tenta refazer a combinação começando depois de todo newline na string.

Se você está usando um padrão com strings que não contém newlines, a melhor performance é obtida usando PCRE_DOTALL, ou iniciando o padrão com ^.* ou ^.*? para indicar explicitamente que é âncorada. Que salva PCRE de ter que varrer ao longo da string verificando por um newline para reiniciar de lá.

Tome cuidado com padrões que contém indefinidas repetições aninhadas. Aqueles que podem tomar um longo tempo para percorrer quando aplicado a uma string que não combina. Considere o pedaço do padrão

^(a+)*

Isto pode combinar “aaaa” em 16 formas diferentes, e isso aumentar muito rapidamente com uma string maior. (O * pode combinar 0, 1, 2, 3 ou 4 vezes, e para cada um desses casos outros 0 ou 4, e + pode combinar diferentes números de vezes.) Quando o restante do padrão for tal que inteiro indo falhar, PCRE tem um princípio de tentar toda variação possível, e isto pode tomar extremamente muito tempo, até mesmo para relativamente pequenas strings.

Uma otimização capturando igual do mais simples caso como

(a+)*b

onde um caractere literal seguido. Antes de embarcar no padrão de procedimento de combinação, PCRE verifica que há um “b” posterior na string, e se não há, ele falha a combinação imediatamente. Contudo, quando não há literal seguido esta otimização não é usada. Você pode ver a diferença em comparação com o comportado de

(a+)*\d

com o padrão acima. O antigo dado como falho quase instantaneamente quando aplicado para toda linha de caracteres “a”, enquanto que o último toma um apreciável tempo com string maiores que 20 caracteres.

Em muitos casos, a solução para este tipo de questão de perfomance é o uso de grupo atômico ou quantificador possessivo.

Referência

Arquivado em:PCRE

Deixe uma resposta

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s

%d blogueiros gostam disto: