Krep - ferramenta de busca de strings 5 vezes mais rápida que o grep

• Ferramenta ultrarrápida de busca de strings escrita em C para aplicações em que desempenho é essencial
• Seleciona dinamicamente o algoritmo ideal de acordo com as características do padrão e do hardware
• Aproveita hardware como SSE4.2/AVX2 para oferecer a máxima taxa de processamento
• Divide arquivos em chunks para processamento paralelo com multithreading, com suporte a grandes volumes
• Usa o algoritmo de busca mais adequado conforme o padrão
  • Boyer-Moore-Horspool: adequado para correspondência de padrões em geral
  • Algoritmo Knuth-Morris-Pratt (KMP): otimizado para padrões curtos
  • Rabin-Karp: eficaz para padrões longos
  • Aceleração por SIMD: melhora de desempenho em hardware com suporte a SSE4.2 e AVX2
• Usa I/O de arquivo com mapeamento de memória para minimizar chamadas de sistema e maximizar a taxa de processamento
• Opções de busca flexíveis
  • Busca com e sem diferenciação entre maiúsculas e minúsculas
  • Além de arquivos, também permite buscar diretamente em strings
  • Oferece modo para exibir apenas a contagem de correspondências

Como usar

krep [OPTIONS] PATTERN [FILE]  

• Buscar “error” em um arquivo de log: krep "error" system.log
• Buscar sem diferenciar maiúsculas/minúsculas usando 8 threads: krep -i -t 8 "ERROR" large_logfile.log
• Exibir a contagem de correspondências (sem mostrar as linhas encontradas): krep -c "TODO" *.c
• Buscar diretamente em uma string, e não em um arquivo: krep -s "Hello" "Hello world"

Opções de linha de comando

• -i : buscar sem diferenciar maiúsculas e minúsculas
• -c : exibir apenas a contagem de correspondências, sem mostrar as linhas encontradas
• -t NUM : usar NUM threads (padrão: 4)
• -s STRING : buscar em uma string, e não em um arquivo
• -v : exibir informações de versão
• -h : exibir ajuda

Benchmark

• O desempenho do krep é excelente em comparação com ferramentas comuns de busca de strings.
  • O krep levou 0,78 segundo para buscar um padrão comum em um arquivo de texto de 1 GB, o que equivale a 1.282 MB/s
  • O grep levou 2,95 segundos na mesma tarefa, registrando 339 MB/s
  • O ripgrep levou 1,48 segundo, mostrando 676 MB/s
• → o krep é cerca de 3,8 vezes mais rápido que o grep e cerca de 1,9 vez mais rápido que o ripgrep (o desempenho pode variar de acordo com o hardware e as características do arquivo)

Origem do nome

• “krep” vem do termo islandês “kreppan”
• Significa “agarrar rapidamente”
• Simboliza reconhecimento eficiente de padrões
• É um comando curto e conciso, fácil de digitar

[clickin]

Se ao abrir mão do suporte a regex ele consegue ser só 2 vezes mais rápido que o ripgrep, a utilidade acaba ficando um pouco menor.
Acho que vou continuar usando o ripgrep mesmo, já que ele aceita regex.

[GN⁺]

Opiniões do Hacker News

• Recursos da CPU (ex.: AVX2) devem ser detectados em tempo de execução

  • ifdef detecta apenas em tempo de compilação se o compilador oferece suporte
  • O programa só é compilado quando o compilador oferece suporte a AVX2
  • É preciso verificar em tempo de execução se a CPU oferece suporte a AVX2
  • No projeto há a parte "detecção em tempo de configuração por meio de flags CPUID e teste real de execução de instruções"
  • É possível aproveitar automaticamente instruções SSE4.2 e AVX2

• Apresentação de uma postagem de blog sobre o projeto krep

  • Na página inicial, ele aparece como mais rápido que o ripgrep
  • Gostaria de comparar com o benchmark completo do ripgrep
  • Ocorreu um erro relacionado a madvise(), sendo necessário adicionar -D_GNU_SOURCE aos CFLAGS do Makefile

• Importância dos casos de teste

  • A questão das fronteiras de blocos na busca de arquivos multithread preocupa
  • Isso introduz novos casos extremos em uma busca simples
  • Adicionar um único caractere ao arquivo pode quebrar a correspondência

• Resultados de benchmark após resolver o problema de build

  • Na primeira tentativa de benchmark, a velocidade foi menor
  • O ripgrep foi 1,52 vez mais rápido que o krep

• Tentativa de benchmark com alta frequência de correspondências

  • O krep foi 3,40 vezes mais rápido que o ripgrep
  • O número de correspondências difere bastante
  • O krep pode não estar fornecendo resultados corretos

• Tentativas adicionais de benchmark

  • O ripgrep é mais rápido para encontrar determinados padrões
  • O krep não encontra correspondências

• Algoritmo do ripgrep e uso de mapeamento de memória

  • O ripgrep usa algoritmos avançados de busca de substring
  • Usa mapeamento de memória e processamento paralelo
  • O krep também usa processamento paralelo, com multithreading ao pesquisar um único arquivo

• Dúvidas sobre os resultados de benchmark

  • É estranho que o ripgrep leve mais de 40 segundos para buscar um padrão em um arquivo de 5 GB
  • Pedido ao OP para explicar como reproduzir o benchmark

• Opiniões sobre o nome krep

  • O "re" de grep significa expressões regulares
  • Como o krep não usa expressões regulares, o nome pode ser inadequado