Re: [PATCH] walker: avoid quadratic list insertion in mark_complete
On Thu, Aug 21, 2014 at 08:30:24PM +0200, René Scharfe wrote:
Show 5 quoted lines
> 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
Jeff King <peff@peff.net>