{"thread":{"id":"32200","subject":"[RFC] pack-objects: compression level for non-blobs","startedAt":"2012-11-26T06:25:54Z","lastAt":"2013-01-02T02:23:39Z","messageCount":19,"participants":["David Michael Barr","Jeff King","Nguyen Thai Ngoc Duy","Shawn Pearce","Duy Nguyen","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"203858","messageId":"1353911154-23495-1-git-send-email-b@rr-dav.id.au","threadId":"32200","inReplyTo":null,"subject":"[RFC] pack-objects: compression level for non-blobs","fromName":"David Michael Barr","fromEmail":"b@rr-dav.id.au","sentAt":"2012-11-26T06:25:54Z","receivedAt":"2012-11-26T06:25:54Z","isPatch":false,"sender":{"key":"b@rr-dav.id.au","avatar":"https://gravatar.com/avatar/1c0f0df262aa1749c478ee3586cef5da6d58382c06cb220882b7ef9b93cbec6f?d=mp&s=160"},"body":"Add config pack.graphcompression similar to pack.compression.\nApplies to non-blob objects and if unspecified falls back to pack.compression.\n\nWe may identify objects compressed with level 0 by their leading bytes.\nUse this to force recompression when the source and target levels mismatch.\nLimit its application to when the config pack.graphcompression is set.\n\nSigned-off-by: David Michael Barr <b@rr-dav.id.au>\n---\n builtin/pack-objects.c | 49 +++++++++++++++++++++++++++++++++++++++++++++----\n 1 file changed, 45 insertions(+), 4 deletions(-)\n\n I started working on this just before taking a vacation,\n so it's been a little while coming.\n\n The intent is to allow selective recompression of pack data.\n For small objects/deltas the overhead of deflate is significant.\n This may improve read performance for the object graph.\n\n I ran some unscientific experiments with the chromium repository.\n With pack.graphcompression = 0, there was a 2.7% increase in pack size.\n I saw a 35% improvement with cold caches and 43% otherwise on git log --raw.\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex f069462..9518daf 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -40,6 +40,7 @@ struct object_entry {\n \tunsigned long z_delta_size;\t/* delta data size (compressed) */\n \tunsigned int hash;\t/* name hint hash */\n \tenum object_type type;\n+\tenum object_type actual_type;\n \tenum object_type in_pack_type;\t/* could be delta */\n \tunsigned char in_pack_header_size;\n \tunsigned char preferred_base; /* we do not pack this, but is available\n@@ -81,6 +82,8 @@ static int num_preferred_base;\n static struct progress *progress_state;\n static int pack_compression_level = Z_DEFAULT_COMPRESSION;\n static int pack_compression_seen;\n+static int pack_graph_compression_level = Z_DEFAULT_COMPRESSION;\n+static int pack_graph_compression_seen;\n \n static unsigned long delta_cache_size = 0;\n static unsigned long max_delta_cache_size = 256 * 1024 * 1024;\n@@ -125,14 +128,14 @@ static void *get_delta(struct object_entry *entry)\n \treturn delta_buf;\n }\n \n-static unsigned long do_compress(void **pptr, unsigned long size)\n+static unsigned long do_compress(void **pptr, unsigned long size, int level)\n {\n \tgit_zstream stream;\n \tvoid *in, *out;\n \tunsigned long maxsize;\n \n \tmemset(&stream, 0, sizeof(stream));\n-\tgit_deflate_init(&stream, pack_compression_level);\n+\tgit_deflate_init(&stream, level);\n \tmaxsize = git_deflate_bound(&stream, size);\n \n \tin = *pptr;\n@@ -191,6 +194,18 @@ static unsigned long write_large_blob_data(struct git_istream *st, struct sha1fi\n \treturn olen;\n }\n \n+static int check_pack_compressed(struct packed_git *p,\n+\t\tstruct pack_window **w_curs,\n+\t\toff_t offset)\n+{\n+\tunsigned long avail;\n+\tint compressed = 0;\n+\tunsigned char *in = use_pack(p, w_curs, offset, &avail);\n+\tif (avail >= 3)\n+\t\tcompressed = !!(in[2] & 0x6);\n+\treturn compressed;\n+}\n+\n /*\n  * we are going to reuse the existing object data as is.  make\n  * sure it is not corrupt.\n@@ -240,6 +255,8 @@ static void copy_pack_data(struct sha1file *f,\n \t}\n }\n \n+#define compression_level(type) ((type) && (type) != OBJ_BLOB ? pack_graph_compression_level : pack_compression_level)\n+\n /* Return 0 if we will bust the pack-size limit */\n static unsigned long write_no_reuse_object(struct sha1file *f, struct object_entry *entry,\n \t\t\t\t\t   unsigned long limit, int usable_delta)\n@@ -286,7 +303,7 @@ static unsigned long write_no_reuse_object(struct sha1file *f, struct object_ent\n \telse if (entry->z_delta_size)\n \t\tdatalen = entry->z_delta_size;\n \telse\n-\t\tdatalen = do_compress(&buf, size);\n+\t\tdatalen = do_compress(&buf, size, compression_level(entry->actual_type));\n \n \t/*\n \t * The object header is a byte of 'type' followed by zero or\n@@ -379,6 +396,13 @@ static unsigned long write_reuse_object(struct sha1file *f, struct object_entry\n \toffset += entry->in_pack_header_size;\n \tdatalen -= entry->in_pack_header_size;\n \n+\tif (!pack_to_stdout &&\n+\t    pack_graph_compression_seen &&\n+\t    check_pack_compressed(p, &w_curs, offset) != !!compression_level(entry->actual_type)) {\n+\t\tunuse_pack(&w_curs);\n+\t\treturn write_no_reuse_object(f, entry, limit, usable_delta);\n+\t}\n+\n \tif (!pack_to_stdout && p->index_version == 1 &&\n \t    check_pack_inflate(p, &w_curs, offset, datalen, entry->size)) {\n \t\terror(\"corrupt packed object for %s\", sha1_to_hex(entry->idx.sha1));\n@@ -955,6 +979,8 @@ static int add_object_entry(const unsigned char *sha1, enum object_type type,\n \tmemset(entry, 0, sizeof(*entry));\n \thashcpy(entry->idx.sha1, sha1);\n \tentry->hash = hash;\n+\tif (pack_graph_compression_seen)\n+\t\tentry->actual_type = sha1_object_info(sha1, NULL);\n \tif (type)\n \t\tentry->type = type;\n \tif (exclude)\n@@ -1758,7 +1784,8 @@ static void find_deltas(struct object_entry **list, unsigned *list_size,\n \t\t */\n \t\tif (entry->delta_data && !pack_to_stdout) {\n \t\t\tentry->z_delta_size = do_compress(&entry->delta_data,\n-\t\t\t\t\t\t\t  entry->delta_size);\n+\t\t\t\t\t\t\t  entry->delta_size,\n+\t\t\t\t\t\t\t  compression_level(entry->actual_type));\n \t\t\tcache_lock();\n \t\t\tdelta_cache_size -= entry->delta_size;\n \t\t\tdelta_cache_size += entry->z_delta_size;\n@@ -2159,6 +2186,16 @@ static int git_pack_config(const char *k, const char *v, void *cb)\n \t\t\t    pack_idx_opts.version);\n \t\treturn 0;\n \t}\n+\tif (!strcmp(k, \"pack.graphcompression\")) {\n+\t\tint level = git_config_int(k, v);\n+\t\tif (level == -1)\n+\t\t\tlevel = Z_DEFAULT_COMPRESSION;\n+\t\telse if (level < 0 || level > Z_BEST_COMPRESSION)\n+\t\t\tdie(\"bad pack graph compression level %d\", level);\n+\t\tpack_graph_compression_level = level;\n+\t\tpack_graph_compression_seen = 1;\n+\t\treturn 0;\n+\t}\n \treturn git_default_config(k, v, cb);\n }\n \n@@ -2519,6 +2556,10 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix)\n \targc = parse_options(argc, argv, prefix, pack_objects_options,\n \t\t\t     pack_usage, 0);\n \n+\t/* Fall back after option parsing to catch --compression */\n+\tif (!pack_graph_compression_seen)\n+\t\tpack_graph_compression_level = pack_compression_level;\n+\n \tif (argc) {\n \t\tbase_name = argv[0];\n \t\targc--;\n-- \n1.8.0\n"},{"id":"203871","messageId":"575D346F7B9B41D4848315209DF07302@rr-dav.id.au","threadId":"32200","inReplyTo":"1353911154-23495-1-git-send-email-b@rr-dav.id.au","subject":"Re: [RFC] pack-objects: compression level for non-blobs","fromName":"David Michael Barr","fromEmail":"b@rr-dav.id.au","sentAt":"2012-11-26T12:35:48Z","receivedAt":"2012-11-26T12:35:48Z","isPatch":false,"sender":{"key":"b@rr-dav.id.au","avatar":"https://gravatar.com/avatar/1c0f0df262aa1749c478ee3586cef5da6d58382c06cb220882b7ef9b93cbec6f?d=mp&s=160"},"body":"> Add config pack.graphcompression similar to pack.compression.\n> Applies to non-blob objects and if unspecified falls back to pack.compression.\n> \n> We may identify objects compressed with level 0 by their leading bytes.\n> Use this to force recompression when the source and target levels mismatch.\n> Limit its application to when the config pack.graphcompression is set.\n> \n> Signed-off-by: David Michael Barr <b@rr-dav.id.au (mailto:b@rr-dav.id.au)>\n> ---\n> builtin/pack-objects.c | 49 +++++++++++++++++++++++++++++++++++++++++++++----\n> 1 file changed, 45 insertions(+), 4 deletions(-)\n> \n> I started working on this just before taking a vacation,\n> so it's been a little while coming.\n> \n> The intent is to allow selective recompression of pack data.\n> For small objects/deltas the overhead of deflate is significant.\n> This may improve read performance for the object graph.\n> \n> I ran some unscientific experiments with the chromium repository.\n> With pack.graphcompression = 0, there was a 2.7% increase in pack size.\n> I saw a 35% improvement with cold caches and 43% otherwise on git log --raw.\n\nI neglected to mention that this is a WIP. I get failures with certain repositories: \n\n    fatal: delta size changed\n\n--\nDavid Michael Barr\n"},{"id":"205625","messageId":"20121229004104.GA24828@sigill.intra.peff.net","threadId":"32200","inReplyTo":"1353911154-23495-1-git-send-email-b@rr-dav.id.au","subject":"Re: [RFC] pack-objects: compression level for non-blobs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-12-29T00:41:05Z","receivedAt":"2012-12-29T00:41:05Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Nov 26, 2012 at 05:25:54PM +1100, David Michael Barr wrote:\n\n>  The intent is to allow selective recompression of pack data.\n>  For small objects/deltas the overhead of deflate is significant.\n>  This may improve read performance for the object graph.\n> \n>  I ran some unscientific experiments with the chromium repository.\n>  With pack.graphcompression = 0, there was a 2.7% increase in pack size.\n>  I saw a 35% improvement with cold caches and 43% otherwise on git log --raw.\n\nThere wasn't much response to this, but those numbers are encouraging. I\nwas curious to replicate them, as well as to break it down by trees and\ncommits. I also wanted to test on more repositories, as well as on both\nSSDs and spinning disks (for cold-cache numbers). Maybe that will catch\nmore people's interest.\n\nAs you mentioned in your follow-up, I ran into the \"delta size changed\"\nproblem. Not sure if it is related, but I noticed here:\n\n> @@ -379,6 +396,13 @@ static unsigned long write_reuse_object(struct sha1file *f, struct object_entry\n>  \toffset += entry->in_pack_header_size;\n>  \tdatalen -= entry->in_pack_header_size;\n>  \n> +\tif (!pack_to_stdout &&\n> +\t    pack_graph_compression_seen &&\n> +\t    check_pack_compressed(p, &w_curs, offset) != !!compression_level(entry->actual_type)) {\n> +\t\tunuse_pack(&w_curs);\n> +\t\treturn write_no_reuse_object(f, entry, limit, usable_delta);\n> +\t}\n> +\n\n...that we seem to re-compress more than necessary. If I instrument that\nblock with a message to stderr and run \"git repack -ad\" repeatedly\nwithout changing the config in between, runs after the first should\nnever re-compress, right? But they seem to. I'm not sure if your\ncheck_pack_compressed heuristic is off or something else. It may or may\nnot be related to the \"delta sized change\" failure.\n\nBut we can leave this side a bit for a moment. Conceptually there are\ntwo interesting things going on in your patch:\n\n  1. Per-object-type compression levels\n\n  2. Auto-recompression when levels change.\n\nWe can figure out (2) later. The meat of the idea is (1), and the patch\nfor that is much simpler. In fact, we can test it out with entirely\nstock git by creating separate tree, commit, and blob packs, each with\ndifferent compression. So that's what I did for my timing, just to keep\nthings simple.\n\nI timed git.git, linux-2.6.git, and WebKit.git. For each repo, I tested\nit with four pack compression scenarios:\n\n  1. all objects at -1 (zlib default)\n\n  2. commits at 0, everything else at -1\n\n  3. trees at 0, everything else at -1\n\n  4. commits and trees at 0, everything else at -1\n\nFor each scenario, I timed \"git rev-list --count --all\" to traverse all\ncommits (which roughly models things like merge-base, ahead/behind\ncounts, etc), and then the same thing with \"--objects\" to traverse all\nobjects (which would roughly match what \"git prune\" or the \"counting\nobjects\" phase of packing would do). For each command, I timed both warm\nand cold disk cache (the latter via \"echo 3 >/proc/sys/vm/drop_caches\").\nEach timing is a best-of-five.  The timings were done on a machine with\nan SSD (which probably matters for cold-cache; I have some spinning disk\nnumbers later).\n\nHere are the git.git numbers:\n\n Pack  | Size          |  Cold Revs  |  Warm Revs  | Cold Objects | Warm Objects\n-------+---------------+-------------+-------------+--------------+--------------\n  none |  41.48        | 0.78        | 0.33        |  2.35        |  1.94       \ncommit |  49.34 (+18%) | 0.57 (-26%) | 0.09 (-74%) |  2.48  (+5%) |  1.70 (-12%)\n  tree |  45.43  (+9%) | 0.80  (+3%) | 0.33   (0%) |  2.11  (-9%) |  1.74 (-10%)\n  both |  53.31 (+28%) | 0.79  (+1%) | 0.08 (-75%) |  2.27  (-3%) |  1.49 (-23%)\n\nThe pack column specifies which scenario (i.e., what was left\nuncompressed).  The size column is the size of the object-dir (in\nmegabytes). The other columns are times to run each command in\nwall-clock seconds. Percentages are comparisons to the baseline \"none\"\ncase (i.e., the status quo).\n\nSo you can see that it's a big win for warm-cache pure-commit\ntraversals. As a sanity check, we can see that the tree-only case is not\nhelped at all there (because we do not look at trees at all). The\ncold-cache case is helped, too, but that benefit goes away (and even\nhurts slightly, but that is probably within the noise) when we also\nleave the trees uncompressed.\n\nThe full-objects traversal doesn't fare quite as well, though there's\nstill some improvement. I think it argues for leaving both uncompressed,\nas the warm case really benefits when both are uncompressed. You lose\nthe cold-cache benefits in the revs-only case, though.\n\nHere are the numbers for linux-2.6.git:\n\n Pack  | Size          |  Cold Revs  |  Warm Revs  | Cold Objects | Warm Objects\n-------+---------------+-------------+-------------+--------------+--------------\n  none | 864.61        | 8.66        | 4.07        | 42.76        | 36.32       \ncommit | 970.46 (+12%) | 8.87  (+2%) | 1.02 (-74%) | 42.94   (0%) | 33.43  (-7%)\n  tree | 895.37  (+3%) | 9.08  (+4%) | 4.07   (0%) | 36.01 (-15%) | 29.62 (-18%)\n  both | 1001.25 (+15%) | 8.90  (+2%) | 1.03 (-74%) | 35.57 (-16%) | 26.25 (-27%)\n\nSimilar warm-cache numbers, but the cold cache for the revs-only case is\nhurt a little bit more.\n\nAnd here's WebKit.git (sizes are in gigabytes this time):\n\n Pack  | Size          |  Cold Revs  |  Warm Revs  | Cold Objects | Warm Objects\n-------+---------------+-------------+-------------+--------------+--------------\n  none |   3.46        | 1.61        | 1.38        | 20.46        | 18.72       \ncommit |   3.54  (+2%) | 1.42 (-11%) | 0.34 (-75%) | 20.42   (0%) | 17.57  (-6%)\n  tree |   3.59  (+3%) | 1.61   (0%) | 1.39   (0%) | 16.01 (-21%) | 14.00 (-25%)\n  both |   3.67  (+6%) | 1.45 (-10%) | 0.34 (-75%) | 15.94 (-22%) | 12.91 (-31%)\n\nPretty similar again (slightly better on the full object traversal).\n\nAnd finally, for comparison, here are the numbers from a (much slower)\nmachine that has spinning disks (albeit in a mirrored raid, which should\nimprove read times) on git.git:\n\n Pack  | Size          |  Cold Revs  |  Warm Revs  | Cold Objects | Warm Objects\n-------+---------------+-------------+-------------+--------------+--------------\n  none |  41.35        | 1.85        | 0.64        |  5.58        |  3.91       \ncommit |  49.23 (+19%) | 1.94  (+4%) | 0.14 (-77%) |  5.51  (-1%) |  3.40 (-12%)\n  tree |  45.27  (+9%) | 1.78  (-3%) | 0.64   (0%) |  5.13  (-8%) |  3.53  (-9%)\n  both |  53.16 (+28%) | 1.83  (-1%) | 0.14 (-77%) |  4.96 (-11%) |  3.32 (-14%)\n\nSurprisingly not all that different than the SSD times. Which may mean I\nscrewed something up. I'm happy to make my test harness available if\nanybody else feels like timing on their repos or machines. But it does\npoint to potentially leaving commits uncompressed, and possibly trees.\n\nI wonder if we could do even better, though. For a traversal, we only\nneed to look at the commit header. We could potentially do a progressive\ninflate and stop before getting to the commit message (which is the bulk\nof the data, and the part that is most likely to benefit from\ncompression).\n\n-Peff\n"},{"id":"205634","messageId":"CACsJy8D_E0shqJAvZH7xqij6F4a6qUxkUPNcZL=0yX5w9bLd_g@mail.gmail.com","threadId":"32200","inReplyTo":"20121229004104.GA24828@sigill.intra.peff.net","subject":"Re: [RFC] pack-objects: compression level for non-blobs","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-12-29T04:34:09Z","receivedAt":"2012-12-29T04:34:09Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Sat, Dec 29, 2012 at 7:41 AM, Jeff King <peff@peff.net> wrote:\n> I wonder if we could do even better, though. For a traversal, we only\n> need to look at the commit header. We could potentially do a progressive\n> inflate and stop before getting to the commit message (which is the bulk\n> of the data, and the part that is most likely to benefit from\n> compression).\n\nCommit cache should solve this efficiently as it also eliminates\nparsing cost. We discussed this last time as a side topic of the\nreachability bitmap feature.\n-- \nDuy\n"},{"id":"205636","messageId":"20121229050707.GA14475@sigill.intra.peff.net","threadId":"32200","inReplyTo":"CACsJy8D_E0shqJAvZH7xqij6F4a6qUxkUPNcZL=0yX5w9bLd_g@mail.gmail.com","subject":"Re: [RFC] pack-objects: compression level for non-blobs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-12-29T05:07:07Z","receivedAt":"2012-12-29T05:07:07Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Dec 29, 2012 at 11:34:09AM +0700, Nguyen Thai Ngoc Duy wrote:\n\n> On Sat, Dec 29, 2012 at 7:41 AM, Jeff King <peff@peff.net> wrote:\n> > I wonder if we could do even better, though. For a traversal, we only\n> > need to look at the commit header. We could potentially do a progressive\n> > inflate and stop before getting to the commit message (which is the bulk\n> > of the data, and the part that is most likely to benefit from\n> > compression).\n> \n> Commit cache should solve this efficiently as it also eliminates\n> parsing cost. We discussed this last time as a side topic of the\n> reachability bitmap feature.\n\nI agree that a commit cache would solve this (though it can not help the\ntree traversal). But just dropping the compression (or doing partial\ndecompression when we only care about the beginning part) is way less\ncode and complexity. There's no cache to manage.\n\n-Peff\n"},{"id":"205637","messageId":"CACsJy8AN3y_4wcZ_w0zz+ZAaDasRT-+h8vA_fp2j4+FL00dbLw@mail.gmail.com","threadId":"32200","inReplyTo":"20121229050707.GA14475@sigill.intra.peff.net","subject":"Re: [RFC] pack-objects: compression level for non-blobs","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-12-29T05:25:04Z","receivedAt":"2012-12-29T05:25:04Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Sat, Dec 29, 2012 at 12:07 PM, Jeff King <peff@peff.net> wrote:\n> On Sat, Dec 29, 2012 at 11:34:09AM +0700, Nguyen Thai Ngoc Duy wrote:\n>\n>> On Sat, Dec 29, 2012 at 7:41 AM, Jeff King <peff@peff.net> wrote:\n>> > I wonder if we could do even better, though. For a traversal, we only\n>> > need to look at the commit header. We could potentially do a progressive\n>> > inflate and stop before getting to the commit message (which is the bulk\n>> > of the data, and the part that is most likely to benefit from\n>> > compression).\n>>\n>> Commit cache should solve this efficiently as it also eliminates\n>> parsing cost. We discussed this last time as a side topic of the\n>> reachability bitmap feature.\n>\n> I agree that a commit cache would solve this (though it can not help the\n> tree traversal).\n\nYeah, caching trees efficiently is not easy.\n\n> But just dropping the compression (or doing partial\n> decompression when we only care about the beginning part) is way less\n> code and complexity.\n\nI think I tried the partial decompression for commit header and it did\nnot help much (or I misremember it, not so sure).\n\n> There's no cache to manage.\n\nIf reachability bitmap is implemented, we'll have per-pack cache\ninfrastructure ready, so less work there for commit cache.\n-- \nDuy\n"},{"id":"205638","messageId":"20121229052747.GA14928@sigill.intra.peff.net","threadId":"32200","inReplyTo":"CACsJy8AN3y_4wcZ_w0zz+ZAaDasRT-+h8vA_fp2j4+FL00dbLw@mail.gmail.com","subject":"Re: [RFC] pack-objects: compression level for non-blobs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-12-29T05:27:47Z","receivedAt":"2012-12-29T05:27:47Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Dec 29, 2012 at 12:25:04PM +0700, Nguyen Thai Ngoc Duy wrote:\n\n> > But just dropping the compression (or doing partial\n> > decompression when we only care about the beginning part) is way less\n> > code and complexity.\n> \n> I think I tried the partial decompression for commit header and it did\n> not help much (or I misremember it, not so sure).\n\nI'll see if I can dig up the reference, as it was something I was going\nto look at next.\n\n> > There's no cache to manage.\n> \n> If reachability bitmap is implemented, we'll have per-pack cache\n> infrastructure ready, so less work there for commit cache.\n\nTrue. I don't want to dissuade you from doing any commit cache work. I\nonly wanted to point out that this alternative may have merit because of\nits simplicity (so we can use it until a caching solution exists, or\neven after, if managing the cache has downsides).\n\n-Peff\n"},{"id":"205644","messageId":"20121229090558.GA31291@sigill.intra.peff.net","threadId":"32200","inReplyTo":"20121229052747.GA14928@sigill.intra.peff.net","subject":"Re: [RFC] pack-objects: compression level for non-blobs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-12-29T09:05:58Z","receivedAt":"2012-12-29T09:05:58Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Dec 29, 2012 at 12:27:47AM -0500, Jeff King wrote:\n\n> > I think I tried the partial decompression for commit header and it did\n> > not help much (or I misremember it, not so sure).\n> \n> I'll see if I can dig up the reference, as it was something I was going\n> to look at next.\n\nI tried the simple patch below, but it actually made things slower!  I'm\nassuming it is because the streaming setup is not micro-optimized very\nwell. A custom read_sha1_until_blank_line() could probably do better.\n\ndiff --git a/commit.c b/commit.c\nindex e8eb0ae..efd6c06 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -8,6 +8,7 @@\n #include \"notes.h\"\n #include \"gpg-interface.h\"\n #include \"mergesort.h\"\n+#include \"streaming.h\"\n \n static struct commit_extra_header *read_commit_extra_header_lines(const char *buf, size_t len, const char **);\n \n@@ -306,6 +307,39 @@ int parse_commit_buffer(struct commit *item, const void *buffer, unsigned long s\n \treturn 0;\n }\n \n+static void *read_commit_header(const unsigned char *sha1,\n+\t\t\t\tenum object_type *type,\n+\t\t\t\tunsigned long *size)\n+{\n+\tstatic const int chunk_size = 256;\n+\tstruct strbuf buf = STRBUF_INIT;\n+\tstruct git_istream *st;\n+\n+\tst = open_istream(sha1, type, size, NULL);\n+\tif (!st)\n+\t\treturn NULL;\n+\twhile (1) {\n+\t\tsize_t start = buf.len;\n+\t\tssize_t readlen;\n+\n+\t\tstrbuf_grow(&buf, chunk_size);\n+\t\treadlen = read_istream(st, buf.buf + start, chunk_size);\n+\t\tbuf.buf[start + readlen + 1] = '\\0';\n+\t\tbuf.len += readlen;\n+\n+\t\tif (readlen < 0) {\n+\t\t\tclose_istream(st);\n+\t\t\tstrbuf_release(&buf);\n+\t\t\treturn NULL;\n+\t\t}\n+\t\tif (!readlen || strstr(buf.buf + start, \"\\n\\n\"))\n+\t\t\tbreak;\n+\t}\n+\n+\tclose_istream(st);\n+\treturn strbuf_detach(&buf, size);\n+}\n+\n int parse_commit(struct commit *item)\n {\n \tenum object_type type;\n@@ -317,7 +351,11 @@ int parse_commit(struct commit *item)\n \t\treturn -1;\n \tif (item->object.parsed)\n \t\treturn 0;\n-\tbuffer = read_sha1_file(item->object.sha1, &type, &size);\n+\n+\tif (!save_commit_buffer)\n+\t\tbuffer = read_commit_header(item->object.sha1, &type, &size);\n+\telse\n+\t\tbuffer = read_sha1_file(item->object.sha1, &type, &size);\n \tif (!buffer)\n \t\treturn error(\"Could not read %s\",\n \t\t\t     sha1_to_hex(item->object.sha1));\n"},{"id":"205645","messageId":"20121229094816.GA23396@sigill.intra.peff.net","threadId":"32200","inReplyTo":"20121229090558.GA31291@sigill.intra.peff.net","subject":"Re: [RFC] pack-objects: compression level for non-blobs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-12-29T09:48:17Z","receivedAt":"2012-12-29T09:48:17Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Dec 29, 2012 at 04:05:58AM -0500, Jeff King wrote:\n\n> On Sat, Dec 29, 2012 at 12:27:47AM -0500, Jeff King wrote:\n> \n> > > I think I tried the partial decompression for commit header and it did\n> > > not help much (or I misremember it, not so sure).\n> > \n> > I'll see if I can dig up the reference, as it was something I was going\n> > to look at next.\n> \n> I tried the simple patch below, but it actually made things slower!  I'm\n> assuming it is because the streaming setup is not micro-optimized very\n> well. A custom read_sha1_until_blank_line() could probably do better.\n\nSomething like the patch below, which does speed things up. But not\nnearly as much as I'd hoped:\n\n  [before]\n  $ best-of-five git rev-list --count --all\n  real    0m4.197s\n  user    0m4.112s\n  sys     0m0.072s\n\n  [after]\n  $ best-of-five git rev-list --count --all\n  real    0m3.782s\n  user    0m3.708s\n  sys     0m0.064s\n\nOnly about a 10% speedup (versus ~75% with uncompressed commits).\n\n---\ndiff --git a/cache.h b/cache.h\nindex 18fdd18..a494d3b 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -724,6 +724,7 @@ int offset_1st_component(const char *path);\n \n /* object replacement */\n #define READ_SHA1_FILE_REPLACE 1\n+#define READ_SHA1_FILE_HEADER 2\n extern void *read_sha1_file_extended(const unsigned char *sha1, enum object_type *type, unsigned long *size, unsigned flag);\n static inline void *read_sha1_file(const unsigned char *sha1, enum object_type *type, unsigned long *size)\n {\n@@ -1059,7 +1060,7 @@ extern int is_pack_valid(struct packed_git *);\n extern off_t nth_packed_object_offset(const struct packed_git *, uint32_t);\n extern off_t find_pack_entry_one(const unsigned char *, struct packed_git *);\n extern int is_pack_valid(struct packed_git *);\n-extern void *unpack_entry(struct packed_git *, off_t, enum object_type *, unsigned long *);\n+extern void *unpack_entry(struct packed_git *, off_t, enum object_type *, unsigned long *, int);\n extern unsigned long unpack_object_header_buffer(const unsigned char *buf, unsigned long len, enum object_type *type, unsigned long *sizep);\n extern unsigned long get_size_from_delta(struct packed_git *, struct pack_window **, off_t);\n extern int unpack_object_header(struct packed_git *, struct pack_window **, off_t *, unsigned long *);\ndiff --git a/commit.c b/commit.c\nindex e8eb0ae..0a088dc 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -312,12 +312,13 @@ int parse_commit(struct commit *item)\n \tvoid *buffer;\n \tunsigned long size;\n \tint ret;\n+\tint flags = save_commit_buffer ? 0 : READ_SHA1_FILE_HEADER;\n \n \tif (!item)\n \t\treturn -1;\n \tif (item->object.parsed)\n \t\treturn 0;\n-\tbuffer = read_sha1_file(item->object.sha1, &type, &size);\n+\tbuffer = read_sha1_file_extended(item->object.sha1, &type, &size, flags);\n \tif (!buffer)\n \t\treturn error(\"Could not read %s\",\n \t\t\t     sha1_to_hex(item->object.sha1));\ndiff --git a/fast-import.c b/fast-import.c\nindex c2a814e..a140d57 100644\n--- a/fast-import.c\n+++ b/fast-import.c\n@@ -1303,7 +1303,7 @@ static void *gfi_unpack_entry(\n \t\t */\n \t\tp->pack_size = pack_size + 20;\n \t}\n-\treturn unpack_entry(p, oe->idx.offset, &type, sizep);\n+\treturn unpack_entry(p, oe->idx.offset, &type, sizep, 0);\n }\n \n static const char *get_mode(const char *str, uint16_t *modep)\ndiff --git a/pack-check.c b/pack-check.c\nindex 63a595c..e4a43c0 100644\n--- a/pack-check.c\n+++ b/pack-check.c\n@@ -116,7 +116,7 @@ static int verify_packfile(struct packed_git *p,\n \t\t\t\t\t    sha1_to_hex(entries[i].sha1),\n \t\t\t\t\t    p->pack_name, (uintmax_t)offset);\n \t\t}\n-\t\tdata = unpack_entry(p, entries[i].offset, &type, &size);\n+\t\tdata = unpack_entry(p, entries[i].offset, &type, &size, 0);\n \t\tif (!data)\n \t\t\terr = error(\"cannot unpack %s from %s at offset %\"PRIuMAX\"\",\n \t\t\t\t    sha1_to_hex(entries[i].sha1), p->pack_name,\ndiff --git a/sha1_file.c b/sha1_file.c\nindex 40b2329..1f1f31a 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -1469,16 +1469,19 @@ static void *unpack_sha1_file(void *map, unsigned long mapsize, enum object_type\n \treturn *hdr ? -1 : type_from_string(type);\n }\n \n-static void *unpack_sha1_file(void *map, unsigned long mapsize, enum object_type *type, unsigned long *size, const unsigned char *sha1)\n+static void *unpack_sha1_file(void *map, unsigned long mapsize, enum object_type *type, unsigned long *size, const unsigned char *sha1, int stop_at_blank)\n {\n \tint ret;\n \tgit_zstream stream;\n-\tchar hdr[8192];\n+\tchar hdr[512];\n \n \tret = unpack_sha1_header(&stream, map, mapsize, hdr, sizeof(hdr));\n \tif (ret < Z_OK || (*type = parse_sha1_header(hdr, size)) < 0)\n \t\treturn NULL;\n-\n+\tif (stop_at_blank && strstr(hdr, \"\\n\\n\")) {\n+\t\t*size = strlen(hdr);\n+\t\treturn xstrdup(hdr);\n+\t}\n \treturn unpack_sha1_rest(&stream, hdr, *size, sha1);\n }\n \n@@ -1667,8 +1670,11 @@ static void *unpack_compressed_entry(struct packed_git *p,\n static void *unpack_compressed_entry(struct packed_git *p,\n \t\t\t\t    struct pack_window **w_curs,\n \t\t\t\t    off_t curpos,\n-\t\t\t\t    unsigned long size)\n+\t\t\t\t    unsigned long *sizep,\n+\t\t\t\t    int stop_at_blank)\n {\n+\tstatic const int chunk_size = 256;\n+\tunsigned long size = *sizep;\n \tint st;\n \tgit_zstream stream;\n \tunsigned char *buffer, *in;\n@@ -1676,15 +1682,27 @@ static void *unpack_compressed_entry(struct packed_git *p,\n \tbuffer = xmallocz(size);\n \tmemset(&stream, 0, sizeof(stream));\n \tstream.next_out = buffer;\n-\tstream.avail_out = size + 1;\n+\n+\tif (stop_at_blank)\n+\t\tstream.avail_out = chunk_size;\n+\telse\n+\t\tstream.avail_out = size + 1;\n \n \tgit_inflate_init(&stream);\n \tdo {\n \t\tin = use_pack(p, w_curs, curpos, &stream.avail_in);\n \t\tstream.next_in = in;\n \t\tst = git_inflate(&stream, Z_FINISH);\n-\t\tif (!stream.avail_out)\n-\t\t\tbreak; /* the payload is larger than it should be */\n+\t\tif (!stream.avail_out) {\n+\t\t\tif (!stop_at_blank)\n+\t\t\t\tbreak; /* the payload is larger than it should be */\n+\t\t\tif (memmem(buffer, chunk_size, \"\\n\\n\", 2)) {\n+\t\t\t\tgit_inflate_end(&stream);\n+\t\t\t\t*sizep = chunk_size;\n+\t\t\t\treturn buffer;\n+\t\t\t}\n+\t\t\tstream.avail_out = size + 1 - chunk_size;\n+\t\t}\n \t\tcurpos += stream.next_in - in;\n \t} while (st == Z_OK || st == Z_BUF_ERROR);\n \tgit_inflate_end(&stream);\n@@ -1731,7 +1749,8 @@ static void *cache_or_unpack_entry(struct packed_git *p, off_t base_offset,\n }\n \n static void *cache_or_unpack_entry(struct packed_git *p, off_t base_offset,\n-\tunsigned long *base_size, enum object_type *type, int keep_cache)\n+\tunsigned long *base_size, enum object_type *type, int keep_cache,\n+\tint stop_at_blank)\n {\n \tvoid *ret;\n \tunsigned long hash = pack_entry_hash(p, base_offset);\n@@ -1739,9 +1758,9 @@ static void *cache_or_unpack_entry(struct packed_git *p, off_t base_offset,\n \n \tret = ent->data;\n \tif (!ret || ent->p != p || ent->base_offset != base_offset)\n-\t\treturn unpack_entry(p, base_offset, type, base_size);\n+\t\treturn unpack_entry(p, base_offset, type, base_size, stop_at_blank);\n \n-\tif (!keep_cache) {\n+\tif (!stop_at_blank && !keep_cache) {\n \t\tent->data = NULL;\n \t\tent->lru.next->prev = ent->lru.prev;\n \t\tent->lru.prev->next = ent->lru.next;\n@@ -1810,7 +1829,7 @@ static void *read_object(const unsigned char *sha1, enum object_type *type,\n }\n \n static void *read_object(const unsigned char *sha1, enum object_type *type,\n-\t\t\t unsigned long *size);\n+\t\t\t unsigned long *size, int stop_at_blank);\n \n static void *unpack_delta_entry(struct packed_git *p,\n \t\t\t\tstruct pack_window **w_curs,\n@@ -1832,7 +1851,7 @@ static void *unpack_delta_entry(struct packed_git *p,\n \t\treturn NULL;\n \t}\n \tunuse_pack(w_curs);\n-\tbase = cache_or_unpack_entry(p, base_offset, &base_size, type, 0);\n+\tbase = cache_or_unpack_entry(p, base_offset, &base_size, type, 0, 0);\n \tif (!base) {\n \t\t/*\n \t\t * We're probably in deep shit, but let's try to fetch\n@@ -1851,12 +1870,12 @@ static void *unpack_delta_entry(struct packed_git *p,\n \t\t      sha1_to_hex(base_sha1), (uintmax_t)base_offset,\n \t\t      p->pack_name);\n \t\tmark_bad_packed_object(p, base_sha1);\n-\t\tbase = read_object(base_sha1, type, &base_size);\n+\t\tbase = read_object(base_sha1, type, &base_size, 0);\n \t\tif (!base)\n \t\t\treturn NULL;\n \t}\n \n-\tdelta_data = unpack_compressed_entry(p, w_curs, curpos, delta_size);\n+\tdelta_data = unpack_compressed_entry(p, w_curs, curpos, &delta_size, 0);\n \tif (!delta_data) {\n \t\terror(\"failed to unpack compressed delta \"\n \t\t      \"at offset %\"PRIuMAX\" from %s\",\n@@ -1895,7 +1914,8 @@ void *unpack_entry(struct packed_git *p, off_t obj_offset,\n int do_check_packed_object_crc;\n \n void *unpack_entry(struct packed_git *p, off_t obj_offset,\n-\t\t   enum object_type *type, unsigned long *sizep)\n+\t\t   enum object_type *type, unsigned long *sizep,\n+\t\t   int stop_at_blank)\n {\n \tstruct pack_window *w_curs = NULL;\n \toff_t curpos = obj_offset;\n@@ -1929,7 +1949,8 @@ void *unpack_entry(struct packed_git *p, off_t obj_offset,\n \tcase OBJ_TREE:\n \tcase OBJ_BLOB:\n \tcase OBJ_TAG:\n-\t\tdata = unpack_compressed_entry(p, &w_curs, curpos, *sizep);\n+\t\tdata = unpack_compressed_entry(p, &w_curs, curpos, sizep,\n+\t\t\t\t\t       stop_at_blank);\n \t\tbreak;\n \tdefault:\n \t\tdata = NULL;\n@@ -2208,14 +2229,15 @@ static void *read_packed_sha1(const unsigned char *sha1,\n }\n \n static void *read_packed_sha1(const unsigned char *sha1,\n-\t\t\t      enum object_type *type, unsigned long *size)\n+\t\t\t      enum object_type *type, unsigned long *size,\n+\t\t\t      int stop_at_blank)\n {\n \tstruct pack_entry e;\n \tvoid *data;\n \n \tif (!find_pack_entry(sha1, &e))\n \t\treturn NULL;\n-\tdata = cache_or_unpack_entry(e.p, e.offset, size, type, 1);\n+\tdata = cache_or_unpack_entry(e.p, e.offset, size, type, 1, stop_at_blank);\n \tif (!data) {\n \t\t/*\n \t\t * We're probably in deep shit, but let's try to fetch\n@@ -2226,7 +2248,7 @@ static void *read_packed_sha1(const unsigned char *sha1,\n \t\terror(\"failed to read object %s at offset %\"PRIuMAX\" from %s\",\n \t\t      sha1_to_hex(sha1), (uintmax_t)e.offset, e.p->pack_name);\n \t\tmark_bad_packed_object(e.p, sha1);\n-\t\tdata = read_object(sha1, type, size);\n+\t\tdata = read_object(sha1, type, size, stop_at_blank);\n \t}\n \treturn data;\n }\n@@ -2255,7 +2277,7 @@ static void *read_object(const unsigned char *sha1, enum object_type *type,\n }\n \n static void *read_object(const unsigned char *sha1, enum object_type *type,\n-\t\t\t unsigned long *size)\n+\t\t\t unsigned long *size, int stop_at_blank)\n {\n \tunsigned long mapsize;\n \tvoid *map, *buf;\n@@ -2268,17 +2290,18 @@ static void *read_object(const unsigned char *sha1, enum object_type *type,\n \t\treturn xmemdupz(co->buf, co->size);\n \t}\n \n-\tbuf = read_packed_sha1(sha1, type, size);\n+\tbuf = read_packed_sha1(sha1, type, size, stop_at_blank);\n \tif (buf)\n \t\treturn buf;\n \tmap = map_sha1_file(sha1, &mapsize);\n \tif (map) {\n-\t\tbuf = unpack_sha1_file(map, mapsize, type, size, sha1);\n+\t\tbuf = unpack_sha1_file(map, mapsize, type, size, sha1,\n+\t\t\t\t       stop_at_blank);\n \t\tmunmap(map, mapsize);\n \t\treturn buf;\n \t}\n \treprepare_packed_git();\n-\treturn read_packed_sha1(sha1, type, size);\n+\treturn read_packed_sha1(sha1, type, size, stop_at_blank);\n }\n \n /*\n@@ -2296,9 +2319,10 @@ void *read_sha1_file_extended(const unsigned char *sha1,\n \tconst struct packed_git *p;\n \tconst unsigned char *repl = (flag & READ_SHA1_FILE_REPLACE)\n \t\t? lookup_replace_object(sha1) : sha1;\n+\tint stop_at_blank = !!(flag & READ_SHA1_FILE_HEADER);\n \n \terrno = 0;\n-\tdata = read_object(repl, type, size);\n+\tdata = read_object(repl, type, size, stop_at_blank);\n \tif (data)\n \t\treturn data;\n \n@@ -2597,7 +2621,7 @@ int force_object_loose(const unsigned char *sha1, time_t mtime)\n \n \tif (has_loose_object(sha1))\n \t\treturn 0;\n-\tbuf = read_packed_sha1(sha1, &type, &len);\n+\tbuf = read_packed_sha1(sha1, &type, &len, 0);\n \tif (!buf)\n \t\treturn error(\"cannot read sha1_file for %s\", sha1_to_hex(sha1));\n \thdrlen = sprintf(hdr, \"%s %lu\", typename(type), len) + 1;\n"},{"id":"205672","messageId":"20121230120542.GA10820@sigill.intra.peff.net","threadId":"32200","inReplyTo":"20121229052747.GA14928@sigill.intra.peff.net","subject":"Re: [RFC] pack-objects: compression level for non-blobs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-12-30T12:05:42Z","receivedAt":"2012-12-30T12:05:42Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Dec 29, 2012 at 12:27:47AM -0500, Jeff King wrote:\n\n> > If reachability bitmap is implemented, we'll have per-pack cache\n> > infrastructure ready, so less work there for commit cache.\n> \n> True. I don't want to dissuade you from doing any commit cache work. I\n> only wanted to point out that this alternative may have merit because of\n> its simplicity (so we can use it until a caching solution exists, or\n> even after, if managing the cache has downsides).\n\nSo I was thinking about this, which led to some coding, which led to\nsome benchmarking.\n\nI want to clean up a few things in the code before I post it, but the\ngeneral idea is to have arbitrary per-pack cache files in the\nobjects/pack directory. Like this:\n\n  $ cd objects/pack && ls\n  pack-a3e262f40d95fc0cc97d92797ff9988551367b75.commits\n  pack-a3e262f40d95fc0cc97d92797ff9988551367b75.idx\n  pack-a3e262f40d95fc0cc97d92797ff9988551367b75.pack\n  pack-a3e262f40d95fc0cc97d92797ff9988551367b75.parents\n  pack-a3e262f40d95fc0cc97d92797ff9988551367b75.timestamps\n  pack-a3e262f40d95fc0cc97d92797ff9988551367b75.trees\n\nEach file describes the objects in the matching pack. If a new pack is\ngenerated, you'd throw away the old cache files along with the old pack,\nand generate new ones. Or not. These are totally optional, and an older\nversion of git will just ignore them. A newer version will use them if\nthey're available, and otherwise fallback to the existing code (i.e.,\nreading the whole object from the pack). So you can generate them at\nrepack time, later on, or not at all. For now I have a separate command\nthat generates them based on the pack index; if this turns out to be a\ngood idea, it would probably get called as part of \"repack\".\n\nEach file is a set of fixed-length records. The \"commits\" file contains\nthe sha1 of every commit in the pack (sorted). A binary search of the\nmmap'd file gives the position of a particular commit within the list,\nand that position is used to index the parents, timestamps, and trees\nfiles (obviously if it is missing, then the other files are useless, but\nwe already have to be able to fallback to just reading the objects\nanyway).\n\nI split it out into multiple files because you can actually operate with\na subset (though in my initial attempt, I transparently plug in at the\nparse_commit layer, which means we need all items to consider the commit\n\"parsed\", whether the caller actually cares or not. But in theory a\nreader could only want to ask for one item).  Making a \"generation\"\ncache file is an obvious next step (and because we already have\n\"commits\", it is only 4 bytes per commit on top of it). Reachability\nbitmaps would be another one (though due to the compression, I am not\nsure they will work with a fixed-size record design, so this may need\nsome modification).\n\nAnyway, here are the numbers I came up with (appended to my earlier\ncompression numbers):\n\ngit.git:\n Pack  | Size          |  Cold Revs  |  Warm Revs  | Cold Objects | Warm Objects\n-------+---------------+-------------+-------------+--------------+--------------\n  none |  56.72        | 0.68        | 0.33        |  2.45        |  1.94       \ncommit |  64.61 (+13%) | 0.50 (-26%) | 0.09 (-74%) |  2.42  (-1%) |  1.69 (-13%)\n  tree |  60.68  (+6%) | 0.79 (+16%) | 0.33   (0%) |  2.23  (-8%) |  1.75  (-9%)\n  both |  68.54 (+20%) | 0.48 (-29%) | 0.08 (-75%) |  2.24  (-8%) |  1.48 (-23%)\n cache |  59.29  (+4%) | 0.57 (-16%) | 0.05 (-84%) |  2.23  (-8%) |  1.66 (-14%)\n\nlinux.git:\n Pack  | Size          |  Cold Revs  |  Warm Revs  | Cold Objects | Warm Objects\n-------+---------------+-------------+-------------+--------------+--------------\n  none | 864.61        | 8.66        | 4.07        | 42.76        | 36.32       \ncommit | 970.46 (+12%) | 8.87  (+2%) | 1.02 (-74%) | 42.94   (0%) | 33.43  (-7%)\n  tree | 895.37  (+3%) | 9.08  (+4%) | 4.07   (0%) | 36.01 (-15%) | 29.62 (-18%)\n  both |1001.25 (+15%) | 8.90  (+2%) | 1.03 (-74%) | 35.57 (-16%) | 26.25 (-27%)\n cache | 894.78  (+3%) | 4.88 (-43%) | 0.69 (-83%) | 38.80  (-9%) | 32.79  (-9%)\n\nwebkit.git:\n Pack  | Size          |  Cold Revs  |  Warm Revs  | Cold Objects | Warm Objects\n-------+---------------+-------------+-------------+--------------+--------------\n  none |   3.46        | 1.61        | 1.38        | 20.46        | 18.72       \ncommit |   3.54  (+2%) | 1.42 (-11%) | 0.34 (-75%) | 20.42   (0%) | 17.57  (-6%)\n  tree |   3.59  (+3%) | 1.61   (0%) | 1.39   (0%) | 16.01 (-21%) | 14.00 (-25%)\n  both |   3.67  (+6%) | 1.45 (-10%) | 0.34 (-75%) | 15.94 (-22%) | 12.91 (-31%)\n cache |   3.47   (0%) | 0.49 (-69%) | 0.14 (-90%) | 19.53  (-4%) | 17.86  (-4%)\n\n\nSo you can see that it performs even better than no-compression on the\nwarm-revs case. Which makes sense, since we do not even have to touch\nthe object data at all, and can do the whole traversal straight out of\nthe cache. So we do not even have to memcpy the bytes around. And it\ntakes up even less space (3-4% versus 12-13% on the first two repos).\nWhich makes sense, because even though we are duplicating some\ninformation that is in the packfile, we are leaving all of the commit\nmessage bodies compressed.\n\nThe other interesting thing is that the cold cache performance also\nimproves by a lot. Again, this makes sense; we are doing the traversal\ncompletely out of cache, and our data is even more tightly packed in the\ncache than it is in the packfile.\n\nOf course, it does very little for the full --objects listing, where we\nspend most of our time inflating trees. We could couple this with\nuncompressed trees (which are not all that much bigger, since the sha1s\ndo not compress anyway). Or we could have an external tree cache, but\nI'm not sure exactly what it would look like (this is basically\nreinventing bits of packv4, but doing so in a way that is redundant with\nthe existing packfile, rather than replacing it). Or since the point of\n--objects is usually reachability, it may make more sense to pursue the\nbitmap, which should be even faster still.\n\n-Peff\n"},{"id":"205673","messageId":"CACsJy8C4UttGKcw11do1POcHZJM7iZ2r7F3ESOqEnWL8kdz+dQ@mail.gmail.com","threadId":"32200","inReplyTo":"20121230120542.GA10820@sigill.intra.peff.net","subject":"Re: [RFC] pack-objects: compression level for non-blobs","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-12-30T12:53:48Z","receivedAt":"2012-12-30T12:53:48Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Sun, Dec 30, 2012 at 7:05 PM, Jeff King <peff@peff.net> wrote:\n> So I was thinking about this, which led to some coding, which led to\n> some benchmarking.\n\nI like your way of thinking! May I suggest you take a new year break\nfirst, then \"think\" about reachability bitmaps ;-) 2013 will be an\nexciting year.\n\n> I want to clean up a few things in the code before I post it, but the\n> general idea is to have arbitrary per-pack cache files in the\n> objects/pack directory. Like this:\n>\n>   $ cd objects/pack && ls\n>   pack-a3e262f40d95fc0cc97d92797ff9988551367b75.commits\n>   pack-a3e262f40d95fc0cc97d92797ff9988551367b75.idx\n>   pack-a3e262f40d95fc0cc97d92797ff9988551367b75.pack\n>   pack-a3e262f40d95fc0cc97d92797ff9988551367b75.parents\n>   pack-a3e262f40d95fc0cc97d92797ff9988551367b75.timestamps\n>   pack-a3e262f40d95fc0cc97d92797ff9988551367b75.trees\n>\n> Each file describes the objects in the matching pack. If a new pack is\n> generated, you'd throw away the old cache files along with the old pack,\n> and generate new ones. Or not. These are totally optional, and an older\n> version of git will just ignore them. A newer version will use them if\n> they're available, and otherwise fallback to the existing code (i.e.,\n> reading the whole object from the pack). So you can generate them at\n\nYou have probably thought about this (and I don't have the source to\ncheck first), but we may need to version these extra files so we can\nchange the format later if needed. Git versions that do not recognize\nnew versions simply ignore the cahce.\n\n> repack time, later on, or not at all. For now I have a separate command\n> that generates them based on the pack index; if this turns out to be a\n> good idea, it would probably get called as part of \"repack\".\n\nI'd like to make it part of index-pack, where we have nearly\neverything in memory. But let's leave it as a separate command first.\n\n> Each file is a set of fixed-length records. The \"commits\" file contains\n> the sha1 of every commit in the pack (sorted). A binary search of the\n> mmap'd file gives the position of a particular commit within the list,\n\nI think we could avoid storing sha-1 in the cache with Shawn's idea\n[1]. But now I read it again I fail to see it :(\n\n[1] http://article.gmane.org/gmane.comp.version-control.git/206485\n\n> Of course, it does very little for the full --objects listing, where we\n> spend most of our time inflating trees. We could couple this with\n> uncompressed trees (which are not all that much bigger, since the sha1s\n> do not compress anyway). Or we could have an external tree cache, but\n> I'm not sure exactly what it would look like (this is basically\n> reinventing bits of packv4, but doing so in a way that is redundant with\n> the existing packfile, rather than replacing it).\n\nDepending on the use case, we could just generate packv4-like cache\nfor recently-used trees only. I'm not sure how tree cache impact a\nmerge operation on a very large worktree (iow, a lot of trees\nreferenced from HEAD to be inflated). This is something a cache can\ndo, but a new pack version cannot.\n\n> Or since the point of\n> --objects is usually reachability, it may make more sense to pursue the\n> bitmap, which should be even faster still.\n\nYes. And if narrow clone ever comes, which needs --objects limited by\npathspec, we could just produce extra bitmaps for frequently-used\npathspecs and only allow narrow clone with those pathspecs.\n-- \nDuy\n"},{"id":"205685","messageId":"20121230213124.GA15946@sigill.intra.peff.net","threadId":"32200","inReplyTo":"CACsJy8C4UttGKcw11do1POcHZJM7iZ2r7F3ESOqEnWL8kdz+dQ@mail.gmail.com","subject":"Re: [RFC] pack-objects: compression level for non-blobs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-12-30T21:31:24Z","receivedAt":"2012-12-30T21:31:24Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Dec 30, 2012 at 07:53:48PM +0700, Nguyen Thai Ngoc Duy wrote:\n\n> >   $ cd objects/pack && ls\n> >   pack-a3e262f40d95fc0cc97d92797ff9988551367b75.commits\n> >   pack-a3e262f40d95fc0cc97d92797ff9988551367b75.idx\n> >   pack-a3e262f40d95fc0cc97d92797ff9988551367b75.pack\n> >   pack-a3e262f40d95fc0cc97d92797ff9988551367b75.parents\n> >   pack-a3e262f40d95fc0cc97d92797ff9988551367b75.timestamps\n> >   pack-a3e262f40d95fc0cc97d92797ff9988551367b75.trees\n> >\n> > Each file describes the objects in the matching pack. If a new pack is\n> > generated, you'd throw away the old cache files along with the old pack,\n> > and generate new ones. Or not. These are totally optional, and an older\n> > version of git will just ignore them. A newer version will use them if\n> > they're available, and otherwise fallback to the existing code (i.e.,\n> > reading the whole object from the pack). So you can generate them at\n> \n> You have probably thought about this (and I don't have the source to\n> check first), but we may need to version these extra files so we can\n> change the format later if needed. Git versions that do not recognize\n> new versions simply ignore the cahce.\n\nAgreed. The current code has a 4-byte magic, followed by a 4-byte\nversion number, followed by a 4-byte record size[1]. Then the data,\nfollowed by the pack sha1, followed by a sha1 of all of the preceding\ndata.  So you can verify the validity of any cache file (both its\nchecksum, and that it matches the right packfile), just as you can with\na \".idx\" file.\n\n[1] Probably the magic and version should be per-file-type, and the\n    record size should be implicit from that; right now I make\n    assumptions about what is in the files based on their names, but\n    that is not part of the checksum.\n\n> > repack time, later on, or not at all. For now I have a separate command\n> > that generates them based on the pack index; if this turns out to be a\n> > good idea, it would probably get called as part of \"repack\".\n> \n> I'd like to make it part of index-pack, where we have nearly\n> everything in memory. But let's leave it as a separate command first.\n\nYeah, in the long run that may work. The steps I figured were:\n\n  1. Optional, external command. Let people experiment.\n\n  2. Once it has proven itself, run the command from index-pack by\n     default (or with a config option).\n\n  3. If it turns out too slow, move the generation directly into the\n     index-pack process.\n\nThe current iteration does not seem all that slow, but that is because I\nam mostly picking static data out of the commits. So I have to load the\ncommits, and that's it. But something like reachability might be more\nexpensive (OTOH, it will always be more expensive, whether we have the\nobjects in memory or not).\n\n> > Each file is a set of fixed-length records. The \"commits\" file contains\n> > the sha1 of every commit in the pack (sorted). A binary search of the\n> > mmap'd file gives the position of a particular commit within the list,\n> \n> I think we could avoid storing sha-1 in the cache with Shawn's idea\n> [1]. But now I read it again I fail to see it :(\n> \n> [1] http://article.gmane.org/gmane.comp.version-control.git/206485\n\nRight. My implementation is very similar to what Shawn said there. I.e.,\nthe timestamps file is literally 4 bytes times the number of commits.\nThe parents file is 40 bytes per commit (2 parents, with a marker to\nindicate \"more or less than 2\"), though a lot of it is zero bytes.\n\nSome alternatives I'm thinking about are:\n\n  1. Using non-fixed-size records, which would allow trivial compression\n     of entries like null sha1s. This would mean adding a separate\n     lookup table, though, mapping sha1s to offsets. Still, even a\n     32-bit offset is only 4 bytes per commit. If it meant dropping 40\n     bytes of zeroes from the 2nd parent field out of half of all\n     commits, that would be a win space-wise. It would be a\n     double-indirect lookup, but it's constant effort, and only two page\n     hits (which would be warm after the first lookup anyway).\n\n  2. Storing offsets to objects in the packfile rather than their sha1s.\n     This would save a lot of space, but would mean we couldn't refer to\n     parents outside of the pack, but that may be OK. This is an\n     optimization, and the case we want to target is a fully (or mostly)\n     packed repo. It's OK to have the lookup fail and fallback to\n     accessing the object.\n\n  3. Dropping the \"commits\" file and just using the pack-*.idx as the\n     index. The problem is that it is sparse in the commit space. So\n     just naively storing 40 bytes per entry is going to waste a lot of\n     space. If we had a separate index as in (1) above, that could be\n     dropped to (say) 4 bytes of offset per object. But still, right now\n     the commits file for linux-2.6 is about 7.2M (20 bytes times ~376K\n     commits). There are almost 3 million total objects, so even storing\n     4 bytes per object is going to be worse.\n\n  4. Making a new index version that stores the sha1s separated by type.\n     This means we can piggy-back on the regular index to get a packed\n     list of just commits. But it also means that regular sha1 lookups\n     of the objects have to look in several places (unless the caller\n     annotates the call to read_sha1_object with \"I am expecting this\n     sha1 to be a commit\"). And of course it means bumping the index\n     version, which is a pain. The external index means it can be\n     completely optional on top of the current index/pack.\n\n> Depending on the use case, we could just generate packv4-like cache\n> for recently-used trees only. I'm not sure how tree cache impact a\n> merge operation on a very large worktree (iow, a lot of trees\n> referenced from HEAD to be inflated). This is something a cache can\n> do, but a new pack version cannot.\n\nI do not care too much about the cost of running merge on a large\nworking tree. Of course it's better to make our optimizations as\ngenerally applicable as possible, but there is a lot of other work going\non in a merge. The really painful, noticeable, repetitive bits right now\nare:\n\n  1. Running git-prune.\n\n  2. Creating a pack from git-upload-pack.\n\nWhich are both just reachability problems. Something like \"git log --\n<pathspec>\" would also be helped by packv4-ish tree access patterns,\nthough, but not by reachability bitmaps. And that may be something\nworth caring about.\n\n> Yes. And if narrow clone ever comes, which needs --objects limited by\n> pathspec, we could just produce extra bitmaps for frequently-used\n> pathspecs and only allow narrow clone with those pathspecs.\n\nI hadn't thought about that. But yeah, because of the optional, external\nnature, there's no reason you couldn't have extra bitmap sets for\nspecialized situations.\n\n-Peff\n"},{"id":"205698","messageId":"CAJo=hJtjtpiPVd6Koy9q5je7s7A4EyDa-CptJNCnHLSLgd9W7g@mail.gmail.com","threadId":"32200","inReplyTo":"20121230213124.GA15946@sigill.intra.peff.net","subject":"Re: [RFC] pack-objects: compression level for non-blobs","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2012-12-31T18:06:15Z","receivedAt":"2012-12-31T18:06:15Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"This thread is pretty interesting. Unfortunately the holidays have\nkept me busy. But I am excited by the work David and Peff are doing.\n:-)\n\nOn Sun, Dec 30, 2012 at 1:31 PM, Jeff King <peff@peff.net> wrote:\n> On Sun, Dec 30, 2012 at 07:53:48PM +0700, Nguyen Thai Ngoc Duy wrote:\n>\n>> >   $ cd objects/pack && ls\n>> >   pack-a3e262f40d95fc0cc97d92797ff9988551367b75.commits\n>> >   pack-a3e262f40d95fc0cc97d92797ff9988551367b75.idx\n>> >   pack-a3e262f40d95fc0cc97d92797ff9988551367b75.pack\n>> >   pack-a3e262f40d95fc0cc97d92797ff9988551367b75.parents\n>> >   pack-a3e262f40d95fc0cc97d92797ff9988551367b75.timestamps\n>> >   pack-a3e262f40d95fc0cc97d92797ff9988551367b75.trees\n>> >\n>> > Each file describes the objects in the matching pack. If a new pack is\n>> > generated, you'd throw away the old cache files along with the old pack,\n>> > and generate new ones. Or not. These are totally optional, and an older\n>> > version of git will just ignore them. A newer version will use them if\n>> > they're available, and otherwise fallback to the existing code (i.e.,\n>> > reading the whole object from the pack). So you can generate them at\n>>\n>> You have probably thought about this (and I don't have the source to\n>> check first), but we may need to version these extra files so we can\n>> change the format later if needed. Git versions that do not recognize\n>> new versions simply ignore the cahce.\n>\n> Agreed. The current code has a 4-byte magic, followed by a 4-byte\n> version number, followed by a 4-byte record size[1]. Then the data,\n> followed by the pack sha1, followed by a sha1 of all of the preceding\n> data.  So you can verify the validity of any cache file (both its\n> checksum, and that it matches the right packfile), just as you can with\n> a \".idx\" file.\n\nPut the pack sha1 into the header, rather than the trailer. Its really\nannoying that you read the header, determine you probably understand\nthis file, and then have to seek to END-40 to read the pack sha1 and\nverify it matches the pack. In an ideal world the pack sha1 would have\nbeen the file name, making this less of an issue, but someone didn't\nanticipate repacking the same object set with possibly different\nresults. :-(\n\nThe idx format is kind of wrong here, I wish we had put the pack sha1\ninto the header. Given that we mmap the files the 20 bytes in front\nvs. 20 bytes in the trailer wouldn't have made any difference on\naccess cost.\n\n>> > Each file is a set of fixed-length records. The \"commits\" file contains\n>> > the sha1 of every commit in the pack (sorted). A binary search of the\n>> > mmap'd file gives the position of a particular commit within the list,\n>>\n>> I think we could avoid storing sha-1 in the cache with Shawn's idea\n>> [1]. But now I read it again I fail to see it :(\n>>\n>> [1] http://article.gmane.org/gmane.comp.version-control.git/206485\n>\n> Right. My implementation is very similar to what Shawn said there. I.e.,\n> the timestamps file is literally 4 bytes times the number of commits.\n> The parents file is 40 bytes per commit (2 parents, with a marker to\n> indicate \"more or less than 2\"), though a lot of it is zero bytes.\n\nHmm, after re-reading [1] I still like my idea better. But I won't\nfind the time to code it myself, so I'll have to go with whatever\nsomeone else writes. :-)\n\nSince tree pointers are also required when parsing a commit (even if\nthey might not get used e.g. `git log master`) maybe this should be 16\nbytes per commit storing the commit time, tree pointer, and 2 parents,\nwith the last 3 fields using the N-th object in the sorted sha1 list\nin the idx. Sorting the file by pack stream ordering gives you good\nlocality during rev-list operations and makes it compact if\npack-objects adheres to writing commits before other objects.\n\nUnfortunately this ordering requires the pack reverse index in memory\nto translate from sha1 to position in the cache file. Making the\nreverse index is a non-trivial cost that may dominate the running time\nfor smaller traversals, or the startup time for `git log` outputting\nto the pager.\n\n> Some alternatives I'm thinking about are:\n>\n>   1. Using non-fixed-size records, which would allow trivial compression\n>      of entries like null sha1s. This would mean adding a separate\n>      lookup table, though, mapping sha1s to offsets. Still, even a\n>      32-bit offset is only 4 bytes per commit. If it meant dropping 40\n>      bytes of zeroes from the 2nd parent field out of half of all\n>      commits, that would be a win space-wise. It would be a\n>      double-indirect lookup, but it's constant effort, and only two page\n>      hits (which would be warm after the first lookup anyway).\n\nOr use a 16 byte fixed width record (see above).\n\n>   2. Storing offsets to objects in the packfile rather than their sha1s.\n>      This would save a lot of space, but would mean we couldn't refer to\n>      parents outside of the pack, but that may be OK. This is an\n>      optimization, and the case we want to target is a fully (or mostly)\n>      packed repo. It's OK to have the lookup fail and fallback to\n>      accessing the object.\n\nI glossed over this in both [1] and this message. I think its\nperfectly reasonable to require parsing the commit when the commit's\nparents are outside of the pack. These edge commits are infrequent\ncompared to the number of commits within the pack. Just mark them the\nsame way you mark an octopus merge, so the reader knows the parent\ndata is not available in the cache. For most repositories the bulk of\nthe commits will be in a single giant pack that contains history to\nthe root.\n\nI wouldn't store the byte offsets here, those are possibly 8 bytes\nwide on bigger packs. Instead store the Nth position in the pack\nstream. Even if you store byte offsets you need to use the pack\nreverse index to recover the SHA-1 in log N time. If you store the Nth\nposition you also use the pack reverse index, but you can fit all\nobjects from that pack in 4 bytes rather than 8 bytes per reference.\n\n>   3. Dropping the \"commits\" file and just using the pack-*.idx as the\n>      index. The problem is that it is sparse in the commit space. So\n>      just naively storing 40 bytes per entry is going to waste a lot of\n>      space. If we had a separate index as in (1) above, that could be\n>      dropped to (say) 4 bytes of offset per object. But still, right now\n>      the commits file for linux-2.6 is about 7.2M (20 bytes times ~376K\n>      commits). There are almost 3 million total objects, so even storing\n>      4 bytes per object is going to be worse.\n\nFix pack-objects to behave the way JGit does, cluster commits first in\nthe pack stream. Now you have a dense space of commits. If I remember\nright this has a tiny positive improvement for most rev-list\noperations with very little downside.\n\n>   4. Making a new index version that stores the sha1s separated by type.\n>      This means we can piggy-back on the regular index to get a packed\n>      list of just commits. But it also means that regular sha1 lookups\n>      of the objects have to look in several places (unless the caller\n>      annotates the call to read_sha1_object with \"I am expecting this\n>      sha1 to be a commit\"). And of course it means bumping the index\n>      version, which is a pain. The external index means it can be\n>      completely optional on top of the current index/pack.\n\nI don't think this is worthwhile.\n\n>> Depending on the use case, we could just generate packv4-like cache\n>> for recently-used trees only. I'm not sure how tree cache impact a\n>> merge operation on a very large worktree (iow, a lot of trees\n>> referenced from HEAD to be inflated). This is something a cache can\n>> do, but a new pack version cannot.\n>\n> I do not care too much about the cost of running merge on a large\n> working tree. Of course it's better to make our optimizations as\n> generally applicable as possible, but there is a lot of other work going\n> on in a merge. The really painful, noticeable, repetitive bits right now\n> are:\n>\n>   1. Running git-prune.\n>\n>   2. Creating a pack from git-upload-pack.\n>\n> Which are both just reachability problems. Something like \"git log --\n> <pathspec>\" would also be helped by packv4-ish tree access patterns,\n> though, but not by reachability bitmaps. And that may be something\n> worth caring about.\n\nblame would also benefit from a packv4-ish tree.\n\nBut upload-pack and prune can make massive improvements through\nbitmaps, while packv4-ish tree would be only a marginal incremental\nimprovement. In the case of upload-pack having a bitmap gives you much\nmore knowledge of the remote's have set, and allows making a smaller\npack, in a lot less time, and a smaller server memory footprint. Now\nthat we have implemented bitmaps in our servers, I can say you really\ndon't want to ignore the gains we can get from them. packv4-ish tree\nmight help some other workloads, but bitmaps provide a better solution\nto these reachability problems than anything else we know.\n\n>> Yes. And if narrow clone ever comes, which needs --objects limited by\n>> pathspec, we could just produce extra bitmaps for frequently-used\n>> pathspecs and only allow narrow clone with those pathspecs.\n>\n> I hadn't thought about that. But yeah, because of the optional, external\n> nature, there's no reason you couldn't have extra bitmap sets for\n> specialized situations.\n\nRight. We still need to redo the JGit patch series to eject the\nbitmaps into an extension file. :-(\n"},{"id":"205756","messageId":"CACsJy8CygfaM+Ee6rURFB-cP2khO8URGDJMG2f3mqg0ebYz+8Q@mail.gmail.com","threadId":"32200","inReplyTo":"CAJo=hJtjtpiPVd6Koy9q5je7s7A4EyDa-CptJNCnHLSLgd9W7g@mail.gmail.com","subject":"Re: [RFC] pack-objects: compression level for non-blobs","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-01-01T04:15:58Z","receivedAt":"2013-01-01T04:15:58Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Tue, Jan 1, 2013 at 1:06 AM, Shawn Pearce <spearce@spearce.org> wrote:\n>>   3. Dropping the \"commits\" file and just using the pack-*.idx as the\n>>      index. The problem is that it is sparse in the commit space. So\n>>      just naively storing 40 bytes per entry is going to waste a lot of\n>>      space. If we had a separate index as in (1) above, that could be\n>>      dropped to (say) 4 bytes of offset per object. But still, right now\n>>      the commits file for linux-2.6 is about 7.2M (20 bytes times ~376K\n>>      commits). There are almost 3 million total objects, so even storing\n>>      4 bytes per object is going to be worse.\n>\n> Fix pack-objects to behave the way JGit does, cluster commits first in\n> the pack stream. Now you have a dense space of commits. If I remember\n> right this has a tiny positive improvement for most rev-list\n> operations with very little downside.\n\nI was going to suggest a similar thing. The current state of C Git's\npack writing is not bad. We mix commits and tags together, but tags\nare few usually. Once we get the upper and lower bound, in terms of\nobject position in the pack, of the commit+tag region, we could reduce\nthe waste significantly. That is if you sort the cache by the object\norder in the pack.\n-- \nDuy\n"},{"id":"205764","messageId":"CACsJy8DpnO6X6jdQVsr1NwrXF2MDBBcHZQTay=TyLFc5p_z9eg@mail.gmail.com","threadId":"32200","inReplyTo":"CACsJy8CygfaM+Ee6rURFB-cP2khO8URGDJMG2f3mqg0ebYz+8Q@mail.gmail.com","subject":"Re: [RFC] pack-objects: compression level for non-blobs","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-01-01T12:10:54Z","receivedAt":"2013-01-01T12:10:54Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Tue, Jan 1, 2013 at 11:15 AM, Duy Nguyen <pclouds@gmail.com> wrote:\n>> Fix pack-objects to behave the way JGit does, cluster commits first in\n>> the pack stream. Now you have a dense space of commits. If I remember\n>> right this has a tiny positive improvement for most rev-list\n>> operations with very little downside.\n>\n> I was going to suggest a similar thing. The current state of C Git's\n> pack writing is not bad. We mix commits and tags together, but tags\n\nAnd I was wrong. At least since 1b4bb16 (pack-objects: optimize\n\"recency order\" - 2011-06-30) commits are spread out and can be mixed\nwith trees too. Grouping them back defeats what Junio did in that\ncommit, I think.\n-- \nDuy\n"},{"id":"205770","messageId":"CAJo=hJsZedd0kfYJnXPhcud8bz3mgU0NMf6O6-_PY1yqv-EfDg@mail.gmail.com","threadId":"32200","inReplyTo":"CACsJy8DpnO6X6jdQVsr1NwrXF2MDBBcHZQTay=TyLFc5p_z9eg@mail.gmail.com","subject":"Re: [RFC] pack-objects: compression level for non-blobs","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2013-01-01T17:17:38Z","receivedAt":"2013-01-01T17:17:38Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Tue, Jan 1, 2013 at 4:10 AM, Duy Nguyen <pclouds@gmail.com> wrote:\n> On Tue, Jan 1, 2013 at 11:15 AM, Duy Nguyen <pclouds@gmail.com> wrote:\n>>> Fix pack-objects to behave the way JGit does, cluster commits first in\n>>> the pack stream. Now you have a dense space of commits. If I remember\n>>> right this has a tiny positive improvement for most rev-list\n>>> operations with very little downside.\n>>\n>> I was going to suggest a similar thing. The current state of C Git's\n>> pack writing is not bad. We mix commits and tags together, but tags\n>\n> And I was wrong. At least since 1b4bb16 (pack-objects: optimize\n> \"recency order\" - 2011-06-30) commits are spread out and can be mixed\n> with trees too. Grouping them back defeats what Junio did in that\n> commit, I think.\n\nI think you misunderstand what 1b4bb16 does. Junio uses a layout\nsimilar to what JGit has done for years. Commits are packed, then\ntrees, then blobs. Only annotated tags are interspersed with commits.\nThe decision on where to place tags is different, but has a similar\npurpose. How blobs are written is very different, Junio's\nimplementation is strictly better than JGit's[1].\n\nSo we can use pack ordering. There will be a gap because of tags, but\nif we assume there are less tags than commits, it will still be a\nreasonable cache file size.\n\n[1] I have known this since he was developing this commit. We talked\nabout clustering by delta chain and the improvements it showed in\nCGit. I tried to implement a similar delta chain clustering in JGit\nbut broke something in the packer and caused data corruption, so its\nstalled.\n"},{"id":"205776","messageId":"7v7gnwbrjf.fsf@alter.siamese.dyndns.org","threadId":"32200","inReplyTo":"CACsJy8DpnO6X6jdQVsr1NwrXF2MDBBcHZQTay=TyLFc5p_z9eg@mail.gmail.com","subject":"Re: [RFC] pack-objects: compression level for non-blobs","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-01-01T20:02:28Z","receivedAt":"2013-01-01T20:02:28Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Duy Nguyen <pclouds@gmail.com> writes:\n\n> On Tue, Jan 1, 2013 at 11:15 AM, Duy Nguyen <pclouds@gmail.com> wrote:\n>>> Fix pack-objects to behave the way JGit does, cluster commits first in\n>>> the pack stream. Now you have a dense space of commits. If I remember\n>>> right this has a tiny positive improvement for most rev-list\n>>> operations with very little downside.\n>>\n>> I was going to suggest a similar thing. The current state of C Git's\n>> pack writing is not bad. We mix commits and tags together, but tags\n>\n> And I was wrong. At least since 1b4bb16 (pack-objects: optimize\n> \"recency order\" - 2011-06-30) commits are spread out and can be mixed\n> with trees too.\n\nReally?  That certainly wasn't the intention of that change.\n\nThe compute_write_order() function first fills the commits in the\noriginal recency order (the order in which rev-list discovered them\nby traversing the history from the tips) until we find a commit that\nis tagged by a ref in the refs/tags/ hierarchy.  When we reach that\npoint, we stop showing the commits and show all the tags in the\nrefs/tags/ hierarchy and commits that are tagged by them, breaking\nthe original ordering of commits so that ancient but tagged commits\nclump at this point.  After that, we resume showing the rest of the\ncommits and tags in the original order they came to us.  Trees are\ndone next, and then the remainder.\n\nSo I am not sure how trees can appear between commits.\n"},{"id":"205815","messageId":"7vmwws79fa.fsf@alter.siamese.dyndns.org","threadId":"32200","inReplyTo":"CAJo=hJsZedd0kfYJnXPhcud8bz3mgU0NMf6O6-_PY1yqv-EfDg@mail.gmail.com","subject":"Re: [RFC] pack-objects: compression level for non-blobs","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-01-01T23:47:21Z","receivedAt":"2013-01-01T23:47:21Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Shawn Pearce <spearce@spearce.org> writes:\n\n> How blobs are written is very different, Junio's\n> implementation is strictly better than JGit's[1].\n\nI do not think there can be a single ordering that is strictly\nbetter than any other one.  The \"clump all objects in a delta family\nand write them width-first, starting from the base object\" may give\nyou a reasonable trade-off for a result of normal repack, but if you\nrepack (like I do) with very shallow --depth with wide --window to\nreally get a tight pack, a delta may end up having too may uncles\nbetween it and its father, requiring a large seek to skip over all\nthe uncles in order to grab the delta data, after you reconstitute\nthe delta base object.\n"},{"id":"205830","messageId":"CACsJy8D0fQ4-DiLx=mqm16Om829Zcno2oTi5F1c78H615-Hivw@mail.gmail.com","threadId":"32200","inReplyTo":"CAJo=hJsZedd0kfYJnXPhcud8bz3mgU0NMf6O6-_PY1yqv-EfDg@mail.gmail.com","subject":"Re: [RFC] pack-objects: compression level for non-blobs","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-01-02T02:23:39Z","receivedAt":"2013-01-02T02:23:39Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Wed, Jan 2, 2013 at 12:17 AM, Shawn Pearce <spearce@spearce.org> wrote:\n>> And I was wrong. At least since 1b4bb16 (pack-objects: optimize\n>> \"recency order\" - 2011-06-30) commits are spread out and can be mixed\n>> with trees too. Grouping them back defeats what Junio did in that\n>> commit, I think.\n>\n> I think you misunderstand what 1b4bb16 does. Junio uses a layout\n> similar to what JGit has done for years. Commits are packed, then\n> trees, then blobs. Only annotated tags are interspersed with commits.\n> The decision on where to place tags is different, but has a similar\n> purpose.\n\nThis is embarrassing. I looked at verify-pack output and somehow saw\ntrees mixed with commits. I must have read it wrong. \"git verify-pack\n-v <pack>|awk '{print $2;}'|uniq on recently created pack shows that\nonly tags and commits are mixed. Sorry for the noise.\n-- \nDuy\n"}]}