Re: [RESEND PATCH v2 4/5] lib/list_sort: Simplify and remove MAX_LIST_LENGTH_BITS
Than you all for the build warning report. The warning produced by gcc versions 4.9, 7.3, 8.1, whatever version Stephen Rothwell is running, is: lib/list_sort.c:17:36: warning: __pure__ attribute ignored [-Wattributes] The relevant code is: 10: /* 11: * By declaring the compare function with the __pure attribute, we give 12: * the compiler more opportunity to optimize. Ideally, we'd use this in 13: * the prototype of list_sort(), but that would involve a lot of churn 14: * at all call sites, so just cast the function pointer passed in. 15: */ 16: typedef int __pure __attribute__((nonnull(2,3))) (*cmp_func)(void *, 17: struct list_head const *, struct list_head const *); As the comment says, the purpose of the __pure attribute is to tell the compiler that, after a call via a function pointer of this type, memory is not clobbered and it is not necessary to reload any cached list pointers. This is, of course, purely optional and may be deleted harmlessly. I just checked, and that makes no difference at all to gcc-8 code generation, so there's no point messing with #ifdef. There are only two questions: how to update the comment, and how to submit the fix. I'm thinking of /* * A more accurate type for comparison functions. Ideally, we'd use * this in the prototype of list_sort(), but that would involve a lot of * churn at all call sites, so just cast the function pointer passed in. * * This could also include __pure to give the compiler more opportunity * to optimize, but that elicits an "attribute ignored" warning on * GCC <= 8.1, and doesn't change GCC 8.3's code generation at all, * so it's omitted. */ How to submit the fix: Andrew, do you prefer a replacement patch or a small fix patch? I'll assume the latter and send it in a few minutes.
Re: [RESEND PATCH v2 4/5] lib/list_sort: Simplify and remove MAX_LIST_LENGTH_BITS
On Tue, 19 Mar 2019 08:16:00 + George Spelvin wrote: > Rather than a fixed-size array of pending sorted runs, use the ->prev > links to keep track of things. This reduces stack usage, eliminates > some ugly overflow handling, and reduces the code size. > > Also: > * merge() no longer needs to handle NULL inputs, so simplify. > * The same applies to merge_and_restore_back_links(), which is renamed > to the less ponderous merge_final(). (It's a static helper function, > so we don't need a super-descriptive name; comments will do.) > * Document the actual return value requirements on the (*cmp)() > function; some callers are already using this feature. > > x86-64 code size 1086 -> 739 bytes (-347) > > (Yes, I see checkpatch complaining about no space after comma in > "__attribute__((nonnull(2,3,4,5)))". Checkpatch is wrong.) x86_64 allnoconfig with gcc-7.3.0: lib/list_sort.c:17:36: warning: __pure__ attribute ignored [-Wattributes] struct list_head const *, struct list_head const *);
[RESEND PATCH v2 4/5] lib/list_sort: Simplify and remove MAX_LIST_LENGTH_BITS
Rather than a fixed-size array of pending sorted runs, use the ->prev
links to keep track of things. This reduces stack usage, eliminates
some ugly overflow handling, and reduces the code size.
Also:
* merge() no longer needs to handle NULL inputs, so simplify.
* The same applies to merge_and_restore_back_links(), which is renamed
to the less ponderous merge_final(). (It's a static helper function,
so we don't need a super-descriptive name; comments will do.)
* Document the actual return value requirements on the (*cmp)()
function; some callers are already using this feature.
x86-64 code size 1086 -> 739 bytes (-347)
(Yes, I see checkpatch complaining about no space after comma in
"__attribute__((nonnull(2,3,4,5)))". Checkpatch is wrong.)
Signed-off-by: George Spelvin
Acked-by: Andrey Abramov
Feedback-from: Rasmus Villemoes
Feedback-from: Andy Shevchenko
Feedback-from: Geert Uytterhoeven
---
include/linux/list_sort.h | 1 +
lib/list_sort.c | 169 --
2 files changed, 109 insertions(+), 61 deletions(-)
diff --git a/include/linux/list_sort.h b/include/linux/list_sort.h
index ba79956e848d..20f178c24e9d 100644
--- a/include/linux/list_sort.h
+++ b/include/linux/list_sort.h
@@ -6,6 +6,7 @@
struct list_head;
+__attribute__((nonnull(2,3)))
void list_sort(void *priv, struct list_head *head,
int (*cmp)(void *priv, struct list_head *a,
struct list_head *b));
diff --git a/lib/list_sort.c b/lib/list_sort.c
index 85759928215b..fc807dd60a51 100644
--- a/lib/list_sort.c
+++ b/lib/list_sort.c
@@ -7,33 +7,47 @@
#include
#include
-#define MAX_LIST_LENGTH_BITS 20
+/*
+ * By declaring the compare function with the __pure attribute, we give
+ * the compiler more opportunity to optimize. Ideally, we'd use this in
+ * the prototype of list_sort(), but that would involve a lot of churn
+ * at all call sites, so just cast the function pointer passed in.
+ */
+typedef int __pure __attribute__((nonnull(2,3))) (*cmp_func)(void *,
+ struct list_head const *, struct list_head const *);
/*
* Returns a list organized in an intermediate format suited
* to chaining of merge() calls: null-terminated, no reserved or
* sentinel head node, "prev" links not maintained.
*/
-static struct list_head *merge(void *priv,
- int (*cmp)(void *priv, struct list_head *a,
- struct list_head *b),
+__attribute__((nonnull(2,3,4)))
+static struct list_head *merge(void *priv, cmp_func cmp,
struct list_head *a, struct list_head *b)
{
- struct list_head head, *tail =
+ struct list_head *head, **tail =
- while (a && b) {
+ for (;;) {
/* if equal, take 'a' -- important for sort stability */
- if ((*cmp)(priv, a, b) <= 0) {
- tail->next = a;
+ if (cmp(priv, a, b) <= 0) {
+ *tail = a;
+ tail = >next;
a = a->next;
+ if (!a) {
+ *tail = b;
+ break;
+ }
} else {
- tail->next = b;
+ *tail = b;
+ tail = >next;
b = b->next;
+ if (!b) {
+ *tail = a;
+ break;
+ }
}
- tail = tail->next;
}
- tail->next = a?:b;
- return head.next;
+ return head;
}
/*
@@ -43,44 +57,52 @@ static struct list_head *merge(void *priv,
* prev-link restoration pass, or maintaining the prev links
* throughout.
*/
-static void merge_and_restore_back_links(void *priv,
- int (*cmp)(void *priv, struct list_head *a,
- struct list_head *b),
- struct list_head *head,
- struct list_head *a, struct list_head *b)
+__attribute__((nonnull(2,3,4,5)))
+static void merge_final(void *priv, cmp_func cmp, struct list_head *head,
+ struct list_head *a, struct list_head *b)
{
struct list_head *tail = head;
u8 count = 0;
- while (a && b) {
+ for (;;) {
/* if equal, take 'a' -- important for sort stability */
- if ((*cmp)(priv, a, b) <= 0) {
+ 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;
[PATCH v2 4/5] lib/list_sort: Simplify and remove MAX_LIST_LENGTH_BITS
Rather than a fixed-size array of pending sorted runs, use the ->prev
links to keep track of things. This reduces stack usage, eliminates
some ugly overflow handling, and reduces the code size.
Also:
* merge() no longer needs to handle NULL inputs, so simplify.
* The same applies to merge_and_restore_back_links(), which is renamed
to the less ponderous merge_final(). (It's a static helper function,
so we don't need a super-descriptive name; comments will do.)
* Document the actual return value requirements on the (*cmp)()
function; some callers are already using this feature.
x86-64 code size 1086 -> 739 bytes (-347)
(Yes, I see checkpatch complaining about no space after comma in
"__attribute__((nonnull(2,3,4,5)))". Checkpatch is wrong.)
Signed-off-by: George Spelvin
Acked-by: Andrey Abramov
Feedback-from: Rasmus Villemoes
Feedback-from: Andy Shevchenko
Feedback-from: Geert Uytterhoeven
---
include/linux/list_sort.h | 1 +
lib/list_sort.c | 169 --
2 files changed, 109 insertions(+), 61 deletions(-)
diff --git a/include/linux/list_sort.h b/include/linux/list_sort.h
index ba79956e848d..20f178c24e9d 100644
--- a/include/linux/list_sort.h
+++ b/include/linux/list_sort.h
@@ -6,6 +6,7 @@
struct list_head;
+__attribute__((nonnull(2,3)))
void list_sort(void *priv, struct list_head *head,
int (*cmp)(void *priv, struct list_head *a,
struct list_head *b));
diff --git a/lib/list_sort.c b/lib/list_sort.c
index 85759928215b..fc807dd60a51 100644
--- a/lib/list_sort.c
+++ b/lib/list_sort.c
@@ -7,33 +7,47 @@
#include
#include
-#define MAX_LIST_LENGTH_BITS 20
+/*
+ * By declaring the compare function with the __pure attribute, we give
+ * the compiler more opportunity to optimize. Ideally, we'd use this in
+ * the prototype of list_sort(), but that would involve a lot of churn
+ * at all call sites, so just cast the function pointer passed in.
+ */
+typedef int __pure __attribute__((nonnull(2,3))) (*cmp_func)(void *,
+ struct list_head const *, struct list_head const *);
/*
* Returns a list organized in an intermediate format suited
* to chaining of merge() calls: null-terminated, no reserved or
* sentinel head node, "prev" links not maintained.
*/
-static struct list_head *merge(void *priv,
- int (*cmp)(void *priv, struct list_head *a,
- struct list_head *b),
+__attribute__((nonnull(2,3,4)))
+static struct list_head *merge(void *priv, cmp_func cmp,
struct list_head *a, struct list_head *b)
{
- struct list_head head, *tail =
+ struct list_head *head, **tail =
- while (a && b) {
+ for (;;) {
/* if equal, take 'a' -- important for sort stability */
- if ((*cmp)(priv, a, b) <= 0) {
- tail->next = a;
+ if (cmp(priv, a, b) <= 0) {
+ *tail = a;
+ tail = >next;
a = a->next;
+ if (!a) {
+ *tail = b;
+ break;
+ }
} else {
- tail->next = b;
+ *tail = b;
+ tail = >next;
b = b->next;
+ if (!b) {
+ *tail = a;
+ break;
+ }
}
- tail = tail->next;
}
- tail->next = a?:b;
- return head.next;
+ return head;
}
/*
@@ -43,44 +57,52 @@ static struct list_head *merge(void *priv,
* prev-link restoration pass, or maintaining the prev links
* throughout.
*/
-static void merge_and_restore_back_links(void *priv,
- int (*cmp)(void *priv, struct list_head *a,
- struct list_head *b),
- struct list_head *head,
- struct list_head *a, struct list_head *b)
+__attribute__((nonnull(2,3,4,5)))
+static void merge_final(void *priv, cmp_func cmp, struct list_head *head,
+ struct list_head *a, struct list_head *b)
{
struct list_head *tail = head;
u8 count = 0;
- while (a && b) {
+ for (;;) {
/* if equal, take 'a' -- important for sort stability */
- if ((*cmp)(priv, a, b) <= 0) {
+ 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;
