Re: [PATCH 2/2] index-pack: kill union delta_base to save memory

Nguyễn Thái Ngọc Duy  [off-list ref] writes:

Once we know the number of objects in the input pack, we allocate an
array of nr_objects of struct delta_entry. On x86-64, this struct is
32 bytes long. The union delta_base, which is part of struct
delta_entry, provides enough space to store either ofs-delta (8 bytes)
or ref-delta (20 bytes).

Sorry for responding to a patch 7000+ messages ago, but some kind
folks at Google were puzzled by this code, and I think they found a
small bug.

You allocate an array of nr_unresolved (which is the sum of
nr_ref_deltas and nr_ofs_deltas in the new world order with patch)
entries, fill only the first nr_ref_deltas entries of it, and then
sort that first n (= nr_ref_deltas) entries.  The qsort and the
subsequent loop only looks at the first n entries, so nothing is
filling or reading these nr_ofs_deltas entres at the end.

I do not see any wrong behaviour other than temporary wastage of
nr_ofs_deltas pointers that would be caused by this, but this
allocation is misleading.

Also, the old code before this change had to use 'i' and 'n' because
some of the things we see in the (old) deltas[] array we scanned
with 'i' would not make it into the sorted_by_pos[] array in the old
world order, but now because you have only ref delta in a separate
ref_deltas[] array, they increment lock&step.  That also puzzled me
while re-reading this code.

Perhaps something like this is needed?


 builtin/index-pack.c | 10 +++++-----
 1 file changed, 5 insertions(+), 5 deletions(-)

diff --git a/builtin/index-pack.c b/builtin/index-pack.c
index 48fa472..d6c48cd 100644
--- a/builtin/index-pack.c
+++ b/builtin/index-pack.c

@@ -1334,7 +1334,7 @@ static int delta_pos_compare(const void *_a, const void *_b)
 static void fix_unresolved_deltas(struct sha1file *f, int nr_unresolved)
 {
 	struct ref_delta_entry **sorted_by_pos;
-	int i, n = 0;
+	int i;
 
 	/*
 	 * Since many unresolved deltas may well be themselves base objects

@@ -1346,12 +1346,12 @@ static void fix_unresolved_deltas(struct sha1file *f, int nr_unresolved)
 	 * before deltas depending on them, a good heuristic is to start
 	 * resolving deltas in the same order as their position in the pack.
 	 */
-	sorted_by_pos = xmalloc(nr_unresolved * sizeof(*sorted_by_pos));
+	sorted_by_pos = xmalloc(nr_ref_deltas * sizeof(*sorted_by_pos));
 	for (i = 0; i < nr_ref_deltas; i++)
-		sorted_by_pos[n++] = &ref_deltas[i];
-	qsort(sorted_by_pos, n, sizeof(*sorted_by_pos), delta_pos_compare);
+		sorted_by_pos[i] = &ref_deltas[i];
+	qsort(sorted_by_pos, nr_ref_deltas, sizeof(*sorted_by_pos), delta_pos_compare);
 
-	for (i = 0; i < n; i++) {
+	for (i = 0; i < nr_ref_deltas; i++) {
 		struct ref_delta_entry *d = sorted_by_pos[i];
 		enum object_type type;
 		struct base_data *base_obj = alloc_base_data();

On Fri, Jul 3, 2015 at 11:51 PM, Junio C Hamano [off-list ref] wrote:

Nguyễn Thái Ngọc Duy  [off-list ref] writes:

quoted

Once we know the number of objects in the input pack, we allocate an
array of nr_objects of struct delta_entry. On x86-64, this struct is
32 bytes long. The union delta_base, which is part of struct
delta_entry, provides enough space to store either ofs-delta (8 bytes)
or ref-delta (20 bytes).

Sorry for responding to a patch 7000+ messages ago, but some kind
folks at Google were puzzled by this code, and I think they found a
small bug.

quoted

 static void fix_unresolved_deltas(struct sha1file *f, int nr_unresolved)
 {
-     struct delta_entry **sorted_by_pos;
+     struct ref_delta_entry **sorted_by_pos;
      int i, n = 0;

      /*

@@ -1282,28 +1344,25 @@ static void fix_unresolved_deltas(struct sha1file *f, int nr_unresolved)
       * resolving deltas in the same order as their position in the pack.
       */
      sorted_by_pos = xmalloc(nr_unresolved * sizeof(*sorted_by_pos));
-     for (i = 0; i < nr_deltas; i++) {
-             if (objects[deltas[i].obj_no].real_type != OBJ_REF_DELTA)
-                     continue;
-             sorted_by_pos[n++] = &deltas[i];
-     }
+     for (i = 0; i < nr_ref_deltas; i++)
+             sorted_by_pos[n++] = &ref_deltas[i];
      qsort(sorted_by_pos, n, sizeof(*sorted_by_pos), delta_pos_compare);

You allocate an array of nr_unresolved (which is the sum of
nr_ref_deltas and nr_ofs_deltas in the new world order with patch)
entries, fill only the first nr_ref_deltas entries of it, and then
sort that first n (= nr_ref_deltas) entries.  The qsort and the
subsequent loop only looks at the first n entries, so nothing is
filling or reading these nr_ofs_deltas entres at the end.

I do not see any wrong behaviour other than temporary wastage of
nr_ofs_deltas pointers that would be caused by this, but this
allocation is misleading.

Also, the old code before this change had to use 'i' and 'n' because
some of the things we see in the (old) deltas[] array we scanned
with 'i' would not make it into the sorted_by_pos[] array in the old
world order, but now because you have only ref delta in a separate
ref_deltas[] array, they increment lock&step.  That also puzzled me
while re-reading this code.

Perhaps something like this is needed?

Yeah I can see the confusion when reading the code without checking
its history. You probably want to kill the argument nr_unresolved too
because it's not needed anymore after your patch.

So what's the bug you mentioned? All I got from the above was wastage
and confusion, no bug.
-- 
Duy