[PATCH 00/10] typed sort of linked lists

[PATCH 00/10] typed sort of linked lists

[René Scharfe]

llist_mergesort() is a function for sorting linked lists of any type
without any dynamic memory allocation.  It just requires the programmer
to define two accessor functions and doesn't need an embedded struct
or magic next pointer placement, which makes it relatively easy to use.

These accessor functions impose function call overhead and a barrier to
type checking.  This series aims to avoid that by giving the compiler
full type information and allow it to inline them.  Programmers don't
need to write the accessor functions anymore and get to use typed
comparison functions -- no more casts from void *.  Sorting gets a bit
quicker.  The cost: Increased binary size.

It starts by making llist_mergesort() leaner without reducing its
performance:

  mergesort: unify ranks loops
  mergesort: tighten merge loop

This matters for the next step, which creates the macro version of
that function:

  mergesort: add macros for typed sort of linked lists

The next two patches show the impact of using the macro on performance
and object text size of the test helper:

  test-mergesort: use DEFINE_LIST_SORT_DEBUG
  test-mergesort: use DEFINE_LIST_SORT

Then all llist_mergesort() callers get converted:

  blame: use DEFINE_LIST_SORT
  commit: use DEFINE_LIST_SORT
  fetch-pack: use DEFINE_LIST_SORT
  packfile: use DEFINE_LIST_SORT

... and the final patch removes the function which has become unused:

  mergesort: remove llist_mergesort()

 Makefile                  |   1 -
 blame.c                   |  30 ++++-------
 commit.c                  |  20 +++----
 fetch-pack.c              |   8 +++
 mergesort.c               |  84 -----------------------------
 mergesort.h               | 108 ++++++++++++++++++++++++++++++++++----
 packfile.c                |  18 ++-----
 remote.c                  |  22 --------
 remote.h                  |   2 -
 t/helper/test-mergesort.c |  34 +++---------
 t/perf/p0071-sort.sh      |   4 +-
 t/t0071-sort.sh           |   2 +-
 12 files changed, 134 insertions(+), 199 deletions(-)
 delete mode 100644 mergesort.c

--
2.37.1

[PATCH 01/10] mergesort: unify ranks loops

[René Scharfe]

llist_mergesort() has a loop for adding a new element to the ranks array
and another one for rolling up said array into a single sorted list at
the end.  We can merge them, so that adding the last element rolls up
the whole array.  Handle the empty list before the main loop now because
list can't be NULL anymore inside the loop.

The result is shorter code and significantly less object text:

main:
__TEXT	__DATA	__OBJC	others	dec	hex
652	0	0	4651	5303	14b7	mergesort.o

With this patch:
__TEXT	__DATA	__OBJC	others	dec	hex
412	0	0	3441	3853	f0d	mergesort.o

Why is the change so big?  The reduction is amplified by llist_merge()
being inlined both before and after.

Performance stays basically the same:

main:
0071.12: llist_mergesort() unsorted    0.24(0.22+0.01)
0071.14: llist_mergesort() sorted      0.12(0.10+0.01)
0071.16: llist_mergesort() reversed    0.12(0.10+0.01)

Benchmark 1: t/helper/test-tool mergesort test
  Time (mean ± σ):     109.0 ms ±   0.3 ms    [User: 107.4 ms, System: 1.1 ms]
  Range (min … max):   108.7 ms … 109.6 ms    27 runs

With this patch:
0071.12: llist_mergesort() unsorted    0.24(0.22+0.01)
0071.14: llist_mergesort() sorted      0.12(0.10+0.01)
0071.16: llist_mergesort() reversed    0.12(0.10+0.01)

Benchmark 1: t/helper/test-tool mergesort test
  Time (mean ± σ):     109.2 ms ±   0.2 ms    [User: 107.5 ms, System: 1.1 ms]
  Range (min … max):   108.9 ms … 109.6 ms    27 runs

Signed-off-by: René Scharfe <l.s.r@web.de>
---
 mergesort.c | 31 +++++++++++++++----------------
 1 file changed, 15 insertions(+), 16 deletions(-)

