{"thread":{"id":"58175","subject":"[PATCH 00/10] typed sort of linked lists","startedAt":"2022-07-16T16:50:16Z","lastAt":"2022-07-25T20:49:58Z","messageCount":15,"participants":["René Scharfe","Junio C Hamano","Derrick Stolee"],"isPatch":true,"patchVersion":1,"patchTotal":10},"messages":[{"id":"459196","messageId":"4d7cd286-398e-215c-f2bd-aa7e8207be4f@web.de","threadId":"58175","inReplyTo":null,"subject":"[PATCH 00/10] typed sort of linked lists","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2022-07-16T16:50:02Z","receivedAt":"2022-07-16T16:50:16Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"llist_mergesort() is a function for sorting linked lists of any type\nwithout any dynamic memory allocation.  It just requires the programmer\nto define two accessor functions and doesn't need an embedded struct\nor magic next pointer placement, which makes it relatively easy to use.\n\nThese accessor functions impose function call overhead and a barrier to\ntype checking.  This series aims to avoid that by giving the compiler\nfull type information and allow it to inline them.  Programmers don't\nneed to write the accessor functions anymore and get to use typed\ncomparison functions -- no more casts from void *.  Sorting gets a bit\nquicker.  The cost: Increased binary size.\n\nIt starts by making llist_mergesort() leaner without reducing its\nperformance:\n\n  mergesort: unify ranks loops\n  mergesort: tighten merge loop\n\nThis matters for the next step, which creates the macro version of\nthat function:\n\n  mergesort: add macros for typed sort of linked lists\n\nThe next two patches show the impact of using the macro on performance\nand object text size of the test helper:\n\n  test-mergesort: use DEFINE_LIST_SORT_DEBUG\n  test-mergesort: use DEFINE_LIST_SORT\n\nThen all llist_mergesort() callers get converted:\n\n  blame: use DEFINE_LIST_SORT\n  commit: use DEFINE_LIST_SORT\n  fetch-pack: use DEFINE_LIST_SORT\n  packfile: use DEFINE_LIST_SORT\n\n... and the final patch removes the function which has become unused:\n\n  mergesort: remove llist_mergesort()\n\n Makefile                  |   1 -\n blame.c                   |  30 ++++-------\n commit.c                  |  20 +++----\n fetch-pack.c              |   8 +++\n mergesort.c               |  84 -----------------------------\n mergesort.h               | 108 ++++++++++++++++++++++++++++++++++----\n packfile.c                |  18 ++-----\n remote.c                  |  22 --------\n remote.h                  |   2 -\n t/helper/test-mergesort.c |  34 +++---------\n t/perf/p0071-sort.sh      |   4 +-\n t/t0071-sort.sh           |   2 +-\n 12 files changed, 134 insertions(+), 199 deletions(-)\n delete mode 100644 mergesort.c\n\n--\n2.37.1\n"},{"id":"459197","messageId":"50b229e9-46b7-fdd1-3f68-de8dd4acf811@web.de","threadId":"58175","inReplyTo":"4d7cd286-398e-215c-f2bd-aa7e8207be4f@web.de","subject":"[PATCH 01/10] mergesort: unify ranks loops","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2022-07-16T16:52:31Z","receivedAt":"2022-07-16T16:52:43Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"llist_mergesort() has a loop for adding a new element to the ranks array\nand another one for rolling up said array into a single sorted list at\nthe end.  We can merge them, so that adding the last element rolls up\nthe whole array.  Handle the empty list before the main loop now because\nlist can't be NULL anymore inside the loop.\n\nThe result is shorter code and significantly less object text:\n\nmain:\n__TEXT\t__DATA\t__OBJC\tothers\tdec\thex\n652\t0\t0\t4651\t5303\t14b7\tmergesort.o\n\nWith this patch:\n__TEXT\t__DATA\t__OBJC\tothers\tdec\thex\n412\t0\t0\t3441\t3853\tf0d\tmergesort.o\n\nWhy is the change so big?  The reduction is amplified by llist_merge()\nbeing inlined both before and after.\n\nPerformance stays basically the same:\n\nmain:\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\nBenchmark 1: t/helper/test-tool mergesort test\n  Time (mean ± σ):     109.0 ms ±   0.3 ms    [User: 107.4 ms, System: 1.1 ms]\n  Range (min … max):   108.7 ms … 109.6 ms    27 runs\n\nWith this patch:\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\nBenchmark 1: t/helper/test-tool mergesort test\n  Time (mean ± σ):     109.2 ms ±   0.2 ms    [User: 107.5 ms, System: 1.1 ms]\n  Range (min … max):   108.9 ms … 109.6 ms    27 runs\n\nSigned-off-by: René Scharfe <l.s.r@web.de>\n---\n mergesort.c | 31 +++++++++++++++----------------\n 1 file changed, 15 insertions(+), 16 deletions(-)\n\ndiff --git a/mergesort.c b/mergesort.c\nindex bd9c6ef8ee..92150c4101 100644\n--- a/mergesort.c\n+++ b/mergesort.c\n@@ -57,28 +57,27 @@ void *llist_mergesort(void *list,\n {\n \tvoid *ranks[bitsizeof(void *)];\n \tsize_t n = 0;\n-\tint i;\n\n-\twhile (list) {\n+\tif (!list)\n+\t\treturn NULL;\n+\n+\tfor (;;) {\n+\t\tint i;\n+\t\tsize_t m;\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 & ((size_t)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\tfor (i = 0, m = n;; i++, m >>= 1) {\n+\t\t\tif (m & 1)\n+\t\t\t\tlist = llist_merge(ranks[i], list, get_next_fn,\n+\t\t\t\t\t\t   set_next_fn, compare_fn);\n+\t\t\telse if (next)\n+\t\t\t\tbreak;\n+\t\t\telse if (!m)\n+\t\t\t\treturn list;\n+\t\t}\n \t\tn++;\n \t\tranks[i] = list;\n \t\tlist = next;\n \t}\n-\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 = ranks[i];\n-\t}\n-\treturn list;\n }\n--\n2.37.1\n"},{"id":"459198","messageId":"df2d020d-29e2-6b6b-bde7-576fc1b9c883@web.de","threadId":"58175","inReplyTo":"4d7cd286-398e-215c-f2bd-aa7e8207be4f@web.de","subject":"[PATCH 02/10] mergesort: tighten merge loop","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2022-07-16T16:53:45Z","receivedAt":"2022-07-16T16:53:53Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"llist_merge() has special inner loops for taking elements from either of\nthe two lists to merge.  That helps consistently preferring one over the\nother, for stability.  Merge the loops, swap the lists when the other\none has the next element for the result and keep track on which one to\nprefer on equality.  This results in shorter code and object text:\n\nBefore:\n__TEXT\t__DATA\t__OBJC\tothers\tdec\thex\n412\t0\t0\t3441\t3853\tf0d\tmergesort.o\n\nWith this patch:\n__TEXT\t__DATA\t__OBJC\tothers\tdec\thex\n352\t0\t0\t3516\t3868\tf1c\tmergesort.o\n\nPerformance doesn't get worse:\n\nBefore:\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\nBenchmark 1: t/helper/test-tool mergesort test\n  Time (mean ± σ):     109.2 ms ±   0.2 ms    [User: 107.5 ms, System: 1.1 ms]\n  Range (min … max):   108.9 ms … 109.6 ms    27 runs\n\nWith this patch:\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\nBenchmark 1: t/helper/test-tool mergesort test\n  Time (mean ± σ):     108.4 ms ±   0.2 ms    [User: 106.7 ms, System: 1.2 ms]\n  Range (min … max):   108.0 ms … 108.8 ms    27 runs\n\nSigned-off-by: René Scharfe <l.s.r@web.de>\n---\n mergesort.c | 19 ++++++-------------\n 1 file changed, 6 insertions(+), 13 deletions(-)\n\ndiff --git a/mergesort.c b/mergesort.c\nindex 92150c4101..6bda3a1c0e 100644\n--- a/mergesort.c\n+++ b/mergesort.c\n@@ -8,10 +8,11 @@ static void *llist_merge(void *list, void *other,\n \t\t\t int (*compare_fn)(const void *, const void *))\n {\n \tvoid *result = list, *tail;\n+\tint prefer_list = compare_fn(list, other) <= 0;\n\n-\tif (compare_fn(list, other) > 0) {\n+\tif (!prefer_list) {\n \t\tresult = other;\n-\t\tgoto other;\n+\t\tSWAP(list, other);\n \t}\n \tfor (;;) {\n \t\tdo {\n@@ -21,18 +22,10 @@ static void *llist_merge(void *list, void *other,\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\t} while (compare_fn(list, other) < prefer_list);\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\tprefer_list ^= 1;\n+\t\tSWAP(list, other);\n \t}\n }\n\n--\n2.37.1\n"},{"id":"459199","messageId":"f127d516-3951-830f-72d4-263557339ec9@web.de","threadId":"58175","inReplyTo":"4d7cd286-398e-215c-f2bd-aa7e8207be4f@web.de","subject":"[PATCH 03/10] mergesort: add macros for typed sort of linked lists","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2022-07-16T16:54:51Z","receivedAt":"2022-07-16T16:54:59Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Add the macros DECLARE_LIST_SORT and DEFINE_LIST_SORT for building\ntype-specific functions for sorting linked lists.  The generated\nfunction expects a typed comparison function.\n\nThe programmer provides full type information (no void pointers).  This\nallows the compiler to check whether the comparison function matches the\nlist type.  It can also inline the \"next\" pointer accessor functions and\neven the comparison function to get rid of the calling overhead.\n\nAlso provide a DECLARE_LIST_SORT_DEBUG macro that allows executing\ncustom code whenever the accessor functions are used.  It's intended to\nbe used by test-mergesort, which counts these operations.\n\nSigned-off-by: René Scharfe <l.s.r@web.de>\n---\n mergesort.h | 101 ++++++++++++++++++++++++++++++++++++++++++++++++++++\n 1 file changed, 101 insertions(+)\n\ndiff --git a/mergesort.h b/mergesort.h\nindex 644cff1f96..7b44355283 100644\n--- a/mergesort.h\n+++ b/mergesort.h\n@@ -14,4 +14,105 @@ void *llist_mergesort(void *list,\n \t\t      void (*set_next_fn)(void *, void *),\n \t\t      int (*compare_fn)(const void *, const void *));\n\n+/* Combine two sorted lists.  Take from `list` on equality. */\n+#define DEFINE_LIST_MERGE_INTERNAL(name, type)\t\t\t\t\\\n+static type *name##__merge(type *list, type *other,\t\t\t\\\n+\t\t\t   int (*compare_fn)(const type *, const type *))\\\n+{\t\t\t\t\t\t\t\t\t\\\n+\ttype *result = list, *tail;\t\t\t\t\t\\\n+\tint prefer_list = compare_fn(list, other) <= 0;\t\t\t\\\n+\t\t\t\t\t\t\t\t\t\\\n+\tif (!prefer_list) {\t\t\t\t\t\t\\\n+\t\tresult = other;\t\t\t\t\t\t\\\n+\t\tSWAP(list, other);\t\t\t\t\t\\\n+\t}\t\t\t\t\t\t\t\t\\\n+\tfor (;;) {\t\t\t\t\t\t\t\\\n+\t\tdo {\t\t\t\t\t\t\t\\\n+\t\t\ttail = list;\t\t\t\t\t\\\n+\t\t\tlist = name##__get_next(list);\t\t\t\\\n+\t\t\tif (!list) {\t\t\t\t\t\\\n+\t\t\t\tname##__set_next(tail, other);\t\t\\\n+\t\t\t\treturn result;\t\t\t\t\\\n+\t\t\t}\t\t\t\t\t\t\\\n+\t\t} while (compare_fn(list, other) < prefer_list);\t\\\n+\t\tname##__set_next(tail, other);\t\t\t\t\\\n+\t\tprefer_list ^= 1;\t\t\t\t\t\\\n+\t\tSWAP(list, other);\t\t\t\t\t\\\n+\t}\t\t\t\t\t\t\t\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+#define DEFINE_LIST_SORT_INTERNAL(scope, name, type)\t\t\t\\\n+scope void name(type **listp,\t\t\t\t\t\t\\\n+\t\tint (*compare_fn)(const type *, const type *))\t\t\\\n+{\t\t\t\t\t\t\t\t\t\\\n+\ttype *list = *listp;\t\t\t\t\t\t\\\n+\ttype *ranks[bitsizeof(type *)];\t\t\t\t\t\\\n+\tsize_t n = 0;\t\t\t\t\t\t\t\\\n+\t\t\t\t\t\t\t\t\t\\\n+\tif (!list)\t\t\t\t\t\t\t\\\n+\t\treturn;\t\t\t\t\t\t\t\\\n+\t\t\t\t\t\t\t\t\t\\\n+\tfor (;;) {\t\t\t\t\t\t\t\\\n+\t\tint i;\t\t\t\t\t\t\t\\\n+\t\tsize_t m;\t\t\t\t\t\t\\\n+\t\ttype *next = name##__get_next(list);\t\t\t\\\n+\t\tif (next)\t\t\t\t\t\t\\\n+\t\t\tname##__set_next(list, NULL);\t\t\t\\\n+\t\tfor (i = 0, m = n;; i++, m >>= 1) {\t\t\t\\\n+\t\t\tif (m & 1) {\t\t\t\t\t\\\n+\t\t\t\tlist = name##__merge(ranks[i], list,\t\\\n+\t\t\t\t\t\t    compare_fn);\t\\\n+\t\t\t} else if (next) {\t\t\t\t\\\n+\t\t\t\tbreak;\t\t\t\t\t\\\n+\t\t\t} else if (!m) {\t\t\t\t\\\n+\t\t\t\t*listp = list;\t\t\t\t\\\n+\t\t\t\treturn;\t\t\t\t\t\\\n+\t\t\t}\t\t\t\t\t\t\\\n+\t\t}\t\t\t\t\t\t\t\\\n+\t\tn++;\t\t\t\t\t\t\t\\\n+\t\tranks[i] = list;\t\t\t\t\t\\\n+\t\tlist = next;\t\t\t\t\t\t\\\n+\t}\t\t\t\t\t\t\t\t\\\n+}\n+\n+#define DECLARE_LIST_SORT(scope, name, type)\t\t\t\\\n+scope void name(type **listp,\t\t\t\t\t\\\n+\t\tint (*compare_fn)(const type *, const type *))\n+\n+#define DEFINE_LIST_SORT_DEBUG(scope, name, type, next_member,\t\\\n+\t\t\t       on_get_next, on_set_next)\t\\\n+\t\t\t\t\t\t\t\t\\\n+static inline type *name##__get_next(const type *elem)\t\t\\\n+{\t\t\t\t\t\t\t\t\\\n+\ton_get_next;\t\t\t\t\t\t\\\n+\treturn elem->next_member;\t\t\t\t\\\n+}\t\t\t\t\t\t\t\t\\\n+\t\t\t\t\t\t\t\t\\\n+static inline void name##__set_next(type *elem, type *next)\t\\\n+{\t\t\t\t\t\t\t\t\\\n+\ton_set_next;\t\t\t\t\t\t\\\n+\telem->next_member = next;\t\t\t\t\\\n+}\t\t\t\t\t\t\t\t\\\n+\t\t\t\t\t\t\t\t\\\n+DEFINE_LIST_MERGE_INTERNAL(name, type)\t\t\t\t\\\n+DEFINE_LIST_SORT_INTERNAL(scope, name, type)\t\t\t\\\n+DECLARE_LIST_SORT(scope, name, type)\n+\n+#define DEFINE_LIST_SORT(scope, name, type, next_member) \\\n+DEFINE_LIST_SORT_DEBUG(scope, name, type, next_member, (void)0, (void)0)\n+\n #endif\n--\n2.37.1\n"},{"id":"459200","messageId":"dda728d4-eedc-c4c6-034e-0a5a03ed9059@web.de","threadId":"58175","inReplyTo":"4d7cd286-398e-215c-f2bd-aa7e8207be4f@web.de","subject":"[PATCH 04/10] test-mergesort: use DEFINE_LIST_SORT_DEBUG","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2022-07-16T16:56:32Z","receivedAt":"2022-07-16T16:56:38Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Define a typed sort function using DEFINE_LIST_SORT_DEBUG for the\nmergesort sanity check instead of using llist_mergesort().  This gets\nrid of the next pointer accessor functions and improves the performance\nat the cost of slightly bigger object text.\n\nBefore:\nBenchmark 1: t/helper/test-tool mergesort test\n  Time (mean ± σ):     108.4 ms ±   0.2 ms    [User: 106.7 ms, System: 1.2 ms]\n  Range (min … max):   108.0 ms … 108.8 ms    27 runs\n\n__TEXT\t__DATA\t__OBJC\tothers\tdec\thex\n6251\t276\t0\t23172\t29699\t7403\tt/helper/test-mergesort.o\n\nWith this patch:\nBenchmark 1: t/helper/test-tool mergesort test\n  Time (mean ± σ):      94.0 ms ±   0.2 ms    [User: 92.4 ms, System: 1.1 ms]\n  Range (min … max):    93.7 ms …  94.5 ms    31 runs\n\n__TEXT\t__DATA\t__OBJC\tothers\tdec\thex\n6407\t276\t0\t24701\t31384\t7a98\tt/helper/test-mergesort.o\n\nSigned-off-by: René Scharfe <l.s.r@web.de>\n---\n t/helper/test-mergesort.c | 19 ++++---------------\n t/t0071-sort.sh           |  2 +-\n 2 files changed, 5 insertions(+), 16 deletions(-)\n\ndiff --git a/t/helper/test-mergesort.c b/t/helper/test-mergesort.c\nindex ebf68f7de8..93d15d59a1 100644\n--- a/t/helper/test-mergesort.c\n+++ b/t/helper/test-mergesort.c\n@@ -273,21 +273,11 @@ struct number {\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+DEFINE_LIST_SORT_DEBUG(static, sort_numbers, struct number, next,\n+\t\t       stats.get_next++, stats.set_next++);\n\n-static int compare_numbers(const void *av, const void *bv)\n+static int compare_numbers(const struct number *an, const struct number *bn)\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@@ -325,8 +315,7 @@ static int test(const struct dist *dist, const struct mode *mode, int n, int m)\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+\tsort_numbers(&list, compare_numbers);\n\n \tQSORT(arr, n, compare_ints);\n \tfor (i = 0, curr = list; i < n && curr; i++, curr = curr->next) {\ndiff --git a/t/t0071-sort.sh b/t/t0071-sort.sh\nindex 6f9a501c72..ba8ad1d1ca 100755\n--- a/t/t0071-sort.sh\n+++ b/t/t0071-sort.sh\n@@ -5,7 +5,7 @@ test_description='verify sort functions'\n TEST_PASSES_SANITIZE_LEAK=true\n . ./test-lib.sh\n\n-test_expect_success 'llist_mergesort()' '\n+test_expect_success 'DEFINE_LIST_SORT_DEBUG' '\n \ttest-tool mergesort test\n '\n\n--\n2.37.1\n"},{"id":"459201","messageId":"54b6a68e-9e2d-c3ec-d6d0-e5dd9a81d391@web.de","threadId":"58175","inReplyTo":"4d7cd286-398e-215c-f2bd-aa7e8207be4f@web.de","subject":"[PATCH 05/10] test-mergesort: use DEFINE_LIST_SORT","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2022-07-16T16:57:18Z","receivedAt":"2022-07-16T16:57:26Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Build a typed sort function for the mergesort performance test tool\nusing DEFINE_LIST_SORT instead of calling llist_mergesort().  This gets\nrid of the next pointer accessor functions and improves the performance\nat the cost of a slightly higher object text size.\n\nBefore:\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\n__TEXT\t__DATA\t__OBJC\tothers\tdec\thex\n6407\t276\t0\t24701\t31384\t7a98\tt/helper/test-mergesort.o\n\nWith this patch:\n0071.12: DEFINE_LIST_SORT unsorted     0.22(0.21+0.01)\n0071.14: DEFINE_LIST_SORT sorted       0.11(0.10+0.01)\n0071.16: DEFINE_LIST_SORT reversed     0.11(0.10+0.01)\n\n__TEXT\t__DATA\t__OBJC\tothers\tdec\thex\n6615\t276\t0\t25832\t32723\t7fd3\tt/helper/test-mergesort.o\n\nSigned-off-by: René Scharfe <l.s.r@web.de>\n---\n t/helper/test-mergesort.c | 15 +++------------\n t/perf/p0071-sort.sh      |  4 ++--\n 2 files changed, 5 insertions(+), 14 deletions(-)\n\ndiff --git a/t/helper/test-mergesort.c b/t/helper/test-mergesort.c\nindex 93d15d59a1..202e54a7ff 100644\n--- a/t/helper/test-mergesort.c\n+++ b/t/helper/test-mergesort.c\n@@ -13,19 +13,10 @@ struct line {\n \tstruct line *next;\n };\n\n-static void *get_next(const void *a)\n-{\n-\treturn ((const struct line *)a)->next;\n-}\n-\n-static void set_next(void *a, void *b)\n-{\n-\t((struct line *)a)->next = b;\n-}\n+DEFINE_LIST_SORT(static, sort_lines, struct line, next);\n\n-static int compare_strings(const void *a, const void *b)\n+static int compare_strings(const struct line *x, const struct line *y)\n {\n-\tconst struct line *x = a, *y = b;\n \treturn strcmp(x->text, y->text);\n }\n\n@@ -47,7 +38,7 @@ static int sort_stdin(void)\n \t\tp = line;\n \t}\n\n-\tlines = llist_mergesort(lines, get_next, set_next, compare_strings);\n+\tsort_lines(&lines, compare_strings);\n\n \twhile (lines) {\n \t\tputs(lines->text);\ndiff --git a/t/perf/p0071-sort.sh b/t/perf/p0071-sort.sh\nindex ed366e2e12..ae4ddac864 100755\n--- a/t/perf/p0071-sort.sh\n+++ b/t/perf/p0071-sort.sh\n@@ -40,11 +40,11 @@ done\n\n for file in unsorted sorted reversed\n do\n-\ttest_perf \"llist_mergesort() $file\" \"\n+\ttest_perf \"DEFINE_LIST_SORT $file\" \"\n \t\ttest-tool mergesort sort <$file >actual\n \t\"\n\n-\ttest_expect_success \"llist_mergesort() $file sorts like sort(1)\" \"\n+\ttest_expect_success \"DEFINE_LIST_SORT $file sorts like sort(1)\" \"\n \t\ttest_cmp_bin sorted actual\n \t\"\n done\n--\n2.37.1\n"},{"id":"459202","messageId":"11f185bd-0117-7f1f-c97c-19cfb0de1384@web.de","threadId":"58175","inReplyTo":"4d7cd286-398e-215c-f2bd-aa7e8207be4f@web.de","subject":"[PATCH 06/10] blame: use DEFINE_LIST_SORT","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2022-07-16T16:58:20Z","receivedAt":"2022-07-16T16:58:27Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Build a typed sort function for blame entries using DEFINE_LIST_SORT\ninstead of calling llist_mergesort().  This gets rid of the next pointer\naccessor functions and their calling overhead at the cost of a slightly\nincreased object text size.\n\nBefore:\n__TEXT\t__DATA\t__OBJC\tothers\tdec\thex\n24621\t56\t0\t147515\t172192\t2a0a0\tblame.o\n\nWith this patch:\n__TEXT\t__DATA\t__OBJC\tothers\tdec\thex\n25229\t56\t0\t151702\t176987\t2b35b\tblame.o\n\nSigned-off-by: René Scharfe <l.s.r@web.de>\n---\n blame.c | 30 +++++++++---------------------\n 1 file changed, 9 insertions(+), 21 deletions(-)\n\ndiff --git a/blame.c b/blame.c\nindex da1052ac94..8bfeaa1c63 100644\n--- a/blame.c\n+++ b/blame.c\n@@ -1098,30 +1098,22 @@ static struct blame_entry *blame_merge(struct blame_entry *list1,\n \t}\n }\n\n-static void *get_next_blame(const void *p)\n-{\n-\treturn ((struct blame_entry *)p)->next;\n-}\n-\n-static void set_next_blame(void *p1, void *p2)\n-{\n-\t((struct blame_entry *)p1)->next = p2;\n-}\n+DEFINE_LIST_SORT(static, sort_blame_entries, struct blame_entry, next);\n\n /*\n  * Final image line numbers are all different, so we don't need a\n  * three-way comparison here.\n  */\n\n-static int compare_blame_final(const void *p1, const void *p2)\n+static int compare_blame_final(const struct blame_entry *e1,\n+\t\t\t       const struct blame_entry *e2)\n {\n-\treturn ((struct blame_entry *)p1)->lno > ((struct blame_entry *)p2)->lno\n-\t\t? 1 : -1;\n+\treturn e1->lno > e2->lno ? 1 : -1;\n }\n\n-static int compare_blame_suspect(const void *p1, const void *p2)\n+static int compare_blame_suspect(const struct blame_entry *s1,\n+\t\t\t\t const struct blame_entry *s2)\n {\n-\tconst struct blame_entry *s1 = p1, *s2 = p2;\n \t/*\n \t * to allow for collating suspects, we sort according to the\n \t * respective pointer value as the primary sorting criterion.\n@@ -1138,8 +1130,7 @@ static int compare_blame_suspect(const void *p1, const void *p2)\n\n void blame_sort_final(struct blame_scoreboard *sb)\n {\n-\tsb->ent = llist_mergesort(sb->ent, get_next_blame, set_next_blame,\n-\t\t\t\t  compare_blame_final);\n+\tsort_blame_entries(&sb->ent, compare_blame_final);\n }\n\n static int compare_commits_by_reverse_commit_date(const void *a,\n@@ -1964,9 +1955,7 @@ static void pass_blame_to_parent(struct blame_scoreboard *sb,\n \t\t    parent, target, 0);\n \t*d.dstq = NULL;\n \tif (ignore_diffs)\n-\t\tnewdest = llist_mergesort(newdest, get_next_blame,\n-\t\t\t\t\t  set_next_blame,\n-\t\t\t\t\t  compare_blame_suspect);\n+\t\tsort_blame_entries(&newdest, compare_blame_suspect);\n \tqueue_blames(sb, parent, newdest);\n\n \treturn;\n@@ -2383,8 +2372,7 @@ static int num_scapegoats(struct rev_info *revs, struct commit *commit, int reve\n  */\n static void distribute_blame(struct blame_scoreboard *sb, struct blame_entry *blamed)\n {\n-\tblamed = llist_mergesort(blamed, get_next_blame, set_next_blame,\n-\t\t\t\t compare_blame_suspect);\n+\tsort_blame_entries(&blamed, compare_blame_suspect);\n \twhile (blamed)\n \t{\n \t\tstruct blame_origin *porigin = blamed->suspect;\n--\n2.37.1\n"},{"id":"459203","messageId":"396b927e-5bbd-1b7d-669e-8e22740b5295@web.de","threadId":"58175","inReplyTo":"4d7cd286-398e-215c-f2bd-aa7e8207be4f@web.de","subject":"[PATCH 07/10] commit: use DEFINE_LIST_SORT","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2022-07-16T16:59:05Z","receivedAt":"2022-07-16T16:59:11Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Use DEFINE_LIST_SORT to build a typed sort function for commit_list\nentries instead of calling llist_mergesort().  This gets rid of the next\npointer accessor functions and their calling overhead at the cost of a\nslightly increased object text size.\n\nBefore:\n__TEXT\t__DATA\t__OBJC\tothers\tdec\thex\n18795\t92\t0\t104654\t123541\t1e295\tcommit.o\n\nWith this patch:\n__TEXT\t__DATA\t__OBJC\tothers\tdec\thex\n18963\t92\t0\t106094\t125149\t1e8dd\tcommit.o\n\nSigned-off-by: René Scharfe <l.s.r@web.de>\n---\n commit.c | 20 ++++++--------------\n 1 file changed, 6 insertions(+), 14 deletions(-)\n\ndiff --git a/commit.c b/commit.c\nindex 1fb1b2ea90..0db461f973 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -642,10 +642,11 @@ struct commit_list * commit_list_insert_by_date(struct commit *item, struct comm\n \treturn commit_list_insert(item, pp);\n }\n\n-static int commit_list_compare_by_date(const void *a, const void *b)\n+static int commit_list_compare_by_date(const struct commit_list *a,\n+\t\t\t\t       const struct commit_list *b)\n {\n-\ttimestamp_t a_date = ((const struct commit_list *)a)->item->date;\n-\ttimestamp_t b_date = ((const struct commit_list *)b)->item->date;\n+\ttimestamp_t a_date = a->item->date;\n+\ttimestamp_t b_date = b->item->date;\n \tif (a_date < b_date)\n \t\treturn 1;\n \tif (a_date > b_date)\n@@ -653,20 +654,11 @@ static int commit_list_compare_by_date(const void *a, const void *b)\n \treturn 0;\n }\n\n-static void *commit_list_get_next(const void *a)\n-{\n-\treturn ((const struct commit_list *)a)->next;\n-}\n-\n-static void commit_list_set_next(void *a, void *next)\n-{\n-\t((struct commit_list *)a)->next = next;\n-}\n+DEFINE_LIST_SORT(static, commit_list_sort, struct commit_list, next);\n\n void commit_list_sort_by_date(struct commit_list **list)\n {\n-\t*list = llist_mergesort(*list, commit_list_get_next, commit_list_set_next,\n-\t\t\t\tcommit_list_compare_by_date);\n+\tcommit_list_sort(list, commit_list_compare_by_date);\n }\n\n struct commit *pop_most_recent_commit(struct commit_list **list,\n--\n2.37.1\n"},{"id":"459204","messageId":"fcae44af-19c9-b289-9c2a-db726dbc586a@web.de","threadId":"58175","inReplyTo":"4d7cd286-398e-215c-f2bd-aa7e8207be4f@web.de","subject":"[PATCH 08/10] fetch-pack: use DEFINE_LIST_SORT","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2022-07-16T16:59:59Z","receivedAt":"2022-07-16T17:00:11Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Build a static typed ref sorting function using DEFINE_LIST_SORT along\nwith a typed comparison function near its only two callers instead of\nhaving an exported version that calls llist_mergesort().  This gets rid\nof the next pointer accessor functions and their calling overhead at the\ncost of a slightly increased object text size.\n\nBefore:\n__TEXT\t__DATA\t__OBJC\tothers\tdec\thex\n23231\t389\t0\t113689\t137309\t2185d\tfetch-pack.o\n29158\t80\t0\t146864\t176102\t2afe6\tremote.o\n\nWith this patch:\n__TEXT\t__DATA\t__OBJC\tothers\tdec\thex\n23591\t389\t0\t117759\t141739\t229ab\tfetch-pack.o\n29070\t80\t0\t145718\t174868\t2ab14\tremote.o\n\nSigned-off-by: René Scharfe <l.s.r@web.de>\n---\n fetch-pack.c |  8 ++++++++\n remote.c     | 22 ----------------------\n remote.h     |  2 --\n 3 files changed, 8 insertions(+), 24 deletions(-)\n\ndiff --git a/fetch-pack.c b/fetch-pack.c\nindex cb6647d657..e4503774b5 100644\n--- a/fetch-pack.c\n+++ b/fetch-pack.c\n@@ -26,6 +26,7 @@\n #include \"commit-reach.h\"\n #include \"commit-graph.h\"\n #include \"sigchain.h\"\n+#include \"mergesort.h\"\n\n static int transfer_unpack_limit = -1;\n static int fetch_unpack_limit = -1;\n@@ -1025,6 +1026,13 @@ static int get_pack(struct fetch_pack_args *args,\n \treturn 0;\n }\n\n+static int ref_compare_name(const struct ref *a, const struct ref *b)\n+{\n+\treturn strcmp(a->name, b->name);\n+}\n+\n+DEFINE_LIST_SORT(static, sort_ref_list, struct ref, next);\n+\n static int cmp_ref_by_name(const void *a_, const void *b_)\n {\n \tconst struct ref *a = *((const struct ref **)a_);\ndiff --git a/remote.c b/remote.c\nindex 1ee2b145d0..e90dca1d56 100644\n--- a/remote.c\n+++ b/remote.c\n@@ -11,7 +11,6 @@\n #include \"dir.h\"\n #include \"tag.h\"\n #include \"string-list.h\"\n-#include \"mergesort.h\"\n #include \"strvec.h\"\n #include \"commit-reach.h\"\n #include \"advice.h\"\n@@ -1082,27 +1081,6 @@ void free_refs(struct ref *ref)\n \t}\n }\n\n-int ref_compare_name(const void *va, const void *vb)\n-{\n-\tconst struct ref *a = va, *b = vb;\n-\treturn strcmp(a->name, b->name);\n-}\n-\n-static void *ref_list_get_next(const void *a)\n-{\n-\treturn ((const struct ref *)a)->next;\n-}\n-\n-static void ref_list_set_next(void *a, void *next)\n-{\n-\t((struct ref *)a)->next = next;\n-}\n-\n-void sort_ref_list(struct ref **l, int (*cmp)(const void *, const void *))\n-{\n-\t*l = llist_mergesort(*l, ref_list_get_next, ref_list_set_next, cmp);\n-}\n-\n int count_refspec_match(const char *pattern,\n \t\t\tstruct ref *refs,\n \t\t\tstruct ref **matched_ref)\ndiff --git a/remote.h b/remote.h\nindex 448675e112..1c4621b414 100644\n--- a/remote.h\n+++ b/remote.h\n@@ -207,9 +207,7 @@ struct ref *find_ref_by_name(const struct ref *list, const char *name);\n struct ref *alloc_ref(const char *name);\n struct ref *copy_ref(const struct ref *ref);\n struct ref *copy_ref_list(const struct ref *ref);\n-void sort_ref_list(struct ref **, int (*cmp)(const void *, const void *));\n int count_refspec_match(const char *, struct ref *refs, struct ref **matched_ref);\n-int ref_compare_name(const void *, const void *);\n\n int check_ref_type(const struct ref *ref, int flags);\n\n--\n2.37.1\n"},{"id":"459205","messageId":"a041739a-cf0c-ac8d-c8ec-5c046575f59a@web.de","threadId":"58175","inReplyTo":"4d7cd286-398e-215c-f2bd-aa7e8207be4f@web.de","subject":"[PATCH 09/10] packfile: use DEFINE_LIST_SORT","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2022-07-16T17:01:18Z","receivedAt":"2022-07-16T17:01:33Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Build a typed sort function for packed_git lists using DEFINE_LIST_SORT\ninstead of calling llist_mergesort().  This gets rid of the next pointer\naccessor functions and their calling overhead at the cost of slightly\nincreased object text size.\n\nBefore:\n__TEXT\t__DATA\t__OBJC\tothers\tdec\thex\n20218\t320\t0\t110936\t131474\t20192\tpackfile.o\n\nWith this patch:\n__TEXT\t__DATA\t__OBJC\tothers\tdec\thex\n20430\t320\t0\t112619\t133369\t208f9\tpackfile.o\n\nSigned-off-by: René Scharfe <l.s.r@web.de>\n---\n packfile.c | 18 +++---------------\n 1 file changed, 3 insertions(+), 15 deletions(-)\n\ndiff --git a/packfile.c b/packfile.c\nindex ed69fe457b..6b0eb9048e 100644\n--- a/packfile.c\n+++ b/packfile.c\n@@ -941,20 +941,10 @@ unsigned long repo_approximate_object_count(struct repository *r)\n \treturn r->objects->approximate_object_count;\n }\n\n-static void *get_next_packed_git(const void *p)\n-{\n-\treturn ((const struct packed_git *)p)->next;\n-}\n-\n-static void set_next_packed_git(void *p, void *next)\n-{\n-\t((struct packed_git *)p)->next = next;\n-}\n+DEFINE_LIST_SORT(static, sort_packs, struct packed_git, next);\n\n-static int sort_pack(const void *a_, const void *b_)\n+static int sort_pack(const struct packed_git *a, const struct packed_git *b)\n {\n-\tconst struct packed_git *a = a_;\n-\tconst struct packed_git *b = b_;\n \tint st;\n\n \t/*\n@@ -981,9 +971,7 @@ static int sort_pack(const void *a_, const void *b_)\n\n static void rearrange_packed_git(struct repository *r)\n {\n-\tr->objects->packed_git = llist_mergesort(\n-\t\tr->objects->packed_git, get_next_packed_git,\n-\t\tset_next_packed_git, sort_pack);\n+\tsort_packs(&r->objects->packed_git, sort_pack);\n }\n\n static void prepare_packed_git_mru(struct repository *r)\n--\n2.37.1\n"},{"id":"459206","messageId":"2fd427e6-2f3c-66d1-bcc5-6bb1e0f59f08@web.de","threadId":"58175","inReplyTo":"4d7cd286-398e-215c-f2bd-aa7e8207be4f@web.de","subject":"[PATCH 10/10] mergesort: remove llist_mergesort()","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2022-07-16T17:02:38Z","receivedAt":"2022-07-16T17:02:48Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Now that all of its callers are gone, remove llist_mergesort().\n\nSigned-off-by: René Scharfe <l.s.r@web.de>\n---\n Makefile    |  1 -\n mergesort.c | 76 -----------------------------------------------------\n mergesort.h | 13 ---------\n 3 files changed, 90 deletions(-)\n delete mode 100644 mergesort.c\n\ndiff --git a/Makefile b/Makefile\nindex 04d0fd1fe6..d41705dc31 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -984,7 +984,6 @@ LIB_OBJS += merge-ort.o\n LIB_OBJS += merge-ort-wrappers.o\n LIB_OBJS += merge-recursive.o\n LIB_OBJS += merge.o\n-LIB_OBJS += mergesort.o\n LIB_OBJS += midx.o\n LIB_OBJS += name-hash.o\n LIB_OBJS += negotiator/default.o\ndiff --git a/mergesort.c b/mergesort.c\ndeleted file mode 100644\nindex 6bda3a1c0e..0000000000\n--- a/mergesort.c\n+++ /dev/null\n@@ -1,76 +0,0 @@\n-#include \"cache.h\"\n-#include \"mergesort.h\"\n-\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-\tvoid *result = list, *tail;\n-\tint prefer_list = compare_fn(list, other) <= 0;\n-\n-\tif (!prefer_list) {\n-\t\tresult = other;\n-\t\tSWAP(list, 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) < prefer_list);\n-\t\tset_next_fn(tail, other);\n-\t\tprefer_list ^= 1;\n-\t\tSWAP(list, other);\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-\tvoid *ranks[bitsizeof(void *)];\n-\tsize_t n = 0;\n-\n-\tif (!list)\n-\t\treturn NULL;\n-\n-\tfor (;;) {\n-\t\tint i;\n-\t\tsize_t m;\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, m = n;; i++, m >>= 1) {\n-\t\t\tif (m & 1)\n-\t\t\t\tlist = llist_merge(ranks[i], list, get_next_fn,\n-\t\t\t\t\t\t   set_next_fn, compare_fn);\n-\t\t\telse if (next)\n-\t\t\t\tbreak;\n-\t\t\telse if (!m)\n-\t\t\t\treturn list;\n-\t\t}\n-\t\tn++;\n-\t\tranks[i] = list;\n-\t\tlist = next;\n-\t}\n-}\ndiff --git a/mergesort.h b/mergesort.h\nindex 7b44355283..7c36f08bd5 100644\n--- a/mergesort.h\n+++ b/mergesort.h\n@@ -1,19 +1,6 @@\n #ifndef MERGESORT_H\n #define MERGESORT_H\n\n-/*\n- * Sort linked list in place.\n- * - get_next_fn() returns the next element given an element of a linked list.\n- * - set_next_fn() takes two elements A and B, and makes B the \"next\" element\n- *   of A on the list.\n- * - compare_fn() takes two elements A and B, and returns negative, 0, positive\n- *   as the same sign as \"subtracting\" B from A.\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 /* Combine two sorted lists.  Take from `list` on equality. */\n #define DEFINE_LIST_MERGE_INTERNAL(name, type)\t\t\t\t\\\n static type *name##__merge(type *list, type *other,\t\t\t\\\n--\n2.37.1\n"},{"id":"459236","messageId":"xmqqk08bv0ax.fsf@gitster.g","threadId":"58175","inReplyTo":"4d7cd286-398e-215c-f2bd-aa7e8207be4f@web.de","subject":"Re: [PATCH 00/10] typed sort of linked lists","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2022-07-17T22:31:18Z","receivedAt":"2022-07-17T22:31:24Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"René Scharfe <l.s.r@web.de> writes:\n\n> It starts by making llist_mergesort() leaner without reducing its\n> performance:\n>\n>   mergesort: unify ranks loops\n>   mergesort: tighten merge loop\n>\n> This matters for the next step, which creates the macro version of\n> that function:\n>\n>   mergesort: add macros for typed sort of linked lists\n>\n> The next two patches show the impact of using the macro on performance\n> and object text size of the test helper:\n>\n>   test-mergesort: use DEFINE_LIST_SORT_DEBUG\n>   test-mergesort: use DEFINE_LIST_SORT\n>\n> Then all llist_mergesort() callers get converted:\n>\n>   blame: use DEFINE_LIST_SORT\n>   commit: use DEFINE_LIST_SORT\n>   fetch-pack: use DEFINE_LIST_SORT\n>   packfile: use DEFINE_LIST_SORT\n>\n> ... and the final patch removes the function which has become unused:\n>\n>   mergesort: remove llist_mergesort()\n\nA nicely presented coherent story that results in an overall code\nreduction.  Thanks for a pleasant read.\n\nWill queue.\n\n\n>  Makefile                  |   1 -\n>  blame.c                   |  30 ++++-------\n>  commit.c                  |  20 +++----\n>  fetch-pack.c              |   8 +++\n>  mergesort.c               |  84 -----------------------------\n>  mergesort.h               | 108 ++++++++++++++++++++++++++++++++++----\n>  packfile.c                |  18 ++-----\n>  remote.c                  |  22 --------\n>  remote.h                  |   2 -\n>  t/helper/test-mergesort.c |  34 +++---------\n>  t/perf/p0071-sort.sh      |   4 +-\n>  t/t0071-sort.sh           |   2 +-\n>  12 files changed, 134 insertions(+), 199 deletions(-)\n>  delete mode 100644 mergesort.c\n>\n> --\n> 2.37.1\n"},{"id":"459902","messageId":"xmqqy1wh3tzy.fsf@gitster.g","threadId":"58175","inReplyTo":"xmqqk08bv0ax.fsf@gitster.g","subject":"Re: [PATCH 00/10] typed sort of linked lists","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2022-07-25T18:52:17Z","receivedAt":"2022-07-25T18:52:24Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano <gitster@pobox.com> writes:\n\n> René Scharfe <l.s.r@web.de> writes:\n>\n>> It starts by making llist_mergesort() leaner without reducing its\n>> performance:\n>>\n>>   mergesort: unify ranks loops\n>>   mergesort: tighten merge loop\n>>\n>> This matters for the next step, which creates the macro version of\n>> that function:\n>>\n>>   mergesort: add macros for typed sort of linked lists\n>>\n>> The next two patches show the impact of using the macro on performance\n>> and object text size of the test helper:\n>>\n>>   test-mergesort: use DEFINE_LIST_SORT_DEBUG\n>>   test-mergesort: use DEFINE_LIST_SORT\n>>\n>> Then all llist_mergesort() callers get converted:\n>>\n>>   blame: use DEFINE_LIST_SORT\n>>   commit: use DEFINE_LIST_SORT\n>>   fetch-pack: use DEFINE_LIST_SORT\n>>   packfile: use DEFINE_LIST_SORT\n>>\n>> ... and the final patch removes the function which has become unused:\n>>\n>>   mergesort: remove llist_mergesort()\n>\n> A nicely presented coherent story that results in an overall code\n> reduction.  Thanks for a pleasant read.\n>\n> Will queue.\n\nNo comments or objections from anybody?  I am planning to merge the\ntopic to 'next' and to 'master' soonish.\n\nThanks.\n"},{"id":"459919","messageId":"3c182e33-ee8e-0a1f-8915-8f97da2499e6@github.com","threadId":"58175","inReplyTo":"xmqqy1wh3tzy.fsf@gitster.g","subject":"Re: [PATCH 00/10] typed sort of linked lists","fromName":"Derrick Stolee","fromEmail":"derrickstolee@github.com","sentAt":"2022-07-25T20:35:59Z","receivedAt":"2022-07-25T20:36:03Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 7/25/2022 2:52 PM, Junio C Hamano wrote:\n> Junio C Hamano <gitster@pobox.com> writes:\n> \n>> René Scharfe <l.s.r@web.de> writes:\n>> A nicely presented coherent story that results in an overall code\n>> reduction.  Thanks for a pleasant read.\n>>\n>> Will queue.\n> \n> No comments or objections from anybody?  I am planning to merge the\n> topic to 'next' and to 'master' soonish.\n\nSorry. I had started reading it and also found it to be a\npleasant read, but did not get around to finishing it and\nsaying so publicly. Consider that done now.\n\nThanks, René!\n-Stolee\n"},{"id":"459922","messageId":"xmqq8rog534j.fsf@gitster.g","threadId":"58175","inReplyTo":"3c182e33-ee8e-0a1f-8915-8f97da2499e6@github.com","subject":"Re: [PATCH 00/10] typed sort of linked lists","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2022-07-25T20:49:48Z","receivedAt":"2022-07-25T20:49:58Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Derrick Stolee <derrickstolee@github.com> writes:\n\n> On 7/25/2022 2:52 PM, Junio C Hamano wrote:\n>> Junio C Hamano <gitster@pobox.com> writes:\n>> \n>>> René Scharfe <l.s.r@web.de> writes:\n>>> A nicely presented coherent story that results in an overall code\n>>> reduction.  Thanks for a pleasant read.\n>>>\n>>> Will queue.\n>> \n>> No comments or objections from anybody?  I am planning to merge the\n>> topic to 'next' and to 'master' soonish.\n>\n> Sorry. I had started reading it and also found it to be a\n> pleasant read, but did not get around to finishing it and\n> saying so publicly. Consider that done now.\n>\n> Thanks, René!\n> -Stolee\n\nThanks.\n"}]}