[TUHS] Short history of 'grep'

[TUHS] Short history of 'grep'

[Warren Toomey]

Norman put this link up on twitter:
https://medium.com/@rualthanzauva/grep-was-a-private-command-of-mine-for-quite-a-while-before-i-made-it-public-ken-thompson-a40e24a5ef48#.t94fs3pgx

All good, except I'm not sure I would have written "One guy McIlroy claimed
grep was invented for him." :-)

Cheers, Warren (a lesser guy)

[TUHS] Short history of 'grep'

[Mary Ann Horton]

A great read.  Thanks!

I'm wondering if anyone can confirm the (possibly apocryphal) grep story 
about the meeting at Bell Labs and the person who was late because she 
couldn't find her keys?  Maybe put some names to the characters?

(I can tell the story as I heard it, but I suspect we've all heard it 
before.)

Thanks,

     Mary Ann

On 01/29/2016 07:00 PM, Warren Toomey wrote:
> Norman put this link up on twitter:
> https://medium.com/@rualthanzauva/grep-was-a-private-command-of-mine-for-quite-a-while-before-i-made-it-public-ken-thompson-a40e24a5ef48#.t94fs3pgx
>
> All good, except I'm not sure I would have written "One guy McIlroy claimed
> grep was invented for him." :-)
>
> Cheers, Warren (a lesser guy)
>

[TUHS] Short history of 'grep'

[Dave Horsfall]

On Sat, 30 Jan 2016, Mary Ann Horton wrote:

> I'm wondering if anyone can confirm the (possibly apocryphal) grep story 
> about the meeting at Bell Labs and the person who was late because she 
> couldn't find her keys?  Maybe put some names to the characters?
> 
> (I can tell the story as I heard it, but I suspect we've all heard it 
> before.)

Please do; I haven't heard it, so others may not have...

-- 
Dave Horsfall DTM (VK2KFU)  "Those who don't understand security will suffer."

[TUHS] Short history of 'grep'

[Mary Ann Horton]

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:
> On Sat, 30 Jan 2016, Mary Ann Horton wrote:
>
>> I'm wondering if anyone can confirm the (possibly apocryphal) grep story
>> about the meeting at Bell Labs and the person who was late because she
>> couldn't find her keys?  Maybe put some names to the characters?
>>
>> (I can tell the story as I heard it, but I suspect we've all heard it
>> before.)
> Please do; I haven't heard it, so others may not have...
>

[TUHS] Short history of 'grep'

[Dave Horsfall]

On Sat, 30 Jan 2016, Mary Ann Horton wrote:

> OK, for those who haven't heard it before...

Hilarious - thanks!

-- 
Dave Horsfall DTM (VK2KFU)  "Those who don't understand security will suffer."

[TUHS] Short history of 'grep'

[Marc Rochkind]

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 at horsfall.org> wrote:

> On Sat, 30 Jan 2016, Mary Ann Horton wrote:
>
> > OK, for those who haven't heard it before...
>
> Hilarious - thanks!
>
> --
> Dave Horsfall DTM (VK2KFU)  "Those who don't understand security will
> suffer."
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://minnie.tuhs.org/pipermail/tuhs/attachments/20160130/babd853c/attachment.html>

[TUHS] Short history of 'grep'

[Dave Horsfall]

I'm still trying to get my around about how a program such as "egrep" 
which handles complex patterns can be faster than one that doesn't...  It 
seems to defeat all logic :-)

Is there a simple explanation, involving small words?  I've never really 
looked at the theory.

-- 
Dave Horsfall DTM (VK2KFU)  "Those who don't understand security will suffer."

[TUHS] Short history of 'grep'

[Larry McVoy]

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:
> I'm still trying to get my around about how a program such as "egrep" 
> which handles complex patterns can be faster than one that doesn't...  It 
> seems to defeat all logic :-)
> 
> Is there a simple explanation, involving small words?  I've never really 
> looked at the theory.
> 
> -- 
> Dave Horsfall DTM (VK2KFU)  "Those who don't understand security will suffer."

-- 
---
Larry McVoy            	     lm at mcvoy.com             http://www.mcvoy.com/lm 

[TUHS] Short history of 'grep'

[jason-tuhs]

> I'm still trying to get my around about how a program such as "egrep" 
> which handles complex patterns can be faster than one that doesn't... 
> It seems to defeat all logic :-)
>
> Is there a simple explanation, involving small words?  I've never really 
> looked at the theory.

My assumption when I read it was that it was a typo/braino, that the 
intent was "fgrep" rather than "egrep".


  -Jason

[TUHS] Short history of 'grep'

[John Cowan]

Dave Horsfall scripsit:

> I'm still trying to get my around about how a program such as "egrep" 
> which handles complex patterns can be faster than one that doesn't...  It 
> seems to defeat all logic :-)

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 at ccil.org
               Si hoc legere scis, nimium eruditionis habes.

