From: "René Scharfe" <l.s.r@web.de>
To: Git List <git@vger.kernel.org>
Cc: Junio C Hamano <gitster@pobox.com>
Subject: [PATCH 3/9] test-mergesort: add test subcommand
Date: Fri, 1 Oct 2021 11:12:27 +0200 [thread overview]
Message-ID: <522fba5e-1048-3377-45c1-7107b55dc6e1@web.de> (raw)
In-Reply-To: <943b1e01-465e-5def-a766-0adf667690de@web.de>
Adapt the qsort certification program from "Engineering a Sort Function"
by Bentley and McIlroy for testing our linked list sort function. It
generates several lists with various distribution patterns and counts
the number of operations llist_mergesort() needs to order them. It
compares the result to the output of a trusted sort function (qsort(1))
and also checks if the sort is stable.
Also add a test script that makes use of the new subcommand.
Signed-off-by: René Scharfe <l.s.r@web.de>
---
t/helper/test-mergesort.c | 232 +++++++++++++++++++++++++++++++++++++-
t/t0071-sort.sh | 11 ++
2 files changed, 242 insertions(+), 1 deletion(-)
create mode 100755 t/t0071-sort.sh
diff --git a/t/helper/test-mergesort.c b/t/helper/test-mergesort.c
index 05be0d067a..8006be8bf8 100644
--- a/t/helper/test-mergesort.c
+++ b/t/helper/test-mergesort.c
@@ -50,9 +50,239 @@ static int sort_stdin(void)
return 0;
}
+static void dist_sawtooth(int *arr, int n, int m)
+{
+ int i;
+ for (i = 0; i < n; i++)
+ arr[i] = i % m;
+}
+
+static void dist_rand(int *arr, int n, int m)
+{
+ int i;
+ for (i = 0; i < n; i++)
+ arr[i] = rand() % m;
+}
+
+static void dist_stagger(int *arr, int n, int m)
+{
+ int i;
+ for (i = 0; i < n; i++)
+ arr[i] = (i * m + i) % n;
+}
+
+static void dist_plateau(int *arr, int n, int m)
+{
+ int i;
+ for (i = 0; i < n; i++)
+ arr[i] = (i < m) ? i : m;
+}
+
+static void dist_shuffle(int *arr, int n, int m)
+{
+ int i, j, k;
+ for (i = j = 0, k = 1; i < n; i++)
+ arr[i] = (rand() % m) ? (j += 2) : (k += 2);
+}
+
+#define DIST(name) { #name, dist_##name }
+
+static struct dist {
+ const char *name;
+ void (*fn)(int *arr, int n, int m);
+} dist[] = {
+ DIST(sawtooth),
+ DIST(rand),
+ DIST(stagger),
+ DIST(plateau),
+ DIST(shuffle),
+};
+
+static void mode_copy(int *arr, int n)
+{
+ /* nothing */
+}
+
+static void mode_reverse(int *arr, int n)
+{
+ int i, j;
+ for (i = 0, j = n - 1; i < j; i++, j--)
+ SWAP(arr[i], arr[j]);
+}
+
+static void mode_reverse_1st_half(int *arr, int n)
+{
+ mode_reverse(arr, n / 2);
+}
+
+static void mode_reverse_2nd_half(int *arr, int n)
+{
+ int half = n / 2;
+ mode_reverse(arr + half, n - half);
+}
+
+static int compare_ints(const void *av, const void *bv)
+{
+ const int *ap = av, *bp = bv;
+ int a = *ap, b = *bp;
+ return (a > b) - (a < b);
+}
+
+static void mode_sort(int *arr, int n)
+{
+ QSORT(arr, n, compare_ints);
+}
+
+static void mode_dither(int *arr, int n)
+{
+ int i;
+ for (i = 0; i < n; i++)
+ arr[i] += i % 5;
+}
+
+#define MODE(name) { #name, mode_##name }
+
+static struct mode {
+ const char *name;
+ void (*fn)(int *arr, int n);
+} mode[] = {
+ MODE(copy),
+ MODE(reverse),
+ MODE(reverse_1st_half),
+ MODE(reverse_2nd_half),
+ MODE(sort),
+ MODE(dither),
+};
+
+static struct stats {
+ int get_next, set_next, compare;
+} stats;
+
+struct number {
+ int value, rank;
+ 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;
+}
+
+static int compare_numbers(const void *av, const void *bv)
+{
+ const struct number *an = av, *bn = bv;
+ int a = an->value, b = bn->value;
+ stats.compare++;
+ return (a > b) - (a < b);
+}
+
+static void clear_numbers(struct number *list)
+{
+ while (list) {
+ struct number *next = list->next;
+ free(list);
+ list = next;
+ }
+}
+
+static int test(const struct dist *dist, const struct mode *mode, int n, int m)
+{
+ int *arr;
+ size_t i;
+ struct number *curr, *list, **tail;
+ int is_sorted = 1;
+ int is_stable = 1;
+ const char *verdict;
+ int result = -1;
+
+ ALLOC_ARRAY(arr, n);
+ dist->fn(arr, n, m);
+ mode->fn(arr, n);
+ for (i = 0, tail = &list; i < n; i++) {
+ curr = xmalloc(sizeof(*curr));
+ curr->value = arr[i];
+ curr->rank = i;
+ *tail = curr;
+ tail = &curr->next;
+ }
+ *tail = NULL;
+
+ stats.get_next = stats.set_next = stats.compare = 0;
+ list = llist_mergesort(list, get_next_number, set_next_number,
+ compare_numbers);
+
+ QSORT(arr, n, compare_ints);
+ for (i = 0, curr = list; i < n && curr; i++, curr = curr->next) {
+ if (arr[i] != curr->value)
+ is_sorted = 0;
+ if (curr->next && curr->value == curr->next->value &&
+ curr->rank >= curr->next->rank)
+ is_stable = 0;
+ }
+ if (i < n) {
+ verdict = "too short";
+ } else if (curr) {
+ verdict = "too long";
+ } else if (!is_sorted) {
+ verdict = "not sorted";
+ } else if (!is_stable) {
+ verdict = "unstable";
+ } else {
+ verdict = "OK";
+ result = 0;
+ }
+
+ printf("%-9s %-16s %8d %8d %8d %8d %8d %s\n",
+ dist->name, mode->name, n, m, stats.get_next, stats.set_next,
+ stats.compare, verdict);
+
+ clear_numbers(list);
+ free(arr);
+
+ return result;
+}
+
+/*
+ * A version of the qsort certification program from "Engineering a Sort
+ * Function" by Bentley and McIlroy, Software—Practice and Experience,
+ * Volume 23, Issue 11, 1249–1265 (November 1993).
+ */
+static int run_tests(int argc, const char **argv)
+{
+ const char *argv_default[] = { "100", "1023", "1024", "1025" };
+ if (!argc)
+ return run_tests(ARRAY_SIZE(argv_default), argv_default);
+ printf("%-9s %-16s %8s %8s %8s %8s %8s %s\n",
+ "distribut", "mode", "n", "m", "get_next", "set_next",
+ "compare", "verdict");
+ while (argc--) {
+ int i, j, m, n = strtol(*argv++, NULL, 10);
+ for (i = 0; i < ARRAY_SIZE(dist); i++) {
+ for (j = 0; j < ARRAY_SIZE(mode); j++) {
+ for (m = 1; m < 2 * n; m *= 2) {
+ if (test(&dist[i], &mode[j], n, m))
+ return 1;
+ }
+ }
+ }
+ }
+ return 0;
+}
+
int cmd__mergesort(int argc, const char **argv)
{
if (argc == 2 && !strcmp(argv[1], "sort"))
return sort_stdin();
- usage("test-tool mergesort sort");
+ if (argc > 1 && !strcmp(argv[1], "test"))
+ return run_tests(argc - 2, argv + 2);
+ fprintf(stderr, "usage: test-tool mergesort sort\n");
+ fprintf(stderr, " or: test-tool mergesort test [<n>...]\n");
+ return 129;
}
diff --git a/t/t0071-sort.sh b/t/t0071-sort.sh
new file mode 100755
index 0000000000..a8ab174879
--- /dev/null
+++ b/t/t0071-sort.sh
@@ -0,0 +1,11 @@
+#!/bin/sh
+
+test_description='verify sort functions'
+
+. ./test-lib.sh
+
+test_expect_success 'llist_mergesort()' '
+ test-tool mergesort test
+'
+
+test_done
--
2.33.0
next prev parent reply other threads:[~2021-10-01 9:12 UTC|newest]
Thread overview: 29+ messages / expand[flat|nested] mbox.gz Atom feed top
2021-10-01 9:07 [PATCH 0/9] mergesort: improve tests and performance René Scharfe
2021-10-01 9:10 ` [PATCH 1/9] test-mergesort: use strbuf_getline() René Scharfe
2021-10-02 9:08 ` Ævar Arnfjörð Bjarmason
2021-10-02 16:56 ` René Scharfe
2021-10-01 9:11 ` [PATCH 2/9] test-mergesort: add sort subcommand René Scharfe
2021-10-01 20:26 ` Junio C Hamano
2021-10-01 9:12 ` René Scharfe [this message]
2021-10-01 20:26 ` [PATCH 3/9] test-mergesort: add test subcommand Junio C Hamano
2021-10-02 8:35 ` Ævar Arnfjörð Bjarmason
2021-10-03 10:15 ` René Scharfe
2021-10-03 17:33 ` Junio C Hamano
2021-10-07 20:00 ` René Scharfe
2021-10-08 4:04 ` [PATCH 10/9 v2] test-mergesort: use repeatable random numbers René Scharfe
2021-10-08 4:17 ` Jeff King
2021-10-08 7:23 ` Ævar Arnfjörð Bjarmason
2021-10-08 17:30 ` René Scharfe
2021-10-08 19:00 ` Ævar Arnfjörð Bjarmason
2021-10-03 10:15 ` [PATCH 3/9] test-mergesort: add test subcommand René Scharfe
2021-10-01 9:14 ` [PATCH 4/9] test-mergesort: add generate subcommand René Scharfe
2021-10-01 9:16 ` [PATCH 5/9] test-mergesort: add unriffle mode René Scharfe
2021-10-01 9:17 ` [PATCH 6/9] test-mergesort: add unriffle_skewed mode René Scharfe
2021-10-01 9:19 ` [PATCH 7/9] p0071: measure sorting of already sorted and reversed files René Scharfe
2021-10-01 9:19 ` [PATCH 8/9] p0071: test performance of llist_mergesort() René Scharfe
2021-10-01 9:22 ` [PATCH 9/9] mergesort: use ranks stack René Scharfe
2022-01-17 17:43 ` Ævar Arnfjörð Bjarmason
2022-01-17 18:22 ` René Scharfe
2022-01-18 5:07 ` René Scharfe
2022-01-18 10:40 ` Ævar Arnfjörð Bjarmason
2022-01-18 12:27 ` René Scharfe
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: http://vger.kernel.org/majordomo-info.html
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=522fba5e-1048-3377-45c1-7107b55dc6e1@web.de \
--to=l.s.r@web.de \
--cc=git@vger.kernel.org \
--cc=gitster@pobox.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this public inbox
https://80x24.org/mirrors/git.git
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).