8

I am using egrep (grep -E) with a PATTERN file. (-f path/to/file).

This is done in an infinite loop on a stream of text. This implies that I cannot accumulate and pass ALL the input to grep at once (like *.log).

Is there a way to make grep "save" the NFA it is building from the PATTERN file to use for it's next run?

I have searched Google and read the documentation with no luck.

I'll try to explain it a little bit more. I need to locate a fixed number of strings with regexes (This is not a part of a question but feel free to suggest otherwise) such as IP addresses, domains etc. The search is done on a feed from the internet. You can think about it as a stream of text. I can't use grep on all of the input since it's a stream. I can accumulate a chunk of stream and use grep on it (thus not using grep on each line) but this is also limited (let's say for 30 seconds).

I know grep is building an NFA from all of its patterns (in my case from a file). So my question here is: can I tell grep to save that NFA for the next run, since it is not going to change? That would save me the time of building that NFA every time.

  • What do you mean by This is done in an infinite loop on a stream of text? Are you saying that you're running one grep per line of text? Where is the text coming from? Would tail -f be an option? – Stéphane Chazelas Sep 11 '17 at 10:39
  • Let's say I'm accumilating the stream for 30 seconds and then run grep on that chunk. – bergerg Sep 11 '17 at 10:41
  • 1
    It's still not clear why you'd need to run grep several times. Possibly related: Why is matching 1250 strings against 90k patterns so slow? – Stéphane Chazelas Sep 11 '17 at 10:43
  • 5
    grep is meant to work on a stream of text, I still don't get why you'd need to run several instances. Why can't you feed all those to the same grep instance? Why do you need to accumulate them before feeding to grep? – Stéphane Chazelas Sep 11 '17 at 11:05
  • 2
    Take a look at flex, and write your own program, that may turn out to be much faster. – user2064000 Sep 11 '17 at 13:45
14

No, there's no such thing. Generally the cost of starting grep (fork a new process, load the executable, shared library, dynamic linkage...) would be a lot greater than compiling the regexps, so this kind of optimisation would make little sense.

Though see Why is matching 1250 strings against 90k patterns so slow? about a bug in some versions of GNU grep that would make it particularly slow for a great number of regexps.

Possibly here, you could avoid running grep several times by feeding your chunks to the same grep instance, for instance by using it as a co-process and use a marker to detect the end. With zsh and GNU grep and awk implementations other than mawk:

coproc grep -E -f patterns -e '^@@MARKER@@$' --line-buffered
process_chunk() {
  { cat; echo @@MARKER@@; } >&p & awk '$0 == "@@MARKER@@"{exit};1' <&p
}
process_chunk < chunk1 > chunk1.grepped
process_chunk < chunk2 > chunk2.grepped

Though it may be simpler to do the whole thing with awk or perl instead.

But if you don't need the grep output to go into different files for different chunks, you can always do:

{
  cat chunk1
  while wget -qO- ...; done # or whatever you use to fetch those chunks
  ...
} | grep -Ef patterns > output
  • I have veraion 3+ of grep so thats not the issue. Didn't even consider the forking overhead. I guess I'll try to stream everything through grep as is. Thanks. – bergerg Sep 11 '17 at 15:43
  • Wouldn't the executable and the shared libraries stay in RAM buffers after processes termination (unless the OP is actually low on RAM)? – Dmitry Grigoryev Sep 11 '17 at 16:01
  • 2
    @DmitryGrigoryev, yes, most likely, still need to be mapped in the process address space and do the link editing. There's more like loading and parsing the locale data, parse the options, the environment... The point is that the cost of the regcomp() is diluted in all that overhead. The first thing to do when optimizing would be to avoid running several greps in the first place. – Stéphane Chazelas Sep 11 '17 at 16:06
1

I can't use grep on all of the input since it's a stream. I can accumulate a chunk of stream and use grep on it...

Are you aware that pipelines block? If you pipe something to grep and all input is not available, grep will wait until it is available and then continue as if the input was there all along.

$ ( echo a1; echo b1; sleep 5; echo a2 ) | grep 'a.'
a1
a2

EDIT: How pipelines work, for example with cmd1 | cmd2 is that both programs will start at the same time, with an e.g. 65,536-byte "chunk buffer" between them. When cmd2 tries to read and that buffer is empty, it will wait for a chunk to be available. When cmd1 tries to write and that buffer is full, it will wait until cmd2 reads it.

From what I can read, there is no need to cut the input into chunks and pass them to grep separately. That's already done automatically.

EDIT2: grep should also print the results as soon as it finds them in the stream. There is no need for the stream to finish before you can get your results.

0

Maybe you can "use grep on all of the input" ? Using nc (netcat), or through script, or via other, similar, tools? Especially if your patternfile is of manageable size (say less than 1000 regexps).

First exemple: You can egrep some streaming connection: (here exemple shown with nc, but others could apply)

prompt:/some/path $ nc somehost someport | egrep -f patternfile | gzip -c - > results.gz

# and while this is running, you can have a look at the growing results.gz:
prompt:/some/otherpath $ tail -f /some/path/results.gz | gzip -c - | less

(note: you can even : touch /some/path/results.gz before starting the nc command, and have tail -f on that (empty) file to not miss anything. Anyway, the results.gz will contain everything you wanted to catch)

second exemple: You could even egrep on a currently running shell session (and showing another way to follow the progression):

#in 1 terminal:
prompt:/home/userA $ script
Script command is started. The file is typescript.
prompt:/home/userA $ 
 ... doing here whatever you want (start IRC? etc) ...
prompt:/home/userA $ ctrl-d # to end the current script session
Script command is complete. The file is typescript.

#and in another terminal, while you are "doing here whatever you want" :
prompt:/home/somewhere $ tail -f /home/userA/typescript | egrep -f patternfile  | tee /some/place/to/store/results.gz

egrep is an highly efficient version of grep, on most systems (see some interresting infos on : https://swtch.com/~rsc/regexp/regexp1.html )

  • you could even use exemple1 on such things as a dd output, etc. – Olivier Dulac Sep 11 '17 at 16:04
  • interresting side note : grep is more efficient the bigger the known part of the regexp is (ex: looking for the string or regexp s is much, mush slower than matching something and this is much slower than matching something even much longer (the latter allowing the regexp match to skip larger portions of the input when differing). On huge files, it basically "divides" the time to parse it by the length ratio (ie, grepping 1 known character is almost 40 times slower than matching a string of 40 known characters. I didn't prof it but it is really noticeable.) – Olivier Dulac Sep 11 '17 at 16:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.