On Wed, Feb 10, 2016 at 8:08 AM, Pedro Giffuni <p...@freebsd.org> wrote:
> Hello; > > El 10/02/2016 a las 02:20, Hans Petter Selasky escribió: > >> On 01/19/16 17:09, Ryan Stone wrote: >> >>> On Tue, Jan 19, 2016 at 10:33 AM, Hans Petter Selasky < >>> hsela...@freebsd.org> >>> wrote: >>> >>> >>>> + qsort(lc->lro_mbuf_data, lc->lro_mbuf_count, sizeof(struct mbuf >>>> *), >>>> + &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 exhibit >> the so-called QuickSort worst case behaviour of O(N**2) sorting time. This >> 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=revision&revision=279663 > > 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 _______________________________________________ svn-src-head@freebsd.org mailing list https://lists.freebsd.org/mailman/listinfo/svn-src-head To unsubscribe, send any mail to "svn-src-head-unsubscr...@freebsd.org"
