Date: Sat, 28 May 2016 07:09:52 +0200 From: Pieter de Goeje <pieter@degoeje.nl> To: Hans Petter Selasky <hselasky@FreeBSD.org>, src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org Subject: Re: svn commit: r300731 - head/sys/netinet Message-ID: <57492820.7080605@degoeje.nl> In-Reply-To: <201605261110.u4QBAW7W099643@repo.freebsd.org> References: <201605261110.u4QBAW7W099643@repo.freebsd.org>
next in thread | previous in thread | raw e-mail | index | archive | help
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. :-)
Regards,
Pieter de Goeje
10000 random keys
=================
x bubble
+ insert
+------------------------------------------------------------+
|+ |
|+ x |
|+ x |
|+ x |
|+ x x|
|A |A| |
+------------------------------------------------------------+
N Min Max Median Avg Stddev
x 5 0.13718 0.14187 0.13724 0.138166 0.0020715164
+ 5 0.02508 0.02525 0.02508 0.025114 7.6026311e-05
Difference at 95.0% confidence
-0.113052 +/- 0.00213774
-81.8233% +/- 1.54723%
(Student's t, pooled s = 0.00146577)
10000 pre-ordered keys
======================
x bubble
+ insert
+------------------------------------------------------------+
|+ x|
|+ x|
|+ x|
|+ x|
|+ x|
|A A|
+------------------------------------------------------------+
N Min Max Median Avg Stddev
x 5 0.05845 0.0585 0.05848 0.058478 1.9235384e-05
+ 5 2e-05 2e-05 2e-05 2e-05 3.2155494e-13
Difference at 95.0% confidence
-0.058458 +/- 1.9837e-05
-99.9658% +/- 0.0339221%
(Student's t, pooled s = 1.36015e-05)
10000 reverse-ordered keys
==========================
x bubble
+ insert
+------------------------------------------------------------+
|+ |
|+ |
|+ x |
|+ xx|
|+ xx|
|A MA|
+------------------------------------------------------------+
N Min Max Median Avg Stddev
x 5 0.06456 0.0647 0.06457 0.064598 5.8051701e-05
+ 5 0.05009 0.05012 0.05009 0.0501 1.4142136e-05
Difference at 95.0% confidence
-0.014498 +/- 6.16181e-05
-22.4434% +/- 0.095387%
(Student's t, pooled s = 4.22493e-05)
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?57492820.7080605>