[0/9] mergesort: improve tests and performance

Message

René Scharfe Oct. 1, 2021, 9:07 a.m. UTC

Our mergesort for linked lists doesn't allocate temporary memory, which
is nice.  It is traversing the list multiple times from start to finish,
though.  This series teaches it to avoid that, which speeds it up
considerably.  But first it improves the associated test helper to
exercise the code harder and to make the effect of the changes visible
in terms of saved operations.

  test-mergesort: use strbuf_getline()
  test-mergesort: add sort subcommand
  test-mergesort: add test subcommand
  test-mergesort: add generate subcommand
  test-mergesort: add unriffle mode
  test-mergesort: add unriffle_skewed mode
  p0071: measure sorting of already sorted and reversed files
  p0071: test performance of llist_mergesort()
  mergesort: use ranks stack

 mergesort.c               | 121 +++++++------
 t/helper/test-mergesort.c | 360 +++++++++++++++++++++++++++++++++++++-
 t/perf/p0071-sort.sh      |  40 ++++-
 t/t0071-sort.sh           |  11 ++
 4 files changed, 465 insertions(+), 67 deletions(-)
 create mode 100755 t/t0071-sort.sh

--
2.33.0