@@ -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);
}
}
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(-) -- 2.37.1