[TUHS] Unix gre, forgotten successor to grep (was: forth on early unix)

[andrew--- via TUHS]

gre was written by me, although these days, i use a local link to grep.

ken’s comment below is likely true now, but at the time gre was written,
it was not true. boyer-moore filtering, as i called it, made a substantial
difference. in fact, it saved (in a documented way) millions of dollars per year
in the 5ESS programming project (during the mid to late 1980s).

it is, of course, dependent on the string being searched for, but once that string
had a literal substring of length 4 or more, it definitively sped things up.
it all depends on the relative speed of CPU versus I/O efficiency.
i also published a paper on this in “Software Practice and Experience” with Dan Sunday.

> On Sep 23, 2025, at 10:40 AM, Ken Thompson via TUHS <tuhs at tuhs.org> wrote:
> 
> i think the plan9 grep is the fastest.
> it is grep, egrep, fgrep also.
> i think it is faster than boyer-moore.
> the whole program is a jit dfa
> 
>  read block
>  for c in block
>  {
>     s=s.state[c]
>     if s == nil do something occasionally
>  }
> 
> it is a very few cycles per byte. all of the
> time is reading a block. i cant imagine b/m
> could be faster. the best b/m could do is
> calculate the skip and then jump over
> bytes that you have already read.
> 
> 
> russ cox used it to do the (now defunct) code
> search in google.
> 
> 
> On Tue, Sep 23, 2025 at 5:14 AM Don Caldwell via TUHS <tuhs at tuhs.org> wrote:
> 
>> It was definitely Andrew Hume. While at Shannon Labs, he was promoting and
>> using it for some of his projects.
>> 
>> On Tue, Sep 23, 2025 at 12:59 AM Noel Hunt via TUHS <tuhs at tuhs.org> wrote:
>> 
>>> I will tentatively suggest that it was Andrew Hume. I suspect
>>> his major contribution was the addition of Boyer-Moore.
>>> 
>>> 
>>> On Tue, 23 Sept 2025 at 04:38, Thalia Archibald via TUHS <tuhs at tuhs.org>
>>> wrote:
>>> 
>>>> Spurred by the discussion on regular expressions in the Forth thread:
>>>> 
>>>> Unix V10 included a command named gre, which aimed to succeed grep,
>>> egrep,
>>>> and
>>>> fgrep.
>>>> 
>>>> Does anyone know anything about it? Who wrote it? Was it used anywhere
>> or
>>>> succeeded by anything? Was it connected to Plan 9 or Inferno?
>>>> 
>>>> From its man page:
>>>>> Gre supplants three classic programs, which are still available:
>>>>> Grep handles only ed(1)-like regular expressions. It uses \(\)
>> instead
>>>> of ().
>>>>> Egrep handles the same patterns as gre except for back-referencing
>> with
>>>> \1, \2, ...
>>>>> Fgrep handles no operators except newline (alternation).
>>>> 
>>>> https://www.tuhs.org/cgi-bin/utree.pl?file=V10/cmd/gre
>>>> https://www.tuhs.org/cgi-bin/utree.pl?file=V10/man/man1/gre.1
>>>> 
>>>> Thanks,
>>>> Thalia Archibald
>>>> 
>>> 
>>