# Really slow 'git gc' 4 messages from 2009-02-19 to 2009-02-19. Participants: Linus Torvalds, Junio C Hamano. Thread: https://gitlist.dev/t/17907 ## Linus Torvalds, 2009-02-19 20:24 Subject: Really slow 'git gc' Message-ID: URL: https://gitlist.dev/e/alpine.LFD.2.00.0902191200010.21686%40localhost.localdomain ``` Ok, so I was wondering why doing a 'git gc' on my kernel backup on one of the linux-foundation machines was taking so long, and I think I've found a performance problem. The way I do kernel back-ups is that I just push to two different sites every once in a while (read: multiple times a day when I do lots of merging), and one of them is master.kernel.org that then gets published to others. The other one is a linux-foundation machine that I have a login on, and that's my "secondary" back-up, in case both kernel.org and my own home machines were to be corrupted somehow. And because it's my secondary, I seldom then log in an gc anything, so it's a mess. But it was _really_ slow when I finally did so today. The whole "Counting objects" phase was counting by hundreds, which it really shouldn't do on a fast machine. The reason? Tons and tons of pack-files. But just the existence of the pack-files is not what killed it: things were _much_ faster if I just did a "git pack-objects" by hand. The real reason _seems_ to be the "--unpacked=pack-....pack" arguments. I literally had 232 pack-files, and it looks like a lot of the time was spent in that silly loop oer 'ignore_packed' in find_pack_entry(), when revision.c does that "has_sha1_pack()" thing. You get a O(n**2) effect in number of pack-files: for each commit we look over every pack-file, and for every pack-file we look at, we look over each ignore_pack entry. I didn't really analyze this a lot, and now the thing is packed and much faster, but I thought I'd throw this out there.. Linus ``` ## Junio C Hamano, 2009-02-19 21:14 Subject: Re: Really slow 'git gc' Message-ID: <7vr61uku2f.fsf@gitster.siamese.dyndns.org> URL: https://gitlist.dev/e/7vr61uku2f.fsf%40gitster.siamese.dyndns.org In-Reply-To: ``` Linus Torvalds writes: > The real reason _seems_ to be the "--unpacked=pack-....pack" arguments. I > literally had 232 pack-files, and it looks like a lot of the time was > spent in that silly loop oer 'ignore_packed' in find_pack_entry(), when > revision.c does that "has_sha1_pack()" thing. You get a O(n**2) effect in > number of pack-files: for each commit we look over every pack-file, and > for every pack-file we look at, we look over each ignore_pack entry. I think we can add a single bit to "struct packed_git" and in the middle of setup_revisions() perform the O(N**2) once, so that find_pack_entry() can check the bit without looping. ``` ## Linus Torvalds, 2009-02-19 21:25 Subject: Re: Really slow 'git gc' Message-ID: URL: https://gitlist.dev/e/alpine.LFD.2.00.0902191318310.21686%40localhost.localdomain In-Reply-To: <7vr61uku2f.fsf@gitster.siamese.dyndns.org> ``` On Thu, 19 Feb 2009, Junio C Hamano wrote: > > I think we can add a single bit to "struct packed_git" and in the middle > of setup_revisions() perform the O(N**2) once, so that find_pack_entry() > can check the bit without looping. Yes. However, most users call find_pack_entry() with a NULL ignore_packed, so we'd still have to pass in that flag to say whether we should look at the bit or not. However, the real issue (?) I think is that the whole "ignore_packed" logic is crazy. It's the wrong way around. The whole thing is broken. Rather than marking which ones are "unpacked" and should be ignored, it should just look at the ones to keep. That's how the filesystem layout works and that's what "git repack" does anyway. So I think we should just remove the whole "--unpacked=" thing, and instead replace it with a "--keep" flag - and then only finding things in the keep packs if we have a list of them. That would (a) make the logic a whole lot easier to follow and (b) get rid of the scalability issue, since you're not really supposed to have more than one or two .keep files anyway (if that). Nobody uses "--unpacked=xyzzy" by hand anyway. The only thing that generates those things is git-repack.sh, so this is not a compatibility issue, I suspect. Linus ``` ## Junio C Hamano, 2009-02-19 21:34 Subject: Re: Really slow 'git gc' Message-ID: <7vk57mkt5j.fsf@gitster.siamese.dyndns.org> URL: https://gitlist.dev/e/7vk57mkt5j.fsf%40gitster.siamese.dyndns.org In-Reply-To: <7vr61uku2f.fsf@gitster.siamese.dyndns.org> ``` Junio C Hamano writes: > Linus Torvalds writes: > >> The real reason _seems_ to be the "--unpacked=pack-....pack" arguments. I >> literally had 232 pack-files, and it looks like a lot of the time was >> spent in that silly loop oer 'ignore_packed' in find_pack_entry(), when >> revision.c does that "has_sha1_pack()" thing. You get a O(n**2) effect in >> number of pack-files: for each commit we look over every pack-file, and >> for every pack-file we look at, we look over each ignore_pack entry. > > I think we can add a single bit to "struct packed_git" and in the middle > of setup_revisions() perform the O(N**2) once, so that find_pack_entry() > can check the bit without looping. Roughly like this, although we probably should change the API because most of the callers pass NULL to it. Also we may need a way to say "I am done with ignoring, please clear the pack_ignore bits from all of them" API. --- cache.h | 4 +++- revision.c | 2 ++ sha1_file.c | 31 +++++++++++++++++++++++-------- 3 files changed, 28 insertions(+), 9 deletions(-) diff --git a/cache.h b/cache.h index 37dfb1c..7e8c008 100644 --- a/cache.h +++ b/cache.h @@ -759,7 +759,8 @@ extern struct packed_git { time_t mtime; int pack_fd; unsigned pack_local:1, - pack_keep:1; + pack_keep:1, + pack_ignore:1; unsigned char sha1[20]; /* something like ".git/objects/pack/xxxxx.pack" */ char pack_name[FLEX_ARRAY]; /* more */ @@ -817,6 +818,7 @@ extern struct packed_git *parse_pack_index(unsigned char *sha1); extern void prepare_packed_git(void); extern void reprepare_packed_git(void); extern void install_packed_git(struct packed_git *pack); +extern void mark_ignore_packed(const char **); extern struct packed_git *find_sha1_pack(const unsigned char *sha1, struct packed_git *packs); diff --git a/revision.c b/revision.c index 286e416..86f80da 100644 --- a/revision.c +++ b/revision.c @@ -1342,6 +1342,8 @@ int setup_revisions(int argc, const char **argv, struct rev_info *revs, const ch object = get_reference(revs, revs->def, sha1, 0); add_pending_object_with_mode(revs, object, revs->def, mode); } + if (revs->ignore_packed) + mark_ignore_packed(revs->ignore_packed); /* Did the user ask for any diff output? Run the diff! */ if (revs->diffopt.output_format & ~DIFF_FORMAT_NO_OUTPUT) diff --git a/sha1_file.c b/sha1_file.c index 5b6e0f6..4a804c7 100644 --- a/sha1_file.c +++ b/sha1_file.c @@ -1937,6 +1937,27 @@ int matches_pack_name(struct packed_git *p, const char *name) return 0; } +void mark_ignore_packed(const char **ignore_packed) +{ + struct packed_git *p; + + if (!ignore_packed || !*ignore_packed) + return; + + prepare_packed_git(); + if (!packed_git) + return; + + for (p = packed_git; p; p = p->next) { + const char **ig; + for (ig = ignore_packed; *ig; ig++) + if (matches_pack_name(p, *ig)) { + p->pack_ignore = 1; + break; + } + } +} + static int find_pack_entry(const unsigned char *sha1, struct pack_entry *e, const char **ignore_packed) { static struct packed_git *last_found = (void *)1; @@ -1949,14 +1970,8 @@ static int find_pack_entry(const unsigned char *sha1, struct pack_entry *e, cons p = (last_found == (void *)1) ? packed_git : last_found; do { - if (ignore_packed) { - const char **ig; - for (ig = ignore_packed; *ig; ig++) - if (matches_pack_name(p, *ig)) - break; - if (*ig) - goto next; - } + if (ignore_packed && p->pack_ignore) + goto next; if (p->num_bad_objects) { unsigned i; ```