[PATCH] refs.c: add a function to sort a ref list, rather then sorting on add

Rather than sorting the refs list while building it, sort in one go
after it is built using a merge sort.  This has a large performance
boost with large numbers of refs.

Signed-off-by: Julian Phillips <redacted>
---

Having got builtin fetch to the point of generating a correct FETCH_HEAD (for a certain path through the code at least), I revisted the speed issue I brought up a while back with the sorting of refs.

Running fetch (builtin version) on a repo with >9000 refs which is up-to-date, using the old sort-on-add I get (best of 5, warm cache):

real    0m4.351s
user    0m4.068s
sys     0m0.219s

With this patch the same fetch gives (worst of 5, warm cache):

real    0m2.196s
user    0m1.870s
sys     0m0.212s

Since this is orthogonal to making fetch a builtin, I don't see that it needs to wait ...

 refs.c |   95 +++++++++++++++++++++++++++++++++++++++++++++++++--------------
 1 files changed, 74 insertions(+), 21 deletions(-)

diff --git a/refs.c b/refs.c
index d2b7b7f..23982fc 100644
--- a/refs.c
+++ b/refs.c

@@ -47,22 +47,7 @@ static struct ref_list *add_ref(const char *name, const unsigned char *sha1,
 				struct ref_list **new_entry)
 {
 	int len;
-	struct ref_list **p = &list, *entry;
-
-	/* Find the place to insert the ref into.. */
-	while ((entry = *p) != NULL) {
-		int cmp = strcmp(entry->name, name);
-		if (cmp > 0)
-			break;
-
-		/* Same as existing entry? */
-		if (!cmp) {
-			if (new_entry)
-				*new_entry = entry;
-			return list;
-		}
-		p = &entry->next;
-	}
+	struct ref_list *entry;
 
 	/* Allocate it and add it in.. */
 	len = strlen(name) + 1;

@@ -71,11 +56,79 @@ static struct ref_list *add_ref(const char *name, const unsigned char *sha1,
 	hashclr(entry->peeled);
 	memcpy(entry->name, name, len);
 	entry->flag = flag;
-	entry->next = *p;
-	*p = entry;
+	entry->next = list;
 	if (new_entry)
 		*new_entry = entry;
-	return list;
+	return entry;
+}
+
+/* merge sort the ref list */
+static struct ref_list *sort_ref_list(struct ref_list *list)
+{
+	int psize, qsize, last_merge_count;
+	struct ref_list *p, *q, *l, *e;
+	struct ref_list *new_list = list;
+	int k = 1;
+	int merge_count = 0;
+
+	if (!list)
+		return list;
+
+	do {
+		last_merge_count = merge_count;
+		merge_count = 0;
+
+		psize = 0;
+
+		p = new_list;
+		q = new_list;
+		new_list = NULL;
+		l = NULL;
+
+		while (p) {
+			merge_count++;
+
+			while (psize < k && q->next) {
+				q = q->next;
+				psize++;
+			}
+			qsize = k;
+
+			while ((psize > 0) || (qsize > 0 && q)) {
+				if (qsize == 0 || !q) {
+					e = p;
+					p = p->next;
+					psize--;
+				} else if (psize == 0) {
+					e = q;
+					q = q->next;
+					qsize--;
+				} else if (strcmp(q->name, p->name) < 0) {
+					e = q;
+					q = q->next;
+					qsize--;
+				} else {
+					e = p;
+					p = p->next;
+					psize--;
+				}
+
+				e->next = NULL;
+
+				if (l)
+					l->next = e;
+				if (!new_list)
+					new_list = e;
+				l = e;
+			}
+
+			p = q;
+		};
+
+		k = k * 2;
+	} while ((last_merge_count != merge_count) || (last_merge_count != 1));
+
+	return new_list;
 }
 
 /*

@@ -142,7 +195,7 @@ static void read_packed_refs(FILE *f, struct cached_refs *cached_refs)
 		    !get_sha1_hex(refline + 1, sha1))
 			hashcpy(last->peeled, sha1);
 	}
-	cached_refs->packed = list;
+	cached_refs->packed = sort_ref_list(list);
 }
 
 static struct ref_list *get_packed_refs(void)

@@ -201,7 +254,7 @@ static struct ref_list *get_ref_dir(const char *base, struct ref_list *list)
 		free(ref);
 		closedir(dir);
 	}
-	return list;
+	return sort_ref_list(list);
 }
 
 static struct ref_list *get_loose_refs(void)

-- 
1.5.1.1

On Tue, 17 Apr 2007, Julian Phillips wrote:

Rather than sorting the refs list while building it, sort in one go
after it is built using a merge sort.  This has a large performance
boost with large numbers of refs.

Signed-off-by: Julian Phillips <redacted>

Acked-by: Linus Torvalds <torvalds@linux-foundation.org>

Looks fine. I think that even your new times are a bit high (over two 
seconds?) but things are clearly better. Have you looked at what takes so 
long now? 

		Linus

On Tue, 17 Apr 2007, Linus Torvalds wrote:

On Tue, 17 Apr 2007, Julian Phillips wrote:

quoted

Rather than sorting the refs list while building it, sort in one go
after it is built using a merge sort.  This has a large performance
boost with large numbers of refs.

Signed-off-by: Julian Phillips <redacted>

Acked-by: Linus Torvalds <torvalds@linux-foundation.org>

Looks fine. I think that even your new times are a bit high (over two
seconds?) but things are clearly better. Have you looked at what takes so
long now?

It's the tag auto-following code, I'm calling read_ref to see if I already 
have that tag - and it appears that doing that a few thousand times takes 
a while.

If I comment out that one line (so the code will _always_ think I have 
the tags - but I do have them, so ...) I get:

real    0m0.472s
user    0m0.277s
sys     0m0.181s

Looks like read_ref is the wrong thing to be using ...

-- 
Julian

  ---
"Life is like a buffet; it's not good but there's plenty of it."

On Tue, 17 Apr 2007, Julian Phillips wrote:

It's the tag auto-following code, I'm calling read_ref to see if I already
have that tag - and it appears that doing that a few thousand times takes a
while.

Heh. I think we should probably call read_refs() just once to read them 
all (when most of them are packed, that's cheap), and then after that, 
have some way to just check for a match on the refs we have cached.

		Linus

On Tue, 17 Apr 2007, Julian Phillips wrote:

Rather than sorting the refs list while building it, sort in one go
after it is built using a merge sort.  This has a large performance
boost with large numbers of refs.

Signed-off-by: Julian Phillips <redacted>
---

Having got builtin fetch to the point of generating a correct FETCH_HEAD (for a certain path through the code at least), I revisted the speed issue I brought up a while back with the sorting of refs.

Running fetch (builtin version) on a repo with >9000 refs which is up-to-date, using the old sort-on-add I get (best of 5, warm cache):

real    0m4.351s
user    0m4.068s
sys     0m0.219s

With this patch the same fetch gives (worst of 5, warm cache):

real    0m2.196s
user    0m1.870s
sys     0m0.212s

Since this is orthogonal to making fetch a builtin, I don't see that it needs to wait ...

In case anyone is curious, doing the same fetch with master 
(v1.5.1.1-135-gf948792):

master (best of 5, warm cache):
real    0m33.962s
user    0m23.992s
sys     0m9.986s

master + patch (worst of 5, warm cache):
real    0m20.821s
user    0m10.390s
sys     0m9.799s

-- 
Julian

  ---
NANCY!!  Why is everything RED?!

On Tue, 17 Apr 2007, Linus Torvalds wrote:

On Tue, 17 Apr 2007, Julian Phillips wrote:

quoted

It's the tag auto-following code, I'm calling read_ref to see if I already
have that tag - and it appears that doing that a few thousand times takes a
while.

Heh. I think we should probably call read_refs() just once to read them
all (when most of them are packed, that's cheap), and then after that,
have some way to just check for a match on the refs we have cached.

I had a look at the exclude_existing function in show-ref.  That uses 
for_each_ref to build a path_list, and path_list_has_path to do the 
filtering...

Using that I get (worst of 5, warm cache):
real    0m0.526s
user    0m0.302s
sys     0m0.176s

-- 
Julian

  ---
The descent to Hades is the same from every place.
 		-- Anaxagoras