Messages in this thread | | | Subject | Re: [PATCH] low performance of lib/sort.c , kernel 2.6.18 | From | Zou Nan hai <> | Date | 29 Sep 2006 06:34:28 +0800 |
| |
On Fri, 2006-09-29 at 06:33, Matt Mackall wrote: > 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 <keios.cn@gmail.com> > > 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: > > http://www.kernel.org/pub/linux/kernel/people/akpm/patches/2.6/2.6.11-rc4/2.6.11-rc4-mm1/broken-out/lib-sort-heapsort-implementation-of-sort.patch > > Then Zou Nan hai sent Andrew a fix for an off-by-one bug here (merged > with my patch): > > http://kernel.org/pub/linux/kernel/people/akpm/patches/2.6/2.6.11/2.6.11-mm1/broken-out/lib-sort-heapsort-implementation-of-sort.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 > sizes). > > Acked-by: Matt Mackall <mpm@selenic.com>
I think this patch is correct.
Thanks Zou Nan hai - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
| |