]> git.ipfire.org Git - thirdparty/git.git/commit
mergesort: tighten merge loop
authorRené Scharfe <l.s.r@web.de>
Sat, 16 Jul 2022 16:53:45 +0000 (18:53 +0200)
committerJunio C Hamano <gitster@pobox.com>
Sun, 17 Jul 2022 22:20:38 +0000 (15:20 -0700)
commit848afebe5604877354bea42d81df380cff03b948
treedd7b8c00c5307deb88231acafda3cf7c4f2a3de1
parent7a3775eeb4c55e707f2c97700a4778de09c73e6f
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>
mergesort.c