{"thread":{"id":"2529","subject":"[PATCH] Rework object refs tracking to reduce memory usage","startedAt":"2005-11-15T16:08:08Z","lastAt":"2005-11-15T16:08:08Z","messageCount":1,"participants":["Sergey Vlasov"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"11903","messageId":"20051115160808.GG24496@master.mivlgu.local","threadId":"2529","inReplyTo":null,"subject":"[PATCH] Rework object refs tracking to reduce memory usage","fromName":"Sergey Vlasov","fromEmail":"vsu@altlinux.ru","sentAt":"2005-11-15T16:08:08Z","receivedAt":"2005-11-15T16:08:08Z","isPatch":true,"sender":{"key":"vsu@altlinux.ru","avatar":"https://avatars.githubusercontent.com/u/616082?v=4"},"body":"Store pointers to referenced objects in a variable sized array instead\nof linked list.  This cuts down memory usage of utilities which use\nobject references; e.g., git-fsck-objects --full on the git.git\nrepository consumes about 2 MB of memory tracked by Massif instead of\n7 MB before the change.  Object refs are still the biggest consumer of\nmemory (57%), but the malloc overhead for a single block instead of a\nlinked list is substantially smaller.\n\nSigned-off-by: Sergey Vlasov <vsu@altlinux.ru>\n\n\n---\n\n commit.c       |   19 ++++++++++++++---\n fsck-objects.c |   22 +++++++++++--------\n object.c       |   64 +++++++++++++++++++++++++++++++++++++++-----------------\n object.h       |   10 +++++++--\n server-info.c  |   25 ++++++++++++++++------\n tag.c          |    7 ++++--\n tree.c         |   13 +++++++++++\n 7 files changed, 117 insertions(+), 43 deletions(-)\n\napplies-to: 4d3146cd52c79f88fcc08b542630cfe7394f5047\n1ab535abd04f9150a9a7904d1459109211369f6c\ndiff --git a/commit.c b/commit.c\nindex ebf4db6..e867b86 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -204,6 +204,7 @@ int parse_commit_buffer(struct commit *i\n \tunsigned char parent[20];\n \tstruct commit_list **pptr;\n \tstruct commit_graft *graft;\n+\tunsigned n_refs = 0;\n \n \tif (item->object.parsed)\n \t\treturn 0;\n@@ -214,7 +215,7 @@ int parse_commit_buffer(struct commit *i\n \t\treturn error(\"bad tree pointer in commit %s\\n\", sha1_to_hex(item->object.sha1));\n \titem->tree = lookup_tree(parent);\n \tif (item->tree)\n-\t\tadd_ref(&item->object, &item->tree->object);\n+\t\tn_refs++;\n \tbufptr += 46; /* \"tree \" + \"hex sha1\" + \"\\n\" */\n \tpptr = &item->parents;\n \n@@ -230,7 +231,7 @@ int parse_commit_buffer(struct commit *i\n \t\tnew_parent = lookup_commit(parent);\n \t\tif (new_parent) {\n \t\t\tpptr = &commit_list_insert(new_parent, pptr)->next;\n-\t\t\tadd_ref(&item->object, &new_parent->object);\n+\t\t\tn_refs++;\n \t\t}\n \t}\n \tif (graft) {\n@@ -241,10 +242,22 @@ int parse_commit_buffer(struct commit *i\n \t\t\tif (!new_parent)\n \t\t\t\tcontinue;\n \t\t\tpptr = &commit_list_insert(new_parent, pptr)->next;\n-\t\t\tadd_ref(&item->object, &new_parent->object);\n+\t\t\tn_refs++;\n \t\t}\n \t}\n \titem->date = parse_commit_date(bufptr);\n+\n+\tif (track_object_refs) {\n+\t\tunsigned i = 0;\n+\t\tstruct commit_list *p;\n+\t\tstruct object_refs *refs = alloc_object_refs(n_refs);\n+\t\tif (item->tree)\n+\t\t\trefs->ref[i++] = &item->tree->object;\n+\t\tfor (p = item->parents; p; p = p->next)\n+\t\t\trefs->ref[i++] = &p->item->object;\n+\t\tset_object_refs(&item->object, refs);\n+\t}\n+\n \treturn 0;\n }\n \ndiff --git a/fsck-objects.c b/fsck-objects.c\nindex c1b279e..0433a1d 100644\n--- a/fsck-objects.c\n+++ b/fsck-objects.c\n@@ -56,7 +56,6 @@ static void check_connectivity(void)\n \t/* Look up all the requirements, warn about missing objects.. */\n \tfor (i = 0; i < nr_objs; i++) {\n \t\tstruct object *obj = objs[i];\n-\t\tstruct object_list *refs;\n \n \t\tif (!obj->parsed) {\n \t\t\tif (!standalone && has_sha1_file(obj->sha1))\n@@ -67,14 +66,19 @@ static void check_connectivity(void)\n \t\t\tcontinue;\n \t\t}\n \n-\t\tfor (refs = obj->refs; refs; refs = refs->next) {\n-\t\t\tif (refs->item->parsed ||\n-\t\t\t    (!standalone && has_sha1_file(refs->item->sha1)))\n-\t\t\t\tcontinue;\n-\t\t\tprintf(\"broken link from %7s %s\\n\",\n-\t\t\t       obj->type, sha1_to_hex(obj->sha1));\n-\t\t\tprintf(\"              to %7s %s\\n\",\n-\t\t\t       refs->item->type, sha1_to_hex(refs->item->sha1));\n+\t\tif (obj->refs) {\n+\t\t\tconst struct object_refs *refs = obj->refs;\n+\t\t\tunsigned j;\n+\t\t\tfor (j = 0; j < refs->count; j++) {\n+\t\t\t\tstruct object *ref = refs->ref[j];\n+\t\t\t\tif (ref->parsed ||\n+\t\t\t\t    (!standalone && has_sha1_file(ref->sha1)))\n+\t\t\t\t\tcontinue;\n+\t\t\t\tprintf(\"broken link from %7s %s\\n\",\n+\t\t\t\t       obj->type, sha1_to_hex(obj->sha1));\n+\t\t\t\tprintf(\"              to %7s %s\\n\",\n+\t\t\t\t       ref->type, sha1_to_hex(ref->sha1));\n+\t\t\t}\n \t\t}\n \n \t\tif (show_unreachable && !(obj->flags & REACHABLE)) {\ndiff --git a/object.c b/object.c\nindex 1fdebe0..427e14c 100644\n--- a/object.c\n+++ b/object.c\n@@ -67,40 +67,66 @@ void created_object(const unsigned char \n \tnr_objs++;\n }\n \n-void add_ref(struct object *refer, struct object *target)\n+struct object_refs *alloc_object_refs(unsigned count)\n {\n-\tstruct object_list **pp, *p;\n+\tstruct object_refs *refs;\n+\tsize_t size = sizeof(*refs) + count*sizeof(struct object *);\n \n-\tif (!track_object_refs)\n-\t\treturn;\n+\trefs = xmalloc(size);\n+\tmemset(refs, 0, size);\n+\trefs->count = count;\n+\treturn refs;\n+}\n+\n+static int compare_object_pointers(const void *a, const void *b)\n+{\n+\tconst struct object * const *pa = a;\n+\tconst struct object * const *pb = b;\n+\treturn *pa - *pb;\n+}\n+\n+void set_object_refs(struct object *obj, struct object_refs *refs)\n+{\n+\tunsigned int i, j;\n \n-\tpp = &refer->refs;\n-\twhile ((p = *pp) != NULL) {\n-\t\tif (p->item == target)\n-\t\t\treturn;\n-\t\tpp = &p->next;\n+\t/* Do not install empty list of references */\n+\tif (refs->count < 1) {\n+\t\tfree(refs);\n+\t\treturn;\n \t}\n \n-\ttarget->used = 1;\n-\tp = xmalloc(sizeof(*p));\n-\tp->item = target;\n-\tp->next = NULL;\n-\t*pp = p;\n+\t/* Sort the list and filter out duplicates */\n+\tqsort(refs->ref, refs->count, sizeof(refs->ref[0]),\n+\t      compare_object_pointers);\n+\tfor (i = j = 1; i < refs->count; i++) {\n+\t\tif (refs->ref[i] != refs->ref[i - 1])\n+\t\t\trefs->ref[j++] = refs->ref[i];\n+\t}\n+\tif (j < refs->count) {\n+\t\t/* Duplicates were found - reallocate list */\n+\t\tsize_t size = sizeof(*refs) + j*sizeof(struct object *);\n+\t\trefs->count = j;\n+\t\trefs = xrealloc(refs, size);\n+\t}\n+\n+\tfor (i = 0; i < refs->count; i++)\n+\t\trefs->ref[i]->used = 1;\n+\tobj->refs = refs;\n }\n \n void mark_reachable(struct object *obj, unsigned int mask)\n {\n-\tstruct object_list *p = obj->refs;\n-\n \tif (!track_object_refs)\n \t\tdie(\"cannot do reachability with object refs turned off\");\n \t/* If we've been here already, don't bother */\n \tif (obj->flags & mask)\n \t\treturn;\n \tobj->flags |= mask;\n-\twhile (p) {\n-\t\tmark_reachable(p->item, mask);\n-\t\tp = p->next;\n+\tif (obj->refs) {\n+\t\tconst struct object_refs *refs = obj->refs;\n+\t\tunsigned i;\n+\t\tfor (i = 0; i < refs->count; i++)\n+\t\t\tmark_reachable(refs->ref[i], mask);\n \t}\n }\n \ndiff --git a/object.h b/object.h\nindex 6accda3..336d986 100644\n--- a/object.h\n+++ b/object.h\n@@ -7,13 +7,18 @@ struct object_list {\n \tconst char *name;\n };\n \n+struct object_refs {\n+\tunsigned count;\n+\tstruct object *ref[0];\n+};\n+\n struct object {\n \tunsigned parsed : 1;\n \tunsigned used : 1;\n \tunsigned int flags;\n \tunsigned char sha1[20];\n \tconst char *type;\n-\tstruct object_list *refs;\n+\tstruct object_refs *refs;\n \tvoid *util;\n };\n \n@@ -35,7 +40,8 @@ struct object *parse_object(const unsign\n /** Returns the object, with potentially excess memory allocated. **/\n struct object *lookup_unknown_object(const unsigned  char *sha1);\n \n-void add_ref(struct object *refer, struct object *target);\n+struct object_refs *alloc_object_refs(unsigned count);\n+void set_object_refs(struct object *obj, struct object_refs *refs);\n \n void mark_reachable(struct object *obj, unsigned int mask);\n \ndiff --git a/server-info.c b/server-info.c\nindex 0cba8e1..e4006f0 100644\n--- a/server-info.c\n+++ b/server-info.c\n@@ -424,7 +424,6 @@ static void find_pack_info_one(int pack_\n {\n \tunsigned char sha1[20];\n \tstruct object *o;\n-\tstruct object_list *ref;\n \tint i;\n \tstruct packed_git *p = info[pack_ix]->p;\n \tint num = num_packed_objects(p);\n@@ -437,8 +436,12 @@ static void find_pack_info_one(int pack_\n \t\t\tdie(\"corrupt pack file %s?\", p->pack_name);\n \t\tif ((o = lookup_object(sha1)) == NULL)\n \t\t\tdie(\"cannot parse %s\", sha1_to_hex(sha1));\n-\t\tfor (ref = o->refs; ref; ref = ref->next)\n-\t\t\tref->item->flags = 0;\n+\t\tif (o->refs) {\n+\t\t\tstruct object_refs *refs = o->refs;\n+\t\t\tint j;\n+\t\t\tfor (j = 0; j < refs->count; j++)\n+\t\t\t\trefs->ref[j]->flags = 0;\n+\t\t}\n \t\to->flags = 0;\n \t}\n \n@@ -448,8 +451,12 @@ static void find_pack_info_one(int pack_\n \t\t\tdie(\"corrupt pack file %s?\", p->pack_name);\n \t\tif ((o = lookup_object(sha1)) == NULL)\n \t\t\tdie(\"cannot find %s\", sha1_to_hex(sha1));\n-\t\tfor (ref = o->refs; ref; ref = ref->next)\n-\t\t\tref->item->flags |= REFERENCED;\n+\t\tif (o->refs) {\n+\t\t\tstruct object_refs *refs = o->refs;\n+\t\t\tint j;\n+\t\t\tfor (j = 0; j < refs->count; j++)\n+\t\t\t\trefs->ref[j]->flags |= REFERENCED;\n+\t\t}\n \t\to->flags |= INTERNAL;\n \t}\n \n@@ -460,8 +467,12 @@ static void find_pack_info_one(int pack_\n \t\t\tdie(\"cannot find %s\", sha1_to_hex(sha1));\n \n \t\tshow(o, pack_ix);\n-\t\tfor (ref = o->refs; ref; ref = ref->next)\n-\t\t\tshow(ref->item, pack_ix);\n+\t\tif (o->refs) {\n+\t\t\tstruct object_refs *refs = o->refs;\n+\t\t\tint j;\n+\t\t\tfor (j = 0; j < refs->count; j++)\n+\t\t\t\tshow(refs->ref[j], pack_ix);\n+\t\t}\n \t}\n \n }\ndiff --git a/tag.c b/tag.c\nindex e574c4b..61ac434 100644\n--- a/tag.c\n+++ b/tag.c\n@@ -75,8 +75,11 @@ int parse_tag_buffer(struct tag *item, v\n \titem->tag[taglen] = '\\0';\n \n \titem->tagged = lookup_object_type(object, type);\n-\tif (item->tagged)\n-\t\tadd_ref(&item->object, item->tagged);\n+\tif (item->tagged && track_object_refs) {\n+\t\tstruct object_refs *refs = alloc_object_refs(1);\n+\t\trefs->ref[0] = item->tagged;\n+\t\tset_object_refs(&item->object, refs);\n+\t}\n \n \treturn 0;\n }\ndiff --git a/tree.c b/tree.c\nindex 315b6a5..8b42a07 100644\n--- a/tree.c\n+++ b/tree.c\n@@ -148,6 +148,7 @@ int parse_tree_buffer(struct tree *item,\n {\n \tvoid *bufptr = buffer;\n \tstruct tree_entry_list **list_p;\n+\tint n_refs = 0;\n \n \tif (item->object.parsed)\n \t\treturn 0;\n@@ -184,11 +185,21 @@ int parse_tree_buffer(struct tree *item,\n \t\t\tobj = &entry->item.blob->object;\n \t\t}\n \t\tif (obj)\n-\t\t\tadd_ref(&item->object, obj);\n+\t\t\tn_refs++;\n \t\tentry->parent = NULL; /* needs to be filled by the user */\n \t\t*list_p = entry;\n \t\tlist_p = &entry->next;\n \t}\n+\n+\tif (track_object_refs) {\n+\t\tstruct tree_entry_list *entry;\n+\t\tunsigned i = 0;\n+\t\tstruct object_refs *refs = alloc_object_refs(n_refs);\n+\t\tfor (entry = item->entries; entry; entry = entry->next)\n+\t\t\trefs->ref[i++] = entry->item.any;\n+\t\tset_object_refs(&item->object, refs);\n+\t}\n+\n \treturn 0;\n }\n \n---\n0.99.9.GIT\n"}]}