{"thread":{"id":"17907","subject":"Really slow 'git gc'","startedAt":"2009-02-19T20:24:43Z","lastAt":"2009-02-19T21:34:32Z","messageCount":4,"participants":["Linus Torvalds","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"105507","messageId":"alpine.LFD.2.00.0902191200010.21686@localhost.localdomain","threadId":"17907","inReplyTo":null,"subject":"Really slow 'git gc'","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2009-02-19T20:24:43Z","receivedAt":"2009-02-19T20:24:43Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nOk, so I was wondering why doing a 'git gc' on my kernel backup on one of \nthe linux-foundation machines was taking so long, and I think I've found a \nperformance problem.\n\nThe way I do kernel back-ups is that I just push to two different sites \nevery once in a while (read: multiple times a day when I do lots of \nmerging), and one of them is master.kernel.org that then gets published to \nothers.\n\nThe other one is a linux-foundation machine that I have a login on, and \nthat's my \"secondary\" back-up, in case both kernel.org and my own home \nmachines were to be corrupted somehow. And because it's my secondary, I \nseldom then log in an gc anything, so it's a mess.\n\nBut it was _really_ slow when I finally did so today. The whole \"Counting \nobjects\" phase was counting by hundreds, which it really shouldn't do on a \nfast machine.\n\nThe reason? Tons and tons of pack-files. But just the existence of the \npack-files is not what killed it: things were _much_ faster if I just did \na \"git pack-objects\" by hand. \n\nThe real reason _seems_ to be the \"--unpacked=pack-....pack\" arguments. I \nliterally had 232 pack-files, and it looks like a lot of the time was \nspent in that silly loop oer 'ignore_packed' in find_pack_entry(), when \nrevision.c does that \"has_sha1_pack()\" thing. You get a O(n**2) effect in \nnumber of pack-files: for each commit we look over every pack-file, and \nfor every pack-file we look at, we look over each ignore_pack entry.\n\nI didn't really analyze this a lot, and now the thing is packed and much \nfaster, but I thought I'd throw this out there..\n\n\t\tLinus\n"},{"id":"105517","messageId":"7vr61uku2f.fsf@gitster.siamese.dyndns.org","threadId":"17907","inReplyTo":"alpine.LFD.2.00.0902191200010.21686@localhost.localdomain","subject":"Re: Really slow 'git gc'","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-02-19T21:14:48Z","receivedAt":"2009-02-19T21:14:48Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds <torvalds@linux-foundation.org> writes:\n\n> The real reason _seems_ to be the \"--unpacked=pack-....pack\" arguments. I \n> literally had 232 pack-files, and it looks like a lot of the time was \n> spent in that silly loop oer 'ignore_packed' in find_pack_entry(), when \n> revision.c does that \"has_sha1_pack()\" thing. You get a O(n**2) effect in \n> number of pack-files: for each commit we look over every pack-file, and \n> for every pack-file we look at, we look over each ignore_pack entry.\n\nI think we can add a single bit to \"struct packed_git\" and in the middle\nof setup_revisions() perform the O(N**2) once, so that find_pack_entry()\ncan check the bit without looping.\n"},{"id":"105518","messageId":"alpine.LFD.2.00.0902191318310.21686@localhost.localdomain","threadId":"17907","inReplyTo":"7vr61uku2f.fsf@gitster.siamese.dyndns.org","subject":"Re: Really slow 'git gc'","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2009-02-19T21:25:30Z","receivedAt":"2009-02-19T21:25:30Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 19 Feb 2009, Junio C Hamano wrote:\n> \n> I think we can add a single bit to \"struct packed_git\" and in the middle\n> of setup_revisions() perform the O(N**2) once, so that find_pack_entry()\n> can check the bit without looping.\n\nYes. However, most users call find_pack_entry() with a NULL ignore_packed, \nso we'd still have to pass in that flag to say whether we should look at \nthe bit or not.\n\nHowever, the real issue (?) I think is that the whole \"ignore_packed\" \nlogic is crazy. It's the wrong way around. The whole thing is broken.\n\nRather than marking which ones are \"unpacked\" and should be ignored, it \nshould just look at the ones to keep. That's how the filesystem layout \nworks and that's what \"git repack\" does anyway.\n\nSo I think we should just remove the whole \"--unpacked=\" thing, and \ninstead replace it with a \"--keep\" flag - and then only finding things in \nthe keep packs if we have a list of them.\n\nThat would (a) make the logic a whole lot easier to follow and (b) get rid \nof the scalability issue, since you're not really supposed to have more \nthan one or two .keep files anyway (if that).\n\nNobody uses \"--unpacked=xyzzy\" by hand anyway. The only thing that \ngenerates those things is git-repack.sh, so this is not a compatibility \nissue, I suspect.\n\n\t\t\tLinus\n"},{"id":"105524","messageId":"7vk57mkt5j.fsf@gitster.siamese.dyndns.org","threadId":"17907","inReplyTo":"7vr61uku2f.fsf@gitster.siamese.dyndns.org","subject":"Re: Really slow 'git gc'","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-02-19T21:34:32Z","receivedAt":"2009-02-19T21:34:32Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano <gitster@pobox.com> writes:\n\n> Linus Torvalds <torvalds@linux-foundation.org> writes:\n>\n>> The real reason _seems_ to be the \"--unpacked=pack-....pack\" arguments. I \n>> literally had 232 pack-files, and it looks like a lot of the time was \n>> spent in that silly loop oer 'ignore_packed' in find_pack_entry(), when \n>> revision.c does that \"has_sha1_pack()\" thing. You get a O(n**2) effect in \n>> number of pack-files: for each commit we look over every pack-file, and \n>> for every pack-file we look at, we look over each ignore_pack entry.\n>\n> I think we can add a single bit to \"struct packed_git\" and in the middle\n> of setup_revisions() perform the O(N**2) once, so that find_pack_entry()\n> can check the bit without looping.\n\nRoughly like this, although we probably should change the API because most\nof the callers pass NULL to it.  Also we may need a way to say \"I am done\nwith ignoring, please clear the pack_ignore bits from all of them\" API.\n\n---\n\n cache.h     |    4 +++-\n revision.c  |    2 ++\n sha1_file.c |   31 +++++++++++++++++++++++--------\n 3 files changed, 28 insertions(+), 9 deletions(-)\n\ndiff --git a/cache.h b/cache.h\nindex 37dfb1c..7e8c008 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -759,7 +759,8 @@ extern struct packed_git {\n \ttime_t mtime;\n \tint pack_fd;\n \tunsigned pack_local:1,\n-\t\t pack_keep:1;\n+\t\t pack_keep:1,\n+\t\t pack_ignore:1;\n \tunsigned char sha1[20];\n \t/* something like \".git/objects/pack/xxxxx.pack\" */\n \tchar pack_name[FLEX_ARRAY]; /* more */\n@@ -817,6 +818,7 @@ extern struct packed_git *parse_pack_index(unsigned char *sha1);\n extern void prepare_packed_git(void);\n extern void reprepare_packed_git(void);\n extern void install_packed_git(struct packed_git *pack);\n+extern void mark_ignore_packed(const char **);\n \n extern struct packed_git *find_sha1_pack(const unsigned char *sha1,\n \t\t\t\t\t struct packed_git *packs);\ndiff --git a/revision.c b/revision.c\nindex 286e416..86f80da 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -1342,6 +1342,8 @@ int setup_revisions(int argc, const char **argv, struct rev_info *revs, const ch\n \t\tobject = get_reference(revs, revs->def, sha1, 0);\n \t\tadd_pending_object_with_mode(revs, object, revs->def, mode);\n \t}\n+\tif (revs->ignore_packed)\n+\t\tmark_ignore_packed(revs->ignore_packed);\n \n \t/* Did the user ask for any diff output? Run the diff! */\n \tif (revs->diffopt.output_format & ~DIFF_FORMAT_NO_OUTPUT)\ndiff --git a/sha1_file.c b/sha1_file.c\nindex 5b6e0f6..4a804c7 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -1937,6 +1937,27 @@ int matches_pack_name(struct packed_git *p, const char *name)\n \treturn 0;\n }\n \n+void mark_ignore_packed(const char **ignore_packed)\n+{\n+\tstruct packed_git *p;\n+\n+\tif (!ignore_packed || !*ignore_packed)\n+\t\treturn;\n+\n+\tprepare_packed_git();\n+\tif (!packed_git)\n+\t\treturn;\n+\n+\tfor (p = packed_git; p; p = p->next) {\n+\t\tconst char **ig;\n+\t\tfor (ig = ignore_packed; *ig; ig++)\n+\t\t\tif (matches_pack_name(p, *ig)) {\n+\t\t\t\tp->pack_ignore = 1;\n+\t\t\t\tbreak;\n+\t\t\t}\n+\t}\n+}\n+\n static int find_pack_entry(const unsigned char *sha1, struct pack_entry *e, const char **ignore_packed)\n {\n \tstatic struct packed_git *last_found = (void *)1;\n@@ -1949,14 +1970,8 @@ static int find_pack_entry(const unsigned char *sha1, struct pack_entry *e, cons\n \tp = (last_found == (void *)1) ? packed_git : last_found;\n \n \tdo {\n-\t\tif (ignore_packed) {\n-\t\t\tconst char **ig;\n-\t\t\tfor (ig = ignore_packed; *ig; ig++)\n-\t\t\t\tif (matches_pack_name(p, *ig))\n-\t\t\t\t\tbreak;\n-\t\t\tif (*ig)\n-\t\t\t\tgoto next;\n-\t\t}\n+\t\tif (ignore_packed && p->pack_ignore)\n+\t\t\tgoto next;\n \n \t\tif (p->num_bad_objects) {\n \t\t\tunsigned i;\n"}]}