When building a large list of objects, most of the time is spent in created_object() inserting the objects in the sorted list. This patch splits the list in 256 sublists to reduce the impact of the O(n^2) list insertion.
On the WineHQ repository (220,000 objects), the patch reduces the time needed for a 'git-rev-list --objects HEAD' from 2 minutes to 20 seconds.
Signed-off-by: Alexandre Julliard <julliard@winehq.org>
---
fsck-objects.c | 66 +++++++++++++++++++++++++++++--------------------------- name-rev.c | 9 ++++---- object.c | 24 ++++++++++---------- object.h | 4 ++- 4 files changed, 53 insertions(+), 50 deletions(-)
68f8fcb7f5883ecc44a80e822e0b78ee8efd9eb9
Show changes to 4 files +53 −50
fsck-objects.c, name-rev.c, object.c, object.h
diff --git a/fsck-objects.c b/fsck-objects.c index 9950be2..5bdb21e 100644 --- a/fsck-objects.c +++ b/fsck-objects.c @@ -58,45 +58,47 @@ static int objwarning(struct object *obj static void check_connectivity(void) { - int i; + int i, j; /* Look up all the requirements, warn about missing objects.. */ - for (i = 0; i < nr_objs; i++) { - struct object *obj = objs[i]; + for (i = 0; i < 256; i++) { + for (j = 0; j < nr_objs[i]; j++) { + struct object *obj = objs[i][j]; - if (!obj->parsed) { - if (!standalone && has_sha1_file(obj->sha1)) - ; /* it is in pack */ - else - printf("missing %s %s\n", - obj->type, sha1_to_hex(obj->sha1)); - continue; - } + if (!obj->parsed) { + if (!standalone && has_sha1_file(obj->sha1)) + ; /* it is in pack */ + else + printf("missing %s %s\n", + obj->type, sha1_to_hex(obj->sha1)); + continue; + } - if (obj->refs) { - const struct object_refs *refs = obj->refs; - unsigned j; - for (j = 0; j < refs->count; j++) { - struct object *ref = refs->ref[j]; - if (ref->parsed || - (!standalone && has_sha1_file(ref->sha1))) - continue; - printf("broken link from %7s %s\n", - obj->type, sha1_to_hex(obj->sha1)); - printf(" to %7s %s\n", - ref->type, sha1_to_hex(ref->sha1)); + if (obj->refs) { + const struct object_refs *refs = obj->refs; + unsigned k; + for (k = 0; k < refs->count; k++) { + struct object *ref = refs->ref[k]; + if (ref->parsed || + (!standalone && has_sha1_file(ref->sha1))) + continue; + printf("broken link from %7s %s\n", + obj->type, sha1_to_hex(obj->sha1)); + printf(" to %7s %s\n", + ref->type, sha1_to_hex(ref->sha1)); + } } - } - if (show_unreachable && !(obj->flags & REACHABLE)) { - printf("unreachable %s %s\n", - obj->type, sha1_to_hex(obj->sha1)); - continue; - } + if (show_unreachable && !(obj->flags & REACHABLE)) { + printf("unreachable %s %s\n", + obj->type, sha1_to_hex(obj->sha1)); + continue; + } - if (!obj->used) { - printf("dangling %s %s\n", obj->type, - sha1_to_hex(obj->sha1)); + if (!obj->used) { + printf("dangling %s %s\n", obj->type, + sha1_to_hex(obj->sha1)); + } } } } diff --git a/name-rev.c b/name-rev.c index bbadb91..9a8d086 100644 --- a/name-rev.c +++ b/name-rev.c @@ -230,11 +230,12 @@ int main(int argc, char **argv) fwrite(p_start, p - p_start, 1, stdout); } } else if (all) { - int i; + int i, j; - for (i = 0; i < nr_objs; i++) - printf("%s %s\n", sha1_to_hex(objs[i]->sha1), - get_rev_name(objs[i])); + for (i = 0; i < 256; i++) + for (j = 0; j < nr_objs[i]; j++) + printf("%s %s\n", sha1_to_hex(objs[i][j]->sha1), + get_rev_name(objs[i][j])); } else for ( ; revs; revs = revs->next) printf("%s %s\n", revs->name, get_rev_name(revs->item)); diff --git a/object.c b/object.c index 1577f74..fcd4d0c 100644 --- a/object.c +++ b/object.c @@ -5,19 +5,19 @@ #include "commit.h" #include "tag.h" -struct object **objs; -int nr_objs; -static int obj_allocs; +struct object **objs[256]; +int nr_objs[256]; +static int obj_allocs[256]; int track_object_refs = 1; static int find_object(const unsigned char *sha1) { - int first = 0, last = nr_objs; + int first = 0, last = nr_objs[*sha1]; while (first < last) { int next = (first + last) / 2; - struct object *obj = objs[next]; + struct object *obj = objs[*sha1][next]; int cmp; cmp = memcmp(sha1, obj->sha1, 20); @@ -36,7 +36,7 @@ struct object *lookup_object(const unsig { int pos = find_object(sha1); if (pos >= 0) - return objs[pos]; + return objs[*sha1][pos]; return NULL; } @@ -54,17 +54,17 @@ void created_object(const unsigned char die("Inserting %s twice\n", sha1_to_hex(sha1)); pos = -pos-1; - if (obj_allocs == nr_objs) { - obj_allocs = alloc_nr(obj_allocs); - objs = xrealloc(objs, obj_allocs * sizeof(struct object *)); + if (obj_allocs[*sha1] == nr_objs[*sha1]) { + obj_allocs[*sha1] = alloc_nr(obj_allocs[*sha1]); + objs[*sha1] = xrealloc(objs[*sha1], obj_allocs[*sha1] * sizeof(struct object *)); } /* Insert it into the right place */ - memmove(objs + pos + 1, objs + pos, (nr_objs - pos) * + memmove(objs[*sha1] + pos + 1, objs[*sha1] + pos, (nr_objs[*sha1] - pos) * sizeof(struct object *)); - objs[pos] = obj; - nr_objs++; + objs[*sha1][pos] = obj; + nr_objs[*sha1]++; } struct object_refs *alloc_object_refs(unsigned count) diff --git a/object.h b/object.h index 0e76182..dcd6ac4 100644 --- a/object.h +++ b/object.h @@ -23,8 +23,8 @@ struct object { }; extern int track_object_refs; -extern int nr_objs; -extern struct object **objs; +extern int nr_objs[256]; +extern struct object **objs[256]; /** Internal only **/ struct object *lookup_object(const unsigned char *sha1);
-- 1.1.6.g68f8 -- Alexandre Julliard julliard@winehq.org
