[PATCH 4/4] fetch-pack: use priority queue for mark_complete

[Jeff King <peff@peff.net>]

The regular commit_list has quadratic insertion complexity.
Fetch-pack will insert an item for each ref we have.  For a
"normal" number of refs, this is not a big deal, but it is
quite inefficient when you have tens or hundreds of
thousands of refs.

Instead, let's use a priority queue with better insertion
performance. For example, timings from one repo (which
stores alternates for all of the Rails forks at GitHub, with
mirrored refs from each individual repo to manage object
pruning):

  $ git for-each-ref | wc -l
  112514

  [before]
  $ time 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

  [after]
  $ time git fetch --no-tags ../remote.git
  6.20user 0.03system 0:06.25elapsed 99%CPU (0avgtext+0avgdata 123712maxresident)k
  0inputs+40outputs (0major+18885minor)pagefaults 0swaps

Signed-off-by: Jeff King <peff@peff.net>
---
So this is the big performance-win patch. But if you didn't read my
other "fetch: avoid repeated commits in mark_complete", go do that. It's
a much simpler solution that yields the same speedup in practice.

 builtin/fetch-pack.c |   11 ++++++-----
 1 files changed, 6 insertions(+), 5 deletions(-)

diff --git a/builtin/fetch-pack.c b/builtin/fetch-pack.c
index 85aff02..9a951f3 100644
--- a/builtin/fetch-pack.c
+++ b/builtin/fetch-pack.c
@@ -457,7 +457,7 @@ done:
 	return count ? retval : 0;
 }
 
-static struct commit_list *complete;
+static struct queue complete = COMMIT_QUEUE_INIT;
 
 static int mark_complete(const char *path, const unsigned char *sha1, int flag, void *cb_data)
 {
@@ -473,18 +473,19 @@ 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);
+		queue_insert(&complete, commit);
 	}
 	return 0;
 }
 
 static void mark_recent_complete_commits(unsigned long cutoff)
 {
-	while (complete && cutoff <= complete->item->date) {
+	struct commit *c;
+	while ((c = queue_peek(&complete)) && cutoff <= c->date) {
 		if (args.verbose)
 			fprintf(stderr, "Marking %s as complete\n",
-				sha1_to_hex(complete->item->object.sha1));
-		pop_most_recent_commit(&complete, COMPLETE);
+				sha1_to_hex(c->object.sha1));
+		pop_commit_from_queue(&complete, COMPLETE);
 	}
 }
 
-- 
1.7.5.8.ga95ab