svn commit: r294327 - in head/sys: dev/cxgb dev/cxgbe dev/e1000 dev/hyperv/netvsc dev/ixgbe dev/mxge netinet sys

[Hans Petter Selasky]

On 02/11/16 17:47, Warner Losh wrote:
> On Wed, Feb 10, 2016 at 8:08 AM, Pedro Giffuni <pfg at 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 <
>>>> hselasky at 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