linux-kernel - Re: [PATCH v3] lib/list_sort: reduce if-statements

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]

Message-ID: <df16fdf4-bb0f-ee58-0c7a-4b3d5ee98959@gmail.com>
Date:   Wed, 29 Mar 2023 09:02:35 +0800
From:   Yan-Jie Wang <yanjiewtw@...il.com>
To:     linux-kernel@...r.kernel.org
Subject: Re: [PATCH v3] lib/list_sort: reduce if-statements

On Sat, Mar 25, 2023 at 8:32 PM Yan-Jie Wang <yanjiewtw@...il.com> wrote:
> 
> Reduce if-statements in merge and merge_final functions by using 
> indirect pointers and bitwise operations.
> 
> This will make the code more elegant and reduce the number of branch
>  instructions in compiled code.
> 
> Signed-off-by: Yan-Jie Wang <yanjiewtw@...il.com> ---

After performing some tests, I found that the merge algorithm I proposed
in this patch is not faster than the original one.

The number of branch instructions executed per loop is still the same
(two branch instructions per loop) since the compiler will generate a
branch instruction for `node = cmp(priv, a, b) <= 0 ? &a : &b;`.

In addition, there are more memory access in my proposed one because the
use of the indirect pointer, `node`, forces the compiler to put the
local variables, `a` and `b`, in memory. This will slow down the
performance.

This is the result of the compiled assembly:
   https://godbolt.org/z/vqorfz967

The test I wrote to evaluate the performance:
   https://github.com/yanjiew1/linux23q1-listsort_merge

I would like to thank Ching-Chun (Jim) Huang for providing advice for
this patch.

Yan-Jie Wang