{"thread":{"id":"31237","subject":"[PATCH/RFC] index-pack: produce pack index version 3","startedAt":"2012-08-12T12:01:29Z","lastAt":"2012-08-16T16:26:33Z","messageCount":10,"participants":["Nguyễn Thái Ngọc Duy","Junio C Hamano","Nguyen Thai Ngoc Duy","Shawn Pearce"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"196882","messageId":"1344772889-8978-1-git-send-email-pclouds@gmail.com","threadId":"31237","inReplyTo":null,"subject":"[PATCH/RFC] index-pack: produce pack index version 3","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-08-12T12:01:29Z","receivedAt":"2012-08-12T12:01:29Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"The sha-1->offset table in v3 is sorted by object type first, then\nsha-1 (as opposed to sorted by sha-1 only in v2). There are four\nfan-out tables, one for each object type. So to look for the offset of\nan object, we first locate the fan-out table based on object type,\nthen do binary search in that region. If we don't know object type, we\nmay need to try all object types (which might be slower than now)\n\nLong term we might gain slight lookup speedup if we know object type\nas search region is made smaller. But for that to happen, we need to\npropagate object type hint down to find_pack_entry_one() and friends.\nPossible thing to do, I think.\n\nThe main reason to group objects by type is to make it possible to\ncreate another sha1->something mapping for a particular object type,\nwithout wasting space for storing sha-1 keys again. For example, we\ncan store commit caches, tree caches... at the end of the index as\nextensions.\n\nNote that this is just one of v3 changes. The format is not fixed yet.\nThe intent is allow extensions add the end of the index. Extensions\nare not covered by the trailer sha-1 that covers the entire index v2,\nso big extensions cannot impact normal operations until they are used.\nExtensions have their own sha-1 trailers.\n\nSigned-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>\n---\n Not compilable as it requires a couple other patches that I don't\n send. Just to get opinions on the format change. Shawn's connectivity\n bitmap cache or whatever cache can then be placed on this.\n\n builtin/index-pack.c |  8 ++++-\n pack-write.c         | 93 +++++++++++++++++++++++++++++++++++++++-------------\n pack.h               |  1 +\n sha1_file.c          | 50 +++++++++++++++++++++-------\n 4 files changed, 116 insertions(+), 36 deletions(-)\n\ndiff --git a/builtin/index-pack.c b/builtin/index-pack.c\nindex 68e2031..22c3cfa 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -1574,7 +1574,7 @@ int cmd_index_pack(int argc, const char **argv, const char *prefix)\n \t\t\t} else if (!prefixcmp(arg, \"--index-version=\")) {\n \t\t\t\tchar *c;\n \t\t\t\topts.version = strtoul(arg + 16, &c, 10);\n-\t\t\t\tif (opts.version > 2)\n+\t\t\t\tif (opts.version > 3)\n \t\t\t\t\tdie(_(\"bad %s\"), arg);\n \t\t\t\tif (*c == ',')\n \t\t\t\t\topts.off32_limit = strtoul(c+1, &c, 0);\n@@ -1650,6 +1650,12 @@ int cmd_index_pack(int argc, const char **argv, const char *prefix)\n \tfor (i = 0; i < nr_objects; i++)\n \t\tidx_objects[i] = &objects[i].idx;\n \topts.nr_objects = nr_objects;\n+\tif (opts.version >= 3) {\n+\t\topts.nr_commits = nr_commits;\n+\t\topts.nr_trees = nr_trees;\n+\t\topts.nr_blobs = nr_blobs;\n+\t\topts.nr_tags = nr_tags;\n+\t}\n \tcurr_index = write_idx_file(index_name, idx_objects, &opts, pack_sha1);\n \tfree(idx_objects);\n \ndiff --git a/pack-write.c b/pack-write.c\nindex 4643796..d4152b5 100644\n--- a/pack-write.c\n+++ b/pack-write.c\n@@ -16,6 +16,15 @@ static int sha1_compare(const void *_a, const void *_b)\n \treturn hashcmp(a->sha1, b->sha1);\n }\n \n+static int type_sha1_compare(const void *_a, const void *_b)\n+{\n+\tstruct pack_idx_entry *a = *(struct pack_idx_entry **)_a;\n+\tstruct pack_idx_entry *b = *(struct pack_idx_entry **)_b;\n+\n+\tassert(OBJ_COMMIT < OBJ_TREE && OBJ_TREE < OBJ_BLOB && OBJ_BLOB < OBJ_TAG);\n+\treturn a->type == b->type ? hashcmp(a->sha1, b->sha1) : a->type - b->type;\n+}\n+\n static int cmp_uint32(const void *a_, const void *b_)\n {\n \tuint32_t a = *((uint32_t *)a_);\n@@ -37,6 +46,32 @@ static int need_large_offset(off_t offset, const struct pack_idx_option *opts)\n \t\t\t sizeof(ofsval), cmp_uint32);\n }\n \n+static void make_fanout_table(struct pack_idx_entry **sorted_by_sha,\n+\t\t\t      unsigned long start, unsigned long end,\n+\t\t\t      uint32_t *array)\n+{\n+\tstruct pack_idx_entry **list = sorted_by_sha + start;\n+\tstruct pack_idx_entry **last = sorted_by_sha + end;\n+\tint i;\n+\n+\t/*\n+\t * Write the first-level table (the list is sorted,\n+\t * but we use a 256-entry lookup to be able to avoid\n+\t * having to do eight extra binary search iterations).\n+\t */\n+\tfor (i = 0; i < 256; i++) {\n+\t\tstruct pack_idx_entry **next = list;\n+\t\twhile (next < last) {\n+\t\t\tstruct pack_idx_entry *obj = *next;\n+\t\t\tif (obj->sha1[0] != i)\n+\t\t\t\tbreak;\n+\t\t\tnext++;\n+\t\t}\n+\t\tarray[i] = htonl(next - sorted_by_sha);\n+\t\tlist = next;\n+\t}\n+}\n+\n /*\n  * On entry *sha1 contains the pack content SHA1 hash, on exit it is\n  * the SHA1 hash of sorted object names. The objects array passed in\n@@ -47,27 +82,23 @@ const char *write_idx_file(const char *index_name, struct pack_idx_entry **objec\n \t\t\t   unsigned char *sha1)\n {\n \tstruct sha1file *f;\n-\tstruct pack_idx_entry **sorted_by_sha, **list, **last;\n+\tstruct pack_idx_entry **sorted_by_sha = NULL, **list;\n \toff_t last_obj_offset = 0;\n \tuint32_t array[256];\n \tint fd;\n \tgit_SHA_CTX ctx;\n-\tuint32_t index_version;\n+\tuint32_t index_version = opts->version;\n \tunsigned long i, nr_objects = opts->nr_objects;\n \n \tif (nr_objects) {\n \t\tsorted_by_sha = objects;\n-\t\tlist = sorted_by_sha;\n-\t\tlast = sorted_by_sha + nr_objects;\n \t\tfor (i = 0; i < nr_objects; ++i) {\n \t\t\tif (objects[i]->offset > last_obj_offset)\n \t\t\t\tlast_obj_offset = objects[i]->offset;\n \t\t}\n \t\tqsort(sorted_by_sha, nr_objects, sizeof(sorted_by_sha[0]),\n-\t\t      sha1_compare);\n+\t\t      opts->version >= 3 ? type_sha1_compare : sha1_compare);\n \t}\n-\telse\n-\t\tsorted_by_sha = list = last = NULL;\n \n \tif (opts->flags & WRITE_IDX_VERIFY) {\n \t\tassert(index_name);\n@@ -87,7 +118,8 @@ const char *write_idx_file(const char *index_name, struct pack_idx_entry **objec\n \t}\n \n \t/* if last object's offset is >= 2^31 we should use index V2 */\n-\tindex_version = need_large_offset(last_obj_offset, opts) ? 2 : opts->version;\n+\tif (opts->version <= 2 && need_large_offset(last_obj_offset, opts))\n+\t\tindex_version = 2;\n \n \t/* index versions 2 and above need a header */\n \tif (index_version >= 2) {\n@@ -97,23 +129,38 @@ const char *write_idx_file(const char *index_name, struct pack_idx_entry **objec\n \t\tsha1write(f, &hdr, sizeof(hdr));\n \t}\n \n-\t/*\n-\t * Write the first-level table (the list is sorted,\n-\t * but we use a 256-entry lookup to be able to avoid\n-\t * having to do eight extra binary search iterations).\n-\t */\n-\tfor (i = 0; i < 256; i++) {\n-\t\tstruct pack_idx_entry **next = list;\n-\t\twhile (next < last) {\n-\t\t\tstruct pack_idx_entry *obj = *next;\n-\t\t\tif (obj->sha1[0] != i)\n-\t\t\t\tbreak;\n-\t\t\tnext++;\n+\tif (index_version >= 3) {\n+\t\tunsigned long ub[OBJ_MAX], lb[OBJ_MAX];\n+\t\t/* we heavily rely on the actual enum constants.. */\n+\t\tassert(OBJ_COMMIT + 1 == OBJ_TREE &&\n+\t\t       OBJ_TREE   + 1 == OBJ_BLOB &&\n+\t\t       OBJ_BLOB   + 1 == OBJ_TAG);\n+\t\tlb[OBJ_COMMIT] = 0;\n+\t\tub[OBJ_COMMIT] = opts->nr_commits;\n+\t\tlb[OBJ_TREE]   = ub[OBJ_COMMIT];\n+\t\tub[OBJ_TREE]   = lb[OBJ_TREE] + opts->nr_trees;\n+\t\tlb[OBJ_BLOB]   = ub[OBJ_TREE];\n+\t\tub[OBJ_BLOB]   = lb[OBJ_BLOB] + opts->nr_blobs;\n+\t\tlb[OBJ_TAG]    = ub[OBJ_BLOB];\n+\t\tub[OBJ_TAG]    = lb[OBJ_TAG]  + opts->nr_tags;\n+\n+\t\t/* make sure nr_{commits,trees,objects,tags} match */\n+\t\tfor (i = OBJ_COMMIT; i <= OBJ_TAG; i++)\n+\t\t\tif (ub[i] > lb[i] &&\n+\t\t\t    (objects[lb[i]]->type != i ||\n+\t\t\t     objects[ub[i]-1]->type != i))\n+\t\t\t\tdie(_(\"expected to have %lu %s, but not so\"),\n+\t\t\t\t    ub[i] - lb[i], typename(i));\n+\n+\t\t/* v3 has four fanout tables instead of one */\n+\t\tfor (i = OBJ_COMMIT; i <= OBJ_TAG; i++) {\n+\t\t\tmake_fanout_table(sorted_by_sha, lb[i], ub[i], array);\n+\t\t\tsha1write(f, array, 256 * 4);\n \t\t}\n-\t\tarray[i] = htonl(next - sorted_by_sha);\n-\t\tlist = next;\n+\t} else {\n+\t\tmake_fanout_table(sorted_by_sha, 0, opts->nr_objects, array);\n+\t\tsha1write(f, array, 256 * 4);\n \t}\n-\tsha1write(f, array, 256 * 4);\n \n \t/* compute the SHA1 hash of sorted object names. */\n \tgit_SHA1_Init(&ctx);\ndiff --git a/pack.h b/pack.h\nindex f94e6c4..1a26f65 100644\n--- a/pack.h\n+++ b/pack.h\n@@ -45,6 +45,7 @@ struct pack_idx_option {\n \tuint32_t off32_limit;\n \n \tunsigned long nr_objects;\n+\tunsigned long nr_commits, nr_trees, nr_tags, nr_blobs;\n \n \t/*\n \t * List of offsets that would fit within off32_limit but\ndiff --git a/sha1_file.c b/sha1_file.c\nindex af5cfbd..66cc38a 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -480,7 +480,7 @@ static int check_packed_git_idx(const char *path,  struct packed_git *p)\n \tvoid *idx_map;\n \tstruct pack_idx_header *hdr;\n \tsize_t idx_size;\n-\tuint32_t version, nr, i, *index;\n+\tuint32_t version, nr, i, *index, nr_fanout;\n \tint fd = git_open_noatime(path);\n \tstruct stat st;\n \n@@ -501,7 +501,7 @@ static int check_packed_git_idx(const char *path,  struct packed_git *p)\n \thdr = idx_map;\n \tif (hdr->idx_signature == htonl(PACK_IDX_SIGNATURE)) {\n \t\tversion = ntohl(hdr->idx_version);\n-\t\tif (version < 2 || version > 2) {\n+\t\tif (version < 2 || version > 3) {\n \t\t\tmunmap(idx_map, idx_size);\n \t\t\treturn error(\"index file %s is version %\"PRIu32\n \t\t\t\t     \" and is not supported by this binary\"\n@@ -515,7 +515,8 @@ static int check_packed_git_idx(const char *path,  struct packed_git *p)\n \tindex = idx_map;\n \tif (version > 1)\n \t\tindex += 2;  /* skip index header */\n-\tfor (i = 0; i < 256; i++) {\n+\tnr_fanout = version <= 2 ? 256 : 4 * 256;\n+\tfor (i = 0; i < nr_fanout; i++) {\n \t\tuint32_t n = ntohl(index[i]);\n \t\tif (n < nr) {\n \t\t\tmunmap(idx_map, idx_size);\n@@ -536,11 +537,11 @@ static int check_packed_git_idx(const char *path,  struct packed_git *p)\n \t\t\tmunmap(idx_map, idx_size);\n \t\t\treturn error(\"wrong index v1 file size in %s\", path);\n \t\t}\n-\t} else if (version == 2) {\n+\t} else if (version == 2 || version == 3) {\n \t\t/*\n \t\t * Minimum size:\n \t\t *  - 8 bytes of header\n-\t\t *  - 256 index entries 4 bytes each\n+\t\t *  - 256 index entries 4 bytes each (1024 entries in v3)\n \t\t *  - 20-byte sha1 entry * nr\n \t\t *  - 4-byte crc entry * nr\n \t\t *  - 4-byte offset entry * nr\n@@ -552,6 +553,8 @@ static int check_packed_git_idx(const char *path,  struct packed_git *p)\n \t\t */\n \t\tunsigned long min_size = 8 + 4*256 + nr*(20 + 4 + 4) + 20 + 20;\n \t\tunsigned long max_size = min_size;\n+\t\tif (version == 3)\n+\t\t\tmin_size += 3 * 4*256;\n \t\tif (nr)\n \t\t\tmax_size += (nr - 1)*8;\n \t\tif (idx_size < min_size || idx_size > max_size) {\n@@ -1945,7 +1948,7 @@ const unsigned char *nth_packed_object_sha1(struct packed_git *p,\n \t}\n \tif (n >= p->num_objects)\n \t\treturn NULL;\n-\tindex += 4 * 256;\n+\tindex += p->index_version >= 3 ? 4 * 4 * 256 : 4 * 256;\n \tif (p->index_version == 1) {\n \t\treturn index + 24 * n + 4;\n \t} else {\n@@ -1957,7 +1960,7 @@ const unsigned char *nth_packed_object_sha1(struct packed_git *p,\n off_t nth_packed_object_offset(const struct packed_git *p, uint32_t n)\n {\n \tconst unsigned char *index = p->index_data;\n-\tindex += 4 * 256;\n+\tindex += p->index_version >= 3 ? 4 * 4 * 256 : 4 * 256;\n \tif (p->index_version == 1) {\n \t\treturn ntohl(*((uint32_t *)(index + 24 * n)));\n \t} else {\n@@ -1972,8 +1975,9 @@ off_t nth_packed_object_offset(const struct packed_git *p, uint32_t n)\n \t}\n }\n \n-off_t find_pack_entry_one(const unsigned char *sha1,\n-\t\t\t\t  struct packed_git *p)\n+static off_t find_pack_entry_one_by_type(const unsigned char *sha1,\n+\t\t\t\t\t struct packed_git *p,\n+\t\t\t\t\t enum object_type type)\n {\n \tconst uint32_t *level1_ofs = p->index_data;\n \tconst unsigned char *index = p->index_data;\n@@ -1994,9 +1998,19 @@ off_t find_pack_entry_one(const unsigned char *sha1,\n \t\tlevel1_ofs += 2;\n \t\tindex += 8;\n \t}\n-\tindex += 4 * 256;\n-\thi = ntohl(level1_ofs[*sha1]);\n-\tlo = ((*sha1 == 0x0) ? 0 : ntohl(level1_ofs[*sha1 - 1]));\n+\tif (p->index_version > 2) {\n+\t\tlevel1_ofs += (type - OBJ_COMMIT) * 256;\n+\t\tindex += 4 * 4 * 256;\n+\t\thi = ntohl(level1_ofs[*sha1]);\n+\t\tif (*sha1 == 0)\n+\t\t\tlo = type == OBJ_COMMIT ? 0 : ntohl(level1_ofs[-1]);\n+\t\telse\n+\t\t\tlo = ntohl(level1_ofs[*sha1 - 1]);\n+\t} else {\n+\t\tindex += 4 * 256;\n+\t\thi = ntohl(level1_ofs[*sha1]);\n+\t\tlo = ((*sha1 == 0x0) ? 0 : ntohl(level1_ofs[*sha1 - 1]));\n+\t}\n \tif (p->index_version > 1) {\n \t\tstride = 20;\n \t} else {\n@@ -2035,6 +2049,18 @@ off_t find_pack_entry_one(const unsigned char *sha1,\n \treturn 0;\n }\n \n+off_t find_pack_entry_one(const unsigned char *sha1,\n+\t\t\t\t  struct packed_git *p)\n+{\n+\toff_t off;\n+\tif ((off = find_pack_entry_one_by_type(sha1, p, OBJ_COMMIT)) != 0 ||\n+\t    (off = find_pack_entry_one_by_type(sha1, p, OBJ_TREE)) != 0 ||\n+\t    (off = find_pack_entry_one_by_type(sha1, p, OBJ_BLOB)) != 0 ||\n+\t    (off = find_pack_entry_one_by_type(sha1, p, OBJ_TAG)) != 0)\n+\t\treturn off;\n+\treturn 0;\n+}\n+\n int is_pack_valid(struct packed_git *p)\n {\n \t/* An already open pack is known to be valid. */\n-- \n1.7.12.rc2.18.g61b472e\n"},{"id":"196886","messageId":"7vtxw8exii.fsf@alter.siamese.dyndns.org","threadId":"31237","inReplyTo":"1344772889-8978-1-git-send-email-pclouds@gmail.com","subject":"Re: [PATCH/RFC] index-pack: produce pack index version 3","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-08-12T19:11:17Z","receivedAt":"2012-08-12T19:11:17Z","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> The main reason to group objects by type is to make it possible to\n> create another sha1->something mapping for a particular object type,\n> without wasting space for storing sha-1 keys again. For example, we\n> can store commit caches, tree caches... at the end of the index as\n> extensions.\n\nWhy can't you do the same with a single \"sorted by SHA-1\" table?\n\nNot impressed yet.\n"},{"id":"196890","messageId":"7vlihjgaaj.fsf@alter.siamese.dyndns.org","threadId":"31237","inReplyTo":"7vtxw8exii.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH/RFC] index-pack: produce pack index version 3","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-08-12T19:49:56Z","receivedAt":"2012-08-12T19:49:56Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano <gitster@pobox.com> writes:\n\n> Nguyễn Thái Ngọc Duy  <pclouds@gmail.com> writes:\n>\n>> The main reason to group objects by type is to make it possible to\n>> create another sha1->something mapping for a particular object type,\n>> without wasting space for storing sha-1 keys again. For example, we\n>> can store commit caches, tree caches... at the end of the index as\n>> extensions.\n>\n> Why can't you do the same with a single \"sorted by SHA-1\" table?\n>\n> Not impressed yet.\n\nThe above should be \"Not impressed yet, as it lacks sufficient\nexplanation of possible future benefits, but the idea is\ninteresting.\"\n\nFor example, the reachability bitmap would want to say something\nlike \"Traversing from commit A, these objects in this pack are\nreachable.\"  The bitmap for one commit A would logically consist of\nN bits for a packfile that stores N objects (the resulting bitmap\nneeds to be compressed before going to disk, perhaps with RLE or\nsomething).  With the single \"sorted by SHA-1\" table, we can use the\nindex in that single table to enumerate all reachable objects of any\ntype in one go.  With four separate tables, on the other hand, we\nwould need four bitmaps per commit.\n\nEither way is _possible_, but I think the former is simpler, and the\nlatter makes it harder to introduce new types of objects in the\nfuture, which I do not think we have examined possible use cases\nwell enough to make that decision to say \"four types is enough\nforever\".\n\nIn either way, we would have such bitmap (or a set of four bitmaps\nin your case) for more than one commit (it is not necessary or\ndesirable to add the reachability bitmap to all commits), and such a\n\"reachability extension\" would need to store a sequence of \"the\ncommit object name the bitmap (or a set of four bitmaps) is about,\nand the bitmap (or set of four bitmaps)\".  That object name does not\nhave to be 20-byte but would be a varint representation of the\noffset into the \"sorted by SHA-1\" table.  That varint representation\nwould be smaller by about 3.5 bits if you have a separate \"commit\nonly, sorted by SHA-1\" table (as the number of all objects tend to\nbe 10x larger than the number of all commits that need them).  For\nthe particular case of \"we want to only annotate the commits, never\nother kinds of objects\" use case, it would be a win.  But without\nknowing what other use cases we will want to use the \"object\nannotation in the pack index file\" mechanism for, it feels like a\npremature optimization to me to have four tables to shave 3.5 bits\nper object.\n"},{"id":"196892","messageId":"CACsJy8CNp2w6PsMSrQ4aFBwHKbOGid4pVHUhE4xgmTatrnEepQ@mail.gmail.com","threadId":"31237","inReplyTo":"7vlihjgaaj.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH/RFC] index-pack: produce pack index version 3","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-08-13T00:57:01Z","receivedAt":"2012-08-13T00:57:01Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Mon, Aug 13, 2012 at 2:49 AM, Junio C Hamano <gitster@pobox.com> wrote:\n> For example, the reachability bitmap would want to say something\n> like \"Traversing from commit A, these objects in this pack are\n> reachable.\"  The bitmap for one commit A would logically consist of\n> N bits for a packfile that stores N objects (the resulting bitmap\n> needs to be compressed before going to disk, perhaps with RLE or\n> something).  With the single \"sorted by SHA-1\" table, we can use the\n> index in that single table to enumerate all reachable objects of any\n> type in one go.  With four separate tables, on the other hand, we\n> would need four bitmaps per commit.\n\nNo we still need one per commit. The n-th bit is in the order of the\nobject in the pack, not the index. How sha-1 is sorted does not\nmatter.\n\n> Either way is _possible_, but I think the former is simpler, and the\n> latter makes it harder to introduce new types of objects in the\n> future, which I do not think we have examined possible use cases\n> well enough to make that decision to say \"four types is enough\n> forever\".\n\nNew types can be put in one of those four tables, depending on its\npurpose. The reason I split because I care particularly about commits\nand trees. If the new type serves the same purpose as tree, for\nexample, then it's better put in tree table...\n\n> In either way, we would have such bitmap (or a set of four bitmaps\n> in your case) for more than one commit (it is not necessary or\n> desirable to add the reachability bitmap to all commits), and such a\n> \"reachability extension\" would need to store a sequence of \"the\n> commit object name the bitmap (or a set of four bitmaps) is about,\n> and the bitmap (or set of four bitmaps)\".  That object name does not\n> have to be 20-byte but would be a varint representation of the\n> offset into the \"sorted by SHA-1\" table.\n\nHow do you reach the bitmap, given its commit sha-1?\n\n> That varint representation\n> would be smaller by about 3.5 bits if you have a separate \"commit\n> only, sorted by SHA-1\" table (as the number of all objects tend to\n> be 10x larger than the number of all commits that need them).  For\n> the particular case of \"we want to only annotate the commits, never\n> other kinds of objects\" use case, it would be a win.  But without\n> knowing what other use cases we will want to use the \"object\n> annotation in the pack index file\" mechanism for, it feels like a\n> premature optimization to me to have four tables to shave 3.5 bits\n> per object.\n\ncaching trees for faster traversal in general case (sort of pack v4\nbut it comes as a cache instead of replacing the real pack).\n-- \nDuy\n"},{"id":"196904","messageId":"7v8vdjfddk.fsf@alter.siamese.dyndns.org","threadId":"31237","inReplyTo":"CACsJy8CNp2w6PsMSrQ4aFBwHKbOGid4pVHUhE4xgmTatrnEepQ@mail.gmail.com","subject":"Re: [PATCH/RFC] index-pack: produce pack index version 3","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-08-13T07:40:55Z","receivedAt":"2012-08-13T07:40:55Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nguyen Thai Ngoc Duy <pclouds@gmail.com> writes:\n\n> On Mon, Aug 13, 2012 at 2:49 AM, Junio C Hamano <gitster@pobox.com> wrote:\n>> For example, the reachability bitmap would want to say something\n>> like \"Traversing from commit A, these objects in this pack are\n>> reachable.\"  The bitmap for one commit A would logically consist of\n>> N bits for a packfile that stores N objects (the resulting bitmap\n>> needs to be compressed before going to disk, perhaps with RLE or\n>> something).  With the single \"sorted by SHA-1\" table, we can use the\n>> index in that single table to enumerate all reachable objects of any\n>> type in one go.  With four separate tables, on the other hand, we\n>> would need four bitmaps per commit.\n>\n> No we still need one per commit. The n-th bit is in the order of the\n> object in the pack, not the index. How sha-1 is sorted does not\n> matter.\n\nThen what is the problem of using that same \"N\" that counts the\nobject using the order of the objects in the pack as a short-hand to\nthe object name instead, if your objective is to avoid having to\nrepeat the full 20-byte object name in your secondary tables?  That\ndoes not call for any split in the list of SHA-1s, no?\n\n>> Either way is _possible_, but I think the former is simpler, and the\n>> latter makes it harder to introduce new types of objects in the\n>> future, which I do not think we have examined possible use cases\n>> well enough to make that decision to say \"four types is enough\n>> forever\".\n>\n> New types can be put in one of those four tables, depending on its\n> purpose. The reason I split because I care particularly about commits\n> and trees. If the new type serves the same purpose as tree, for\n> example, then it's better put in tree table...\n\nAnd when there are multiple uses, one that wants to treat trees and\ncommits more or less the same way, and another that wants to treat\nthem in a distinct way, even without considering a new type, how\nwould your \"we have four separate tables\" help?  The former user\nwants three \"commits+trees\", \"tags\" and \"blobs\" table while the\nlatter wants four, no?\n\n>> In either way, we would have such bitmap (or a set of four bitmaps\n>> in your case) for more than one commit (it is not necessary or\n>> desirable to add the reachability bitmap to all commits), and such a\n>> \"reachability extension\" would need to store a sequence of \"the\n>> commit object name the bitmap (or a set of four bitmaps) is about,\n>> and the bitmap (or set of four bitmaps)\".  That object name does not\n>> have to be 20-byte but would be a varint representation of the\n>> offset into the \"sorted by SHA-1\" table.\n>\n> How do you reach the bitmap, given its commit sha-1?\n\nLook at the ordered list of SHA-1 in the pack idx file as an array\nof 20-byte entries, and find the commit SHA-1 in that array by\nNewton-Raphson/bisection.  You have an index into the array that\nholds the object name.  You can use it as the local object number\nin the packfile.  Then you can find that object number (that is\nshorter than 20-byte object name) in your secondary table, no?\n"},{"id":"196950","messageId":"CAJo=hJtwS=fdjTCVsEQHdVn9p+_2k-wJ_W_zLtZkWGO+M4suNQ@mail.gmail.com","threadId":"31237","inReplyTo":"7v8vdjfddk.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH/RFC] index-pack: produce pack index version 3","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2012-08-14T00:46:56Z","receivedAt":"2012-08-14T00:46:56Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Let me start by echoing Junio's remark... \"lacks sufficient\njustification\". You don't give enough evidence to support even why it\nis worth looking at this commit, let alone why it should be included\nand cause a format change in the idx file format.\n\nAt some point you start to hand-wave about how it may benefit my\nbitmap reachability index idea, but you don't seem to fully understand\nthat idea. And some of what you do here sounds like it actively hurts\ndoing the bitmap reachability project. So again this doesn't really\nhelp.\n\nColby is nearly done prototyping the bitmap reachability\nimplementation in JGit and will release the code under the BSD license\nthere soon. I can't promise when yet because Colby will soon be\nheading out for some (much deserved) vacation time, and doesn't want\nto publish something until he is ready to stand behind the code. So it\nmight not show up until mid-September. But I think its worth giving\nhim a few weeks to finish getting the code ready, vs. rushing\nsomething in that someone else thinks might help. We have waited more\nthan 6 years or whatever to improve packing. Colby's experiments are\nshowing massive improvements (40s enumeration cut to 100ms) with low\ndisk usage increase (<10%) and no pack file format changes. Its OK to\nwait 4 more weeks.\n\nOn Mon, Aug 13, 2012 at 12:40 AM, Junio C Hamano <gitster@pobox.com> wrote:\n> Nguyen Thai Ngoc Duy <pclouds@gmail.com> writes:\n>\n>> On Mon, Aug 13, 2012 at 2:49 AM, Junio C Hamano <gitster@pobox.com> wrote:\n>>> For example, the reachability bitmap would want to say something\n>>> like \"Traversing from commit A, these objects in this pack are\n>>> reachable.\"  The bitmap for one commit A would logically consist of\n>>> N bits for a packfile that stores N objects (the resulting bitmap\n>>> needs to be compressed before going to disk, perhaps with RLE or\n>>> something).  With the single \"sorted by SHA-1\" table, we can use the\n>>> index in that single table to enumerate all reachable objects of any\n>>> type in one go.  With four separate tables, on the other hand, we\n>>> would need four bitmaps per commit.\n>>\n>> No we still need one per commit. The n-th bit is in the order of the\n>> object in the pack, not the index. How sha-1 is sorted does not\n>> matter.\n\nYes, for RLE encoding to work well it is important that the bits are\nassigned using pack offset ordering, not SHA-1 ordering. The object at\nbit 0 is the object at offset 12 in the pack file, not the object that\nhas the lowest SHA-1. The RLE encoding is relying on the packer to\nstore objects closely reachable by time near each other in the pack\nfile. Which the packer already does because we have roughly proven\nthough the years that this ordering works sufficiently well enough for\nnobody to propose another ordering.  :-)\n\n> Then what is the problem of using that same \"N\" that counts the\n> object using the order of the objects in the pack as a short-hand to\n> the object name instead, if your objective is to avoid having to\n> repeat the full 20-byte object name in your secondary tables?  That\n> does not call for any split in the list of SHA-1s, no?\n\nExactly. There is no need to store a second copy of the SHA-1s\nanywhere. We can discover information about object identified by bit N\nby creating the reverse pack index in memory. The N-th entry in the\nreverse index will tell us the Y-th position in the normal idx file,\nwhich gives us the SHA-1. So SHA-1 can be obtained from a bitmap in\nconstant time, once the reverse index is built. The reverse index\nbuild costs O(N log N) time, but its already required by the packer to\ndo efficient reuse of packed objects. We already pay this O(N log N)\npenalty. So its currently free to us.\n\nThe bitmap approach Colby and I are collaborating on also contains 4\nRLE bitmaps indicating what type each object is. Its needed so the\npacker can avoid looking up type data in the base pack file, while\nalso avoiding parsing of trees where the mode information normally\nprovides the type hint. We could instead get this by splitting the\nSHA-1 table into 4 tables as this patch proposes, but it doesn't help.\nType information can be obtained fast enough from these 4 RLE bitmaps,\nwithout muddying the read code path with needing to know what table to\nsearch, or needing to search 4 tables rather than 1 table.\n\n>>> Either way is _possible_, but I think the former is simpler, and the\n>>> latter makes it harder to introduce new types of objects in the\n>>> future, which I do not think we have examined possible use cases\n>>> well enough to make that decision to say \"four types is enough\n>>> forever\".\n>>\n>> New types can be put in one of those four tables, depending on its\n>> purpose.\n\nNo. A new type should get a new table. We should never cram a new type\ninto an existing type table just because it sounds like a good idea.\nIts not. We are unlikely to add a new type anytime soon. If we do its\ngoing to take more work than just worrying about where it fits into an\nidx file. But it shouldn't be combined into a bucket with an existing\ntype.\n\n>> The reason I split because I care particularly about commits\n>> and trees. If the new type serves the same purpose as tree, for\n>> example, then it's better put in tree table...\n\nIt isn't worth speculating about this. We aren't likely to add a new\ntype. If we do its probably not like another type.\n\n> And when there are multiple uses, one that wants to treat trees and\n> commits more or less the same way, and another that wants to treat\n> them in a distinct way, even without considering a new type, how\n> would your \"we have four separate tables\" help?  The former user\n> wants three \"commits+trees\", \"tags\" and \"blobs\" table while the\n> latter wants four, no?\n\nAnd this paragraph alone indicates why splitting the SHA-1 table is a\nstupid idea. Readers who have a SHA-1 in hand shouldn't have to dig\naround in 4 different tables trying to figure out what it wants. Or\nmaybe 3 tables if it thinks its tree-ish. Its just a stupid discussion\nto have. At this level of the system the object database is a database\nkeyed by SHA-1s. Simple. Don't muddle it.\n\n>>> In either way, we would have such bitmap (or a set of four bitmaps\n>>> in your case) for more than one commit (it is not necessary or\n>>> desirable to add the reachability bitmap to all commits), and such a\n>>> \"reachability extension\" would need to store a sequence of \"the\n>>> commit object name the bitmap (or a set of four bitmaps) is about,\n>>> and the bitmap (or set of four bitmaps)\".  That object name does not\n>>> have to be 20-byte but would be a varint representation of the\n>>> offset into the \"sorted by SHA-1\" table.\n\nYes.\n\n>> How do you reach the bitmap, given its commit sha-1?\n>\n> Look at the ordered list of SHA-1 in the pack idx file as an array\n> of 20-byte entries, and find the commit SHA-1 in that array by\n> Newton-Raphson/bisection.  You have an index into the array that\n> holds the object name.  You can use it as the local object number\n> in the packfile.  Then you can find that object number (that is\n> shorter than 20-byte object name) in your secondary table, no?\n\nYes, exactly. But I am trying to steer Colby into a slightly different\ndirection. For ~222k commits we need only about 2k reachability\nbitmaps. If these are keyed by N-th SHA-1 as Junio states, we can\nlookup the object in the object map and mark a flag on it saying\n\"reachability bitmap exists on this commit\". Later if the revision\nwalker hits a commit with this flag set, we know we should look at\nthat bitmap information. Allocating 2k commits into the revision\nwalking map is fairly cheap, and makes it fast for the walker to later\nidentify where a bitmap exists. But I don't have any data yet to prove\nwhat the fastest way to manage finding the right bitmaps is.\n"},{"id":"196951","messageId":"CACsJy8CPmGLMoy6-AKuKGLtFQfQO3yKgXCmfb2=Qhmi676cXxA@mail.gmail.com","threadId":"31237","inReplyTo":"CAJo=hJtwS=fdjTCVsEQHdVn9p+_2k-wJ_W_zLtZkWGO+M4suNQ@mail.gmail.com","subject":"Re: [PATCH/RFC] index-pack: produce pack index version 3","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-08-14T01:27:39Z","receivedAt":"2012-08-14T01:27:39Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Tue, Aug 14, 2012 at 7:46 AM, Shawn Pearce <spearce@spearce.org> wrote:\n> Colby is nearly done prototyping the bitmap reachability\n> implementation in JGit and will release the code under the BSD license\n> there soon. I can't promise when yet because Colby will soon be\n> heading out for some (much deserved) vacation time, and doesn't want\n> to publish something until he is ready to stand behind the code. So it\n> might not show up until mid-September. But I think its worth giving\n> him a few weeks to finish getting the code ready, vs. rushing\n> something in that someone else thinks might help. We have waited more\n> than 6 years or whatever to improve packing. Colby's experiments are\n> showing massive improvements (40s enumeration cut to 100ms) with low\n> disk usage increase (<10%) and no pack file format changes. Its OK to\n> wait 4 more weeks.\n\nThanks. I did not know it's being worked on (your last email did not\nindicate that, I think). I just wanted to try out and see how it might\nwork. And sure I can wait :)\n--\nDuy\n"},{"id":"197076","messageId":"7vmx1v2y01.fsf@alter.siamese.dyndns.org","threadId":"31237","inReplyTo":"CAJo=hJtwS=fdjTCVsEQHdVn9p+_2k-wJ_W_zLtZkWGO+M4suNQ@mail.gmail.com","subject":"Re: [PATCH/RFC] index-pack: produce pack index version 3","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-08-16T05:42:54Z","receivedAt":"2012-08-16T05:42:54Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Shawn Pearce <spearce@spearce.org> writes:\n\n> ... But I think its worth giving\n> him a few weeks to finish getting the code ready, vs. rushing\n> something in that someone else thinks might help. We have waited more\n> than 6 years or whatever to improve packing. Colby's experiments are\n> showing massive improvements (40s enumeration cut to 100ms) with low\n> disk usage increase (<10%) and no pack file format changes.\n\nNo matter what you do, you would be saving the bitmap somewhere\noutside the *.pack file, yes?  Will it be in some extended section\nof the new *.idx file?\n\nWith the bitmap, your object enumeration phase may go very fast, and\nyou would be able to figure out, in response to a fetch request \"I\nhave these tips of refs; please update me with these refs of yours\",\nthe set of objects you would need to pack (i.e. the ones that are\nreachable from your refs that were asked for, but that are not\nreachable from the refs the requestor has).  \n\nAmong these objects, there will be ones that are expressed as a\ndelta against what you are going to send, or as a delta against what\nyou know the recipient must already have (if you are using thin pack\ntransfer) in the packfiles you have, and you can send these deltas\nas-is without recomputation.\n\nBut there will be ones that are either expressed as a base in your\npackfile, or as a delta against something you are not going to send\nand you know that the recipient does not have.  In order to turn\nthese objects into deltas, it may be necessary to have a way to\nrecord which \"delta chain\" each object belongs to, and if you are\nintroducing the mechanism to have extended sections in the new *.idx\nfile, that may be a good place to do so.  When you need to express\nan object that your bitmap told you to send (as opposed to rev-list\nwalking told you with the paths to the objects), you can find other\nobjects that belong to the same \"delta chain\" and that you know are\navailable to the recipient when it starts to fixing the thin pack\nusing that extra piece of information, in order to find the optimal\ndelta base to encode such an object against.\n\nJust for fun, I applied the attached patch and repacked the history\nleading to v1.7.12-rc3 with the default depth/window:\n\n  git rev-list --objects --all |\n  git pack-objects \\\n      --no-reuse-delta --no-reuse-object --delta-base-offset \\\n      [--no-namehash] pack\n\nwith and without the experimental --no-namehash option.  The result\nis staggering.  With name-hash to group objects from the same path\nclose together in the delta window, the resulting pack is 33M.\nWithout the name-hash hint, the same pack is 163M!  Needless to say,\nkeeping the objects that should be hashed together inside a delta\nwindow is really important.\n\nAn obvious way to record the \"delta chain\" is to simply keep the\nname_hash of each object in the pack, which would need 2 bytes per\nobject in the pack, that would bloat pack_idx_entry size from 32\nbytes to 34 bytes per entry.  That way, after your bitmap discovers\nan object that cannot reuse existing deltas, you can throw it, other\nsuch objects with the same name-hash, and then objects that you know\nwill be available to the recipient (you mark the last category of\nobjects as \"preferred base\"), into the delta_list so that they are\nclose together in the delta window.\n\nAnd here is a patch to experiment the name-hash based grouping\nheuristics.\n\n builtin/pack-objects.c | 5 ++++-\n 1 file changed, 4 insertions(+), 1 deletion(-)\n\ndiff --git c/builtin/pack-objects.c w/builtin/pack-objects.c\nindex 782e7d0..a2dd67b 100644\n--- c/builtin/pack-objects.c\n+++ w/builtin/pack-objects.c\n@@ -67,6 +67,7 @@ static int keep_unreachable, unpack_unreachable, include_tag;\n static unsigned long unpack_unreachable_expiration;\n static int local;\n static int incremental;\n+static int use_name_hash = 1;\n static int ignore_packed_keep;\n static int allow_ofs_delta;\n static struct pack_idx_option pack_idx_opts;\n@@ -863,7 +864,7 @@ static unsigned name_hash(const char *name)\n {\n \tunsigned c, hash = 0;\n \n-\tif (!name)\n+\tif (!name || !use_name_hash)\n \t\treturn 0;\n \n \t/*\n@@ -2468,6 +2469,8 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix)\n \t\t\t  \"limit pack window by memory in addition to object limit\"),\n \t\tOPT_INTEGER(0, \"depth\", &depth,\n \t\t\t    \"maximum length of delta chain allowed in the resulting pack\"),\n+\t\tOPT_BOOL(0, \"namehash\", &use_name_hash,\n+\t\t\t \"assign name hint to each path\"),\n \t\tOPT_BOOL(0, \"reuse-delta\", &reuse_delta,\n \t\t\t \"reuse existing deltas\"),\n \t\tOPT_BOOL(0, \"reuse-object\", &reuse_object,\n"},{"id":"197102","messageId":"CAJo=hJtgq7j67RU28ziQN4xUX7S5-YcaiApmcpMSYdamV-0SgQ@mail.gmail.com","threadId":"31237","inReplyTo":"7vmx1v2y01.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH/RFC] index-pack: produce pack index version 3","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2012-08-16T15:54:00Z","receivedAt":"2012-08-16T15:54:00Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Wed, Aug 15, 2012 at 10:42 PM, Junio C Hamano <gitster@pobox.com> wrote:\n> Shawn Pearce <spearce@spearce.org> writes:\n>\n>> ... But I think its worth giving\n>> him a few weeks to finish getting the code ready, vs. rushing\n>> something in that someone else thinks might help. We have waited more\n>> than 6 years or whatever to improve packing. Colby's experiments are\n>> showing massive improvements (40s enumeration cut to 100ms) with low\n>> disk usage increase (<10%) and no pack file format changes.\n>\n> No matter what you do, you would be saving the bitmap somewhere\n> outside the *.pack file, yes?  Will it be in some extended section\n> of the new *.idx file?\n\nYes, because it is derived from the pack stream its stored external\nfrom it. We have chosen to append it as a new section below the CRC-32\ntable in the *.idx file. It could also go into a new file stream\n(*.bdx?) but I don't think this is worthwhile. Its a bikeshed that can\nbe painted once the algorithm has proven its value. If it can't do\nthat, its irrelevant where its stored.\n\n> With the bitmap, your object enumeration phase may go very fast, and\n> you would be able to figure out, in response to a fetch request \"I\n> have these tips of refs; please update me with these refs of yours\",\n> the set of objects you would need to pack (i.e. the ones that are\n> reachable from your refs that were asked for, but that are not\n> reachable from the refs the requestor has).\n\nYes. Not only that, but we are finding that the number of objects to\nsend is fewer, resulting in a much smaller data stream. The bitmap\ngives us near perfect knowledge of everything the client has, not just\nthe objects on the edge of the graph cut expressed by the ACKed have\nlines. Objects that existed earlier than the cut don't have to be\nreset.\n\nSo the object enumeration phase goes very fast. The compressing\nobjects phase is also time reduced, as fewer objects are needed to be\nconsidered, as fewer objects are being sent. With more complete\nknowledge of the have side, more deltas can be reused as-is, rather\nthan re-encoded on the fly. This reduces the compressing objects phase\ntime even further. And with fewer objects to send, we have easily seen\ntrivial cases of a Linux kernel fetch that is 1 week behind Linus' tip\nsave like 200K on an 800K transfer. Its hard to hate having all of the\nphases go faster, and transmit less data to the client.\n\n> Among these objects, there will be ones that are expressed as a\n> delta against what you are going to send, or as a delta against what\n> you know the recipient must already have (if you are using thin pack\n> transfer) in the packfiles you have, and you can send these deltas\n> as-is without recomputation.\n\nYes. I point that out above before even reading this far in your message. :-(\n\n> But there will be ones that are either expressed as a base in your\n> packfile, or as a delta against something you are not going to send\n> and you know that the recipient does not have.  In order to turn\n> these objects into deltas, it may be necessary to have a way to\n> record which \"delta chain\" each object belongs to\n\nExcellent observation. Instead of performing a hacky delta base search\nby looking at identical path names in the have set, finding another\ncandidate in the same cluster of deltas that the object is currently\nencoded against would yield a pretty efficient delta on the wire. It\ndoesn't have to be another object in the same chain, it could also be\na sibling object that shares a similar transitive delta base.\n\n>, and if you are\n> introducing the mechanism to have extended sections in the new *.idx\n> file, that may be a good place to do so.\n\nThus far we haven't done an extended sections modification to the\n*.idx format. Its just a 'E003' version that requires the bitmaps to\nbe present below the CRC-32 table. But I can see how framing this as a\ngroup of optional extensions would be worthwhile.\n\n>  When you need to express\n> an object that your bitmap told you to send (as opposed to rev-list\n> walking told you with the paths to the objects), you can find other\n> objects that belong to the same \"delta chain\" and that you know are\n> available to the recipient when it starts to fixing the thin pack\n> using that extra piece of information, in order to find the optimal\n> delta base to encode such an object against.\n\nYes.\n\n> Just for fun, I applied the attached patch and repacked the history\n> leading to v1.7.12-rc3 with the default depth/window:\n>\n>   git rev-list --objects --all |\n>   git pack-objects \\\n>       --no-reuse-delta --no-reuse-object --delta-base-offset \\\n>       [--no-namehash] pack\n>\n> with and without the experimental --no-namehash option.  The result\n> is staggering.  With name-hash to group objects from the same path\n> close together in the delta window, the resulting pack is 33M.\n> Without the name-hash hint, the same pack is 163M!  Needless to say,\n> keeping the objects that should be hashed together inside a delta\n> window is really important.\n\nCute experiment. Yes that name hash works as a decent predictor of\nwhich objects should go near each other in the delta window. So does\nthe descending size sort.\n\n> An obvious way to record the \"delta chain\" is to simply keep the\n> name_hash of each object in the pack, which would need 2 bytes per\n> object in the pack, that would bloat pack_idx_entry size from 32\n> bytes to 34 bytes per entry.  That way, after your bitmap discovers\n> an object that cannot reuse existing deltas, you can throw it, other\n> such objects with the same name-hash, and then objects that you know\n> will be available to the recipient (you mark the last category of\n> objects as \"preferred base\"), into the delta_list so that they are\n> close together in the delta window.\n\nYes, this is one thought I had. Inside of JGit I think the name hash\nis 32 bits, not 16 bits. Storing the name hash into the *.idx file\nmeans we need to codify what the name hash algorithm is for a given\n*.idx file version, and compatible implementations of Git must use the\nsame hash function. Thus far the name hash has been an in-memory\ntransient concept that doesn't need to be persisted across runs of the\npacker. Storing it means we have to do that.\n\nAnother alternative is to try and group objects by delta clusters. Tag\neach object with some marker for the non-delta base object the delta\nchain it builds on top of. Delta groups are supposed to tend to be\nbushy and not long, so many many objects should share the same common\nbase object. Most of them have the same name hash, but even when they\ndon't their contents were near enough together that the prior packer\nrun chose to combine these together. This avoids the need to encode\nthe name-hash function into the *.idx file format, and instead lets us\nwork with something that any implementation can easily observe from\nthe file's contents.\n\nTagging each object with its base could cost 4 bytes per entry, so\n32->36 bytes... a 12% increase in file size. It may be possible to\norganize these as bitmaps and get really good compression from deltas\nthat are located near each other in the pack stream, but doing the\nlookup to identify which base would be more expensive. We would\nprobably have to walk the object's delta chain backwards to identify\nthe base, then inflate the bitmap to identify the candidate siblings.\n"},{"id":"197107","messageId":"7vwr0y247a.fsf@alter.siamese.dyndns.org","threadId":"31237","inReplyTo":"CAJo=hJtgq7j67RU28ziQN4xUX7S5-YcaiApmcpMSYdamV-0SgQ@mail.gmail.com","subject":"Re: [PATCH/RFC] index-pack: produce pack index version 3","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-08-16T16:26:33Z","receivedAt":"2012-08-16T16:26:33Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Shawn Pearce <spearce@spearce.org> writes:\n\n> On Wed, Aug 15, 2012 at 10:42 PM, Junio C Hamano <gitster@pobox.com> wrote:\n> ...\n>> An obvious way to record the \"delta chain\" is to simply keep the\n>> name_hash of each object in the pack, which would need 2 bytes per\n>> object in the pack, that would bloat pack_idx_entry size from 32\n>> bytes to 34 bytes per entry.  That way, after your bitmap discovers\n>> an object that cannot reuse existing deltas, you can throw it, other\n>> such objects with the same name-hash, and then objects that you know\n>> will be available to the recipient (you mark the last category of\n>> objects as \"preferred base\"), into the delta_list so that they are\n>> close together in the delta window.\n>\n> Yes, this is one thought I had. Inside of JGit I think the name hash\n> is 32 bits, not 16 bits. Storing the name hash into the *.idx file\n> means we need to codify what the name hash algorithm is for a given\n> *.idx file version, and compatible implementations of Git must use the\n> same hash function. Thus far the name hash has been an in-memory\n> transient concept that doesn't need to be persisted across runs of the\n> packer. Storing it means we have to do that.\n\nLet's not go there.  We cannot resurrect the name hash out of *.pack\nstream, which means index-pack cannot recreate it after receiving\nobjects over the network.  We would need to instead teach index-pack\nto observe the delta chains, and come up with some \"delta chain\nidentifier\" (unique name to identify what you called \"delta cluster\"\nin your response) on its own, and give it to each object when it\nwrites the *.idx file out.\n"}]}