{"thread":{"id":"10752","subject":"[PATCH 05/11] Bulk allocate struct commit_list, as we do for struct commit","startedAt":"2007-11-09T11:06:24Z","lastAt":"2007-11-09T11:06:24Z","messageCount":1,"participants":["Shawn O. Pearce"],"isPatch":true,"patchVersion":1,"patchTotal":11},"messages":[{"id":"59021","messageId":"20071109110623.GE19368@spearce.org","threadId":"10752","inReplyTo":null,"subject":"[PATCH 05/11] Bulk allocate struct commit_list, as we do for struct commit","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-11-09T11:06:24Z","receivedAt":"2007-11-09T11:06:24Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Typically every commit has at least one struct commit_list allocated\nfor its parent.  It is also not uncommon for there to be more than\none allocated per commit, especially if merges are common in this\nrepository.\n\nRunning `git rev-list --all` doesn't usually wind up requiring many\ncommit_list items (about 1024 for git.git right now) as the commits\nare output as soon as they are first seen and then the parent list\nis freed as it is no longer necessary for traversal.  However when\nwe add --topo-order or --date-order and request sorting the lists\nare not deallocated until after sorting is complete.  Any memory\nthey consume during that time just increases our footprint.\n\nIn git.git for 15865 commits we need 50354 commit_lists to complete\na --topo-order sort.  That's an average of 3 commit_list items per\ncommit (I blame my local reflogs of Junio's pu branch for the high\nratio of commits to their parents).  With that kind of allocation\nindividually mallocing them is wasting a lot of memory for these\nvery small and otherwise lightwight objects.\n\nAside from reducing our memory usage during the --topo-order\nsorting case a major benefit from allocating these by blocks is we\ncan release them enmass when we release the other objects in the\nobject pool.  This reduces the cost of the scrub_commit() function\nas it no longer needs to free each parent entry individually.\n\nSigned-off-by: Shawn O. Pearce <spearce@spearce.org>\n---\n alloc.c               |    5 ++++-\n builtin-diff-tree.c   |    8 ++------\n builtin-rev-parse.c   |    2 +-\n builtin-send-pack.c   |    2 +-\n builtin-show-branch.c |    2 +-\n cache.h               |    2 ++\n commit.c              |   13 ++++++-------\n http-push.c           |    2 +-\n reflog-walk.c         |    2 +-\n revision.c            |    6 +++---\n upload-pack.c         |    2 +-\n 11 files changed, 23 insertions(+), 23 deletions(-)\n\ndiff --git a/alloc.c b/alloc.c\nindex 5737a73..b69f613 100644\n--- a/alloc.c\n+++ b/alloc.c\n@@ -51,7 +51,7 @@ static void report(const char* name, struct node_pool *p, size_t sz)\n \tcount -= p->nr;\n \n \tsz = (count * sz) >> 10;\n-\tfprintf(stderr, \"%10s: %8u (\" SZ_FMT \" kB)\", name, count, sz);\n+\tfprintf(stderr, \"%15s: %8u (\" SZ_FMT \" kB)\", name, count, sz);\n \tif (free)\n \t\tfprintf(stderr, \", %8u on free list\", free);\n \tfputc('\\n', stderr);\n@@ -144,6 +144,7 @@ static void scrub_any_object(union any_object *o)\n \t}\n }\n \n+DEFINE_ALLOCATOR(commit_list, struct commit_list)\n DEFINE_ALLOCATOR(blob, struct blob)\n DEFINE_SCRUBBING_ALLOCATOR(tree, struct tree, scrub_tree)\n DEFINE_SCRUBBING_ALLOCATOR(commit, struct commit, scrub_commit)\n@@ -155,6 +156,7 @@ void alloc_report(void)\n \treport_blob();\n \treport_tree();\n \treport_commit();\n+\treport_commit_list();\n \treport_tag();\n \treport_object();\n }\n@@ -164,6 +166,7 @@ void alloc_free_everything(void)\n \tfree_all_blob();\n \tfree_all_tree();\n \tfree_all_commit();\n+\tfree_all_commit_list();\n \tfree_all_tag();\n \tfree_all_object();\n }\ndiff --git a/builtin-diff-tree.c b/builtin-diff-tree.c\nindex 0b591c8..eb340d2 100644\n--- a/builtin-diff-tree.c\n+++ b/builtin-diff-tree.c\n@@ -31,14 +31,10 @@ static int diff_tree_stdin(char *line)\n \tif (isspace(line[40]) && !get_sha1_hex(line+41, sha1)) {\n \t\t/* Graft the fake parents locally to the commit */\n \t\tint pos = 41;\n-\t\tstruct commit_list **pptr, *parents;\n+\t\tstruct commit_list **pptr;\n \n \t\t/* Free the real parent list */\n-\t\tfor (parents = commit->parents; parents; ) {\n-\t\t\tstruct commit_list *tmp = parents->next;\n-\t\t\tfree(parents);\n-\t\t\tparents = tmp;\n-\t\t}\n+\t\tfree_commit_list(commit->parents);\n \t\tcommit->parents = NULL;\n \t\tpptr = &(commit->parents);\n \t\twhile (line[pos] && !get_sha1_hex(line + pos, sha1)) {\ndiff --git a/builtin-rev-parse.c b/builtin-rev-parse.c\nindex d1038a0..7500814 100644\n--- a/builtin-rev-parse.c\n+++ b/builtin-rev-parse.c\n@@ -200,7 +200,7 @@ static int try_difference(const char *arg)\n \t\t\t\tstruct commit_list *n = exclude->next;\n \t\t\t\tshow_rev(REVERSED,\n \t\t\t\t\t exclude->item->object.sha1,NULL);\n-\t\t\t\tfree(exclude);\n+\t\t\t\tfree_commit_list_node(exclude);\n \t\t\t\texclude = n;\n \t\t\t}\n \t\t}\ndiff --git a/builtin-send-pack.c b/builtin-send-pack.c\nindex 5a0f5c6..818519e 100644\n--- a/builtin-send-pack.c\n+++ b/builtin-send-pack.c\n@@ -82,7 +82,7 @@ static void unmark_and_free(struct commit_list *list, unsigned int mark)\n \t\tstruct commit_list *temp = list;\n \t\ttemp->item->object.flags &= ~mark;\n \t\tlist = temp->next;\n-\t\tfree(temp);\n+\t\tfree_commit_list_node(temp);\n \t}\n }\n \ndiff --git a/builtin-show-branch.c b/builtin-show-branch.c\nindex 6dc835d..f10377c 100644\n--- a/builtin-show-branch.c\n+++ b/builtin-show-branch.c\n@@ -38,7 +38,7 @@ static struct commit *pop_one_commit(struct commit_list **list_p)\n \tlist = *list_p;\n \tcommit = list->item;\n \t*list_p = list->next;\n-\tfree(list);\n+\tfree_commit_list_node(list);\n \treturn commit;\n }\n \ndiff --git a/cache.h b/cache.h\nindex 8289de1..a33c8ee 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -586,6 +586,8 @@ extern void *alloc_tree_node(void);\n extern void *alloc_commit_node(void);\n extern void *alloc_tag_node(void);\n extern void *alloc_object_node(void);\n+extern void *alloc_commit_list_node(void);\n+extern void free_commit_list_node(void *);\n extern void alloc_report(void);\n extern void alloc_free_everything(void);\n \ndiff --git a/commit.c b/commit.c\nindex 05f3cd6..796fc59 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -320,13 +320,12 @@ int parse_commit(struct commit *item)\n \n void scrub_commit(struct commit *item)\n {\n-\tfree_commit_list(item->parents);\n \tfree(item->buffer);\n }\n \n struct commit_list *commit_list_insert(struct commit *item, struct commit_list **list_p)\n {\n-\tstruct commit_list *new_list = xmalloc(sizeof(struct commit_list));\n+\tstruct commit_list *new_list = alloc_commit_list_node();\n \tnew_list->item = item;\n \tnew_list->next = *list_p;\n \t*list_p = new_list;\n@@ -338,7 +337,7 @@ void free_commit_list(struct commit_list *list)\n \twhile (list) {\n \t\tstruct commit_list *temp = list;\n \t\tlist = temp->next;\n-\t\tfree(temp);\n+\t\tfree_commit_list_node(temp);\n \t}\n }\n \n@@ -374,7 +373,7 @@ struct commit *pop_most_recent_commit(struct commit_list **list,\n \tstruct commit_list *old = *list;\n \n \t*list = (*list)->next;\n-\tfree(old);\n+\tfree_commit_list_node(old);\n \n \twhile (parents) {\n \t\tstruct commit *commit = parents->item;\n@@ -416,7 +415,7 @@ struct commit *pop_commit(struct commit_list **stack)\n \n \tif (top) {\n \t\t*stack = top->next;\n-\t\tfree(top);\n+\t\tfree_commit_list_node(top);\n \t}\n \treturn item;\n }\n@@ -561,7 +560,7 @@ static struct commit_list *merge_bases(struct commit *one, struct commit *two)\n \n \t\tcommit = list->item;\n \t\tn = list->next;\n-\t\tfree(list);\n+\t\tfree_commit_list_node(list);\n \t\tlist = n;\n \n \t\tflags = commit->object.flags & (PARENT1 | PARENT2 | STALE);\n@@ -592,7 +591,7 @@ static struct commit_list *merge_bases(struct commit *one, struct commit *two)\n \t\tstruct commit_list *n = list->next;\n \t\tif (!(list->item->object.flags & STALE))\n \t\t\tinsert_by_date(list->item, &result);\n-\t\tfree(list);\n+\t\tfree_commit_list_node(list);\n \t\tlist = n;\n \t}\n \treturn result;\ndiff --git a/http-push.c b/http-push.c\nindex 99328f5..75f1664 100644\n--- a/http-push.c\n+++ b/http-push.c\n@@ -1931,7 +1931,7 @@ static void unmark_and_free(struct commit_list *list, unsigned int mark)\n \t\tstruct commit_list *temp = list;\n \t\ttemp->item->object.flags &= ~mark;\n \t\tlist = temp->next;\n-\t\tfree(temp);\n+\t\tfree_commit_list_node(temp);\n \t}\n }\n \ndiff --git a/reflog-walk.c b/reflog-walk.c\nindex ee1456b..a6cc6ca 100644\n--- a/reflog-walk.c\n+++ b/reflog-walk.c\n@@ -236,7 +236,7 @@ void fake_reflog_parent(struct reflog_walk_info *info, struct commit *commit)\n \t\treturn;\n \t}\n \n-\tcommit->parents = xcalloc(sizeof(struct commit_list), 1);\n+\tcommit->parents = alloc_commit_list_node();\n \tcommit->parents->item = commit_info->commit;\n \tcommit->object.flags &= ~(ADDED | SEEN | SHOWN);\n }\ndiff --git a/revision.c b/revision.c\nindex 931f978..d9c3998 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -554,7 +554,7 @@ static int limit_list(struct rev_info *revs)\n \t\tshow_early_output_fn_t show;\n \n \t\tlist = list->next;\n-\t\tfree(entry);\n+\t\tfree_commit_list_node(entry);\n \n \t\tif (revs->max_age != -1 && (commit->date < revs->max_age))\n \t\t\tobj->flags |= UNINTERESTING;\n@@ -735,7 +735,7 @@ static void prepare_show_merge(struct rev_info *revs)\n \twhile (bases) {\n \t\tstruct commit *it = bases->item;\n \t\tstruct commit_list *n = bases->next;\n-\t\tfree(bases);\n+\t\tfree_commit_list_node(bases);\n \t\tbases = n;\n \t\tit->object.flags |= UNINTERESTING;\n \t\tadd_pending_object(revs, &it->object, \"(merge-base)\");\n@@ -1451,7 +1451,7 @@ static struct commit *get_revision_1(struct rev_info *revs)\n \t\tstruct commit *commit = entry->item;\n \n \t\trevs->commits = entry->next;\n-\t\tfree(entry);\n+\t\tfree_commit_list_node(entry);\n \n \t\tif (revs->reflog_info)\n \t\t\tfake_reflog_parent(revs->reflog_info, commit);\ndiff --git a/upload-pack.c b/upload-pack.c\nindex 7e04311..51796dc 100644\n--- a/upload-pack.c\n+++ b/upload-pack.c\n@@ -331,7 +331,7 @@ static int reachable(struct commit *want)\n \twhile (work) {\n \t\tstruct commit_list *list = work->next;\n \t\tstruct commit *commit = work->item;\n-\t\tfree(work);\n+\t\tfree_commit_list_node(work);\n \t\twork = list;\n \n \t\tif (commit->object.flags & THEY_HAVE) {\n-- \n1.5.3.5.1622.g41d10\n"}]}