From: Jeff King <peff@peff.net>
Date: Fri, 22 Aug 2014 04:01:31 GMT
Subject: Re: [PATCH] walker: avoid quadratic list insertion in mark_complete
Message-ID: <20140822040131.GA27992@peff.net>
In-Reply-To: <53F63AC0.1090605@web.de>

On Thu, Aug 21, 2014 at 08:30:24PM +0200, René Scharfe wrote:

> Similar to 16445242 (fetch-pack: avoid quadratic list insertion in
> mark_complete), sort only after all refs are collected instead of while
> inserting.  The result is the same, but it's more efficient that way.
> The difference will only be measurable in repositories with a large
> number of refs.

Thanks, this looks obviously correct.

I wonder if we should do this on top:

diff --git a/walker.c b/walker.c
index 0148264..70088b8 100644
--- a/walker.c
+++ b/walker.c
@@ -203,7 +203,7 @@ static int interpret_target(struct walker *walker, char *target, unsigned char *
 static int mark_complete(const char *path, const unsigned char *sha1, int flag, void *cb_data)
 {
 	struct commit *commit = lookup_commit_reference_gently(sha1, 1);
-	if (commit) {
+	if (commit && !(commit->object.flags & COMPLETE)) {
 		commit->object.flags |= COMPLETE;
 		commit_list_insert_by_date(commit, &complete);
 	}

It's not as big a deal with your patch since you've made it O(n log n),
but reducing n further does not hurt.

-Peff