diff --git a/mergesort.c b/mergesort.c
index bd9c6ef8ee..92150c4101 100644
--- a/mergesort.c
+++ b/mergesort.c
@@ -57,28 +57,27 @@ void *llist_mergesort(void *list,
 {
 	void *ranks[bitsizeof(void *)];
 	size_t n = 0;
-	int i;

-	while (list) {
+	if (!list)
+		return NULL;
+
+	for (;;) {
+		int i;
+		size_t m;
 		void *next = get_next_fn(list);
 		if (next)
 			set_next_fn(list, NULL);
-		for (i = 0; n & ((size_t)1 << i); i++)
-			list = llist_merge(ranks[i], list, get_next_fn,
-					   set_next_fn, compare_fn);
+		for (i = 0, m = n;; i++, m >>= 1) {
+			if (m & 1)
+				list = llist_merge(ranks[i], list, get_next_fn,
+						   set_next_fn, compare_fn);
+			else if (next)
+				break;
+			else if (!m)
+				return list;
+		}
 		n++;
 		ranks[i] = list;
 		list = next;
 	}
-
-	for (i = 0; n; i++, n >>= 1) {
-		if (!(n & 1))
-			continue;
-		if (list)
-			list = llist_merge(ranks[i], list, get_next_fn,
-					   set_next_fn, compare_fn);
-		else
-			list = ranks[i];
-	}
-	return list;
 }
--
2.37.1

[PATCH 02/10] mergesort: tighten merge loop

[René Scharfe]

llist_merge() has special inner loops for taking elements from either of
the two lists to merge.  That helps consistently preferring one over the
other, for stability.  Merge the loops, swap the lists when the other
one has the next element for the result and keep track on which one to
prefer on equality.  This results in shorter code and object text:

Before:
__TEXT	__DATA	__OBJC	others	dec	hex
412	0	0	3441	3853	f0d	mergesort.o

With this patch:
__TEXT	__DATA	__OBJC	others	dec	hex
352	0	0	3516	3868	f1c	mergesort.o

Performance doesn't get worse:

Before:
0071.12: llist_mergesort() unsorted    0.24(0.22+0.01)
0071.14: llist_mergesort() sorted      0.12(0.10+0.01)
0071.16: llist_mergesort() reversed    0.12(0.10+0.01)

Benchmark 1: t/helper/test-tool mergesort test
  Time (mean ± σ):     109.2 ms ±   0.2 ms    [User: 107.5 ms, System: 1.1 ms]
  Range (min … max):   108.9 ms … 109.6 ms    27 runs

With this patch:
0071.12: llist_mergesort() unsorted    0.24(0.22+0.01)
0071.14: llist_mergesort() sorted      0.12(0.10+0.01)
0071.16: llist_mergesort() reversed    0.12(0.10+0.01)

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

Signed-off-by: René Scharfe <l.s.r@web.de>
---
 mergesort.c | 19 ++++++-------------
 1 file changed, 6 insertions(+), 13 deletions(-)

diff --git a/mergesort.c b/mergesort.c
index 92150c4101..6bda3a1c0e 100644
--- a/mergesort.c
+++ b/mergesort.c
@@ -8,10 +8,11 @@ static void *llist_merge(void *list, void *other,
 			 int (*compare_fn)(const void *, const void *))
 {
 	void *result = list, *tail;
+	int prefer_list = compare_fn(list, other) <= 0;

-	if (compare_fn(list, other) > 0) {
+	if (!prefer_list) {
 		result = other;
-		goto other;
+		SWAP(list, other);
 	}
 	for (;;) {
 		do {
@@ -21,18 +22,10 @@ static void *llist_merge(void *list, void *other,
 				set_next_fn(tail, other);
 				return result;
 			}
-		} while (compare_fn(list, other) <= 0);
+		} while (compare_fn(list, other) < prefer_list);
 		set_next_fn(tail, other);
-	other:
-		do {
-			tail = other;
-			other = get_next_fn(other);
-			if (!other) {
-				set_next_fn(tail, list);
-				return result;
-			}
-		} while (compare_fn(list, other) > 0);
-		set_next_fn(tail, list);
+		prefer_list ^= 1;
+		SWAP(list, other);
 	}
 }

--
2.37.1

[PATCH 03/10] mergesort: add macros for typed sort of linked lists

[René Scharfe]

Add the macros DECLARE_LIST_SORT and DEFINE_LIST_SORT for building
type-specific functions for sorting linked lists.  The generated
function expects a typed comparison function.

The programmer provides full type information (no void pointers).  This
allows the compiler to check whether the comparison function matches the
list type.  It can also inline the "next" pointer accessor functions and
even the comparison function to get rid of the calling overhead.

Also provide a DECLARE_LIST_SORT_DEBUG macro that allows executing
custom code whenever the accessor functions are used.  It's intended to
be used by test-mergesort, which counts these operations.

Signed-off-by: René Scharfe <l.s.r@web.de>
---
 mergesort.h | 101 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 101 insertions(+)

diff --git a/mergesort.h b/mergesort.h
index 644cff1f96..7b44355283 100644
--- a/mergesort.h
+++ b/mergesort.h
@@ -14,4 +14,105 @@ void *llist_mergesort(void *list,
 		      void (*set_next_fn)(void *, void *),
 		      int (*compare_fn)(const void *, const void *));

+/* Combine two sorted lists.  Take from `list` on equality. */
+#define DEFINE_LIST_MERGE_INTERNAL(name, type)				\
+static type *name##__merge(type *list, type *other,			\
+			   int (*compare_fn)(const type *, const type *))\
+{									\
+	type *result = list, *tail;					\
+	int prefer_list = compare_fn(list, other) <= 0;			\
+									\
+	if (!prefer_list) {						\
+		result = other;						\
+		SWAP(list, other);					\
+	}								\
+	for (;;) {							\
+		do {							\
+			tail = list;					\
+			list = name##__get_next(list);			\
+			if (!list) {					\
+				name##__set_next(tail, other);		\
+				return result;				\
+			}						\
+		} while (compare_fn(list, other) < prefer_list);	\
+		name##__set_next(tail, other);				\
+		prefer_list ^= 1;					\
+		SWAP(list, other);					\
+	}								\
+}
+
+/*
+ * Perform an iterative mergesort using an array of sublists.
+ *
+ * n is the number of items.
+ * ranks[i] is undefined if n & 2^i == 0, and assumed empty.
+ * ranks[i] contains a sublist of length 2^i otherwise.
+ *
+ * The number of bits in a void pointer limits the number of objects
+ * that can be created, and thus the number of array elements necessary
+ * to be able to sort any valid list.
+ *
+ * Adding an item to this array is like incrementing a binary number;
+ * positional values for set bits correspond to sublist lengths.
+ */
+#define DEFINE_LIST_SORT_INTERNAL(scope, name, type)			\
+scope void name(type **listp,						\
+		int (*compare_fn)(const type *, const type *))		\
+{									\
+	type *list = *listp;						\
+	type *ranks[bitsizeof(type *)];					\
+	size_t n = 0;							\
+									\
+	if (!list)							\
+		return;							\
+									\
+	for (;;) {							\
+		int i;							\
+		size_t m;						\
+		type *next = name##__get_next(list);			\
+		if (next)						\
+			name##__set_next(list, NULL);			\
+		for (i = 0, m = n;; i++, m >>= 1) {			\
+			if (m & 1) {					\
+				list = name##__merge(ranks[i], list,	\
+						    compare_fn);	\
+			} else if (next) {				\
+				break;					\
+			} else if (!m) {				\
+				*listp = list;				\
+				return;					\
+			}						\
+		}							\
+		n++;							\
+		ranks[i] = list;					\
+		list = next;						\
+	}								\
+}
+
+#define DECLARE_LIST_SORT(scope, name, type)			\
+scope void name(type **listp,					\
+		int (*compare_fn)(const type *, const type *))
+
+#define DEFINE_LIST_SORT_DEBUG(scope, name, type, next_member,	\
+			       on_get_next, on_set_next)	\
+								\
+static inline type *name##__get_next(const type *elem)		\
+{								\
+	on_get_next;						\
+	return elem->next_member;				\
+}								\
+								\
+static inline void name##__set_next(type *elem, type *next)	\
+{								\
+	on_set_next;						\
+	elem->next_member = next;				\
+}								\
+								\
+DEFINE_LIST_MERGE_INTERNAL(name, type)				\
+DEFINE_LIST_SORT_INTERNAL(scope, name, type)			\
+DECLARE_LIST_SORT(scope, name, type)
+
+#define DEFINE_LIST_SORT(scope, name, type, next_member) \
+DEFINE_LIST_SORT_DEBUG(scope, name, type, next_member, (void)0, (void)0)
+
 #endif
