Tempo de execução estranho para o grep recursivo

Question

Estou em uma máquina Linux Ubuntu, usando um grande número de arquivos. Alguém pode explicar esses horários?

>time grep -nIr acct_margin *
[... 3 results ...]
real    0m0.555s
user    0m0.400s
sys     0m0.150s

Caso insensitivo:

>time grep -niIr acct_margin *
[... 3 results ...]

real    0m45.739s
user    0m45.300s
sys     0m0.240s

Com um operador "ou" no regex:

>time grep -nIr "acct_margin\|MARGIN_TABLE" *
[... 5 results ...]

real    0m15.892s
user    0m15.540s
sys     0m0.260s

Caso insensitivo:

>time grep -niIr "acct_margin\|MARGIN_TABLE" *
[... 5 results ...]

real    0m52.433s
user    0m52.050s
sys     0m0.200s

Eu executei os comandos o suficiente para que os arquivos sejam armazenados em cache ( htop confirma o espaço de memória RAM aberto).

A insensibilidade a casos incorre em um fator de quase 100 vezes mais lento? Isso deve ser um aumento constante de tempo na quantidade de processamento. Operador de tubulação um fator de 30x mais lento? Eu acho que não posso argumentar com os resultados, mas estou apenas curioso sobre como alguém escreve grep de tal forma que ele funciona dessa maneira, e se há alguma maneira de contornar isso. Grep de alta performance, alguém?

    

Answer 1

Case insensitivity incurs a factor of nearly 100x slower? That should be a constant time increase in amount of processing.

Bem, não. Para começar, existem 1024 strings diferentes que correspondem a acct_margin com a opção -i .

A correspondência acct_margin é sensível a maiúsculas e minúsculas; se o caractere atual não for a , pule. Com a dobra de maiúsculas e minúsculas, você precisa verificar se o caractere atual é um um ou um A . Isso não é apenas dois testes, você também tem muito mais jogos que você não pode pular diretamente. ¹ Ele fica mais difícil para caracteres não-ASCII.

No entanto, grep -i não deve ser tão lento. Isso parece ser uma implementação incorreta da dobra de maiúsculas e minúsculas quando são esperados caracteres multi-byte (mesmo que nenhum esteja presente nos arquivos).

Possíveis soluções alternativas

1. Não use a opção -i e construa a expressão regular sem distinção entre maiúsculas e minúsculas à mão.

2. Se os arquivos contiverem apenas caracteres ASCII, defina temporariamente o identificador de codificação da variável de ambiente LANG para ISO-8859-1 (também conhecido como Europa Ocidental, Latim -1 ou Página de Código 819).

3. Selecione um dos tipos de expressão regular não padrão ( --fixed-strings , --extended-regexp ou --perl-regexp ).

4. Se os arquivos contiverem apenas caracteres ASCII e dobrar em maiúsculas a saída for admissível, não use a opção -i e caracteres de divisão de canal para grep.

Configuração de teste

Eu criei um arquivo de 500 MB de bytes pseudo-aleatórios codificados em Base64 em meu computador ² , eliminei todos os processos intensivos em CPU ou memória e comparei os tempos de execução das soluções alternativas acima para um grep ou grep -i simples.

Alimentei o arquivo de entrada para grep e tr usando um redirecionador e descartei a saída para eliminar possíveis fontes de bias.

Eu corri todos os comandos várias vezes; os tempos de execução foram estáveis (variação máxima de ± 0,01s).

Bechmarks

$ # Make time output only elapsed time:
$ TIME="  %es"
$ # C create 500MB file of 76 printable ASCII characters per line:
$ < /dev/urandom base64 | head -c 500MB > file
$ # Verify that current character encoding is UTF8:
$ echo "  $LANG"
  en_US.UTF-8
# Benchmark of case-sensitive 'grep' for comparison:
$ < file time grep test > /dev/null
  0.45s
$ # Benchmark of case-sensitive 'grep --perl-regexp' for comparison:
$ < file time grep -P test > /dev/null
  0.82s
$ # Benchmark of case-insensitive 'grep' for comparison:
$ < file time grep -i test > /dev/null
  21.08s
$ # Workaround 1:
$ < file time grep [Tt][Ee][Ss][Tt] > /dev/null
  1.53s
$ # Workaround 2:
$ (LANG=en_US.ISO-8859-1; < file time grep -i test > /dev/null)
  1.53s
$ # Workaround 3:
$ < file time grep -Pi test > /dev/null
  1.33s
$ # Workarounds 2 and 3 combined:
$ (LANG=en_US.ISO-8859-1; < file time grep -Pi test > /dev/null)
  1.25s
$ # Workarounds 4:
$ < file time tr [A-Z] [a-z] | grep test > /dev/null
  0.46s

Não houve diferença mensurável entre o padrão e os outros tipos de expressão regular não padrão.

Não houve diferença mensurável entre a última versão do grep dos repositórios padrão do Ubuntu (2.10) e a última versão estável do GNU grep (2.14).

Conclusões

• A solução alternativa 1 e 2 resulta na mesma aceleração.

  Isso sugere que a solução alternativa 1 é semelhante a como a dobra de maiúsculas do grep funciona quando nenhum caractere multi-byte é previsto.

• Embora --perl-regexp seja muito mais lento para correspondência com distinção entre maiúsculas e minúsculas, é magnitudes mais rápidas para correspondência de maiúsculas e minúsculas.

• --perl-regexp se torna ainda mais rápido se nenhum caractere de múltiplos bytes for previsto.

• À custa de dobrar a saída, a solução alternativa 4 pode ser tão rápida quanto a diferenciação entre maiúsculas e minúsculas.

_{¹ Não estou sugerindo que é assim que o grep funciona internamente. Isso é importante para ilustrar por que a correspondência sem distinção entre maiúsculas e minúsculas é mais complicada.}

_{² Intel Core i5-3570K, RAM de 16 GiB, Ubuntu 12.10}