Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20;
Message-ID: <df16fdf4-bb0f-ee58-0c7a-4b3d5ee98959@gmail.com>
Date:   Wed, 29 Mar 2023 09:02:35 +0800
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101
 Thunderbird/102.9.0
From:   Yan-Jie Wang <yanjiewtw@gmail.com>
Subject: Re: [PATCH v3] lib/list_sort: reduce if-statements
To:     linux-kernel@vger.kernel.org
References: <20230325091654.106040-1-yanjiewtw@gmail.com>
 <20230325123216.226120-1-yanjiewtw@gmail.com>
Content-Language: en-US
In-Reply-To: <20230325123216.226120-1-yanjiewtw@gmail.com>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Precedence: bulk

On Sat, Mar 25, 2023 at 8:32 PM Yan-Jie Wang <yanjiewtw@gmail.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@gmail.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