{"thread":{"id":"25196","subject":"[PATCH] pack-objects: never deltify objects bigger than window_memory_limit.","startedAt":"2010-09-22T10:25:05Z","lastAt":"2010-09-23T05:01:45Z","messageCount":3,"participants":["Avery Pennarun","Nicolas Pitre"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"151286","messageId":"1285151105-32454-1-git-send-email-apenwarr@gmail.com","threadId":"25196","inReplyTo":null,"subject":"[PATCH] pack-objects: never deltify objects bigger than window_memory_limit.","fromName":"Avery Pennarun","fromEmail":"apenwarr@gmail.com","sentAt":"2010-09-22T10:25:05Z","receivedAt":"2010-09-22T10:25:05Z","isPatch":true,"sender":{"key":"apenwarr@gmail.com","avatar":"https://avatars.githubusercontent.com/u/20592?v=4"},"body":"With very large objects, just loading them into the delta window wastes a\nhuge amount of memory.  In one repo, I have some objects around 1GB in size,\nand git-pack-objects seems to require about 8x that in order to deltify it,\neven when the window memory limit is small (eg. --window-memory=100M).  With\nthis patch, the maximum memory usage is about halved.\n\nPerhaps more importantly, however, disabling deltification for large objects\nseems to reduce memory thrashing when you can't fit multiple large objects\ninto physical RAM at once.  It seems to be the difference between \"never\nfinishes\" and \"finishes eventually\" for me.\n\nTest:\n\nI created a test repo with 10 sequential commits containing a bunch of\nnearly-identical 110MB files (just appending a line each time).\n\nWithout this patch:\n\n    $ /usr/bin/time git repack -a --window-memory=100M\n\n    Counting objects: 43, done.\n    warning: suboptimal pack - out of memory\n    Compressing objects: 100% (43/43), done.\n    Writing objects: 100% (43/43), done.\n    Total 43 (delta 14), reused 0 (delta 0)\n    42.79user 1.07system 0:44.53elapsed 98%CPU (0avgtext+0avgdata\n      866736maxresident)k\n      0inputs+2752outputs (0major+718471minor)pagefaults 0swaps\n\nWith this patch:\n\n    $ /usr/bin/time -a git repack -a --window-memory=100M\n\n    Counting objects: 43, done.\n    Compressing objects: 100% (30/30), done.\n    Writing objects: 100% (43/43), done.\n    Total 43 (delta 14), reused 0 (delta 0)\n    35.86user 0.65system 0:36.30elapsed 100%CPU (0avgtext+0avgdata\n      437568maxresident)k\n      0inputs+2768outputs (0major+366137minor)pagefaults 0swaps\n\nIt apparently still uses about 4x the memory of the largest object, which is\nabout twice as good as before, though still kind of awful.  (Ideally, we\nwouldn't even load the entire large object into memory even once.)\n\nSigned-off-by: Avery Pennarun <apenwarr@gmail.com>\n---\n builtin/pack-objects.c |    3 +++\n 1 files changed, 3 insertions(+), 0 deletions(-)\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex 0e81673..9f1a289 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -1791,6 +1791,9 @@ static void prepare_pack(int window, int depth)\n \t\tif (entry->size < 50)\n \t\t\tcontinue;\n \n+\t\tif (window_memory_limit && entry->size > window_memory_limit)\n+                \tcontinue;\n+\n \t\tif (entry->no_try_delta)\n \t\t\tcontinue;\n \n-- \n1.7.3.1.gca9d1\n"},{"id":"151292","messageId":"alpine.LFD.2.00.1009220749440.13233@xanadu.home","threadId":"25196","inReplyTo":"1285151105-32454-1-git-send-email-apenwarr@gmail.com","subject":"Re: [PATCH] pack-objects: never deltify objects bigger than window_memory_limit.","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2010-09-22T12:00:20Z","receivedAt":"2010-09-22T12:00:20Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Wed, 22 Sep 2010, Avery Pennarun wrote:\n\n> With very large objects, just loading them into the delta window wastes a\n> huge amount of memory.  In one repo, I have some objects around 1GB in size,\n> and git-pack-objects seems to require about 8x that in order to deltify it,\n> even when the window memory limit is small (eg. --window-memory=100M).  With\n> this patch, the maximum memory usage is about halved.\n> \n> Perhaps more importantly, however, disabling deltification for large objects\n> seems to reduce memory thrashing when you can't fit multiple large objects\n> into physical RAM at once.  It seems to be the difference between \"never\n> finishes\" and \"finishes eventually\" for me.\n> \n> Test:\n> \n> I created a test repo with 10 sequential commits containing a bunch of\n> nearly-identical 110MB files (just appending a line each time).\n> \n> Without this patch:\n> \n>     $ /usr/bin/time git repack -a --window-memory=100M\n> \n>     Counting objects: 43, done.\n>     warning: suboptimal pack - out of memory\n>     Compressing objects: 100% (43/43), done.\n>     Writing objects: 100% (43/43), done.\n>     Total 43 (delta 14), reused 0 (delta 0)\n>     42.79user 1.07system 0:44.53elapsed 98%CPU (0avgtext+0avgdata\n>       866736maxresident)k\n>       0inputs+2752outputs (0major+718471minor)pagefaults 0swaps\n> \n> With this patch:\n> \n>     $ /usr/bin/time -a git repack -a --window-memory=100M\n> \n>     Counting objects: 43, done.\n>     Compressing objects: 100% (30/30), done.\n>     Writing objects: 100% (43/43), done.\n>     Total 43 (delta 14), reused 0 (delta 0)\n>     35.86user 0.65system 0:36.30elapsed 100%CPU (0avgtext+0avgdata\n>       437568maxresident)k\n>       0inputs+2768outputs (0major+366137minor)pagefaults 0swaps\n> \n> It apparently still uses about 4x the memory of the largest object, which is\n> about twice as good as before, though still kind of awful.  (Ideally, we\n> wouldn't even load the entire large object into memory even once.)\n\nTo not load big objects into memory, we'd have to add support for the \ncore.bigFileThreshold config option in more places.\n\n>  builtin/pack-objects.c |    3 +++\n>  1 files changed, 3 insertions(+), 0 deletions(-)\n> \n> diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\n> index 0e81673..9f1a289 100644\n> --- a/builtin/pack-objects.c\n> +++ b/builtin/pack-objects.c\n> @@ -1791,6 +1791,9 @@ static void prepare_pack(int window, int depth)\n>  \t\tif (entry->size < 50)\n>  \t\t\tcontinue;\n>  \n> +\t\tif (window_memory_limit && entry->size > window_memory_limit)\n> +                \tcontinue;\n> +\n\nI think you should even use entry->size/2 here, or even entry->size/4.  \nThe reason for that is 1) you need at least 2 such similar objects in \nmemory to find a possible delta, and 2) reference object to delta \nagainst has to be block indexed and that index table is almost the same \nsize as the object itself especially on 64-bit machines.\n\n\nNicolas\n"},{"id":"151339","messageId":"AANLkTinZtJc7LA5rpW85Yk+64oE38MZrs-b5af9-e1mT@mail.gmail.com","threadId":"25196","inReplyTo":"alpine.LFD.2.00.1009220749440.13233@xanadu.home","subject":"Re: [PATCH] pack-objects: never deltify objects bigger than window_memory_limit.","fromName":"Avery Pennarun","fromEmail":"apenwarr@gmail.com","sentAt":"2010-09-23T05:01:45Z","receivedAt":"2010-09-23T05:01:45Z","isPatch":true,"sender":{"key":"apenwarr@gmail.com","avatar":"https://avatars.githubusercontent.com/u/20592?v=4"},"body":"On Wed, Sep 22, 2010 at 5:00 AM, Nicolas Pitre <nico@fluxnic.net> wrote:\n> On Wed, 22 Sep 2010, Avery Pennarun wrote:\n> To not load big objects into memory, we'd have to add support for the\n> core.bigFileThreshold config option in more places.\n\nWell, it could be automatic in git-pack-objects if it was enabled when\nthe object is larger than window_memory_limit.  But I see your point.\n\nAnyway, it requires more knowledge of the guts of git (plus patience\nand motivation) than I currently have.  My patch was sufficient to get\nmy previously-un-packable repo packed on my system, which was a big\nstep forward.\n\n>> +             if (window_memory_limit && entry->size > window_memory_limit)\n>> +                     continue;\n>\n> I think you should even use entry->size/2 here, or even entry->size/4.\n> The reason for that is 1) you need at least 2 such similar objects in\n> memory to find a possible delta, and 2) reference object to delta\n> against has to be block indexed and that index table is almost the same\n> size as the object itself especially on 64-bit machines.\n\nI would be happy to re-spin my exciting two line patch to include\nwhatever threshold you think it best :)\n\nGood point about #1; dividing by two does seem like a good idea.\n(Though arguably you could construct a small object from a large one\njust by deleting a lot of stuff, and a small + large object could fit\nin a window close to the large object's size.  I doubt this happens\nfrequently, though.)\n\nAs for #2, does the block index table count toward the\nwindow_memory_limit right now?  If it doesn't, then dividing by 4\ndoesn't seem to make sense.  If it does, then it does make sense, I\nguess.  (Though maybe dividing by 3 is a bit more generous just in\ncase.)\n\nAnyway, the window_size_limit stuff seems pretty weakly implemented\noverall; with or without my patch, it seems like you could end up\nusing vastly more memory than the window size.  Imagine setting the\nwindow_memory_limit to 10MB and packing a 1GB object; it still ends up\nin memory at least two or three times, for a 200x overshoot.  Without\nmy patch, it's about 2x worse than even that, though I don't know why.\n\nSo my question is: is it worth it to try to treat window_memory_limit\nas \"maximum memory used by the pack operation\" or should it literally\nbe the maximum size of the window?  If the former, well, we've got a\nlot of work ahead of us, but dividing by 4 might be appropriate.  If\nthe latter, dividing by two is probably the most we should do.\n\nFWIW, the test timings described in my commit message are unaffected\nwhether we divide by 1, 2, or 4, because as it happens, I didn't have\nany objects between 25 and 100 MB in size :)\n\nHave fun,\n\nAvery\n"}]}