[TUHS] Short history of 'grep'

[Random832]

On Sat, Jan 30, 2016, at 21:06, jason-tuhs at shalott.net wrote:
> 
> > I'm still trying to get my around about how a program such as "egrep" 
> > which handles complex patterns can be faster than one that doesn't... 
> > It seems to defeat all logic :-)
> >
> > Is there a simple explanation, involving small words?  I've never really 
> > looked at the theory.
> 
> My assumption when I read it was that it was a typo/braino, that the 
> intent was "fgrep" rather than "egrep".

Wouldn't you have to know exactly what your keys look like?

[TUHS] Short history of 'grep'

[Mary Ann Horton]

It's not a typo.

When I tell this story to nontechical folks, I prefix it with the brief 
note that fgrep ought to be fastest, because it's simple, and egrep 
ought to be slowest, because it's complex, but in reality fgrep is 
slowest and egrep is fastest.  Otherwise the story makes no sense.

     Mary Ann

On 01/30/2016 06:06 PM, jason-tuhs at shalott.net wrote:
>
>> I'm still trying to get my around about how a program such as "egrep" 
>> which handles complex patterns can be faster than one that doesn't... 
>> It seems to defeat all logic :-)
>>
>> Is there a simple explanation, involving small words?  I've never 
>> really looked at the theory.
>
> My assumption when I read it was that it was a typo/braino, that the 
> intent was "fgrep" rather than "egrep".
>
>
>  -Jason
>

[TUHS] Short history of 'grep'

[John Cowan]

Mary Ann Horton scripsit:

> When I tell this story to nontechical folks, I prefix it with the
> brief note that fgrep ought to be fastest, because it's simple, and
> egrep ought to be slowest, because it's complex, but in reality
> fgrep is slowest and egrep is fastest.  

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 at ccil.org
After fixing the Y2K bug in an application:
        WELCOME TO <censored>
        DATE: MONDAK, JANUARK 1, 1900

[TUHS] Short history of 'grep'

[Tony Finch]

John Cowan <cowan at mercury.ccil.org> wrote:
> Dave Horsfall scripsit:
>
> > I'm still trying to get my around about how a program such as "egrep"
> > which handles complex patterns can be faster than one that doesn't...  It
> > seems to defeat all logic :-)
>
[...]
> 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.

Right. The relevant section in the article that started this thread says:

: 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 simplecharacter searches but was
: slower for complex search patterns (due to the high cost of build-ing the
: state machine that recognised the patterns).

The "putting theory into practice" refers to compiling the regex to a DFA,
rather than interpreting an NFA.

Russ Cox has a good summary of differing regex implementation techniques
at https://swtch.com/~rsc/regexp/regexp1.html

This makes me wonder how well-known was the technique of compiling to a
DFA, and whether it was widely implemented before awk, egrep, and lex.

Tony.
-- 
f.anthony.n.finch  <dot at dotat.at>  http://dotat.at/
Fair Isle, Faeroes: Southeast 6 to gale 8, veering southwest gale 8 to storm
10, becoming cyclonic later. Very rough, becoming high or very high. Rain or
squally showers. Moderate or poor.

[TUHS] Short history of 'grep'

[Tony Finch]

Mary Ann Horton <mah at mhorton.net> wrote:

> It's not a typo.
>
> When I tell this story to nontechical folks, I prefix it with the brief note
> that fgrep ought to be fastest, because it's simple, and egrep ought to be
> slowest, because it's complex, but in reality fgrep is slowest and egrep is
> fastest.  Otherwise the story makes no sense.

Does fgrep win if you are matching lots of fixed strings?

https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm

Tony.
-- 
f.anthony.n.finch  <dot at dotat.at>  http://dotat.at/
Trafalgar: North or northwest 4 or 5. Moderate or rough. Fair. Good.

[TUHS] Short history of 'grep'

[scj]

: 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

[TUHS] Short history of 'grep'

[Larry McVoy]

You guys really need to go look at gnu grep.  It blows away unix grep
in terms of performance.  

http://lists.freebsd.org/pipermail/freebsd-current/2010-August/019310.html

The guy writing that post did gnu grep.  He was also a guy at Intel that 
did all sorts of magic.  I've got a guy working for me, crazy smart guy,
his job at Intel was taking Haertel's code and dumbing it down so they 
had some chance of supporting it.

Read that post, Mike is one smart dude.

On Sat, Mar 05, 2016 at 12:48:19PM +1100, Dave Horsfall wrote:
> On Sun, 31 Jan 2016, Doug McIlroy wrote:
> 
> [...]
> 
> > That's the short story. In real life egrep overcomes the exponential by 
> > lazily constructing the machine--not generating a state until it is 
> > encountered in the parse, so no more than n states get constructed. It's 
> > a complex program, though, for the already fancy preprocessing must be 
> > interleaved with the parsing.
> 
> Many thanks; I think I understand a little better now...  It's been many 
> years since I majored in Computer Science :-)
> 
> -- 
> Dave Horsfall DTM (VK2KFU)  "Those who don't understand security will suffer."

