Come funziona grep così veloce?

Question

Sono davvero stupito dalla funzionalità di GREP in shell, in precedenza utilizzavo il metodo della sottostringa in java ma ora utilizzo GREP per questo e viene eseguito in pochi secondi, è incredibilmente più veloce del codice Java che ho usato per scrivere (secondo la mia esperienza potrei essere sbagliato però)

Detto questo non sono stato in grado di capire come sta accadendo? non c'è anche molto disponibile sul web.

Qualcuno può aiutarmi con questo?

Answer 1

Presumendo che la tua domanda riguarda GNU grep in particolare. Ecco una nota dell'autore, Mike Haertel:

GNU grep è veloce perché evita l'accesso a ogni byte di ingresso.

GNU grep è veloce perché esegue le istruzioni MOLTO POCHI PER OGNI BYTE che fa sguardo.

GNU grep utilizza il noto algoritmo di Boyer-Moore, che guarda prima per la lettera finale della stringa di destinazione, e usa una tabella di ricerca per raccontarla quanto anticipo si può saltare in ingresso ogni volta che trova a carattere non corrispondente.

GNU grep srotola anche il ciclo interno di Boyer-Moore, e imposta i Boyer-Moore voci della tabella delta in modo tale che essa non deve fare il test di uscita anello ad ogni passo srotolato. Il risultato di questo è che, nel limite, GNU grep ha una media di meno di 3 istruzioni x86 eseguite per ogni byte di input che effettivamente guarda (e salta completamente molti byte ).

GNU grep utilizza chiamate di sistema di input Unix raw ed evita di copiare i dati dopo averlo letto. Inoltre, GNU grep evita l'interruzione dell'ingresso nelle linee . La ricerca di nuove righe rallenterebbe gradualmente di un fattore pari a diverse volte, perché per trovare le nuove righe dovrebbe guardare a ogni byte!

Così, invece di utilizzare il metodo di line-oriented, GNU grep legge i dati grezzi in un buffer di grandi dimensioni, ricerche il buffer utilizzando Boyer-Moore, e solo quando trova una corrispondenza lo fa andare a cercare le nuove righe di delimitazione (Alcune opzioni della riga di comando come -n disattivare questa ottimizzazione.)

questa risposta è un sottoinsieme delle informazioni prese da here.

Answer 2

Da aggiungere all'eccellente risposta di Steve.

Esso non può essere ampiamente conosciuto ma grep è quasi sempre più veloce quando grep per una più pattern-stringa di un breve uno, perché in un modello più lungo, Boyer-Moore può saltare in avanti nella passi più lunghi per raggiungere ancora meglio sublineari velocità:

Esempio:

# after running these twice to ensure apples-to-apples comparison 
# (everything is in the buffer cache) 

$ time grep -c 'tg=f_c' 20140910.log 
28 
0.168u 0.068s 0:00.26 

$ time grep -c ' /cc/merchant.json tg=f_c' 20140910.log 
28 
0.100u 0.056s 0:00.17 

La forma più lunga è il 35% più veloce!

Come mai? Boyer-Moore aggiunge una tabella di salto dalla stringa di modello e ogni volta che si verifica una mancata corrispondenza, seleziona il salto più lungo possibile (dall'ultimo carattere al primo) prima di confrontare un singolo carattere nell'input con il carattere nel salto tavolo.

Ecco a good video explaining Boyer Moore

Un altro errore comune (per GNU grep) è che è più veloce di fgrepgrep. f in fgrep non sta per "veloce", sta per "fisso" (vedere la pagina man), e poiché entrambi sono lo stesso programma, ed entrambi usano Boyer-Moore, non c'è differenza di velocità tra loro quando ricerca di stringhe fisse senza regexp di caratteri speciali. L'unico motivo per cui utilizzo fgrep è quando c'è un carattere speciale regexp (come ., [] o *). Non voglio che venga interpretato come tale. E anche allora la forma più portatile/standard di grep -F è preferita su fgrep.