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@xxxxxx> 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é
