Subject: Re: Really slow 'git gc'

From: Junio C Hamano <[email-masked]>
Date: Thu, 19 Feb 2009 13:14:48 -0800

Linus Torvalds <[email-masked]> 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.