{"thread":{"id":"56619","subject":"[PATCH 0/9] mergesort: improve tests and performance","startedAt":"2021-10-01T09:07:14Z","lastAt":"2022-01-18T12:27:18Z","messageCount":29,"participants":["René Scharfe","Junio C Hamano","Ævar Arnfjörð Bjarmason","Jeff King"],"isPatch":true,"patchVersion":1,"patchTotal":9},"messages":[{"id":"437626","messageId":"943b1e01-465e-5def-a766-0adf667690de@web.de","threadId":"56619","inReplyTo":null,"subject":"[PATCH 0/9] mergesort: improve tests and performance","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2021-10-01T09:07:00Z","receivedAt":"2021-10-01T09:07:14Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Our mergesort for linked lists doesn't allocate temporary memory, which\nis nice. It is traversing the list multiple times from start to finish,\nthough. This series teaches it to avoid that, which speeds it up\nconsiderably. But first it improves the associated test helper to\nexercise the code harder and to make the effect of the changes visible\nin terms of saved operations.\n\n test-mergesort: use strbuf_getline()\n test-mergesort: add sort subcommand\n test-mergesort: add test subcommand\n test-mergesort: add generate subcommand\n test-mergesort: add unriffle mode\n test-mergesort: add unriffle_skewed mode\n p0071: measure sorting of already sorted and reversed files\n p0071: test performance of llist_mergesort()\n mergesort: use ranks stack\n\n mergesort.c | 121 +++++++------\n t/helper/test-mergesort.c | 360 +++++++++++++++++++++++++++++++++++++-\n t/perf/p0071-sort.sh | 40 ++++-\n t/t0071-sort.sh | 11 ++\n 4 files changed, 465 insertions(+), 67 deletions(-)\n create mode 100755 t/t0071-sort.sh\n\n--\n2.33.0\n"},{"id":"437627","messageId":"928cb42c-c45b-c90a-c71b-2f6669e03251@web.de","threadId":"56619","inReplyTo":"943b1e01-465e-5def-a766-0adf667690de@web.de","subject":"[PATCH 1/9] test-mergesort: use strbuf_getline()","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2021-10-01T09:10:09Z","receivedAt":"2021-10-01T09:10:25Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Strip line ending characters to make sure empty lines are sorted like\nsort(1) does.\n\nSigned-off-by: René Scharfe \n---\n t/helper/test-mergesort.c | 6 ++----\n 1 file changed, 2 insertions(+), 4 deletions(-)\n\ndiff --git a/t/helper/test-mergesort.c b/t/helper/test-mergesort.c\nindex c5cffaa4b7..621e2a5197 100644\n--- a/t/helper/test-mergesort.c\n+++ b/t/helper/test-mergesort.c\n@@ -28,9 +28,7 @@ int cmd__mergesort(int argc, const char **argv)\n \tstruct line *line, *p = NULL, *lines = NULL;\n \tstruct strbuf sb = STRBUF_INIT;\n\n-\tfor (;;) {\n-\t\tif (strbuf_getwholeline(&sb, stdin, '\\n'))\n-\t\t\tbreak;\n+\twhile (!strbuf_getline(&sb, stdin)) {\n \t\tline = xmalloc(sizeof(struct line));\n \t\tline->text = strbuf_detach(&sb, NULL);\n \t\tif (p) {\n@@ -46,7 +44,7 @@ int cmd__mergesort(int argc, const char **argv)\n \tlines = llist_mergesort(lines, get_next, set_next, compare_strings);\n\n \twhile (lines) {\n-\t\tprintf(\"%s\", lines->text);\n+\t\tputs(lines->text);\n \t\tlines = lines->next;\n \t}\n \treturn 0;\n--\n2.33.0\n\n"},{"id":"437628","messageId":"f0a8c3c5-4c51-5128-42a3-3dadb8600a6f@web.de","threadId":"56619","inReplyTo":"943b1e01-465e-5def-a766-0adf667690de@web.de","subject":"[PATCH 2/9] test-mergesort: add sort subcommand","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2021-10-01T09:11:19Z","receivedAt":"2021-10-01T09:11:24Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Give the code for sorting a text file its own sub-command. This allows\nextending the helper, which we'll do in the following patches.\n\nSigned-off-by: René Scharfe \n---\n t/helper/test-mergesort.c | 9 ++++++++-\n 1 file changed, 8 insertions(+), 1 deletion(-)\n\ndiff --git a/t/helper/test-mergesort.c b/t/helper/test-mergesort.c\nindex 621e2a5197..05be0d067a 100644\n--- a/t/helper/test-mergesort.c\n+++ b/t/helper/test-mergesort.c\n@@ -23,7 +23,7 @@ static int compare_strings(const void *a, const void *b)\n \treturn strcmp(x->text, y->text);\n }\n\n-int cmd__mergesort(int argc, const char **argv)\n+static int sort_stdin(void)\n {\n \tstruct line *line, *p = NULL, *lines = NULL;\n \tstruct strbuf sb = STRBUF_INIT;\n@@ -49,3 +49,10 @@ int cmd__mergesort(int argc, const char **argv)\n \t}\n \treturn 0;\n }\n+\n+int cmd__mergesort(int argc, const char **argv)\n+{\n+\tif (argc == 2 && !strcmp(argv[1], \"sort\"))\n+\t\treturn sort_stdin();\n+\tusage(\"test-tool mergesort sort\");\n+}\n--\n2.33.0\n"},{"id":"437629","messageId":"522fba5e-1048-3377-45c1-7107b55dc6e1@web.de","threadId":"56619","inReplyTo":"943b1e01-465e-5def-a766-0adf667690de@web.de","subject":"[PATCH 3/9] test-mergesort: add test subcommand","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2021-10-01T09:12:27Z","receivedAt":"2021-10-01T09:12:32Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Adapt the qsort certification program from \"Engineering a Sort Function\"\nby Bentley and McIlroy for testing our linked list sort function. It\ngenerates several lists with various distribution patterns and counts\nthe number of operations llist_mergesort() needs to order them. It\ncompares the result to the output of a trusted sort function (qsort(1))\nand also checks if the sort is stable.\n\nAlso add a test script that makes use of the new subcommand.\n\nSigned-off-by: René Scharfe \n---\n t/helper/test-mergesort.c | 232 +++++++++++++++++++++++++++++++++++++-\n t/t0071-sort.sh | 11 ++\n 2 files changed, 242 insertions(+), 1 deletion(-)\n create mode 100755 t/t0071-sort.sh\n\ndiff --git a/t/helper/test-mergesort.c b/t/helper/test-mergesort.c\nindex 05be0d067a..8006be8bf8 100644\n--- a/t/helper/test-mergesort.c\n+++ b/t/helper/test-mergesort.c\n@@ -50,9 +50,239 @@ static int sort_stdin(void)\n \treturn 0;\n }\n\n+static void dist_sawtooth(int *arr, int n, int m)\n+{\n+\tint i;\n+\tfor (i = 0; i < n; i++)\n+\t\tarr[i] = i % m;\n+}\n+\n+static void dist_rand(int *arr, int n, int m)\n+{\n+\tint i;\n+\tfor (i = 0; i < n; i++)\n+\t\tarr[i] = rand() % m;\n+}\n+\n+static void dist_stagger(int *arr, int n, int m)\n+{\n+\tint i;\n+\tfor (i = 0; i < n; i++)\n+\t\tarr[i] = (i * m + i) % n;\n+}\n+\n+static void dist_plateau(int *arr, int n, int m)\n+{\n+\tint i;\n+\tfor (i = 0; i < n; i++)\n+\t\tarr[i] = (i < m) ? i : m;\n+}\n+\n+static void dist_shuffle(int *arr, int n, int m)\n+{\n+\tint i, j, k;\n+\tfor (i = j = 0, k = 1; i < n; i++)\n+\t\tarr[i] = (rand() % m) ? (j += 2) : (k += 2);\n+}\n+\n+#define DIST(name) { #name, dist_##name }\n+\n+static struct dist {\n+\tconst char *name;\n+\tvoid (*fn)(int *arr, int n, int m);\n+} dist[] = {\n+\tDIST(sawtooth),\n+\tDIST(rand),\n+\tDIST(stagger),\n+\tDIST(plateau),\n+\tDIST(shuffle),\n+};\n+\n+static void mode_copy(int *arr, int n)\n+{\n+\t/* nothing */\n+}\n+\n+static void mode_reverse(int *arr, int n)\n+{\n+\tint i, j;\n+\tfor (i = 0, j = n - 1; i < j; i++, j--)\n+\t\tSWAP(arr[i], arr[j]);\n+}\n+\n+static void mode_reverse_1st_half(int *arr, int n)\n+{\n+\tmode_reverse(arr, n / 2);\n+}\n+\n+static void mode_reverse_2nd_half(int *arr, int n)\n+{\n+\tint half = n / 2;\n+\tmode_reverse(arr + half, n - half);\n+}\n+\n+static int compare_ints(const void *av, const void *bv)\n+{\n+\tconst int *ap = av, *bp = bv;\n+\tint a = *ap, b = *bp;\n+\treturn (a > b) - (a < b);\n+}\n+\n+static void mode_sort(int *arr, int n)\n+{\n+\tQSORT(arr, n, compare_ints);\n+}\n+\n+static void mode_dither(int *arr, int n)\n+{\n+\tint i;\n+\tfor (i = 0; i < n; i++)\n+\t\tarr[i] += i % 5;\n+}\n+\n+#define MODE(name) { #name, mode_##name }\n+\n+static struct mode {\n+\tconst char *name;\n+\tvoid (*fn)(int *arr, int n);\n+} mode[] = {\n+\tMODE(copy),\n+\tMODE(reverse),\n+\tMODE(reverse_1st_half),\n+\tMODE(reverse_2nd_half),\n+\tMODE(sort),\n+\tMODE(dither),\n+};\n+\n+static struct stats {\n+\tint get_next, set_next, compare;\n+} stats;\n+\n+struct number {\n+\tint value, rank;\n+\tstruct number *next;\n+};\n+\n+static void *get_next_number(const void *a)\n+{\n+\tstats.get_next++;\n+\treturn ((const struct number *)a)->next;\n+}\n+\n+static void set_next_number(void *a, void *b)\n+{\n+\tstats.set_next++;\n+\t((struct number *)a)->next = b;\n+}\n+\n+static int compare_numbers(const void *av, const void *bv)\n+{\n+\tconst struct number *an = av, *bn = bv;\n+\tint a = an->value, b = bn->value;\n+\tstats.compare++;\n+\treturn (a > b) - (a < b);\n+}\n+\n+static void clear_numbers(struct number *list)\n+{\n+\twhile (list) {\n+\t\tstruct number *next = list->next;\n+\t\tfree(list);\n+\t\tlist = next;\n+\t}\n+}\n+\n+static int test(const struct dist *dist, const struct mode *mode, int n, int m)\n+{\n+\tint *arr;\n+\tsize_t i;\n+\tstruct number *curr, *list, **tail;\n+\tint is_sorted = 1;\n+\tint is_stable = 1;\n+\tconst char *verdict;\n+\tint result = -1;\n+\n+\tALLOC_ARRAY(arr, n);\n+\tdist->fn(arr, n, m);\n+\tmode->fn(arr, n);\n+\tfor (i = 0, tail = &list; i < n; i++) {\n+\t\tcurr = xmalloc(sizeof(*curr));\n+\t\tcurr->value = arr[i];\n+\t\tcurr->rank = i;\n+\t\t*tail = curr;\n+\t\ttail = &curr->next;\n+\t}\n+\t*tail = NULL;\n+\n+\tstats.get_next = stats.set_next = stats.compare = 0;\n+\tlist = llist_mergesort(list, get_next_number, set_next_number,\n+\t\t\t compare_numbers);\n+\n+\tQSORT(arr, n, compare_ints);\n+\tfor (i = 0, curr = list; i < n && curr; i++, curr = curr->next) {\n+\t\tif (arr[i] != curr->value)\n+\t\t\tis_sorted = 0;\n+\t\tif (curr->next && curr->value == curr->next->value &&\n+\t\t curr->rank >= curr->next->rank)\n+\t\t\tis_stable = 0;\n+\t}\n+\tif (i < n) {\n+\t\tverdict = \"too short\";\n+\t} else if (curr) {\n+\t\tverdict = \"too long\";\n+\t} else if (!is_sorted) {\n+\t\tverdict = \"not sorted\";\n+\t} else if (!is_stable) {\n+\t\tverdict = \"unstable\";\n+\t} else {\n+\t\tverdict = \"OK\";\n+\t\tresult = 0;\n+\t}\n+\n+\tprintf(\"%-9s %-16s %8d %8d %8d %8d %8d %s\\n\",\n+\t dist->name, mode->name, n, m, stats.get_next, stats.set_next,\n+\t stats.compare, verdict);\n+\n+\tclear_numbers(list);\n+\tfree(arr);\n+\n+\treturn result;\n+}\n+\n+/*\n+ * A version of the qsort certification program from \"Engineering a Sort\n+ * Function\" by Bentley and McIlroy, Software—Practice and Experience,\n+ * Volume 23, Issue 11, 1249–1265 (November 1993).\n+ */\n+static int run_tests(int argc, const char **argv)\n+{\n+\tconst char *argv_default[] = { \"100\", \"1023\", \"1024\", \"1025\" };\n+\tif (!argc)\n+\t\treturn run_tests(ARRAY_SIZE(argv_default), argv_default);\n+\tprintf(\"%-9s %-16s %8s %8s %8s %8s %8s %s\\n\",\n+\t \"distribut\", \"mode\", \"n\", \"m\", \"get_next\", \"set_next\",\n+\t \"compare\", \"verdict\");\n+\twhile (argc--) {\n+\t\tint i, j, m, n = strtol(*argv++, NULL, 10);\n+\t\tfor (i = 0; i < ARRAY_SIZE(dist); i++) {\n+\t\t\tfor (j = 0; j < ARRAY_SIZE(mode); j++) {\n+\t\t\t\tfor (m = 1; m < 2 * n; m *= 2) {\n+\t\t\t\t\tif (test(&dist[i], &mode[j], n, m))\n+\t\t\t\t\t\treturn 1;\n+\t\t\t\t}\n+\t\t\t}\n+\t\t}\n+\t}\n+\treturn 0;\n+}\n+\n int cmd__mergesort(int argc, const char **argv)\n {\n \tif (argc == 2 && !strcmp(argv[1], \"sort\"))\n \t\treturn sort_stdin();\n-\tusage(\"test-tool mergesort sort\");\n+\tif (argc > 1 && !strcmp(argv[1], \"test\"))\n+\t\treturn run_tests(argc - 2, argv + 2);\n+\tfprintf(stderr, \"usage: test-tool mergesort sort\\n\");\n+\tfprintf(stderr, \" or: test-tool mergesort test [...]\\n\");\n+\treturn 129;\n }\ndiff --git a/t/t0071-sort.sh b/t/t0071-sort.sh\nnew file mode 100755\nindex 0000000000..a8ab174879\n--- /dev/null\n+++ b/t/t0071-sort.sh\n@@ -0,0 +1,11 @@\n+#!/bin/sh\n+\n+test_description='verify sort functions'\n+\n+. ./test-lib.sh\n+\n+test_expect_success 'llist_mergesort()' '\n+\ttest-tool mergesort test\n+'\n+\n+test_done\n--\n2.33.0\n"},{"id":"437631","messageId":"1b6e34fc-b758-f6e7-39b2-e73f309591bd@web.de","threadId":"56619","inReplyTo":"943b1e01-465e-5def-a766-0adf667690de@web.de","subject":"[PATCH 4/9] test-mergesort: add generate subcommand","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2021-10-01T09:14:32Z","receivedAt":"2021-10-01T09:14:38Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Add a subcommand for printing test data. It can be used to generate\nspecial test cases and feed them into the sort subcommand or sort(1) for\nperformance measurements. It may also be useful to illustrate the\neffect of distributions, modes and their parameters.\n\nIt generates n integers with the specified distribution and its\ndistribution-specific parameter m. E.g. m is the maximum value for\nthe plateau distribution and the length and height of individual teeth\nof the sawtooth distribution.\n\nThe generated values are printed as zero-padded eight-digit hexadecimal\nnumbers to make sure alphabetic and numeric order are the same.\n\nSigned-off-by: René Scharfe \n---\n t/helper/test-mergesort.c | 60 ++++++++++++++++++++++++++++++++++++++-\n 1 file changed, 59 insertions(+), 1 deletion(-)\n\ndiff --git a/t/helper/test-mergesort.c b/t/helper/test-mergesort.c\nindex 8006be8bf8..27ba252d4a 100644\n--- a/t/helper/test-mergesort.c\n+++ b/t/helper/test-mergesort.c\n@@ -98,6 +98,16 @@ static struct dist {\n \tDIST(shuffle),\n };\n\n+static const struct dist *get_dist_by_name(const char *name)\n+{\n+\tint i;\n+\tfor (i = 0; i < ARRAY_SIZE(dist); i++) {\n+\t if (!strcmp(dist[i].name, name))\n+\t\t return &dist[i];\n+\t}\n+\treturn NULL;\n+}\n+\n static void mode_copy(int *arr, int n)\n {\n \t/* nothing */\n@@ -154,6 +164,41 @@ static struct mode {\n \tMODE(dither),\n };\n\n+static const struct mode *get_mode_by_name(const char *name)\n+{\n+\tint i;\n+\tfor (i = 0; i < ARRAY_SIZE(mode); i++) {\n+\t if (!strcmp(mode[i].name, name))\n+\t\t return &mode[i];\n+\t}\n+\treturn NULL;\n+}\n+\n+static int generate(int argc, const char **argv)\n+{\n+\tconst struct dist *dist = NULL;\n+\tconst struct mode *mode = NULL;\n+\tint i, n, m, *arr;\n+\n+\tif (argc != 4)\n+\t\treturn 1;\n+\n+\tdist = get_dist_by_name(argv[0]);\n+\tmode = get_mode_by_name(argv[1]);\n+\tn = strtol(argv[2], NULL, 10);\n+\tm = strtol(argv[3], NULL, 10);\n+\tif (!dist || !mode)\n+\t\treturn 1;\n+\n+\tALLOC_ARRAY(arr, n);\n+\tdist->fn(arr, n, m);\n+\tmode->fn(arr, n);\n+\tfor (i = 0; i < n; i++)\n+\t\tprintf(\"%08x\\n\", arr[i]);\n+\tfree(arr);\n+\treturn 0;\n+}\n+\n static struct stats {\n \tint get_next, set_next, compare;\n } stats;\n@@ -278,11 +323,24 @@ static int run_tests(int argc, const char **argv)\n\n int cmd__mergesort(int argc, const char **argv)\n {\n+\tint i;\n+\tconst char *sep;\n+\n+\tif (argc == 6 && !strcmp(argv[1], \"generate\"))\n+\t\treturn generate(argc - 2, argv + 2);\n \tif (argc == 2 && !strcmp(argv[1], \"sort\"))\n \t\treturn sort_stdin();\n \tif (argc > 1 && !strcmp(argv[1], \"test\"))\n \t\treturn run_tests(argc - 2, argv + 2);\n-\tfprintf(stderr, \"usage: test-tool mergesort sort\\n\");\n+\tfprintf(stderr, \"usage: test-tool mergesort generate \\n\");\n+\tfprintf(stderr, \" or: test-tool mergesort sort\\n\");\n \tfprintf(stderr, \" or: test-tool mergesort test [...]\\n\");\n+\tfprintf(stderr, \"\\n\");\n+\tfor (i = 0, sep = \"distributions: \"; i < ARRAY_SIZE(dist); i++, sep = \", \")\n+\t\tfprintf(stderr, \"%s%s\", sep, dist[i].name);\n+\tfprintf(stderr, \"\\n\");\n+\tfor (i = 0, sep = \"modes: \"; i < ARRAY_SIZE(mode); i++, sep = \", \")\n+\t\tfprintf(stderr, \"%s%s\", sep, mode[i].name);\n+\tfprintf(stderr, \"\\n\");\n \treturn 129;\n }\n--\n2.33.0\n"},{"id":"437632","messageId":"fbeacc0e-d870-2aef-3177-9b661ffc6768@web.de","threadId":"56619","inReplyTo":"943b1e01-465e-5def-a766-0adf667690de@web.de","subject":"[PATCH 5/9] test-mergesort: add unriffle mode","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2021-10-01T09:16:49Z","receivedAt":"2021-10-01T09:16:56Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Add a mode that turns sorted items into adversarial input for mergesort.\nDo that by running mergesort in reverse and rearranging the items in\nsuch a way that each merge needs the maximum number of operations to\nundo it.\n\nTo riffle is a card shuffling technique and involves splitting a deck\ninto two and then to interleave them. A perfect riffle takes one card\nfrom each half in turn. That's similar to the most expensive merge,\nwhich has to take one item from each sublist in turn, which requires the\nmaximum number of comparisons (n-1).\n\nSo unriffle does that in reverse, i.e. it generates the first sublist\nout of the items at even indexes and the second sublist out of the items\nat odd indexes, without changing their order in any other way. Done\nrecursively until we reach the trivial sublist length of one, this\ntwists the list into an order that requires the maximum effort for\nmergesort to untangle.\n\nAs a baseline, here are the rand distributions with the highest number\nof comparisons from \"test-tool mergesort test\":\n\n $ t/helper/test-tool mergesort test | awk '\n NR > 1 && $1 != \"rand\" {next}\n $7 > max[$3] {max[$3] = $7; line[$3] = $0}\n END {for (n in line) print line[n]}\n '\n\ndistribut mode n m get_next set_next compare verdict\nrand copy 100 32 1184 700 569 OK\nrand reverse_1st_half 1023 256 16373 10230 8976 OK\nrand reverse_1st_half 1024 512 16384 10240 8993 OK\nrand dither 1025 64 18454 11275 9970 OK\n\nAnd here are the most expensive ones overall:\n\n $ t/helper/test-tool mergesort test | awk '\n $7 > max[$3] {max[$3] = $7; line[$3] = $0}\n END {for (n in line) print line[n]}\n '\n\ndistribut mode n m get_next set_next compare verdict\nstagger reverse 100 64 1184 700 580 OK\nsawtooth unriffle 1023 1024 16373 10230 9179 OK\nsawtooth unriffle 1024 1024 16384 10240 9217 OK\nstagger unriffle 1025 2048 18454 11275 10241 OK\n\nThe sawtooth distribution with m>=n generates a sorted list. The\nunriffle mode is designed to turn that into adversarial input for\nmergesort, and that checks out for n=1023 and n=1024, where it produces\nthe list that requires the most comparisons.\n\nItem counts that are not powers of two have other winners, and that's\nbecause unriffle recursively splits lists into equal-sized halves, while\nllist_mergesort() splits them into the biggest power of two smaller than\nn and the rest, e.g. for n=1025 it sorts the first 1024 separately and\nfinally merges them to the last item.\n\nSo unriffle mode works as designed for the intended use case, but to\nconsistently generate adversarial input for unbalanced merges we need\nsomething else.\n\nSigned-off-by: René Scharfe \n---\n t/helper/test-mergesort.c | 29 +++++++++++++++++++++++++++++\n 1 file changed, 29 insertions(+)\n\ndiff --git a/t/helper/test-mergesort.c b/t/helper/test-mergesort.c\nindex 27ba252d4a..d71ef568f3 100644\n--- a/t/helper/test-mergesort.c\n+++ b/t/helper/test-mergesort.c\n@@ -150,6 +150,34 @@ static void mode_dither(int *arr, int n)\n \t\tarr[i] += i % 5;\n }\n\n+static void unriffle(int *arr, int n, int *tmp)\n+{\n+\tint i, j;\n+\tCOPY_ARRAY(tmp, arr, n);\n+\tfor (i = j = 0; i < n; i += 2)\n+\t\tarr[j++] = tmp[i];\n+\tfor (i = 1; i < n; i += 2)\n+\t\tarr[j++] = tmp[i];\n+}\n+\n+static void unriffle_recursively(int *arr, int n, int *tmp)\n+{\n+\tif (n > 1) {\n+\t\tint half = n / 2;\n+\t\tunriffle(arr, n, tmp);\n+\t\tunriffle_recursively(arr, half, tmp);\n+\t\tunriffle_recursively(arr + half, n - half, tmp);\n+\t}\n+}\n+\n+static void mode_unriffle(int *arr, int n)\n+{\n+\tint *tmp;\n+\tALLOC_ARRAY(tmp, n);\n+\tunriffle_recursively(arr, n, tmp);\n+\tfree(tmp);\n+}\n+\n #define MODE(name) { #name, mode_##name }\n\n static struct mode {\n@@ -162,6 +190,7 @@ static struct mode {\n \tMODE(reverse_2nd_half),\n \tMODE(sort),\n \tMODE(dither),\n+\tMODE(unriffle),\n };\n\n static const struct mode *get_mode_by_name(const char *name)\n--\n2.33.0\n"},{"id":"437651","messageId":"8763ebde-772c-500c-20fc-cbde43dcefeb@web.de","threadId":"56619","inReplyTo":"943b1e01-465e-5def-a766-0adf667690de@web.de","subject":"[PATCH 6/9] test-mergesort: add unriffle_skewed mode","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2021-10-01T09:17:57Z","receivedAt":"2021-10-01T09:18:02Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Add a mode that turns a sorted list into adversarial input for a\nbottom-up mergesort implementation that doubles the length of sorted\nsublists at each level -- like our llist_mergesort().\n\nWhile unriffle mode splits the list in half at each recursion step,\nunriffle_skewed splits it into 2^l items and the rest, with 2^l being\nthe highest power of two smaller than the number of items and thus\n2^l >= rest. The rest is unriffled with the tail of the first half to\nrequire a merge to compare the maximum number of elements.\n\nIt complements the unriffle mode, which targets balanced merges. If\nthe number of elements is a power of two then both actually produce the\nsame result, as 2^l == rest == n/2 at each recursion step in that case.\n\nHere are the results:\n\n $ t/helper/test-tool mergesort test | awk '\n $7 > max[$3] {max[$3] = $7; line[$3] = $0}\n END {for (n in line) print line[n]}\n '\n\ndistribut mode n m get_next set_next compare verdict\nsawtooth unriffle_skewed 100 128 1184 700 589 OK\nsawtooth unriffle_skewed 1023 1024 16373 10230 9207 OK\nsawtooth unriffle 1024 1024 16384 10240 9217 OK\nsawtooth unriffle_skewed 1025 2048 18454 11275 10241 OK\n\nThe sawtooth distribution with m>=n produces a sorted list and\nunriffle_skewed mode turns it into adversarial input for unbalanced\nmerges, which it wins in all cases except for n=1024 -- the resulting\nlist is the same, but unriffle is tested before unriffle_skewed, so its\nresult is selected by the AWK script.\n\nSigned-off-by: René Scharfe \n---\n t/helper/test-mergesort.c | 28 ++++++++++++++++++++++++++++\n 1 file changed, 28 insertions(+)\n\ndiff --git a/t/helper/test-mergesort.c b/t/helper/test-mergesort.c\nindex d71ef568f3..43ec74e2d3 100644\n--- a/t/helper/test-mergesort.c\n+++ b/t/helper/test-mergesort.c\n@@ -178,6 +178,33 @@ static void mode_unriffle(int *arr, int n)\n \tfree(tmp);\n }\n\n+static unsigned int prev_pow2(unsigned int n)\n+{\n+\tunsigned int pow2 = 1;\n+\twhile (pow2 * 2 < n)\n+\t\tpow2 *= 2;\n+\treturn pow2;\n+}\n+\n+static void unriffle_recursively_skewed(int *arr, int n, int *tmp)\n+{\n+\tif (n > 1) {\n+\t\tint pow2 = prev_pow2(n);\n+\t\tint rest = n - pow2;\n+\t\tunriffle(arr + pow2 - rest, rest * 2, tmp);\n+\t\tunriffle_recursively_skewed(arr, pow2, tmp);\n+\t\tunriffle_recursively_skewed(arr + pow2, rest, tmp);\n+\t}\n+}\n+\n+static void mode_unriffle_skewed(int *arr, int n)\n+{\n+\tint *tmp;\n+\tALLOC_ARRAY(tmp, n);\n+\tunriffle_recursively_skewed(arr, n, tmp);\n+\tfree(tmp);\n+}\n+\n #define MODE(name) { #name, mode_##name }\n\n static struct mode {\n@@ -191,6 +218,7 @@ static struct mode {\n \tMODE(sort),\n \tMODE(dither),\n \tMODE(unriffle),\n+\tMODE(unriffle_skewed),\n };\n\n static const struct mode *get_mode_by_name(const char *name)\n--\n2.33.0\n"},{"id":"437652","messageId":"3fa28f14-5e53-7367-b628-6eab2d5737be@web.de","threadId":"56619","inReplyTo":"943b1e01-465e-5def-a766-0adf667690de@web.de","subject":"[PATCH 7/9] p0071: measure sorting of already sorted and reversed files","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2021-10-01T09:19:04Z","receivedAt":"2021-10-01T09:19:10Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Check if sorting takes advantage of already sorted or reversed content,\nor if that corner case actually decreases performance, like it would for\na simplistic quicksort implementation.\n\nSigned-off-by: René Scharfe \n---\n t/perf/p0071-sort.sh | 29 ++++++++++++++++++++++-------\n 1 file changed, 22 insertions(+), 7 deletions(-)\n\ndiff --git a/t/perf/p0071-sort.sh b/t/perf/p0071-sort.sh\nindex 6e924f5fa3..5b39b68f35 100755\n--- a/t/perf/p0071-sort.sh\n+++ b/t/perf/p0071-sort.sh\n@@ -11,16 +11,31 @@ test_expect_success 'setup' '\n \tgit cat-file --batch >unsorted\n '\n\n-test_perf 'sort(1)' '\n-\tsort expect\n+test_perf 'sort(1) unsorted' '\n+\tsort sorted\n '\n\n-test_perf 'string_list_sort()' '\n-\ttest-tool string-list sort actual\n+test_expect_success 'reverse' '\n+\tsort -r reversed\n '\n\n-test_expect_success 'string_list_sort() sorts like sort(1)' '\n-\ttest_cmp_bin expect actual\n-'\n+for file in sorted reversed\n+do\n+\ttest_perf \"sort(1) $file\" \"\n+\t\tsort <$file >actual\n+\t\"\n+done\n+\n+for file in unsorted sorted reversed\n+do\n+\n+\ttest_perf \"string_list_sort() $file\" \"\n+\t\ttest-tool string-list sort <$file >actual\n+\t\"\n+\n+\ttest_expect_success \"string_list_sort() $file sorts like sort(1)\" \"\n+\t\ttest_cmp_bin sorted actual\n+\t\"\n+done\n\n test_done\n--\n2.33.0\n"},{"id":"437653","messageId":"9ecbd8c8-2907-7955-0b85-f9bbae8475d1@web.de","threadId":"56619","inReplyTo":"943b1e01-465e-5def-a766-0adf667690de@web.de","subject":"[PATCH 8/9] p0071: test performance of llist_mergesort()","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2021-10-01T09:19:51Z","receivedAt":"2021-10-01T09:19:58Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Signed-off-by: René Scharfe \n---\n t/perf/p0071-sort.sh | 11 +++++++++++\n 1 file changed, 11 insertions(+)\n\ndiff --git a/t/perf/p0071-sort.sh b/t/perf/p0071-sort.sh\nindex 5b39b68f35..ed366e2e12 100755\n--- a/t/perf/p0071-sort.sh\n+++ b/t/perf/p0071-sort.sh\n@@ -38,4 +38,15 @@ do\n \t\"\n done\n\n+for file in unsorted sorted reversed\n+do\n+\ttest_perf \"llist_mergesort() $file\" \"\n+\t\ttest-tool mergesort sort <$file >actual\n+\t\"\n+\n+\ttest_expect_success \"llist_mergesort() $file sorts like sort(1)\" \"\n+\t\ttest_cmp_bin sorted actual\n+\t\"\n+done\n+\n test_done\n--\n2.33.0\n"},{"id":"437654","messageId":"636647b1-f666-f1e2-4127-ee0869b61036@web.de","threadId":"56619","inReplyTo":"943b1e01-465e-5def-a766-0adf667690de@web.de","subject":"[PATCH 9/9] mergesort: use ranks stack","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2021-10-01T09:22:39Z","receivedAt":"2021-10-01T09:22:46Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"The bottom-up mergesort implementation needs to skip through sublists a\nlot. A recursive version could avoid that, but would require log2(n)\nstack frames. Explicitly manage a stack of sorted sublists of various\nlengths instead to avoid fast-forwarding while also keeping a lid on\nmemory usage.\n\nWhile this patch was developed independently, a ranks stack is also used\nin https://github.com/mono/mono/blob/master/mono/eglib/sort.frag.h by\nthe Mono project.\n\nThe idea is to keep slots for log2(n_max) sorted sublists, one for each\npower of 2. Such a construct can accommodate lists of any length up to\nn_max. Since there is a known maximum number of items (effectively\nSIZE_MAX), we can preallocate the whole rank stack.\n\nWe add items one by one, which is akin to incrementing a binary number.\nMake use of that by keeping track of the number of items and check bits\nin it instead of checking for NULL in the rank stack when checking if a\nsublist of a certain rank exists, in order to avoid memory accesses.\n\nThe first item can go into the empty first slot as a sublist of length\n2^0. The second one needs to be merged with the previous sublist and\nthe result goes into the empty second slot as a sublist of length 2^1.\nThe third one goes into vacated first slot and so on. At the end we\nmerge all the sublists to get the result.\n\nThe new version still performs a stable sort by making sure to put items\nseen earlier first when the compare function indicates equality. That's\ndone by preferring items from sublists with a higher rank.\n\nThe new merge function also tries to minimize the number of operations.\nLike blame.c::blame_merge(), the function doesn't set the next pointer\nif it already points to the right item, and it exits when it reaches the\nend of one of the two sublists that it's given. The old code couldn't\ndo the latter because it kept all items in a single list.\n\nThe number of comparisons stays the same, though. Here's example output\nof \"test-tool mergesort test\" for the rand distributions with the most\nnumber of comparisons with the ranks stack:\n\n $ t/helper/test-tool mergesort test | awk '\n NR > 1 && $1 != \"rand\" {next}\n $7 > max[$3] {max[$3] = $7; line[$3] = $0}\n END {for (n in line) print line[n]}\n '\n\ndistribut mode n m get_next set_next compare verdict\nrand copy 100 32 669 420 569 OK\nrand dither 1023 64 9997 5396 8974 OK\nrand dither 1024 512 10007 6159 8983 OK\nrand dither 1025 256 10993 5988 9968 OK\n\nHere are the differences to the results without this patch:\n\ndistribut mode n m get_next set_next compare\nrand copy 100 32 -515 -280 0\nrand dither 1023 64 -6376 -4834 0\nrand dither 1024 512 -6377 -4081 0\nrand dither 1025 256 -7461 -5287 0\n\nThe numbers of get_next and set_next calls are reduced significantly.\n\nNB: These winners are different than the ones shown in the patch that\nintroduced the unriffle mode because the addition of the unriffle_skewed\nmode in between changed the consumption of rand() values.\n\nHere are the distributions with the most comparisons overall with the\nranks stack:\n\n $ t/helper/test-tool mergesort test | awk '\n $7 > max[$3] {max[$3] = $7; line[$3] = $0}\n END {for (n in line) print line[n]}\n '\n\ndistribut mode n m get_next set_next compare verdict\nsawtooth unriffle_skewed 100 128 689 632 589 OK\nsawtooth unriffle_skewed 1023 1024 10230 10220 9207 OK\nsawtooth unriffle 1024 1024 10241 10240 9217 OK\nsawtooth unriffle_skewed 1025 2048 11266 10242 10241 OK\n\nAnd here the differences to before:\n\ndistribut mode n m get_next set_next compare\nsawtooth unriffle_skewed 100 128 -495 -68 0\nsawtooth unriffle_skewed 1023 1024 -6143 -10 0\nsawtooth unriffle 1024 1024 -6143 0 0\nsawtooth unriffle_skewed 1025 2048 -7188 -1033 0\n\nWe get a similar reduction of get_next calls here, but only a slight\nreduction of set_next calls, if at all.\n\nAnd here are the results of p0071-sort.sh before:\n\n0071.12: llist_mergesort() unsorted 0.36(0.33+0.01)\n0071.14: llist_mergesort() sorted 0.15(0.13+0.01)\n0071.16: llist_mergesort() reversed 0.16(0.14+0.01)\n\n... and here the ones with this patch:\n\n0071.12: llist_mergesort() unsorted 0.24(0.22+0.01)\n0071.14: llist_mergesort() sorted 0.12(0.10+0.01)\n0071.16: llist_mergesort() reversed 0.12(0.10+0.01)\n\nNB: We can't use t/perf/run to compare revisions in one run because it\nuses the test-tool from the worktree, not from the revisions being\ntested.\n\nSigned-off-by: René Scharfe \n---\n mergesort.c | 121 ++++++++++++++++++++++++++++------------------------\n 1 file changed, 66 insertions(+), 55 deletions(-)\n\ndiff --git a/mergesort.c b/mergesort.c\nindex e5fdf2ee4a..6216835566 100644\n--- a/mergesort.c\n+++ b/mergesort.c\n@@ -1,73 +1,84 @@\n #include \"cache.h\"\n #include \"mergesort.h\"\n\n-struct mergesort_sublist {\n-\tvoid *ptr;\n-\tunsigned long len;\n-};\n-\n-static void *get_nth_next(void *list, unsigned long n,\n-\t\t\t void *(*get_next_fn)(const void *))\n+/* Combine two sorted lists. Take from `list` on equality. */\n+static void *llist_merge(void *list, void *other,\n+\t\t\t void *(*get_next_fn)(const void *),\n+\t\t\t void (*set_next_fn)(void *, void *),\n+\t\t\t int (*compare_fn)(const void *, const void *))\n {\n-\twhile (n-- && list)\n-\t\tlist = get_next_fn(list);\n-\treturn list;\n-}\n+\tvoid *result = list, *tail;\n\n-static void *pop_item(struct mergesort_sublist *l,\n-\t\t void *(*get_next_fn)(const void *))\n-{\n-\tvoid *p = l->ptr;\n-\tl->ptr = get_next_fn(l->ptr);\n-\tl->len = l->ptr ? (l->len - 1) : 0;\n-\treturn p;\n+\tif (compare_fn(list, other) > 0) {\n+\t\tresult = other;\n+\t\tgoto other;\n+\t}\n+\tfor (;;) {\n+\t\tdo {\n+\t\t\ttail = list;\n+\t\t\tlist = get_next_fn(list);\n+\t\t\tif (!list) {\n+\t\t\t\tset_next_fn(tail, other);\n+\t\t\t\treturn result;\n+\t\t\t}\n+\t\t} while (compare_fn(list, other) <= 0);\n+\t\tset_next_fn(tail, other);\n+\tother:\n+\t\tdo {\n+\t\t\ttail = other;\n+\t\t\tother = get_next_fn(other);\n+\t\t\tif (!other) {\n+\t\t\t\tset_next_fn(tail, list);\n+\t\t\t\treturn result;\n+\t\t\t}\n+\t\t} while (compare_fn(list, other) > 0);\n+\t\tset_next_fn(tail, list);\n+\t}\n }\n\n+/*\n+ * Perform an iterative mergesort using an array of sublists.\n+ *\n+ * n is the number of items.\n+ * ranks[i] is undefined if n & 2^i == 0, and assumed empty.\n+ * ranks[i] contains a sublist of length 2^i otherwise.\n+ *\n+ * The number of bits in a void pointer limits the number of objects\n+ * that can be created, and thus the number of array elements necessary\n+ * to be able to sort any valid list.\n+ *\n+ * Adding an item to this array is like incrementing a binary number;\n+ * positional values for set bits correspond to sublist lengths.\n+ */\n void *llist_mergesort(void *list,\n \t\t void *(*get_next_fn)(const void *),\n \t\t void (*set_next_fn)(void *, void *),\n \t\t int (*compare_fn)(const void *, const void *))\n {\n-\tunsigned long l;\n-\n-\tif (!list)\n-\t\treturn NULL;\n-\tfor (l = 1; ; l *= 2) {\n-\t\tvoid *curr;\n-\t\tstruct mergesort_sublist p, q;\n+\tvoid *ranks[bitsizeof(void *)];\n+\tsize_t n = 0;\n+\tint i;\n\n-\t\tp.ptr = list;\n-\t\tq.ptr = get_nth_next(p.ptr, l, get_next_fn);\n-\t\tif (!q.ptr)\n-\t\t\tbreak;\n-\t\tp.len = q.len = l;\n+\twhile (list) {\n+\t\tvoid *next = get_next_fn(list);\n+\t\tif (next)\n+\t\t\tset_next_fn(list, NULL);\n+\t\tfor (i = 0; n & (1 << i); i++)\n+\t\t\tlist = llist_merge(ranks[i], list, get_next_fn,\n+\t\t\t\t\t set_next_fn, compare_fn);\n+\t\tn++;\n+\t\tranks[i] = list;\n+\t\tlist = next;\n+\t}\n\n-\t\tif (compare_fn(p.ptr, q.ptr) > 0)\n-\t\t\tlist = curr = pop_item(&q, get_next_fn);\n+\tfor (i = 0; n; i++, n >>= 1) {\n+\t\tif (!(n & 1))\n+\t\t\tcontinue;\n+\t\tif (list)\n+\t\t\tlist = llist_merge(ranks[i], list, get_next_fn,\n+\t\t\t\t\t set_next_fn, compare_fn);\n \t\telse\n-\t\t\tlist = curr = pop_item(&p, get_next_fn);\n-\n-\t\twhile (p.ptr) {\n-\t\t\twhile (p.len || q.len) {\n-\t\t\t\tvoid *prev = curr;\n-\n-\t\t\t\tif (!p.len)\n-\t\t\t\t\tcurr = pop_item(&q, get_next_fn);\n-\t\t\t\telse if (!q.len)\n-\t\t\t\t\tcurr = pop_item(&p, get_next_fn);\n-\t\t\t\telse if (compare_fn(p.ptr, q.ptr) > 0)\n-\t\t\t\t\tcurr = pop_item(&q, get_next_fn);\n-\t\t\t\telse\n-\t\t\t\t\tcurr = pop_item(&p, get_next_fn);\n-\t\t\t\tset_next_fn(prev, curr);\n-\t\t\t}\n-\t\t\tp.ptr = q.ptr;\n-\t\t\tp.len = l;\n-\t\t\tq.ptr = get_nth_next(p.ptr, l, get_next_fn);\n-\t\t\tq.len = q.ptr ? l : 0;\n-\n-\t\t}\n-\t\tset_next_fn(curr, NULL);\n+\t\t\tlist = ranks[i];\n \t}\n \treturn list;\n }\n--\n2.33.0\n"},{"id":"437723","messageId":"xmqq7dew7aqd.fsf@gitster.g","threadId":"56619","inReplyTo":"522fba5e-1048-3377-45c1-7107b55dc6e1@web.de","subject":"Re: [PATCH 3/9] test-mergesort: add test subcommand","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2021-10-01T20:26:18Z","receivedAt":"2021-10-01T20:26:26Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"René Scharfe writes:\n\n> +static void dist_rand(int *arr, int n, int m)\n> +{\n> +\tint i;\n> +\tfor (i = 0; i < n; i++)\n> +\t\tarr[i] = rand() % m;\n> +}\n> ...\n> +static void dist_shuffle(int *arr, int n, int m)\n> +{\n> +\tint i, j, k;\n> +\tfor (i = j = 0, k = 1; i < n; i++)\n> +\t\tarr[i] = (rand() % m) ? (j += 2) : (k += 2);\n> +}\n\nI briefly wondered if we want to seed the rand() in some way to make\nthe tests reproducible, but we'd need to ship our own rand() if we\nwanted to go that route, which would probably be too much.\n\n> +static int test(const struct dist *dist, const struct mode *mode, int n, int m)\n> +{\n> +...\n> +\tfor (i = 0, curr = list; i < n && curr; i++, curr = curr->next) {\n> +\t\tif (arr[i] != curr->value)\n> +\t\t\tis_sorted = 0;\n> +\t\tif (curr->next && curr->value == curr->next->value &&\n> +\t\t curr->rank >= curr->next->rank)\n> +\t\t\tis_stable = 0;\n> +\t}\n> +\tif (i < n) {\n> +\t\tverdict = \"too short\";\n> +\t} else if (curr) {\n> +\t\tverdict = \"too long\";\n> +\t} else if (!is_sorted) {\n> +\t\tverdict = \"not sorted\";\n> +\t} else if (!is_stable) {\n> +\t\tverdict = \"unstable\";\n> +\t} else {\n> +\t\tverdict = \"OK\";\n> +\t\tresult = 0;\n> +\t}\n> +\n> +\tprintf(\"%-9s %-16s %8d %8d %8d %8d %8d %s\\n\",\n> +\t dist->name, mode->name, n, m, stats.get_next, stats.set_next,\n> +\t stats.compare, verdict);\n> +\n> +\tclear_numbers(list);\n> +\tfree(arr);\n> +\n> +\treturn result;\n> +}\n\nNice.\n\n> int cmd__mergesort(int argc, const char **argv)\n> {\n> \tif (argc == 2 && !strcmp(argv[1], \"sort\"))\n> \t\treturn sort_stdin();\n> -\tusage(\"test-tool mergesort sort\");\n> +\tif (argc > 1 && !strcmp(argv[1], \"test\"))\n> +\t\treturn run_tests(argc - 2, argv + 2);\n> +\tfprintf(stderr, \"usage: test-tool mergesort sort\\n\");\n> +\tfprintf(stderr, \" or: test-tool mergesort test [...]\\n\");\n> +\treturn 129;\n\nIf you can live with OPT_CMDMODE to implement sort/test subcommands,\nyou'd get to have parse_options() to do the usage for you, I think.\nI am not sure if it is worth it, as t/helper/ is not end-user\nfacing.\n\n"},{"id":"437724","messageId":"xmqqzgrs5w5r.fsf@gitster.g","threadId":"56619","inReplyTo":"f0a8c3c5-4c51-5128-42a3-3dadb8600a6f@web.de","subject":"Re: [PATCH 2/9] test-mergesort: add sort subcommand","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2021-10-01T20:26:24Z","receivedAt":"2021-10-01T20:26:33Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"René Scharfe writes:\n\n> Give the code for sorting a text file its own sub-command. This allows\n> extending the helper, which we'll do in the following patches.\n> ...\n> -int cmd__mergesort(int argc, const char **argv)\n> +static int sort_stdin(void)\n> {\n> \tstruct line *line, *p = NULL, *lines = NULL;\n> \tstruct strbuf sb = STRBUF_INIT;\n> @@ -49,3 +49,10 @@ int cmd__mergesort(int argc, const char **argv)\n> \t}\n> \treturn 0;\n> }\n> +\n> +int cmd__mergesort(int argc, const char **argv)\n> +{\n> +\tif (argc == 2 && !strcmp(argv[1], \"sort\"))\n> +\t\treturn sort_stdin();\n> +\tusage(\"test-tool mergesort sort\");\n> +}\n\nThis smelled funny, as it would certainly have broken any existing\nscript in t/ that were using \"test-tool mergesort René Scharfe writes:\n>\n>> +static void dist_rand(int *arr, int n, int m)\n>> +{\n>> +\tint i;\n>> +\tfor (i = 0; i < n; i++)\n>> +\t\tarr[i] = rand() % m;\n>> +}\n>> ...\n>> +static void dist_shuffle(int *arr, int n, int m)\n>> +{\n>> +\tint i, j, k;\n>> +\tfor (i = j = 0, k = 1; i < n; i++)\n>> +\t\tarr[i] = (rand() % m) ? (j += 2) : (k += 2);\n>> +}\n>\n> I briefly wondered if we want to seed the rand() in some way to make\n> the tests reproducible, but we'd need to ship our own rand() if we\n> wanted to go that route, which would probably be too much.\n\nWouldn't calling srand() with some constant value suffice on most\nplatforms? I'm aware of it being a NOOP and rand() always being randomly\nseeded on (IIRC) OpenBSD, but that should work on e.g. glibc.\n\n>> int cmd__mergesort(int argc, const char **argv)\n>> {\n>> \tif (argc == 2 && !strcmp(argv[1], \"sort\"))\n>> \t\treturn sort_stdin();\n>> -\tusage(\"test-tool mergesort sort\");\n>> +\tif (argc > 1 && !strcmp(argv[1], \"test\"))\n>> +\t\treturn run_tests(argc - 2, argv + 2);\n>> +\tfprintf(stderr, \"usage: test-tool mergesort sort\\n\");\n>> +\tfprintf(stderr, \" or: test-tool mergesort test [...]\\n\");\n>> +\treturn 129;\n>\n> If you can live with OPT_CMDMODE to implement sort/test subcommands,\n> you'd get to have parse_options() to do the usage for you, I think.\n> I am not sure if it is worth it, as t/helper/ is not end-user\n> facing.\n\nYeah I think the one thing that could improve here is this custom\ngetopts handling, in particular the manual formatting of \"usage\" and\n\"or\" is a bit ugly, considering that you'll get it for free with the\nparse_options() \"usage\" array.\n"},{"id":"437753","messageId":"87fstjpzdu.fsf@evledraar.gmail.com","threadId":"56619","inReplyTo":"928cb42c-c45b-c90a-c71b-2f6669e03251@web.de","subject":"Re: [PATCH 1/9] test-mergesort: use strbuf_getline()","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2021-10-02T09:08:19Z","receivedAt":"2021-10-02T09:08:52Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Fri, Oct 01 2021, René Scharfe wrote:\n\n> \twhile (lines) {\n> -\t\tprintf(\"%s\", lines->text);\n> +\t\tputs(lines->text);\n> \t\tlines = lines->next;\n\nAside: I wonder if we should have a coccicheck for that (not as part of\nthis series), but maybe it would generate too much noise.\n"},{"id":"437769","messageId":"0bff46b8-fd45-c4e5-e8b3-60e68ba7c2b9@web.de","threadId":"56619","inReplyTo":"87fstjpzdu.fsf@evledraar.gmail.com","subject":"Re: [PATCH 1/9] test-mergesort: use strbuf_getline()","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2021-10-02T16:56:58Z","receivedAt":"2021-10-02T16:57:05Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 02.10.21 um 11:08 schrieb Ævar Arnfjörð Bjarmason:\n>\n> On Fri, Oct 01 2021, René Scharfe wrote:\n>\n>> \twhile (lines) {\n>> -\t\tprintf(\"%s\", lines->text);\n>> +\t\tputs(lines->text);\n>> \t\tlines = lines->next;\n>\n> Aside: I wonder if we should have a coccicheck for that (not as part of\n> this series), but maybe it would generate too much noise.\n\nTo replace printf(\"%s\\n\", s) with puts(s)? I considered such a semantic\npatch before as well. It would effectively forbid that specific printf\nusage. And why shouldn't it? puts(3) is easier to use and its call is\nshorter.\n\nBut puts(3) is also confusing: It adds a trailing newline, but its\nsibling fputs(3) doesn't. And it would look weird in the middle of a\nrun of printf calls.\n\nClang already does the replacement with -O1 and GCC even with -O0, so\nthere is no further performance improvement or object text size\nreduction to be gained.\n\nAnd so I dropped the idea.\n\nRené\n"},{"id":"437802","messageId":"d03313db-1c1d-0e27-cdf3-06a389dcd3ae@web.de","threadId":"56619","inReplyTo":"87o887q0s9.fsf@evledraar.gmail.com","subject":"Re: [PATCH 3/9] test-mergesort: add test subcommand","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2021-10-03T10:15:24Z","receivedAt":"2021-10-03T10:15:31Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 02.10.21 um 10:35 schrieb Ævar Arnfjörð Bjarmason:\n>\n> On Fri, Oct 01 2021, Junio C Hamano wrote:\n>\n>> René Scharfe writes:\n>>\n>>> int cmd__mergesort(int argc, const char **argv)\n>>> {\n>>> \tif (argc == 2 && !strcmp(argv[1], \"sort\"))\n>>> \t\treturn sort_stdin();\n>>> -\tusage(\"test-tool mergesort sort\");\n>>> +\tif (argc > 1 && !strcmp(argv[1], \"test\"))\n>>> +\t\treturn run_tests(argc - 2, argv + 2);\n>>> +\tfprintf(stderr, \"usage: test-tool mergesort sort\\n\");\n>>> +\tfprintf(stderr, \" or: test-tool mergesort test [...]\\n\");\n>>> +\treturn 129;\n>>\n>> If you can live with OPT_CMDMODE to implement sort/test subcommands,\n>> you'd get to have parse_options() to do the usage for you, I think.\n>> I am not sure if it is worth it, as t/helper/ is not end-user\n>> facing.\n>\n> Yeah I think the one thing that could improve here is this custom\n> getopts handling, in particular the manual formatting of \"usage\" and\n> \"or\" is a bit ugly, considering that you'll get it for free with the\n> parse_options() \"usage\" array.\n\nI don't see how using parseopt would help here. Maintaining the \"usage\"\nand \"or\" strings manually is trivial. The meaty part of the usage\nstring (e.g. \"test [...]\") would not be generated, neither would the\nrepeated part (\"test-tool mergesort\"). OPT_CMDMODE would require\ndouble dashes for no good reason.\n\nPowerShell's param array allows specifying value types, positions and\ngroup parameters into sets. I think it's expressive enough to allow\ndeclaring all three subcommands and their parameters, and then can\nparse command lines and generate help text automatically.\n\nUntil parseopt gains similar capabilities I'd like to avoid that\ndependency.\n\nRené\n"},{"id":"437803","messageId":"850aa059-61d9-0eba-5809-e0c27a19dfb4@web.de","threadId":"56619","inReplyTo":"87o887q0s9.fsf@evledraar.gmail.com","subject":"Re: [PATCH 3/9] test-mergesort: add test subcommand","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2021-10-03T10:15:21Z","receivedAt":"2021-10-03T10:15:36Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 02.10.21 um 10:35 schrieb Ævar Arnfjörð Bjarmason:\n>\n> On Fri, Oct 01 2021, Junio C Hamano wrote:\n>\n>> René Scharfe writes:\n>>\n>>> +static void dist_rand(int *arr, int n, int m)\n>>> +{\n>>> +\tint i;\n>>> +\tfor (i = 0; i < n; i++)\n>>> +\t\tarr[i] = rand() % m;\n>>> +}\n>>> ...\n>>> +static void dist_shuffle(int *arr, int n, int m)\n>>> +{\n>>> +\tint i, j, k;\n>>> +\tfor (i = j = 0, k = 1; i < n; i++)\n>>> +\t\tarr[i] = (rand() % m) ? (j += 2) : (k += 2);\n>>> +}\n>>\n>> I briefly wondered if we want to seed the rand() in some way to make\n>> the tests reproducible, but we'd need to ship our own rand() if we\n>> wanted to go that route, which would probably be too much.\n>\n> Wouldn't calling srand() with some constant value suffice on most\n> platforms? I'm aware of it being a NOOP and rand() always being randomly\n> seeded on (IIRC) OpenBSD, but that should work on e.g. glibc.\n\nRight, so we'd need to ship our own random number generator.\n\nRepeatable tests are not essential (the original paper didn't mention\nseeding), but shouldn't be much trouble to implement and would simplify\ncomparisons across versions, systems and among testers.\n\nThe only downside I can think of is that it may perhaps also simplify\nover-fitting, i.e. I might find micro-tweaks that only work for our\nspecific rand() sequence and then misinterpret them as general\nimprovements..\n\nRené\n"},{"id":"437815","messageId":"xmqqee9210a1.fsf@gitster.g","threadId":"56619","inReplyTo":"850aa059-61d9-0eba-5809-e0c27a19dfb4@web.de","subject":"Re: [PATCH 3/9] test-mergesort: add test subcommand","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2021-10-03T17:33:10Z","receivedAt":"2021-10-03T17:33:16Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"René Scharfe writes:\n\n> Repeatable tests are not essential (the original paper didn't mention\n> seeding), but shouldn't be much trouble to implement and would simplify\n> comparisons across versions, systems and among testers.\n>\n> The only downside I can think of is that it may perhaps also simplify\n> over-fitting, i.e. I might find micro-tweaks that only work for our\n> specific rand() sequence and then misinterpret them as general\n> improvements..\n\nYup, I think you summarized the pros-and-cons nicely.\n"},{"id":"438199","messageId":"a3eeb255-56e3-eb22-ebf7-e9f04c95fa44@web.de","threadId":"56619","inReplyTo":"xmqqee9210a1.fsf@gitster.g","subject":"Re: [PATCH 3/9] test-mergesort: add test subcommand","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2021-10-07T20:00:04Z","receivedAt":"2021-10-07T20:00:18Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 03.10.21 um 19:33 schrieb Junio C Hamano:\n> René Scharfe writes:\n>\n>> Repeatable tests are not essential (the original paper didn't mention\n>> seeding), but shouldn't be much trouble to implement and would simplify\n>> comparisons across versions, systems and among testers.\n>>\n>> The only downside I can think of is that it may perhaps also simplify\n>> over-fitting, i.e. I might find micro-tweaks that only work for our\n>> specific rand() sequence and then misinterpret them as general\n>> improvements..\n>\n> Yup, I think you summarized the pros-and-cons nicely.\n\nSeeing that the series is in next already, here's a bonus patch for\nthat.\n\n--- >8 ---\nSubject: [PATCH 10/9] test-mergesort: use repeatable random numbers\n\nUse MINSTD to generate pseudo-random numbers consistently instead of\nusing rand(3), whose output can vary from system to system, and reset\nits seed before filling in the test values. This gives repeatable\nresults across versions and systems, which simplifies sharing and\ncomparing of results between developers.\n\nSigned-off-by: René Scharfe \n---\n t/helper/test-mergesort.c | 12 ++++++++++--\n 1 file changed, 10 insertions(+), 2 deletions(-)\n\ndiff --git a/t/helper/test-mergesort.c b/t/helper/test-mergesort.c\nindex 43ec74e2d3..8d128ae437 100644\n--- a/t/helper/test-mergesort.c\n+++ b/t/helper/test-mergesort.c\n@@ -2,6 +2,12 @@\n #include \"cache.h\"\n #include \"mergesort.h\"\n\n+static unsigned int minstd_rand(unsigned int *state)\n+{\n+\t*state = (uint64_t)*state * 48271 % 2147483647;\n+\treturn *state;\n+}\n+\n struct line {\n \tchar *text;\n \tstruct line *next;\n@@ -60,8 +66,9 @@ static void dist_sawtooth(int *arr, int n, int m)\n static void dist_rand(int *arr, int n, int m)\n {\n \tint i;\n+\tunsigned int seed = 1;\n \tfor (i = 0; i < n; i++)\n-\t\tarr[i] = rand() % m;\n+\t\tarr[i] = minstd_rand(&seed) % m;\n }\n\n static void dist_stagger(int *arr, int n, int m)\n@@ -81,8 +88,9 @@ static void dist_plateau(int *arr, int n, int m)\n static void dist_shuffle(int *arr, int n, int m)\n {\n \tint i, j, k;\n+\tunsigned int seed = 1;\n \tfor (i = j = 0, k = 1; i < n; i++)\n-\t\tarr[i] = (rand() % m) ? (j += 2) : (k += 2);\n+\t\tarr[i] = minstd_rand(&seed) % m ? (j += 2) : (k += 2);\n }\n\n #define DIST(name) { #name, dist_##name }\n--\n2.33.0\n\n"},{"id":"438264","messageId":"b73452fa-f5b0-0ab4-25e8-7494637c49f5@web.de","threadId":"56619","inReplyTo":"a3eeb255-56e3-eb22-ebf7-e9f04c95fa44@web.de","subject":"[PATCH 10/9 v2] test-mergesort: use repeatable random numbers","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2021-10-08T04:04:42Z","receivedAt":"2021-10-08T04:04:55Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Use MINSTD to generate pseudo-random numbers consistently instead of\nusing rand(3), whose output can vary from system to system, and reset\nits seed before filling in the test values. This gives repeatable\nresults across versions and systems, which simplifies sharing and\ncomparing of results between developers.\n\nSigned-off-by: René Scharfe \n---\nChange: Use uint32_t to avoid relying on unsigned int being exactly\n4 bytes wide. D'oh!\n\n t/helper/test-mergesort.c | 12 ++++++++++--\n 1 file changed, 10 insertions(+), 2 deletions(-)\n\ndiff --git a/t/helper/test-mergesort.c b/t/helper/test-mergesort.c\nindex 29758cf89b..c6fa816be3 100644\n--- a/t/helper/test-mergesort.c\n+++ b/t/helper/test-mergesort.c\n@@ -2,6 +2,12 @@\n #include \"cache.h\"\n #include \"mergesort.h\"\n\n+static uint32_t minstd_rand(uint32_t *state)\n+{\n+\t*state = (uint64_t)*state * 48271 % 2147483647;\n+\treturn *state;\n+}\n+\n struct line {\n \tchar *text;\n \tstruct line *next;\n@@ -60,8 +66,9 @@ static void dist_sawtooth(int *arr, int n, int m)\n static void dist_rand(int *arr, int n, int m)\n {\n \tint i;\n+\tuint32_t seed = 1;\n \tfor (i = 0; i < n; i++)\n-\t\tarr[i] = rand() % m;\n+\t\tarr[i] = minstd_rand(&seed) % m;\n }\n\n static void dist_stagger(int *arr, int n, int m)\n@@ -81,8 +88,9 @@ static void dist_plateau(int *arr, int n, int m)\n static void dist_shuffle(int *arr, int n, int m)\n {\n \tint i, j, k;\n+\tuint32_t seed = 1;\n \tfor (i = j = 0, k = 1; i < n; i++)\n-\t\tarr[i] = (rand() % m) ? (j += 2) : (k += 2);\n+\t\tarr[i] = minstd_rand(&seed) % m ? (j += 2) : (k += 2);\n }\n\n #define DIST(name) { #name, dist_##name }\n--\n2.33.0\n"},{"id":"438266","messageId":"YV/GUg3yXDfuS3BA@coredump.intra.peff.net","threadId":"56619","inReplyTo":"b73452fa-f5b0-0ab4-25e8-7494637c49f5@web.de","subject":"Re: [PATCH 10/9 v2] test-mergesort: use repeatable random numbers","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2021-10-08T04:17:22Z","receivedAt":"2021-10-08T04:17:26Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Oct 08, 2021 at 06:04:42AM +0200, René Scharfe wrote:\n\n> Use MINSTD to generate pseudo-random numbers consistently instead of\n> using rand(3), whose output can vary from system to system, and reset\n> its seed before filling in the test values. This gives repeatable\n> results across versions and systems, which simplifies sharing and\n> comparing of results between developers.\n\nNice. As a bonus, I noticed that Coverity complains about the use of\nrand() as a security red-flag (even though of course we don't care about\nits quality here). This should get rid of it by hiding the same thing in\na custom implementation. ;)\n\nWe have a similar LCG in t/helper/test-genrandom.c, but I don't think\nthere's any reason this needs to be factored into a shared one. And in\nparticular, I'd be loathe to change the genrandom one, as it may create\nsmall bugs in the test suite (cases where we rely on hashes of the data\nhaving particular attributes).\n\n-Peff\n"},{"id":"438278","messageId":"87tuhsez93.fsf@evledraar.gmail.com","threadId":"56619","inReplyTo":"b73452fa-f5b0-0ab4-25e8-7494637c49f5@web.de","subject":"Re: [PATCH 10/9 v2] test-mergesort: use repeatable random numbers","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2021-10-08T07:23:21Z","receivedAt":"2021-10-08T07:45:26Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Fri, Oct 08 2021, René Scharfe wrote:\n\n> Use MINSTD to generate pseudo-random numbers consistently instead of\n> using rand(3), whose output can vary from system to system, and reset\n> its seed before filling in the test values. This gives repeatable\n> results across versions and systems, which simplifies sharing and\n> comparing of results between developers.\n>\n> Signed-off-by: René Scharfe \n> ---\n> Change: Use uint32_t to avoid relying on unsigned int being exactly\n> 4 bytes wide. D'oh!\n>\n> t/helper/test-mergesort.c | 12 ++++++++++--\n> 1 file changed, 10 insertions(+), 2 deletions(-)\n>\n> diff --git a/t/helper/test-mergesort.c b/t/helper/test-mergesort.c\n> index 29758cf89b..c6fa816be3 100644\n> --- a/t/helper/test-mergesort.c\n> +++ b/t/helper/test-mergesort.c\n> @@ -2,6 +2,12 @@\n> #include \"cache.h\"\n> #include \"mergesort.h\"\n>\n> +static uint32_t minstd_rand(uint32_t *state)\n> +{\n> +\t*state = (uint64_t)*state * 48271 % 2147483647;\n> +\treturn *state;\n> +}\n> +\n> struct line {\n> \tchar *text;\n> \tstruct line *next;\n> @@ -60,8 +66,9 @@ static void dist_sawtooth(int *arr, int n, int m)\n> static void dist_rand(int *arr, int n, int m)\n> {\n> \tint i;\n> +\tuint32_t seed = 1;\n> \tfor (i = 0; i < n; i++)\n> -\t\tarr[i] = rand() % m;\n> +\t\tarr[i] = minstd_rand(&seed) % m;\n> }\n>\n> static void dist_stagger(int *arr, int n, int m)\n> @@ -81,8 +88,9 @@ static void dist_plateau(int *arr, int n, int m)\n> static void dist_shuffle(int *arr, int n, int m)\n> {\n> \tint i, j, k;\n> +\tuint32_t seed = 1;\n> \tfor (i = j = 0, k = 1; i < n; i++)\n> -\t\tarr[i] = (rand() % m) ? (j += 2) : (k += 2);\n> +\t\tarr[i] = minstd_rand(&seed) % m ? (j += 2) : (k += 2);\n> }\n>\n> #define DIST(name) { #name, dist_##name }\n\nJust to your upthread:\n\n \"Right, so we'd need to ship our own random number generator.\"\n\nI don't really think this matters in either case here, and if anything a\nflaky failure in this test would quickly point us in the right\ndirection, as opposed to say having the N test_expect_success being run\nin rand() order or whatever.\n\nIf we'd like results we can compare across platforms we're surely better\nof here running this in a loop with different per-platform srand()\nvalues N times for some high value of N, than we are in picking one\n\"golden\" distribution.\n\nBut just on srand() and rand() use more generally in the test suite: I\nthink it's fine to just assume that we can call srand()/rand() and get\n\"predictable\" results, because what we're really after in most cases is\nto avoid hard-to-diagnose flakyness. If as a result of random\ndistribution we'll get a consistent failure on one OS (or the flakyness\nis just OpenBSD...).\n\nAlso generally: If you'd like \"portable\" rand() for a test just shell\nout to perl. I ran this on various Perl versions (oldest 5.12) on Debian\nLinux, OSX, Solaris & OpenBSD, all returned the same number for both:\n\n ruby -e 'srand(1); puts rand'; perl -E 'srand(1); say $^V; say rand'\n\nWhereas a C program doing the same:\n \n #include \n #include \n \n int main(void)\n {\n srand(1);\n printf(\"rand = %d\\n\", rand());\n return 0;\n }\n\nReturns different numbers an all, and on OpenBSD the number is different\neach time, per their well-known non-standard srand()/rand() behavior.\n"},{"id":"438302","messageId":"c43ce422-0eba-0c7e-af01-a85cd948b0bb@web.de","threadId":"56619","inReplyTo":"87tuhsez93.fsf@evledraar.gmail.com","subject":"Re: [PATCH 10/9 v2] test-mergesort: use repeatable random numbers","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2021-10-08T17:30:20Z","receivedAt":"2021-10-08T17:30:36Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 08.10.21 um 09:23 schrieb Ævar Arnfjörð Bjarmason:\n>\n> Just to your upthread:\n>\n> \"Right, so we'd need to ship our own random number generator.\"\n>\n> I don't really think this matters in either case here, and if anything a\n> flaky failure in this test would quickly point us in the right\n> direction, as opposed to say having the N test_expect_success being run\n> in rand() order or whatever.\n>\n> If we'd like results we can compare across platforms we're surely better\n> of here running this in a loop with different per-platform srand()\n> values N times for some high value of N, than we are in picking one\n> \"golden\" distribution.\n\nA mergesort bug that only causes invalid results for certain RNG seeds\nis not impossible, but unlikely. Portability of results is more useful\nfor comparing the number of operations needed for different types of\ninput, i.e. for performance work, not so much for correctness checking.\n(And those results need to be taken with enough salt to avoid micro-\noptimizing for specific distributions.)\n\nAdding more rand and shuffle distributions, parameterized with different\nseeds, is certainly possible. Not sure what it would prove, though. We\nwould visit a bigger part of the permutation space, but that thing is so\nhuge (N!) that any reasonable sample is still small. That's why I added\nthe unriffle modes, to find maxima.\n\n> But just on srand() and rand() use more generally in the test suite: I\n> think it's fine to just assume that we can call srand()/rand() and get\n> \"predictable\" results, because what we're really after in most cases is\n> to avoid hard-to-diagnose flakyness. If as a result of random\n> distribution we'll get a consistent failure on one OS (or the flakyness\n> is just OpenBSD...).\n\nI can't find any current use of rand() in t/, except perhaps\nt/helper/test-genrandom.c, which open-codes it to get reproducible\nresults. I don't see how calling rand() instead would improve it.\n\n> Also generally: If you'd like \"portable\" rand() for a test just shell\n> out to perl. I ran this on various Perl versions (oldest 5.12) on Debian\n> Linux, OSX, Solaris & OpenBSD, all returned the same number for both:\n>\n> ruby -e 'srand(1); puts rand'; perl -E 'srand(1); say $^V; say rand'\n>\n> Whereas a C program doing the same:\n>\n> #include \n> #include \n>\n> int main(void)\n> {\n> srand(1);\n> printf(\"rand = %d\\n\", rand());\n> return 0;\n> }\n>\n> Returns different numbers an all, and on OpenBSD the number is different\n> each time, per their well-known non-standard srand()/rand() behavior.\n\nFor test shell code that needs only a few random numbers this would\nbe fine.\n\nFor test-genrandom it would also work, but I don't see any benefit in\nconverting it to a scripting language.\n\nShelling out to a script to avoid a multiplication and a modulo in\ntest-mergesort is not interesting, to put it mildly. A mode that sorts\ninput from stdin like the sort subcommand, but returns the operation\ncounts, might be useful if you want to test distributions generated by\na Perl script or other data source of your choice.\n\nRené\n"},{"id":"438309","messageId":"874k9rnxvv.fsf@evledraar.gmail.com","threadId":"56619","inReplyTo":"c43ce422-0eba-0c7e-af01-a85cd948b0bb@web.de","subject":"Re: [PATCH 10/9 v2] test-mergesort: use repeatable random numbers","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2021-10-08T19:00:13Z","receivedAt":"2021-10-08T19:02:18Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Fri, Oct 08 2021, René Scharfe wrote:\n\n> Am 08.10.21 um 09:23 schrieb Ævar Arnfjörð Bjarmason:\n>> Also generally: If you'd like \"portable\" rand() for a test just shell\n>> out to perl. I ran this on various Perl versions (oldest 5.12) on Debian\n>> Linux, OSX, Solaris & OpenBSD, all returned the same number for both:\n>>\n>> ruby -e 'srand(1); puts rand'; perl -E 'srand(1); say $^V; say rand'\n>>\n>> Whereas a C program doing the same:\n>>\n>> #include \n>> #include \n>>\n>> int main(void)\n>> {\n>> srand(1);\n>> printf(\"rand = %d\\n\", rand());\n>> return 0;\n>> }\n>>\n>> Returns different numbers an all, and on OpenBSD the number is different\n>> each time, per their well-known non-standard srand()/rand() behavior.\n>\n> For test shell code that needs only a few random numbers this would\n> be fine.\n>\n> For test-genrandom it would also work, but I don't see any benefit in\n> converting it to a scripting language.\n>\n> Shelling out to a script to avoid a multiplication and a modulo in\n> test-mergesort is not interesting, to put it mildly. A mode that sorts\n> input from stdin like the sort subcommand, but returns the operation\n> counts, might be useful if you want to test distributions generated by\n> a Perl script or other data source of your choice.\n\nYes, it has zero applicablility here.\n\nIt was just an aside/FYI since we were on the topic of the\ncross-platformness of rand().\n\nI.e. one might assume that for the general problem of seeding something\nrandomly cross-platform one had to ship a rand(), but usually at least\nperl is there ahead of you, and since it has its own rand()...\n"},{"id":"446363","messageId":"220117.864k62qmt1.gmgdl@evledraar.gmail.com","threadId":"56619","inReplyTo":"636647b1-f666-f1e2-4127-ee0869b61036@web.de","subject":"Re: [PATCH 9/9] mergesort: use ranks stack","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2022-01-17T17:43:08Z","receivedAt":"2022-01-17T17:44:48Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Fri, Oct 01 2021, René Scharfe wrote:\n\n\n> +/*\n> + * Perform an iterative mergesort using an array of sublists.\n> + *\n> + * n is the number of items.\n> + * ranks[i] is undefined if n & 2^i == 0, and assumed empty.\n> + * ranks[i] contains a sublist of length 2^i otherwise.\n> + *\n> + * The number of bits in a void pointer limits the number of objects\n> + * that can be created, and thus the number of array elements necessary\n> + * to be able to sort any valid list.\n> + *\n> + * Adding an item to this array is like incrementing a binary number;\n> + * positional values for set bits correspond to sublist lengths.\n> + */\n> void *llist_mergesort(void *list,\n> \t\t void *(*get_next_fn)(const void *),\n> \t\t void (*set_next_fn)(void *, void *),\n> \t\t int (*compare_fn)(const void *, const void *))\n> {\n> -\tunsigned long l;\n> -\n> -\tif (!list)\n> -\t\treturn NULL;\n> -\tfor (l = 1; ; l *= 2) {\n> -\t\tvoid *curr;\n> -\t\tstruct mergesort_sublist p, q;\n> +\tvoid *ranks[bitsizeof(void *)];\n> +\tsize_t n = 0;\n> +\tint i;\n>\n> -\t\tp.ptr = list;\n> -\t\tq.ptr = get_nth_next(p.ptr, l, get_next_fn);\n> -\t\tif (!q.ptr)\n> -\t\t\tbreak;\n> -\t\tp.len = q.len = l;\n> +\twhile (list) {\n> +\t\tvoid *next = get_next_fn(list);\n> +\t\tif (next)\n> +\t\t\tset_next_fn(list, NULL);\n> +\t\tfor (i = 0; n & (1 << i); i++)\n> +\t\t\tlist = llist_merge(ranks[i], list, get_next_fn,\n> +\t\t\t\t\t set_next_fn, compare_fn);\n> +\t\tn++;\n> +\t\tranks[i] = list;\n> +\t\tlist = next;\n> +\t}\n\n(Commenting on a commit integrated into v2.34.0)\n\nThe aCC compiler on HP/UX notes:\n\n \"mergesort.c\", line 67: warning #2549-D: variable \"ranks\" is used before its value is set\n list = llist_merge(ranks[i], list, get_next_fn,\n\nIt's commenting on the ranks[i] within the for-loop-within-while-loop\nabove.\n\n>\n> -\t\tif (compare_fn(p.ptr, q.ptr) > 0)\n> -\t\t\tlist = curr = pop_item(&q, get_next_fn);\n> +\tfor (i = 0; n; i++, n >>= 1) {\n> +\t\tif (!(n & 1))\n> +\t\t\tcontinue;\n> +\t\tif (list)\n> +\t\t\tlist = llist_merge(ranks[i], list, get_next_fn,\n> +\t\t\t\t\t set_next_fn, compare_fn);\n> \t\telse\n> -\t\t\tlist = curr = pop_item(&p, get_next_fn);\n> -\n> -\t\twhile (p.ptr) {\n> -\t\t\twhile (p.len || q.len) {\n> -\t\t\t\tvoid *prev = curr;\n> -\n> -\t\t\t\tif (!p.len)\n> -\t\t\t\t\tcurr = pop_item(&q, get_next_fn);\n> -\t\t\t\telse if (!q.len)\n> -\t\t\t\t\tcurr = pop_item(&p, get_next_fn);\n> -\t\t\t\telse if (compare_fn(p.ptr, q.ptr) > 0)\n> -\t\t\t\t\tcurr = pop_item(&q, get_next_fn);\n> -\t\t\t\telse\n> -\t\t\t\t\tcurr = pop_item(&p, get_next_fn);\n> -\t\t\t\tset_next_fn(prev, curr);\n> -\t\t\t}\n> -\t\t\tp.ptr = q.ptr;\n> -\t\t\tp.len = l;\n> -\t\t\tq.ptr = get_nth_next(p.ptr, l, get_next_fn);\n> -\t\t\tq.len = q.ptr ? l : 0;\n> -\n> -\t\t}\n> -\t\tset_next_fn(curr, NULL);\n> +\t\t\tlist = ranks[i];\n> \t}\n> \treturn list;\n> }\n\n"},{"id":"446368","messageId":"c605ecc2-29d6-9025-152e-1bcb831e7188@web.de","threadId":"56619","inReplyTo":"220117.864k62qmt1.gmgdl@evledraar.gmail.com","subject":"Re: [PATCH 9/9] mergesort: use ranks stack","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2022-01-17T18:22:06Z","receivedAt":"2022-01-17T18:22:15Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 17.01.22 um 18:43 schrieb Ævar Arnfjörð Bjarmason:\n>\n> On Fri, Oct 01 2021, René Scharfe wrote:\n>\n>\n>> +/*\n>> + * Perform an iterative mergesort using an array of sublists.\n>> + *\n>> + * n is the number of items.\n>> + * ranks[i] is undefined if n & 2^i == 0, and assumed empty.\n>> + * ranks[i] contains a sublist of length 2^i otherwise.\n>> + *\n>> + * The number of bits in a void pointer limits the number of objects\n>> + * that can be created, and thus the number of array elements necessary\n>> + * to be able to sort any valid list.\n>> + *\n>> + * Adding an item to this array is like incrementing a binary number;\n>> + * positional values for set bits correspond to sublist lengths.\n>> + */\n>> void *llist_mergesort(void *list,\n>> \t\t void *(*get_next_fn)(const void *),\n>> \t\t void (*set_next_fn)(void *, void *),\n>> \t\t int (*compare_fn)(const void *, const void *))\n>> {\n>> -\tunsigned long l;\n>> -\n>> -\tif (!list)\n>> -\t\treturn NULL;\n>> -\tfor (l = 1; ; l *= 2) {\n>> -\t\tvoid *curr;\n>> -\t\tstruct mergesort_sublist p, q;\n>> +\tvoid *ranks[bitsizeof(void *)];\n>> +\tsize_t n = 0;\n>> +\tint i;\n>>\n>> -\t\tp.ptr = list;\n>> -\t\tq.ptr = get_nth_next(p.ptr, l, get_next_fn);\n>> -\t\tif (!q.ptr)\n>> -\t\t\tbreak;\n>> -\t\tp.len = q.len = l;\n>> +\twhile (list) {\n>> +\t\tvoid *next = get_next_fn(list);\n>> +\t\tif (next)\n>> +\t\t\tset_next_fn(list, NULL);\n>> +\t\tfor (i = 0; n & (1 << i); i++)\n>> +\t\t\tlist = llist_merge(ranks[i], list, get_next_fn,\n>> +\t\t\t\t\t set_next_fn, compare_fn);\n>> +\t\tn++;\n>> +\t\tranks[i] = list;\n>> +\t\tlist = next;\n>> +\t}\n>\n> (Commenting on a commit integrated into v2.34.0)\n>\n> The aCC compiler on HP/UX notes:\n>\n> \"mergesort.c\", line 67: warning #2549-D: variable \"ranks\" is used before its value is set\n> list = llist_merge(ranks[i], list, get_next_fn,\n>\n> It's commenting on the ranks[i] within the for-loop-within-while-loop\n> above.\n\nThat would be a bug. I think none of the array elements are read before\nthey are written -- but of course I'm biased. Can that compiler show a\nsequence that would lead to reading uninitialized data? Or anyone else?\n\nInitializing the array would memset(3) 128 bytes on 32-bit systems and\n512 bytes on 64-bit systems. Doing that everywhere just to appease a\nconfused compiler on a dying platform would be merciful, but still sad.\n\n>\n>>\n>> -\t\tif (compare_fn(p.ptr, q.ptr) > 0)\n>> -\t\t\tlist = curr = pop_item(&q, get_next_fn);\n>> +\tfor (i = 0; n; i++, n >>= 1) {\n>> +\t\tif (!(n & 1))\n>> +\t\t\tcontinue;\n>> +\t\tif (list)\n>> +\t\t\tlist = llist_merge(ranks[i], list, get_next_fn,\n>> +\t\t\t\t\t set_next_fn, compare_fn);\n>> \t\telse\n>> -\t\t\tlist = curr = pop_item(&p, get_next_fn);\n>> -\n>> -\t\twhile (p.ptr) {\n>> -\t\t\twhile (p.len || q.len) {\n>> -\t\t\t\tvoid *prev = curr;\n>> -\n>> -\t\t\t\tif (!p.len)\n>> -\t\t\t\t\tcurr = pop_item(&q, get_next_fn);\n>> -\t\t\t\telse if (!q.len)\n>> -\t\t\t\t\tcurr = pop_item(&p, get_next_fn);\n>> -\t\t\t\telse if (compare_fn(p.ptr, q.ptr) > 0)\n>> -\t\t\t\t\tcurr = pop_item(&q, get_next_fn);\n>> -\t\t\t\telse\n>> -\t\t\t\t\tcurr = pop_item(&p, get_next_fn);\n>> -\t\t\t\tset_next_fn(prev, curr);\n>> -\t\t\t}\n>> -\t\t\tp.ptr = q.ptr;\n>> -\t\t\tp.len = l;\n>> -\t\t\tq.ptr = get_nth_next(p.ptr, l, get_next_fn);\n>> -\t\t\tq.len = q.ptr ? l : 0;\n>> -\n>> -\t\t}\n>> -\t\tset_next_fn(curr, NULL);\n>> +\t\t\tlist = ranks[i];\n>> \t}\n>> \treturn list;\n>> }\n>\n"},{"id":"446393","messageId":"cf5053b9-451c-7db6-acff-aae41bfabed3@web.de","threadId":"56619","inReplyTo":"c605ecc2-29d6-9025-152e-1bcb831e7188@web.de","subject":"Re: [PATCH 9/9] mergesort: use ranks stack","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2022-01-18T05:07:15Z","receivedAt":"2022-01-18T05:07:23Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"\n\nAm 17.01.22 um 19:22 schrieb René Scharfe:\n> Am 17.01.22 um 18:43 schrieb Ævar Arnfjörð Bjarmason:\n>>\n>> On Fri, Oct 01 2021, René Scharfe wrote:\n>>\n>>\n>>> +/*\n>>> + * Perform an iterative mergesort using an array of sublists.\n>>> + *\n>>> + * n is the number of items.\n>>> + * ranks[i] is undefined if n & 2^i == 0, and assumed empty.\n>>> + * ranks[i] contains a sublist of length 2^i otherwise.\n>>> + *\n>>> + * The number of bits in a void pointer limits the number of objects\n>>> + * that can be created, and thus the number of array elements necessary\n>>> + * to be able to sort any valid list.\n>>> + *\n>>> + * Adding an item to this array is like incrementing a binary number;\n>>> + * positional values for set bits correspond to sublist lengths.\n>>> + */\n>>> void *llist_mergesort(void *list,\n>>> \t\t void *(*get_next_fn)(const void *),\n>>> \t\t void (*set_next_fn)(void *, void *),\n>>> \t\t int (*compare_fn)(const void *, const void *))\n>>> {\n>>> -\tunsigned long l;\n>>> -\n>>> -\tif (!list)\n>>> -\t\treturn NULL;\n>>> -\tfor (l = 1; ; l *= 2) {\n>>> -\t\tvoid *curr;\n>>> -\t\tstruct mergesort_sublist p, q;\n>>> +\tvoid *ranks[bitsizeof(void *)];\n>>> +\tsize_t n = 0;\n>>> +\tint i;\n>>>\n>>> -\t\tp.ptr = list;\n>>> -\t\tq.ptr = get_nth_next(p.ptr, l, get_next_fn);\n>>> -\t\tif (!q.ptr)\n>>> -\t\t\tbreak;\n>>> -\t\tp.len = q.len = l;\n>>> +\twhile (list) {\n>>> +\t\tvoid *next = get_next_fn(list);\n>>> +\t\tif (next)\n>>> +\t\t\tset_next_fn(list, NULL);\n>>> +\t\tfor (i = 0; n & (1 << i); i++)\n>>> +\t\t\tlist = llist_merge(ranks[i], list, get_next_fn,\n>>> +\t\t\t\t\t set_next_fn, compare_fn);\n>>> +\t\tn++;\n>>> +\t\tranks[i] = list;\n>>> +\t\tlist = next;\n>>> +\t}\n>>\n>> (Commenting on a commit integrated into v2.34.0)\n>>\n>> The aCC compiler on HP/UX notes:\n>>\n>> \"mergesort.c\", line 67: warning #2549-D: variable \"ranks\" is used before its value is set\n>> list = llist_merge(ranks[i], list, get_next_fn,\n>>\n>> It's commenting on the ranks[i] within the for-loop-within-while-loop\n>> above.\n>\n> That would be a bug. I think none of the array elements are read before\n> they are written -- but of course I'm biased. Can that compiler show a\n> sequence that would lead to reading uninitialized data? Or anyone else?\n>\n> Initializing the array would memset(3) 128 bytes on 32-bit systems and\n> 512 bytes on 64-bit systems. Doing that everywhere just to appease a\n> confused compiler on a dying platform would be merciful, but still sad.\n\nDoes the warning disappear if you add \"ranks[0] = NULL;\" before the while\nloop? And if it does, has adding \"if (n & 1) ranks[0] = NULL;\" instead\nthe same effect?\n\n>\n>>\n>>>\n>>> -\t\tif (compare_fn(p.ptr, q.ptr) > 0)\n>>> -\t\t\tlist = curr = pop_item(&q, get_next_fn);\n>>> +\tfor (i = 0; n; i++, n >>= 1) {\n>>> +\t\tif (!(n & 1))\n>>> +\t\t\tcontinue;\n>>> +\t\tif (list)\n>>> +\t\t\tlist = llist_merge(ranks[i], list, get_next_fn,\n>>> +\t\t\t\t\t set_next_fn, compare_fn);\n>>> \t\telse\n>>> -\t\t\tlist = curr = pop_item(&p, get_next_fn);\n>>> -\n>>> -\t\twhile (p.ptr) {\n>>> -\t\t\twhile (p.len || q.len) {\n>>> -\t\t\t\tvoid *prev = curr;\n>>> -\n>>> -\t\t\t\tif (!p.len)\n>>> -\t\t\t\t\tcurr = pop_item(&q, get_next_fn);\n>>> -\t\t\t\telse if (!q.len)\n>>> -\t\t\t\t\tcurr = pop_item(&p, get_next_fn);\n>>> -\t\t\t\telse if (compare_fn(p.ptr, q.ptr) > 0)\n>>> -\t\t\t\t\tcurr = pop_item(&q, get_next_fn);\n>>> -\t\t\t\telse\n>>> -\t\t\t\t\tcurr = pop_item(&p, get_next_fn);\n>>> -\t\t\t\tset_next_fn(prev, curr);\n>>> -\t\t\t}\n>>> -\t\t\tp.ptr = q.ptr;\n>>> -\t\t\tp.len = l;\n>>> -\t\t\tq.ptr = get_nth_next(p.ptr, l, get_next_fn);\n>>> -\t\t\tq.len = q.ptr ? l : 0;\n>>> -\n>>> -\t\t}\n>>> -\t\tset_next_fn(curr, NULL);\n>>> +\t\t\tlist = ranks[i];\n>>> \t}\n>>> \treturn list;\n>>> }\n>>\n"},{"id":"446398","messageId":"220118.86r195pb2b.gmgdl@evledraar.gmail.com","threadId":"56619","inReplyTo":"cf5053b9-451c-7db6-acff-aae41bfabed3@web.de","subject":"Re: [PATCH 9/9] mergesort: use ranks stack","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2022-01-18T10:40:43Z","receivedAt":"2022-01-18T10:56:04Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Tue, Jan 18 2022, René Scharfe wrote:\n\n> Am 17.01.22 um 19:22 schrieb René Scharfe:\n>> Am 17.01.22 um 18:43 schrieb Ævar Arnfjörð Bjarmason:\n>>>\n>>> On Fri, Oct 01 2021, René Scharfe wrote:\n>>>\n>>>\n>>>> +/*\n>>>> + * Perform an iterative mergesort using an array of sublists.\n>>>> + *\n>>>> + * n is the number of items.\n>>>> + * ranks[i] is undefined if n & 2^i == 0, and assumed empty.\n>>>> + * ranks[i] contains a sublist of length 2^i otherwise.\n>>>> + *\n>>>> + * The number of bits in a void pointer limits the number of objects\n>>>> + * that can be created, and thus the number of array elements necessary\n>>>> + * to be able to sort any valid list.\n>>>> + *\n>>>> + * Adding an item to this array is like incrementing a binary number;\n>>>> + * positional values for set bits correspond to sublist lengths.\n>>>> + */\n>>>> void *llist_mergesort(void *list,\n>>>> \t\t void *(*get_next_fn)(const void *),\n>>>> \t\t void (*set_next_fn)(void *, void *),\n>>>> \t\t int (*compare_fn)(const void *, const void *))\n>>>> {\n>>>> -\tunsigned long l;\n>>>> -\n>>>> -\tif (!list)\n>>>> -\t\treturn NULL;\n>>>> -\tfor (l = 1; ; l *= 2) {\n>>>> -\t\tvoid *curr;\n>>>> -\t\tstruct mergesort_sublist p, q;\n>>>> +\tvoid *ranks[bitsizeof(void *)];\n>>>> +\tsize_t n = 0;\n>>>> +\tint i;\n>>>>\n>>>> -\t\tp.ptr = list;\n>>>> -\t\tq.ptr = get_nth_next(p.ptr, l, get_next_fn);\n>>>> -\t\tif (!q.ptr)\n>>>> -\t\t\tbreak;\n>>>> -\t\tp.len = q.len = l;\n>>>> +\twhile (list) {\n>>>> +\t\tvoid *next = get_next_fn(list);\n>>>> +\t\tif (next)\n>>>> +\t\t\tset_next_fn(list, NULL);\n>>>> +\t\tfor (i = 0; n & (1 << i); i++)\n>>>> +\t\t\tlist = llist_merge(ranks[i], list, get_next_fn,\n>>>> +\t\t\t\t\t set_next_fn, compare_fn);\n>>>> +\t\tn++;\n>>>> +\t\tranks[i] = list;\n>>>> +\t\tlist = next;\n>>>> +\t}\n>>>\n>>> (Commenting on a commit integrated into v2.34.0)\n>>>\n>>> The aCC compiler on HP/UX notes:\n>>>\n>>> \"mergesort.c\", line 67: warning #2549-D: variable \"ranks\" is used before its value is set\n>>> list = llist_merge(ranks[i], list, get_next_fn,\n>>>\n>>> It's commenting on the ranks[i] within the for-loop-within-while-loop\n>>> above.\n>>\n>> That would be a bug. I think none of the array elements are read before\n>> they are written -- but of course I'm biased. Can that compiler show a\n>> sequence that would lead to reading uninitialized data? Or anyone else?\n>>\n>> Initializing the array would memset(3) 128 bytes on 32-bit systems and\n>> 512 bytes on 64-bit systems. Doing that everywhere just to appease a\n>> confused compiler on a dying platform would be merciful, but still sad.\n>\n> Does the warning disappear if you add \"ranks[0] = NULL;\" before the while\n> loop? And if it does, has adding \"if (n & 1) ranks[0] = NULL;\" instead\n> the same effect?\n\nBoth of those make the warning go away.\n\nAnyway, if you think the pre-image in master now is fine let's leave it\nas it is. There's no point in just trying to appease aCC here.\n\nI just thought I'd send a quick mail about it because I was looking at\nits warning output, most of those warnings point to obviously harmless\nissues, but I thought this one *might* point to an actual logic error\n(but didn't look carefully enough myself), so I thought I'd send a quick\nnote about it.\n\nIf you think not it's probably best just to leave the code as-is.\n\n>>\n>>>\n>>>>\n>>>> -\t\tif (compare_fn(p.ptr, q.ptr) > 0)\n>>>> -\t\t\tlist = curr = pop_item(&q, get_next_fn);\n>>>> +\tfor (i = 0; n; i++, n >>= 1) {\n>>>> +\t\tif (!(n & 1))\n>>>> +\t\t\tcontinue;\n>>>> +\t\tif (list)\n>>>> +\t\t\tlist = llist_merge(ranks[i], list, get_next_fn,\n>>>> +\t\t\t\t\t set_next_fn, compare_fn);\n>>>> \t\telse\n>>>> -\t\t\tlist = curr = pop_item(&p, get_next_fn);\n>>>> -\n>>>> -\t\twhile (p.ptr) {\n>>>> -\t\t\twhile (p.len || q.len) {\n>>>> -\t\t\t\tvoid *prev = curr;\n>>>> -\n>>>> -\t\t\t\tif (!p.len)\n>>>> -\t\t\t\t\tcurr = pop_item(&q, get_next_fn);\n>>>> -\t\t\t\telse if (!q.len)\n>>>> -\t\t\t\t\tcurr = pop_item(&p, get_next_fn);\n>>>> -\t\t\t\telse if (compare_fn(p.ptr, q.ptr) > 0)\n>>>> -\t\t\t\t\tcurr = pop_item(&q, get_next_fn);\n>>>> -\t\t\t\telse\n>>>> -\t\t\t\t\tcurr = pop_item(&p, get_next_fn);\n>>>> -\t\t\t\tset_next_fn(prev, curr);\n>>>> -\t\t\t}\n>>>> -\t\t\tp.ptr = q.ptr;\n>>>> -\t\t\tp.len = l;\n>>>> -\t\t\tq.ptr = get_nth_next(p.ptr, l, get_next_fn);\n>>>> -\t\t\tq.len = q.ptr ? l : 0;\n>>>> -\n>>>> -\t\t}\n>>>> -\t\tset_next_fn(curr, NULL);\n>>>> +\t\t\tlist = ranks[i];\n>>>> \t}\n>>>> \treturn list;\n>>>> }\n>>>\n\n"},{"id":"446399","messageId":"e8396687-3bd4-4f52-1952-d99836c01d5d@web.de","threadId":"56619","inReplyTo":"220118.86r195pb2b.gmgdl@evledraar.gmail.com","subject":"Re: [PATCH 9/9] mergesort: use ranks stack","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2022-01-18T12:27:05Z","receivedAt":"2022-01-18T12:27:18Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 18.01.22 um 11:40 schrieb Ævar Arnfjörð Bjarmason:\n>\n> On Tue, Jan 18 2022, René Scharfe wrote:\n>\n>> Am 17.01.22 um 19:22 schrieb René Scharfe:\n>>> Am 17.01.22 um 18:43 schrieb Ævar Arnfjörð Bjarmason:\n>>>>\n>>>> On Fri, Oct 01 2021, René Scharfe wrote:\n>>>>\n>>>>\n>>>>> +/*\n>>>>> + * Perform an iterative mergesort using an array of sublists.\n>>>>> + *\n>>>>> + * n is the number of items.\n>>>>> + * ranks[i] is undefined if n & 2^i == 0, and assumed empty.\n>>>>> + * ranks[i] contains a sublist of length 2^i otherwise.\n>>>>> + *\n>>>>> + * The number of bits in a void pointer limits the number of objects\n>>>>> + * that can be created, and thus the number of array elements necessary\n>>>>> + * to be able to sort any valid list.\n>>>>> + *\n>>>>> + * Adding an item to this array is like incrementing a binary number;\n>>>>> + * positional values for set bits correspond to sublist lengths.\n>>>>> + */\n>>>>> void *llist_mergesort(void *list,\n>>>>> \t\t void *(*get_next_fn)(const void *),\n>>>>> \t\t void (*set_next_fn)(void *, void *),\n>>>>> \t\t int (*compare_fn)(const void *, const void *))\n>>>>> {\n>>>>> -\tunsigned long l;\n>>>>> -\n>>>>> -\tif (!list)\n>>>>> -\t\treturn NULL;\n>>>>> -\tfor (l = 1; ; l *= 2) {\n>>>>> -\t\tvoid *curr;\n>>>>> -\t\tstruct mergesort_sublist p, q;\n>>>>> +\tvoid *ranks[bitsizeof(void *)];\n>>>>> +\tsize_t n = 0;\n>>>>> +\tint i;\n>>>>>\n>>>>> -\t\tp.ptr = list;\n>>>>> -\t\tq.ptr = get_nth_next(p.ptr, l, get_next_fn);\n>>>>> -\t\tif (!q.ptr)\n>>>>> -\t\t\tbreak;\n>>>>> -\t\tp.len = q.len = l;\n>>>>> +\twhile (list) {\n>>>>> +\t\tvoid *next = get_next_fn(list);\n>>>>> +\t\tif (next)\n>>>>> +\t\t\tset_next_fn(list, NULL);\n>>>>> +\t\tfor (i = 0; n & (1 << i); i++)\n>>>>> +\t\t\tlist = llist_merge(ranks[i], list, get_next_fn,\n>>>>> +\t\t\t\t\t set_next_fn, compare_fn);\n>>>>> +\t\tn++;\n>>>>> +\t\tranks[i] = list;\n>>>>> +\t\tlist = next;\n>>>>> +\t}\n>>>>\n>>>> (Commenting on a commit integrated into v2.34.0)\n>>>>\n>>>> The aCC compiler on HP/UX notes:\n>>>>\n>>>> \"mergesort.c\", line 67: warning #2549-D: variable \"ranks\" is used before its value is set\n>>>> list = llist_merge(ranks[i], list, get_next_fn,\n>>>>\n>>>> It's commenting on the ranks[i] within the for-loop-within-while-loop\n>>>> above.\n>>>\n>>> That would be a bug. I think none of the array elements are read before\n>>> they are written -- but of course I'm biased. Can that compiler show a\n>>> sequence that would lead to reading uninitialized data? Or anyone else?\n>>>\n>>> Initializing the array would memset(3) 128 bytes on 32-bit systems and\n>>> 512 bytes on 64-bit systems. Doing that everywhere just to appease a\n>>> confused compiler on a dying platform would be merciful, but still sad.\n>>\n>> Does the warning disappear if you add \"ranks[0] = NULL;\" before the while\n>> loop? And if it does, has adding \"if (n & 1) ranks[0] = NULL;\" instead\n>> the same effect?\n>\n> Both of those make the warning go away.\n\nThe second one is optimized out by GCC and Clang because n == 0 before\nthe while loop. The data flow analysis in aCC that leads to the warning\nmust be taking some shortcuts if can be fooled by an inconsequential\nexpression.\n\n> Anyway, if you think the pre-image in master now is fine let's leave it\n> as it is. There's no point in just trying to appease aCC here.\n>\n> I just thought I'd send a quick mail about it because I was looking at\n> its warning output, most of those warnings point to obviously harmless\n> issues, but I thought this one *might* point to an actual logic error\n> (but didn't look carefully enough myself), so I thought I'd send a quick\n> note about it.\n\nSure, it would be a disaster if this loop somehow read uninitialized\ndata, and any hint needs towards that end must be taken seriously. But\nthat warning from aCC seems to be a false positive.\n\nAdding \"if (n & 1) ranks[0] = NULL;\" before the loop and a comment would\nnot change the code generated by \"normal\" optimizing compilers, so we\ncould add this at the cost of slightly hurting readability, if necessary.\n\n> If you think not it's probably best just to leave the code as-is.\n\nThat works for me as well. :)\n\nRené\n"}]}