[PATCH v3 2/2] lib/list_sort: Remove dummy cmp() calls to speed up merge_final()

[Kuan-Wei Chiu <visitorckw@gmail.com>]

Historically, list_sort() implemented a hack in merge_final():
    if (unlikely(!++count))
        cmp(priv, b, b);

This was introduced 16 years ago in commit 835cc0c8477f ("lib: more
scalable list_sort()") so that callers could periodically invoke
cond_resched() within their comparison functions when merging highly
unbalanced lists.

An audit of the kernel tree reveals that fs/ubifs/ was the sole user
of this mechanism. Recent discussions and inspections by Richard
Weinberger confirm that UBIFS lists are strictly bounded in size (a few
thousand elements at most), meaning it does not strictly rely on these
dummy callbacks to prevent soft lockups.

For the vast majority of list_sort() users (such as block layer IO
schedulers and file systems), this hack results in completely wasted
function calls. In the worst-case scenario (merging an already sorted
list where 'a' is exhausted quickly), it results in approximately
(N/2)/256 unnecessary cmp() invocations.

Remove the dummy cmp(priv, b, b) fallback from merge_final(). This
saves unnecessary function calls, avoids branching overhead in the
tight loop, and slightly speeds up the final merge step for all generic
list_sort() users.

Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com>
---
 lib/list_sort.c | 9 ---------
 1 file changed, 9 deletions(-)

diff --git a/lib/list_sort.c b/lib/list_sort.c
index a310ecb7ccc0..e8ff17c9b2d0 100644
--- a/lib/list_sort.c
+++ b/lib/list_sort.c
@@ -76,15 +76,6 @@ static void merge_final(void *priv, list_cmp_func_t cmp, struct list_head *head,
 	/* Finish linking remainder of list b on to tail */
 	tail->next = b;
 	do {
-		/*
-		 * If the merge is highly unbalanced (e.g. the input is
-		 * already sorted), this loop may run many iterations.
-		 * Continue callbacks to the client even though no
-		 * element comparison is needed, so the client's cmp()
-		 * routine can invoke cond_resched() periodically.
-		 */
-		if (unlikely(!++count))
-			cmp(priv, b, b);
 		b->prev = tail;
 		tail = b;
 		b = b->next;
-- 
2.53.0.959.g497ff81fa9-goog


______________________________________________________
Linux MTD discussion mailing list
http://lists.infradead.org/mailman/listinfo/linux-mtd/