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 <julian@xxxxxxxxxxxxxxxxx>
---
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
-
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html