Hello Andrew,
    About a year ago I told you I would get you some more information
about a problem I was seeing that might be in the Linux VM or ext{2,3}
code.  Well I finally have it!!  Sorry it took me so long :-)
    Given all you have to do with 2.6, I suspect this is not a good
time for you to look at this.  I am going to CC linux-kernel and hope
that someone over there finds this interesting.  I am sending it to
you not because I expect you to look at it right now, but because I
think it makes an interesting testcase for FS development.  I hope
it can be of some use to you.
    The attached program implements an external sort algorithm.
External sorting is a way to sort data that is too large to fit into
memory.  Instead of moving the data around in memory, it moves data
around on disk.  The algorithm is based on mergesort.
    All the external sort algorithms I found in books assumed the
data was stored on magnetic tape, and would repeatedly stream 
through it.  I designed this one with the assumption that the data
was on disk, and tried to optimize the access patterns to take
advantage of the file system caching.  Unfortunatly I do not think
the cache is working as well as it could be.
    For example, I have a laptop with 288M of ram, running the kernel
that came with fedora-core1.  I run the attached program as:

  ./exsort 3000000 300000

Which means create a file with 3,000,000 records, with each group
of 300,000 records already in sorted order.  This file ends up
being about 235M.  The sort algorithm needs a temporary file with
will grow to about 1/2 the size of the input file, but only at
the end of the run.  For most of the run the temp file is smaller
than this.  So for most of the run both files will fit into the
memory of the machine.  Thus I would expect the program to run
quickly, because it will not need to touch the disk.  Things are
in cache.  This is not what I see.  Instead the program seems to
be very much disk bound.  I dont know if this indicates a problem
in the kernel or if I am just expecting too much from the cache.
But I think it makes an interesting testcase.
    I have not tested this with a 2.6 kernel.  I ran this program
on ext3.  I have tested a similar program on ext2 and ext3.  It
runs better on ext2 since the journal is not there, but it is
still not as fast as I think it should be.
    The program is attached.  I hope you find it useful, and I would
love go hear your opinions about what it might be doing to the VM & FS.

Thanks,

Jim