From: Junio C Hamano <gitster@pobox.com>
Date: Thu, 19 Feb 2009 21:14:48 GMT
Subject: Re: Really slow 'git gc'
Message-ID: <7vr61uku2f.fsf@gitster.siamese.dyndns.org>
In-Reply-To: <alpine.LFD.2.00.0902191200010.21686@localhost.localdomain>

Linus Torvalds <torvalds@linux-foundation.org> 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.