* [PATCH 00/10] typed sort of linked lists
@ 2022-07-16 16:50 René Scharfe
2022-07-16 16:52 ` [PATCH 01/10] mergesort: unify ranks loops René Scharfe
` (10 more replies)
0 siblings, 11 replies; 15+ messages in thread
From: René Scharfe @ 2022-07-16 16:50 UTC (permalink / raw)
To: Git List; +Cc: Junio C Hamano
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
^ permalink raw reply [flat|nested] 15+ messages in thread
* [PATCH 01/10] mergesort: unify ranks loops
2022-07-16 16:50 [PATCH 00/10] typed sort of linked lists René Scharfe
@ 2022-07-16 16:52 ` René Scharfe
2022-07-16 16:53 ` [PATCH 02/10] mergesort: tighten merge loop René Scharfe
` (9 subsequent siblings)
10 siblings, 0 replies; 15+ messages in thread
From: René Scharfe @ 2022-07-16 16:52 UTC (permalink / raw)
To: Git List; +Cc: Junio C Hamano
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
^ permalink raw reply related [flat|nested] 15+ messages in thread
* [PATCH 02/10] mergesort: tighten merge loop
2022-07-16 16:50 [PATCH 00/10] typed sort of linked lists René Scharfe
2022-07-16 16:52 ` [PATCH 01/10] mergesort: unify ranks loops René Scharfe
@ 2022-07-16 16:53 ` René Scharfe
2022-07-16 16:54 ` [PATCH 03/10] mergesort: add macros for typed sort of linked lists René Scharfe
` (8 subsequent siblings)
10 siblings, 0 replies; 15+ messages in thread
From: René Scharfe @ 2022-07-16 16:53 UTC (permalink / raw)
To: Git List; +Cc: Junio C Hamano
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
^ permalink raw reply related [flat|nested] 15+ messages in thread
* [PATCH 03/10] mergesort: add macros for typed sort of linked lists
2022-07-16 16:50 [PATCH 00/10] typed sort of linked lists René Scharfe
2022-07-16 16:52 ` [PATCH 01/10] mergesort: unify ranks loops René Scharfe
2022-07-16 16:53 ` [PATCH 02/10] mergesort: tighten merge loop René Scharfe
@ 2022-07-16 16:54 ` René Scharfe
2022-07-16 16:56 ` [PATCH 04/10] test-mergesort: use DEFINE_LIST_SORT_DEBUG René Scharfe
` (7 subsequent siblings)
10 siblings, 0 replies; 15+ messages in thread
From: René Scharfe @ 2022-07-16 16:54 UTC (permalink / raw)
To: Git List; +Cc: Junio C Hamano
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
^ permalink raw reply related [flat|nested] 15+ messages in thread
* [PATCH 04/10] test-mergesort: use DEFINE_LIST_SORT_DEBUG
2022-07-16 16:50 [PATCH 00/10] typed sort of linked lists René Scharfe
` (2 preceding siblings ...)
2022-07-16 16:54 ` [PATCH 03/10] mergesort: add macros for typed sort of linked lists René Scharfe
@ 2022-07-16 16:56 ` René Scharfe
2022-07-16 16:57 ` [PATCH 05/10] test-mergesort: use DEFINE_LIST_SORT René Scharfe
` (6 subsequent siblings)
10 siblings, 0 replies; 15+ messages in thread
From: René Scharfe @ 2022-07-16 16:56 UTC (permalink / raw)
To: Git List; +Cc: Junio C Hamano
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
^ permalink raw reply related [flat|nested] 15+ messages in thread
* [PATCH 05/10] test-mergesort: use DEFINE_LIST_SORT
2022-07-16 16:50 [PATCH 00/10] typed sort of linked lists René Scharfe
` (3 preceding siblings ...)
2022-07-16 16:56 ` [PATCH 04/10] test-mergesort: use DEFINE_LIST_SORT_DEBUG René Scharfe
@ 2022-07-16 16:57 ` René Scharfe
2022-07-16 16:58 ` [PATCH 06/10] blame: " René Scharfe
` (5 subsequent siblings)
10 siblings, 0 replies; 15+ messages in thread
From: René Scharfe @ 2022-07-16 16:57 UTC (permalink / raw)
To: Git List; +Cc: Junio C Hamano
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
^ permalink raw reply related [flat|nested] 15+ messages in thread
* [PATCH 06/10] blame: use DEFINE_LIST_SORT
2022-07-16 16:50 [PATCH 00/10] typed sort of linked lists René Scharfe
` (4 preceding siblings ...)
2022-07-16 16:57 ` [PATCH 05/10] test-mergesort: use DEFINE_LIST_SORT René Scharfe
@ 2022-07-16 16:58 ` René Scharfe
2022-07-16 16:59 ` [PATCH 07/10] commit: " René Scharfe
` (4 subsequent siblings)
10 siblings, 0 replies; 15+ messages in thread
From: René Scharfe @ 2022-07-16 16:58 UTC (permalink / raw)
To: Git List; +Cc: Junio C Hamano
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
^ permalink raw reply related [flat|nested] 15+ messages in thread
* [PATCH 07/10] commit: use DEFINE_LIST_SORT
2022-07-16 16:50 [PATCH 00/10] typed sort of linked lists René Scharfe
` (5 preceding siblings ...)
2022-07-16 16:58 ` [PATCH 06/10] blame: " René Scharfe
@ 2022-07-16 16:59 ` René Scharfe
2022-07-16 16:59 ` [PATCH 08/10] fetch-pack: " René Scharfe
` (3 subsequent siblings)
10 siblings, 0 replies; 15+ messages in thread
From: René Scharfe @ 2022-07-16 16:59 UTC (permalink / raw)
To: Git List; +Cc: Junio C Hamano
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
^ permalink raw reply related [flat|nested] 15+ messages in thread
* [PATCH 08/10] fetch-pack: use DEFINE_LIST_SORT
2022-07-16 16:50 [PATCH 00/10] typed sort of linked lists René Scharfe
` (6 preceding siblings ...)
2022-07-16 16:59 ` [PATCH 07/10] commit: " René Scharfe
@ 2022-07-16 16:59 ` René Scharfe
2022-07-16 17:01 ` [PATCH 09/10] packfile: " René Scharfe
` (2 subsequent siblings)
10 siblings, 0 replies; 15+ messages in thread
From: René Scharfe @ 2022-07-16 16:59 UTC (permalink / raw)
To: Git List; +Cc: Junio C Hamano
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
^ permalink raw reply related [flat|nested] 15+ messages in thread
* [PATCH 09/10] packfile: use DEFINE_LIST_SORT
2022-07-16 16:50 [PATCH 00/10] typed sort of linked lists René Scharfe
` (7 preceding siblings ...)
2022-07-16 16:59 ` [PATCH 08/10] fetch-pack: " René Scharfe
@ 2022-07-16 17:01 ` René Scharfe
2022-07-16 17:02 ` [PATCH 10/10] mergesort: remove llist_mergesort() René Scharfe
2022-07-17 22:31 ` [PATCH 00/10] typed sort of linked lists Junio C Hamano
10 siblings, 0 replies; 15+ messages in thread
From: René Scharfe @ 2022-07-16 17:01 UTC (permalink / raw)
To: Git List; +Cc: Junio C Hamano
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
^ permalink raw reply related [flat|nested] 15+ messages in thread
* [PATCH 10/10] mergesort: remove llist_mergesort()
2022-07-16 16:50 [PATCH 00/10] typed sort of linked lists René Scharfe
` (8 preceding siblings ...)
2022-07-16 17:01 ` [PATCH 09/10] packfile: " René Scharfe
@ 2022-07-16 17:02 ` René Scharfe
2022-07-17 22:31 ` [PATCH 00/10] typed sort of linked lists Junio C Hamano
10 siblings, 0 replies; 15+ messages in thread
From: René Scharfe @ 2022-07-16 17:02 UTC (permalink / raw)
To: Git List; +Cc: Junio C Hamano
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
^ permalink raw reply related [flat|nested] 15+ messages in thread
* Re: [PATCH 00/10] typed sort of linked lists
2022-07-16 16:50 [PATCH 00/10] typed sort of linked lists René Scharfe
` (9 preceding siblings ...)
2022-07-16 17:02 ` [PATCH 10/10] mergesort: remove llist_mergesort() René Scharfe
@ 2022-07-17 22:31 ` Junio C Hamano
2022-07-25 18:52 ` Junio C Hamano
10 siblings, 1 reply; 15+ messages in thread
From: Junio C Hamano @ 2022-07-17 22:31 UTC (permalink / raw)
To: René Scharfe; +Cc: Git List
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
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [PATCH 00/10] typed sort of linked lists
2022-07-17 22:31 ` [PATCH 00/10] typed sort of linked lists Junio C Hamano
@ 2022-07-25 18:52 ` Junio C Hamano
2022-07-25 20:35 ` Derrick Stolee
0 siblings, 1 reply; 15+ messages in thread
From: Junio C Hamano @ 2022-07-25 18:52 UTC (permalink / raw)
To: Git List; +Cc: René Scharfe
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.
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [PATCH 00/10] typed sort of linked lists
2022-07-25 18:52 ` Junio C Hamano
@ 2022-07-25 20:35 ` Derrick Stolee
2022-07-25 20:49 ` Junio C Hamano
0 siblings, 1 reply; 15+ messages in thread
From: Derrick Stolee @ 2022-07-25 20:35 UTC (permalink / raw)
To: Junio C Hamano, Git List; +Cc: René Scharfe
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
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [PATCH 00/10] typed sort of linked lists
2022-07-25 20:35 ` Derrick Stolee
@ 2022-07-25 20:49 ` Junio C Hamano
0 siblings, 0 replies; 15+ messages in thread
From: Junio C Hamano @ 2022-07-25 20:49 UTC (permalink / raw)
To: Derrick Stolee; +Cc: Git List, René Scharfe
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.
^ permalink raw reply [flat|nested] 15+ messages in thread
end of thread, other threads:[~2022-07-25 20:49 UTC | newest]
Thread overview: 15+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2022-07-16 16:50 [PATCH 00/10] typed sort of linked lists René Scharfe
2022-07-16 16:52 ` [PATCH 01/10] mergesort: unify ranks loops René Scharfe
2022-07-16 16:53 ` [PATCH 02/10] mergesort: tighten merge loop René Scharfe
2022-07-16 16:54 ` [PATCH 03/10] mergesort: add macros for typed sort of linked lists René Scharfe
2022-07-16 16:56 ` [PATCH 04/10] test-mergesort: use DEFINE_LIST_SORT_DEBUG René Scharfe
2022-07-16 16:57 ` [PATCH 05/10] test-mergesort: use DEFINE_LIST_SORT René Scharfe
2022-07-16 16:58 ` [PATCH 06/10] blame: " René Scharfe
2022-07-16 16:59 ` [PATCH 07/10] commit: " René Scharfe
2022-07-16 16:59 ` [PATCH 08/10] fetch-pack: " René Scharfe
2022-07-16 17:01 ` [PATCH 09/10] packfile: " René Scharfe
2022-07-16 17:02 ` [PATCH 10/10] mergesort: remove llist_mergesort() René Scharfe
2022-07-17 22:31 ` [PATCH 00/10] typed sort of linked lists Junio C Hamano
2022-07-25 18:52 ` Junio C Hamano
2022-07-25 20:35 ` Derrick Stolee
2022-07-25 20:49 ` Junio C Hamano
Code repositories for project(s) associated with this public inbox
https://80x24.org/mirrors/git.git
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).