--
2.37.1

[PATCH 04/10] test-mergesort: use DEFINE_LIST_SORT_DEBUG

[René Scharfe]

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

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

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

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

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

Signed-off-by: René Scharfe <l.s.r@web.de>
---
 t/helper/test-mergesort.c | 19 ++++---------------
 t/t0071-sort.sh           |  2 +-
 2 files changed, 5 insertions(+), 16 deletions(-)

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

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

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

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

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

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

--
2.37.1

[PATCH 05/10] test-mergesort: use DEFINE_LIST_SORT

[René Scharfe]

Build a typed sort function for the mergesort performance test tool
using DEFINE_LIST_SORT instead of calling llist_mergesort().  This gets
rid of the next pointer accessor functions and improves the performance
at the cost of a slightly higher object text size.

Before:
0071.12: llist_mergesort() unsorted    0.24(0.22+0.01)
0071.14: llist_mergesort() sorted      0.12(0.10+0.01)
0071.16: llist_mergesort() reversed    0.12(0.10+0.01)

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

With this patch:
0071.12: DEFINE_LIST_SORT unsorted     0.22(0.21+0.01)
0071.14: DEFINE_LIST_SORT sorted       0.11(0.10+0.01)
0071.16: DEFINE_LIST_SORT reversed     0.11(0.10+0.01)

