svn commit: r300731 - head/sys/netinet

[Hans Petter Selasky]

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