Btrfs: replace raid56 stripe bubble sort with insert sort
PATCH 1/1 Btrfs: replace raid56 stripe bubble sort with insert sort
Insert sort are generaly perform better then bubble sort, by have less iterations on avarage.
That version also try place element to right position instead of raw swap.
I'm not sure how many stripes per bio raid56, btrfs try to store (and try to sort).
So, that a bit shorter just in the name of a great justice.
--- fs/btrfs/volumes.c | 29 ++++++++++++----------------- 1 file changed, 12 insertions(+), 17 deletions(-)
fs/btrfs/volumes.c +12 -17
@@ -5317,29 +5317,24 @@ static inline int parity_smaller(u64 a, u64 b)return a > b; } -/* Bubble-sort the stripe set to put the parity/syndrome stripes last */ +/* Insertion-sort the stripe set to put the parity/syndrome stripes last */ static void sort_parity_stripes (struct btrfs_bio *bbio,int num_stripes) {struct btrfs_bio_stripe s; -int i; +int i, j;u64 l; -int again =1 ; -while (again) { - again =0 ; -for (i =0 ; i < num_stripes -1 ; i++) { -if (parity_smaller (bbio->raid_map[i], - bbio->raid_map[i+1 ])) { - s = bbio->stripes[i]; - l = bbio->raid_map[i]; - bbio->stripes[i] = bbio->stripes[i+1 ]; - bbio->raid_map[i] = bbio->raid_map[i+1 ]; - bbio->stripes[i+1 ] = s; - bbio->raid_map[i+1 ] = l; - - again =1 ; - } +for (i =1 ; i < num_stripes; i++) { + s = bbio->stripes[i]; + l = bbio->raid_map[i]; +for (j = i -1 ; j >=0 ; j--) { +if (!parity_smaller (bbio->raid_map[j], l)) +break ; + bbio->stripes[j+1 ] = bbio->stripes[j]; + bbio->raid_map[j+1 ] = bbio->raid_map[j]; } + bbio->stripes[j+1 ] = s; + bbio->raid_map[j+1 ] = l; } }
Signature · 1 line
2.15.1
Quoted 7 lines · Timofey Titovets
Insert sort are generaly perform better then bubble sort, by have less iterations on avarage.
That version also try place element to right position instead of raw swap.I'm not sure how many stripes per bio raid56,
btrfs try to store (and try to sort).
If you don't know it, besides unlikely to be doing the best possible thing here, you might actually make things worse or not offering any benefit. IOW, you should know it for sure before submitting such changes.
You should know if the number of elements to sort is big enough such that an insertion sort is faster than a bubble sort, and more importantly, measure it and mention it in the changelog. As it is, you are showing lack of understanding of the code and component you are touching, and leaving many open questions such as how faster this is, why insertion sort and not a quick/merge/heap/whatever sort, etc.
Quoted 60 lines
So, that a bit shorter just in the name of a great justice.
Signed-off-by Timofey Titovets <[email protected]>--- fs/btrfs/volumes.c | 29 ++++++++++++----------------- 1 file changed, 12 insertions(+), 17 deletions(-)fs/btrfs/volumes.c +12
-18@@ -5317,29 +5317,24 @@ static inline int parity_smaller(u64 a, u64 b)return a > b; } -/* Bubble-sort the stripe set to put the parity/syndrome stripes last */ +/* Insertion-sort the stripe set to put the parity/syndrome stripes last */ static void sort_parity_stripes (struct btrfs_bio *bbio,int num_stripes) {struct btrfs_bio_stripe s; -int i; +int i, j;u64 l; -int again =1 ; -while (again) { - again =0 ; -for (i =0 ; i < num_stripes -1 ; i++) { -if (parity_smaller (bbio->raid_map[i], - bbio->raid_map[i+1 ])) { - s = bbio->stripes[i]; - l = bbio->raid_map[i]; - bbio->stripes[i] = bbio->stripes[i+1 ]; - bbio->raid_map[i] = bbio->raid_map[i+1 ]; - bbio->stripes[i+1 ] = s; - bbio->raid_map[i+1 ] = l; - - again =1 ; - } +for (i =1 ; i < num_stripes; i++) { + s = bbio->stripes[i]; + l = bbio->raid_map[i]; +for (j = i -1 ; j >=0 ; j--) { +if (!parity_smaller (bbio->raid_map[j], l)) +break ; + bbio->stripes[j+1 ] = bbio->stripes[j]; + bbio->raid_map[j+1 ] = bbio->raid_map[j]; } + bbio->stripes[j+1 ] = s; + bbio->raid_map[j+1 ] = l; } } --2.15.1
--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Signature · 3 lines
Filipe David Manana, “Whether you think you can, or you think you can't — you're right.”
2018-01-03 14:40 GMT+03:00 Filipe Manana <[email protected]>:
Quoted 24 lines · Timofey Titovets
Quoted 7 lines
Insert sort are generaly perform better then bubble sort, by have less iterations on avarage.
That version also try place element to right position instead of raw swap.I'm not sure how many stripes per bio raid56, btrfs try to store (and try to sort).
If you don't know it, besides unlikely to be doing the best possible thing here, you might actually make things worse or not offering any benefit. IOW, you should know it for sure before submitting such changes.
You should know if the number of elements to sort is big enough such that an insertion sort is faster than a bubble sort, and more importantly, measure it and mention it in the changelog. As it is, you are showing lack of understanding of the code and component you are touching, and leaving many open questions such as how faster this is, why insertion sort and not a quick/merge/heap/whatever sort, etc.
--
Filipe David Manana,
Quoted 1 line
“Whether you think you can, or you think you can't — you're right.”
Sorry, you are right,
I must do some tests and investigations before send a patch. (I just try believe in some magic math things).
Input size depends on number of devs,
so on small arrays, like 3-5 no meaningful difference.
Example: raid6 (with 4 disks) produce many stripe line addresses like:
1. 4641783808 4641849344 4641914880 18446744073709551614
2. 4641652736 4641718272 18446744073709551614 4641587200
3. 18446744073709551614 4636475392 4636540928 4636606464
4. 4641521664 18446744073709551614 4641390592 4641456128
For that count of elements any sorting algo will work fast enough.
Let's, consider that addresses as random non-repeating numbers.
We can use tool like Sound Of Sorting (SoS) to make some easy to interpret tests of algorithms.
(Sorry, no script to reproduce, as SoS not provide a cli, just hand made by run SoS with different params).
Table (also in attach with source data points):
Sort_algo |Disk_num |3 |4 |6 |8 |10 |12 |14 |AVG Bubble |Comparasions |3 |6 |15 |28 |45 |66 |91 |36,2857142857143 Bubble |Array_Accesses |7,8 |18,2 |45,8 |81,8 |133,4 |192 |268,6 |106,8 Insertion |Comparasions |2,8 |5 |11,6 |17 |28,6 |39,4 |55,2 |22,8 Insertion |Array_Accesses |8,4 |13,6 |31 |48,8 |80,4 |109,6 |155,8 |63,9428571428571
i.e. on Size like 3-4 no much difference,
Insertion sort will work faster on bigger arrays (up to 1.7x for 14 disk array).
Does that make a sense?
I think yes, i.e. in any case that are several dozen machine instructions. Which can be used elsewhere.
P.S. For heap sort, which are also available in kernel by sort(), That will to much overhead on that small number of devices, i.e. heap sort will show a profit over insert sort at 16+ cells in array.
/* Snob mode on */P.S.S.
Heap sort & other like, need additional memory,
so that useless to compare in our case,
but they will works faster, of course.
/* Snob mode off */
Thanks.
Signature · 2 lines
Have a nice day, Timofey.
Filipe Manana
NAKQuoted 40 lines · Timofey Titovets
2018-01-03 14:40 GMT+03:00 Filipe Manana <[email protected]>:
Quoted 24 lines · Timofey Titovets
Quoted 7 lines
Insert sort are generaly perform better then bubble sort, by have less iterations on avarage.
That version also try place element to right position instead of raw swap.I'm not sure how many stripes per bio raid56, btrfs try to store (and try to sort).
If you don't know it, besides unlikely to be doing the best possible thing here, you might actually make things worse or not offering any benefit. IOW, you should know it for sure before submitting such changes.
You should know if the number of elements to sort is big enough such that an insertion sort is faster than a bubble sort, and more importantly, measure it and mention it in the changelog. As it is, you are showing lack of understanding of the code and component you are touching, and leaving many open questions such as how faster this is, why insertion sort and not a quick/merge/heap/whatever sort, etc.
--
Filipe David Manana,Quoted 1 line
“Whether you think you can, or you think you can't — you're right.”
Sorry, you are right,
I must do some tests and investigations before send a patch. (I just try believe in some magic math things).Input size depends on number of devs,
so on small arrays, like 3-5 no meaningful difference.Example: raid6 (with 4 disks) produce many stripe line addresses like:
1. 4641783808 4641849344 4641914880 18446744073709551614
2. 4641652736 4641718272 18446744073709551614 4641587200
3. 18446744073709551614 4636475392 4636540928 4636606464
4. 4641521664 18446744073709551614 4641390592 4641456128
Quoted 6 lines
For that count of elements any sorting algo will work fast enough.
Let's, consider that addresses as random non-repeating numbers.
We can use tool like Sound Of Sorting (SoS) to make some easy to interpret tests of algorithms.
Nack.
My point was about testing in the btrfs code and not somewhere else. We can all get estimations from CS books, websites, etc for multiple algorithms for different input sizes. And these are typically comparing the average case, and while some algorithms perform better than others in the average case, things can get reversed in the worst case (heap sort vs quick sort iirc, better in worst case but usually worse in the average case).
What matters is in the btrfs context - that where things have to be measured.
Quoted 20 lines
(Sorry, no script to reproduce, as SoS not provide a cli, just hand made by run SoS with different params).
Table (also in attach with source data points):
Sort_algo |Disk_num |3 |4 |6 |8 |10 |12 |14 |AVG Bubble |Comparasions |3 |6 |15 |28 |45 |66 |91 |36,2857142857143 Bubble |Array_Accesses |7,8 |18,2 |45,8 |81,8 |133,4 |192 |268,6 |106,8 Insertion |Comparasions |2,8 |5 |11,6 |17 |28,6 |39,4 |55,2 |22,8 Insertion |Array_Accesses |8,4 |13,6 |31 |48,8 |80,4 |109,6 |155,8|63,9428571428571
i.e. on Size like 3-4 no much difference,
Insertion sort will work faster on bigger arrays (up to 1.7x for 14 disk array).Does that make a sense?
I think yes, i.e. in any case that are several dozen machine instructions. Which can be used elsewhere.
Quoted 7 lines
P.S. For heap sort, which are also available in kernel bysort(), That will to much overhead on that small number of devices, i.e. heap sort will show a profit over insert sort at 16+ cells in array./* Snob mode on */
P.S.S.
Heap sort & other like, need additional memory,
Yes... My point in listing the heap sort and other algorithms was not meant to propose using any of them but rather for you to explain why insertion sort and not something else.
And I think you are confusing heap sort with merge sort. Merge sort is the one that requires extra memory.
Quoted 8 lines
so that useless to compare in our case,
but they will works faster, of course.
/* Snob mode off */Thanks.
--
Have a nice day,
Timofey.
Signature · 3 lines
Filipe David Manana, “Whether you think you can, or you think you can't — you're right.”