__TEXT	__DATA	__OBJC	others	dec	hex
6615	276	0	25832	32723	7fd3	t/helper/test-mergesort.o

Signed-off-by: René Scharfe <l.s.r@web.de>
---
 t/helper/test-mergesort.c | 15 +++------------
 t/perf/p0071-sort.sh      |  4 ++--
 2 files changed, 5 insertions(+), 14 deletions(-)

diff --git a/t/helper/test-mergesort.c b/t/helper/test-mergesort.c
index 93d15d59a1..202e54a7ff 100644
--- a/t/helper/test-mergesort.c
+++ b/t/helper/test-mergesort.c
@@ -13,19 +13,10 @@ struct line {
 	struct line *next;
 };

-static void *get_next(const void *a)
-{
-	return ((const struct line *)a)->next;
-}
-
-static void set_next(void *a, void *b)
-{
-	((struct line *)a)->next = b;
-}
+DEFINE_LIST_SORT(static, sort_lines, struct line, next);

-static int compare_strings(const void *a, const void *b)
+static int compare_strings(const struct line *x, const struct line *y)
 {
-	const struct line *x = a, *y = b;
 	return strcmp(x->text, y->text);
 }

@@ -47,7 +38,7 @@ static int sort_stdin(void)
 		p = line;
 	}

-	lines = llist_mergesort(lines, get_next, set_next, compare_strings);
+	sort_lines(&lines, compare_strings);

 	while (lines) {
 		puts(lines->text);
diff --git a/t/perf/p0071-sort.sh b/t/perf/p0071-sort.sh
index ed366e2e12..ae4ddac864 100755
--- a/t/perf/p0071-sort.sh
+++ b/t/perf/p0071-sort.sh
@@ -40,11 +40,11 @@ done

 for file in unsorted sorted reversed
 do
-	test_perf "llist_mergesort() $file" "
+	test_perf "DEFINE_LIST_SORT $file" "
 		test-tool mergesort sort <$file >actual
 	"

-	test_expect_success "llist_mergesort() $file sorts like sort(1)" "
+	test_expect_success "DEFINE_LIST_SORT $file sorts like sort(1)" "
 		test_cmp_bin sorted actual
 	"
 done
--
2.37.1

[PATCH 06/10] blame: use DEFINE_LIST_SORT

[René Scharfe]

Build a typed sort function for blame entries using DEFINE_LIST_SORT
instead of calling llist_mergesort().  This gets rid of the next pointer
accessor functions and their calling overhead at the cost of a slightly
increased object text size.

Before:
__TEXT	__DATA	__OBJC	others	dec	hex
24621	56	0	147515	172192	2a0a0	blame.o

With this patch:
__TEXT	__DATA	__OBJC	others	dec	hex
25229	56	0	151702	176987	2b35b	blame.o

Signed-off-by: René Scharfe <l.s.r@web.de>
---
 blame.c | 30 +++++++++---------------------
 1 file changed, 9 insertions(+), 21 deletions(-)

diff --git a/blame.c b/blame.c
index da1052ac94..8bfeaa1c63 100644
--- a/blame.c
+++ b/blame.c
@@ -1098,30 +1098,22 @@ static struct blame_entry *blame_merge(struct blame_entry *list1,
 	}
 }

-static void *get_next_blame(const void *p)
-{
-	return ((struct blame_entry *)p)->next;
-}
-
-static void set_next_blame(void *p1, void *p2)
-{
-	((struct blame_entry *)p1)->next = p2;
-}
+DEFINE_LIST_SORT(static, sort_blame_entries, struct blame_entry, next);

 /*
  * Final image line numbers are all different, so we don't need a
  * three-way comparison here.
  */

-static int compare_blame_final(const void *p1, const void *p2)
+static int compare_blame_final(const struct blame_entry *e1,
+			       const struct blame_entry *e2)
 {
-	return ((struct blame_entry *)p1)->lno > ((struct blame_entry *)p2)->lno
-		? 1 : -1;
+	return e1->lno > e2->lno ? 1 : -1;
 }

