# [PATCH] walker: avoid quadratic list insertion in mark_complete

2 messages from 2014-08-21 to 2014-08-22. Participants: René Scharfe, Jeff King.
Thread: https://gitlist.dev/t/37394

## René Scharfe, 2014-08-21 18:30

Subject: [PATCH] walker: avoid quadratic list insertion in mark_complete
Message-ID: <53F63AC0.1090605@web.de>
URL: https://gitlist.dev/e/53F63AC0.1090605%40web.de

```
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.

Signed-off-by: Rene Scharfe <l.s.r@web.de>
---
 walker.c | 6 ++++--
 1 file changed, 4 insertions(+), 2 deletions(-)

diff --git a/walker.c b/walker.c
index 0148264..0596e99 100644
--- a/walker.c
+++ b/walker.c
@@ -205,7 +205,7 @@ static int mark_complete(const char *path, const unsigned char *sha1, int flag,
 	struct commit *commit = lookup_commit_reference_gently(sha1, 1);
 	if (commit) {
 		commit->object.flags |= COMPLETE;
-		commit_list_insert_by_date(commit, &complete);
+		commit_list_insert(commit, &complete);
 	}
 	return 0;
 }
@@ -271,8 +271,10 @@ int walker_fetch(struct walker *walker, int targets, char **target,
 		}
 	}
 
-	if (!walker->get_recover)
+	if (!walker->get_recover) {
 		for_each_ref(mark_complete, NULL);
+		commit_list_sort_by_date(&complete);
+	}
 
 	for (i = 0; i < targets; i++) {
 		if (interpret_target(walker, target[i], &sha1[20 * i])) {
-- 
2.1.0

```

## Jeff King, 2014-08-22 04:01

Subject: Re: [PATCH] walker: avoid quadratic list insertion in mark_complete
Message-ID: <20140822040131.GA27992@peff.net>
URL: https://gitlist.dev/e/20140822040131.GA27992%40peff.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

```