Perché "grep -ignore-case" 50 volte più lento?

Question

Sono stato molto sorpreso di vederlo quando si aggiunge l'opzione --ignore-case a grep che può rallentare la ricerca di 50 volte. Ho provato questo su due macchine diverse con lo stesso risultato. Sono curioso di scoprire una spiegazione per l'enorme differenza di prestazioni.

Vorrei anche vedere un comando alternativo a grep per le ricerche senza distinzione tra maiuscole e minuscole. Non ho bisogno di espressioni regolari, ho appena corretto la ricerca delle stringhe. In primo luogo il file di prova sarà un file di testo 50   MB con alcuni dati fittizi, è possibile utilizzare il seguente codice per generarlo:

Creare test.txt

yes all work and no play makes Jack a dull boy | head -c 50M > test.txt 
echo "Jack is no fun" >> test.txt 
echo "Jack is no Fun" >> test.txt 

Dimostrazione

Di seguito è una dimostrazione della lentezza. Aggiungendo l'opzione --ignore-case il comando diventa 57 volte più lento.

$ time grep fun test.txt 
all work and no plJack is no fun 
real 0m0.061s 

$ time grep --ignore-case fun test.txt 
all work and no plJack is no fun 
Jack is no Fun 
real 0m3.498s 

Possibili spiegazioni

Googling in giro ho trovato un una discussione su grep essere lento nella versione locale UTF-8. Così ho eseguito il test seguente, e ha accelerato. Le impostazioni internazionali predefinite sulla mia macchina sono en_US.UTF-8, quindi impostarla su POSIX sembra aver effettuato un avvio delle prestazioni, ma ora ovviamente non riesco a cercare correttamente il testo Unicode che è indesiderabile. Inoltre è ancora 2,5 volte più lento.

$ time LANG=POSIX grep --ignore-case fun test.txt 
all work and no plJack is no fun 
Jack is no Fun 
real 0m0.142s 

Alternative

potremmo usare Perl invece è più veloce, ma ancora 5,5 volte più veloce del grep maiuscole e minuscole. E il POSIX grep sopra è circa il doppio più veloce.

$ time perl -ne '/fun/i && print' test.txt 
all work and no plJack is no fun 
Jack is no Fun 
real 0m0.388s 

Quindi mi piacerebbe trovare un'alternativa rapida e corretta e una spiegazione se qualcuno ne ha uno.

UPDATE - CentOS

Le due macchine che sono stati testati sopra entrambi correvano Ubuntu uno 11.04 (Natty Narwhal), l'altra 12.04 (Precise Pangolin). L'esecuzione degli stessi test su una macchina CentOS 5.3 produce i seguenti risultati interessanti. I risultati delle prestazioni dei due casi sono quasi identici. Ora CentOS 5.3 è stato rilasciato nel gennaio 2009 e sta eseguendo grep 2.5.1 mentre Ubuntu 12.04 sta eseguendo grep 2.10. Quindi potrebbero esserci cambiamenti nella nuova versione e differenze nelle due distribuzioni.

$ time grep fun test.txt 
Jack is no fun 
real 0m0.026s 

$ time grep --ignore-case fun test.txt 
Jack is no fun 
Jack is no Fun 
real 0m0.027s 

Answer 1

penso che questo bug report aiuta a comprendere il motivo per cui è lento:

bug report grep, slow on ignore-case

Answer 2

di fare una ricerca case-insensitive, grep deve prima convertire l'intero file di 50   MB a uno caso o l'altro. Ci vorrà del tempo. Non solo, ma ci sono copie di memoria ...

Nel tuo caso di test, devi prima generare il file.Ciò significa che sarà memorizzato nella cache. La prima esecuzione di grep ha solo mmap le pagine memorizzate nella cache; non ha nemmeno bisogno di accedere al disco.

Il grep senza distinzione tra maiuscole e minuscole fa lo stesso, ma poi tenta di modificare tali dati. Ciò significa che il kernel prenderà un'eccezione per ciascuna pagina modificata 4   kB e finirà per dover copiare l'intero 50   MB in una nuova memoria, una pagina alla volta.

Fondamentalmente, vorrei aspettarsi questo per essere più lento. Forse non 57x più lento, ma decisamente più lento.

Answer 3

Questa lentezza è dovuta a grep (su un locale UTF-8) che accede costantemente ai file "/ usr/lib/locale/locale-archive" e "/usr/lib/gconv/gconv-modules.cache".

Può essere visualizzato utilizzando l'utilità strace. Entrambi i file provengono da glibc.

Answer 4

Il motivo è che è necessario eseguire un confronto compatibile con Unicode per le impostazioni internazionali correnti e, a giudicare dalla risposta di Marat, non è molto efficiente.

Questo mostra quanto più veloce è quando Unicode non viene presa in considerazione:

$ time LC_CTYPE=C grep -i fun test.txt 
all work and no plJack is no fun 
Jack is no Fun 
real 0m0.192s 

Naturalmente, questa alternativa non funzionerà con i caratteri in altre lingue come N/N, O/o, Ð/ð, Æ/æ e così via.

Un'altra alternativa è quella di modificare l'espressione regolare in modo che corrisponda con il caso di insensibilità:

$ time grep '[Ff][Uu][Nn]' test.txt 
all work and no plJack is no fun 
Jack is no Fun 
real 0m0.193s 

Questo è ragionevolmente veloce, ma ovviamente è un dolore per convertire ogni carattere in una classe, e non è facile convertirlo in un alias o in uno script sh, a differenza del precedente.

Per confronto, nel mio sistema:

$ time grep fun test.txt 
all work and no plJack is no fun 
real 0m0.085s 

$ time grep -i fun test.txt 
all work and no plJack is no fun 
Jack is no Fun 
real 0m3.810s