grab
1.0.0
Esta é minha própria versão experimental e paralela do grep para que eu possa testar várias estratégias para acelerar o acesso a grandes árvores de diretórios. Em armazenamento Flash ou SSDs, você pode facilmente superar os greps comuns por um fator de 8.
Opções:
Usage: ./greppin [-rIOLlsSH] [-n <cores>] <regex> <path>
-2 -- use PCRE2 instead of PCRE
-O -- print file offset of match
-l -- do not print the matching line (Useful if you want
to see _all_ offsets; if you also print the line, only
the first match in the line counts)
-s -- single match; dont search file further after first match
(similar to grep on a binary)
-H -- use hyperscan lib for scanning
-S -- only for hyperscan: interpret pattern as string literal instead of regex
-L -- machine has low mem; half chunk-size (default 2GB)
may be used multiple times
-I -- enable highlighting of matches (useful)
-n -- Use multiple cores in parallel (omit for single core)
-r -- recurse on directory
grab usa a biblioteca pcre , então basicamente é equivalente a grep -P -a . O -P é importante, pois as expressões regulares compatíveis com Perl têm características diferentes das expressões regulares básicas.
Existem dois ramos. master e greppin . Master é o grab 'tradicional' que deve ser compilado e executado na maioria dos sistemas POSIX. greppin vem com sua própria versão otimizada e paralelizada de nftw() e readdir() , que novamente dobra a velocidade além da aceleração que o branch master já fornece. O branch greppin roda em Linux, BSD e OSX. greppin também vem com suporte para bibliotecas hyperscan da Intel que tentam explorar as instruções SIMD da CPU, se possível (AVX2, AVX512 etc.) ao compilar o padrão regex no código JIT.
Você provavelmente desejará construir o branch greppin :
$ git checkout greppin
[...]
$ cd src; make
[...]
Certifique-se de ter os pacotes da biblioteca pcre e pcre2 instalados. Em sistemas BSD você precisa gmake em vez de make . Se você deseja fazer tecnologia de ponta com o mecanismo de regex múltiplo do greppin e suporte a hyperscan, primeiro você precisa obter e construir isso:
$ git clone https://github.com/intel/hyperscan
[...]
$ cd hyperscan
$ mkdir build; cd build
$ cmake -DFAT_RUNTIME=1 -DBUILD_STATIC_AND_SHARED=1 ..
[...]
$ make
[...]
Isso criará o chamado tempo de execução gordo das bibliotecas hyperscan que contêm suporte para todas as famílias de CPU, a fim de selecionar o padrão de compilação correto em tempo de execução para maior desempenho. Assim que a compilação terminar, você cria o greppin com base nisso:
(dentro do repositório clonado)
$ cd src
$ HYPERSCAN_BUILD=/path/to/hyperscan/build make -f Makefile.hs
[...]
Isso produzirá um binário greppin que permite que a opção -H carregue um mecanismo diferente em tempo de execução, tentando explorar todos os bits de desempenho possíveis.
Você poderia vinculá-lo a bibliotecas já instaladas, mas a API adicionou recentemente algumas funções na versão 5.x e a maioria das distros vem com 4.x.
grab está usando mmap(2) e corresponde a todo o blob do arquivo sem contar novas linhas (o que grep está fazendo mesmo se não houver correspondência [como em uma revisão de código grep minha em 2012; as coisas podem ser diferentes hoje]) o que é muito mais rápido que read(2) - dividir o arquivo em pequenos pedaços e contar as novas linhas. Se disponível, o grab também usa o recurso PCRE JIT. No entanto, as acelerações só são mensuráveis em árvores de arquivos grandes ou em HDDs ou SSDs rápidos. No último caso, a aceleração pode ser drasticamente (até 3 vezes mais rápida) se corresponder recursivamente e em paralelo. Como o armazenamento é o gargalo, paralelizar a busca em HDDs não faz sentido, já que a busca leva mais tempo do que apenas fazer as coisas de forma linear.
Além disso, grab está ignorando arquivos que são pequenos demais para conter a expressão regular. Para regex maiores em uma pesquisa recursiva, isso pode pular uma boa quantidade de arquivos, mesmo sem abri-los.
Uma biblioteca pcre bastante nova é necessária; em alguns sistemas mais antigos, a compilação pode falhar devido à falta de PCRE_INFO_MINLENGTH e pcre_study() .
Os arquivos são mapeados e combinados em pedaços de 1Gig. Para arquivos maiores, os últimos 4.096 bytes (1 página) de um pedaço são sobrepostos, para que as correspondências em um limite de 1 Gig possam ser encontradas. Neste caso, você vê a correspondência duplicada (mas com o mesmo deslocamento).
Se você medir grep vs. grab , lembre-se de descartar os caches dentry e de página entre cada execução: echo 3 > /proc/sys/vm/drop_caches
Observe que grep imprimirá apenas 'correspondências de arquivo binário', se detectar arquivos binários, enquanto grab imprimirá todas as correspondências, a menos que -s seja fornecido. Portanto, para um teste de velocidade é necessário procurar uma expressão que não existe nos dados, para forçar a busca de todos os arquivos.
grab foi feito para percorrer rapidamente grandes árvores de diretórios sem indexação. O grep original possui de longe um conjunto de opções mais completo. A aceleração para uma correspondência de arquivo único é muito pequena, se é que é mensurável.
Para SSDs, a opção multicore faz sentido. Para HDDs isso não acontece, já que o cabeçote precisa ser posicionado para frente e para trás entre os threads, destruindo potencialmente o princípio da localidade e prejudicando o desempenho.
A ramificação greppin apresenta sua própria versão paralela sem bloqueio de nftw() , portanto, o tempo de inatividade dos núcleos N - 1 quando o primeiro núcleo constrói a árvore de diretórios também pode ser usado para trabalhar.
O que resta observar: o grab percorrerá os diretórios fisicamente , ou seja, não seguirá links simbólicos.
spot é a versão paralela de find . Ele oferece suporte às opções usadas com mais frequência como você as conhece. Não há muito mais para contar sobre isso, apenas experimente.
Isso mostra a aceleração em uma máquina de 4 núcleos com uma pesquisa em um SSD:
root@linux:~# echo 3 > /proc/sys/vm/drop_caches
root@linux:~# time grep -r foobardoesnotexist /source/linux
real 0m34.811s
user 0m3.710s
sys 0m10.936s
root@linux:~# echo 3 > /proc/sys/vm/drop_caches
root@linux:~# time grab -r foobardoesnotexist /source/linux
real 0m31.629s
user 0m4.984s
sys 0m8.690s
root@linux:~# echo 3 > /proc/sys/vm/drop_caches
root@linux:~# time grab -n 2 -r foobardoesnotexist /source/linux
real 0m15.203s
user 0m3.689s
sys 0m4.665s
root@linux:~# echo 3 > /proc/sys/vm/drop_caches
root@linux:~# time grab -n 4 -r foobardoesnotexist /source/linux
real 0m13.135s
user 0m4.023s
sys 0m5.581s
Com ramo greppin :
root@linux:~# echo 3 > /proc/sys/vm/drop_caches
root@linux:~# time grep -a -P -r linus /source/linux/|wc -l
16918
real 1m12.470s
user 0m49.548s
sys 0m6.162s
root@linux:~# echo 3 > /proc/sys/vm/drop_caches
root@linux:~# time greppin -n 4 -r linus /source/linux/|wc -l
16918
real 0m8.773s
user 0m4.670s
sys 0m5.837s
root@linux:~#
Sim! ~ 9s contra ~ 72s! Isso é 8x mais rápido em uma máquina SSD de 4 núcleos que o grep tradicional.
Apenas para provar que resultou na mesma saída:
root@linux:~# echo 3 > /proc/sys/vm/drop_caches
root@linux:~# greppin -n 4 -r linus /source/linux/|sort|md5sum
a1f9fe635bd22575a4cce851e79d26a0 -
root@linux:~# echo 3 > /proc/sys/vm/drop_caches
root@linux:~# grep -P -a -r linus /source/linux/|sort|md5sum
a1f9fe635bd22575a4cce851e79d26a0 -
root@linux:~#
Na comparação de núcleo único, a aceleração também depende de qual CPU o kernel realmente agenda o grep , portanto, uma captura pode ou não ser mais rápida (na maioria das vezes é). Se a carga for igual entre os testes de núcleo único, o grab verá uma aceleração se pesquisar em árvores de arquivos grandes. Em configurações multi-core, o grab pode se beneficiar do corse.
O projeto pode ser encontrado aqui.
A principal aceleração que está dentro de suas tabelas de benchmark decorre do fato de que ripgrep ignora muitos arquivos (principalmente dotfiles) quando invocado sem opções especiais, além de tratar arquivos binários como um destino de correspondência única (semelhante a grep ). Para obter resultados comparáveis, lembre-se de (4 é o número de núcleos):
echo 3 > /proc/sys/vm/drop_caches entre cada execução-j 4 -a --no-unicode --no-pcre2-unicode -uuu --mmap a ripgrep , pois por padrão ele corresponderá ao Unicode, que é 3 vezes mais lento, e tentará compensar a perda de velocidade ignorando 'ignorar' arquivos baseados em. -e é mais rápido que -P , então é melhor escolher -e , mas não é tão poderoso quanto um PCRE/dev/null para evitar efeitos baseados em tty-H -n 4 ao greppin se desejar melhor desempenho. -H é compatível com PCRE com apenas algumas exceções (de acordo com o documento do hyperscan)setfattr -n user.pax.flags -v "m" /path/to/binary se você executar em sistemas grsec e precisar de mapeamentos rwx JIT Então vá em frente e verifique os horários. Mesmo quando não está usando o hyperscan, greppin é significativamente mais rápido que rg ao usar expressões PCRE2 (PCRE2 vs. PCRE2) e ainda mais rápido ao comparar as expressões mais rápidas (-e vs. hyperscan).
