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

From: Martin Ågren <martin.agren@gmail.com>
Date: Jul 22, 2022, 07:19 UTC
Message-ID: <CAN0heSrpXq0bKW5E70a421GhDXDFnvT+=txw=rPQJu47n65TSw@mail.gmail.com>
In-Reply-To: <b908b42b-2cd5-12b2-b47d-abecfb370429@web.de>

On Fri, 22 Jul 2022 at 00:14, René Scharfe <l.s.r@web.de> wrote:

>
> Am 20.07.2022 um 03:20 schrieb Junio C Hamano:
> > * rs/mergesort (2022-07-17) 10 commits

Show 6 quoted lines

> 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:

FWIW, here are my measurements on a Core i7-8700T running Ubuntu 20.04:

On e72d93e88c (The fifth batch, 2022-07-19): 0071.12: llist_mergesort() unsorted 0.42(0.38+0.03) 0071.14: llist_mergesort() sorted 0.17(0.14+0.02) 0071.16: llist_mergesort() reversed 0.16(0.10+0.05)

Benchmark 1: t/helper/test-tool mergesort test
  Time (mean ± σ):     143.9 ms ±   0.4 ms    [User: 143.6 ms, System: 0.3 ms]
  Range (min … max):   143.1 ms … 144.7 ms    20 runs

After patch 1 (mergesort: unify ranks loops): 0071.12: llist_mergesort() unsorted 0.41(0.36+0.05) 0071.14: llist_mergesort() sorted 0.17(0.12+0.05) 0071.16: llist_mergesort() reversed 0.16(0.12+0.04)

Benchmark 1: t/helper/test-tool mergesort test
  Time (mean ± σ):     141.5 ms ±   0.5 ms    [User: 141.1 ms, System: 0.5 ms]
  Range (min … max):   141.0 ms … 142.9 ms    21 runs

After patch 2 (mergesort: tighten merge loop): 0071.12: llist_mergesort() unsorted 0.42(0.39+0.03) 0071.14: llist_mergesort() sorted 0.17(0.10+0.06) 0071.16: llist_mergesort() reversed 0.16(0.11+0.04)

Benchmark 1: t/helper/test-tool mergesort test
  Time (mean ± σ):     142.6 ms ±   0.9 ms    [User: 142.1 ms, System: 0.6 ms]
  Range (min … max):   141.9 ms … 145.3 ms    21 runs

After patch 5 (test-mergesort: use DEFINE_LIST_SORT): 0071.12: DEFINE_LIST_SORT unsorted 0.40(0.35+0.04) 0071.14: DEFINE_LIST_SORT sorted 0.16(0.11+0.04) 0071.16: DEFINE_LIST_SORT reversed 0.16(0.11+0.05)

Benchmark 1: t/helper/test-tool mergesort test
  Time (mean ± σ):     123.3 ms ±   0.5 ms    [User: 123.0 ms, System: 0.4 ms]
  Range (min … max):   122.7 ms … 125.2 ms    23 runs

Martin