{"thread":{"id":"3342","subject":"[FYI] pack idx format","startedAt":"2006-02-15T08:39:23Z","lastAt":"2006-02-18T06:50:32Z","messageCount":17,"participants":["Junio C Hamano","Johannes Schindelin","Nicolas Pitre","Linus Torvalds","Andreas Ericsson"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"16198","messageId":"7vd5hpm2x0.fsf@assigned-by-dhcp.cox.net","threadId":"3342","inReplyTo":null,"subject":"[FYI] pack idx format","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-02-15T08:39:23Z","receivedAt":"2006-02-15T08:39:23Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"This is still WIP but if anybody is interested...  Once done, it\nshould become Documentation/technical/pack-format.txt.\n\nThe reason I started doing this is to prototype this one:\n\n\t<7v4q3453qu.fsf@assigned-by-dhcp.cox.net>\n\n-- >8 --\n\nIdx file:\n\nThe idx file is to map object name SHA1 to offset into the\ncorresponding pack file.  There is the 'first-level fan-out'\ntable at the beginning, and then the main part of the index\nfollows.  This is a table whose entries are sorted by their\nobject name SHA1.  The file ends with some trailer information.\n\nThe main part is a table of 24-byte entries, and each entry is:\n\n\toffset : 4-byte network byte order integer.\n\tSHA1   : 20-byte object name SHA1.\n\nThe data for the named object begins at byte offset \"offset\" in\nthe corresponding pack file.\n\nBefore this main table, at the beginning of the idx file, there\nis a table of 256 4-byte network byte order integers.  This is\ncalled \"first-level fan-out\".  N-th entry of this table records\nthe offset into the main index for the first object whose object\nname SHA1 starts with N+1.  fanout[255] points at the end of\nmain index.  The offset is expressed in 24-bytes unit.\n\nExample:\n\n\tidx\n\t    +--------------------------------+\n\t    | fanout[0] = 2                  |-.\n\t    +--------------------------------+ |\n\t    | fanout[1]                      | |\n\t    +--------------------------------+ |\n\t    | fanout[2]                      | |\n\t    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ |\n\t    | fanout[255]                    | |\n\t    +--------------------------------+ |\nmain\t    | offset                         | |\nindex\t    | object name 00XXXXXXXXXXXXXXXX | |\ntable\t    +--------------------------------+ | \n\t    | offset                         | |\n\t    | object name 00XXXXXXXXXXXXXXXX | |\n\t    +--------------------------------+ |\n\t  .-| offset                         |<+\n\t  | | object name 01XXXXXXXXXXXXXXXX |\n\t  | +--------------------------------+\n\t  | | offset                         |\n\t  | | object name 01XXXXXXXXXXXXXXXX |\n\t  | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n\t  | | offset                         |\n\t  | | object name FFXXXXXXXXXXXXXXXX |\n\t  | +--------------------------------+\ntrailer\t  | | packfile checksum              |\n\t  | +--------------------------------+\n\t  | | idxfile checksum               |\n\t  | +--------------------------------+\n          .-------.      \n                  |\nPack file entry: <+\n\n     packed object header:\n\t1-byte type (upper 4-bit)\n\t       size0 (lower 4-bit) \n        n-byte sizeN (as long as MSB is set, each 7-bit)\n\t\tsize0..sizeN form 4+7+7+..+7 bit integer, size0\n\t\tis the most significant part.\n     packed object data:\n        If it is not DELTA, then deflated bytes (the size above\n\t\tis the size before compression).\n\tIf it is DELTA, then\n\t  20-byte base object name SHA1 (the size above is the\n\t  \tsize of the delta data that follows).\n          delta data, deflated.\n"},{"id":"16209","messageId":"Pine.LNX.4.63.0602151208181.9837@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"3342","inReplyTo":"7vd5hpm2x0.fsf@assigned-by-dhcp.cox.net","subject":"Re: [FYI] pack idx format","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2006-02-15T11:16:08Z","receivedAt":"2006-02-15T11:16:08Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Wed, 15 Feb 2006, Junio C Hamano wrote:\n\n> [...]\n> \n> Before this main table, at the beginning of the idx file, there\n> is a table of 256 4-byte network byte order integers.  This is\n> called \"first-level fan-out\".  N-th entry of this table records\n> the offset into the main index for the first object whose object\n> name SHA1 starts with N+1.  fanout[255] points at the end of\n> main index.  The offset is expressed in 24-bytes unit.\n\nThe description of the n-th entry is not completely correct. How about \nsomething like this:\n\nThe fan-out table is sort of an index to the main table: It contains \noffsets into the main table, and all SHA1s starting with byte b are \nbetween fanout[b-1] .. fanout[b]-1 (or if b==0 between 0 .. fanout[0]-1).\n\nComments?\n\nCiao,\nDscho\n"},{"id":"16220","messageId":"Pine.LNX.4.64.0602151144010.5606@localhost.localdomain","threadId":"3342","inReplyTo":"7vd5hpm2x0.fsf@assigned-by-dhcp.cox.net","subject":"Re: [FYI] pack idx format","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-02-15T16:46:46Z","receivedAt":"2006-02-15T16:46:46Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Wed, 15 Feb 2006, Junio C Hamano wrote:\n\n> This is still WIP but if anybody is interested...  Once done, it\n> should become Documentation/technical/pack-format.txt.\n> \n[...]\n> \n> Pack file entry: <+\n> \n>      packed object header:\n> \t1-byte type (upper 4-bit)\n\nActually the type occupies only 3 bits (bits 4 to 6) as bit 7 is the \nsize continuation bit.\n\n\nNicolas\n"},{"id":"16232","messageId":"7vbqx8m62q.fsf@assigned-by-dhcp.cox.net","threadId":"3342","inReplyTo":"7vd5hpm2x0.fsf@assigned-by-dhcp.cox.net","subject":"[PATCH] pack-objects: reuse data from existing pack.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-02-16T01:43:25Z","receivedAt":"2006-02-16T01:43:25Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"When generating a new pack, notice if we have already the wanted\nobject in existing packs.  If the object has a delitified\nrepresentation, and its base object is also what we are going to\npack, then reuse the existing deltified representation\nunconditionally, bypassing all the expensive find_deltas() and\ntry_deltas() routines.\n\nAlso, when writing out such deltified representation and\nundeltified representation, if a matching data already exists in\nan existing pack, just write it out without uncompressing &\nrecompressing.\n\nWithout this patch:\n\n    $ git-rev-list --objects v1.0.0 >RL\n    $ time git-pack-objects p <RL\n\n    Generating pack...\n    Done counting 12233 objects.\n    Packing 12233 objects....................\n    60a88b3979df41e22d1edc3967095e897f720192\n\n    real    0m32.751s\n    user    0m27.090s\n    sys     0m2.750s\n\nWith this patch:\n\n    $ git-rev-list --objects v1.0.0 >RL\n    $ time ../git.junio/git-pack-objects q <RL\n\n    Generating pack...\n    Done counting 12233 objects.\n    Packing 12233 objects.....................\n    60a88b3979df41e22d1edc3967095e897f720192\n    Total 12233, written 12233, reused 12177\n\n    real    0m4.007s\n    user    0m3.360s\n    sys     0m0.090s\n\nSigned-off-by: Junio C Hamano <junkio@cox.net>\n\n---\n\n * This may depend on one cleanup patch I have not sent out, but\n   I am so excited that I could not help sending this out first.\n\n   Admittedly this is hot off the press, I have not had enough\n   time to beat this too hard, but the resulting pack from the\n   above passed unpack-objects, index-pack and verify-pack.\n\n pack-objects.c |  317 ++++++++++++++++++++++++++++++++++++++++++++++----------\n pack.h         |    4 +\n sha1_file.c    |   19 +++\n 3 files changed, 283 insertions(+), 57 deletions(-)\n\n0d574a3c3ec6924118d06ee0487d02d2fbb12646\ndiff --git a/pack-objects.c b/pack-objects.c\nindex c5a5e61..f2a45a2 100644\n--- a/pack-objects.c\n+++ b/pack-objects.c\n@@ -9,13 +9,16 @@ static const char pack_usage[] = \"git-pa\n \n struct object_entry {\n \tunsigned char sha1[20];\n-\tunsigned long size;\n-\tunsigned long offset;\n-\tunsigned int depth;\n-\tunsigned int hash;\n+\tunsigned long size;\t/* uncompressed size */\n+\tunsigned long offset;\t/* offset into the final pack file (nonzero if already written) */\n+\tunsigned int depth;\t/* delta depth */\n+\tunsigned int hash;\t/* name hint hash */\n \tenum object_type type;\n-\tunsigned long delta_size;\n-\tstruct object_entry *delta;\n+\tunsigned long delta_size;\t/* delta data size (uncompressed) */\n+\tstruct object_entry *delta;\t/* delta base object */\n+\tstruct packed_git *in_pack; \t/* already in pack */\n+\tenum object_type in_pack_type;\t/* could be delta */\n+\tunsigned int in_pack_offset;\n };\n \n static unsigned char object_list_sha1[20];\n@@ -29,6 +32,105 @@ static const char *base_name;\n static unsigned char pack_file_sha1[20];\n static int progress = 1;\n \n+static int *object_ix = NULL;\n+static int object_ix_hashsz = 0;\n+\n+struct pack_revindex {\n+\tstruct packed_git *p;\n+\tunsigned long *revindex;\n+} *pack_revindex = NULL;\n+static int pack_revindex_hashsz = 0;\n+\n+static int pack_revindex_ix(struct packed_git *p)\n+{\n+\tunsigned int ui = (unsigned int) p;\n+\tint i;\n+\tui = ui ^ (ui >> 16);\n+\ti = (int)(ui % pack_revindex_hashsz);\n+\twhile (pack_revindex[i].p) {\n+\t\tif (pack_revindex[i].p == p)\n+\t\t\treturn i;\n+\t\tif (++i == pack_revindex_hashsz)\n+\t\t\ti = 0;\n+\t}\n+\treturn -1 - i;\n+}\n+\n+static void prepare_pack_ix(void)\n+{\n+\tint num;\n+\tstruct packed_git *p;\n+\tfor (num = 0, p = packed_git; p; p = p->next)\n+\t\tnum++;\n+\tif (!num)\n+\t\treturn;\n+\tpack_revindex_hashsz = num * 11;\n+\tpack_revindex = xcalloc(sizeof(*pack_revindex), pack_revindex_hashsz);\n+\tfor (p = packed_git; p; p = p->next) {\n+\t\tnum = pack_revindex_ix(p);\n+\t\tnum = - 1 - num;\n+\t\tpack_revindex[num].p = p;\n+\t}\n+\t/* revindex elements are lazily initialized */\n+}\n+\n+static int cmp_offset(const void *a_, const void *b_)\n+{\n+\tunsigned long a = *(unsigned long *) a_;\n+\tunsigned long b = *(unsigned long *) b_;\n+\tif (a < b)\n+\t\treturn -1;\n+\telse if (a == b)\n+\t\treturn 0;\n+\telse\n+\t\treturn 1;\n+}\n+\n+static void prepare_pack_revindex(struct pack_revindex *rix)\n+{\n+\tstruct packed_git *p = rix->p;\n+\tint num_ent = num_packed_objects(p);\n+\tint i;\n+\tvoid *index = p->index_base + 256;\n+\n+\trix->revindex = xmalloc(sizeof(unsigned long) * (num_ent + 1));\n+\tfor (i = 0; i < num_ent; i++) {\n+\t\tlong hl = *((long *)(index + 24 * i));\n+\t\trix->revindex[i] = ntohl(hl);\n+\t}\n+\trix->revindex[num_ent] = p->pack_size - 20;\n+\tqsort(rix->revindex, num_ent, sizeof(unsigned long), cmp_offset);\n+}\n+\n+static unsigned long find_packed_object_size(struct packed_git *p,\n+\t\t\t\t\t     unsigned long ofs)\n+{\n+\tint num;\n+\tint lo, hi;\n+\tstruct pack_revindex *rix;\n+\tunsigned long *revindex;\n+\tnum = pack_revindex_ix(p);\n+\tif (num < 0)\n+\t\tdie(\"internal error: pack revindex uninitialized\");\n+\trix = &pack_revindex[num];\n+\tif (!rix->revindex)\n+\t\tprepare_pack_revindex(rix);\n+\trevindex = rix->revindex;\n+\tlo = 0;\n+\thi = num_packed_objects(p) + 1;\n+\tdo {\n+\t\tint mi = (lo + hi) / 2;\n+\t\tif (revindex[mi] == ofs) {\n+\t\t\treturn revindex[mi+1] - ofs;\n+\t\t}\n+\t\telse if (ofs < revindex[mi])\n+\t\t\thi = mi;\n+\t\telse\n+\t\t\tlo = mi + 1;\n+\t} while (lo < hi);\n+\tdie(\"internal error: pack revindex corrupt\");\n+}\n+\n static void *delta_against(void *buf, unsigned long size, struct object_entry *entry)\n {\n \tunsigned long othersize, delta_size;\n@@ -74,39 +176,59 @@ static int encode_header(enum object_typ\n \treturn n;\n }\n \n+static int written = 0;\n+static int reused = 0;\n+\n static unsigned long write_object(struct sha1file *f, struct object_entry *entry)\n {\n \tunsigned long size;\n \tchar type[10];\n-\tvoid *buf = read_sha1_file(entry->sha1, type, &size);\n+\tvoid *buf;\n \tunsigned char header[10];\n \tunsigned hdrlen, datalen;\n \tenum object_type obj_type;\n \n-\tif (!buf)\n-\t\tdie(\"unable to read %s\", sha1_to_hex(entry->sha1));\n-\tif (size != entry->size)\n-\t\tdie(\"object %s size inconsistency (%lu vs %lu)\", sha1_to_hex(entry->sha1), size, entry->size);\n-\n-\t/*\n-\t * The object header is a byte of 'type' followed by zero or\n-\t * more bytes of length.  For deltas, the 20 bytes of delta sha1\n-\t * follows that.\n-\t */\n \tobj_type = entry->type;\n-\tif (entry->delta) {\n-\t\tbuf = delta_against(buf, size, entry);\n-\t\tsize = entry->delta_size;\n-\t\tobj_type = OBJ_DELTA;\n-\t}\n-\thdrlen = encode_header(obj_type, size, header);\n-\tsha1write(f, header, hdrlen);\n-\tif (entry->delta) {\n-\t\tsha1write(f, entry->delta, 20);\n-\t\thdrlen += 20;\n+\tif (!entry->in_pack ||\n+\t    (obj_type != entry->in_pack_type)) {\n+\t\tbuf = read_sha1_file(entry->sha1, type, &size);\n+\t\tif (!buf)\n+\t\t\tdie(\"unable to read %s\", sha1_to_hex(entry->sha1));\n+\t\tif (size != entry->size)\n+\t\t\tdie(\"object %s size inconsistency (%lu vs %lu)\",\n+\t\t\t    sha1_to_hex(entry->sha1), size, entry->size);\n+\t\tif (entry->delta) {\n+\t\t\tbuf = delta_against(buf, size, entry);\n+\t\t\tsize = entry->delta_size;\n+\t\t\tobj_type = OBJ_DELTA;\n+\t\t}\n+\t\t/*\n+\t\t * The object header is a byte of 'type' followed by zero or\n+\t\t * more bytes of length.  For deltas, the 20 bytes of delta\n+\t\t * sha1 follows that.\n+\t\t */\n+\t\thdrlen = encode_header(obj_type, size, header);\n+\t\tsha1write(f, header, hdrlen);\n+\n+\t\tif (entry->delta) {\n+\t\t\tsha1write(f, entry->delta, 20);\n+\t\t\thdrlen += 20;\n+\t\t}\n+\t\tdatalen = sha1write_compressed(f, buf, size);\n+\t\tfree(buf);\n+\t}\n+\telse {\n+\t\tstruct packed_git *p = entry->in_pack;\n+\t\tuse_packed_git(p);\n+\n+\t\tdatalen = find_packed_object_size(p, entry->in_pack_offset);\n+\t\tbuf = p->pack_base + entry->in_pack_offset;\n+\t\tsha1write(f, buf, datalen);\n+\t\tunuse_packed_git(p);\n+\t\thdrlen = 0; /* not really */\n+\t\treused++;\n \t}\n-\tdatalen = sha1write_compressed(f, buf, size);\n-\tfree(buf);\n+\twritten++;\n \treturn hdrlen + datalen;\n }\n \n@@ -196,18 +318,21 @@ static int add_object_entry(unsigned cha\n {\n \tunsigned int idx = nr_objects;\n \tstruct object_entry *entry;\n-\n-\tif (incremental || local) {\n-\t\tstruct packed_git *p;\n-\n-\t\tfor (p = packed_git; p; p = p->next) {\n-\t\t\tstruct pack_entry e;\n-\n-\t\t\tif (find_pack_entry_one(sha1, &e, p)) {\n-\t\t\t\tif (incremental)\n-\t\t\t\t\treturn 0;\n-\t\t\t\tif (local && !p->pack_local)\n-\t\t\t\t\treturn 0;\n+\tstruct packed_git *p;\n+\tunsigned int found_offset;\n+\tstruct packed_git *found_pack;\n+\n+\tfound_pack = NULL;\n+\tfor (p = packed_git; p; p = p->next) {\n+\t\tstruct pack_entry e;\n+\t\tif (find_pack_entry_one(sha1, &e, p)) {\n+\t\t\tif (incremental)\n+\t\t\t\treturn 0;\n+\t\t\tif (local && !p->pack_local)\n+\t\t\t\treturn 0;\n+\t\t\tif (!found_pack) {\n+\t\t\t\tfound_offset = e.offset;\n+\t\t\t\tfound_pack = e.p;\n \t\t\t}\n \t\t}\n \t}\n@@ -221,30 +346,99 @@ static int add_object_entry(unsigned cha\n \tmemset(entry, 0, sizeof(*entry));\n \tmemcpy(entry->sha1, sha1, 20);\n \tentry->hash = hash;\n+\tif (found_pack) {\n+\t\tentry->in_pack = found_pack;\n+\t\tentry->in_pack_offset = found_offset;\n+\t}\n \tnr_objects = idx+1;\n \treturn 1;\n }\n \n+static int locate_object_entry_hash(unsigned char *sha1)\n+{\n+\tint i;\n+\tunsigned int ui;\n+\tmemcpy(&ui, sha1, sizeof(unsigned int));\n+\ti = ui % object_ix_hashsz;\n+\twhile (0 < object_ix[i]) {\n+\t\tif (!memcmp(sha1, objects[object_ix[i]-1].sha1, 20))\n+\t\t\treturn i;\n+\t\tif (++i == object_ix_hashsz)\n+\t\t\ti = 0;\n+\t}\n+\treturn -1 - i;\n+}\n+\n+static struct object_entry *locate_object_entry(unsigned char *sha1)\n+{\n+\tint i = locate_object_entry_hash(sha1);\n+\tif (0 <= i)\n+\t\treturn &objects[object_ix[i]-1];\n+\treturn NULL;\n+}\n+\n static void check_object(struct object_entry *entry)\n {\n \tchar type[20];\n \n-\tif (!sha1_object_info(entry->sha1, type, &entry->size)) {\n-\t\tif (!strcmp(type, \"commit\")) {\n-\t\t\tentry->type = OBJ_COMMIT;\n-\t\t} else if (!strcmp(type, \"tree\")) {\n-\t\t\tentry->type = OBJ_TREE;\n-\t\t} else if (!strcmp(type, \"blob\")) {\n-\t\t\tentry->type = OBJ_BLOB;\n-\t\t} else if (!strcmp(type, \"tag\")) {\n-\t\t\tentry->type = OBJ_TAG;\n-\t\t} else\n-\t\t\tdie(\"unable to pack object %s of type %s\",\n-\t\t\t    sha1_to_hex(entry->sha1), type);\n+\tif (entry->in_pack) {\n+\t\t/* Check if it is delta, and the base is also an object\n+\t\t * we are going to pack.  If so we will reuse the existing\n+\t\t * delta.\n+\t\t */\n+\t\tunsigned char base[20];\n+\t\tunsigned long size;\n+\t\tstruct object_entry *base_entry;\n+\t\tif (!check_reuse_pack_delta(entry->in_pack,\n+\t\t\t\t\t    entry->in_pack_offset,\n+\t\t\t\t\t    base, &size,\n+\t\t\t\t\t    &entry->in_pack_type) &&\n+\t\t    (base_entry = locate_object_entry(base))) {\n+\t\t\t/* we do not know yet, but it does not matter */\n+\t\t\tentry->depth = 1;\n+\t\t\t/* uncompressed size */\n+\t\t\tentry->size = entry->delta_size = size;\n+\t\t\tentry->delta = base_entry;\n+\t\t\tentry->type = OBJ_DELTA; /* !! */\n+\t\t\treturn;\n+\t\t}\n+\t\t/* Otherwise we would do the usual */\n \t}\n-\telse\n+\n+\tif (sha1_object_info(entry->sha1, type, &entry->size))\n \t\tdie(\"unable to get type of object %s\",\n \t\t    sha1_to_hex(entry->sha1));\n+\n+\tif (!strcmp(type, \"commit\")) {\n+\t\tentry->type = OBJ_COMMIT;\n+\t} else if (!strcmp(type, \"tree\")) {\n+\t\tentry->type = OBJ_TREE;\n+\t} else if (!strcmp(type, \"blob\")) {\n+\t\tentry->type = OBJ_BLOB;\n+\t} else if (!strcmp(type, \"tag\")) {\n+\t\tentry->type = OBJ_TAG;\n+\t} else\n+\t\tdie(\"unable to pack object %s of type %s\",\n+\t\t    sha1_to_hex(entry->sha1), type);\n+}\n+\n+static void hash_objects(void)\n+{\n+\tint i;\n+\tstruct object_entry *oe;\n+\n+\tobject_ix_hashsz = nr_objects * 2;\n+\tobject_ix = xcalloc(sizeof(int), object_ix_hashsz);\n+\tfor (i = 0, oe = objects; i < nr_objects; i++, oe++) {\n+\t\tint ix = locate_object_entry_hash(oe->sha1);\n+\t\tif (0 <= ix) {\n+\t\t\terror(\"the same object '%s' added twice\",\n+\t\t\t      sha1_to_hex(oe->sha1));\n+\t\t\tcontinue;\n+\t\t}\n+\t\tix = -1 - ix;\n+\t\tobject_ix[ix] = i + 1;\n+\t}\n }\n \n static void get_object_details(void)\n@@ -252,6 +446,8 @@ static void get_object_details(void)\n \tint i;\n \tstruct object_entry *entry = objects;\n \n+\thash_objects();\n+\tprepare_pack_ix();\n \tfor (i = 0; i < nr_objects; i++)\n \t\tcheck_object(entry++);\n }\n@@ -382,6 +578,11 @@ static void find_deltas(struct object_en\n \t\t\teye_candy -= nr_objects / 20;\n \t\t\tfputc('.', stderr);\n \t\t}\n+\n+\t\tif (entry->delta)\n+\t\t\t/* we already know what we need to know */\n+\t\t\tcontinue;\n+\n \t\tfree(n->data);\n \t\tn->entry = entry;\n \t\tn->data = read_sha1_file(entry->sha1, type, &size);\n@@ -411,10 +612,12 @@ static void find_deltas(struct object_en\n \n static void prepare_pack(int window, int depth)\n {\n-\tget_object_details();\n-\n \tif (progress)\n \t\tfprintf(stderr, \"Packing %d objects\", nr_objects);\n+\tget_object_details();\n+\tif (progress)\n+\t\tfprintf(stderr, \".\");\n+\n \tsorted_by_type = create_sorted_list(type_size_sort);\n \tif (window && depth)\n \t\tfind_deltas(sorted_by_type, window+1, depth);\n@@ -599,5 +802,7 @@ int main(int argc, char **argv)\n \t\t\tputs(sha1_to_hex(object_list_sha1));\n \t\t}\n \t}\n+\tfprintf(stderr, \"Total %d, written %d, reused %d\\n\",\n+\t\tnr_objects, written, reused);\n \treturn 0;\n }\ndiff --git a/pack.h b/pack.h\nindex 9dafa2b..694e0c5 100644\n--- a/pack.h\n+++ b/pack.h\n@@ -29,5 +29,7 @@ struct pack_header {\n };\n \n extern int verify_pack(struct packed_git *, int);\n-\n+extern int check_reuse_pack_delta(struct packed_git *, unsigned long,\n+\t\t\t\t  unsigned char *, unsigned long *,\n+\t\t\t\t  enum object_type *);\n #endif\ndiff --git a/sha1_file.c b/sha1_file.c\nindex 64cf245..0a3a721 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -826,6 +826,25 @@ static unsigned long unpack_object_heade\n \treturn offset;\n }\n \n+int check_reuse_pack_delta(struct packed_git *p, unsigned long offset,\n+\t\t\t   unsigned char *base, unsigned long *sizep,\n+\t\t\t   enum object_type *kindp)\n+{\n+\tunsigned long ptr;\n+\tint status = -1;\n+\n+\tuse_packed_git(p);\n+\tptr = offset;\n+\tptr = unpack_object_header(p, ptr, kindp, sizep);\n+\tif (*kindp != OBJ_DELTA)\n+\t\tgoto done;\n+\tmemcpy(base, p->pack_base + ptr, 20);\n+\tstatus = 0;\n+ done:\n+\tunuse_packed_git(p);\n+\treturn status;\n+}\n+\n void packed_object_info_detail(struct pack_entry *e,\n \t\t\t       char *type,\n \t\t\t       unsigned long *size,\n-- \n1.2.0.gcfba7\n"},{"id":"16233","messageId":"7v64ngm602.fsf_-_@assigned-by-dhcp.cox.net","threadId":"3342","inReplyTo":"7vbqx8m62q.fsf@assigned-by-dhcp.cox.net","subject":"[PATCH] packed objects: minor cleanup","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-02-16T01:45:01Z","receivedAt":"2006-02-16T01:45:01Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"The delta depth is unsigned.\n\nSigned-off-by: Junio C Hamano <junkio@cox.net>\n\n---\n\n * And this is the clean-up patch that comes before the \"packed\n   representation reuse\" patch.\n\n cache.h      |    2 +-\n pack-check.c |    4 ++--\n sha1_file.c  |    4 ++--\n 3 files changed, 5 insertions(+), 5 deletions(-)\n\nf8f135c9bae74f846a92e1f1f1fea8308802ace5\ndiff --git a/cache.h b/cache.h\nindex c255421..b5db01f 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -322,7 +322,7 @@ extern int num_packed_objects(const stru\n extern int nth_packed_object_sha1(const struct packed_git *, int, unsigned char*);\n extern int find_pack_entry_one(const unsigned char *, struct pack_entry *, struct packed_git *);\n extern void *unpack_entry_gently(struct pack_entry *, char *, unsigned long *);\n-extern void packed_object_info_detail(struct pack_entry *, char *, unsigned long *, unsigned long *, int *, unsigned char *);\n+extern void packed_object_info_detail(struct pack_entry *, char *, unsigned long *, unsigned long *, unsigned int *, unsigned char *);\n \n /* Dumb servers support */\n extern int update_server_info(int);\ndiff --git a/pack-check.c b/pack-check.c\nindex 67a7ecd..eca32b6 100644\n--- a/pack-check.c\n+++ b/pack-check.c\n@@ -84,7 +84,7 @@ static void show_pack_info(struct packed\n \t\tchar type[20];\n \t\tunsigned long size;\n \t\tunsigned long store_size;\n-\t\tint delta_chain_length;\n+\t\tunsigned int delta_chain_length;\n \n \t\tif (nth_packed_object_sha1(p, i, sha1))\n \t\t\tdie(\"internal error pack-check nth-packed-object\");\n@@ -98,7 +98,7 @@ static void show_pack_info(struct packed\n \t\tif (!delta_chain_length)\n \t\t\tprintf(\"%-6s %lu %u\\n\", type, size, e.offset);\n \t\telse\n-\t\t\tprintf(\"%-6s %lu %u %d %s\\n\", type, size, e.offset,\n+\t\t\tprintf(\"%-6s %lu %u %u %s\\n\", type, size, e.offset,\n \t\t\t       delta_chain_length, sha1_to_hex(base_sha1));\n \t}\n \ndiff --git a/sha1_file.c b/sha1_file.c\nindex 3d11a9b..64cf245 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -830,7 +830,7 @@ void packed_object_info_detail(struct pa\n \t\t\t       char *type,\n \t\t\t       unsigned long *size,\n \t\t\t       unsigned long *store_size,\n-\t\t\t       int *delta_chain_length,\n+\t\t\t       unsigned int *delta_chain_length,\n \t\t\t       unsigned char *base_sha1)\n {\n \tstruct packed_git *p = e->p;\n@@ -844,7 +844,7 @@ void packed_object_info_detail(struct pa\n \tif (kind != OBJ_DELTA)\n \t\t*delta_chain_length = 0;\n \telse {\n-\t\tint chain_length = 0;\n+\t\tunsigned int chain_length = 0;\n \t\tmemcpy(base_sha1, pack, 20);\n \t\tdo {\n \t\t\tstruct pack_entry base_ent;\n-- \n1.2.0.gcfba7\n"},{"id":"16234","messageId":"7vy80ckqsm.fsf@assigned-by-dhcp.cox.net","threadId":"3342","inReplyTo":"Pine.LNX.4.64.0602151144010.5606@localhost.localdomain","subject":"Re: [FYI] pack idx format","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-02-16T01:58:49Z","receivedAt":"2006-02-16T01:58:49Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nicolas Pitre <nico@cam.org> writes:\n\n> On Wed, 15 Feb 2006, Junio C Hamano wrote:\n>\n>> This is still WIP but if anybody is interested...  Once done, it\n>> should become Documentation/technical/pack-format.txt.\n>> \n> [...]\n>> \n>> Pack file entry: <+\n>> \n>>      packed object header:\n>> \t1-byte type (upper 4-bit)\n>\n> Actually the type occupies only 3 bits (bits 4 to 6) as bit 7 is the \n> size continuation bit.\n\nYou are right.\n"},{"id":"16240","messageId":"Pine.LNX.4.64.0602152226130.5606@localhost.localdomain","threadId":"3342","inReplyTo":"7vbqx8m62q.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] pack-objects: reuse data from existing pack.","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-02-16T03:41:24Z","receivedAt":"2006-02-16T03:41:24Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Wed, 15 Feb 2006, Junio C Hamano wrote:\n\n> When generating a new pack, notice if we have already the wanted\n> object in existing packs.  If the object has a delitified\n> representation, and its base object is also what we are going to\n> pack, then reuse the existing deltified representation\n> unconditionally, bypassing all the expensive find_deltas() and\n> try_deltas() routines.\n> \n> Also, when writing out such deltified representation and\n> undeltified representation, if a matching data already exists in\n> an existing pack, just write it out without uncompressing &\n> recompressing.\n\nGreat !\n\n> Without this patch:\n> \n>     $ git-rev-list --objects v1.0.0 >RL\n>     $ time git-pack-objects p <RL\n> \n>     Generating pack...\n>     Done counting 12233 objects.\n>     Packing 12233 objects....................\n>     60a88b3979df41e22d1edc3967095e897f720192\n> \n>     real    0m32.751s\n>     user    0m27.090s\n>     sys     0m2.750s\n> \n> With this patch:\n> \n>     $ git-rev-list --objects v1.0.0 >RL\n>     $ time ../git.junio/git-pack-objects q <RL\n> \n>     Generating pack...\n>     Done counting 12233 objects.\n>     Packing 12233 objects.....................\n>     60a88b3979df41e22d1edc3967095e897f720192\n>     Total 12233, written 12233, reused 12177\n> \n>     real    0m4.007s\n>     user    0m3.360s\n>     sys     0m0.090s\n> \n> Signed-off-by: Junio C Hamano <junkio@cox.net>\n> \n> ---\n> \n>  * This may depend on one cleanup patch I have not sent out, but\n>    I am so excited that I could not help sending this out first.\n> \n>    Admittedly this is hot off the press, I have not had enough\n>    time to beat this too hard, but the resulting pack from the\n>    above passed unpack-objects, index-pack and verify-pack.\n\nIn fact, the resulting pack should be identical with or without this \npatch, shouldn't it?\n\nFYI: I have list of patches to produce even smaller (yet still \ncompatible) packs, or less dense ones but with much reduced CPU usage.  \nAll depending on a new --speed argument to git-pack-objects.  I've been \nable to produce 15-20% smaller packs with the same depth and window \nsize, but taking twice as much CPU time to produce. Combined with your \npatch, one could repack the object store with the maximum compression \neven if it is expensive CPU wise, but any pull will benefit from it \nafterwards with no additional cost.\n\nI only need to find some time to finally clean and re-test those \npatches...\n\n\nNicolas\n"},{"id":"16241","messageId":"Pine.LNX.4.64.0602151953290.916@g5.osdl.org","threadId":"3342","inReplyTo":"7vbqx8m62q.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] pack-objects: reuse data from existing pack.","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-02-16T03:55:32Z","receivedAt":"2006-02-16T03:55:32Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Wed, 15 Feb 2006, Junio C Hamano wrote:\n>\n> When generating a new pack, notice if we have already the wanted\n> object in existing packs.  If the object has a delitified\n> representation, and its base object is also what we are going to\n> pack, then reuse the existing deltified representation\n> unconditionally, bypassing all the expensive find_deltas() and\n> try_deltas() routines.\n\nI bow down before you.\n\nNo ugly special-case caching, just automatically \"the right thing\", with \nvery little overhead.\n\nIt just makes sense.\n\nWe have a winner.\n\n\t\tLinus\n"},{"id":"16242","messageId":"7v4q30kl71.fsf@assigned-by-dhcp.cox.net","threadId":"3342","inReplyTo":"Pine.LNX.4.64.0602152226130.5606@localhost.localdomain","subject":"Re: [PATCH] pack-objects: reuse data from existing pack.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-02-16T03:59:46Z","receivedAt":"2006-02-16T03:59:46Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nicolas Pitre <nico@cam.org> writes:\n\n> On Wed, 15 Feb 2006, Junio C Hamano wrote:\n>\n>>     Generating pack...\n>>     Done counting 12233 objects.\n>>     Packing 12233 objects.....................\n>>     60a88b3979df41e22d1edc3967095e897f720192\n>>     Total 12233, written 12233, reused 12177\n>> ...\n> In fact, the resulting pack should be identical with or without this \n> patch, shouldn't it?\n\nNot necessarily.  The delta-depth limitation is currently lifted\nwhen reusing deltified objects (finding out the current depth is\nnot so expensive compared to uncompress-delta-recompress cycle,\nbut still costs somewhat, and the objective of this exercise is\nto gain performance).\n\nNotice the numbers 'written' and 'reused' in the output?\nThe difference in that example comes from the fact that I am\nomitting some objects from the set of objects to be packed\n(v1.0.0 is ancient) in a repository where some newer objects are\npacked.  Since packing-delta goes backwards, what is in v1.0.0\nbut not in my tip tends to be delitified in the original pack,\nbut the resulting pack needs to have them expanded -- that is\nwhere the difference comes from.\n\nA cleaned-up patch will be in \"pu\" branch tonight.  I considered\nputting it in \"next\", but decided against it.  I have not spent\nenough time really beating on it, although I haven't seen major\nbreakage.\n"},{"id":"16244","messageId":"7vzmksj69h.fsf@assigned-by-dhcp.cox.net","threadId":"3342","inReplyTo":"Pine.LNX.4.64.0602151953290.916@g5.osdl.org","subject":"Re: [PATCH] pack-objects: reuse data from existing pack.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-02-16T04:07:38Z","receivedAt":"2006-02-16T04:07:38Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds <torvalds@osdl.org> writes:\n\n> No ugly special-case caching, just automatically \"the right thing\", with \n> very little overhead.\n>\n> It just makes sense.\n\nThanks.  I threw away two rounds of crap before this one, which\nwere full of ugly special cases ;-).\n"},{"id":"16258","messageId":"43F438AA.1040508@op5.se","threadId":"3342","inReplyTo":"7vbqx8m62q.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] pack-objects: reuse data from existing pack.","fromName":"Andreas Ericsson","fromEmail":"ae@op5.se","sentAt":"2006-02-16T08:32:42Z","receivedAt":"2006-02-16T08:32:42Z","isPatch":true,"sender":{"key":"ae@op5.se","avatar":"https://gravatar.com/avatar/426e89595c75a8f5252dd0c989e5fabe5bcac616e68557427ad9aef6b0ca342a?d=mp&s=160"},"body":"Junio C Hamano wrote:\n> When generating a new pack, notice if we have already the wanted\n> object in existing packs.  If the object has a delitified\n> representation, and its base object is also what we are going to\n> pack, then reuse the existing deltified representation\n> unconditionally, bypassing all the expensive find_deltas() and\n> try_deltas() routines.\n> \n> Also, when writing out such deltified representation and\n> undeltified representation, if a matching data already exists in\n> an existing pack, just write it out without uncompressing &\n> recompressing.\n> \n> Without this patch:\n> \n>     $ git-rev-list --objects v1.0.0 >RL\n>     $ time git-pack-objects p <RL\n> \n>     Generating pack...\n>     Done counting 12233 objects.\n>     Packing 12233 objects....................\n>     60a88b3979df41e22d1edc3967095e897f720192\n> \n>     real    0m32.751s\n>     user    0m27.090s\n>     sys     0m2.750s\n> \n> With this patch:\n> \n>     $ git-rev-list --objects v1.0.0 >RL\n>     $ time ../git.junio/git-pack-objects q <RL\n> \n>     Generating pack...\n>     Done counting 12233 objects.\n>     Packing 12233 objects.....................\n>     60a88b3979df41e22d1edc3967095e897f720192\n>     Total 12233, written 12233, reused 12177\n> \n>     real    0m4.007s\n>     user    0m3.360s\n>     sys     0m0.090s\n> \n\nWhoa! Columbus and the egg. Strange noone saw it before. It's so obvious \nwhen you shove it under the nose like that. :)\n\nNow that pack-creation went from bizarrely expensive to insanely cheap \n(well, comparable to \"tar czf\" anyways), what's BCP for packing a public \nrepository? Always one mega-pack and never worry, or should one still \nuse incremental and sometimes overlapping pack-files?\n\n-- \nAndreas Ericsson                   andreas.ericsson@op5.se\nOP5 AB                             www.op5.se\nTel: +46 8-230225                  Fax: +46 8-230231\n"},{"id":"16261","messageId":"7vr763bra7.fsf@assigned-by-dhcp.cox.net","threadId":"3342","inReplyTo":"43F438AA.1040508@op5.se","subject":"Re: [PATCH] pack-objects: reuse data from existing pack.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-02-16T09:13:04Z","receivedAt":"2006-02-16T09:13:04Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Andreas Ericsson <ae@op5.se> writes:\n\n> Whoa! Columbus and the egg. Strange noone saw it before. It's so\n> obvious when you shove it under the nose like that. :)\n\nI wished the pack format were not so dense as we have today.  It\nis very expensive to obtain the uncompressed size of a deltified\nobject.  For this reason, a delta newly created (either from a\nnon-delta in an existing pack or from a loose object) by the\nexperimental algorithm is never made against an object that is\nin deltified form in a pack.  Also it incurs nontrivial cost to\nobtain the size of the in-pack representation of an object\n(either deltified or not).  But the inefficiency in the\nresulting pack due to these factors may not matter in practice.\n\nI just packed v2.6.16-rc3 object list (184141 objects) using the\ncurrent and the experimental, just for fun.  Tonight's one runs\njust under 1 minutes on my Duron 750 (with slow disks I should\nadd).  This was done in a repository that has about 1500 loose\nobjects and a single mega pack; reuse rate of packed data by the\nexperimental algorithm is about 99%.  I am hoping the one from\nthe \"master\" would come back before I finish writing this\nmessage ;-).\n\nThere are subtleties.\n\nFor example, in a typical project, files tend to grow rather\nthan shrink on average, and older ones tend to be in packs.  If\nyou do packing the traditional way, the largest one (which is\ntypically the latest) is kept as non-delta, and all the smaller\nones will be incremental delta from that, no matter how your\npacks and loose objects are organized.\n\nUsually, you have the latest objects as loose objects in your\nrepository to be packed (either you push from it, or somebody\nelse pulls from you).  In other words, as you develop after your\nlast repack, you would accumulate loose objects, and they are\nthe ones that typically matter the most.\n\nLet's say you have been changing the same file in every commit\n(1..N), then you fully packed and then created another commit\n(revision N+1) that touches the file.  The experimental\nreuse-packer would:\n\n    - notice blobs from revision 1..(N-1) are deltified,\n      relative to the rev one greater than each of them.\n      these would be reused.\n    - notice blob from revision N is in the pack but not\n      deltified.\n    - notice blob from revision N+1 is loose.\n\nThen emit the bigger one between N or N+1 as non-delta, the\nother one as delta.  1..(N-1) are output as delta.  If it\nhappens to choose N as plain, it does not have to uncompress and\nrecompress so the pack process would go very fast, but you would\nend up always having to apply a delta to bring rev N to N+1 on\ntop of the non-delta N to get to the latest blob in rev N+1, and\nyou typically would want to access rev N+1 blob more often.\n\nIn other words, the experimental reuse-packer would create a\nsuboptimal pack in such a case.  Not a big deal, though.\n\nWe may want an option to disable the optimization for\nweekly/monthly repacking.  git-daemon (or whatever runs\npack-objects via upload-pack) should use the default with the\noptimization, since this is so obviously faster.\n\n> Now that pack-creation went from bizarrely expensive to insanely cheap\n> (well, comparable to \"tar czf\" anyways), what's BCP for packing a\n> public repository? Always one mega-pack and never worry, or should one\n> still use incremental and sometimes overlapping pack-files?\n\nI would say an optimum single mega-pack would work the best, but\n\"repack -a -d\" to create the mega-pack _with_ the optimization\nmay have performance impact for users of resulting packs.\n\nOh, the traditional one finally came back after 11 minutes.\n"},{"id":"16300","messageId":"7vu0ay8v4f.fsf@assigned-by-dhcp.cox.net","threadId":"3342","inReplyTo":"7vbqx8m62q.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] pack-objects: reuse data from existing pack.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-02-17T04:30:40Z","receivedAt":"2006-02-17T04:30:40Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano <junkio@cox.net> writes:\n\n> When generating a new pack, notice if we have already the wanted\n> object in existing packs.  If the object has a delitified\n> representation, and its base object is also what we are going to\n> pack, then reuse the existing deltified representation\n> unconditionally, bypassing all the expensive find_deltas() and\n> try_deltas() routines.\n\nThis one has one nasty data corruption bug, which fortunately I\nthink I have figured out how to fix.  Please do not use it for\nyour production repository in the meantime.\n"},{"id":"16308","messageId":"7vlkwa6zk6.fsf@assigned-by-dhcp.cox.net","threadId":"3342","inReplyTo":"7vu0ay8v4f.fsf@assigned-by-dhcp.cox.net","subject":"[PATCH] pack-objects: finishing touches.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-02-17T10:37:45Z","receivedAt":"2006-02-17T10:37:45Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano <junkio@cox.net> writes:\n\n> This one has one nasty data corruption bug, which fortunately I\n> think I have figured out how to fix.  Please do not use it for\n> your production repository in the meantime.\n\nIt turns out that there wasn't a data corruption bug, but it can\ncreate a pack with delta chains whose length exceeds twice the\nspecified depth.  The data corruption bug was on my unpublished\nWIP and killed even before it hit \"pu\" ;-).  This addresses most\nof the remaining issues and has been merged to \"next\" tonight.\n\n-- >8 --\nThis introduces --no-reuse-delta option to disable reusing of\nexisting delta, which is a large part of the optimization\nintroduced by this series.  This may become necessary if\nrepeated repacking makes delta chain too long.  With this, the\noutput of the command becomes identical to that of the older\nimplementation.\n\nIt still allows reusing non-deltified representations; there is\nno point uncompressing and recompressing the whole text.\n\nIt also adds a couple more statistics output, while squelching\nit under -q flag, which the last round forgot to do.\n\nOne remaining minor issue when --no-reuse-delta option is not\nused is that it can create a delta chain that is deeper than\nspecified.\n\n    A<--B<--C<--D   E   F   G\n\nSuppose we have a delta chain A to D (A is stored in full either\nin a pack or as a loose object. B is depth1 delta relative to A,\nC is depth2 delta relative to B...) with loose objects E, F, G.\nAnd we are going to pack them.\n\nB, C and D are left as delta against A, B and C respectively.\nSo A, E, F, and G are examined, and let's say we decided to keep\nE expanded, and store the rest as deltas like this:\n\n\tE<--F<--G<--A\n\nOops.  We ended up making D a bit too deep, didn't we?  B, C and\nD form a chain on top of A!\n\nThis is because we did not know what the final depth of A would\nbe when checking objects and deciding to keep the existing\ndelta.\n\nTo prevent this from happening, we could say that A should be\nkept expanded.  But how would we tell that, cheaply?\n\nTo do this most precisely, after check_object() runs, each\nobject that is used as the base object of some existing delta\nneeds to be marked with the maximum depth of the objects we\ndecided to keep deltified (in this case, D is depth 3 relative\nto A, so if no other delta chain that is longer than 3 based on\nA exists, mark A with 3).  Then when attempting to deltify A, we\nwould take that number into account to see if the final delta\nchain that leads to D becomes too deep.\n\nHowever, this is a bit cumbersome to compute, so we would cheat\nand reduce the maximum depth for A arbitrarily to depth/4 in\nthis implementation.\n\nSigned-off-by: Junio C Hamano <junkio@cox.net>\n\n---\n\n Documentation/git-pack-objects.txt |   21 +++++++\n pack-objects.c                     |  102 +++++++++++++++++++++++++-----------\n 2 files changed, 91 insertions(+), 32 deletions(-)\n\n98885061623676a37575e59d7f7aff64072e3300\ndiff --git a/Documentation/git-pack-objects.txt b/Documentation/git-pack-objects.txt\nindex 2d67d39..4cb2e83 100644\n--- a/Documentation/git-pack-objects.txt\n+++ b/Documentation/git-pack-objects.txt\n@@ -8,7 +8,10 @@ git-pack-objects - Create a packed archi\n \n SYNOPSIS\n --------\n-'git-pack-objects' [--non-empty] [--local] [--incremental] [--window=N] [--depth=N] {--stdout | base-name} < object-list\n+[verse]\n+'git-pack-objects' [-q] [--no-reuse-delta] [--non-empty]\n+\t[--local] [--incremental] [--window=N] [--depth=N]\n+\t{--stdout | base-name} < object-list\n \n \n DESCRIPTION\n@@ -32,6 +35,10 @@ Placing both in the pack/ subdirectory o\n any of the directories on $GIT_ALTERNATE_OBJECT_DIRECTORIES)\n enables git to read from such an archive.\n \n+In a packed archive, an object is either stored as a compressed\n+whole, or as a difference from some other object.  The latter is\n+often called a delta.\n+\n \n OPTIONS\n -------\n@@ -74,6 +81,18 @@ base-name::\n         Only create a packed archive if it would contain at\n         least one object.\n \n+-q::\n+\tThis flag makes the command not to report its progress\n+\ton the standard error stream.\n+\n+--no-reuse-delta::\n+\tWhen creating a packed archive in a repository that\n+\thas existing packs, the command reuses existing deltas.\n+\tThis sometimes results in a slightly suboptimal pack.\n+\tThis flag tells the command not to reuse existing deltas\n+\tbut compute them from scratch.\n+\n+\n Author\n ------\n Written by Linus Torvalds <torvalds@osdl.org>\ndiff --git a/pack-objects.c b/pack-objects.c\nindex 70fb2af..38e1c99 100644\n--- a/pack-objects.c\n+++ b/pack-objects.c\n@@ -5,7 +5,7 @@\n #include \"csum-file.h\"\n #include <sys/time.h>\n \n-static const char pack_usage[] = \"git-pack-objects [-q] [--non-empty] [--local] [--incremental] [--window=N] [--depth=N] {--stdout | base-name} < object-list\";\n+static const char pack_usage[] = \"git-pack-objects [-q] [--no-reuse-delta] [--non-empty] [--local] [--incremental] [--window=N] [--depth=N] {--stdout | base-name} < object-list\";\n \n struct object_entry {\n \tunsigned char sha1[20];\n@@ -14,10 +14,11 @@ struct object_entry {\n \tunsigned int depth;\t/* delta depth */\n \tunsigned int hash;\t/* name hint hash */\n \tenum object_type type;\n+\tunsigned char edge;\t/* reused delta chain points at this entry. */\n+\tenum object_type in_pack_type;\t/* could be delta */\n \tunsigned long delta_size;\t/* delta data size (uncompressed) */\n \tstruct object_entry *delta;\t/* delta base object */\n \tstruct packed_git *in_pack; \t/* already in pack */\n-\tenum object_type in_pack_type;\t/* could be delta */\n \tunsigned int in_pack_offset;\n };\n \n@@ -36,6 +37,7 @@ struct object_entry {\n \n static unsigned char object_list_sha1[20];\n static int non_empty = 0;\n+static int no_reuse_delta = 0;\n static int local = 0;\n static int incremental = 0;\n static struct object_entry **sorted_by_sha, **sorted_by_type;\n@@ -75,7 +77,9 @@ static int pack_revindex_hashsz = 0;\n  * stats\n  */\n static int written = 0;\n+static int written_delta = 0;\n static int reused = 0;\n+static int reused_delta = 0;\n \n static int pack_revindex_ix(struct packed_git *p)\n {\n@@ -227,10 +231,23 @@ static unsigned long write_object(struct\n \tunsigned char header[10];\n \tunsigned hdrlen, datalen;\n \tenum object_type obj_type;\n+\tint to_reuse = 0;\n \n \tobj_type = entry->type;\n-\tif (!entry->in_pack ||\n-\t    (obj_type != entry->in_pack_type)) {\n+\tif (! entry->in_pack)\n+\t\tto_reuse = 0;\t/* can't reuse what we don't have */\n+\telse if (obj_type == OBJ_DELTA)\n+\t\tto_reuse = 1;\t/* check_object() decided it for us */\n+\telse if (obj_type != entry->in_pack_type)\n+\t\tto_reuse = 0;\t/* pack has delta which is unusable */\n+\telse if (entry->delta)\n+\t\tto_reuse = 0;\t/* we want to pack afresh */\n+\telse\n+\t\tto_reuse = 1;\t/* we have it in-pack undeltified,\n+\t\t\t\t * and we do not need to deltify it.\n+\t\t\t\t */\n+\n+\tif (! to_reuse) {\n \t\tbuf = read_sha1_file(entry->sha1, type, &size);\n \t\tif (!buf)\n \t\t\tdie(\"unable to read %s\", sha1_to_hex(entry->sha1));\n@@ -266,8 +283,12 @@ static unsigned long write_object(struct\n \t\tsha1write(f, buf, datalen);\n \t\tunuse_packed_git(p);\n \t\thdrlen = 0; /* not really */\n+\t\tif (obj_type == OBJ_DELTA)\n+\t\t\treused_delta++;\n \t\treused++;\n \t}\n+\tif (obj_type == OBJ_DELTA)\n+\t\twritten_delta++;\n \twritten++;\n \treturn hdrlen + datalen;\n }\n@@ -294,7 +315,6 @@ static void write_pack_file(void)\n \tint i;\n \tstruct sha1file *f;\n \tunsigned long offset;\n-\tunsigned long mb;\n \tstruct pack_header hdr;\n \n \tif (!base_name)\n@@ -357,10 +377,9 @@ static int add_object_entry(unsigned cha\n \tunsigned int idx = nr_objects;\n \tstruct object_entry *entry;\n \tstruct packed_git *p;\n-\tunsigned int found_offset;\n-\tstruct packed_git *found_pack;\n+\tunsigned int found_offset = 0;\n+\tstruct packed_git *found_pack = NULL;\n \n-\tfound_pack = NULL;\n \tfor (p = packed_git; p; p = p->next) {\n \t\tstruct pack_entry e;\n \t\tif (find_pack_entry_one(sha1, &e, p)) {\n@@ -420,32 +439,39 @@ static void check_object(struct object_e\n \tchar type[20];\n \n \tif (entry->in_pack) {\n+\t\tunsigned char base[20];\n+\t\tunsigned long size;\n+\t\tstruct object_entry *base_entry;\n+\n+\t\t/* We want in_pack_type even if we do not reuse delta.\n+\t\t * There is no point not reusing non-delta representations.\n+\t\t */\n+\t\tcheck_reuse_pack_delta(entry->in_pack,\n+\t\t\t\t       entry->in_pack_offset,\n+\t\t\t\t       base, &size,\n+\t\t\t\t       &entry->in_pack_type);\n+\n \t\t/* Check if it is delta, and the base is also an object\n \t\t * we are going to pack.  If so we will reuse the existing\n \t\t * delta.\n \t\t */\n-\t\tunsigned char base[20];\n-\t\tunsigned long size;\n-\t\tstruct object_entry *base_entry;\n-\t\tif (!check_reuse_pack_delta(entry->in_pack,\n-\t\t\t\t\t    entry->in_pack_offset,\n-\t\t\t\t\t    base, &size,\n-\t\t\t\t\t    &entry->in_pack_type) &&\n+\t\tif (!no_reuse_delta &&\n+\t\t    entry->in_pack_type == OBJ_DELTA &&\n \t\t    (base_entry = locate_object_entry(base))) {\n-\t\t\t/* We do not know depth at this point, but it\n-\t\t\t * does not matter.  Getting delta_chain_length\n-\t\t\t * with packed_object_info_detail() is not so\n-\t\t\t * expensive, so we could do that later if we\n-\t\t\t * wanted to.  Calling sha1_object_info to get\n-\t\t\t * the true size (and later an uncompressed\n-\t\t\t * representation) of deeply deltified object\n-\t\t\t * is quite expensive.\n+\n+\t\t\t/* Depth value does not matter - find_deltas()\n+\t\t\t * will never consider reused delta as the\n+\t\t\t * base object to deltify other objects\n+\t\t\t * against, in order to avoid circular deltas.\n \t\t\t */\n-\t\t\tentry->depth = 1;\n-\t\t\t/* uncompressed size */\n+\n+\t\t\t/* uncompressed size of the delta data */\n \t\t\tentry->size = entry->delta_size = size;\n \t\t\tentry->delta = base_entry;\n \t\t\tentry->type = OBJ_DELTA;\n+\n+\t\t\tbase_entry->edge = 1;\n+\n \t\t\treturn;\n \t\t}\n \t\t/* Otherwise we would do the usual */\n@@ -568,6 +594,13 @@ static int try_delta(struct unpacked *cu\n \tif (cur_entry->type != old_entry->type)\n \t\treturn -1;\n \n+\t/* If the current object is at edge, take the depth the objects\n+\t * that depend on the current object into account -- otherwise\n+\t * they would become too deep.\n+\t */\n+\tif (cur_entry->edge)\n+\t\tmax_depth /= 4;\n+\n \tsize = cur_entry->size;\n \tif (size < 50)\n \t\treturn -1;\n@@ -627,7 +660,7 @@ static void find_deltas(struct object_en\n \n \t\tif (entry->delta)\n \t\t\t/* This happens if we decided to reuse existing\n-\t\t\t * delta from a pack.\n+\t\t\t * delta from a pack.  \"!no_reuse_delta &&\" is implied.\n \t\t\t */\n \t\t\tcontinue;\n \n@@ -636,6 +669,7 @@ static void find_deltas(struct object_en\n \t\tn->data = read_sha1_file(entry->sha1, type, &size);\n \t\tif (size != entry->size)\n \t\t\tdie(\"object %s inconsistent object length (%lu vs %lu)\", sha1_to_hex(entry->sha1), size, entry->size);\n+\n \t\tj = window;\n \t\twhile (--j > 0) {\n \t\t\tunsigned int other_idx = idx + j;\n@@ -664,7 +698,7 @@ static void prepare_pack(int window, int\n \t\tfprintf(stderr, \"Packing %d objects\", nr_objects);\n \tget_object_details();\n \tif (progress)\n-\t\tfprintf(stderr, \".\");\n+\t\tfputc('.', stderr);\n \n \tsorted_by_type = create_sorted_list(type_size_sort);\n \tif (window && depth)\n@@ -694,8 +728,9 @@ static int reuse_cached_pack(unsigned ch\n \t\t}\n \t}\n \n-\tfprintf(stderr, \"Reusing %d objects pack %s\\n\", nr_objects,\n-\t\tsha1_to_hex(sha1));\n+\tif (progress)\n+\t\tfprintf(stderr, \"Reusing %d objects pack %s\\n\", nr_objects,\n+\t\t\tsha1_to_hex(sha1));\n \n \tif (pack_to_stdout) {\n \t\tif (copy_fd(ifd, 1))\n@@ -775,6 +810,10 @@ int main(int argc, char **argv)\n \t\t\t\tprogress = 0;\n \t\t\t\tcontinue;\n \t\t\t}\n+\t\t\tif (!strcmp(\"--no-reuse-delta\", arg)) {\n+\t\t\t\tno_reuse_delta = 1;\n+\t\t\t\tcontinue;\n+\t\t\t}\n \t\t\tif (!strcmp(\"--stdout\", arg)) {\n \t\t\t\tpack_to_stdout = 1;\n \t\t\t\tcontinue;\n@@ -850,7 +889,8 @@ int main(int argc, char **argv)\n \t\t\tputs(sha1_to_hex(object_list_sha1));\n \t\t}\n \t}\n-\tfprintf(stderr, \"Total %d, written %d, reused %d\\n\",\n-\t\tnr_objects, written, reused);\n+\tif (progress)\n+\t\tfprintf(stderr, \"Total %d, written %d (delta %d), reused %d (delta %d)\\n\",\n+\t\t\tnr_objects, written, written_delta, reused, reused_delta);\n \treturn 0;\n }\n-- \n1.2.1.g91016\n"},{"id":"16328","messageId":"Pine.LNX.4.64.0602170738390.916@g5.osdl.org","threadId":"3342","inReplyTo":"7vu0ay8v4f.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] pack-objects: reuse data from existing pack.","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-02-17T15:39:14Z","receivedAt":"2006-02-17T15:39:14Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 16 Feb 2006, Junio C Hamano wrote:\n> \n> This one has one nasty data corruption bug, which fortunately I\n> think I have figured out how to fix.\n\nCircular deltas? What else can go wrong?\n\n\t\tLinus\n"},{"id":"16333","messageId":"7v3bih4zns.fsf@assigned-by-dhcp.cox.net","threadId":"3342","inReplyTo":"Pine.LNX.4.64.0602170738390.916@g5.osdl.org","subject":"Re: [PATCH] pack-objects: reuse data from existing pack.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-02-17T18:18:31Z","receivedAt":"2006-02-17T18:18:31Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds <torvalds@osdl.org> writes:\n\n> On Thu, 16 Feb 2006, Junio C Hamano wrote:\n>> \n>> This one has one nasty data corruption bug, which fortunately I\n>> think I have figured out how to fix.\n>\n> Circular deltas? What else can go wrong?\n\nCircular deltas are prevented by not using deltified objects\ncheck_object() decides to keep in find_deltas(), so I do not\nthink it is an issue.\n"},{"id":"16365","messageId":"7vpslltb2f.fsf@assigned-by-dhcp.cox.net","threadId":"3342","inReplyTo":"7vlkwa6zk6.fsf@assigned-by-dhcp.cox.net","subject":"[PATCH] pack-objects: avoid delta chains that are too long.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-02-18T06:50:32Z","receivedAt":"2006-02-18T06:50:32Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"This tries to rework the solution for the excess delta chain\nproblem. An earlier commit worked it around ``cheaply'', but\nrepeated repacking risks unbound growth of delta chains.\n\nThis version counts the length of delta chain we are reusing\nfrom the existing pack, and makes sure a base object that has\nsufficiently long delta chain does not get deltified.\n\nSigned-off-by: Junio C Hamano <junkio@cox.net>\n\n---\n\n * This solves the problem by doing exactly what the previous\n   commit log suggested.  We limit the chain depth correctly, to\n   save the user of the resulting pack from suffering runtime\n   overhead.\n\n   Will be in \"next\" tonight.\n\n pack-objects.c |   43 +++++++++++++++++++++++++++++++++++--------\n 1 files changed, 35 insertions(+), 8 deletions(-)\n\ne4c9327a77bd59e85d4b17a612e78977d68773ee\ndiff --git a/pack-objects.c b/pack-objects.c\nindex 38e1c99..0c9f4c9 100644\n--- a/pack-objects.c\n+++ b/pack-objects.c\n@@ -10,16 +10,22 @@ static const char pack_usage[] = \"git-pa\n struct object_entry {\n \tunsigned char sha1[20];\n \tunsigned long size;\t/* uncompressed size */\n-\tunsigned long offset;\t/* offset into the final pack file (nonzero if already written) */\n+\tunsigned long offset;\t/* offset into the final pack file;\n+\t\t\t\t * nonzero if already written.\n+\t\t\t\t */\n \tunsigned int depth;\t/* delta depth */\n+\tunsigned int delta_limit;\t/* base adjustment for in-pack delta */\n \tunsigned int hash;\t/* name hint hash */\n \tenum object_type type;\n-\tunsigned char edge;\t/* reused delta chain points at this entry. */\n \tenum object_type in_pack_type;\t/* could be delta */\n \tunsigned long delta_size;\t/* delta data size (uncompressed) */\n \tstruct object_entry *delta;\t/* delta base object */\n \tstruct packed_git *in_pack; \t/* already in pack */\n \tunsigned int in_pack_offset;\n+\tstruct object_entry *delta_child; /* delitified objects who bases me */\n+\tstruct object_entry *delta_sibling; /* other deltified objects who\n+\t\t\t\t\t     * uses the same base as me\n+\t\t\t\t\t     */\n };\n \n /*\n@@ -470,7 +476,8 @@ static void check_object(struct object_e\n \t\t\tentry->delta = base_entry;\n \t\t\tentry->type = OBJ_DELTA;\n \n-\t\t\tbase_entry->edge = 1;\n+\t\t\tentry->delta_sibling = base_entry->delta_child;\n+\t\t\tbase_entry->delta_child = entry;\n \n \t\t\treturn;\n \t\t}\n@@ -513,15 +520,32 @@ static void hash_objects(void)\n \t}\n }\n \n+static unsigned int check_delta_limit(struct object_entry *me, unsigned int n)\n+{\n+\tstruct object_entry *child = me->delta_child;\n+\tunsigned int m = n;\n+\twhile (child) {\n+\t\tunsigned int c = check_delta_limit(child, n + 1);\n+\t\tif (m < c)\n+\t\t\tm = c;\n+\t\tchild = child->delta_sibling;\n+\t}\n+\treturn m;\n+}\n+\n static void get_object_details(void)\n {\n \tint i;\n-\tstruct object_entry *entry = objects;\n+\tstruct object_entry *entry;\n \n \thash_objects();\n \tprepare_pack_ix();\n-\tfor (i = 0; i < nr_objects; i++)\n-\t\tcheck_object(entry++);\n+\tfor (i = 0, entry = objects; i < nr_objects; i++, entry++)\n+\t\tcheck_object(entry);\n+\tfor (i = 0, entry = objects; i < nr_objects; i++, entry++)\n+\t\tif (!entry->delta && entry->delta_child)\n+\t\t\tentry->delta_limit =\n+\t\t\t\tcheck_delta_limit(entry, 1);\n }\n \n typedef int (*entry_sort_t)(const struct object_entry *, const struct object_entry *);\n@@ -598,8 +622,11 @@ static int try_delta(struct unpacked *cu\n \t * that depend on the current object into account -- otherwise\n \t * they would become too deep.\n \t */\n-\tif (cur_entry->edge)\n-\t\tmax_depth /= 4;\n+\tif (cur_entry->delta_child) {\n+\t\tif (max_depth <= cur_entry->delta_limit)\n+\t\t\treturn 0;\n+\t\tmax_depth -= cur_entry->delta_limit;\n+\t}\n \n \tsize = cur_entry->size;\n \tif (size < 50)\n-- \n1.2.1.g9b132\n"}]}