From f00a039839243c382682a3a5a757e1e6f88abd3d Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Ren=C3=A9=20Scharfe?= Date: Sat, 16 Jul 2022 18:56:32 +0200 Subject: test-mergesort: use DEFINE_LIST_SORT_DEBUG MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit 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 Signed-off-by: Junio C Hamano --- t/helper/test-mergesort.c | 19 ++++--------------- t/t0071-sort.sh | 2 +- 2 files changed, 5 insertions(+), 16 deletions(-) (limited to 't') 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 ' -- cgit v1.2.3 From b378c2ff1e5f87cc7751d39aef97364acdcdf537 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Ren=C3=A9=20Scharfe?= Date: Sat, 16 Jul 2022 18:57:18 +0200 Subject: test-mergesort: use DEFINE_LIST_SORT MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Build a typed sort function for the mergesort performance test tool using DEFINE_LIST_SORT instead of calling llist_mergesort(). This gets rid of the next pointer accessor functions and improves the performance at the cost of a slightly higher object text size. Before: 0071.12: llist_mergesort() unsorted 0.24(0.22+0.01) 0071.14: llist_mergesort() sorted 0.12(0.10+0.01) 0071.16: llist_mergesort() reversed 0.12(0.10+0.01) __TEXT __DATA __OBJC others dec hex 6407 276 0 24701 31384 7a98 t/helper/test-mergesort.o With this patch: 0071.12: DEFINE_LIST_SORT unsorted 0.22(0.21+0.01) 0071.14: DEFINE_LIST_SORT sorted 0.11(0.10+0.01) 0071.16: DEFINE_LIST_SORT reversed 0.11(0.10+0.01) __TEXT __DATA __OBJC others dec hex 6615 276 0 25832 32723 7fd3 t/helper/test-mergesort.o Signed-off-by: René Scharfe Signed-off-by: Junio C Hamano --- t/helper/test-mergesort.c | 15 +++------------ t/perf/p0071-sort.sh | 4 ++-- 2 files changed, 5 insertions(+), 14 deletions(-) (limited to 't') diff --git a/t/helper/test-mergesort.c b/t/helper/test-mergesort.c index 93d15d59a1..202e54a7ff 100644 --- a/t/helper/test-mergesort.c +++ b/t/helper/test-mergesort.c @@ -13,19 +13,10 @@ struct line { struct line *next; }; -static void *get_next(const void *a) -{ - return ((const struct line *)a)->next; -} - -static void set_next(void *a, void *b) -{ - ((struct line *)a)->next = b; -} +DEFINE_LIST_SORT(static, sort_lines, struct line, next); -static int compare_strings(const void *a, const void *b) +static int compare_strings(const struct line *x, const struct line *y) { - const struct line *x = a, *y = b; return strcmp(x->text, y->text); } @@ -47,7 +38,7 @@ static int sort_stdin(void) p = line; } - lines = llist_mergesort(lines, get_next, set_next, compare_strings); + sort_lines(&lines, compare_strings); while (lines) { puts(lines->text); diff --git a/t/perf/p0071-sort.sh b/t/perf/p0071-sort.sh index ed366e2e12..ae4ddac864 100755 --- a/t/perf/p0071-sort.sh +++ b/t/perf/p0071-sort.sh @@ -40,11 +40,11 @@ done for file in unsorted sorted reversed do - test_perf "llist_mergesort() $file" " + test_perf "DEFINE_LIST_SORT $file" " test-tool mergesort sort <$file >actual " - test_expect_success "llist_mergesort() $file sorts like sort(1)" " + test_expect_success "DEFINE_LIST_SORT $file sorts like sort(1)" " test_cmp_bin sorted actual " done -- cgit v1.2.3