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 <[email protected]>
---
lib/list_sort.c | 51 +++++++++++--------------------------------
tools/lib/list_sort.c | 51 +++++++++++--------------------------------
2 files changed, 26 insertions(+), 76 deletions(-)
diff --git a/lib/list_sort.c b/lib/list_sort.c
index 0fb59e92ca2d..393fcb9948c5 100644
--- a/lib/list_sort.c
+++ b/lib/list_sort.c
@@ -16,28 +16,15 @@ __attribute__((nonnull(2,3,4)))
static struct list_head *merge(void *priv, list_cmp_func_t cmp,
struct list_head *a, struct list_head *b)
{
- struct list_head *head, **tail = &head;
+ struct list_head *head, **tail = &head, **node;
- for (;;) {
+ for (node = NULL; a && b; *node = (*node)->next) {
/* if equal, take 'a' -- important for sort stability */
- if (cmp(priv, a, b) <= 0) {
- *tail = a;
- tail = &a->next;
- a = a->next;
- if (!a) {
- *tail = b;
- break;
- }
- } else {
- *tail = b;
- tail = &b->next;
- b = b->next;
- if (!b) {
- *tail = a;
- break;
- }
- }
+ node = cmp(priv, a, b) <= 0 ? &a : &b;
+ *tail = *node;
+ tail = &(*node)->next;
}
+ *tail = (struct list_head *) ((uintptr_t) a | (uintptr_t) b);
return head;
}
@@ -52,29 +39,17 @@ __attribute__((nonnull(2,3,4,5)))
static void merge_final(void *priv, list_cmp_func_t cmp, struct list_head *head,
struct list_head *a, struct list_head *b)
{
- struct list_head *tail = head;
+ struct list_head *tail = head, **node;
u8 count = 0;
- for (;;) {
+ for (node = NULL; a && b; *node = (*node)->next) {
/* if equal, take 'a' -- important for sort stability */
- if (cmp(priv, a, b) <= 0) {
- tail->next = a;
- a->prev = tail;
- tail = a;
- a = a->next;
- if (!a)
- break;
- } else {
- tail->next = b;
- b->prev = tail;
- tail = b;
- b = b->next;
- if (!b) {
- b = a;
- break;
- }
- }
+ node = cmp(priv, a, b) <= 0 ? &a : &b;
+ tail->next = *node;
+ (*node)->prev = tail;
+ tail = *node;
}
+ b = (struct list_head *) ((uintptr_t) a | (uintptr_t) b);
/* Finish linking remainder of list b on to tail */
tail->next = b;
diff --git a/tools/lib/list_sort.c b/tools/lib/list_sort.c
index 10c067e3a8d2..5b1baa6a67d9 100644
--- a/tools/lib/list_sort.c
+++ b/tools/lib/list_sort.c
@@ -15,28 +15,15 @@ __attribute__((nonnull(2,3,4)))
static struct list_head *merge(void *priv, list_cmp_func_t cmp,
struct list_head *a, struct list_head *b)
{
- struct list_head *head, **tail = &head;
+ struct list_head *head, **tail = &head, **node;
- for (;;) {
+ for (node = NULL; a && b; *node = (*node)->next) {
/* if equal, take 'a' -- important for sort stability */
- if (cmp(priv, a, b) <= 0) {
- *tail = a;
- tail = &a->next;
- a = a->next;
- if (!a) {
- *tail = b;
- break;
- }
- } else {
- *tail = b;
- tail = &b->next;
- b = b->next;
- if (!b) {
- *tail = a;
- break;
- }
- }
+ node = cmp(priv, a, b) <= 0 ? &a : &b;
+ *tail = *node;
+ tail = &(*node)->next;
}
+ *tail = (struct list_head *) ((uintptr_t) a | (uintptr_t) b);
return head;
}
@@ -51,29 +38,17 @@ __attribute__((nonnull(2,3,4,5)))
static void merge_final(void *priv, list_cmp_func_t cmp, struct list_head *head,
struct list_head *a, struct list_head *b)
{
- struct list_head *tail = head;
+ struct list_head *tail = head, **node;
u8 count = 0;
- for (;;) {
+ for (node = NULL; a && b; *node = (*node)->next) {
/* if equal, take 'a' -- important for sort stability */
- if (cmp(priv, a, b) <= 0) {
- tail->next = a;
- a->prev = tail;
- tail = a;
- a = a->next;
- if (!a)
- break;
- } else {
- tail->next = b;
- b->prev = tail;
- tail = b;
- b = b->next;
- if (!b) {
- b = a;
- break;
- }
- }
+ node = cmp(priv, a, b) <= 0 ? &a : &b;
+ tail->next = *node;
+ (*node)->prev = tail;
+ tail = *node;
}
+ b = (struct list_head *) ((uintptr_t) a | (uintptr_t) b);
/* Finish linking remainder of list b on to tail */
tail->next = b;
base-commit: 65aca32efdcb0965502d3db2f1fa33838c070952
--
2.34.1
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 <[email protected]>
---
Changes since v1:
* Use do-while instead of for-loop to avoid an unnecessory check at
the beginning of the loop.
* After moving *node to the next node, just check whether *node is
NULL or not instead of checking both a && b to determine whether to
continue.
* Above changes further reduces the compiled code size and branch
instructions.
lib/list_sort.c | 55 ++++++++++++-------------------------------
tools/lib/list_sort.c | 55 ++++++++++++-------------------------------
2 files changed, 30 insertions(+), 80 deletions(-)
diff --git a/lib/list_sort.c b/lib/list_sort.c
index 0fb59e92ca2d..4744332c2aca 100644
--- a/lib/list_sort.c
+++ b/lib/list_sort.c
@@ -16,28 +16,15 @@ __attribute__((nonnull(2,3,4)))
static struct list_head *merge(void *priv, list_cmp_func_t cmp,
struct list_head *a, struct list_head *b)
{
- struct list_head *head, **tail = &head;
+ struct list_head *head, **tail = &head, **node = NULL;
- for (;;) {
+ do {
/* if equal, take 'a' -- important for sort stability */
- if (cmp(priv, a, b) <= 0) {
- *tail = a;
- tail = &a->next;
- a = a->next;
- if (!a) {
- *tail = b;
- break;
- }
- } else {
- *tail = b;
- tail = &b->next;
- b = b->next;
- if (!b) {
- *tail = a;
- break;
- }
- }
- }
+ node = cmp(priv, a, b) <= 0 ? &a : &b;
+ *tail = *node;
+ tail = &(*node)->next;
+ } while ((*node = (*node)->next));
+ *tail = (struct list_head *) ((uintptr_t) a | (uintptr_t) b);
return head;
}
@@ -52,29 +39,17 @@ __attribute__((nonnull(2,3,4,5)))
static void merge_final(void *priv, list_cmp_func_t cmp, struct list_head *head,
struct list_head *a, struct list_head *b)
{
- struct list_head *tail = head;
+ struct list_head *tail = head, **node = NULL;
u8 count = 0;
- for (;;) {
+ do {
/* if equal, take 'a' -- important for sort stability */
- if (cmp(priv, a, b) <= 0) {
- tail->next = a;
- a->prev = tail;
- tail = a;
- a = a->next;
- if (!a)
- break;
- } else {
- tail->next = b;
- b->prev = tail;
- tail = b;
- b = b->next;
- if (!b) {
- b = a;
- break;
- }
- }
- }
+ node = cmp(priv, a, b) <= 0 ? &a : &b;
+ tail->next = *node;
+ (*node)->prev = tail;
+ tail = *node;
+ } while ((*node = (*node)->next));
+ b = (struct list_head *) ((uintptr_t) a | (uintptr_t) b);
/* Finish linking remainder of list b on to tail */
tail->next = b;
diff --git a/tools/lib/list_sort.c b/tools/lib/list_sort.c
index 10c067e3a8d2..fac6e9a9bbff 100644
--- a/tools/lib/list_sort.c
+++ b/tools/lib/list_sort.c
@@ -15,28 +15,15 @@ __attribute__((nonnull(2,3,4)))
static struct list_head *merge(void *priv, list_cmp_func_t cmp,
struct list_head *a, struct list_head *b)
{
- struct list_head *head, **tail = &head;
+ struct list_head *head, **tail = &head, **node = NULL;
- for (;;) {
+ do {
/* if equal, take 'a' -- important for sort stability */
- if (cmp(priv, a, b) <= 0) {
- *tail = a;
- tail = &a->next;
- a = a->next;
- if (!a) {
- *tail = b;
- break;
- }
- } else {
- *tail = b;
- tail = &b->next;
- b = b->next;
- if (!b) {
- *tail = a;
- break;
- }
- }
- }
+ node = cmp(priv, a, b) <= 0 ? &a : &b;
+ *tail = *node;
+ tail = &(*node)->next;
+ } while ((*node = (*node)->next));
+ *tail = (struct list_head *) ((uintptr_t) a | (uintptr_t) b);
return head;
}
@@ -51,29 +38,17 @@ __attribute__((nonnull(2,3,4,5)))
static void merge_final(void *priv, list_cmp_func_t cmp, struct list_head *head,
struct list_head *a, struct list_head *b)
{
- struct list_head *tail = head;
+ struct list_head *tail = head, **node = NULL;
u8 count = 0;
- for (;;) {
+ do {
/* if equal, take 'a' -- important for sort stability */
- if (cmp(priv, a, b) <= 0) {
- tail->next = a;
- a->prev = tail;
- tail = a;
- a = a->next;
- if (!a)
- break;
- } else {
- tail->next = b;
- b->prev = tail;
- tail = b;
- b = b->next;
- if (!b) {
- b = a;
- break;
- }
- }
- }
+ node = cmp(priv, a, b) <= 0 ? &a : &b;
+ tail->next = *node;
+ (*node)->prev = tail;
+ tail = *node;
+ } while ((*node = (*node)->next));
+ b = (struct list_head *) ((uintptr_t) a | (uintptr_t) b);
/* Finish linking remainder of list b on to tail */
tail->next = b;
base-commit: 65aca32efdcb0965502d3db2f1fa33838c070952
--
2.34.1
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 <[email protected]>
---
Changes since v2:
* Remove unnecessory assignments to the variable, node.
Changes since v1:
* Use do-while instead of for-loop to avoid an unnecessory check at
the beginning of the loop.
* After moving *node to the next node, just check whether *node is
NULL or not instead of checking both a && b to determine whether to
continue.
* Above changes further reduces the compiled code size and branch
instructions.
lib/list_sort.c | 55 ++++++++++++-------------------------------
tools/lib/list_sort.c | 55 ++++++++++++-------------------------------
2 files changed, 30 insertions(+), 80 deletions(-)
diff --git a/lib/list_sort.c b/lib/list_sort.c
index 0fb59e92ca2d..9a2745a1a44b 100644
--- a/lib/list_sort.c
+++ b/lib/list_sort.c
@@ -16,28 +16,15 @@ __attribute__((nonnull(2,3,4)))
static struct list_head *merge(void *priv, list_cmp_func_t cmp,
struct list_head *a, struct list_head *b)
{
- struct list_head *head, **tail = &head;
+ struct list_head *head, **tail = &head, **node;
- for (;;) {
+ do {
/* if equal, take 'a' -- important for sort stability */
- if (cmp(priv, a, b) <= 0) {
- *tail = a;
- tail = &a->next;
- a = a->next;
- if (!a) {
- *tail = b;
- break;
- }
- } else {
- *tail = b;
- tail = &b->next;
- b = b->next;
- if (!b) {
- *tail = a;
- break;
- }
- }
- }
+ node = cmp(priv, a, b) <= 0 ? &a : &b;
+ *tail = *node;
+ tail = &(*node)->next;
+ } while ((*node = (*node)->next));
+ *tail = (struct list_head *) ((uintptr_t) a | (uintptr_t) b);
return head;
}
@@ -52,29 +39,17 @@ __attribute__((nonnull(2,3,4,5)))
static void merge_final(void *priv, list_cmp_func_t cmp, struct list_head *head,
struct list_head *a, struct list_head *b)
{
- struct list_head *tail = head;
+ struct list_head *tail = head, **node;
u8 count = 0;
- for (;;) {
+ do {
/* if equal, take 'a' -- important for sort stability */
- if (cmp(priv, a, b) <= 0) {
- tail->next = a;
- a->prev = tail;
- tail = a;
- a = a->next;
- if (!a)
- break;
- } else {
- tail->next = b;
- b->prev = tail;
- tail = b;
- b = b->next;
- if (!b) {
- b = a;
- break;
- }
- }
- }
+ node = cmp(priv, a, b) <= 0 ? &a : &b;
+ tail->next = *node;
+ (*node)->prev = tail;
+ tail = *node;
+ } while ((*node = (*node)->next));
+ b = (struct list_head *) ((uintptr_t) a | (uintptr_t) b);
/* Finish linking remainder of list b on to tail */
tail->next = b;
diff --git a/tools/lib/list_sort.c b/tools/lib/list_sort.c
index 10c067e3a8d2..5054b2196981 100644
--- a/tools/lib/list_sort.c
+++ b/tools/lib/list_sort.c
@@ -15,28 +15,15 @@ __attribute__((nonnull(2,3,4)))
static struct list_head *merge(void *priv, list_cmp_func_t cmp,
struct list_head *a, struct list_head *b)
{
- struct list_head *head, **tail = &head;
+ struct list_head *head, **tail = &head, **node;
- for (;;) {
+ do {
/* if equal, take 'a' -- important for sort stability */
- if (cmp(priv, a, b) <= 0) {
- *tail = a;
- tail = &a->next;
- a = a->next;
- if (!a) {
- *tail = b;
- break;
- }
- } else {
- *tail = b;
- tail = &b->next;
- b = b->next;
- if (!b) {
- *tail = a;
- break;
- }
- }
- }
+ node = cmp(priv, a, b) <= 0 ? &a : &b;
+ *tail = *node;
+ tail = &(*node)->next;
+ } while ((*node = (*node)->next));
+ *tail = (struct list_head *) ((uintptr_t) a | (uintptr_t) b);
return head;
}
@@ -51,29 +38,17 @@ __attribute__((nonnull(2,3,4,5)))
static void merge_final(void *priv, list_cmp_func_t cmp, struct list_head *head,
struct list_head *a, struct list_head *b)
{
- struct list_head *tail = head;
+ struct list_head *tail = head, **node;
u8 count = 0;
- for (;;) {
+ do {
/* if equal, take 'a' -- important for sort stability */
- if (cmp(priv, a, b) <= 0) {
- tail->next = a;
- a->prev = tail;
- tail = a;
- a = a->next;
- if (!a)
- break;
- } else {
- tail->next = b;
- b->prev = tail;
- tail = b;
- b = b->next;
- if (!b) {
- b = a;
- break;
- }
- }
- }
+ node = cmp(priv, a, b) <= 0 ? &a : &b;
+ tail->next = *node;
+ (*node)->prev = tail;
+ tail = *node;
+ } while ((*node = (*node)->next));
+ b = (struct list_head *) ((uintptr_t) a | (uintptr_t) b);
/* Finish linking remainder of list b on to tail */
tail->next = b;
base-commit: 65aca32efdcb0965502d3db2f1fa33838c070952
--
2.34.1
On Sat, Mar 25, 2023 at 8:32 PM Yan-Jie Wang <[email protected]> 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 <[email protected]> ---
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