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

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [day] [month] [year] [list]

Date:	Fri, 29 Sep 2006 09:56:22 +0800
From:	keios <keios.cn@...il.com>
To:	"Matt Mackall" <mpm@...enic.com>
Cc:	linux-kernel@...r.kernel.org, "Andrew Morton" <akpm@...l.org>
Subject: Re: [PATCH] low performance of lib/sort.c , kernel 2.6.18

Yes, it is almost same as the first version, except a little
difference : descendants of node [r] is [r * 2 + 1] and [r * 2 + 2]
(comment:the size of element is ignored), but yours is [r * 2] and [r
* 2 + 1] .

The tree you build is :
       [0]
        |
       [1]
      /   \
    [2]   [3]
   /  \    /  \
 [4]  [5][6]  [7]

Not same as standard tree :
       [0]
      /   \
    [1]   [2]
   /  \    /  \
 [3]  [4][5]  [6]

We can find the standard algorithm here:
http://en.wikipedia.org/wiki/Heapsort .

So , in every shift-down operation (comment: In sort.c, it is after
heapify , second loop in /* sort */ section ), [0] will compare with
[0] and [1], and always swap with [1] . Performance lost here .

Acked-by: keios <keios.cn@...il.com>

On 9/29/06, Matt Mackall <mpm@...enic.com> 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@...il.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@...enic.com>
>
> --
> 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@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/