Re: [PATCH v6 00/11] nd/pack-objects-pack-struct updates

[Ramsay Jones <ramsay@ramsayjones.plus.com>]

On 22/03/18 09:32, Jeff King wrote:
> On Wed, Mar 21, 2018 at 04:59:19PM +0100, Duy Nguyen wrote:
> 
>>> I hate to be a wet blanket, but am I the only one who is wondering
>>> whether the tradeoffs is worth it? 8% memory reduction doesn't seem
>>> mind-bogglingly good,
>>
>> AEvar measured RSS. If we count objects[] array alone, the saving is
>> 40% (136 bytes per entry down to 80). Some is probably eaten up by
>> mmap in rss.
> 
> Measuring actual heap usage with massif, I get before/after peak heaps
> of 1728 and 1346MB respectively when repacking linux.git. So that's ~22%
> savings overall.
> 
> Of the used heap after your patches:
> 
>  - ~40% of that is from packlist_alloc()
>  - ~17% goes to "struct object"
>  - ~10% for the object.c hash table to store all the "struct object"
>  - ~7% goes to the delta cache
>  - ~7% goes to the pack revindex (actually, there's a duplicate 7%
>        there, too; I think our peak is when we're sorting the revindex
>        and have to keep two copies in memory at once)

which begs the question, how much slower would it be if we
replaced the radix-sort with an in-place sort (e.g. heapsort).

I hacked up the patch below, just for fun. I don't have any
large repos (or enough disk space) to do any meaningful perf
tests, but I did at least compile it and it passes the test-suite.
(That is no guarantee that I haven't introduced bugs, of course!)

;-)

ATB,
Ramsay Jones

-- >8 --
Subject: [PATCH] pack-revindex: replace radix-sort with in-place heapsort

Signed-off-by: Ramsay Jones <ramsay@ramsayjones.plus.com>
---
 pack-revindex.c | 60 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 60 insertions(+)

diff --git a/pack-revindex.c b/pack-revindex.c
index ff5f62c03..16f17eac1 100644
--- a/pack-revindex.c
+++ b/pack-revindex.c
@@ -15,6 +15,7 @@
  * get the object sha1 from the main index.
  */
 
+#ifdef DUMMY
 /*
  * This is a least-significant-digit radix sort.
  *
@@ -112,6 +113,65 @@ static void sort_revindex(struct revindex_entry *entries, unsigned n, off_t max)
 #undef BUCKETS
 #undef DIGIT_SIZE
 }
+#endif
+
+static inline void swap(struct revindex_entry *a, int i, int j)
+{
+	struct revindex_entry t;
+
+	t = a[i];
+	a[i] = a[j];
+	a[j] = t;
+}
+
+/*
+ * assume that elements first .. last (array index first-1 .. last-1) obey
+ * the partially ordered tree property, except possibly for the children of
+ * the first element. push down the first element until the partially
+ * ordered tree property is restored.
+ */
+static void push_down(struct revindex_entry *a, int first, int last)
+{
+	int parent = first;
+	int last_node = last / 2;
+
+	while (parent <= last_node) {
+
+		int left = 2 * parent;
+		int right = left + 1;
+		int biggest;
+
+		if (right > last) /* parent only has one child */
+			biggest = left;
+		else {
+			if (a[left-1].offset >= a[right-1].offset)
+				biggest = left;
+			else
+				biggest = right;
+
+		}
+
+		if (a[parent-1].offset >= a[biggest-1].offset)
+			break; /* partially ordered tree property, we're done */
+
+		/* push parent down */
+		swap(a, parent-1, biggest-1);
+		parent = biggest;
+	}
+}
+
+static void sort_revindex(struct revindex_entry *entries, unsigned n, off_t max)
+{
+	int i;
+
+	for (i = n/2; i > 0; i--)
+		push_down(entries, i, n);
+
+	for (i = n; i > 1; i--) {
+		swap(entries, 0, i-1);
+		push_down(entries, 1, i-1);
+	}
+}
 
 /*
  * Ordered list of offsets of objects in the pack.
-- 
2.16.0