From owner-svn-src-all@freebsd.org Sat May 28 20:47:25 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 84B1FB4EBB6; Sat, 28 May 2016 20:47:25 +0000 (UTC) (envelope-from hps@selasky.org) Received: from mail.turbocat.net (mail.turbocat.net [IPv6:2a01:4f8:d16:4514::2]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client did not present a certificate) by mx1.freebsd.org (Postfix) with ESMTPS id 522E9168D; Sat, 28 May 2016 20:47:25 +0000 (UTC) (envelope-from hps@selasky.org) Received: from laptop015.home.selasky.org (unknown [62.141.129.119]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by mail.turbocat.net (Postfix) with ESMTPSA id D48721FE024; Sat, 28 May 2016 22:47:21 +0200 (CEST) Subject: Re: svn commit: r300731 - head/sys/netinet To: Pieter de Goeje , src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org References: <201605261110.u4QBAW7W099643@repo.freebsd.org> <57492820.7080605@degoeje.nl> From: Hans Petter Selasky Message-ID: Date: Sat, 28 May 2016 22:50:43 +0200 User-Agent: Mozilla/5.0 (X11; FreeBSD amd64; rv:45.0) Gecko/20100101 Thunderbird/45.0 MIME-Version: 1.0 In-Reply-To: <57492820.7080605@degoeje.nl> Content-Type: text/plain; charset=windows-1252; format=flowed Content-Transfer-Encoding: 7bit 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 20:47:25 -0000 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