Subject: Re: [PATCH] low performance of lib/sort.c , kernel 2.6.18
From: Zou Nan hai <nanhai.zou@intel.com>
To: Matt Mackall <mpm@selenic.com>
Cc: keios <keios.cn@gmail.com>, LKML <linux-kernel@vger.kernel.org>,
       Andrew Morton <akpm@osdl.org>
In-Reply-To: <20060928223341.GI6412@waste.org>
References: <76505a370609280818r3ffc9a4akf4cec6ed366d32e3@mail.gmail.com>
	 <20060928223341.GI6412@waste.org>
Content-Type: text/plain
Organization: 
Message-Id: <1159482868.5251.22.camel@linux-znh>
Mime-Version: 1.0
Date: 29 Sep 2006 06:34:28 +0800
Content-Transfer-Encoding: 7bit
Sender: linux-kernel-owner@vger.kernel.org
Content-Length: 1573
Lines: 41

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/