Skip to contentSkip to conversation

block: change sort order of elv_dispatch_sort

RFC In review Shaohua Li 2 participants 7 messages Dec 8, 2010 – Dec 9, 2010 Block layer

lore
Share & tools
lore

Shaohua Li

author
#0 lore raw

RFC 1/1 block: change sort order of elv_dispatch_sort

Change the sort order a little bit. Makes requests with sector above boundary in ascendant order, and requests with sector below boundary in descendant order. The goal is we have less disk spindle move.
For example, boundary is 7, we add sector 8, 1, 9, 2, 3, 4, 10, 12, 5, 11, 6 In the original sort, the sorted list is:
8, 9, 10, 11, 12, 1, 2, 3, 4, 5, 6
the spindle move is 8->12->1->6, total movement is 12*2 sectors with the new sort, the list is:
8, 9, 10, 11, 12, 6, 5, 4, 3, 2, 1
the spindle move is 8->12->6->1, total movement is 12*1.5 sectors

block/elevator.c +3 -3
index 2569512..1e01e49 100644
@@ -443,12 +443,12 @@ void elv_dispatch_sort(struct request_queue *q, struct request *rq)
 		if (blk_rq_pos(rq) >= boundary) {
 			if (blk_rq_pos(pos) < boundary)
 				continue;
+			if (blk_rq_pos(rq) >= blk_rq_pos(pos))
+				break;
 		} else {
-			if (blk_rq_pos(pos) >= boundary)
+			if (blk_rq_pos(rq) < blk_rq_pos(pos))
 				break;
 		}
-		if (blk_rq_pos(rq) >= blk_rq_pos(pos))
-			break;
 	}
 
 	list_add(&rq->queuelist, entry);
#1 lore raw
Quoted 10 lines · Shaohua Li

Change the sort order a little bit. Makes requests with sector above boundary in ascendant order, and requests with sector below boundary in descendant order. The goal is we have less disk spindle move.
For example, boundary is 7, we add sector 8, 1, 9, 2, 3, 4, 10, 12, 5, 11, 6 In the original sort, the sorted list is:
8, 9, 10, 11, 12, 1, 2, 3, 4, 5, 6
the spindle move is 8->12->1->6, total movement is 12*2 sectors with the new sort, the list is:
8, 9, 10, 11, 12, 6, 5, 4, 3, 2, 1
the spindle move is 8->12->6->1, total movement is 12*1.5 sectors

It was actually done this way on purpose, it's been a while since we have done two way elevators even outside the dispatch list sorting itself.

Do you have any results to back this change up? I'd argue that continuing to the end, sweeping back, and reading forwards again will be faster then doing backwards reads usually.

Signature · 1 line
Jens Axboe
author
#2 lore raw
Quoted 12 lines · Jens Axboe
Quoted 10 lines · Shaohua Li

Change the sort order a little bit. Makes requests with sector above boundary in ascendant order, and requests with sector below boundary in descendant order. The goal is we have less disk spindle move.
For example, boundary is 7, we add sector 8, 1, 9, 2, 3, 4, 10, 12, 5, 11, 6 In the original sort, the sorted list is:
8, 9, 10, 11, 12, 1, 2, 3, 4, 5, 6
the spindle move is 8->12->1->6, total movement is 12*2 sectors with the new sort, the list is:
8, 9, 10, 11, 12, 6, 5, 4, 3, 2, 1
the spindle move is 8->12->6->1, total movement is 12*1.5 sectors

Quoted 7 lines

It was actually done this way on purpose, it's been a while since we have done two way elevators even outside the dispatch list sorting itself.

Do you have any results to back this change up? I'd argue that continuing to the end, sweeping back, and reading forwards again will be faster then doing backwards reads usually.

No, have no data, that is why this is a RFC patch. Part reason is I don't know when we dispatch several requests to the list. Appears driver only takes one request one time. What kind of test do you suggest? I'm curious why the sweeping back is faster. It definitely needs more spindle move. is there any hardware trick here?

Thanks,
Shaohua

#3 lore raw
Quoted 17 lines · Shaohua Li
Quoted 16 lines · Jens Axboe
Quoted 10 lines · Shaohua Li

