On 05/28/16 07:09, Pieter de Goeje wrote:
Hi,
Replacing the bubble sort with insertion sort gives an 80% reduction in
runtime on average (with randomized keys) for small partitions.
If the keys are pre-sorted, insertion sort runs in linear time, and even
if the keys are reversed, insertion sort is faster than bubble sort,
although not by much. See below for measurements.
Insertion sort tested:
for (x = 1; x < size; x++) {
temp = parray[x];
for( y = x; y > 0 && temp.seq < parray[y - 1].seq; y--) {
parray[y] = parray[y - 1];
}
parray[y] = temp;
}
Like bubble sort, insertion sort is O(N^2) in the worst case (reversed
keys), but it is much faster on average because it is an adaptive sort
unlike bubble sort.
The tests were run outside of the kernel, with a proxied struct
lro_mbuf_sort which consisted of a struct with seq as its only member.
The benchmarks were run in isolation on the bubble/insertion sort only.
I didn't have time to test this with the full radix sort, but I expect
that the cutoff value of 12 could be raised slightly after replacing the
bubble sort.
I did verify that the improvements in runtime still hold for very small
number of keys (12), but I didn't include these results below.
Assuming I've done my work correctly, you should be able to just drop in
the code above. :-)
Hi,
I've managed to reproduce your findings with random data sets and
created the following review:
https://reviews.freebsd.org/D6619
Thank you!
--HPS
_______________________________________________
svn-src-all@freebsd.org mailing list
https://lists.freebsd.org/mailman/listinfo/svn-src-all
To unsubscribe, send any mail to "svn-src-all-unsubscr...@freebsd.org"
