Re: prio_tree generalization

[Werner Almesberger <wa@almesberger.net>]

Andrew Morton wrote:
> Offtopic, but that's a premature optmztn.

Hmm, maybe. But it's actually not so much more work to use a
tree than it is to use a linear list. Particularly prio_tree is
very light on its users, because - unlike with RB trees - you
don't have to code all the lookups.

It may actually be nice to have something like a set of
includable functions using some GET_INDEX macro also for RB
trees, to make the easy cases even easier to write.

> A disk isn't going to retire more than 100 requests/sec in practice, and
> the cost of an all-requests search is relatively small.

On admittedly not very impressive hardware (a 1.2 GHz Duron), I
see about 60-100 us processing time per request submission in a
random access test using kernel AIO, with elevators using mainly
RB trees, with nr_requests = 8192.

The 60 us are for my experimental elevator, the 100 us for
anticipatory, so most of that time really is spent in the
elevator.

So, a few ms per request don't seem too unlikely for a linear
search, combined with a larger-than-default queue. (It seems
that most people trying to optimize elevator performance are
using something in the nr_requests = 1000 range.)

- Werner

-- 
  _________________________________________________________________________
 / Werner Almesberger, Buenos Aires, Argentina         wa@almesberger.net /
/_http://www.almesberger.net/____________________________________________/