On 02/11/16 17:47, Warner Losh wrote:
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?
No, I've abandoned the mergesort patch.
--HPS
_______________________________________________
svn-src-all@freebsd.org mailing list
https://lists.freebsd.org/mailman/listinfo/svn-src-all
To unsubscribe, send any mail to "svn-src-all-unsubscr...@freebsd.org"
