From 4a4e6fd74f7d4564ed43eaaf59b6bd70c1959f1a Mon Sep 17 00:00:00 2001 From: Sergey Vlasov Date: Tue, 15 Nov 2005 19:08:08 +0300 Subject: Rework object refs tracking to reduce memory usage Store pointers to referenced objects in a variable sized array instead of linked list. This cuts down memory usage of utilities which use object references; e.g., git-fsck-objects --full on the git.git repository consumes about 2 MB of memory tracked by Massif instead of 7 MB before the change. Object refs are still the biggest consumer of memory (57%), but the malloc overhead for a single block instead of a linked list is substantially smaller. Signed-off-by: Sergey Vlasov Signed-off-by: Junio C Hamano --- object.c | 62 ++++++++++++++++++++++++++++++++++++++++++++------------------ 1 file changed, 44 insertions(+), 18 deletions(-) (limited to 'object.c') diff --git a/object.c b/object.c index 1fdebe012b..427e14cae2 100644 --- a/object.c +++ b/object.c @@ -67,40 +67,66 @@ void created_object(const unsigned char *sha1, struct object *obj) nr_objs++; } -void add_ref(struct object *refer, struct object *target) +struct object_refs *alloc_object_refs(unsigned count) { - struct object_list **pp, *p; + struct object_refs *refs; + size_t size = sizeof(*refs) + count*sizeof(struct object *); - if (!track_object_refs) + refs = xmalloc(size); + memset(refs, 0, size); + refs->count = count; + return refs; +} + +static int compare_object_pointers(const void *a, const void *b) +{ + const struct object * const *pa = a; + const struct object * const *pb = b; + return *pa - *pb; +} + +void set_object_refs(struct object *obj, struct object_refs *refs) +{ + unsigned int i, j; + + /* Do not install empty list of references */ + if (refs->count < 1) { + free(refs); return; + } - pp = &refer->refs; - while ((p = *pp) != NULL) { - if (p->item == target) - return; - pp = &p->next; + /* Sort the list and filter out duplicates */ + qsort(refs->ref, refs->count, sizeof(refs->ref[0]), + compare_object_pointers); + for (i = j = 1; i < refs->count; i++) { + if (refs->ref[i] != refs->ref[i - 1]) + refs->ref[j++] = refs->ref[i]; + } + if (j < refs->count) { + /* Duplicates were found - reallocate list */ + size_t size = sizeof(*refs) + j*sizeof(struct object *); + refs->count = j; + refs = xrealloc(refs, size); } - target->used = 1; - p = xmalloc(sizeof(*p)); - p->item = target; - p->next = NULL; - *pp = p; + for (i = 0; i < refs->count; i++) + refs->ref[i]->used = 1; + obj->refs = refs; } void mark_reachable(struct object *obj, unsigned int mask) { - struct object_list *p = obj->refs; - if (!track_object_refs) die("cannot do reachability with object refs turned off"); /* If we've been here already, don't bother */ if (obj->flags & mask) return; obj->flags |= mask; - while (p) { - mark_reachable(p->item, mask); - p = p->next; + if (obj->refs) { + const struct object_refs *refs = obj->refs; + unsigned i; + for (i = 0; i < refs->count; i++) + mark_reachable(refs->ref[i], mask); } } -- cgit v1.2.1