deadline-ioscheduler rb-tree sort

Hi,

This is something I whipped together the other day for testing the over head of the O(N) insert scan that the deadline io scheduler does. So instead of using a plain linked list, I adapted it to use an rb tree since that was already available with the generic implementation in the kernel.

Results are quite promising, overhead is down a lot. I'm not pushing this for inclusion, just sending it out so others can test etc. Patch is against 2.5.45.

===== drivers/block/ll_rw_blk.c 1.135 vs edited =====

@@ -2175,8 +2183,8 @@
 	queue_nr_requests = (total_ram >> 9) & ~7;
 	if (queue_nr_requests < 16)
 		queue_nr_requests = 16;
-	if (queue_nr_requests > 128)
-		queue_nr_requests = 128;
+	if (queue_nr_requests > 512)
+		queue_nr_requests = 512;
 
 	batch_requests = queue_nr_requests / 8;
 	if (batch_requests > 8)

===== drivers/block/deadline-iosched.c 1.9 vs edited =====

Jens Axboe

I completed a couple of runs of tiobench, and thought I would share a few notes. The test was a 128 thread tiobench, using varying queue
sizes: ranging from 128 per list (the default), 512 per list, and 4096 per list. IO performance generally increased with bigger queues, for now lets just look at profiles though.

Testing was done on a 9GB SCSI drive, SMP machine, 512megs of RAM. File system used was ext2. Kernel used was 2.5.45-vanilla with and without the deadline-rbtree patch.

With 128 requests per list, the stock kernel has the following relevant oprofile results:

c0236000 1972     0.0233741   deadline_merge
c0232cd0 683      0.00809559  __make_request
c0235f30 315      0.00373369  deadline_find_hash
c02364a0 283      0.0033544   deadline_add_request
c0236310 248      0.00293954  deadline_move_requests
c02363b0 196      0.00232319  deadline_next_request

rbtree version has the following highscore list:

c0232cd0 560      0.00680737  __make_request
c02361d0 267      0.00324566  deadline_rb_find
c0235f80 234      0.00284451  deadline_hash_add
c0235fe0 225      0.0027351   deadline_hash_find
c0236100 204      0.00247983  deadline_rb_add
c0236660 157      0.00190849  deadline_next_request

No regression when compared to the stock settings, in fact it looks pretty darn good.

With 512 requests per list, stock kernel scores:

c0236000 6094     0.0860452   deadline_merge
c0232cd0 714      0.0100814   __make_request
c0235f30 545      0.00769521  deadline_find_hash
c02364a0 307      0.00433474  deadline_add_request
c0236310 234      0.003304    deadline_move_requests
c02363b0 163      0.0023015   deadline_next_request

and rbtree version:

c0232cd0 665      0.00950867  __make_request
c0235fe0 350      0.00500456  deadline_hash_find
c02361d0 287      0.00410374  deadline_rb_find
c0235f80 236      0.0033745   deadline_hash_add
c0236100 197      0.00281685  deadline_rb_add
c0236660 121      0.00173015  deadline_next_request

stock kernel shows worse behaviour with 512 requests vs 128, rbtree version is basically the same. Final test was with 4096 requests per list. stock kernel highscore:

c0236000 11753    0.228824    deadline_merge
c0232cd0 707      0.0137649   __make_request
c0235f30 625      0.0121684   deadline_find_hash
c02364a0 309      0.00601604  deadline_add_request
c02363b0 134      0.0026089   deadline_next_request

and rbtree for 4096 requests:

c0232cd0 1152     0.0163495   __make_request
c0235fe0 931      0.013213    deadline_hash_find
c02361d0 523      0.00742254  deadline_rb_find
c0235f80 424      0.00601751  deadline_hash_add
c0236100 293      0.00415832  deadline_rb_add
c0236660 166      0.00235591  deadline_next_request

Now the back merge hash table is getting too small, obviously. It's worth nothing that with 4096 requests, deadline_merge in the stock kernel is the biggest cpu user in the kernel apart from copy_to/from_user and mark_offset_tsc.

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.

Full profile numbers are available from:

http://www.kernel.org/pub/linux/kernel/people/axboe/misc/

Jens Axboe

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?

Just a few comments about data structures - not important.

Technically I think that a priority queue, i.e. a heap (partially ordered tree) is sufficient for the request queue. I don't know the request queue code well enough to be sure, though.

Both heaps and trees are O(N log N), the difference being that an rbtree does a bit more constant-time work to balance the tree while maintaining a stricter ordering.

If it was worth it (I suspect not), you can make a data structure which has O(1) amortised insertion time for a number of common cases, such as runs of ascending block numbers. Seems a likely pattern for a filesystem...

Implementing the latter would likely be a lot of work for little gain though.

-- Jamie

I looked into that as well, and I do have a generic binomial heap implementation that I plan on test as well.

Fibonacci heaps, for instance. I looked into that as well. However, it's actually more important to have (if possible) O(1) extraction than insert. Extraction is typically run from interrupt context, when a driver wants to requeue more requests because it has completed one (or some). That was a worry with the rbtree solution. The linked list may have had sucky O(N) insert, but extraction was a nice O(1). So far I haven't been able to notice any regression in this area, regardless.

Indeed

Jens Axboe

There's a skip list variant which offers O(1) extraction from the head of the list, and probabilistic O(log n) insertion, fwiw.

-- Jamie

Agree

Indeed

Well yes, cue long story about vm flushing acting up with longer queues...

I think there are two sides to this. One is that some devices just dont ever need long queues. For a floppy and cdrom, it's just a huge waste of memory, they should always just limited to a few entries. Some devices might benefit from nice long queues, we want to give them the option of having them. That's the hardware side, and I suspect such hints are best passed in by the drivers. Probably by specifying device class.

Then there's the vm side, where we don't want to waste large amounts of memory on requests... So based on the class of a device, select a default depth that fits with the current system.

But yes, definitely needs to be tweakable.

Jens Axboe