-static int compare_blame_suspect(const void *p1, const void *p2)
+static int compare_blame_suspect(const struct blame_entry *s1,
+				 const struct blame_entry *s2)
 {
-	const struct blame_entry *s1 = p1, *s2 = p2;
 	/*
 	 * to allow for collating suspects, we sort according to the
 	 * respective pointer value as the primary sorting criterion.
@@ -1138,8 +1130,7 @@ static int compare_blame_suspect(const void *p1, const void *p2)

 void blame_sort_final(struct blame_scoreboard *sb)
 {
-	sb->ent = llist_mergesort(sb->ent, get_next_blame, set_next_blame,
-				  compare_blame_final);
+	sort_blame_entries(&sb->ent, compare_blame_final);
 }

 static int compare_commits_by_reverse_commit_date(const void *a,
@@ -1964,9 +1955,7 @@ static void pass_blame_to_parent(struct blame_scoreboard *sb,
 		    parent, target, 0);
 	*d.dstq = NULL;
 	if (ignore_diffs)
-		newdest = llist_mergesort(newdest, get_next_blame,
-					  set_next_blame,
-					  compare_blame_suspect);
+		sort_blame_entries(&newdest, compare_blame_suspect);
 	queue_blames(sb, parent, newdest);

 	return;
@@ -2383,8 +2372,7 @@ static int num_scapegoats(struct rev_info *revs, struct commit *commit, int reve
  */
 static void distribute_blame(struct blame_scoreboard *sb, struct blame_entry *blamed)
 {
-	blamed = llist_mergesort(blamed, get_next_blame, set_next_blame,
-				 compare_blame_suspect);
+	sort_blame_entries(&blamed, compare_blame_suspect);
 	while (blamed)
 	{
 		struct blame_origin *porigin = blamed->suspect;
--
2.37.1

[PATCH 07/10] commit: use DEFINE_LIST_SORT

[René Scharfe]

Use DEFINE_LIST_SORT to build a typed sort function for commit_list
entries instead of calling llist_mergesort().  This gets rid of the next
pointer accessor functions and their calling overhead at the cost of a
slightly increased object text size.

Before:
__TEXT	__DATA	__OBJC	others	dec	hex
18795	92	0	104654	123541	1e295	commit.o

With this patch:
__TEXT	__DATA	__OBJC	others	dec	hex
18963	92	0	106094	125149	1e8dd	commit.o

Signed-off-by: René Scharfe <l.s.r@web.de>
---
 commit.c | 20 ++++++--------------
 1 file changed, 6 insertions(+), 14 deletions(-)

diff --git a/commit.c b/commit.c
index 1fb1b2ea90..0db461f973 100644
--- a/commit.c
+++ b/commit.c
@@ -642,10 +642,11 @@ struct commit_list * commit_list_insert_by_date(struct commit *item, struct comm
 	return commit_list_insert(item, pp);
 }

-static int commit_list_compare_by_date(const void *a, const void *b)
+static int commit_list_compare_by_date(const struct commit_list *a,
+				       const struct commit_list *b)
 {
-	timestamp_t a_date = ((const struct commit_list *)a)->item->date;
-	timestamp_t b_date = ((const struct commit_list *)b)->item->date;
+	timestamp_t a_date = a->item->date;
+	timestamp_t b_date = b->item->date;
 	if (a_date < b_date)
 		return 1;
 	if (a_date > b_date)
@@ -653,20 +654,11 @@ static int commit_list_compare_by_date(const void *a, const void *b)
 	return 0;
 }

-static void *commit_list_get_next(const void *a)
-{
-	return ((const struct commit_list *)a)->next;
-}
-
-static void commit_list_set_next(void *a, void *next)
-{
-	((struct commit_list *)a)->next = next;
-}
+DEFINE_LIST_SORT(static, commit_list_sort, struct commit_list, next);

 void commit_list_sort_by_date(struct commit_list **list)
 {
-	*list = llist_mergesort(*list, commit_list_get_next, commit_list_set_next,
-				commit_list_compare_by_date);
+	commit_list_sort(list, commit_list_compare_by_date);
 }

 struct commit *pop_most_recent_commit(struct commit_list **list,
--
2.37.1

[PATCH 08/10] fetch-pack: use DEFINE_LIST_SORT

[René Scharfe]

Build a static typed ref sorting function using DEFINE_LIST_SORT along
with a typed comparison function near its only two callers instead of
having an exported version that calls llist_mergesort().  This gets rid
of the next pointer accessor functions and their calling overhead at the
cost of a slightly increased object text size.

Before:
__TEXT	__DATA	__OBJC	others	dec	hex
23231	389	0	113689	137309	2185d	fetch-pack.o
29158	80	0	146864	176102	2afe6	remote.o

With this patch:
__TEXT	__DATA	__OBJC	others	dec	hex
23591	389	0	117759	141739	229ab	fetch-pack.o
29070	80	0	145718	174868	2ab14	remote.o

Signed-off-by: René Scharfe <l.s.r@web.de>
---
 fetch-pack.c |  8 ++++++++
 remote.c     | 22 ----------------------
 remote.h     |  2 --
 3 files changed, 8 insertions(+), 24 deletions(-)

diff --git a/fetch-pack.c b/fetch-pack.c
index cb6647d657..e4503774b5 100644
--- a/fetch-pack.c
+++ b/fetch-pack.c
@@ -26,6 +26,7 @@
 #include "commit-reach.h"
 #include "commit-graph.h"
 #include "sigchain.h"
+#include "mergesort.h"

 static int transfer_unpack_limit = -1;
 static int fetch_unpack_limit = -1;
@@ -1025,6 +1026,13 @@ static int get_pack(struct fetch_pack_args *args,
 	return 0;
 }

+static int ref_compare_name(const struct ref *a, const struct ref *b)
+{
+	return strcmp(a->name, b->name);
+}
+
+DEFINE_LIST_SORT(static, sort_ref_list, struct ref, next);
+
 static int cmp_ref_by_name(const void *a_, const void *b_)
 {
 	const struct ref *a = *((const struct ref **)a_);
diff --git a/remote.c b/remote.c
index 1ee2b145d0..e90dca1d56 100644
--- a/remote.c
+++ b/remote.c
@@ -11,7 +11,6 @@
 #include "dir.h"
 #include "tag.h"
 #include "string-list.h"
-#include "mergesort.h"
 #include "strvec.h"
 #include "commit-reach.h"
 #include "advice.h"
@@ -1082,27 +1081,6 @@ void free_refs(struct ref *ref)
 	}
 }

-int ref_compare_name(const void *va, const void *vb)
-{
-	const struct ref *a = va, *b = vb;
-	return strcmp(a->name, b->name);
-}
-
-static void *ref_list_get_next(const void *a)
-{
-	return ((const struct ref *)a)->next;
-}
-
-static void ref_list_set_next(void *a, void *next)
-{
-	((struct ref *)a)->next = next;
-}
-
-void sort_ref_list(struct ref **l, int (*cmp)(const void *, const void *))
-{
-	*l = llist_mergesort(*l, ref_list_get_next, ref_list_set_next, cmp);
-}
-
 int count_refspec_match(const char *pattern,
 			struct ref *refs,
 			struct ref **matched_ref)
diff --git a/remote.h b/remote.h
index 448675e112..1c4621b414 100644
--- a/remote.h
+++ b/remote.h
@@ -207,9 +207,7 @@ struct ref *find_ref_by_name(const struct ref *list, const char *name);
 struct ref *alloc_ref(const char *name);
 struct ref *copy_ref(const struct ref *ref);
 struct ref *copy_ref_list(const struct ref *ref);
-void sort_ref_list(struct ref **, int (*cmp)(const void *, const void *));
 int count_refspec_match(const char *, struct ref *refs, struct ref **matched_ref);
-int ref_compare_name(const void *, const void *);

 int check_ref_type(const struct ref *ref, int flags);

--
2.37.1

[PATCH 09/10] packfile: use DEFINE_LIST_SORT

[René Scharfe]

Build a typed sort function for packed_git lists using DEFINE_LIST_SORT
instead of calling llist_mergesort().  This gets rid of the next pointer
accessor functions and their calling overhead at the cost of slightly
increased object text size.

Before:
__TEXT	__DATA	__OBJC	others	dec	hex
20218	320	0	110936	131474	20192	packfile.o

With this patch:
__TEXT	__DATA	__OBJC	others	dec	hex
20430	320	0	112619	133369	208f9	packfile.o

Signed-off-by: René Scharfe <l.s.r@web.de>
---
 packfile.c | 18 +++---------------
 1 file changed, 3 insertions(+), 15 deletions(-)

diff --git a/packfile.c b/packfile.c
index ed69fe457b..6b0eb9048e 100644
--- a/packfile.c
+++ b/packfile.c
@@ -941,20 +941,10 @@ unsigned long repo_approximate_object_count(struct repository *r)
 	return r->objects->approximate_object_count;
 }

-static void *get_next_packed_git(const void *p)
-{
-	return ((const struct packed_git *)p)->next;
-}
-
-static void set_next_packed_git(void *p, void *next)
-{
-	((struct packed_git *)p)->next = next;
-}
+DEFINE_LIST_SORT(static, sort_packs, struct packed_git, next);

-static int sort_pack(const void *a_, const void *b_)
+static int sort_pack(const struct packed_git *a, const struct packed_git *b)
 {
-	const struct packed_git *a = a_;
-	const struct packed_git *b = b_;
 	int st;

 	/*
@@ -981,9 +971,7 @@ static int sort_pack(const void *a_, const void *b_)

 static void rearrange_packed_git(struct repository *r)
 {
-	r->objects->packed_git = llist_mergesort(
-		r->objects->packed_git, get_next_packed_git,
-		set_next_packed_git, sort_pack);
+	sort_packs(&r->objects->packed_git, sort_pack);
 }

 static void prepare_packed_git_mru(struct repository *r)
--
2.37.1

[PATCH 10/10] mergesort: remove llist_mergesort()

[René Scharfe]

Now that all of its callers are gone, remove llist_mergesort().

Signed-off-by: René Scharfe <l.s.r@web.de>
---
 Makefile    |  1 -
 mergesort.c | 76 -----------------------------------------------------
 mergesort.h | 13 ---------
 3 files changed, 90 deletions(-)
 delete mode 100644 mergesort.c

diff --git a/Makefile b/Makefile
index 04d0fd1fe6..d41705dc31 100644
--- a/Makefile
+++ b/Makefile
@@ -984,7 +984,6 @@ LIB_OBJS += merge-ort.o
 LIB_OBJS += merge-ort-wrappers.o
 LIB_OBJS += merge-recursive.o
 LIB_OBJS += merge.o
-LIB_OBJS += mergesort.o
 LIB_OBJS += midx.o
 LIB_OBJS += name-hash.o
 LIB_OBJS += negotiator/default.o
diff --git a/mergesort.c b/mergesort.c
deleted file mode 100644
index 6bda3a1c0e..0000000000
--- a/mergesort.c
+++ /dev/null
@@ -1,76 +0,0 @@
-#include "cache.h"
-#include "mergesort.h"
-
-/* Combine two sorted lists.  Take from `list` on equality. */
-static void *llist_merge(void *list, void *other,
-			 void *(*get_next_fn)(const void *),
-			 void (*set_next_fn)(void *, void *),
-			 int (*compare_fn)(const void *, const void *))
-{
-	void *result = list, *tail;
-	int prefer_list = compare_fn(list, other) <= 0;
-
-	if (!prefer_list) {
-		result = other;
-		SWAP(list, other);
-	}
-	for (;;) {
-		do {
-			tail = list;
-			list = get_next_fn(list);
-			if (!list) {
-				set_next_fn(tail, other);
-				return result;
-			}
-		} while (compare_fn(list, other) < prefer_list);
-		set_next_fn(tail, other);
-		prefer_list ^= 1;
-		SWAP(list, other);
-	}
-}
-
-/*
- * Perform an iterative mergesort using an array of sublists.
- *
- * n is the number of items.
- * ranks[i] is undefined if n & 2^i == 0, and assumed empty.
- * ranks[i] contains a sublist of length 2^i otherwise.
- *
- * The number of bits in a void pointer limits the number of objects
- * that can be created, and thus the number of array elements necessary
- * to be able to sort any valid list.
- *
- * Adding an item to this array is like incrementing a binary number;
- * positional values for set bits correspond to sublist lengths.
- */
-void *llist_mergesort(void *list,
-		      void *(*get_next_fn)(const void *),
-		      void (*set_next_fn)(void *, void *),
-		      int (*compare_fn)(const void *, const void *))
-{
-	void *ranks[bitsizeof(void *)];
-	size_t n = 0;
-
-	if (!list)
-		return NULL;
-
-	for (;;) {
-		int i;
-		size_t m;
-		void *next = get_next_fn(list);
-		if (next)
-			set_next_fn(list, NULL);
-		for (i = 0, m = n;; i++, m >>= 1) {
-			if (m & 1)
-				list = llist_merge(ranks[i], list, get_next_fn,
-						   set_next_fn, compare_fn);
-			else if (next)
-				break;
-			else if (!m)
-				return list;
-		}
-		n++;
-		ranks[i] = list;
-		list = next;
-	}
-}
diff --git a/mergesort.h b/mergesort.h
index 7b44355283..7c36f08bd5 100644
--- a/mergesort.h
+++ b/mergesort.h
@@ -1,19 +1,6 @@
 #ifndef MERGESORT_H
 #define MERGESORT_H

-/*
- * Sort linked list in place.
- * - get_next_fn() returns the next element given an element of a linked list.
- * - set_next_fn() takes two elements A and B, and makes B the "next" element
- *   of A on the list.
- * - compare_fn() takes two elements A and B, and returns negative, 0, positive
- *   as the same sign as "subtracting" B from A.
- */
-void *llist_mergesort(void *list,
-		      void *(*get_next_fn)(const void *),
-		      void (*set_next_fn)(void *, void *),
-		      int (*compare_fn)(const void *, const void *));
-
 /* Combine two sorted lists.  Take from `list` on equality. */
 #define DEFINE_LIST_MERGE_INTERNAL(name, type)				\
 static type *name##__merge(type *list, type *other,			\
--
2.37.1

Re: [PATCH 00/10] typed sort of linked lists

[Junio C Hamano]

René Scharfe <l.s.r@web.de> writes:

> It starts by making llist_mergesort() leaner without reducing its
> performance:
>
>   mergesort: unify ranks loops
>   mergesort: tighten merge loop
>
> This matters for the next step, which creates the macro version of
> that function:
>
>   mergesort: add macros for typed sort of linked lists
>
> The next two patches show the impact of using the macro on performance
> and object text size of the test helper:
>
>   test-mergesort: use DEFINE_LIST_SORT_DEBUG
>   test-mergesort: use DEFINE_LIST_SORT
>
> Then all llist_mergesort() callers get converted:
>
>   blame: use DEFINE_LIST_SORT
>   commit: use DEFINE_LIST_SORT
>   fetch-pack: use DEFINE_LIST_SORT
>   packfile: use DEFINE_LIST_SORT
>
> ... and the final patch removes the function which has become unused:
>
>   mergesort: remove llist_mergesort()

A nicely presented coherent story that results in an overall code
reduction.  Thanks for a pleasant read.

Will queue.


>  Makefile                  |   1 -
>  blame.c                   |  30 ++++-------
>  commit.c                  |  20 +++----
>  fetch-pack.c              |   8 +++
>  mergesort.c               |  84 -----------------------------
>  mergesort.h               | 108 ++++++++++++++++++++++++++++++++++----
>  packfile.c                |  18 ++-----
>  remote.c                  |  22 --------
>  remote.h                  |   2 -
>  t/helper/test-mergesort.c |  34 +++---------
>  t/perf/p0071-sort.sh      |   4 +-
>  t/t0071-sort.sh           |   2 +-
>  12 files changed, 134 insertions(+), 199 deletions(-)
>  delete mode 100644 mergesort.c
>
> --
> 2.37.1

Re: [PATCH 00/10] typed sort of linked lists

[Junio C Hamano]

Junio C Hamano <gitster@pobox.com> writes:

> René Scharfe <l.s.r@web.de> writes:
>
>> It starts by making llist_mergesort() leaner without reducing its
>> performance:
>>
>>   mergesort: unify ranks loops
>>   mergesort: tighten merge loop
>>
>> This matters for the next step, which creates the macro version of
>> that function:
>>
>>   mergesort: add macros for typed sort of linked lists
>>
>> The next two patches show the impact of using the macro on performance
>> and object text size of the test helper:
>>
>>   test-mergesort: use DEFINE_LIST_SORT_DEBUG
>>   test-mergesort: use DEFINE_LIST_SORT
>>
>> Then all llist_mergesort() callers get converted:
>>
>>   blame: use DEFINE_LIST_SORT
>>   commit: use DEFINE_LIST_SORT
>>   fetch-pack: use DEFINE_LIST_SORT
>>   packfile: use DEFINE_LIST_SORT
>>
>> ... and the final patch removes the function which has become unused:
>>
>>   mergesort: remove llist_mergesort()
>
> A nicely presented coherent story that results in an overall code
> reduction.  Thanks for a pleasant read.
>
> Will queue.

No comments or objections from anybody?  I am planning to merge the
topic to 'next' and to 'master' soonish.

Thanks.

Re: [PATCH 00/10] typed sort of linked lists

[Derrick Stolee]

On 7/25/2022 2:52 PM, Junio C Hamano wrote:
> Junio C Hamano <gitster@pobox.com> writes:
> 
>> René Scharfe <l.s.r@web.de> writes:
>> A nicely presented coherent story that results in an overall code
>> reduction.  Thanks for a pleasant read.
>>
>> Will queue.
> 
> No comments or objections from anybody?  I am planning to merge the
> topic to 'next' and to 'master' soonish.

Sorry. I had started reading it and also found it to be a
pleasant read, but did not get around to finishing it and
saying so publicly. Consider that done now.

Thanks, René!
-Stolee

Re: [PATCH 00/10] typed sort of linked lists

[Junio C Hamano]

Derrick Stolee <derrickstolee@github.com> writes:

> On 7/25/2022 2:52 PM, Junio C Hamano wrote:
>> Junio C Hamano <gitster@pobox.com> writes:
>> 
>>> René Scharfe <l.s.r@web.de> writes:
>>> A nicely presented coherent story that results in an overall code
>>> reduction.  Thanks for a pleasant read.
>>>
>>> Will queue.
>> 
>> No comments or objections from anybody?  I am planning to merge the
>> topic to 'next' and to 'master' soonish.
>
> Sorry. I had started reading it and also found it to be a
> pleasant read, but did not get around to finishing it and
> saying so publicly. Consider that done now.
>
> Thanks, René!
> -Stolee

Thanks.