Re: [PATCH] low performance of lib/sort.c , kernel 2.6.18

From: Matt Mackall
Date: Thu Sep 28 2006 - 18:35:43 EST

On Thu, Sep 28, 2006 at 11:18:45PM +0800, keios wrote:
> It is a non-standard heap-sort algorithm implementation because the
> index of child node is wrong . The sort function still outputs right
> result, but the performance is O( n * ( log(n) + 1 ) ) , about 10% ~
> 20% worse than standard algorithm .
> Signed-off-by: keios <>

Was a bit mystified by this as your patch matches what I've got
in my userspace test harness from 2003.

Here's what I submitted, which is almost the same as yours:

Then Zou Nan hai sent Andrew a fix for an off-by-one bug here (merged
with my patch):

..which introduced the performance regression.

And then I subsequently tweaked my local copy for use in another
project, coming up with your version.

So this passes my test harness just fine (for both even and odd array

Acked-by: Matt Mackall <mpm@xxxxxxxxxxx>

Mathematics is the supreme nostalgia of our time.
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at
Please read the FAQ at