Hi all, I was expecting it to take order n time to match against n patterns, where n is the number of lines in the pattern file.
What I am experiencing: The execution time of grep -f behaves like n^a, with a somewhere in the range [2.5, 3.0]. The execution time with a 100 line pattern file was 0.17 sec, but the execution time with a 1000 line pattern file was 59.7 seconds, nowhere near the 10 * 0.17 sec = 1.7 seconds that I expected. Details and reproduction steps are given below. Thanks, Narfi Here is what I did, I created 1000 strings and 1000 regexps: cat /dev/urandom | od -x | head -1000 > regexps.txt cat /dev/urandom | od -x | head -1000 > text.txt Avoid any problems with the locale: export LC_ALL=C export LANG=C export LANGUAGE=C I then timed the execution of matching against the first 100, 200, etc patterns in regexps.txt: for n in 100 200 300 400 500 600 700 800 900 1000; do head -$n regexps.txt > current_regexps.txt /usr/bin/time grep -f current_regexps.txt text.txt done Following is the user time in seconds as reported by /usr/bin/time, for n in 100, 200, ..., 1000: 0.17 0.80 2.08 4.10 7.02 11.33 17.31 28.68 41.39 59.70 This is on Mandriva 2006. % grep --version grep (GNU grep) 2.5.1