rs/mergesort (was: What's cooking in git.git (Jul 2022, #06; Tue, 19))

["René Scharfe" <l.s.r@web.de>]

Am 20.07.2022 um 03:20 schrieb Junio C Hamano:
> * rs/mergesort (2022-07-17) 10 commits
>   - mergesort: remove llist_mergesort()
>   - packfile: use DEFINE_LIST_SORT
>   - fetch-pack: use DEFINE_LIST_SORT
>   - commit: use DEFINE_LIST_SORT
>   - blame: use DEFINE_LIST_SORT
>   - test-mergesort: use DEFINE_LIST_SORT
>   - test-mergesort: use DEFINE_LIST_SORT_DEBUG
>   - mergesort: add macros for typed sort of linked lists
>   - mergesort: tighten merge loop
>   - mergesort: unify ranks loops
>
>   Make our mergesort implementation type-safe.
>
>   Will merge to 'next'?
>   source: <4d7cd286-398e-215c-f2bd-aa7e8207be4f@web.de>

A confirmation that performance improves or at least doesn't get worse
on other platforms as well would be a good.  The numbers I gave in the
commit messages were for macOS 12.4 on an M1.

I managed to install the Git SDK on a Windows 11 laptop with a Ryzen
5800H, and it gives me mixed results:

main:
0071.12: llist_mergesort() unsorted    0.69(0.01+0.03)
0071.14: llist_mergesort() sorted      0.42(0.03+0.04)
0071.16: llist_mergesort() reversed    0.41(0.01+0.04)

Benchmark 1: .\t\helper\test-tool mergesort test
  Time (mean ± σ):     136.0 ms ±   1.8 ms    [User: 0.7 ms, System: 3.8 ms]
  Range (min … max):   132.9 ms … 140.4 ms    20 runs

After patch 1:
0071.12: llist_mergesort() unsorted    0.68(0.00+0.06)
0071.14: llist_mergesort() sorted      0.41(0.01+0.06)
0071.16: llist_mergesort() reversed    0.41(0.00+0.04)

Benchmark 1: .\t\helper\test-tool mergesort test
  Time (mean ± σ):     137.8 ms ±   2.2 ms    [User: 0.7 ms, System: 1.3 ms]
  Range (min … max):   133.8 ms … 142.8 ms    20 runs

After patch 2:
0071.12: llist_mergesort() unsorted    0.69(0.00+0.04)
0071.14: llist_mergesort() sorted      0.41(0.00+0.04)
0071.16: llist_mergesort() reversed    0.41(0.00+0.07)

Benchmark 1: .\t\helper\test-tool mergesort test
  Time (mean ± σ):     138.4 ms ±   3.1 ms    [User: 2.9 ms, System: 1.9 ms]
  Range (min … max):   134.3 ms … 144.0 ms    21 runs

After patch 5:
0071.12: DEFINE_LIST_SORT unsorted     0.70(0.01+0.04)
0071.14: DEFINE_LIST_SORT sorted       0.40(0.01+0.03)
0071.16: DEFINE_LIST_SORT reversed     0.40(0.00+0.04)

Benchmark 1: .\t\helper\test-tool mergesort test
  Time (mean ± σ):     119.2 ms ±   2.3 ms    [User: 0.6 ms, System: 2.7 ms]
  Range (min … max):   115.8 ms … 124.1 ms    24 runs

So there's higher variance to begin with, and test-mergesort seems to be
held back by something else than the sorting itself -- perhaps memory
allocation or layout?  Not a showstopper, I would say, but also not as
nice a success story as given in the commit messages.

René