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).
Pedro.
_______________________________________________
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"
