From owner-svn-src-all@freebsd.org Sat May 28 05:17:27 2016 Return-Path: Delivered-To: svn-src-all@mailman.ysv.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:1900:2254:206a::19:1]) by mailman.ysv.freebsd.org (Postfix) with ESMTP id 073FCB4D080; Sat, 28 May 2016 05:17:27 +0000 (UTC) (envelope-from pieter@degoeje.nl) Received: from degoeje.nl (degoeje.nl [81.169.238.128]) by mx1.freebsd.org (Postfix) with ESMTP id BE3C71F11; Sat, 28 May 2016 05:17:26 +0000 (UTC) (envelope-from pieter@degoeje.nl) Received: from [130.89.165.91] (nox.student.utwente.nl [130.89.165.91]) by degoeje.nl (Postfix) with ESMTPSA id 11C3415C0035; Sat, 28 May 2016 07:09:54 +0200 (CEST) Subject: Re: svn commit: r300731 - head/sys/netinet To: Hans Petter Selasky , src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org References: <201605261110.u4QBAW7W099643@repo.freebsd.org> From: Pieter de Goeje Message-ID: <57492820.7080605@degoeje.nl> Date: Sat, 28 May 2016 07:09:52 +0200 User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:38.0) Gecko/20100101 Thunderbird/38.7.2 MIME-Version: 1.0 In-Reply-To: <201605261110.u4QBAW7W099643@repo.freebsd.org> Content-Type: text/plain; charset=windows-1252; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Status: No, score=-1.0 required=3.5 tests=ALL_TRUSTED autolearn=ham autolearn_force=no version=3.4.0 X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on degoeje.nl X-BeenThere: svn-src-all@freebsd.org X-Mailman-Version: 2.1.22 Precedence: list List-Id: "SVN commit messages for the entire src tree \(except for " user" and " projects" \)" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sat, 28 May 2016 05:17:27 -0000 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)