[PATCH 02/10] mergesort: tighten merge loop

From: René Scharfe <l.s.r@web.de>
Date: Jul 16, 2022, 16:53 UTC
Message-ID: <df2d020d-29e2-6b6b-bde7-576fc1b9c883@web.de>
In-Reply-To: <4d7cd286-398e-215c-f2bd-aa7e8207be4f@web.de>

llist_merge() has special inner loops for taking elements from either of the two lists to merge. That helps consistently preferring one over the other, for stability. Merge the loops, swap the lists when the other one has the next element for the result and keep track on which one to prefer on equality. This results in shorter code and object text:

Before: __TEXT __DATA __OBJC others dec hex 412 0 0 3441 3853 f0d mergesort.o

With this patch: __TEXT __DATA __OBJC others dec hex 352 0 0 3516 3868 f1c mergesort.o

Performance doesn't get worse:

Before: 0071.12: llist_mergesort() unsorted 0.24(0.22+0.01) 0071.14: llist_mergesort() sorted 0.12(0.10+0.01) 0071.16: llist_mergesort() reversed 0.12(0.10+0.01)

Benchmark 1: t/helper/test-tool mergesort test
  Time (mean ± σ):     109.2 ms ±   0.2 ms    [User: 107.5 ms, System: 1.1 ms]
  Range (min … max):   108.9 ms … 109.6 ms    27 runs

With this patch: 0071.12: llist_mergesort() unsorted 0.24(0.22+0.01) 0071.14: llist_mergesort() sorted 0.12(0.10+0.01) 0071.16: llist_mergesort() reversed 0.12(0.10+0.01)

Benchmark 1: t/helper/test-tool mergesort test
  Time (mean ± σ):     108.4 ms ±   0.2 ms    [User: 106.7 ms, System: 1.2 ms]
  Range (min … max):   108.0 ms … 108.8 ms    27 runs

Signed-off-by: René Scharfe <l.s.r@web.de>
---
 mergesort.c | 19 ++++++-------------
 1 file changed, 6 insertions(+), 13 deletions(-)

diff --git a/mergesort.c b/mergesort.c
index 92150c4101..6bda3a1c0e 100644
--- a/mergesort.c
+++ b/mergesort.c
@@ -8,10 +8,11 @@ static void *llist_merge(void *list, void *other,
 			 int (*compare_fn)(const void *, const void *))
 {
 	void *result = list, *tail;
+	int prefer_list = compare_fn(list, other) <= 0;

-	if (compare_fn(list, other) > 0) {
+	if (!prefer_list) {
 		result = other;
-		goto other;
+		SWAP(list, other);
 	}
 	for (;;) {
 		do {
@@ -21,18 +22,10 @@ static void *llist_merge(void *list, void *other,
 				set_next_fn(tail, other);
 				return result;
 			}
-		} while (compare_fn(list, other) <= 0);
+		} while (compare_fn(list, other) < prefer_list);
 		set_next_fn(tail, other);
-	other:
-		do {
-			tail = other;
-			other = get_next_fn(other);
-			if (!other) {
-				set_next_fn(tail, list);
-				return result;
-			}
-		} while (compare_fn(list, other) > 0);
-		set_next_fn(tail, list);
+		prefer_list ^= 1;
+		SWAP(list, other);
 	}
 }

--
2.37.1