llist_mergesort() has a loop for adding a new element to the ranks array
and another one for rolling up said array into a single sorted list at
the end. We can merge them, so that adding the last element rolls up
the whole array. Handle the empty list before the main loop now because
list can't be NULL anymore inside the loop.
The result is shorter code and significantly less object text:
main:
__TEXT __DATA __OBJC others dec hex
652 0 0 4651 5303 14b7 mergesort.o
With this patch:
__TEXT __DATA __OBJC others dec hex
412 0 0 3441 3853 f0d mergesort.o
Why is the change so big? The reduction is amplified by llist_merge()
being inlined both before and after.
Performance stays basically the same:
main:
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.0 ms ± 0.3 ms [User: 107.4 ms, System: 1.1 ms]
Range (min … max): 108.7 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 ± σ): 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
Signed-off-by: René Scharfe <l.s.r@xxxxxx>
---
mergesort.c | 31 +++++++++++++++----------------
1 file changed, 15 insertions(+), 16 deletions(-)
diff --git a/mergesort.c b/mergesort.c
index bd9c6ef8ee..92150c4101 100644
--- a/mergesort.c
+++ b/mergesort.c
@@ -57,28 +57,27 @@ void *llist_mergesort(void *list,
{
void *ranks[bitsizeof(void *)];
size_t n = 0;
- int i;
- while (list) {
+ if (!list)
+ return NULL;
+
+ for (;;) {
+ int i;
+ size_t m;
void *next = get_next_fn(list);
if (next)
set_next_fn(list, NULL);
- for (i = 0; n & ((size_t)1 << i); i++)
- list = llist_merge(ranks[i], list, get_next_fn,
- set_next_fn, compare_fn);
+ for (i = 0, m = n;; i++, m >>= 1) {
+ if (m & 1)
+ list = llist_merge(ranks[i], list, get_next_fn,
+ set_next_fn, compare_fn);
+ else if (next)
+ break;
+ else if (!m)
+ return list;
+ }
n++;
ranks[i] = list;
list = next;
}
-
- for (i = 0; n; i++, n >>= 1) {
- if (!(n & 1))
- continue;
- if (list)
- list = llist_merge(ranks[i], list, get_next_fn,
- set_next_fn, compare_fn);
- else
- list = ranks[i];
- }
- return list;
}
--
2.37.1
