OK, for those who haven't heard it before... There was a meeting at Bell Labs. One women came in late, all out of breath. She apologized: "I'm so sorry I'm late, but I was grepping my apartment for my keys." One of the senior UNIX guys in the meeting responded dryly: "You should have used egrep, it's faster." On 01/30/2016 11:44 AM, Dave Horsfall wrote:

grep is the best-known case of the regular-expression code being extracted from ed for use elsewhere. Another case is the regex library, created by me, for use in some PWB code we were working on, probably around 1974. My recollection is that the code was in assembler, as I think ed remained in assembler long after UNIX itself went to C. I wrapped it for calling from C, of course... we didn't code in assembler. --Marc On Sat, Jan 30, 2016 at 1:40 PM, Dave Horsfall <dave(a)horsfall.org> wrote:

If you really want to see a fast grep then you need to look at gnu grep by Mike Haertel. Thread about it here: http://lists.freebsd.org/pipermail/freebsd-current/2010-August/019310.html If you are a performance nerd then that thread and that code is worth a read. Mike is extremely good at performance. He's as good at that as all the original Unix people were at getting stuff to fit in a small amount of memory. I like to think of myself as a performance guy but Mike is better. On Sun, Jan 31, 2016 at 12:41:15PM +1100, Dave Horsfall wrote: -- --- Larry McVoy lm at mcvoy.com http://www.mcvoy.com/lm

On Sat, Jan 30, 2016, at 21:06, jason-tuhs(a)shalott.net wrote: Wouldn't you have to know exactly what your keys look like?

Mary Ann Horton scripsit: Is it really? The one time I used fgrep in production, I was checking a a few hundred documents at a time to see which ones contained any of a few thousand keywords. "fgrep -l -f keywords" seemed to do the job quite quickly: would it really have been faster to assemble the keywords into a single egrep regex and use egrep? (This was on Solaris, so using more or less classic fgrep, not GNU grep.) For a while I referred to myself as "just another desperate fgrep hacker". I use "ex" as my normal text editor (including for this email); I drop into vi mode occasionally, mostly to bounce on the % key when writing Lisp. Because there is no support for | in ex regexes, I rely on the low entropy of English text (about 2.7 bits per letter) and search for e.g. "open|shut" by searching for "[os][ph][eu][nt]". I may get a few false positives, but they will easily be removed by vgrep. -- John Cowan http://www.ccil.org/~cowan cowan(a)ccil.org After fixing the Y2K bug in an application: WELCOME TO <censored> DATE: MONDAK, JANUARK 1, 1900

Dave Horsfall scripsit: Actually, it just appears to be that way. Many egrep things like + and ? are supported in grep too, you just have to enter them as \+ and \?, at least now that we have Posix regular expressions. What egrep does not support that grep does is backreferences, and that allows it to use highly efficient deterministic (i.e. non-backtracking) finite state automata. Classic grep uses backtracking, which makes it much slower on problematic expressions like "a*b" where there is no b in the input. On the other hand, creating a deterministic automaton has higher setup costs. -- John Cowan http://www.ccil.org/~cowan cowan(a)ccil.org Si hoc legere scis, nimium eruditionis habes.

: Al Aho decided to put theory into practice, and implemented full regular : expressions (including alternation and grouping which were missing from : grep)and wrote egrep over a weekend. Fgrep, specialised for the case of : multiple (alternate) literal strings, was written in the same weekend. : Egrep was about twice as fast as grep for simple character searches but : was slower for complex search patterns (due to the high cost of building : the state machine that recognised the patterns). I remember talking to Al about his programming experiences not long after he wrote egrep. His focus was theory, and he wrote far more books and papers than programs. He said something like: "I never realized that you had to write so many different algorithms to get something to work. I thought I just needed to write one!" Also, as a practical example of exponential blowup doing an fgrep-like problem, use lex to recognize a bunch of reserved words ("if","for","else", "while","int",... and such) and follow it with lnu* to recognize identifier names (where lnu recognizes letters, numbers, and underscore). I gave up on lex for PCC when the lexer got bigger than all the rest of the compiler... Steve