Change the sort order a little bit. Makes requests with sector above boundary in ascendant order, and requests with sector below boundary in descendant order. The goal is we have less disk spindle move.
For example, boundary is 7, we add sector 8, 1, 9, 2, 3, 4, 10, 12, 5, 11, 6 In the original sort, the sorted list is:
8, 9, 10, 11, 12, 1, 2, 3, 4, 5, 6
the spindle move is 8->12->1->6, total movement is 12*2 sectors with the new sort, the list is:
8, 9, 10, 11, 12, 6, 5, 4, 3, 2, 1
the spindle move is 8->12->6->1, total movement is 12*1.5 sectors

It was actually done this way on purpose, it's been a while since we have done two way elevators even outside the dispatch list sorting itself.

Quoted 6 lines
Quoted 3 lines

Do you have any results to back this change up? I'd argue that continuing to the end, sweeping back, and reading forwards again will be faster then doing backwards reads usually.

No, have no data, that is why this is a RFC patch. Part reason is I don't know when we dispatch several requests to the list. Appears driver only takes one request one time. What kind of test do you suggest?

Yes that is usually the case, it's mainly meant as a holding point for dispatch, or for requeue, or for request that don't give sort ordering. Or on io scheduler switches, for instance.

Quoted 2 lines

I'm curious why the sweeping back is faster. It definitely needs more spindle move. is there any hardware trick here?

The idea is that while the initial seek is longer, due to drive prefetch serving the latter half request series after the sweep is faster.

I know that classic OS books mentions this is a good method, but I don't think that has been the case for a long time.

Signature · 1 line
Jens Axboe
author
#4 lore raw
Quoted 21 lines · Jens Axboe
Quoted 20 lines · Shaohua Li
Quoted 19 lines · Jens Axboe
Quoted 10 lines · Shaohua Li

Change the sort order a little bit. Makes requests with sector above boundary in ascendant order, and requests with sector below boundary in descendant order. The goal is we have less disk spindle move.
For example, boundary is 7, we add sector 8, 1, 9, 2, 3, 4, 10, 12, 5, 11, 6 In the original sort, the sorted list is:
8, 9, 10, 11, 12, 1, 2, 3, 4, 5, 6
the spindle move is 8->12->1->6, total movement is 12*2 sectors with the new sort, the list is:
8, 9, 10, 11, 12, 6, 5, 4, 3, 2, 1
the spindle move is 8->12->6->1, total movement is 12*1.5 sectors

It was actually done this way on purpose, it's been a while since we have done two way elevators even outside the dispatch list sorting itself.

Do you have any results to back this change up? I'd argue that continuing to the end, sweeping back, and reading forwards again will be faster then doing backwards reads usually.

Quoted 7 lines
Quoted 3 lines

No, have no data, that is why this is a RFC patch. Part reason is I don't know when we dispatch several requests to the list. Appears driver only takes one request one time. What kind of test do you suggest?

Yes that is usually the case, it's mainly meant as a holding point for dispatch, or for requeue, or for request that don't give sort ordering. Or on io scheduler switches, for instance.

Have a test in a hacked way. I use modified noop iosched, and every time when noop tries to dispatch request, it dispatches all requests in its list. Test does random read. The result is actually quite stable. The changed order always gives slightly better throughput, but the improvement is quite small (<1%)

Quoted 8 lines
Quoted 2 lines

I'm curious why the sweeping back is faster. It definitely needs more spindle move. is there any hardware trick here?

The idea is that while the initial seek is longer, due to drive prefetch serving the latter half request series after the sweep is faster.

I know that classic OS books mentions this is a good method, but I don't think that has been the case for a long time.

Hmm, if this is sequential I/O, then requests already merged. if not, how could drive know how to do prefetch.

Thanks,
shaohua

#5 lore raw
Quoted 30 lines · Shaohua Li
Quoted 21 lines · Jens Axboe
Quoted 20 lines · Shaohua Li
Quoted 19 lines · Jens Axboe
Quoted 10 lines · Shaohua Li

Change the sort order a little bit. Makes requests with sector above boundary in ascendant order, and requests with sector below boundary in descendant order. The goal is we have less disk spindle move.
For example, boundary is 7, we add sector 8, 1, 9, 2, 3, 4, 10, 12, 5, 11, 6 In the original sort, the sorted list is:
8, 9, 10, 11, 12, 1, 2, 3, 4, 5, 6
the spindle move is 8->12->1->6, total movement is 12*2 sectors with the new sort, the list is:
8, 9, 10, 11, 12, 6, 5, 4, 3, 2, 1
the spindle move is 8->12->6->1, total movement is 12*1.5 sectors

