Re: rbtree scores (was Re: [patch] deadline-ioscheduler rb-tree sort)

[Andrew Morton]

Jens Axboe wrote:
> 
> As expected, the stock version O(N) insertion scan really hurts. Even
> with 128 requests per list, rbtree version is far superior. Once bigger
> lists are used, there's just no comparison whatsoever.
> 

Jens,  the tree just makes sense.

Remember that we added the blk_grow_request_list() thing to 2.4 for
the Dolphin SCI and other high-end hardware.  High throughput, long
request queue, uh-oh.  Probably they're not using the stock merge/insert
engine, but I bet someone will want to (Hi, Bill).

And we do know that for some classes of workloads, a larger request
queue is worth a 10x boost in throughput.

The length of the request queue is really a very important VM and
block parameter.  Varying it will have much less impact on the VM than
it used to, but it is still there...

When we get on to making the block tunables tunable, request queue
length should be there, and we will be needing that tree.

Have I convinced you yet?