svn commit: r300731 - head/sys/netinet

[Pieter de Goeje]

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)