It was actually done this way on purpose, it's been a while since we have done two way elevators even outside the dispatch list sorting itself.

Do you have any results to back this change up? I'd argue that continuing to the end, sweeping back, and reading forwards again will be faster then doing backwards reads usually.

Quoted 7 lines
Quoted 3 lines

No, have no data, that is why this is a RFC patch. Part reason is I don't know when we dispatch several requests to the list. Appears driver only takes one request one time. What kind of test do you suggest?

Yes that is usually the case, it's mainly meant as a holding point for dispatch, or for requeue, or for request that don't give sort ordering. Or on io scheduler switches, for instance.

Quoted 5 lines

Have a test in a hacked way. I use modified noop iosched, and every time when noop tries to dispatch request, it dispatches all requests in its list. Test does random read. The result is actually quite stable. The changed order always gives slightly better throughput, but the improvement is quite small (<1%)

First of all I think 1% is too close to call, unless your results are REALLY stable. Secondly, a truly random workload is not a good test case as requests are going to be all over the map anyway. For something more realistic (like your example, but of course not fully contig) it would be interesting to see.

Quoted 11 lines
Quoted 8 lines
Quoted 2 lines

I'm curious why the sweeping back is faster. It definitely needs more spindle move. is there any hardware trick here?

The idea is that while the initial seek is longer, due to drive prefetch serving the latter half request series after the sweep is faster.

I know that classic OS books mentions this is a good method, but I don't think that has been the case for a long time.

Hmm, if this is sequential I/O, then requests already merged. if not, how could drive know how to do prefetch.

Certainly, the requests are not going to look like in your example. I didn't take those literally, I was assuming you just meant increasing order on both sides. Once the drive has positioned the head, it is going to read more than just the single sector in that request. They do do read caching.

Signature · 1 line
Jens Axboe
author
#6 lore raw
Quoted 37 lines · Jens Axboe
Quoted 30 lines · Shaohua Li
Quoted 21 lines · Jens Axboe
Quoted 20 lines · Shaohua Li
Quoted 19 lines · Jens Axboe
Quoted 10 lines · Shaohua Li

Change the sort order a little bit. Makes requests with sector above boundary in ascendant order, and requests with sector below boundary in descendant order. The goal is we have less disk spindle move.
For example, boundary is 7, we add sector 8, 1, 9, 2, 3, 4, 10, 12, 5, 11, 6 In the original sort, the sorted list is:
8, 9, 10, 11, 12, 1, 2, 3, 4, 5, 6
the spindle move is 8->12->1->6, total movement is 12*2 sectors with the new sort, the list is:
8, 9, 10, 11, 12, 6, 5, 4, 3, 2, 1
the spindle move is 8->12->6->1, total movement is 12*1.5 sectors

It was actually done this way on purpose, it's been a while since we have done two way elevators even outside the dispatch list sorting itself.

Do you have any results to back this change up? I'd argue that continuing to the end, sweeping back, and reading forwards again will be faster then doing backwards reads usually.

Quoted 7 lines
Quoted 3 lines

No, have no data, that is why this is a RFC patch. Part reason is I don't know when we dispatch several requests to the list. Appears driver only takes one request one time. What kind of test do you suggest?

Yes that is usually the case, it's mainly meant as a holding point for dispatch, or for requeue, or for request that don't give sort ordering. Or on io scheduler switches, for instance.

Quoted 5 lines

Have a test in a hacked way. I use modified noop iosched, and every time when noop tries to dispatch request, it dispatches all requests in its list. Test does random read. The result is actually quite stable. The changed order always gives slightly better throughput, but the improvement is quite small (<1%)

Quoted 5 lines

First of all I think 1% is too close to call, unless your results are REALLY stable. Secondly, a truly random workload is not a good test case as requests are going to be all over the map anyway. For something more realistic (like your example, but of course not fully contig) it would be interesting to see.

Tried a random I/O read with block size range from 4k to 64k, I thought this is more realistic. The test result for the two different sort methods still shows slightly difference. I'll give up the patch unless there is better workload to try.

Thanks,
Shaohua