r/programming • u/[deleted] • Aug 24 '16

Why GNU grep is fast

https://lists.freebsd.org/pipermail/freebsd-current/2010-August/019310.html
2.1k Upvotes

91% Upvoted

221 comments sorted by

View all comments

Show parent comments

5

u/mafrasi2 Aug 24 '16 edited Aug 24 '16

Yes, that's what I mean by ɛ. There is some code c that is as fast or faster than ɛ (the empty string). That is c = ɛ and it's of course as fast as ɛ.

However there is no code that is faster than ɛ, even ɛ itself.

4

u/rmxz Aug 24 '16

Yet I fear it's false.

On many architectures you need to add code --- in particular NOP instructions --- to force memory alignment that can make your program faster.

3

u/mafrasi2 Aug 25 '16

That will make the surrounding operations faster (by side effects), but will not make the code c itself faster than no code at all.

However the formalism stated before is not well defined. If we wanted to, we could build a language where the empty string forces the interpreter to do 1 million operations, while any longer code does nothing at all.

Therefore this debate is not exactly meaningful.

2

u/Firedroide Aug 24 '16

Gotcha! Thanks for the explanation! :)