From 848afebe5604877354bea42d81df380cff03b948 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Ren=C3=A9=20Scharfe?= Date: Sat, 16 Jul 2022 18:53:45 +0200 Subject: mergesort: tighten merge loop MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit 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 Signed-off-by: Junio C Hamano --- mergesort.c | 19 ++++++------------- 1 file changed, 6 insertions(+), 13 deletions(-) (limited to 'mergesort.c') 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); } } -- cgit v1.2.3