ugrep indexer
v1.0.0
O utilitário ugrep-indexer indexa arquivos recursivamente para acelerar o grepping recursivo.
Além disso, o conteúdo dos arquivos compactados e compactados é indexado quando especificado com uma opção de linha de comando. Isso elimina a busca neles quando nenhum de seus conteúdos corresponde aos padrões especificados.
ugrep é um pesquisador rápido de arquivos compatível com grep que suporta pesquisa baseada em índice. A pesquisa baseada em índice pode ser significativamente mais rápida em sistemas de arquivos lentos e quando o cache do sistema de arquivos é ineficaz: se o sistema de arquivos em uma unidade pesquisada não estiver armazenado em cache na RAM, ou seja, estiver "frio", a indexação acelerará a pesquisa. Ele pesquisa apenas os arquivos que podem corresponder a um padrão regex especificado usando um índice do arquivo. Este índice permite uma verificação rápida se existe uma possível correspondência, evitando assim a busca em todos os arquivos.
A pesquisa baseada em indexação com ugrep é segura e nunca ignora arquivos atualizados que agora podem corresponder. Se quaisquer arquivos e diretórios forem adicionados ou alterados após a indexação, a pesquisa sempre pesquisará essas adições e alterações feitas no sistema de arquivos, comparando os registros de data e hora do arquivo e do diretório com o registro de data e hora da indexação.
Quando muitos arquivos são adicionados ou alterados após a indexação, podemos querer reindexar para atualizar os índices. A reindexação é incremental, portanto não levará tanto tempo quanto o processo de indexação inicial.
Um exemplo típico, mas pequeno, de pesquisa baseada em índice, por exemplo, no repositório ugrep v3.12.6 colocado em uma unidade separada:
$ cd drive/ugrep
$ ugrep-indexer -I
12247077 bytes scanned and indexed with 19% noise on average
1317 files indexed in 28 directories
28 new directories indexed
1317 new files indexed
0 modified files indexed
0 deleted files removed from indexes
128 binary files ignored with --ignore-binary
0 symbolic links skipped
0 devices skipped
5605227 bytes indexing storage increase at 4256 bytes/file
A pesquisa normal em um sistema de arquivos frio sem indexação leva 1,02 segundos após desmontar a drive e montá-la novamente para limpar o cache do FS e registrar o efeito da indexação:
$ ugrep -I -l 'std::chrono' --stats
src/ugrep.cpp
Searched 1317 files in 28 directories in 1.02 seconds with 8 threads: 1 matching (0.07593%)
Ripgrep 13.0.0 leva mais tempo com 1,18 segundos para a mesma pesquisa fria (ripgrep ignora arquivos binários por padrão, então a opção -I não é especificada):
$ time rg -l 'std::chrono'
src/ugrep.cpp
1.18 real 0.01 user 0.06 sys
Por outro lado, com a indexação, a pesquisa em um sistema de arquivos frio leva apenas 0,0487 segundos com o ugrep, que é 21 vezes mais rápido, após desmontar drive e montá-la novamente para limpar o cache do FS e registrar o efeito da indexação:
$ ugrep --index -I -l 'std::chrono' --stats
src/ugrep.cpp
Searched 1317 files in 28 directories in 0.0487 seconds with 8 threads: 1 matching (0.07593%)
Skipped 1316 of 1317 files with non-matching indexes
Sempre há alguma variação no tempo decorrido, sendo 0,0487 segundos o melhor tempo de quatro execuções de pesquisa que produziram um intervalo de tempo de pesquisa de 0,0487 (aceleração de 21x) a 0,0983 segundos (aceleração de 10x).
O aumento de velocidade pode ser significativamente maior em geral em comparação com esta pequena demonstração, dependendo de vários fatores, do tamanho dos arquivos indexados, da velocidade de leitura do sistema de arquivos e assumindo que a maioria dos arquivos está fria.
O algoritmo de indexação que projetei é provavelmente monotônico : uma maior precisão garante um maior desempenho de pesquisa, reduzindo a taxa de falsos positivos, mas também aumenta a sobrecarga de armazenamento do índice. Da mesma forma, uma precisão menor diminui o desempenho da pesquisa, mas também reduz a sobrecarga de armazenamento do índice. Portanto, chamei meu indexador de indexador monotônico .
Se o espaço de armazenamento de arquivos for escasso, podemos reduzir a sobrecarga de armazenamento do índice especificando uma precisão de indexação mais baixa.
Indexar o exemplo acima com nível 0 (opção -0 ) reduz a sobrecarga de armazenamento de indexação em 8,6 vezes, de 4.256 bytes por arquivo para míseros 490 bytes por arquivo:
12247077 bytes scanned and indexed with 42% noise on average
1317 files indexed in 28 directories
0 new directories indexed
1317 new files indexed
0 modified files indexed
0 deleted files removed from indexes
128 binary files ignored with --ignore-binary
0 symbolic links skipped
0 devices skipped
646123 bytes indexing storage increase at 490 bytes/file
A pesquisa indexada ainda é muito mais rápida em 12x do que a não indexada neste exemplo, com 16 arquivos realmente pesquisados (15 falsos positivos):
Searched 1317 files in 28 directories in 0.0722 seconds with 8 threads: 1 matching (0.07593%)
Skipped 1301 of 1317 files with non-matching indexes
Os padrões Regex que são mais complexos do que este exemplo podem ter uma taxa de falsos positivos mais alta naturalmente, que é a taxa de arquivos considerados possivelmente correspondentes, quando não o são. Uma taxa de falsos positivos mais alta pode reduzir a velocidade de pesquisa quando a taxa for grande o suficiente para causar impacto.
A tabela a seguir mostra como a precisão da indexação afeta o armazenamento da indexação e o ruído médio por arquivo indexado. As colunas mais à direita mostram a velocidade de pesquisa e a taxa de falsos positivos para ugrep --index -I -l 'std::chrono' :
| conta. | armazenamento de índice (KB) | ruído médio | falsos positivos | tempo(s) de pesquisa |
|---|---|---|---|---|
-0 | 631 | 42% | 15 | 0,0722 |
-1 | 1276 | 39% | 1 | 0,0506 |
-2 | 1576 | 36% | 0 | 0,0487 |
-3 | 2692 | 31% | 0 | infeliz |
-4 | 2966 | 28% | 0 | infeliz |
-5 | 4953 | 23% | 0 | infeliz |
-6 | 5474 | 19% | 0 | infeliz |
-7 | 9513 | 15% | 0 | infeliz |
-8 | 10889 | 11% | 0 | infeliz |
-9 | 13388 | 7% | 0 | infeliz |
Se a regex especificada corresponder a muitos outros padrões possíveis, por exemplo, com a pesquisa ugrep --index -I -l '(todo|TODO)[: ]' , então poderemos observar uma taxa maior de falsos positivos entre os 1317 arquivos pesquisados, resultando em tempos de pesquisa um pouco mais longos:
| conta. | falsos positivos | tempo(s) de pesquisa |
|---|---|---|
-0 | 189 | 0,292 |
-1 | 69 | 0,122 |
-2 | 43 | 0,103 |
-3 | 19 | 0,101 |
-4 | 16 | 0,097 |
-5 | 2 | 0,096 |
-6 | 1 | infeliz |
-7 | 0 | infeliz |
-8 | 0 | infeliz |
-9 | 0 | infeliz |
Precisão -4 é o padrão (de -5 anteriormente em versões mais antigas), que tende a funcionar muito bem para pesquisas com padrões regex de complexidade modesta.
Uma palavra de cautela. Sempre há uma pequena sobrecarga para verificar os índices. Isso significa que se todos os arquivos já estiverem armazenados em cache na RAM, porque os arquivos foram pesquisados ou lidos recentemente, a indexação não irá necessariamente acelerar a pesquisa, obviamente. Nesse caso, uma pesquisa não indexada pode ser mais rápida. Além disso, uma pesquisa baseada em índice tem um tempo de inicialização mais longo. Esse tempo de inicialização aumenta quando são usadas classes de caracteres Unicode e curingas que devem ser convertidas em tabelas hash.
Para resumir, a pesquisa baseada em índice é mais eficaz ao pesquisar muitos arquivos frios e quando os padrões regex não correspondem muito, ou seja, queremos limitar o uso de repetições ilimitadas * e + e limitar o uso de classes de caracteres Unicode quando possível. Isso reduz o tempo de inicialização do ugrep e limita a taxa de correspondências de padrões falsos positivos (veja também as perguntas e respostas abaixo).
Indexe recursiva e incrementalmente todos os arquivos não binários mostrando o progresso:
ugrep-indexer -I -v
Indexe recursiva e incrementalmente todos os arquivos não binários, incluindo arquivos não binários armazenados em arquivos e em arquivos compactados, mostrando o progresso:
ugrep-indexer -z -I -v
Indexe incrementalmente todos os arquivos não binários, incluindo arquivos e arquivos compactados, mostre o progresso, siga links simbólicos para arquivos (mas não para diretórios), mas não indexe arquivos e diretórios que correspondam aos globs em .gitignore:
ugrep-indexer -z -I -v -S -X
Force a reindexação de todos os arquivos não binários, incluindo arquivos e arquivos compactados, siga links simbólicos para arquivos (mas não para diretórios), mas não indexe arquivos e diretórios que correspondam aos globs em .gitignore:
ugrep-indexer -f -z -I -v -S -X
O mesmo, mas reduza o armazenamento do arquivo de índice ao mínimo, diminuindo a precisão da indexação de 5 (padrão) para 0:
ugrep-indexer -f -0 -z -I -v -S -X
Aumente o desempenho da pesquisa aumentando a precisão da indexação de 5 (padrão) para 7 ao custo de arquivos de índice maiores:
ugrep-indexer -f7zIvSX
Exclua recursivamente todos os arquivos de índice ._UG#_Store ocultos para restaurar a árvore de diretórios para não indexada:
ugrep-indexer -d
Configure e compile com:
./build.sh
Se desejar, mas não for obrigatório, instale com:
sudo make install
Adicione uma opção para criar um arquivo de índice, por exemplo, especificado explicitamente para ugrep. Isso poderia melhorar ainda mais a velocidade da pesquisa indexada se o arquivo de índice estiver localizado em um sistema de arquivos rápido. Caso contrário, não espere muitas melhorias ou até mesmo uma possível lentidão, já que um único arquivo de índice não pode ser pesquisado simultaneamente e mais entradas de índice serão verificadas quando na verdade os diretórios forem ignorados (ignorando seus índices também). As experiências dirão. Uma advertência crítica desta abordagem é que a pesquisa baseada em índice com ugrep --index não é mais segura: arquivos novos e modificados que ainda não estão indexados não serão pesquisados.
Cada filtro Bloom de N-gram tem seu próprio "nível de bits" na tabela hash para evitar conflitos de hash. Por exemplo, 2 gramas não compartilham nenhum bit com 3 gramas. Isso garante que nunca teremos falsos positivos com caracteres falsamente correspondidos que na verdade não fazem parte do padrão. No entanto, o espaço de bits de 1 grama (caractere único) é pequeno (no máximo 256 bits). Portanto, desperdiçamos alguns bits quando as tabelas hash são maiores. Uma abordagem possível para reduzir o desperdício é combinar 1 grama com 2 gramas para compartilhar o mesmo espaço de bits. Isso é fácil de fazer se considerarmos 1 grama igual a 2 gramas com o segundo caractere definido como (NUL). Podemos diminuir a taxa de falsos positivos com um segundo hash de 2 gramas baseado em um método de hash diferente. Ou podemos expandir as “camadas de bits” de 8 para 9 para armazenar 9 gramas. Isso aumentará a precisão da indexação para padrões mais longos (9 ou mais) sem custo adicional. Por outro lado, essa mudança pode causar mais falsos positivos quando há correspondência falsa de caracteres que não fazem parte do padrão; perdemos a vantagem de uma precisão perfeita de 1 grama.
A indexação adiciona um arquivo de índice oculto ._UG#_Store a cada diretório indexado. Os arquivos indexados são verificados (nunca alterados!) pelo ugrep-indexer para gerar arquivos de índice.
O tamanho dos arquivos de índice depende da precisão especificada, sendo -0 o mais baixo (arquivos de índice pequenos) e -9 o mais alto (arquivos de índice grandes). A precisão padrão é -4 . Consulte o próximo Q para obter detalhes sobre o impacto da precisão no tamanho da indexação versus velocidade de pesquisa.
A indexação nunca segue links simbólicos para diretórios , porque diretórios vinculados simbolicamente podem estar localizados em qualquer lugar em um sistema de arquivos, ou em outro sistema de arquivos, onde não queremos adicionar arquivos de índice. Você ainda pode indexar links simbólicos para arquivos com a opção ugrep-indexer -S .
A opção -v ( --verbose ) exibe o progresso da indexação e o "ruído" de cada arquivo indexado. O ruído é uma medida de entropia ou aleatoriedade na entrada. Um nível mais alto de ruído significa que a indexação foi menos precisa na representação do conteúdo de um arquivo. Por exemplo, um arquivo grande com dados aleatórios é difícil de indexar com precisão e terá um alto nível de ruído.
A complexidade da indexação é linear no tamanho de um determinado arquivo a ser indexado. Na prática, não é um processo rápido, nem uma pesquisa tão rápida, e pode levar algum tempo para concluir uma passagem completa de indexação em uma grande árvore de diretórios. Quando a indexação for concluída, o ugrep-indexer exibe os resultados da indexação. O tamanho total dos índices adicionados e o ruído médio de indexação também são relatados.
A verificação de um arquivo para indexação resulta em uma tabela de hashes de indexação de 64 KB. Em seguida, o indexador ugrep divide a tabela pela metade com compactação de bits usando bit a bit - e desde que a precisão alvo não seja excedida. A redução pela metade é possível porque a tabela codifica hashes para 8 janelas em deslocamentos desde o início do padrão, correspondendo aos 8 bits por célula da tabela de hash de índice. Combinar as duas metades da tabela pode transformar alguns bits de um em zero, o que pode causar uma correspondência de falso positivo. Isso prova a monotonicidade do indexador. Um valor hash de zero bits indica uma possível correspondência.
O indexador ugrep detecta "arquivos binários", que podem ser ignorados e não indexados com a opção -I do indexador ugrep ( --ignore-binary ). Isso é útil ao pesquisar com a opção ugrep -I ( --ignore-binary ) para ignorar arquivos binários, que é um cenário típico.
O indexador ugrep obedece às exclusões de arquivo .gitignore quando especificado com a opção -X ( --ignore-files ). Arquivos e diretórios ignorados não serão indexados para economizar espaço no sistema de arquivos. Isso funciona bem ao procurar arquivos com a opção ugrep --ignore-files .
A indexação pode ser abortada, por exemplo, com CTRL-C, o que não resultará na perda da capacidade de pesquisa com ugrep, mas deixará a estrutura de diretórios apenas parcialmente indexada.
A opção -c verifica os índices em busca de referências obsoletas e arquivos e diretórios não indexados.
Os índices são excluídos com a opção ugrep-indexer -d .
O indexador ugrep foi extensivamente testado comparando os resultados da pesquisa ugrep --index com os resultados "lentos" da pesquisa ugrep não indexados em milhares de arquivos com milhares de padrões de pesquisa aleatórios.
A pesquisa baseada em indexação funciona com todas as opções ugrep, exceto com a opção -v ( --invert-match ), --filter , -P ( --perl-regexp ) e -Z ( --fuzzy ). A opção -c ( --count ) com --index define automaticamente --min-count=1 para pular todos os arquivos com zero correspondências.
Se algum arquivo ou diretório foi atualizado, adicionado ou excluído após a indexação, então ugrep --index sempre pesquisará esses arquivos e diretórios quando eles estiverem presentes no caminho de pesquisa recursiva. Você pode executar o ugrep-indexer novamente para atualizar incrementalmente todos os índices.
Os padrões Regex são convertidos internamente pelo ugrep com a opção --index em uma forma de tabelas hash para até os primeiros 16 bytes dos padrões regex especificados, possivelmente mais curtos para reduzir o tempo de construção quando os padrões regex são complexos. Portanto, os primeiros 8 a 16 caracteres de um padrão regex a ser pesquisado são os mais críticos e não devem corresponder muito para limitar as chamadas correspondências de falsos positivos que podem retardar a pesquisa.
No ugrep, um padrão regex é convertido em um DFA. Um autômato finito de hash de indexação (HFA) é construído sobre o DFA para representar de forma compacta tabelas hash como transições de estado com bordas rotuladas. Este HFA consiste em até oito camadas, cada uma deslocada em um byte para representar a próxima janela de 8 bytes sobre o padrão. Cada camada HFA codifica hashes de índice para aquela parte do padrão. A função hash de índice escolhida é "aditiva", o que significa que o próximo byte é adicionado quando o hash é feito com o hash anterior. Isto é muito importante porque reduz criticamente a sobrecarga de construção do HFA. Agora podemos codificar transições HFA rotuladas para estados como múltiplas arestas com intervalos de valores de hash de 16 bits, em vez de um conjunto de arestas únicas, cada uma com um valor de hash individual. Para esse fim, uso minha biblioteca de intervalos abertos reflex::ORanges<T> derivada de std::set<T> .
Uma função maybe_match() de string única muito simples com a função hash de índice prime 61 é fornecida abaixo para demonstrar a pesquisa baseada em índice de uma única string:
// prime 61 hashing
uint16_t indexhash(uint16_t h, uint8_t b, size_t size)
{
return ((h << 6) - h - h - h + b) & (size - 1);
}
// return possible match of string given array of hashes of size <= 64K (power of two)
bool maybe_match(const char *string, uint8_t *hashes, size_t size)
{
size_t len = strlen(string); // practically we can and should limit len to e.g. 15 or 16
for (const char *window = string; len > 0; ++window, --len)
{
uint16_t h = window[0] & (size - 1);
if (hashes[h] & 0x01)
return false
size_t k, n = len < 8 ? len : 8;
for (k = 1; k < n; ++k)
{
h = indexhash(h, window[k], size);
if (hashes[h] & (1 << k))
return false;
}
}
return true;
}
O hash principal 61 foi escolhido entre muitas outras funções de hash possíveis usando uma configuração experimental realista. Uma função de hash candidata foi testada pesquisando repetidamente uma palavra sorteada aleatoriamente em um arquivo da Wikipedia de 100 MB. A palavra sofreu mutação com uma, duas ou três letras aleatórias. Esta mutação é verificada para garantir que não corresponda a uma palavra válida real no arquivo da Wikipedia. Em seguida, a taxa de falsos positivos foi registrada sempre que uma palavra mutada correspondia ao arquivo. Uma função hash com uma taxa mínima de falsos positivos deve ser uma boa candidata em geral.
Ao usar uma janela de 8 (ou menor, dependendo do comprimento do padrão), a taxa de falsos positivos é menor em comparação com os filtros Bloom padrão. Mais especificamente, funções hash N² são usadas em vez de N em um filtro Bloom. Para padrões mais curtos, N é muitas vezes demasiado pequeno para limitar falsos positivos. Portanto, o N² é mais eficaz. Ele também rejeita qualquer padrão de uma correspondência que tenha um caractere em qualquer lugar nos primeiros 8 bytes do padrão e não ocorra realmente em nenhum lugar de um arquivo indexado, enquanto um filtro Bloom padrão pode ter uma correspondência de falso positivo. Além disso, o endereçamento de bits usado para indexar a tabela de hashes permite uma compactação eficiente da tabela.
A indexação é uma forma de compactação com perdas. Quanto maior a precisão da indexação, mais rápido deve ser o desempenho da pesquisa ugrep, ignorando mais arquivos que não correspondem. Uma maior precisão reduz o ruído (menos perdas). Um alto nível de ruído faz com que o ugrep às vezes pesquise arquivos indexados que não correspondem. Chamamos isso de “correspondências falsas positivas”. Maior precisão requer arquivos de índice maiores. Normalmente esperamos 4K ou menos de armazenamento de indexação por arquivo, em média. O mínimo é 128 bytes de armazenamento de índice por arquivo, excluindo o nome do arquivo e um cabeçalho de índice de 4 bytes. O máximo é o armazenamento de 64 K bytes por arquivo para arquivos muito grandes e barulhentos.
Ao pesquisar arquivos indexados com ugrep --index --stats , a opção --stats mostra as estatísticas da pesquisa após a conclusão da pesquisa baseada em indexação. Quando muitos arquivos não são ignorados na pesquisa devido ao ruído de indexação (ou seja, falsos positivos), uma maior precisão ajuda a aumentar a eficácia da indexação, o que pode acelerar a pesquisa.
Os arquivos UTF-16 e UTF-32 também são indexados. O indexador os trata como UTF-8 após convertê-los internamente em UTF-8 para indexar.
O espaço em disco é economizado arquivando (zip/tar/pax/cpio) e compactando arquivos. Por outro lado, pesquisar arquivos e arquivos compactados é muito mais lento do que pesquisar arquivos normais. Indexar arquivos e arquivos compactados com ugrep-indexer -z -I e pesquisá-los com ugrep -z -I --index PATTERN acelera a pesquisa, ou seja, quando arquivos compactados e compactados são ignorados. Por outro lado, os requisitos de armazenamento em disco aumentarão com a adição de entradas de arquivo de índice para arquivos compactados. Observe que quando os arquivos compactados contêm binários, a opção -I ignora esses binários.
A sobrecarga inicial de ugrep --index para construir tabelas hash de indexação depende dos padrões regex. Se um padrão regex for muito "permissivo", ou seja, corresponder a muitos padrões possíveis, então o tempo de inicialização do ugrep --index aumenta significativamente para calcular tabelas hash. Isso pode acontecer quando grandes classes de caracteres Unicode e curingas são usadas, especialmente com repetições * e + ilimitadas. Para descobrir como o tempo de inicialização aumenta, use a opção ugrep --index -r PATTERN /dev/null --stats=vm para pesquisar /dev/null com seu PATTERN.
Os arquivos de índice devem ser muito densos em conteúdo informativo e esse é o caso deste novo algoritmo de indexação para ugrep que projetei e implementei. Quanto mais denso for um arquivo de índice, mais compacto ele representará com precisão os dados do arquivo original. Isso torna difícil ou impossível compactar arquivos de índice. Este também é um bom indicador da eficácia de um arquivo de índice na prática.
