Can we see some numbers that support switching from the well known, and validated, qsort() to this private version of mergesort? If this is a win then we probably want an abstracted version of this to sit along side our qsort.

@gnn : Yes, Andrew is going to test it, probably next week.

In D4994#106361, @hselasky wrote:

@gnn : Yes, Andrew is going to test it, probably next week.

After running the latest version of the patch (with the fixed compare) for several days on internet facing hosts with ~90K connections, I cannot find much difference between the qsort and mergesort versions. Both aggregate at the same rate, and use roughly the same amount of CPU. Honestly, for our workloads, I'm quite happy with either.

I think choosing mergesort over qsort comes down to rstone's comments on the commit of the qsort version ("In the worst case, qsort() can take O(n**2) time and consume O(n) stack space. Is there a DOS concern here?")

If the performance is the same then I think using the tried and true algorithm wins out over putting a new one in specifically just for this case.

Hi,

@gnn

The reason we don't use a factored out mergesort() is that mergesort() needs a temporary working array, which it allocates using malloc(). Then it becomes very slow.

Given that this code is running in the fast path it makes sense to unroll/optimize away constants.

Did you have a look at the existing qsort() code v.s. this one?

BTW: Would it help if I factored out the sorting function to be a generic mergesort for pointers in libkern.h ?

For example:

void
mergesort_by_pointer(void ptr, void temp, unsigned max, compare_func_t);

--HPS

Have we tested the case where there is only a single flow, so all of the flowids are equal? That tends to be a very bad case for qsort.

@rstone

The entries are never equal due to the sequence number stamped on each mbuf. Is this also the case when the array appears already sorted?