{"thread":{"id":"35568","subject":"[PATCH] [RFC] Making use of bitmaps for thin objects","startedAt":"2013-12-22T19:47:34Z","lastAt":"2014-01-07T17:26:44Z","messageCount":11,"participants":["Ben Maurer","Jeff King","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"232356","messageId":"1387741654-14890-1-git-send-email-bmaurer@fb.com","threadId":"35568","inReplyTo":null,"subject":"[PATCH] [RFC] Making use of bitmaps for thin objects","fromName":"Ben Maurer","fromEmail":"bmaurer@fb.com","sentAt":"2013-12-22T19:47:34Z","receivedAt":"2013-12-22T19:47:34Z","isPatch":true,"sender":{"key":"bmaurer@fb.com","avatar":null},"body":"I've been hacking with the performance of git on a large, quickly\nchanging git repo used inside Facebook. Pulling a week of changes\nfrom this repo can be quite painful.\n\n$ { echo HEAD && echo ^$have; } | time git pack-objects --no-use-bitmap-index --revs --stdout  >/dev/null\nCounting objects: 221082, done.\nCompressing objects: 100% (20174/20174), done.\nTotal 221082 (delta 197889), reused 215144 (delta 194084)\n86.53user 7.89system 1:12.76elapsed 129%CPU (0avgtext+0avgdata 5746608maxresident)k\n0inputs+0outputs (0major+3177262minor)pagefaults 0swaps\n\nJeff King's bitmap branch appears to give a very substantial speedup.\nAfter applying this branch, the \"counting objects\" phase is basically\nfree. However, I found that the compression phase still takes a\nnon-trivial amount of time.\n\n$ { echo HEAD && echo ^$have; } | time ../git-bitmap/install/bin/git pack-objects --use-bitmap-index --revs --stdout  >/dev/null\nCounting objects: 220909, done.\nCompressing objects: 100% (20038/20038), done.\nTotal 220909 (delta 197794), reused 215074 (delta 194050)\n47.96user 2.45system 0:28.39elapsed 177%CPU (0avgtext+0avgdata 5890768maxresident)k\n0inputs+0outputs (0major+984875minor)pagefaults 0swaps\n\nIt looks like most of the time spent compressing objects was in cases\nwhere the object was already compressed in the packfile, but the delta\nwas based on an object that the client already had. For some reason,\n--thin wasn't enabling reuse of these deltas.\n\nThis is a hacky, poorly styled attempt to figure how how much better\nperformance could be. With the bitmap branch, git should know what\nobjects the client has already and can easily test if an existing delta\ncan be reused. I don't know the branch well enough to code this, so\nas a hack, I just assumed the client has any delta base that is in\nthe pack file (for our repo, this is always true, because we have a\nlinear history)\n\nThis greatly reduces the time:\n\n$ { echo HEAD && echo ^$have; } | time ../git-bitmap/install/bin/git pack-objects --use-bitmap-index --revs --stdout --thin  >/dev/null\nCounting objects: 220909, done.\nCompressing objects: 100% (14203/14203), done.\nTotal 220909 (delta 194050), reused 220909 (delta 199885)\n3.57user 1.28system 0:04.59elapsed 105%CPU (0avgtext+0avgdata 2007296maxresident)k\n0inputs+0outputs (0major+416243minor)pagefaults 0swaps\n\nI didn't do much testing here, I did run git-index-pack --fix-thin\nthen git fsck, as a sanity check.\n\nI'd appreciate feedback here, if this is a valid approach, maybe\nsomebody more involved in the bitmap branch would be interested\nin implementing the actual logic to figure out if the thin\nrevision is valid\n\n * I was rather confused as to how --thin works today. I could\n   not figure out how the choice was made to reuse a thin delta\n   in the existing code base.\n * I had a very hacky way of communicating to the pack writing code\n   that there was a delta, but that it need not take that into\n   account for the pruposes of sorting the file. Does anybody have\n   a better suggestion here?\n\nSigned-off-by: Ben Maurer <bmaurer@fb.com>\n---\n builtin/pack-objects.c | 26 +++++++++++++++++++-------\n pack-objects.h         |  1 +\n 2 files changed, 20 insertions(+), 7 deletions(-)\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex c2f2847..3dc4411 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -53,6 +53,7 @@ static unsigned long pack_size_limit;\n static int depth = 50;\n static int delta_search_threads;\n static int pack_to_stdout;\n+static int thin = 0;\n static int num_preferred_base;\n static struct progress *progress_state;\n static int pack_compression_level = Z_DEFAULT_COMPRESSION;\n@@ -347,7 +348,8 @@ static unsigned long write_no_reuse_object(struct sha1file *f, struct object_ent\n\n /* Return 0 if we will bust the pack-size limit */\n static unsigned long write_reuse_object(struct sha1file *f, struct object_entry *entry,\n-\t\t\t\t\tunsigned long limit, int usable_delta)\n+\t\t\t\t\tunsigned long limit, int usable_delta,\n+\t\t\t\t\tconst unsigned char* thin_delta_sha1)\n {\n \tstruct packed_git *p = entry->in_pack;\n \tstruct pack_window *w_curs = NULL;\n@@ -361,7 +363,11 @@ static unsigned long write_reuse_object(struct sha1file *f, struct object_entry\n \tif (entry->delta)\n \t\ttype = (allow_ofs_delta && entry->delta->idx.offset) ?\n \t\t\tOBJ_OFS_DELTA : OBJ_REF_DELTA;\n-\thdrlen = encode_in_pack_object_header(type, entry->size, header);\n+\n+\tif (thin_delta_sha1)\n+\t\ttype = OBJ_REF_DELTA;\n+\n+\thdrlen = encode_in_pack_object_header(type, thin_delta_sha1 ? entry->delta_size : entry->size, header);\n\n \toffset = entry->in_pack_offset;\n \trevidx = find_pack_revindex(p, offset);\n@@ -403,7 +409,7 @@ static unsigned long write_reuse_object(struct sha1file *f, struct object_entry\n \t\t\treturn 0;\n \t\t}\n \t\tsha1write(f, header, hdrlen);\n-\t\tsha1write(f, entry->delta->idx.sha1, 20);\n+\t\tsha1write(f, thin_delta_sha1 ? thin_delta_sha1 : entry->delta->idx.sha1, 20);\n \t\thdrlen += 20;\n \t\treused_delta++;\n \t} else {\n@@ -469,11 +475,13 @@ static unsigned long write_object(struct sha1file *f,\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+\tif (!is_null_sha1(entry->thin_delta_ref))\n+\t\tlen = write_reuse_object(f, entry, limit, usable_delta,\n+\t\t\t\t\t entry->thin_delta_ref);\n+\telse if (!to_reuse)\n \t\tlen = write_no_reuse_object(f, entry, limit, usable_delta);\n \telse\n-\t\tlen = write_reuse_object(f, entry, limit, usable_delta);\n+\t\tlen = write_reuse_object(f, entry, limit, usable_delta, NULL);\n \tif (!len)\n \t\treturn 0;\n\n@@ -1358,6 +1366,9 @@ static void check_object(struct object_entry *entry)\n \t\t\tbase_entry->delta_child = entry;\n \t\t\tunuse_pack(&w_curs);\n \t\t\treturn;\n+\t\t} else if (base_ref && pack_to_stdout && thin) {\n+\t\t\thashcpy(entry->thin_delta_ref, base_ref);\n+\t\t\tentry->delta_size = entry->size;\n \t\t}\n\n \t\tif (entry->type) {\n@@ -2088,6 +2099,8 @@ static void prepare_pack(int window, int depth)\n\n \t\tif (entry->no_try_delta)\n \t\t\tcontinue;\n+\t\tif (!is_null_sha1(entry->thin_delta_ref))\n+\t\t\tcontinue;\n\n \t\tif (!entry->preferred_base) {\n \t\t\tnr_deltas++;\n@@ -2493,7 +2506,6 @@ static int option_parse_ulong(const struct option *opt,\n int cmd_pack_objects(int argc, const char **argv, const char *prefix)\n {\n \tint use_internal_rev_list = 0;\n-\tint thin = 0;\n \tint all_progress_implied = 0;\n \tconst char *rp_av[6];\n \tint rp_ac = 0;\ndiff --git a/pack-objects.h b/pack-objects.h\nindex d1b98b3..a973bc5 100644\n--- a/pack-objects.h\n+++ b/pack-objects.h\n@@ -27,6 +27,7 @@ struct object_entry {\n \tunsigned no_try_delta:1;\n \tunsigned tagged:1; /* near the very tip of refs */\n \tunsigned filled:1; /* assigned write-order */\n+\tunsigned char thin_delta_ref[20];\n };\n\n struct packing_data {\n--\n1.8.1\n"},{"id":"232357","messageId":"5CDDBDF2D36D9F43B9F5E99003F6A0D43B67C0DA@PRN-MBX02-1.TheFacebook.com","threadId":"35568","inReplyTo":"1387741654-14890-1-git-send-email-bmaurer@fb.com","subject":"RE: [PATCH] [RFC] Making use of bitmaps for thin objects","fromName":"Ben Maurer","fromEmail":"bmaurer@fb.com","sentAt":"2013-12-22T21:55:23Z","receivedAt":"2013-12-22T21:55:23Z","isPatch":true,"sender":{"key":"bmaurer@fb.com","avatar":null},"body":"One issue with this approach is that it seems git-pack-index doesn't perform as well with thin packs. git-index-pack uses a multi-threaded approach to resolving the deltas. However, the multithreading only works on deltas that are exclusively in the pack. After the multi-threaded phase, it incrementally brings in objects from external packs, but in single threaded manner. Many objects in the pack have some dependency on an external object, therefore, defeating the multithreading.\n\nWhat's the use case for a pack file with a SHA1 reference living inside the pack file (why not just use an offset?) Would it make sense to assume that all such files are external and bring them in in the first phase."},{"id":"232715","messageId":"20140106145723.GA15489@sigill.intra.peff.net","threadId":"35568","inReplyTo":"1387741654-14890-1-git-send-email-bmaurer@fb.com","subject":"Re: [PATCH] [RFC] Making use of bitmaps for thin objects","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-01-06T14:57:24Z","receivedAt":"2014-01-06T14:57:24Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Dec 22, 2013 at 11:47:34AM -0800, Ben Maurer wrote:\n\n> Jeff King's bitmap branch appears to give a very substantial speedup.\n> After applying this branch, the \"counting objects\" phase is basically\n> free. However, I found that the compression phase still takes a\n> non-trivial amount of time.\n\nSorry for the slow reply; I've been on vacation.\n\nFirst off, I'm excited that you're looking into using bitmaps. We've\nbeen using them for a while at GitHub, but more testing is definitely\nappreciated. :)\n\nWhen you build your bitmaps, do you set the pack.writeBitmapHashCache\noption? We found that it makes a significant difference during the\ncompression phase, as otherwise git attempts deltas between random files\nbased on size. Here are some numbers for a simulated fetch from\ntorvalds/linux, representing about 7 weeks of history. Running:\n\n  from=2d3c627502f2a9b0a7de06a5a2df2365542a72c9\n  to=f0a679afefc0b6288310f88606b4bb1f243f1aa9\n  run() {\n    (echo $to && echo ^$from) |\n    git pack-objects --stdout --all-progress --revs >/dev/null\n  }\n\n  echo \"==> no hash cache\"\n  git repack -adb 2>/dev/null\n  time run\n\n  echo \"==> with hash cache\"\n  git -c pack.writebitmaphashcache=1 repack -adb 2>/dev/null\n  time run\n\nproduces:\n\n  ==> no hash cache\n  Counting objects: 20661, done.\n  Delta compression using up to 8 threads.\n  Compressing objects: 100% (7700/7700), done.\n  Writing objects: 100% (20661/20661), 23.23 MiB | 11.13 MiB/s, done.\n  Total 20661 (delta 13884), reused 16638 (delta 12940)\n\n  real    0m3.626s\n  user    0m10.760s\n  sys     0m0.060s\n\n  ==> with hash cache\n  Counting objects: 20661, done.\n  Delta compression using up to 8 threads.\n  Compressing objects: 100% (7700/7700), done.\n  Writing objects: 100% (20661/20661), 22.64 MiB | 10.82 MiB/s, done.\n  Total 20661 (delta 14038), reused 16638 (delta 12940)\n\n  real    0m3.072s\n  user    0m6.168s\n  sys     0m0.100s\n\nSo our resulting pack shrinks a little because we find better deltas,\nbut note that we save a fair bit of CPU time (the wall clock time ends\nup not all that different, because the single-threaded writing phase\nrepresents a big chunk of that).\n\n> It looks like most of the time spent compressing objects was in cases\n> where the object was already compressed in the packfile, but the delta\n> was based on an object that the client already had. For some reason,\n> --thin wasn't enabling reuse of these deltas.\n\nI'm not too surprised. The long-time strategy for a fetch has been to\nwalk down the \"haves\" and \"wants\" to their merge base. That boundary\ncommit is marked as a \"preferred base\", meaning we won't send it, but\nit's a good base for other objects, since we know the client has it.\n\nTechnically _all_ of the history reachable from that merge base could be\nmarked as a preferred base, but we don't do so for efficiency reasons:\n\n  1. It's expensive to walk the full object graph for a small fetch, and\n\n  2. You would clog the delta-search algorithm if you had a very large\n     number of preferred-base objects.\n\nWith bitmaps, though, the history walk is free (we just check each\nobject against our \"have\" bitmap), so (1) is a non-issue. For (2), we\nprobably don't want to stick each object into the preferred-base list,\nbut we do want to reuse on-disk deltas we have, if we know the other\nside has the base.\n\nI don't know if you went through the same line of thinking, but that\nmatches your proposed solution. :)\n\n> This is a hacky, poorly styled attempt to figure how how much better\n> performance could be. With the bitmap branch, git should know what\n> objects the client has already and can easily test if an existing delta\n> can be reused. I don't know the branch well enough to code this, so\n> as a hack, I just assumed the client has any delta base that is in\n> the pack file (for our repo, this is always true, because we have a\n> linear history)\n\nEven without a linear history, it mostly works. If you are fetching all\nof the branches from the other side, then you will end up with all of\nthe objects that the remote has. Which means that either you already\nhave the base, or the remote is about to send it to you.\n\nIt will break down, though, whenever the other side has something you're\nnot fetching. For that you really need to do the \"have\" bitmap check.\n\n> This greatly reduces the time:\n> \n> $ { echo HEAD && echo ^$have; } | time ../git-bitmap/install/bin/git pack-objects --use-bitmap-index --revs --stdout --thin  >/dev/null\n> Counting objects: 220909, done.\n> Compressing objects: 100% (14203/14203), done.\n> Total 220909 (delta 194050), reused 220909 (delta 199885)\n> 3.57user 1.28system 0:04.59elapsed 105%CPU (0avgtext+0avgdata 2007296maxresident)k\n> 0inputs+0outputs (0major+416243minor)pagefaults 0swaps\n\nYou might try with \"--all-progress\" (or pipe to \"wc -c\"), as this should\nbe reducing the output size, too.\n\nHere's my same torvalds/linux test, run with the patch I'm including\nbelow:\n\n  Counting objects: 20661, done.\n  Delta compression using up to 8 threads.\n  Compressing objects: 100% (3677/3677), done.\n  Writing objects: 100% (20661/20661), 5.17 MiB | 0 bytes/s, done.\n  Total 20661 (delta 16963), reused 20661 (delta 16963)\n\n  real    0m0.355s\n  user    0m0.312s\n  sys     0m0.044s\n\nWe dropped an order of magnitude in time, but we also shrunk the\npackfile from 22MiB to 5MiB! That's good enough to make me assume\nthere's a bug in my code. :)\n\n> I'd appreciate feedback here, if this is a valid approach, maybe\n> somebody more involved in the bitmap branch would be interested\n> in implementing the actual logic to figure out if the thin\n> revision is valid\n\nIt's definitely a valid approach. I'm not sure if JGit is doing this\noptimization itself already, but it was something we were already\nconsidering for C git.\n\n>  * I was rather confused as to how --thin works today. I could\n>    not figure out how the choice was made to reuse a thin delta\n>    in the existing code base.\n\nHaving been confused by it myself before, I think the magic keyword is\n\"preferred base\". Once you know that, the code makes more sense. :)\n\n>  * I had a very hacky way of communicating to the pack writing code\n>    that there was a delta, but that it need not take that into\n>    account for the pruposes of sorting the file. Does anybody have\n>    a better suggestion here?\n\nYes. Your approach writes the thin-sha1 into a special field in the\nobject_entry. This has two downsides:\n\n  1. It bloats the object_entry by 20 bytes. Given that a full repack of\n     the kernel has over 4 million of these, that's 80MB.\n\n  2. You have to special-case many sites which are expecting to find\n     delta information in entry->delta.\n\nWe can solve both by storing the information in entry->delta.  Usually\nthat field points to another object_entry in the main \"to-pack\" list,\neither for an object we are sending or for a preferred base. But since\nwe don't want to clog the list, we can just allocate a one-off\nobject_entry to use as the base.\n\nI came up with the patch below. We _may_ need to allocate the \"fake\"\nobject_entry bases in a separate list, and actually connect them\ncorrectly via the delta_child/delta_sibling pointers, but I haven't\nlooked carefully yet at how those fields are used (I think it is mostly\nfor write order, but we don't care here since the base objects aren't\nbeing written at all).\n\nLet me know how this patch does for you. My testing has been fairly\nlimited so far.\n\n---\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex c733379..0cff874 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -1402,6 +1402,19 @@ static void check_object(struct object_entry *entry)\n \t\t\tbase_entry->delta_child = entry;\n \t\t\tunuse_pack(&w_curs);\n \t\t\treturn;\n+\t\t} else if(base_ref && bitmap_have(base_ref)) {\n+\t\t\tentry->type = entry->in_pack_type;\n+\t\t\tentry->delta_size = entry->size;\n+\t\t\t/*\n+\t\t\t * XXX we'll leak this, but it's probably OK\n+\t\t\t * since we'll exit immediately after the packing\n+\t\t\t * is done\n+\t\t\t */\n+\t\t\tentry->delta = xcalloc(1, sizeof(*entry->delta));\n+\t\t\thashcpy(entry->delta->idx.sha1, base_ref);\n+\t\t\tentry->delta->preferred_base = 1;\n+\t\t\tunuse_pack(&w_curs);\n+\t\t\treturn;\n \t\t}\n \n \t\tif (entry->type) {\ndiff --git a/pack-bitmap.c b/pack-bitmap.c\nindex ae0b57b..1bae7e8 100644\n--- a/pack-bitmap.c\n+++ b/pack-bitmap.c\n@@ -86,6 +86,9 @@ static struct bitmap_index {\n \t/* Bitmap result of the last performed walk */\n \tstruct bitmap *result;\n \n+\t/* \"have\" bitmap from the last performed walk */\n+\tstruct bitmap *haves;\n+\n \t/* Version of the bitmap index */\n \tunsigned int version;\n \n@@ -743,8 +746,8 @@ int prepare_bitmap_walk(struct rev_info *revs)\n \t\tbitmap_and_not(wants_bitmap, haves_bitmap);\n \n \tbitmap_git.result = wants_bitmap;\n+\tbitmap_git.haves = haves_bitmap;\n \n-\tbitmap_free(haves_bitmap);\n \treturn 0;\n }\n \n@@ -1071,3 +1074,19 @@ int rebuild_existing_bitmaps(struct packing_data *mapping,\n \tbitmap_free(rebuild);\n \treturn 0;\n }\n+\n+int bitmap_have(const unsigned char *sha1)\n+{\n+\tint pos;\n+\n+\tif (!bitmap_git.loaded)\n+\t\treturn 0; /* no bitmap loaded */\n+\tif (!bitmap_git.haves)\n+\t\treturn 0; /* walk had no \"haves\" */\n+\n+\tpos = bitmap_position_packfile(sha1);\n+\tif (pos < 0)\n+\t\treturn 0;\n+\n+\treturn bitmap_get(bitmap_git.haves, pos);\n+}\ndiff --git a/pack-bitmap.h b/pack-bitmap.h\nindex 8b7f4e9..a63ee6b 100644\n--- a/pack-bitmap.h\n+++ b/pack-bitmap.h\n@@ -49,6 +49,8 @@ int prepare_bitmap_walk(struct rev_info *revs);\n int reuse_partial_packfile_from_bitmap(struct packed_git **packfile, uint32_t *entries, off_t *up_to);\n int rebuild_existing_bitmaps(struct packing_data *mapping, khash_sha1 *reused_bitmaps, int show_progress);\n \n+int bitmap_have(const unsigned char *sha1);\n+\n void bitmap_writer_show_progress(int show);\n void bitmap_writer_set_checksum(unsigned char *sha1);\n void bitmap_writer_build_type_index(struct pack_idx_entry **index, uint32_t index_nr);\n"},{"id":"232716","messageId":"20140106151052.GB15489@sigill.intra.peff.net","threadId":"35568","inReplyTo":"5CDDBDF2D36D9F43B9F5E99003F6A0D43B67C0DA@PRN-MBX02-1.TheFacebook.com","subject":"Re: [PATCH] [RFC] Making use of bitmaps for thin objects","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-01-06T15:10:52Z","receivedAt":"2014-01-06T15:10:52Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Dec 22, 2013 at 09:55:23PM +0000, Ben Maurer wrote:\n\n> One issue with this approach is that it seems git-pack-index doesn't\n> perform as well with thin packs. git-index-pack uses a multi-threaded\n> approach to resolving the deltas. However, the multithreading only\n> works on deltas that are exclusively in the pack. After the\n> multi-threaded phase, it incrementally brings in objects from external\n> packs, but in single threaded manner. Many objects in the pack have\n> some dependency on an external object, therefore, defeating the\n> multithreading.\n\nYes. It will also just plain perform worse, because it will have to\ncopy over more external objects. This is somewhat made up for getting an\nactual smaller pack size, but I suspect the completed thin-pack ends up\nlarger than what the server would otherwise send. Because the server is\nblindly reusing on-disk deltas (which is good, because it takes load off\nof the server), it misses good delta opportunities between objects in\nthe sent pack (which are likely almost as small, but would not require\nfixing on the other end).\n\nSingle-threading the extra work we have to do just exacerbates the\nproblem, of course.\n\nStill, I think it will be a net win for end-to-end wall clock time of\nthe operation. You are saving CPU time on the server end, and you're\nsaving network bandwidth with a smaller pack.\n\nIn my tests on torvalds/linux, doing a fetch across a local machine (so\nbasically discounting network improvements), the times look like (this\nis end-to-end, counting both server and client CPU time):\n\n  [vanilla]\n  real    0m3.850s\n  user    0m7.504s\n  sys     0m0.380s\n\n  [patched]\n  real    0m2.785s\n  user    0m2.472s\n  sys     0m0.180s\n\nSo it was a win both for wall-clock and CPU.\n\n> What's the use case for a pack file with a SHA1 reference living\n> inside the pack file (why not just use an offset?) Would it make sense\n> to assume that all such files are external and bring them in in the\n> first phase.\n\nOnce upon a time, ref-delta was the only format supported by packfiles. Later,\ndelta-base-offset was invented, and the client and server negotiate the\nuse of the feature before the packfile is generated (and even when we\nreuse objects, pack-objects will rewrite the header on the fly to use\nref-delta if necessary).\n\nThese days, pretty much everybody supports delta-base-offset, so I don't\nthink there is any reason index-pack should see ref-delta for a non-thin\nobject. We could probably teach index-pack an \"--assume-refs-are-thin\"\noption to optimize for this case, and have fetch-pack/receive-pack pass\nit whenever they know that delta-base-offset was negotiated.\n\n-Peff\n"},{"id":"232726","messageId":"xmqq38l1kqw2.fsf@gitster.dls.corp.google.com","threadId":"35568","inReplyTo":"20140106151052.GB15489@sigill.intra.peff.net","subject":"Re: [PATCH] [RFC] Making use of bitmaps for thin objects","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-01-06T16:37:49Z","receivedAt":"2014-01-06T16:37:49Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> We could probably teach index-pack an \"--assume-refs-are-thin\"\n> option to optimize for this case, and have fetch-pack/receive-pack pass\n> it whenever they know that delta-base-offset was negotiated.\n\nI thought the existing negotiation merely means \"I understand offset\nencoded bases, so you are allowed to use that encoding\", not \"I will\nnot accept encoding other than the offset format, so you must use\nthat encoding for everything\".\n"},{"id":"232754","messageId":"20140106194152.GB27062@sigill.intra.peff.net","threadId":"35568","inReplyTo":"xmqq38l1kqw2.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH] [RFC] Making use of bitmaps for thin objects","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-01-06T19:41:52Z","receivedAt":"2014-01-06T19:41:52Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Jan 06, 2014 at 08:37:49AM -0800, Junio C Hamano wrote:\n\n> Jeff King <peff@peff.net> writes:\n> \n> > We could probably teach index-pack an \"--assume-refs-are-thin\"\n> > option to optimize for this case, and have fetch-pack/receive-pack pass\n> > it whenever they know that delta-base-offset was negotiated.\n> \n> I thought the existing negotiation merely means \"I understand offset\n> encoded bases, so you are allowed to use that encoding\", not \"I will\n> not accept encoding other than the offset format, so you must use\n> that encoding for everything\".\n\nYou are right about what it means. But this is an optimization, not a\ncorrectness thing. So if we assume that senders who are allowed to send\noffsets will generally do so, it might be a reasonable optimization to\nguess that ref-delta objects will need thin completion. If we are wrong,\nthe worst case is that we add an extra local object to the end of the\npack. So as long as we are right most of the time, it may still be a\nwin.\n\nOf course, it may also be possible to simply multi-thread the\nthin-completion portion of index-pack. That would be even better, though\nI am not sure how it would work. The resolution of an object in one\nthread can always become the input for another thread. But maybe we\ncould have each thread come up with a proposed set of objects to add to\nthe pack, and then drop duplicates or something. I haven't looked\nclosely.\n\n-Peff\n"},{"id":"232761","messageId":"20140106203847.GA643@sigill.intra.peff.net","threadId":"35568","inReplyTo":"20140106145723.GA15489@sigill.intra.peff.net","subject":"Re: [PATCH] [RFC] Making use of bitmaps for thin objects","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-01-06T20:38:47Z","receivedAt":"2014-01-06T20:38:47Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Jan 06, 2014 at 09:57:23AM -0500, Jeff King wrote:\n\n> diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\n> index c733379..0cff874 100644\n> --- a/builtin/pack-objects.c\n> +++ b/builtin/pack-objects.c\n> @@ -1402,6 +1402,19 @@ static void check_object(struct object_entry *entry)\n>  \t\t\tbase_entry->delta_child = entry;\n>  \t\t\tunuse_pack(&w_curs);\n>  \t\t\treturn;\n> +\t\t} else if(base_ref && bitmap_have(base_ref)) {\n> +\t\t\tentry->type = entry->in_pack_type;\n> +\t\t\tentry->delta_size = entry->size;\n> +\t\t\t/*\n> +\t\t\t * XXX we'll leak this, but it's probably OK\n> +\t\t\t * since we'll exit immediately after the packing\n> +\t\t\t * is done\n> +\t\t\t */\n> +\t\t\tentry->delta = xcalloc(1, sizeof(*entry->delta));\n> +\t\t\thashcpy(entry->delta->idx.sha1, base_ref);\n> +\t\t\tentry->delta->preferred_base = 1;\n> +\t\t\tunuse_pack(&w_curs);\n> +\t\t\treturn;\n>  \t\t}\n\nJust reading over this again, the conditional here should obviously be\nchecking \"thin\" (which needs to become a global, as in your patch).\n\n-Peff\n"},{"id":"232766","messageId":"5CDDBDF2D36D9F43B9F5E99003F6A0D4466883DF@PRN-MBX02-1.TheFacebook.com","threadId":"35568","inReplyTo":"20140106145723.GA15489@sigill.intra.peff.net","subject":"RE: [PATCH] [RFC] Making use of bitmaps for thin objects","fromName":"Ben Maurer","fromEmail":"bmaurer@fb.com","sentAt":"2014-01-06T21:15:04Z","receivedAt":"2014-01-06T21:15:04Z","isPatch":true,"sender":{"key":"bmaurer@fb.com","avatar":null},"body":"> Sorry for the slow reply; I've been on vacation.\n\nNo worries.\n\n> When you build your bitmaps, do you set the pack.writeBitmapHashCache\n> option? We found that it makes a significant difference during the\n> compression phase, as otherwise git attempts deltas between random files\n> based on size. Here are some numbers for a simulated fetch from\n> torvalds/linux, representing about 7 weeks of history. Running:\n\nYeah, I enabled this option. I don't have timings for generating the bitmap index without this option unfortunately (this is a pretty large repo, doing the full repack that I needed to do to generate the first version took 15+ minutes)\n\n> Having been confused by it myself before, I think the magic keyword is\n> \"preferred base\". Once you know that, the code makes more sense. :)\n\nAh, nice! That was pretty confusing :-)\n\n> Let me know how this patch does for you. My testing has been fairly\n> limited so far.\n\nThis patch looks like a much cleaner version :-). Works well for me, but my test setup may not be great since I didn't get any errors from completely ignoring the haves bitmap :-). "},{"id":"232771","messageId":"20140106215713.GA7133@sigill.intra.peff.net","threadId":"35568","inReplyTo":"5CDDBDF2D36D9F43B9F5E99003F6A0D4466883DF@PRN-MBX02-1.TheFacebook.com","subject":"Re: [PATCH] [RFC] Making use of bitmaps for thin objects","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-01-06T21:57:13Z","receivedAt":"2014-01-06T21:57:13Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Jan 06, 2014 at 09:15:04PM +0000, Ben Maurer wrote:\n\n> > Let me know how this patch does for you. My testing has been fairly\n> > limited so far.\n> \n> This patch looks like a much cleaner version :-). Works well for me,\n> but my test setup may not be great since I didn't get any errors from\n> completely ignoring the haves bitmap :-).\n\nGreat. Out of curiosity, can you show the before/after? The timings\nshould be similar to what your patch produced, but I'm really curious to\nsee how the pack size changes.\n\n-Peff\n"},{"id":"232775","messageId":"5CDDBDF2D36D9F43B9F5E99003F6A0D4466885EE@PRN-MBX02-1.TheFacebook.com","threadId":"35568","inReplyTo":"20140106215713.GA7133@sigill.intra.peff.net","subject":"RE: [PATCH] [RFC] Making use of bitmaps for thin objects","fromName":"Ben Maurer","fromEmail":"bmaurer@fb.com","sentAt":"2014-01-06T22:14:30Z","receivedAt":"2014-01-06T22:14:30Z","isPatch":true,"sender":{"key":"bmaurer@fb.com","avatar":null},"body":"It looks like for my repo the size win wasn't as big (~10%). Is it possible that with the kernel test you got extremely lucky and there was some huge binary blob that thin packing turned into a tiny delta?\n\nThe repo I'm testing with here isn't a typical codebase -- it is used to store configuration information and it has very different update patterns than most codebases.\n\nWhen you get a chance, it'd be handy if you could push an updated version of your change out to your public github repo. I'd like to see if folks here are interested in testing this more, and it'd be good to make sure we're testing the diff that is targeted for upstream.\n\nBitmap index, without thin packing:\n\nCounting objects: 158825, done.\nDelta compression using up to 32 threads.\nCompressing objects: 100% (18113/18113), done.\nWriting objects: 100% (158825/158825), 89.87 MiB | 11.23 MiB/s, done.\nTotal 158825 (delta 139493), reused 153076 (delta 135730)\nreal 15.60\nuser 34.38\nsys 2.99\n\n\nBitmap index, with thin packing:\n\nCounting objects: 158825, done.\nDelta compression using up to 32 threads.\nCompressing objects: 100% (12364/12364), done.\nWriting objects: 100% (158825/158825), 81.35 MiB | 0 bytes/s, done.\nTotal 158825 (delta 135730), reused 158825 (delta 141479)\nreal 2.70\nuser 2.28\nsys 0.65\n\n\n________________________________________\nFrom: Jeff King [peff@peff.net]\nSent: Monday, January 06, 2014 1:57 PM\nTo: Ben Maurer\nCc: git@vger.kernel.org\nSubject: Re: [PATCH] [RFC] Making use of bitmaps for thin objects\n\nOn Mon, Jan 06, 2014 at 09:15:04PM +0000, Ben Maurer wrote:\n\n> > Let me know how this patch does for you. My testing has been fairly\n> > limited so far.\n>\n> This patch looks like a much cleaner version :-). Works well for me,\n> but my test setup may not be great since I didn't get any errors from\n> completely ignoring the haves bitmap :-).\n\nGreat. Out of curiosity, can you show the before/after? The timings\nshould be similar to what your patch produced, but I'm really curious to\nsee how the pack size changes.\n\n-Peff\n"},{"id":"232813","messageId":"20140107172644.GA19051@sigill.intra.peff.net","threadId":"35568","inReplyTo":"5CDDBDF2D36D9F43B9F5E99003F6A0D4466885EE@PRN-MBX02-1.TheFacebook.com","subject":"Re: [PATCH] [RFC] Making use of bitmaps for thin objects","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-01-07T17:26:44Z","receivedAt":"2014-01-07T17:26:44Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Jan 06, 2014 at 10:14:30PM +0000, Ben Maurer wrote:\n\n> It looks like for my repo the size win wasn't as big (~10%). Is it\n> possible that with the kernel test you got extremely lucky and there\n> was some huge binary blob that thin packing turned into a tiny delta?\n\nI don't think so. When I look at the reused-delta numbers, I see that we\nreused ~3000 extra deltas (and the \"compressing\" progress meter drops by\nthe same amount. If I do a full clone (or just index-pack the result),\nit claims ~3000 thin objects completed with local objects (versus 0 in\nthe normal case).\n\nSo I think we really are getting a lot of little savings adding up,\nwhich makes sense. If there were thousands of changed files, a non-thin\npack has to have at least _one_ full version of each file. With thin\npacks, we might literally have only deltas.\n\nIt was a 7-week period, which might make more difference. I'm going to\nrun some experiments with different time periods to see if that changes\nanything.\n\nIt might also be the repo contents. I'm going to try my experiments on a\nfew different repositories. It may be that either the kernel or your\nrepo is unusual in some way.\n\nOr maybe I was just lucky. :)\n\n> When you get a chance, it'd be handy if you could push an updated\n> version of your change out to your public github repo. I'd like to see\n> if folks here are interested in testing this more, and it'd be good to\n> make sure we're testing the diff that is targeted for upstream.\n\nI've pushed it to:\n\n  git://github.com/peff/git.git jk/bitmap-reuse-delta\n\nI'll continue to rebase it forward as time goes on (until a cleaned-up\nversion gets merged upstream), but the tip of that branch should always\nbe in a working state.\n\n-Peff\n"}]}