Date: Thu, 11 Feb 2016 09:47:14 -0700 From: Warner Losh <imp@bsdimp.com> To: Pedro Giffuni <pfg@freebsd.org> Cc: Hans Petter Selasky <hps@selasky.org>, Ryan Stone <rysto32@gmail.com>, "src-committers@freebsd.org" <src-committers@freebsd.org>, "svn-src-all@freebsd.org" <svn-src-all@freebsd.org>, "svn-src-head@freebsd.org" <svn-src-head@freebsd.org> Subject: Re: svn commit: r294327 - in head/sys: dev/cxgb dev/cxgbe dev/e1000 dev/hyperv/netvsc dev/ixgbe dev/mxge netinet sys Message-ID: <CANCZdfpmYMGKJkX4uQR6Uet18cffJ4-uXxRSxfbe3Q6p2Pb48Q@mail.gmail.com> In-Reply-To: <56BB5280.5060609@FreeBSD.org> References: <201601191533.u0JFXSxf037804@repo.freebsd.org> <CAFMmRNz3uXim3H3-sGuBUBs45Jy8p260ywothgp4iFkUcnvnEw@mail.gmail.com> <56BAE4BC.9000105@selasky.org> <56BB5280.5060609@FreeBSD.org>
next in thread | previous in thread | raw e-mail | index | archive | help
On Wed, Feb 10, 2016 at 8:08 AM, Pedro Giffuni <pfg@freebsd.org> wrote: > Hello; > > El 10/02/2016 a las 02:20, Hans Petter Selasky escribi=C3=B3: > >> On 01/19/16 17:09, Ryan Stone wrote: >> >>> On Tue, Jan 19, 2016 at 10:33 AM, Hans Petter Selasky < >>> hselasky@freebsd.org> >>> wrote: >>> >>> >>>> + qsort(lc->lro_mbuf_data, lc->lro_mbuf_count, sizeof(struct mbu= f >>>> *), >>>> + &tcp_lro_mbuf_compare_header); >>>> >>>> >>> In the worst case, qsort() can take O(n**2) time and consume O(n) stack >>> space. Is there a DOS concern here? >>> >>> >> Hi, >> >> Our FreeBSD qsort() routine has been specifically modified to not exhibi= t >> the so-called QuickSort worst case behaviour of O(N**2) sorting time. Th= is >> is not documented in our source code, but here: >> >> http://cs.fit.edu/~pkc/classes/writing/samples/bentley93engineering.pdf >> >> So I think DOS w.r.t O(N**2) is not a valid consern. >> >> Thank you for your input Ryan. >> >> BTW: >> >> Drew Gallatin has tested our qsort() v.s. my mergesort() and found that: >> >> "It looks like mergesort is nearly 2x as expensive. (4.7% vs 2.5%)" >> >> > FWIW, our libc qsort() has an additional enhancement: > > http://svnweb.freebsd.org/base?view=3Drevision&revision=3D279663 > > In my measurements qsort(3) was now always faster than mergesort(3). If it is faster, is there any good reason to maintain both qsort and mergesort in the kernel then? Warner
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?CANCZdfpmYMGKJkX4uQR6Uet18cffJ4-uXxRSxfbe3Q6p2Pb48Q>