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

From: René Scharfe <l.s.r@web.de>
Date: Jul 21, 2022, 21:25 UTC
Message-ID: <b908b42b-2cd5-12b2-b47d-abecfb370429@web.de>
In-Reply-To: <xmqqpmi04m1f.fsf@gitster.g>

Am 20.07.2022 um 03:20 schrieb Junio C Hamano:

Show 16 quoted lines

> * 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é