Re: Patch for block write clustering

Emil Briggs (
Thu, 5 Mar 1998 01:10:00 -0500 (EST)

>I have similar patches I was playing with from 2.1.26 and also saw a massive
>improvement with IDE drives (although not at high at 600%) but was unable to
>get any major improvements with SCSI drives.

I havn't tried SCSI but I suspect that due to the large caches and the sorting
algorithms on most SCSI drives it might not help that much.

>Presumably the same situation may also exist when reading, but I'm not
>really sure how this can be improved... (I did think of creating a global
>request queue, and when >= n tasks are waiting or before m ticks, re-order
>and perform the reads? Doesn't sound very good to me).

It would be tricky to implement. Might be fun to try though.

>The other major concern I had was that if I had many many buffers to flush
>(say over 100MB) that the sort would take a non-trivial amount of time and
>actually worsen the situation. I actually wrote use-land code to test this
>idea by dumping the write-list from the previous bdflush and timing various
>sorts.... could this be an issue for machines with large amounts of buffers?
>(Assume worst case time to sort 30,000 elements?) There was also an issue of
>additional memory required to do all this, but that I'm sure can probably be
>worked around.

I don't think this should be a problem. We don't need to sort the full 30,000
at one shot -- a few hundred at a time should be enough to greatly reduce the head
movements and should keep the nonlinear scaling of the sort down to a reasonable
level. I'm not sure though if shell sort is the best algorithm to use here.
I havn't seen a rigorous analysis of shellsort -- but it is in place unlike
quicksort which was why I picked it.


To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to