[04/10] test-mergesort: use DEFINE_LIST_SORT_DEBUG

Commit Message

René Scharfe July 16, 2022, 4:56 p.m. UTC

Define a typed sort function using DEFINE_LIST_SORT_DEBUG for the
mergesort sanity check instead of using llist_mergesort().  This gets
rid of the next pointer accessor functions and improves the performance
at the cost of slightly bigger object text.

Before:
Benchmark 1: t/helper/test-tool mergesort test
  Time (mean ± σ):     108.4 ms ±   0.2 ms    [User: 106.7 ms, System: 1.2 ms]
  Range (min … max):   108.0 ms … 108.8 ms    27 runs

__TEXT	__DATA	__OBJC	others	dec	hex
6251	276	0	23172	29699	7403	t/helper/test-mergesort.o

With this patch:
Benchmark 1: t/helper/test-tool mergesort test
  Time (mean ± σ):      94.0 ms ±   0.2 ms    [User: 92.4 ms, System: 1.1 ms]
  Range (min … max):    93.7 ms …  94.5 ms    31 runs

__TEXT	__DATA	__OBJC	others	dec	hex
6407	276	0	24701	31384	7a98	t/helper/test-mergesort.o

Signed-off-by: René Scharfe <[e-mail]>
---
 t/helper/test-mergesort.c | 19 ++++---------------
 t/t0071-sort.sh           |  2 +-
 2 files changed, 5 insertions(+), 16 deletions(-)

--
2.37.1

Patch

diff --git a/t/helper/test-mergesort.c b/t/helper/test-mergesort.c
index ebf68f7de8..93d15d59a1 100644
--- a/t/helper/test-mergesort.c
+++ b/t/helper/test-mergesort.c
@@ -273,21 +273,11 @@  struct number {
 	struct number *next;
 };

-static void *get_next_number(const void *a)
-{
-	stats.get_next++;
-	return ((const struct number *)a)->next;
-}
-
-static void set_next_number(void *a, void *b)
-{
-	stats.set_next++;
-	((struct number *)a)->next = b;
-}
+DEFINE_LIST_SORT_DEBUG(static, sort_numbers, struct number, next,
+		       stats.get_next++, stats.set_next++);

-static int compare_numbers(const void *av, const void *bv)
+static int compare_numbers(const struct number *an, const struct number *bn)
 {
-	const struct number *an = av, *bn = bv;
 	int a = an->value, b = bn->value;
 	stats.compare++;
 	return (a > b) - (a < b);
@@ -325,8 +315,7 @@  static int test(const struct dist *dist, const struct mode *mode, int n, int m)
 	*tail = NULL;

 	stats.get_next = stats.set_next = stats.compare = 0;
-	list = llist_mergesort(list, get_next_number, set_next_number,
-			       compare_numbers);
+	sort_numbers(&list, compare_numbers);

 	QSORT(arr, n, compare_ints);
 	for (i = 0, curr = list; i < n && curr; i++, curr = curr->next) {
diff --git a/t/t0071-sort.sh b/t/t0071-sort.sh
index 6f9a501c72..ba8ad1d1ca 100755
--- a/t/t0071-sort.sh
+++ b/t/t0071-sort.sh
@@ -5,7 +5,7 @@  test_description='verify sort functions'
 TEST_PASSES_SANITIZE_LEAK=true
 . ./test-lib.sh

-test_expect_success 'llist_mergesort()' '
+test_expect_success 'DEFINE_LIST_SORT_DEBUG' '
 	test-tool mergesort test
 '