-- 
---
Larry McVoy            	     lm at mcvoy.com             http://www.mcvoy.com/lm 

[TUHS] Short history of 'grep'

[Dave Horsfall]

On Sun, 31 Jan 2016, Doug McIlroy wrote:

[...]

> That's the short story. In real life egrep overcomes the exponential by 
> lazily constructing the machine--not generating a state until it is 
> encountered in the parse, so no more than n states get constructed. It's 
> a complex program, though, for the already fancy preprocessing must be 
> interleaved with the parsing.

Many thanks; I think I understand a little better now...  It's been many 
years since I majored in Computer Science :-)

-- 
Dave Horsfall DTM (VK2KFU)  "Those who don't understand security will suffer."

[TUHS] Short history of 'grep'

[Doug McIlroy]

Ken kindly tells me that both stories are right, though clearly
my impression that my query prompted Ken to write grep is wrong:

        i dont see any differences between our stories.
        you asked and i dug around and found it.

Would we have greps today, had that little incident not occurred?

Doug

[TUHS] Short history of 'grep'

[Doug McIlroy]

> I'm still trying to get my around about how a program such as "egrep"
> which handles complex patterns can be faster than one that doesn't

> Is there a simple explanation, involving small words?

First, the big-word explanation. Grep is implemented as a nondeterministic
finite automaton, egrep as a deterministic finite automaton. Theory folk 
abbreviate these terms to "NFA" and "DFA", but these are probably not
what you had in mind as "small words".

The way grep works is to keep a record of possible partial parsings
as it scans the subject text; it doesn't know which (if any) will
ultimately be the right one, hence "nondeterministic". For example, 
suppose grep seeks pattern '^a.*bbbc' in text 'a.*bbbbbbc'. When
it has read past 3 b's, the possible partial parses are 'a.*', 'a.*b',
'a.*bb' and 'a.*bbb'. If it then reads another b, it splits the
first partial parse into 'a.*' and 'a.*b', updates the next two
to 'a.*bb' and 'a.*bbb', and kills off the fourth. If instead it
reads a c, recognition is successful; if anything else, all partials 
are killed and recognition fails.

Egrep, by preprocessing the expression, produces separate code for
each of several possible states: "no b's", "1 b", 2 b's" and "3 bs".
When it's in state "1 b", for example, it switches on the next 
character into "2 b's" or fails, depending on whether the 
character is b or not--very fast. Grep, on the other hand, has to  
update all the live parses.

So if egrep is so fast, why do we have grep? One reason is that
grep only needs to keep a list of possible progress points
in the expression. This list can't be longer than the expression.
In egrep, though, each state is a subset of progress points.
The number of possible subsets is exponential in the length
of the expression, so the recognition machine that egrep constructs
before attempting the parse can explode--perhaps overflowing
memory, or perhaps taking so long in construction that grep
can finish its slow parse before egrep even begins its fast parse.

To revert to the words of theory folks, grep takes time O(m*n) and
space O(m) worst case, while egrep takes time and space O(2^m+n).
(2^m is an overestimate, but you get the idea.)

That's the short story. In real life egrep overcomes the exponential
by lazily constructing the machine--not generating a state until it
is encountered in the parse, so no more than n states get constructed.
It's a complex program, though, for the already fancy preprocessing 
must be interleaved with the parsing.

Egrep is a tour de force of classical computer science, and pays
off big on scanning big files. Still, there's a lot to say for 
the simple elegance of grep (and the theoretical simplicity
of nondeterministic automata). On small jobs it can often win.
And it is guaranteed to work in O(m) memory, while egrep may need
O(n). 

-------------------------------------------------

Ken Thompson invented the grep algorithm and published it in CACM.
A pointy-headed reviewer for Computing Reviews scoffed: why would
anybody want to use the method when a DFA could do the recognition
in time O(n)? Of course the reviewer overlooked the potentially
exponential costs of constructing a DFA.

Some years later Al Aho wrote the more complicated egrep in the 
expectation that bad exponential cases wouldn't happen in everyday life. 
But one did. This job took 30 seconds' preprocessing to prepare
for a fraction of a second's parsing. Chagrined, Al conceived
the lazy-evaluation trick to overcome the exponential and
achieved O(n) run time, albeit with a big linear constant.

In regard to the "short history of grep", I have always thought
my request that Ken liberate regular expressions from ed caused
him to write grep. I asked him one afternoon, but I can't remember
whether I asked in person or by email. Anyway, next morning I
got an email message directing me to grep. If Ken took it
from his hip pocket, I was unaware. I'll have to ask him.

Doug