Great article, really makes you think about O(n) substring searching doesn't it?
It would've been nice to drill down why mmap makes a difference in particular, why not use something like lseek to skip characters?
It would've been nice to drill down why mmap makes a difference in particular, why not use something like lseek to skip characters?
Also, if you're reading from a file with lseek() and read(), you have to marshall data into the struct the kernel expects, make the syscall, and the kernel copies the data into the user-space buffer you provide. If you're reading from a file with mmap(), the page cache just appears in your address-space, no copying necessary.
On the other hand, I was curious why the default had changed from "use mmap" to "don't use mmap". Turns out, the grep 2.6.3 documentation states:
--mmap: This option is ignored for backwards compatibility. It used to read input with the `mmap' system call, instead of the default `read' system call. On modern systems, `--mmap' rarely if ever yields better performance.
Then again, hard drives return minimum sized blocks of data anyway, which is sized in kilobytes. So I'm guessing the "skipping" is a performance benefit only as so far as user space goes.
One would really have to grep a long string to be able to skip more than a block/page!