Re: [PATCH] index-pack: reduce memory footprint a bit

> On Mon, Feb 09, 2015 at 11:27:21AM -0800, Junio C Hamano wrote:
>> > On a 3.4M object repo that's about 53MB. The saving is less impressive
>> > compared to index-pack total memory use (about 400MB before delta
>> > resolving, so the saving is just 13%)
>> >
>> > Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
>> > ---
>> >  I'm not sure if this patch is worth pursuing. It makes the code a
>> >  little bit harder to read. I was just wondering how much memory could
>> >  be saved..
>
> (text reordered)
>
>> I do not find the result all that harder to read.  I however think
>> that the change would make it a lot harder to maintain, especially
>> because the name "object-entry-extra" does not have any direct link
>> to "show-stat" to hint us that this must be allocated when show-stat
>> is in use and must never be looked at when show-stat is not in use.
>
> Noted. To be fixed.
>
>> I would say 13% is already impressive ;-).
>
> The second patch makes the total saving 119MB, close to 30% (again on
> x86-64, 32-bit platform number may be different). If we only compare
> with the size of objects[] and deltas[], the saving percentage is 37%
> (only for clone case) for this repo. Now it looks impressive to me :-D
>
> The patch is larger than the previous one, but not really complex. And
> the final index-pack.c is not hard to read either, probably becase we
> already handle ofs-delta and ref-delta separately.
>
> -- 8< --
> Subject: [PATCH 2/2] index-pack: kill union delta_base to save memory
>
> 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).
>
> Notice that with "recent" Git versions, ofs-delta objects are
> preferred over ref-delta objects and ref-delta objects have no reason
> to be present in a clone pack. So in clone case we waste
> (20-8) * nr_objects bytes because of this union. That's about 38MB out
> of 100MB for deltas[] with 3.4M objects, or 38%. deltas[] would be
> around 62MB without the waste.
>
> This patch attempts to eliminate that. deltas[] array is split into
> two: one for ofs-delta and one for ref-delta. Many functions are also
> duplicated because of this split. With this patch, ofs_delta_entry[]
> array takes 38MB. ref_deltas[] should remain unallocated in clone case
> (0 bytes). This array grows as we see ref-delta. We save more than
> half in clone case, or 25% of total book keeping.
>
> The saving is more than the calculation above because padding is
> removed by __attribute__((packed)) on ofs_delta_entry. This attribute
> should be ok to use, as we used to have it in our code base for some
> time. The last use was removed because it may lead to incorrect
> behavior when the struct is not packed, which is not the case in
> index-pack.
>
> A note about ofs_deltas allocation. We could use ref_deltas memory
> allocation strategy for ofs_deltas. But that probably just adds more
> overhead on top. ofs-deltas are generally the majority (1/2 to 2/3) in
> any pack. Incremental realloc may lead to too many memcpy. And if we
> preallocate, say 1/2 or 2/3 of nr_objects initially, the growth rate
> of ALLOC_GROW() could make this array larger than nr_objects, wasting
> more memory.
>
> Brought-up-by: Matthew Sporleder <msporleder@gmail.com>
> Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
> ---
>  builtin/index-pack.c | 260 +++++++++++++++++++++++++++++++--------------------
>  1 file changed, 160 insertions(+), 100 deletions(-)
>
> diff --git a/builtin/index-pack.c b/builtin/index-pack.c
> index 07b2c0c..27e3c8b 100644
> --- a/builtin/index-pack.c
> +++ b/builtin/index-pack.c
> @@ -28,11 +28,6 @@ struct object_stat {
>         int base_object_no;
>  };
>
> -union delta_base {
> -       unsigned char sha1[20];
> -       off_t offset;
> -};
> -
>  struct base_data {
>         struct base_data *base;
>         struct base_data *child;
> @@ -52,26 +47,28 @@ struct thread_local {
>         int pack_fd;
>  };
>
> -/*
> - * Even if sizeof(union delta_base) == 24 on 64-bit archs, we really want
> - * to memcmp() only the first 20 bytes.
> - */
> -#define UNION_BASE_SZ  20
> -
>  #define FLAG_LINK (1u<<20)
>  #define FLAG_CHECKED (1u<<21)
>
> -struct delta_entry {
> -       union delta_base base;
> +struct ofs_delta_entry {
> +       off_t offset;
> +       int obj_no;
> +} __attribute__((packed));
> +
> +struct ref_delta_entry {
> +       unsigned char sha1[20];
>         int obj_no;
>  };
>
>  static struct object_entry *objects;
>  static struct object_stat *obj_stat;
> -static struct delta_entry *deltas;
> +static struct ofs_delta_entry *ofs_deltas;
> +static struct ref_delta_entry *ref_deltas;
>  static struct thread_local nothread_data;
>  static int nr_objects;
> -static int nr_deltas;
> +static int nr_ofs_deltas;
> +static int nr_ref_deltas;
> +static int ref_deltas_alloc;
>  static int nr_resolved_deltas;
>  static int nr_threads;
>
> @@ -480,7 +477,8 @@ static void *unpack_entry_data(unsigned long offset, unsigned long size,
>  }
>
>  static void *unpack_raw_entry(struct object_entry *obj,
> -                             union delta_base *delta_base,
> +                             off_t *ofs_offset,
> +                             unsigned char *ref_sha1,
>                               unsigned char *sha1)
>  {
>         unsigned char *p;
> @@ -509,11 +507,10 @@ static void *unpack_raw_entry(struct object_entry *obj,
>
>         switch (obj->type) {
>         case OBJ_REF_DELTA:
> -               hashcpy(delta_base->sha1, fill(20));
> +               hashcpy(ref_sha1, fill(20));
>                 use(20);
>                 break;
>         case OBJ_OFS_DELTA:
> -               memset(delta_base, 0, sizeof(*delta_base));
>                 p = fill(1);
>                 c = *p;
>                 use(1);
> @@ -527,8 +524,8 @@ static void *unpack_raw_entry(struct object_entry *obj,
>                         use(1);
>                         base_offset = (base_offset << 7) + (c & 127);
>                 }
> -               delta_base->offset = obj->idx.offset - base_offset;
> -               if (delta_base->offset <= 0 || delta_base->offset >= obj->idx.offset)
> +               *ofs_offset = obj->idx.offset - base_offset;
> +               if (*ofs_offset <= 0 || *ofs_offset >= obj->idx.offset)
>                         bad_object(obj->idx.offset, _("delta base offset is out of bound"));
>                 break;
>         case OBJ_COMMIT:
> @@ -612,55 +609,108 @@ static void *get_data_from_pack(struct object_entry *obj)
>         return unpack_data(obj, NULL, NULL);
>  }
>
> -static int compare_delta_bases(const union delta_base *base1,
> -                              const union delta_base *base2,
> -                              enum object_type type1,
> -                              enum object_type type2)
> +static int compare_ofs_delta_bases(off_t offset1, off_t offset2,
> +                                  enum object_type type1,
> +                                  enum object_type type2)
> +{
> +       int cmp = type1 - type2;
> +       if (cmp)
> +               return cmp;
> +       return offset1 - offset2;
> +}
> +
> +static int find_ofs_delta(const off_t offset, enum object_type type)
> +{
> +       int first = 0, last = nr_ofs_deltas;
> +
> +       while (first < last) {
> +               int next = (first + last) / 2;
> +               struct ofs_delta_entry *delta = &ofs_deltas[next];
> +               int cmp;
> +
> +               cmp = compare_ofs_delta_bases(offset, delta->offset,
> +                                             type, objects[delta->obj_no].type);
> +               if (!cmp)
> +                       return next;
> +               if (cmp < 0) {
> +                       last = next;
> +                       continue;
> +               }
> +               first = next+1;
> +       }
> +       return -first-1;
> +}
> +
> +static void find_ofs_delta_children(off_t offset,
> +                                   int *first_index, int *last_index,
> +                                   enum object_type type)
> +{
> +       int first = find_ofs_delta(offset, type);
> +       int last = first;
> +       int end = nr_ofs_deltas - 1;
> +
> +       if (first < 0) {
> +               *first_index = 0;
> +               *last_index = -1;
> +               return;
> +       }
> +       while (first > 0 && ofs_deltas[first - 1].offset == offset)
> +               --first;
> +       while (last < end && ofs_deltas[last + 1].offset == offset)
> +               ++last;
> +       *first_index = first;
> +       *last_index = last;
> +}
> +
> +static int compare_ref_delta_bases(const unsigned char *sha1,
> +                                  const unsigned char *sha2,
> +                                  enum object_type type1,
> +                                  enum object_type type2)
>  {
>         int cmp = type1 - type2;
>         if (cmp)
>                 return cmp;
> -       return memcmp(base1, base2, UNION_BASE_SZ);
> +       return hashcmp(sha1, sha2);
>  }
>
> -static int find_delta(const union delta_base *base, enum object_type type)
> +static int find_ref_delta(const unsigned char *sha1, enum object_type type)
>  {
> -       int first = 0, last = nr_deltas;
> -
> -        while (first < last) {
> -                int next = (first + last) / 2;
> -                struct delta_entry *delta = &deltas[next];
> -                int cmp;
> -
> -               cmp = compare_delta_bases(base, &delta->base,
> -                                         type, objects[delta->obj_no].type);
> -                if (!cmp)
> -                        return next;
> -                if (cmp < 0) {
> -                        last = next;
> -                        continue;
> -                }
> -                first = next+1;
> -        }
> -        return -first-1;
> +       int first = 0, last = nr_ref_deltas;
> +
> +       while (first < last) {
> +               int next = (first + last) / 2;
> +               struct ref_delta_entry *delta = &ref_deltas[next];
> +               int cmp;
> +
> +               cmp = compare_ref_delta_bases(sha1, delta->sha1,
> +                                             type, objects[delta->obj_no].type);
> +               if (!cmp)
> +                       return next;
> +               if (cmp < 0) {
> +                       last = next;
> +                       continue;
> +               }
> +               first = next+1;
> +       }
> +       return -first-1;
>  }
>
> -static void find_delta_children(const union delta_base *base,
> -                               int *first_index, int *last_index,
> -                               enum object_type type)
> +static void find_ref_delta_children(const unsigned char *sha1,
> +                                   int *first_index, int *last_index,
> +                                   enum object_type type)
>  {
> -       int first = find_delta(base, type);
> +       int first = find_ref_delta(sha1, type);
>         int last = first;
> -       int end = nr_deltas - 1;
> +       int end = nr_ref_deltas - 1;
>
>         if (first < 0) {
>                 *first_index = 0;
>                 *last_index = -1;
>                 return;
>         }
> -       while (first > 0 && !memcmp(&deltas[first - 1].base, base, UNION_BASE_SZ))
> +       while (first > 0 && !hashcmp(ref_deltas[first - 1].sha1, sha1))
>                 --first;
> -       while (last < end && !memcmp(&deltas[last + 1].base, base, UNION_BASE_SZ))
> +       while (last < end && !hashcmp(ref_deltas[last + 1].sha1, sha1))
>                 ++last;
>         *first_index = first;
>         *last_index = last;
> @@ -927,16 +977,13 @@ static struct base_data *find_unresolved_deltas_1(struct base_data *base,
>                                                   struct base_data *prev_base)
>  {
>         if (base->ref_last == -1 && base->ofs_last == -1) {
> -               union delta_base base_spec;
> -
> -               hashcpy(base_spec.sha1, base->obj->idx.sha1);
> -               find_delta_children(&base_spec,
> -                                   &base->ref_first, &base->ref_last, OBJ_REF_DELTA);
> +               find_ref_delta_children(base->obj->idx.sha1,
> +                                       &base->ref_first, &base->ref_last,
> +                                       OBJ_REF_DELTA);
>
> -               memset(&base_spec, 0, sizeof(base_spec));
> -               base_spec.offset = base->obj->idx.offset;
> -               find_delta_children(&base_spec,
> -                                   &base->ofs_first, &base->ofs_last, OBJ_OFS_DELTA);
> +               find_ofs_delta_children(base->obj->idx.offset,
> +                                       &base->ofs_first, &base->ofs_last,
> +                                       OBJ_OFS_DELTA);
>
>                 if (base->ref_last == -1 && base->ofs_last == -1) {
>                         free(base->data);
> @@ -947,7 +994,7 @@ static struct base_data *find_unresolved_deltas_1(struct base_data *base,
>         }
>
>         if (base->ref_first <= base->ref_last) {
> -               struct object_entry *child = objects + deltas[base->ref_first].obj_no;
> +               struct object_entry *child = objects + ref_deltas[base->ref_first].obj_no;
>                 struct base_data *result = alloc_base_data();
>
>                 if (!compare_and_swap_type(&child->real_type, OBJ_REF_DELTA,
> @@ -963,7 +1010,7 @@ static struct base_data *find_unresolved_deltas_1(struct base_data *base,
>         }
>
>         if (base->ofs_first <= base->ofs_last) {
> -               struct object_entry *child = objects + deltas[base->ofs_first].obj_no;
> +               struct object_entry *child = objects + ofs_deltas[base->ofs_first].obj_no;
>                 struct base_data *result = alloc_base_data();
>
>                 assert(child->real_type == OBJ_OFS_DELTA);
> @@ -999,15 +1046,20 @@ static void find_unresolved_deltas(struct base_data *base)
>         }
>  }
>
> -static int compare_delta_entry(const void *a, const void *b)
> +static int compare_ofs_delta_entry(const void *a, const void *b)
> +{
> +       const struct ofs_delta_entry *delta_a = a;
> +       const struct ofs_delta_entry *delta_b = b;
> +
> +       return delta_a->offset - delta_b->offset;
> +}
> +
> +static int compare_ref_delta_entry(const void *a, const void *b)
>  {
> -       const struct delta_entry *delta_a = a;
> -       const struct delta_entry *delta_b = b;
> +       const struct ref_delta_entry *delta_a = a;
> +       const struct ref_delta_entry *delta_b = b;
>
> -       /* group by type (ref vs ofs) and then by value (sha-1 or offset) */
> -       return compare_delta_bases(&delta_a->base, &delta_b->base,
> -                                  objects[delta_a->obj_no].type,
> -                                  objects[delta_b->obj_no].type);
> +       return hashcmp(delta_a->sha1, delta_b->sha1);
>  }
>
>  static void resolve_base(struct object_entry *obj)
> @@ -1053,7 +1105,8 @@ static void *threaded_second_pass(void *data)
>  static void parse_pack_objects(unsigned char *sha1)
>  {
>         int i, nr_delays = 0;
> -       struct delta_entry *delta = deltas;
> +       struct ofs_delta_entry *ofs_delta = ofs_deltas;
> +       unsigned char ref_delta_sha1[20];
>         struct stat st;
>
>         if (verbose)
> @@ -1062,12 +1115,18 @@ static void parse_pack_objects(unsigned char *sha1)
>                                 nr_objects);
>         for (i = 0; i < nr_objects; i++) {
>                 struct object_entry *obj = &objects[i];
> -               void *data = unpack_raw_entry(obj, &delta->base, obj->idx.sha1);
> +               void *data = unpack_raw_entry(obj, &ofs_delta->offset,
> +                                             ref_delta_sha1, obj->idx.sha1);
>                 obj->real_type = obj->type;
> -               if (is_delta_type(obj->type)) {
> -                       nr_deltas++;
> -                       delta->obj_no = i;
> -                       delta++;
> +               if (obj->type == OBJ_OFS_DELTA) {
> +                       nr_ofs_deltas++;
> +                       ofs_delta->obj_no = i;
> +                       ofs_delta++;
> +               } else if (obj->type == OBJ_REF_DELTA) {
> +                       ALLOC_GROW(ref_deltas, nr_ref_deltas + 1, ref_deltas_alloc);
> +                       hashcpy(ref_deltas[nr_ref_deltas].sha1, ref_delta_sha1);
> +                       ref_deltas[nr_ref_deltas].obj_no = i;
> +                       nr_ref_deltas++;
>                 } else if (!data) {
>                         /* large blobs, check later */
>                         obj->real_type = OBJ_BAD;
> @@ -1118,15 +1177,18 @@ static void resolve_deltas(void)
>  {
>         int i;
>
> -       if (!nr_deltas)
> +       if (!nr_ofs_deltas && !nr_ref_deltas)
>                 return;
>
>         /* Sort deltas by base SHA1/offset for fast searching */
> -       qsort(deltas, nr_deltas, sizeof(struct delta_entry),
> -             compare_delta_entry);
> +       qsort(ofs_deltas, nr_ofs_deltas, sizeof(struct ofs_delta_entry),
> +             compare_ofs_delta_entry);
> +       qsort(ref_deltas, nr_ref_deltas, sizeof(struct ref_delta_entry),
> +             compare_ref_delta_entry);
>
>         if (verbose)
> -               progress = start_progress(_("Resolving deltas"), nr_deltas);
> +               progress = start_progress(_("Resolving deltas"),
> +                                         nr_ref_deltas + nr_ofs_deltas);
>
>  #ifndef NO_PTHREADS
>         nr_dispatched = 0;
> @@ -1164,7 +1226,7 @@ static void resolve_deltas(void)
>  static void fix_unresolved_deltas(struct sha1file *f, int nr_unresolved);
>  static void conclude_pack(int fix_thin_pack, const char *curr_pack, unsigned char *pack_sha1)
>  {
> -       if (nr_deltas == nr_resolved_deltas) {
> +       if (nr_ref_deltas + nr_ofs_deltas == nr_resolved_deltas) {
>                 stop_progress(&progress);
>                 /* Flush remaining pack final 20-byte SHA1. */
>                 flush();
> @@ -1175,7 +1237,7 @@ static void conclude_pack(int fix_thin_pack, const char *curr_pack, unsigned cha
>                 struct sha1file *f;
>                 unsigned char read_sha1[20], tail_sha1[20];
>                 struct strbuf msg = STRBUF_INIT;
> -               int nr_unresolved = nr_deltas - nr_resolved_deltas;
> +               int nr_unresolved = nr_ofs_deltas + nr_ref_deltas - nr_resolved_deltas;
>                 int nr_objects_initial = nr_objects;
>                 if (nr_unresolved <= 0)
>                         die(_("confusion beyond insanity"));
> @@ -1197,11 +1259,11 @@ static void conclude_pack(int fix_thin_pack, const char *curr_pack, unsigned cha
>                         die(_("Unexpected tail checksum for %s "
>                               "(disk corruption?)"), curr_pack);
>         }
> -       if (nr_deltas != nr_resolved_deltas)
> +       if (nr_ofs_deltas + nr_ref_deltas != nr_resolved_deltas)
>                 die(Q_("pack has %d unresolved delta",
>                        "pack has %d unresolved deltas",
> -                      nr_deltas - nr_resolved_deltas),
> -                   nr_deltas - nr_resolved_deltas);
> +                      nr_ofs_deltas + nr_ref_deltas - nr_resolved_deltas),
> +                   nr_ofs_deltas + nr_ref_deltas - nr_resolved_deltas);
>  }
>
>  static int write_compressed(struct sha1file *f, void *in, unsigned int size)
> @@ -1261,14 +1323,14 @@ static struct object_entry *append_obj_to_pack(struct sha1file *f,
>
>  static int delta_pos_compare(const void *_a, const void *_b)
>  {
> -       struct delta_entry *a = *(struct delta_entry **)_a;
> -       struct delta_entry *b = *(struct delta_entry **)_b;
> +       struct ref_delta_entry *a = *(struct ref_delta_entry **)_a;
> +       struct ref_delta_entry *b = *(struct ref_delta_entry **)_b;
>         return a->obj_no - b->obj_no;
>  }
>
>  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);
>
>         for (i = 0; i < n; i++) {
> -               struct delta_entry *d = sorted_by_pos[i];
> +               struct ref_delta_entry *d = sorted_by_pos[i];
>                 enum object_type type;
>                 struct base_data *base_obj = alloc_base_data();
>
>                 if (objects[d->obj_no].real_type != OBJ_REF_DELTA)
>                         continue;
> -               base_obj->data = read_sha1_file(d->base.sha1, &type, &base_obj->size);
> +               base_obj->data = read_sha1_file(d->sha1, &type, &base_obj->size);
>                 if (!base_obj->data)
>                         continue;
>
> -               if (check_sha1_signature(d->base.sha1, base_obj->data,
> +               if (check_sha1_signature(d->sha1, base_obj->data,
>                                 base_obj->size, typename(type)))
> -                       die(_("local object %s is corrupt"), sha1_to_hex(d->base.sha1));
> -               base_obj->obj = append_obj_to_pack(f, d->base.sha1,
> +                       die(_("local object %s is corrupt"), sha1_to_hex(d->sha1));
> +               base_obj->obj = append_obj_to_pack(f, d->sha1,
>                                         base_obj->data, base_obj->size, type);
>                 find_unresolved_deltas(base_obj);
>                 display_progress(progress, nr_resolved_deltas);
> @@ -1495,7 +1554,7 @@ static void read_idx_option(struct pack_idx_option *opts, const char *pack_name)
>
>  static void show_pack_info(int stat_only)
>  {
> -       int i, baseobjects = nr_objects - nr_deltas;
> +       int i, baseobjects = nr_objects - nr_ref_deltas - nr_ofs_deltas;
>         unsigned long *chain_histogram = NULL;
>
>         if (deepest_delta)
> @@ -1680,11 +1739,12 @@ int cmd_index_pack(int argc, const char **argv, const char *prefix)
>         objects = xcalloc(nr_objects + 1, sizeof(struct object_entry));
>         if (show_stat)
>                 obj_stat = xcalloc(nr_objects + 1, sizeof(struct object_stat));
> -       deltas = xcalloc(nr_objects, sizeof(struct delta_entry));
> +       ofs_deltas = xcalloc(nr_objects, sizeof(struct ofs_delta_entry));
>         parse_pack_objects(pack_sha1);
>         resolve_deltas();
>         conclude_pack(fix_thin_pack, curr_pack, pack_sha1);
> -       free(deltas);
> +       free(ofs_deltas);
> +       free(ref_deltas);
>         if (strict)
>                 foreign_nr = check_objects();
>
> --
> 2.2.0.513.g477eb31
>
> -- 8< --