{"thread":{"id":"38607","subject":"[PATCH 0/2] nd/slim-index-pack-memory-usage updates","startedAt":"2015-02-20T01:58:06Z","lastAt":"2015-03-01T02:37:40Z","messageCount":11,"participants":["Nguyễn Thái Ngọc Duy","Junio C Hamano","Duy Nguyen"],"isPatch":true,"patchVersion":1,"patchTotal":2},"messages":[{"id":"256377","messageId":"1424397488-22169-1-git-send-email-pclouds@gmail.com","threadId":"38607","inReplyTo":null,"subject":"[PATCH 0/2] nd/slim-index-pack-memory-usage updates","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2015-02-20T01:58:06Z","receivedAt":"2015-02-20T01:58:06Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"Compared to 'pu', the first patch is unchanged, except the commit\nmessage. The second patch has __attribute((packed)) removed because it\ncauses problems on some ARM systems. x86 people who want to save more\nmemory just have to put it back by themselves.\n\nNguyễn Thái Ngọc Duy (2):\n  index-pack: reduce object_entry size to save memory\n  index-pack: kill union delta_base to save memory\n\n builtin/index-pack.c | 290 +++++++++++++++++++++++++++++++--------------------\n 1 file changed, 179 insertions(+), 111 deletions(-)\n\n-- \n2.3.0.rc1.137.g477eb31\n"},{"id":"256379","messageId":"1424397488-22169-2-git-send-email-pclouds@gmail.com","threadId":"38607","inReplyTo":"1424397488-22169-1-git-send-email-pclouds@gmail.com","subject":"[PATCH 1/2] index-pack: reduce object_entry size to save memory","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2015-02-20T01:58:07Z","receivedAt":"2015-02-20T01:58:07Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"For each object in the input pack, we need one struct object_entry. On\nx86-64, this struct is 64 bytes long. Although:\n\n - The 8 bytes for delta_depth and base_object_no are only useful when\n   show_stat is set. And it's never set unless someone is debugging.\n\n - The three fields hdr_size, type and real_type take 4 bytes each\n   even though they never use more than 4 bits.\n\nBy moving delta_depth and base_object_no out of struct object_entry\nand make the other 3 fields one byte long instead of 4, we shrink 25%\nof this struct.\n\nOn a 3.4M object repo (*) that's about 53MB. The saving is less\nimpressive compared to index-pack memory use for basic bookkeeping (**),\nabout 16%.\n\n(*) linux-2.6.git already has 4M objects as of v3.19-rc7 so this is\nnot an unrealistic number of objects that we have to deal with.\n\n(**)  3.4M * (sizeof(object_entry) + sizeof(delta_entry)) = 311MB\n\nBrought-up-by: Matthew Sporleder <msporleder@gmail.com>\nSigned-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>\n---\n builtin/index-pack.c | 30 +++++++++++++++++++-----------\n 1 file changed, 19 insertions(+), 11 deletions(-)\n\ndiff --git a/builtin/index-pack.c b/builtin/index-pack.c\nindex 4632117..07b2c0c 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -18,9 +18,12 @@ static const char index_pack_usage[] =\n struct object_entry {\n \tstruct pack_idx_entry idx;\n \tunsigned long size;\n-\tunsigned int hdr_size;\n-\tenum object_type type;\n-\tenum object_type real_type;\n+\tunsigned char hdr_size;\n+\tchar type;\n+\tchar real_type;\n+};\n+\n+struct object_stat {\n \tunsigned delta_depth;\n \tint base_object_no;\n };\n@@ -64,6 +67,7 @@ struct delta_entry {\n };\n \n static struct object_entry *objects;\n+static struct object_stat *obj_stat;\n static struct delta_entry *deltas;\n static struct thread_local nothread_data;\n static int nr_objects;\n@@ -873,13 +877,15 @@ static void resolve_delta(struct object_entry *delta_obj,\n \tvoid *base_data, *delta_data;\n \n \tif (show_stat) {\n-\t\tdelta_obj->delta_depth = base->obj->delta_depth + 1;\n+\t\tint i = delta_obj - objects;\n+\t\tint j = base->obj - objects;\n+\t\tobj_stat[i].delta_depth = obj_stat[j].delta_depth + 1;\n \t\tdeepest_delta_lock();\n-\t\tif (deepest_delta < delta_obj->delta_depth)\n-\t\t\tdeepest_delta = delta_obj->delta_depth;\n+\t\tif (deepest_delta < obj_stat[i].delta_depth)\n+\t\t\tdeepest_delta = obj_stat[i].delta_depth;\n \t\tdeepest_delta_unlock();\n+\t\tobj_stat[i].base_object_no = j;\n \t}\n-\tdelta_obj->base_object_no = base->obj - objects;\n \tdelta_data = get_data_from_pack(delta_obj);\n \tbase_data = get_base_data(base);\n \tresult->obj = delta_obj;\n@@ -902,7 +908,7 @@ static void resolve_delta(struct object_entry *delta_obj,\n  * \"want\"; if so, swap in \"set\" and return true. Otherwise, leave it untouched\n  * and return false.\n  */\n-static int compare_and_swap_type(enum object_type *type,\n+static int compare_and_swap_type(char *type,\n \t\t\t\t enum object_type want,\n \t\t\t\t enum object_type set)\n {\n@@ -1499,7 +1505,7 @@ static void show_pack_info(int stat_only)\n \t\tstruct object_entry *obj = &objects[i];\n \n \t\tif (is_delta_type(obj->type))\n-\t\t\tchain_histogram[obj->delta_depth - 1]++;\n+\t\t\tchain_histogram[obj_stat[i].delta_depth - 1]++;\n \t\tif (stat_only)\n \t\t\tcontinue;\n \t\tprintf(\"%s %-6s %lu %lu %\"PRIuMAX,\n@@ -1508,8 +1514,8 @@ static void show_pack_info(int stat_only)\n \t\t       (unsigned long)(obj[1].idx.offset - obj->idx.offset),\n \t\t       (uintmax_t)obj->idx.offset);\n \t\tif (is_delta_type(obj->type)) {\n-\t\t\tstruct object_entry *bobj = &objects[obj->base_object_no];\n-\t\t\tprintf(\" %u %s\", obj->delta_depth, sha1_to_hex(bobj->idx.sha1));\n+\t\t\tstruct object_entry *bobj = &objects[obj_stat[i].base_object_no];\n+\t\t\tprintf(\" %u %s\", obj_stat[i].delta_depth, sha1_to_hex(bobj->idx.sha1));\n \t\t}\n \t\tputchar('\\n');\n \t}\n@@ -1672,6 +1678,8 @@ int cmd_index_pack(int argc, const char **argv, const char *prefix)\n \tcurr_pack = open_pack_file(pack_name);\n \tparse_pack_header();\n \tobjects = xcalloc(nr_objects + 1, sizeof(struct object_entry));\n+\tif (show_stat)\n+\t\tobj_stat = xcalloc(nr_objects + 1, sizeof(struct object_stat));\n \tdeltas = xcalloc(nr_objects, sizeof(struct delta_entry));\n \tparse_pack_objects(pack_sha1);\n \tresolve_deltas();\n-- \n2.3.0.rc1.137.g477eb31\n"},{"id":"256378","messageId":"1424397488-22169-3-git-send-email-pclouds@gmail.com","threadId":"38607","inReplyTo":"1424397488-22169-1-git-send-email-pclouds@gmail.com","subject":"[PATCH 2/2] index-pack: kill union delta_base to save memory","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2015-02-20T01:58:08Z","receivedAt":"2015-02-20T01:58:08Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"Once we know the number of objects in the input pack, we allocate an\narray of nr_objects of struct delta_entry. On x86-64, this struct is\n32 bytes long. The union delta_base, which is part of struct\ndelta_entry, provides enough space to store either ofs-delta (8 bytes)\nor ref-delta (20 bytes).\n\nNotice that with \"recent\" Git versions, ofs-delta objects are\npreferred over ref-delta objects and ref-delta objects have no reason\nto be present in a clone pack. So in clone case we waste (20-8) *\nnr_objects bytes because of this union. That's about 38MB out of 100MB\nfor deltas[] with 3.4M objects, or 38%. deltas[] would be around 62MB\nwithout the waste.\n\nThis patch attempts to eliminate that. deltas[] array is split into\ntwo: one for ofs-delta and one for ref-delta. Many functions are also\nduplicated because of this split. With this patch, ofs_deltas[] array\ntakes 51MB. ref_deltas[] should remain unallocated in clone case (0\nbytes). This array grows as we see ref-delta. We save about half in\nclone case, or 25% of total bookkeeping.\n\nThe saving is more than the calculation above because some padding in\nthe old delta_entry struct is removed. ofs_delta_entry is 16 bytes,\nincluding the 4 bytes padding. That's 13MB for padding, but packing\nthe struct could break platforms that do not support unaligned\naccess. If someone on 32-bit is really low on memory and only deals\nwith packs smaller than 2G, using 32-bit off_t would eliminate the\npadding and save 27MB on top.\n\nA note about ofs_deltas allocation. We could use ref_deltas memory\nallocation strategy for ofs_deltas. But that probably just adds more\noverhead on top. ofs-deltas are generally the majority (1/2 to 2/3) in\nany pack. Incremental realloc may lead to too many memcpy. And if we\npreallocate, say 1/2 or 2/3 of nr_objects initially, the growth rate\nof ALLOC_GROW() could make this array larger than nr_objects, wasting\nmore memory.\n\nBrought-up-by: Matthew Sporleder <msporleder@gmail.com>\nSigned-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>\n---\n builtin/index-pack.c | 260 +++++++++++++++++++++++++++++++--------------------\n 1 file changed, 160 insertions(+), 100 deletions(-)\n\ndiff --git a/builtin/index-pack.c b/builtin/index-pack.c\nindex 07b2c0c..eae41c4 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -28,11 +28,6 @@ struct object_stat {\n \tint base_object_no;\n };\n \n-union delta_base {\n-\tunsigned char sha1[20];\n-\toff_t offset;\n-};\n-\n struct base_data {\n \tstruct base_data *base;\n \tstruct base_data *child;\n@@ -52,26 +47,28 @@ struct thread_local {\n \tint pack_fd;\n };\n \n-/*\n- * Even if sizeof(union delta_base) == 24 on 64-bit archs, we really want\n- * to memcmp() only the first 20 bytes.\n- */\n-#define UNION_BASE_SZ\t20\n-\n #define FLAG_LINK (1u<<20)\n #define FLAG_CHECKED (1u<<21)\n \n-struct delta_entry {\n-\tunion delta_base base;\n+struct ofs_delta_entry {\n+\toff_t offset;\n+\tint obj_no;\n+};\n+\n+struct ref_delta_entry {\n+\tunsigned char sha1[20];\n \tint obj_no;\n };\n \n static struct object_entry *objects;\n static struct object_stat *obj_stat;\n-static struct delta_entry *deltas;\n+static struct ofs_delta_entry *ofs_deltas;\n+static struct ref_delta_entry *ref_deltas;\n static struct thread_local nothread_data;\n static int nr_objects;\n-static int nr_deltas;\n+static int nr_ofs_deltas;\n+static int nr_ref_deltas;\n+static int ref_deltas_alloc;\n static int nr_resolved_deltas;\n static int nr_threads;\n \n@@ -480,7 +477,8 @@ static void *unpack_entry_data(unsigned long offset, unsigned long size,\n }\n \n static void *unpack_raw_entry(struct object_entry *obj,\n-\t\t\t      union delta_base *delta_base,\n+\t\t\t      off_t *ofs_offset,\n+\t\t\t      unsigned char *ref_sha1,\n \t\t\t      unsigned char *sha1)\n {\n \tunsigned char *p;\n@@ -509,11 +507,10 @@ static void *unpack_raw_entry(struct object_entry *obj,\n \n \tswitch (obj->type) {\n \tcase OBJ_REF_DELTA:\n-\t\thashcpy(delta_base->sha1, fill(20));\n+\t\thashcpy(ref_sha1, fill(20));\n \t\tuse(20);\n \t\tbreak;\n \tcase OBJ_OFS_DELTA:\n-\t\tmemset(delta_base, 0, sizeof(*delta_base));\n \t\tp = fill(1);\n \t\tc = *p;\n \t\tuse(1);\n@@ -527,8 +524,8 @@ static void *unpack_raw_entry(struct object_entry *obj,\n \t\t\tuse(1);\n \t\t\tbase_offset = (base_offset << 7) + (c & 127);\n \t\t}\n-\t\tdelta_base->offset = obj->idx.offset - base_offset;\n-\t\tif (delta_base->offset <= 0 || delta_base->offset >= obj->idx.offset)\n+\t\t*ofs_offset = obj->idx.offset - base_offset;\n+\t\tif (*ofs_offset <= 0 || *ofs_offset >= obj->idx.offset)\n \t\t\tbad_object(obj->idx.offset, _(\"delta base offset is out of bound\"));\n \t\tbreak;\n \tcase OBJ_COMMIT:\n@@ -612,55 +609,108 @@ static void *get_data_from_pack(struct object_entry *obj)\n \treturn unpack_data(obj, NULL, NULL);\n }\n \n-static int compare_delta_bases(const union delta_base *base1,\n-\t\t\t       const union delta_base *base2,\n-\t\t\t       enum object_type type1,\n-\t\t\t       enum object_type type2)\n+static int compare_ofs_delta_bases(off_t offset1, off_t offset2,\n+\t\t\t\t   enum object_type type1,\n+\t\t\t\t   enum object_type type2)\n {\n \tint cmp = type1 - type2;\n \tif (cmp)\n \t\treturn cmp;\n-\treturn memcmp(base1, base2, UNION_BASE_SZ);\n+\treturn offset1 - offset2;\n }\n \n-static int find_delta(const union delta_base *base, enum object_type type)\n+static int find_ofs_delta(const off_t offset, enum object_type type)\n {\n-\tint first = 0, last = nr_deltas;\n-\n-        while (first < last) {\n-                int next = (first + last) / 2;\n-                struct delta_entry *delta = &deltas[next];\n-                int cmp;\n-\n-\t\tcmp = compare_delta_bases(base, &delta->base,\n-\t\t\t\t\t  type, objects[delta->obj_no].type);\n-                if (!cmp)\n-                        return next;\n-                if (cmp < 0) {\n-                        last = next;\n-                        continue;\n-                }\n-                first = next+1;\n-        }\n-        return -first-1;\n+\tint first = 0, last = nr_ofs_deltas;\n+\n+\twhile (first < last) {\n+\t\tint next = (first + last) / 2;\n+\t\tstruct ofs_delta_entry *delta = &ofs_deltas[next];\n+\t\tint cmp;\n+\n+\t\tcmp = compare_ofs_delta_bases(offset, delta->offset,\n+\t\t\t\t\t      type, objects[delta->obj_no].type);\n+\t\tif (!cmp)\n+\t\t\treturn next;\n+\t\tif (cmp < 0) {\n+\t\t\tlast = next;\n+\t\t\tcontinue;\n+\t\t}\n+\t\tfirst = next+1;\n+\t}\n+\treturn -first-1;\n }\n \n-static void find_delta_children(const union delta_base *base,\n-\t\t\t\tint *first_index, int *last_index,\n-\t\t\t\tenum object_type type)\n+static void find_ofs_delta_children(off_t offset,\n+\t\t\t\t    int *first_index, int *last_index,\n+\t\t\t\t    enum object_type type)\n {\n-\tint first = find_delta(base, type);\n+\tint first = find_ofs_delta(offset, type);\n \tint last = first;\n-\tint end = nr_deltas - 1;\n+\tint end = nr_ofs_deltas - 1;\n \n \tif (first < 0) {\n \t\t*first_index = 0;\n \t\t*last_index = -1;\n \t\treturn;\n \t}\n-\twhile (first > 0 && !memcmp(&deltas[first - 1].base, base, UNION_BASE_SZ))\n+\twhile (first > 0 && ofs_deltas[first - 1].offset == offset)\n \t\t--first;\n-\twhile (last < end && !memcmp(&deltas[last + 1].base, base, UNION_BASE_SZ))\n+\twhile (last < end && ofs_deltas[last + 1].offset == offset)\n+\t\t++last;\n+\t*first_index = first;\n+\t*last_index = last;\n+}\n+\n+static int compare_ref_delta_bases(const unsigned char *sha1,\n+\t\t\t\t   const unsigned char *sha2,\n+\t\t\t\t   enum object_type type1,\n+\t\t\t\t   enum object_type type2)\n+{\n+\tint cmp = type1 - type2;\n+\tif (cmp)\n+\t\treturn cmp;\n+\treturn hashcmp(sha1, sha2);\n+}\n+\n+static int find_ref_delta(const unsigned char *sha1, enum object_type type)\n+{\n+\tint first = 0, last = nr_ref_deltas;\n+\n+\twhile (first < last) {\n+\t\tint next = (first + last) / 2;\n+\t\tstruct ref_delta_entry *delta = &ref_deltas[next];\n+\t\tint cmp;\n+\n+\t\tcmp = compare_ref_delta_bases(sha1, delta->sha1,\n+\t\t\t\t\t      type, objects[delta->obj_no].type);\n+\t\tif (!cmp)\n+\t\t\treturn next;\n+\t\tif (cmp < 0) {\n+\t\t\tlast = next;\n+\t\t\tcontinue;\n+\t\t}\n+\t\tfirst = next+1;\n+\t}\n+\treturn -first-1;\n+}\n+\n+static void find_ref_delta_children(const unsigned char *sha1,\n+\t\t\t\t    int *first_index, int *last_index,\n+\t\t\t\t    enum object_type type)\n+{\n+\tint first = find_ref_delta(sha1, type);\n+\tint last = first;\n+\tint end = nr_ref_deltas - 1;\n+\n+\tif (first < 0) {\n+\t\t*first_index = 0;\n+\t\t*last_index = -1;\n+\t\treturn;\n+\t}\n+\twhile (first > 0 && !hashcmp(ref_deltas[first - 1].sha1, sha1))\n+\t\t--first;\n+\twhile (last < end && !hashcmp(ref_deltas[last + 1].sha1, sha1))\n \t\t++last;\n \t*first_index = first;\n \t*last_index = last;\n@@ -927,16 +977,13 @@ static struct base_data *find_unresolved_deltas_1(struct base_data *base,\n \t\t\t\t\t\t  struct base_data *prev_base)\n {\n \tif (base->ref_last == -1 && base->ofs_last == -1) {\n-\t\tunion delta_base base_spec;\n-\n-\t\thashcpy(base_spec.sha1, base->obj->idx.sha1);\n-\t\tfind_delta_children(&base_spec,\n-\t\t\t\t    &base->ref_first, &base->ref_last, OBJ_REF_DELTA);\n+\t\tfind_ref_delta_children(base->obj->idx.sha1,\n+\t\t\t\t\t&base->ref_first, &base->ref_last,\n+\t\t\t\t\tOBJ_REF_DELTA);\n \n-\t\tmemset(&base_spec, 0, sizeof(base_spec));\n-\t\tbase_spec.offset = base->obj->idx.offset;\n-\t\tfind_delta_children(&base_spec,\n-\t\t\t\t    &base->ofs_first, &base->ofs_last, OBJ_OFS_DELTA);\n+\t\tfind_ofs_delta_children(base->obj->idx.offset,\n+\t\t\t\t\t&base->ofs_first, &base->ofs_last,\n+\t\t\t\t\tOBJ_OFS_DELTA);\n \n \t\tif (base->ref_last == -1 && base->ofs_last == -1) {\n \t\t\tfree(base->data);\n@@ -947,7 +994,7 @@ static struct base_data *find_unresolved_deltas_1(struct base_data *base,\n \t}\n \n \tif (base->ref_first <= base->ref_last) {\n-\t\tstruct object_entry *child = objects + deltas[base->ref_first].obj_no;\n+\t\tstruct object_entry *child = objects + ref_deltas[base->ref_first].obj_no;\n \t\tstruct base_data *result = alloc_base_data();\n \n \t\tif (!compare_and_swap_type(&child->real_type, OBJ_REF_DELTA,\n@@ -963,7 +1010,7 @@ static struct base_data *find_unresolved_deltas_1(struct base_data *base,\n \t}\n \n \tif (base->ofs_first <= base->ofs_last) {\n-\t\tstruct object_entry *child = objects + deltas[base->ofs_first].obj_no;\n+\t\tstruct object_entry *child = objects + ofs_deltas[base->ofs_first].obj_no;\n \t\tstruct base_data *result = alloc_base_data();\n \n \t\tassert(child->real_type == OBJ_OFS_DELTA);\n@@ -999,15 +1046,20 @@ static void find_unresolved_deltas(struct base_data *base)\n \t}\n }\n \n-static int compare_delta_entry(const void *a, const void *b)\n+static int compare_ofs_delta_entry(const void *a, const void *b)\n+{\n+\tconst struct ofs_delta_entry *delta_a = a;\n+\tconst struct ofs_delta_entry *delta_b = b;\n+\n+\treturn delta_a->offset - delta_b->offset;\n+}\n+\n+static int compare_ref_delta_entry(const void *a, const void *b)\n {\n-\tconst struct delta_entry *delta_a = a;\n-\tconst struct delta_entry *delta_b = b;\n+\tconst struct ref_delta_entry *delta_a = a;\n+\tconst struct ref_delta_entry *delta_b = b;\n \n-\t/* group by type (ref vs ofs) and then by value (sha-1 or offset) */\n-\treturn compare_delta_bases(&delta_a->base, &delta_b->base,\n-\t\t\t\t   objects[delta_a->obj_no].type,\n-\t\t\t\t   objects[delta_b->obj_no].type);\n+\treturn hashcmp(delta_a->sha1, delta_b->sha1);\n }\n \n static void resolve_base(struct object_entry *obj)\n@@ -1053,7 +1105,8 @@ static void *threaded_second_pass(void *data)\n static void parse_pack_objects(unsigned char *sha1)\n {\n \tint i, nr_delays = 0;\n-\tstruct delta_entry *delta = deltas;\n+\tstruct ofs_delta_entry *ofs_delta = ofs_deltas;\n+\tunsigned char ref_delta_sha1[20];\n \tstruct stat st;\n \n \tif (verbose)\n@@ -1062,12 +1115,18 @@ static void parse_pack_objects(unsigned char *sha1)\n \t\t\t\tnr_objects);\n \tfor (i = 0; i < nr_objects; i++) {\n \t\tstruct object_entry *obj = &objects[i];\n-\t\tvoid *data = unpack_raw_entry(obj, &delta->base, obj->idx.sha1);\n+\t\tvoid *data = unpack_raw_entry(obj, &ofs_delta->offset,\n+\t\t\t\t\t      ref_delta_sha1, obj->idx.sha1);\n \t\tobj->real_type = obj->type;\n-\t\tif (is_delta_type(obj->type)) {\n-\t\t\tnr_deltas++;\n-\t\t\tdelta->obj_no = i;\n-\t\t\tdelta++;\n+\t\tif (obj->type == OBJ_OFS_DELTA) {\n+\t\t\tnr_ofs_deltas++;\n+\t\t\tofs_delta->obj_no = i;\n+\t\t\tofs_delta++;\n+\t\t} else if (obj->type == OBJ_REF_DELTA) {\n+\t\t\tALLOC_GROW(ref_deltas, nr_ref_deltas + 1, ref_deltas_alloc);\n+\t\t\thashcpy(ref_deltas[nr_ref_deltas].sha1, ref_delta_sha1);\n+\t\t\tref_deltas[nr_ref_deltas].obj_no = i;\n+\t\t\tnr_ref_deltas++;\n \t\t} else if (!data) {\n \t\t\t/* large blobs, check later */\n \t\t\tobj->real_type = OBJ_BAD;\n@@ -1118,15 +1177,18 @@ static void resolve_deltas(void)\n {\n \tint i;\n \n-\tif (!nr_deltas)\n+\tif (!nr_ofs_deltas && !nr_ref_deltas)\n \t\treturn;\n \n \t/* Sort deltas by base SHA1/offset for fast searching */\n-\tqsort(deltas, nr_deltas, sizeof(struct delta_entry),\n-\t      compare_delta_entry);\n+\tqsort(ofs_deltas, nr_ofs_deltas, sizeof(struct ofs_delta_entry),\n+\t      compare_ofs_delta_entry);\n+\tqsort(ref_deltas, nr_ref_deltas, sizeof(struct ref_delta_entry),\n+\t      compare_ref_delta_entry);\n \n \tif (verbose)\n-\t\tprogress = start_progress(_(\"Resolving deltas\"), nr_deltas);\n+\t\tprogress = start_progress(_(\"Resolving deltas\"),\n+\t\t\t\t\t  nr_ref_deltas + nr_ofs_deltas);\n \n #ifndef NO_PTHREADS\n \tnr_dispatched = 0;\n@@ -1164,7 +1226,7 @@ static void resolve_deltas(void)\n static void fix_unresolved_deltas(struct sha1file *f, int nr_unresolved);\n static void conclude_pack(int fix_thin_pack, const char *curr_pack, unsigned char *pack_sha1)\n {\n-\tif (nr_deltas == nr_resolved_deltas) {\n+\tif (nr_ref_deltas + nr_ofs_deltas == nr_resolved_deltas) {\n \t\tstop_progress(&progress);\n \t\t/* Flush remaining pack final 20-byte SHA1. */\n \t\tflush();\n@@ -1175,7 +1237,7 @@ static void conclude_pack(int fix_thin_pack, const char *curr_pack, unsigned cha\n \t\tstruct sha1file *f;\n \t\tunsigned char read_sha1[20], tail_sha1[20];\n \t\tstruct strbuf msg = STRBUF_INIT;\n-\t\tint nr_unresolved = nr_deltas - nr_resolved_deltas;\n+\t\tint nr_unresolved = nr_ofs_deltas + nr_ref_deltas - nr_resolved_deltas;\n \t\tint nr_objects_initial = nr_objects;\n \t\tif (nr_unresolved <= 0)\n \t\t\tdie(_(\"confusion beyond insanity\"));\n@@ -1197,11 +1259,11 @@ static void conclude_pack(int fix_thin_pack, const char *curr_pack, unsigned cha\n \t\t\tdie(_(\"Unexpected tail checksum for %s \"\n \t\t\t      \"(disk corruption?)\"), curr_pack);\n \t}\n-\tif (nr_deltas != nr_resolved_deltas)\n+\tif (nr_ofs_deltas + nr_ref_deltas != nr_resolved_deltas)\n \t\tdie(Q_(\"pack has %d unresolved delta\",\n \t\t       \"pack has %d unresolved deltas\",\n-\t\t       nr_deltas - nr_resolved_deltas),\n-\t\t    nr_deltas - nr_resolved_deltas);\n+\t\t       nr_ofs_deltas + nr_ref_deltas - nr_resolved_deltas),\n+\t\t    nr_ofs_deltas + nr_ref_deltas - nr_resolved_deltas);\n }\n \n static int write_compressed(struct sha1file *f, void *in, unsigned int size)\n@@ -1261,14 +1323,14 @@ static struct object_entry *append_obj_to_pack(struct sha1file *f,\n \n static int delta_pos_compare(const void *_a, const void *_b)\n {\n-\tstruct delta_entry *a = *(struct delta_entry **)_a;\n-\tstruct delta_entry *b = *(struct delta_entry **)_b;\n+\tstruct ref_delta_entry *a = *(struct ref_delta_entry **)_a;\n+\tstruct ref_delta_entry *b = *(struct ref_delta_entry **)_b;\n \treturn a->obj_no - b->obj_no;\n }\n \n static void fix_unresolved_deltas(struct sha1file *f, int nr_unresolved)\n {\n-\tstruct delta_entry **sorted_by_pos;\n+\tstruct ref_delta_entry **sorted_by_pos;\n \tint i, n = 0;\n \n \t/*\n@@ -1282,28 +1344,25 @@ static void fix_unresolved_deltas(struct sha1file *f, int nr_unresolved)\n \t * resolving deltas in the same order as their position in the pack.\n \t */\n \tsorted_by_pos = xmalloc(nr_unresolved * sizeof(*sorted_by_pos));\n-\tfor (i = 0; i < nr_deltas; i++) {\n-\t\tif (objects[deltas[i].obj_no].real_type != OBJ_REF_DELTA)\n-\t\t\tcontinue;\n-\t\tsorted_by_pos[n++] = &deltas[i];\n-\t}\n+\tfor (i = 0; i < nr_ref_deltas; i++)\n+\t\tsorted_by_pos[n++] = &ref_deltas[i];\n \tqsort(sorted_by_pos, n, sizeof(*sorted_by_pos), delta_pos_compare);\n \n \tfor (i = 0; i < n; i++) {\n-\t\tstruct delta_entry *d = sorted_by_pos[i];\n+\t\tstruct ref_delta_entry *d = sorted_by_pos[i];\n \t\tenum object_type type;\n \t\tstruct base_data *base_obj = alloc_base_data();\n \n \t\tif (objects[d->obj_no].real_type != OBJ_REF_DELTA)\n \t\t\tcontinue;\n-\t\tbase_obj->data = read_sha1_file(d->base.sha1, &type, &base_obj->size);\n+\t\tbase_obj->data = read_sha1_file(d->sha1, &type, &base_obj->size);\n \t\tif (!base_obj->data)\n \t\t\tcontinue;\n \n-\t\tif (check_sha1_signature(d->base.sha1, base_obj->data,\n+\t\tif (check_sha1_signature(d->sha1, base_obj->data,\n \t\t\t\tbase_obj->size, typename(type)))\n-\t\t\tdie(_(\"local object %s is corrupt\"), sha1_to_hex(d->base.sha1));\n-\t\tbase_obj->obj = append_obj_to_pack(f, d->base.sha1,\n+\t\t\tdie(_(\"local object %s is corrupt\"), sha1_to_hex(d->sha1));\n+\t\tbase_obj->obj = append_obj_to_pack(f, d->sha1,\n \t\t\t\t\tbase_obj->data, base_obj->size, type);\n \t\tfind_unresolved_deltas(base_obj);\n \t\tdisplay_progress(progress, nr_resolved_deltas);\n@@ -1495,7 +1554,7 @@ static void read_idx_option(struct pack_idx_option *opts, const char *pack_name)\n \n static void show_pack_info(int stat_only)\n {\n-\tint i, baseobjects = nr_objects - nr_deltas;\n+\tint i, baseobjects = nr_objects - nr_ref_deltas - nr_ofs_deltas;\n \tunsigned long *chain_histogram = NULL;\n \n \tif (deepest_delta)\n@@ -1680,11 +1739,12 @@ int cmd_index_pack(int argc, const char **argv, const char *prefix)\n \tobjects = xcalloc(nr_objects + 1, sizeof(struct object_entry));\n \tif (show_stat)\n \t\tobj_stat = xcalloc(nr_objects + 1, sizeof(struct object_stat));\n-\tdeltas = xcalloc(nr_objects, sizeof(struct delta_entry));\n+\tofs_deltas = xcalloc(nr_objects, sizeof(struct ofs_delta_entry));\n \tparse_pack_objects(pack_sha1);\n \tresolve_deltas();\n \tconclude_pack(fix_thin_pack, curr_pack, pack_sha1);\n-\tfree(deltas);\n+\tfree(ofs_deltas);\n+\tfree(ref_deltas);\n \tif (strict)\n \t\tforeign_nr = check_objects();\n \n-- \n2.3.0.rc1.137.g477eb31\n"},{"id":"256493","messageId":"xmqqegphuze8.fsf@gitster.dls.corp.google.com","threadId":"38607","inReplyTo":"1424397488-22169-2-git-send-email-pclouds@gmail.com","subject":"Re: [PATCH 1/2] index-pack: reduce object_entry size to save memory","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2015-02-23T02:37:03Z","receivedAt":"2015-02-23T02:37:03Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nguyễn Thái Ngọc Duy  <pclouds@gmail.com> writes:\n\n> diff --git a/builtin/index-pack.c b/builtin/index-pack.c\n> index 4632117..07b2c0c 100644\n> --- a/builtin/index-pack.c\n> +++ b/builtin/index-pack.c\n> @@ -18,9 +18,12 @@ static const char index_pack_usage[] =\n>  struct object_entry {\n>  \tstruct pack_idx_entry idx;\n>  \tunsigned long size;\n> -\tunsigned int hdr_size;\n> -\tenum object_type type;\n> -\tenum object_type real_type;\n> +\tunsigned char hdr_size;\n> +\tchar type;\n> +\tchar real_type;\n\nDon't you need these two fields to be able to hold a negative value\nlike OBJ_BAD (= -1)?  You'd need to spell \"signed char\" out here.\n"},{"id":"256495","messageId":"CACsJy8CGQAx9KVHF_yGHh+zi6xirtP7ZxTb3-2NafGkmjQkcGA@mail.gmail.com","threadId":"38607","inReplyTo":"xmqqegphuze8.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH 1/2] index-pack: reduce object_entry size to save memory","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2015-02-23T03:38:30Z","receivedAt":"2015-02-23T03:38:30Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Mon, Feb 23, 2015 at 9:37 AM, Junio C Hamano <gitster@pobox.com> wrote:\n> Nguyễn Thái Ngọc Duy  <pclouds@gmail.com> writes:\n>\n>> diff --git a/builtin/index-pack.c b/builtin/index-pack.c\n>> index 4632117..07b2c0c 100644\n>> --- a/builtin/index-pack.c\n>> +++ b/builtin/index-pack.c\n>> @@ -18,9 +18,12 @@ static const char index_pack_usage[] =\n>>  struct object_entry {\n>>       struct pack_idx_entry idx;\n>>       unsigned long size;\n>> -     unsigned int hdr_size;\n>> -     enum object_type type;\n>> -     enum object_type real_type;\n>> +     unsigned char hdr_size;\n>> +     char type;\n>> +     char real_type;\n>\n> Don't you need these two fields to be able to hold a negative value\n> like OBJ_BAD (= -1)?  You'd need to spell \"signed char\" out here.\n\nRight. char's signedness is undefined. Can't believe I hit this on ARM\nnot 2 months ago and already forgot the lesson. Will fix.\n-- \nDuy\n"},{"id":"256675","messageId":"1424947928-19396-1-git-send-email-pclouds@gmail.com","threadId":"38607","inReplyTo":"1424397488-22169-1-git-send-email-pclouds@gmail.com","subject":"[PATCH v2 0/2] nd/slim-index-pack-memory-usage updates","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2015-02-26T10:52:06Z","receivedAt":"2015-02-26T10:52:06Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"This fixes the \"signed char\" bug in 1/2: \"char\" alone could be either\nsigned or unsigned but we do need signed char.\n\nOne point to clang for detecting \"obj->real_type != OBJ_BAD\" on ARM\nwhere real_type becomes unsigned char and OBJ_BAD is -1. gcc just\nkeeps quiet..\n\nNguyễn Thái Ngọc Duy (2):\n  index-pack: reduce object_entry size to save memory\n  index-pack: kill union delta_base to save memory\n\n builtin/index-pack.c | 290 +++++++++++++++++++++++++++++++--------------------\n 1 file changed, 179 insertions(+), 111 deletions(-)\n\n-- \n2.3.0.rc1.137.g477eb31\n"},{"id":"256676","messageId":"1424947928-19396-2-git-send-email-pclouds@gmail.com","threadId":"38607","inReplyTo":"1424947928-19396-1-git-send-email-pclouds@gmail.com","subject":"[PATCH v2 1/2] index-pack: reduce object_entry size to save memory","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2015-02-26T10:52:07Z","receivedAt":"2015-02-26T10:52:07Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"For each object in the input pack, we need one struct object_entry. On\nx86-64, this struct is 64 bytes long. Although:\n\n - The 8 bytes for delta_depth and base_object_no are only useful when\n   show_stat is set. And it's never set unless someone is debugging.\n\n - The three fields hdr_size, type and real_type take 4 bytes each\n   even though they never use more than 4 bits.\n\nBy moving delta_depth and base_object_no out of struct object_entry\nand make the other 3 fields one byte long instead of 4, we shrink 25%\nof this struct.\n\nOn a 3.4M object repo (*) that's about 53MB. The saving is less\nimpressive compared to index-pack memory use for basic bookkeeping (**),\nabout 16%.\n\n(*) linux-2.6.git already has 4M objects as of v3.19-rc7 so this is\nnot an unrealistic number of objects that we have to deal with.\n\n(**)  3.4M * (sizeof(object_entry) + sizeof(delta_entry)) = 311MB\n\nBrought-up-by: Matthew Sporleder <msporleder@gmail.com>\nSigned-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>\n---\n builtin/index-pack.c | 30 +++++++++++++++++++-----------\n 1 file changed, 19 insertions(+), 11 deletions(-)\n\ndiff --git a/builtin/index-pack.c b/builtin/index-pack.c\nindex 4632117..9d854fb 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -18,9 +18,12 @@ static const char index_pack_usage[] =\n struct object_entry {\n \tstruct pack_idx_entry idx;\n \tunsigned long size;\n-\tunsigned int hdr_size;\n-\tenum object_type type;\n-\tenum object_type real_type;\n+\tunsigned char hdr_size;\n+\tsigned char type;\n+\tsigned char real_type;\n+};\n+\n+struct object_stat {\n \tunsigned delta_depth;\n \tint base_object_no;\n };\n@@ -64,6 +67,7 @@ struct delta_entry {\n };\n \n static struct object_entry *objects;\n+static struct object_stat *obj_stat;\n static struct delta_entry *deltas;\n static struct thread_local nothread_data;\n static int nr_objects;\n@@ -873,13 +877,15 @@ static void resolve_delta(struct object_entry *delta_obj,\n \tvoid *base_data, *delta_data;\n \n \tif (show_stat) {\n-\t\tdelta_obj->delta_depth = base->obj->delta_depth + 1;\n+\t\tint i = delta_obj - objects;\n+\t\tint j = base->obj - objects;\n+\t\tobj_stat[i].delta_depth = obj_stat[j].delta_depth + 1;\n \t\tdeepest_delta_lock();\n-\t\tif (deepest_delta < delta_obj->delta_depth)\n-\t\t\tdeepest_delta = delta_obj->delta_depth;\n+\t\tif (deepest_delta < obj_stat[i].delta_depth)\n+\t\t\tdeepest_delta = obj_stat[i].delta_depth;\n \t\tdeepest_delta_unlock();\n+\t\tobj_stat[i].base_object_no = j;\n \t}\n-\tdelta_obj->base_object_no = base->obj - objects;\n \tdelta_data = get_data_from_pack(delta_obj);\n \tbase_data = get_base_data(base);\n \tresult->obj = delta_obj;\n@@ -902,7 +908,7 @@ static void resolve_delta(struct object_entry *delta_obj,\n  * \"want\"; if so, swap in \"set\" and return true. Otherwise, leave it untouched\n  * and return false.\n  */\n-static int compare_and_swap_type(enum object_type *type,\n+static int compare_and_swap_type(signed char *type,\n \t\t\t\t enum object_type want,\n \t\t\t\t enum object_type set)\n {\n@@ -1499,7 +1505,7 @@ static void show_pack_info(int stat_only)\n \t\tstruct object_entry *obj = &objects[i];\n \n \t\tif (is_delta_type(obj->type))\n-\t\t\tchain_histogram[obj->delta_depth - 1]++;\n+\t\t\tchain_histogram[obj_stat[i].delta_depth - 1]++;\n \t\tif (stat_only)\n \t\t\tcontinue;\n \t\tprintf(\"%s %-6s %lu %lu %\"PRIuMAX,\n@@ -1508,8 +1514,8 @@ static void show_pack_info(int stat_only)\n \t\t       (unsigned long)(obj[1].idx.offset - obj->idx.offset),\n \t\t       (uintmax_t)obj->idx.offset);\n \t\tif (is_delta_type(obj->type)) {\n-\t\t\tstruct object_entry *bobj = &objects[obj->base_object_no];\n-\t\t\tprintf(\" %u %s\", obj->delta_depth, sha1_to_hex(bobj->idx.sha1));\n+\t\t\tstruct object_entry *bobj = &objects[obj_stat[i].base_object_no];\n+\t\t\tprintf(\" %u %s\", obj_stat[i].delta_depth, sha1_to_hex(bobj->idx.sha1));\n \t\t}\n \t\tputchar('\\n');\n \t}\n@@ -1672,6 +1678,8 @@ int cmd_index_pack(int argc, const char **argv, const char *prefix)\n \tcurr_pack = open_pack_file(pack_name);\n \tparse_pack_header();\n \tobjects = xcalloc(nr_objects + 1, sizeof(struct object_entry));\n+\tif (show_stat)\n+\t\tobj_stat = xcalloc(nr_objects + 1, sizeof(struct object_stat));\n \tdeltas = xcalloc(nr_objects, sizeof(struct delta_entry));\n \tparse_pack_objects(pack_sha1);\n \tresolve_deltas();\n-- \n2.3.0.rc1.137.g477eb31\n"},{"id":"256677","messageId":"1424947928-19396-3-git-send-email-pclouds@gmail.com","threadId":"38607","inReplyTo":"1424947928-19396-1-git-send-email-pclouds@gmail.com","subject":"[PATCH v2 2/2] index-pack: kill union delta_base to save memory","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2015-02-26T10:52:08Z","receivedAt":"2015-02-26T10:52:08Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"Once we know the number of objects in the input pack, we allocate an\narray of nr_objects of struct delta_entry. On x86-64, this struct is\n32 bytes long. The union delta_base, which is part of struct\ndelta_entry, provides enough space to store either ofs-delta (8 bytes)\nor ref-delta (20 bytes).\n\nNotice that with \"recent\" Git versions, ofs-delta objects are\npreferred over ref-delta objects and ref-delta objects have no reason\nto be present in a clone pack. So in clone case we waste (20-8) *\nnr_objects bytes because of this union. That's about 38MB out of 100MB\nfor deltas[] with 3.4M objects, or 38%. deltas[] would be around 62MB\nwithout the waste.\n\nThis patch attempts to eliminate that. deltas[] array is split into\ntwo: one for ofs-delta and one for ref-delta. Many functions are also\nduplicated because of this split. With this patch, ofs_deltas[] array\ntakes 51MB. ref_deltas[] should remain unallocated in clone case (0\nbytes). This array grows as we see ref-delta. We save about half in\nclone case, or 25% of total bookkeeping.\n\nThe saving is more than the calculation above because some padding in\nthe old delta_entry struct is removed. ofs_delta_entry is 16 bytes,\nincluding the 4 bytes padding. That's 13MB for padding, but packing\nthe struct could break platforms that do not support unaligned\naccess. If someone on 32-bit is really low on memory and only deals\nwith packs smaller than 2G, using 32-bit off_t would eliminate the\npadding and save 27MB on top.\n\nA note about ofs_deltas allocation. We could use ref_deltas memory\nallocation strategy for ofs_deltas. But that probably just adds more\noverhead on top. ofs-deltas are generally the majority (1/2 to 2/3) in\nany pack. Incremental realloc may lead to too many memcpy. And if we\npreallocate, say 1/2 or 2/3 of nr_objects initially, the growth rate\nof ALLOC_GROW() could make this array larger than nr_objects, wasting\nmore memory.\n\nBrought-up-by: Matthew Sporleder <msporleder@gmail.com>\nSigned-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>\n---\n builtin/index-pack.c | 260 +++++++++++++++++++++++++++++++--------------------\n 1 file changed, 160 insertions(+), 100 deletions(-)\n\ndiff --git a/builtin/index-pack.c b/builtin/index-pack.c\nindex 9d854fb..3ed53e3 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -28,11 +28,6 @@ struct object_stat {\n \tint base_object_no;\n };\n \n-union delta_base {\n-\tunsigned char sha1[20];\n-\toff_t offset;\n-};\n-\n struct base_data {\n \tstruct base_data *base;\n \tstruct base_data *child;\n@@ -52,26 +47,28 @@ struct thread_local {\n \tint pack_fd;\n };\n \n-/*\n- * Even if sizeof(union delta_base) == 24 on 64-bit archs, we really want\n- * to memcmp() only the first 20 bytes.\n- */\n-#define UNION_BASE_SZ\t20\n-\n #define FLAG_LINK (1u<<20)\n #define FLAG_CHECKED (1u<<21)\n \n-struct delta_entry {\n-\tunion delta_base base;\n+struct ofs_delta_entry {\n+\toff_t offset;\n+\tint obj_no;\n+};\n+\n+struct ref_delta_entry {\n+\tunsigned char sha1[20];\n \tint obj_no;\n };\n \n static struct object_entry *objects;\n static struct object_stat *obj_stat;\n-static struct delta_entry *deltas;\n+static struct ofs_delta_entry *ofs_deltas;\n+static struct ref_delta_entry *ref_deltas;\n static struct thread_local nothread_data;\n static int nr_objects;\n-static int nr_deltas;\n+static int nr_ofs_deltas;\n+static int nr_ref_deltas;\n+static int ref_deltas_alloc;\n static int nr_resolved_deltas;\n static int nr_threads;\n \n@@ -480,7 +477,8 @@ static void *unpack_entry_data(unsigned long offset, unsigned long size,\n }\n \n static void *unpack_raw_entry(struct object_entry *obj,\n-\t\t\t      union delta_base *delta_base,\n+\t\t\t      off_t *ofs_offset,\n+\t\t\t      unsigned char *ref_sha1,\n \t\t\t      unsigned char *sha1)\n {\n \tunsigned char *p;\n@@ -509,11 +507,10 @@ static void *unpack_raw_entry(struct object_entry *obj,\n \n \tswitch (obj->type) {\n \tcase OBJ_REF_DELTA:\n-\t\thashcpy(delta_base->sha1, fill(20));\n+\t\thashcpy(ref_sha1, fill(20));\n \t\tuse(20);\n \t\tbreak;\n \tcase OBJ_OFS_DELTA:\n-\t\tmemset(delta_base, 0, sizeof(*delta_base));\n \t\tp = fill(1);\n \t\tc = *p;\n \t\tuse(1);\n@@ -527,8 +524,8 @@ static void *unpack_raw_entry(struct object_entry *obj,\n \t\t\tuse(1);\n \t\t\tbase_offset = (base_offset << 7) + (c & 127);\n \t\t}\n-\t\tdelta_base->offset = obj->idx.offset - base_offset;\n-\t\tif (delta_base->offset <= 0 || delta_base->offset >= obj->idx.offset)\n+\t\t*ofs_offset = obj->idx.offset - base_offset;\n+\t\tif (*ofs_offset <= 0 || *ofs_offset >= obj->idx.offset)\n \t\t\tbad_object(obj->idx.offset, _(\"delta base offset is out of bound\"));\n \t\tbreak;\n \tcase OBJ_COMMIT:\n@@ -612,55 +609,108 @@ static void *get_data_from_pack(struct object_entry *obj)\n \treturn unpack_data(obj, NULL, NULL);\n }\n \n-static int compare_delta_bases(const union delta_base *base1,\n-\t\t\t       const union delta_base *base2,\n-\t\t\t       enum object_type type1,\n-\t\t\t       enum object_type type2)\n+static int compare_ofs_delta_bases(off_t offset1, off_t offset2,\n+\t\t\t\t   enum object_type type1,\n+\t\t\t\t   enum object_type type2)\n {\n \tint cmp = type1 - type2;\n \tif (cmp)\n \t\treturn cmp;\n-\treturn memcmp(base1, base2, UNION_BASE_SZ);\n+\treturn offset1 - offset2;\n }\n \n-static int find_delta(const union delta_base *base, enum object_type type)\n+static int find_ofs_delta(const off_t offset, enum object_type type)\n {\n-\tint first = 0, last = nr_deltas;\n-\n-        while (first < last) {\n-                int next = (first + last) / 2;\n-                struct delta_entry *delta = &deltas[next];\n-                int cmp;\n-\n-\t\tcmp = compare_delta_bases(base, &delta->base,\n-\t\t\t\t\t  type, objects[delta->obj_no].type);\n-                if (!cmp)\n-                        return next;\n-                if (cmp < 0) {\n-                        last = next;\n-                        continue;\n-                }\n-                first = next+1;\n-        }\n-        return -first-1;\n+\tint first = 0, last = nr_ofs_deltas;\n+\n+\twhile (first < last) {\n+\t\tint next = (first + last) / 2;\n+\t\tstruct ofs_delta_entry *delta = &ofs_deltas[next];\n+\t\tint cmp;\n+\n+\t\tcmp = compare_ofs_delta_bases(offset, delta->offset,\n+\t\t\t\t\t      type, objects[delta->obj_no].type);\n+\t\tif (!cmp)\n+\t\t\treturn next;\n+\t\tif (cmp < 0) {\n+\t\t\tlast = next;\n+\t\t\tcontinue;\n+\t\t}\n+\t\tfirst = next+1;\n+\t}\n+\treturn -first-1;\n }\n \n-static void find_delta_children(const union delta_base *base,\n-\t\t\t\tint *first_index, int *last_index,\n-\t\t\t\tenum object_type type)\n+static void find_ofs_delta_children(off_t offset,\n+\t\t\t\t    int *first_index, int *last_index,\n+\t\t\t\t    enum object_type type)\n {\n-\tint first = find_delta(base, type);\n+\tint first = find_ofs_delta(offset, type);\n \tint last = first;\n-\tint end = nr_deltas - 1;\n+\tint end = nr_ofs_deltas - 1;\n \n \tif (first < 0) {\n \t\t*first_index = 0;\n \t\t*last_index = -1;\n \t\treturn;\n \t}\n-\twhile (first > 0 && !memcmp(&deltas[first - 1].base, base, UNION_BASE_SZ))\n+\twhile (first > 0 && ofs_deltas[first - 1].offset == offset)\n \t\t--first;\n-\twhile (last < end && !memcmp(&deltas[last + 1].base, base, UNION_BASE_SZ))\n+\twhile (last < end && ofs_deltas[last + 1].offset == offset)\n+\t\t++last;\n+\t*first_index = first;\n+\t*last_index = last;\n+}\n+\n+static int compare_ref_delta_bases(const unsigned char *sha1,\n+\t\t\t\t   const unsigned char *sha2,\n+\t\t\t\t   enum object_type type1,\n+\t\t\t\t   enum object_type type2)\n+{\n+\tint cmp = type1 - type2;\n+\tif (cmp)\n+\t\treturn cmp;\n+\treturn hashcmp(sha1, sha2);\n+}\n+\n+static int find_ref_delta(const unsigned char *sha1, enum object_type type)\n+{\n+\tint first = 0, last = nr_ref_deltas;\n+\n+\twhile (first < last) {\n+\t\tint next = (first + last) / 2;\n+\t\tstruct ref_delta_entry *delta = &ref_deltas[next];\n+\t\tint cmp;\n+\n+\t\tcmp = compare_ref_delta_bases(sha1, delta->sha1,\n+\t\t\t\t\t      type, objects[delta->obj_no].type);\n+\t\tif (!cmp)\n+\t\t\treturn next;\n+\t\tif (cmp < 0) {\n+\t\t\tlast = next;\n+\t\t\tcontinue;\n+\t\t}\n+\t\tfirst = next+1;\n+\t}\n+\treturn -first-1;\n+}\n+\n+static void find_ref_delta_children(const unsigned char *sha1,\n+\t\t\t\t    int *first_index, int *last_index,\n+\t\t\t\t    enum object_type type)\n+{\n+\tint first = find_ref_delta(sha1, type);\n+\tint last = first;\n+\tint end = nr_ref_deltas - 1;\n+\n+\tif (first < 0) {\n+\t\t*first_index = 0;\n+\t\t*last_index = -1;\n+\t\treturn;\n+\t}\n+\twhile (first > 0 && !hashcmp(ref_deltas[first - 1].sha1, sha1))\n+\t\t--first;\n+\twhile (last < end && !hashcmp(ref_deltas[last + 1].sha1, sha1))\n \t\t++last;\n \t*first_index = first;\n \t*last_index = last;\n@@ -927,16 +977,13 @@ static struct base_data *find_unresolved_deltas_1(struct base_data *base,\n \t\t\t\t\t\t  struct base_data *prev_base)\n {\n \tif (base->ref_last == -1 && base->ofs_last == -1) {\n-\t\tunion delta_base base_spec;\n-\n-\t\thashcpy(base_spec.sha1, base->obj->idx.sha1);\n-\t\tfind_delta_children(&base_spec,\n-\t\t\t\t    &base->ref_first, &base->ref_last, OBJ_REF_DELTA);\n+\t\tfind_ref_delta_children(base->obj->idx.sha1,\n+\t\t\t\t\t&base->ref_first, &base->ref_last,\n+\t\t\t\t\tOBJ_REF_DELTA);\n \n-\t\tmemset(&base_spec, 0, sizeof(base_spec));\n-\t\tbase_spec.offset = base->obj->idx.offset;\n-\t\tfind_delta_children(&base_spec,\n-\t\t\t\t    &base->ofs_first, &base->ofs_last, OBJ_OFS_DELTA);\n+\t\tfind_ofs_delta_children(base->obj->idx.offset,\n+\t\t\t\t\t&base->ofs_first, &base->ofs_last,\n+\t\t\t\t\tOBJ_OFS_DELTA);\n \n \t\tif (base->ref_last == -1 && base->ofs_last == -1) {\n \t\t\tfree(base->data);\n@@ -947,7 +994,7 @@ static struct base_data *find_unresolved_deltas_1(struct base_data *base,\n \t}\n \n \tif (base->ref_first <= base->ref_last) {\n-\t\tstruct object_entry *child = objects + deltas[base->ref_first].obj_no;\n+\t\tstruct object_entry *child = objects + ref_deltas[base->ref_first].obj_no;\n \t\tstruct base_data *result = alloc_base_data();\n \n \t\tif (!compare_and_swap_type(&child->real_type, OBJ_REF_DELTA,\n@@ -963,7 +1010,7 @@ static struct base_data *find_unresolved_deltas_1(struct base_data *base,\n \t}\n \n \tif (base->ofs_first <= base->ofs_last) {\n-\t\tstruct object_entry *child = objects + deltas[base->ofs_first].obj_no;\n+\t\tstruct object_entry *child = objects + ofs_deltas[base->ofs_first].obj_no;\n \t\tstruct base_data *result = alloc_base_data();\n \n \t\tassert(child->real_type == OBJ_OFS_DELTA);\n@@ -999,15 +1046,20 @@ static void find_unresolved_deltas(struct base_data *base)\n \t}\n }\n \n-static int compare_delta_entry(const void *a, const void *b)\n+static int compare_ofs_delta_entry(const void *a, const void *b)\n+{\n+\tconst struct ofs_delta_entry *delta_a = a;\n+\tconst struct ofs_delta_entry *delta_b = b;\n+\n+\treturn delta_a->offset - delta_b->offset;\n+}\n+\n+static int compare_ref_delta_entry(const void *a, const void *b)\n {\n-\tconst struct delta_entry *delta_a = a;\n-\tconst struct delta_entry *delta_b = b;\n+\tconst struct ref_delta_entry *delta_a = a;\n+\tconst struct ref_delta_entry *delta_b = b;\n \n-\t/* group by type (ref vs ofs) and then by value (sha-1 or offset) */\n-\treturn compare_delta_bases(&delta_a->base, &delta_b->base,\n-\t\t\t\t   objects[delta_a->obj_no].type,\n-\t\t\t\t   objects[delta_b->obj_no].type);\n+\treturn hashcmp(delta_a->sha1, delta_b->sha1);\n }\n \n static void resolve_base(struct object_entry *obj)\n@@ -1053,7 +1105,8 @@ static void *threaded_second_pass(void *data)\n static void parse_pack_objects(unsigned char *sha1)\n {\n \tint i, nr_delays = 0;\n-\tstruct delta_entry *delta = deltas;\n+\tstruct ofs_delta_entry *ofs_delta = ofs_deltas;\n+\tunsigned char ref_delta_sha1[20];\n \tstruct stat st;\n \n \tif (verbose)\n@@ -1062,12 +1115,18 @@ static void parse_pack_objects(unsigned char *sha1)\n \t\t\t\tnr_objects);\n \tfor (i = 0; i < nr_objects; i++) {\n \t\tstruct object_entry *obj = &objects[i];\n-\t\tvoid *data = unpack_raw_entry(obj, &delta->base, obj->idx.sha1);\n+\t\tvoid *data = unpack_raw_entry(obj, &ofs_delta->offset,\n+\t\t\t\t\t      ref_delta_sha1, obj->idx.sha1);\n \t\tobj->real_type = obj->type;\n-\t\tif (is_delta_type(obj->type)) {\n-\t\t\tnr_deltas++;\n-\t\t\tdelta->obj_no = i;\n-\t\t\tdelta++;\n+\t\tif (obj->type == OBJ_OFS_DELTA) {\n+\t\t\tnr_ofs_deltas++;\n+\t\t\tofs_delta->obj_no = i;\n+\t\t\tofs_delta++;\n+\t\t} else if (obj->type == OBJ_REF_DELTA) {\n+\t\t\tALLOC_GROW(ref_deltas, nr_ref_deltas + 1, ref_deltas_alloc);\n+\t\t\thashcpy(ref_deltas[nr_ref_deltas].sha1, ref_delta_sha1);\n+\t\t\tref_deltas[nr_ref_deltas].obj_no = i;\n+\t\t\tnr_ref_deltas++;\n \t\t} else if (!data) {\n \t\t\t/* large blobs, check later */\n \t\t\tobj->real_type = OBJ_BAD;\n@@ -1118,15 +1177,18 @@ static void resolve_deltas(void)\n {\n \tint i;\n \n-\tif (!nr_deltas)\n+\tif (!nr_ofs_deltas && !nr_ref_deltas)\n \t\treturn;\n \n \t/* Sort deltas by base SHA1/offset for fast searching */\n-\tqsort(deltas, nr_deltas, sizeof(struct delta_entry),\n-\t      compare_delta_entry);\n+\tqsort(ofs_deltas, nr_ofs_deltas, sizeof(struct ofs_delta_entry),\n+\t      compare_ofs_delta_entry);\n+\tqsort(ref_deltas, nr_ref_deltas, sizeof(struct ref_delta_entry),\n+\t      compare_ref_delta_entry);\n \n \tif (verbose)\n-\t\tprogress = start_progress(_(\"Resolving deltas\"), nr_deltas);\n+\t\tprogress = start_progress(_(\"Resolving deltas\"),\n+\t\t\t\t\t  nr_ref_deltas + nr_ofs_deltas);\n \n #ifndef NO_PTHREADS\n \tnr_dispatched = 0;\n@@ -1164,7 +1226,7 @@ static void resolve_deltas(void)\n static void fix_unresolved_deltas(struct sha1file *f, int nr_unresolved);\n static void conclude_pack(int fix_thin_pack, const char *curr_pack, unsigned char *pack_sha1)\n {\n-\tif (nr_deltas == nr_resolved_deltas) {\n+\tif (nr_ref_deltas + nr_ofs_deltas == nr_resolved_deltas) {\n \t\tstop_progress(&progress);\n \t\t/* Flush remaining pack final 20-byte SHA1. */\n \t\tflush();\n@@ -1175,7 +1237,7 @@ static void conclude_pack(int fix_thin_pack, const char *curr_pack, unsigned cha\n \t\tstruct sha1file *f;\n \t\tunsigned char read_sha1[20], tail_sha1[20];\n \t\tstruct strbuf msg = STRBUF_INIT;\n-\t\tint nr_unresolved = nr_deltas - nr_resolved_deltas;\n+\t\tint nr_unresolved = nr_ofs_deltas + nr_ref_deltas - nr_resolved_deltas;\n \t\tint nr_objects_initial = nr_objects;\n \t\tif (nr_unresolved <= 0)\n \t\t\tdie(_(\"confusion beyond insanity\"));\n@@ -1197,11 +1259,11 @@ static void conclude_pack(int fix_thin_pack, const char *curr_pack, unsigned cha\n \t\t\tdie(_(\"Unexpected tail checksum for %s \"\n \t\t\t      \"(disk corruption?)\"), curr_pack);\n \t}\n-\tif (nr_deltas != nr_resolved_deltas)\n+\tif (nr_ofs_deltas + nr_ref_deltas != nr_resolved_deltas)\n \t\tdie(Q_(\"pack has %d unresolved delta\",\n \t\t       \"pack has %d unresolved deltas\",\n-\t\t       nr_deltas - nr_resolved_deltas),\n-\t\t    nr_deltas - nr_resolved_deltas);\n+\t\t       nr_ofs_deltas + nr_ref_deltas - nr_resolved_deltas),\n+\t\t    nr_ofs_deltas + nr_ref_deltas - nr_resolved_deltas);\n }\n \n static int write_compressed(struct sha1file *f, void *in, unsigned int size)\n@@ -1261,14 +1323,14 @@ static struct object_entry *append_obj_to_pack(struct sha1file *f,\n \n static int delta_pos_compare(const void *_a, const void *_b)\n {\n-\tstruct delta_entry *a = *(struct delta_entry **)_a;\n-\tstruct delta_entry *b = *(struct delta_entry **)_b;\n+\tstruct ref_delta_entry *a = *(struct ref_delta_entry **)_a;\n+\tstruct ref_delta_entry *b = *(struct ref_delta_entry **)_b;\n \treturn a->obj_no - b->obj_no;\n }\n \n static void fix_unresolved_deltas(struct sha1file *f, int nr_unresolved)\n {\n-\tstruct delta_entry **sorted_by_pos;\n+\tstruct ref_delta_entry **sorted_by_pos;\n \tint i, n = 0;\n \n \t/*\n@@ -1282,28 +1344,25 @@ static void fix_unresolved_deltas(struct sha1file *f, int nr_unresolved)\n \t * resolving deltas in the same order as their position in the pack.\n \t */\n \tsorted_by_pos = xmalloc(nr_unresolved * sizeof(*sorted_by_pos));\n-\tfor (i = 0; i < nr_deltas; i++) {\n-\t\tif (objects[deltas[i].obj_no].real_type != OBJ_REF_DELTA)\n-\t\t\tcontinue;\n-\t\tsorted_by_pos[n++] = &deltas[i];\n-\t}\n+\tfor (i = 0; i < nr_ref_deltas; i++)\n+\t\tsorted_by_pos[n++] = &ref_deltas[i];\n \tqsort(sorted_by_pos, n, sizeof(*sorted_by_pos), delta_pos_compare);\n \n \tfor (i = 0; i < n; i++) {\n-\t\tstruct delta_entry *d = sorted_by_pos[i];\n+\t\tstruct ref_delta_entry *d = sorted_by_pos[i];\n \t\tenum object_type type;\n \t\tstruct base_data *base_obj = alloc_base_data();\n \n \t\tif (objects[d->obj_no].real_type != OBJ_REF_DELTA)\n \t\t\tcontinue;\n-\t\tbase_obj->data = read_sha1_file(d->base.sha1, &type, &base_obj->size);\n+\t\tbase_obj->data = read_sha1_file(d->sha1, &type, &base_obj->size);\n \t\tif (!base_obj->data)\n \t\t\tcontinue;\n \n-\t\tif (check_sha1_signature(d->base.sha1, base_obj->data,\n+\t\tif (check_sha1_signature(d->sha1, base_obj->data,\n \t\t\t\tbase_obj->size, typename(type)))\n-\t\t\tdie(_(\"local object %s is corrupt\"), sha1_to_hex(d->base.sha1));\n-\t\tbase_obj->obj = append_obj_to_pack(f, d->base.sha1,\n+\t\t\tdie(_(\"local object %s is corrupt\"), sha1_to_hex(d->sha1));\n+\t\tbase_obj->obj = append_obj_to_pack(f, d->sha1,\n \t\t\t\t\tbase_obj->data, base_obj->size, type);\n \t\tfind_unresolved_deltas(base_obj);\n \t\tdisplay_progress(progress, nr_resolved_deltas);\n@@ -1495,7 +1554,7 @@ static void read_idx_option(struct pack_idx_option *opts, const char *pack_name)\n \n static void show_pack_info(int stat_only)\n {\n-\tint i, baseobjects = nr_objects - nr_deltas;\n+\tint i, baseobjects = nr_objects - nr_ref_deltas - nr_ofs_deltas;\n \tunsigned long *chain_histogram = NULL;\n \n \tif (deepest_delta)\n@@ -1680,11 +1739,12 @@ int cmd_index_pack(int argc, const char **argv, const char *prefix)\n \tobjects = xcalloc(nr_objects + 1, sizeof(struct object_entry));\n \tif (show_stat)\n \t\tobj_stat = xcalloc(nr_objects + 1, sizeof(struct object_stat));\n-\tdeltas = xcalloc(nr_objects, sizeof(struct delta_entry));\n+\tofs_deltas = xcalloc(nr_objects, sizeof(struct ofs_delta_entry));\n \tparse_pack_objects(pack_sha1);\n \tresolve_deltas();\n \tconclude_pack(fix_thin_pack, curr_pack, pack_sha1);\n-\tfree(deltas);\n+\tfree(ofs_deltas);\n+\tfree(ref_deltas);\n \tif (strict)\n \t\tforeign_nr = check_objects();\n \n-- \n2.3.0.rc1.137.g477eb31\n"},{"id":"256753","messageId":"xmqqzj7zhx31.fsf@gitster.dls.corp.google.com","threadId":"38607","inReplyTo":"1424947928-19396-3-git-send-email-pclouds@gmail.com","subject":"Re: [PATCH v2 2/2] index-pack: kill union delta_base to save memory","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2015-02-27T21:18:58Z","receivedAt":"2015-02-27T21:18:58Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nguyễn Thái Ngọc Duy  <pclouds@gmail.com> writes:\n\n> Notice that with \"recent\" Git versions, ofs-delta objects are\n> preferred over ref-delta objects and ref-delta objects have no reason\n> to be present in a clone pack.\n\nIt is true that we try to use ofs-delta as much as possible, but\nwhere does \"have no reason to be present\" come from?\n\nWhen an object cannot be represented as an ofs-delta (which can only\nrefer backwards), don't we use ref-delta, instead of storing it as a\ndeflated-full object?\n\nProbably \"Not so ancient versions of Git tries to use ofs-delta\nencoding whenever possible, so it is expected that objects encoded\nusing ref-delta are minority\" may be closer to the truth.  And that\nobservation does justify why using two separate pools (one with\n8-byte entries for ofs-delta, the other with 20-byte entries for\nref-delta) is a better idean than using one pool with 20-byte\nentries for both kinds.\n"},{"id":"256774","messageId":"CACsJy8A3MxpQRwboVjyv7akvzgf3y23ZsnAaxuHXkm2U=tUk0A@mail.gmail.com","threadId":"38607","inReplyTo":"xmqqzj7zhx31.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH v2 2/2] index-pack: kill union delta_base to save memory","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2015-02-28T11:44:07Z","receivedAt":"2015-02-28T11:44:07Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Sat, Feb 28, 2015 at 4:18 AM, Junio C Hamano <gitster@pobox.com> wrote:\n> Nguyễn Thái Ngọc Duy  <pclouds@gmail.com> writes:\n>\n>> Notice that with \"recent\" Git versions, ofs-delta objects are\n>> preferred over ref-delta objects and ref-delta objects have no reason\n>> to be present in a clone pack.\n>\n> It is true that we try to use ofs-delta as much as possible, but\n> where does \"have no reason to be present\" come from?\n\nLack of knowledge, or writing without double checking the code.\n\n> When an object cannot be represented as an ofs-delta (which can only\n> refer backwards), don't we use ref-delta, instead of storing it as a\n> deflated-full object?\n\nAh I think you're right. The decision to choose ofs-delta in\npack-objects is if ofs-delta is enabled _and_ the offset to base is\navailable (i.e. base is already written).\n\n> Probably \"Not so ancient versions of Git tries to use ofs-delta\n> encoding whenever possible, so it is expected that objects encoded\n> using ref-delta are minority\" may be closer to the truth.  And that\n> observation does justify why using two separate pools (one with\n> 8-byte entries for ofs-delta, the other with 20-byte entries for\n> ref-delta) is a better idean than using one pool with 20-byte\n> entries for both kinds.\n\nYes. Looks good. Should I send a patch, or you fix the commit message locally?\n-- \nDuy\n"},{"id":"256788","messageId":"xmqqegp9igsr.fsf@gitster.dls.corp.google.com","threadId":"38607","inReplyTo":"CACsJy8A3MxpQRwboVjyv7akvzgf3y23ZsnAaxuHXkm2U=tUk0A@mail.gmail.com","subject":"Re: [PATCH v2 2/2] index-pack: kill union delta_base to save memory","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2015-03-01T02:37:40Z","receivedAt":"2015-03-01T02:37:40Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Duy Nguyen <pclouds@gmail.com> writes:\n\n>> Probably \"Not so ancient versions of Git tries to use ofs-delta\n>> encoding whenever possible, so it is expected that objects encoded\n>> using ref-delta are minority\" may be closer to the truth.  And that\n>> observation does justify why using two separate pools (one with\n>> 8-byte entries for ofs-delta, the other with 20-byte entries for\n>> ref-delta) is a better idean than using one pool with 20-byte\n>> entries for both kinds.\n>\n> Yes. Looks good. Should I send a patch, or you fix the commit\n> message locally?\n\nThinking about the above again, I do not think there is any point\nsaying \"not so ancient versions of Git\", as the receiving index-pack\nwould not even know what implementaiton of Git sits on the other end\nof the connection; it may even be a jGit based server, for example.\nSo something like:\n\n    Because ofs-delta encoding is more efficient space-wise and more\n    performant at runtime than ref-delta encoding, Git packers try\n    to use ofs-delta whenever possible, and it is expected that\n    objects encoded as ref-delta are minority.\n\nperhaps?\n"}]}