Re: Really slow 'git gc'
From: Junio C Hamano <hidden>
Date: 2016-06-15 22:46:14
Subsystem:
the rest · Maintainer:
Linus Torvalds
Possibly related (same subject, not in this thread)
- 2016-06-15 · Really slow 'git gc' · Linus Torvalds <torvalds@linux-foundation.org>
- 2016-06-15 · Re: Really slow 'git gc' · Junio C Hamano <hidden>
- 2016-06-15 · Re: Really slow 'git gc' · Linus Torvalds <torvalds@linux-foundation.org>
Junio C Hamano [off-list ref] writes:
Linus Torvalds [off-list ref] writes:quoted
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;