Messages in this thread | | | Date | Fri, 01 Nov 2002 11:34:03 -0800 | From | Andrew Morton <> | Subject | Re: rbtree scores (was Re: [patch] deadline-ioscheduler rb-tree sort) |
| |
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? - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
| |