From ea5f2208217a332dd02f62f3880052eaf8b1a57b Mon Sep 17 00:00:00 2001 From: Jeff King Date: Thu, 19 May 2011 16:48:51 -0400 Subject: [PATCH] fetch: avoid repeated commits in mark_complete We add every local ref to a list so that we can mark them and all of their ancestors back to a certain cutoff point. However, if some refs point to the same commit, we will end up adding them to the list many times. Furthermore, since commit_lists are stored as linked lists, we must do an O(n) traversal of the list in order to find the right place to insert each commit. This makes building the list O(n^2) in the number of refs. For normal repositories, this isn't a big deal. We have a few hundreds refs at most, and most of them are unique. But consider an "alternates" repo that serves as an object database for many other similar repos. For reachability, it needs to keep a copy of the refs in each child repo. This means it may have a large number of refs, many of which point to the same commits. By noting commits we have already added to the list, we can shrink the size of "n" in such a repo to the number of unique commits, which is on the order of what a normal repo would contain (it's actually more than a normal repo, since child repos may have branches at different states, but in practice it tends to be much smaller than the list with duplicates). Here are the results on one particular giant repo (containing objects for all Rails forks on GitHub): $ git for-each-ref | wc -l 112514 [before] $ git fetch --no-tags ../remote.git 63.52user 0.12system 1:03.68elapsed 99%CPU (0avgtext+0avgdata 137648maxresident)k 1856inputs+48outputs (11major+19603minor)pagefaults 0swaps $ git fetch --no-tags ../remote.git 6.15user 0.08system 0:06.25elapsed 99%CPU (0avgtext+0avgdata 123856maxresident)k 0inputs+40outputs (0major+18872minor)pagefaults 0swaps Signed-off-by: Jeff King Signed-off-by: Junio C Hamano --- builtin/fetch-pack.c | 6 ++++-- 1 file changed, 4 insertions(+), 2 deletions(-) diff --git a/builtin/fetch-pack.c b/builtin/fetch-pack.c index 85aff029b2..56c0b4a38d 100644 --- a/builtin/fetch-pack.c +++ b/builtin/fetch-pack.c @@ -472,8 +472,10 @@ static int mark_complete(const char *path, const unsigned char *sha1, int flag, } if (o && o->type == OBJ_COMMIT) { struct commit *commit = (struct commit *)o; - commit->object.flags |= COMPLETE; - commit_list_insert_by_date(commit, &complete); + if (!(commit->object.flags & COMPLETE)) { + commit->object.flags |= COMPLETE; + commit_list_insert_by_date(commit, &complete); + } } return 0; } -- 2.11.4.GIT