Date: Sat, 28 May 2016 22:50:43 +0200 From: Hans Petter Selasky <hps@selasky.org> To: Pieter de Goeje <pieter@degoeje.nl>, src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org Subject: Re: svn commit: r300731 - head/sys/netinet Message-ID: <f6d804a5-c9d9-b50c-cd82-38d2d411ae13@selasky.org> In-Reply-To: <57492820.7080605@degoeje.nl> References: <201605261110.u4QBAW7W099643@repo.freebsd.org> <57492820.7080605@degoeje.nl>
next in thread | previous in thread | raw e-mail | index | archive | help
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
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?f6d804a5-c9d9-b50c-cd82-38d2d411ae13>