Re: Making diff(1) of linux kernels faster

[Marcelo Tosatti]

On Wed, 17 Oct 2001, Andrea Arcangeli wrote:

> On Wed, Oct 17, 2001 at 11:21:03AM -0700, Linus Torvalds wrote:
> > 
> > On Wed, 17 Oct 2001, Marcelo Tosatti wrote:
> > > >
> > > > And I've for a long time thought about adding a "readahead()" system call.
> > > > There are just too many uses for it, it has come up in many different
> > > > areas..
> > >
> > > There is a paper on USENIX 2001 which does implement directory readahead
> > > and it shows huge improvements for some workload.
> > 
> > Hmm.. The implementation is trivial, it's really just a simple 3-line
> > while-loop, with the rest of the code just doing argument checking etc.
> > 
> > Attached is the kernel diff ("ra-diff") along with a stupid program
> > ("preread.c"), cribbed mostly from Pauls first patch to use it to pre-read
> > a while tree.
> > 
> > It took much longer to compile the kernel and reboot, and write the
> > test-program than it did to write the patch itself ;)
> > 
> > It walks the whole kernel tree in 0.2 seconds of CPU-time on my machine
> > (of course, if it actually needs to start IO, the 0.2 seconds becomes 0.3
> > seconds of CPU time and almost a minute and a half of wall-clock.
> > Anyway, it clearly isn't a CPU-hog like doing a real "read" would have
> > been).
> 
> I think with directory readahead Marcelo meant a transparent kernel
> heuristic in the readdir path. ext2_get_page is completly synchronous
> and it's reading one page at time, that's bad but it can be improved
> transparently to userspace, just like we do with the files, and also
> like the old code was doing before the directory in pagecache IIRC.

Exactly. 

Btw, the USENIX 2001 paper is called "Design and Implementation of a
Predictive File Prefetching Algorithm".

They have a Linux implementation of their complex prediction algo, but I
think directory readahead itself makes sense for most stuff.