diff options
author | René Scharfe <l.s.r@web.de> | 2022-07-16 19:53:45 +0300 |
---|---|---|
committer | Junio C Hamano <gitster@pobox.com> | 2022-07-18 01:20:38 +0300 |
commit | 848afebe5604877354bea42d81df380cff03b948 (patch) | |
tree | dd7b8c00c5307deb88231acafda3cf7c4f2a3de1 /mergesort.c | |
parent | 7a3775eeb4c55e707f2c97700a4778de09c73e6f (diff) |
mergesort: tighten merge loop
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>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Diffstat (limited to 'mergesort.c')
-rw-r--r-- | mergesort.c | 19 |
1 files 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); } } |