Messages in this thread | | | Date | Wed, 29 Mar 2023 09:02:35 +0800 | From | Yan-Jie Wang <> | Subject | Re: [PATCH v3] lib/list_sort: reduce if-statements |
| |
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
| |