{"thread":{"id":"50622","subject":"[RFC PATCH 0/4] name-rev: improve memory usage","startedAt":"2019-03-01T17:50:39Z","lastAt":"2019-03-03T20:28:13Z","messageCount":18,"participants":["Alban Gruin","Eric Sunshine","Jeff King","Johannes Schindelin","Christian Couder"],"isPatch":true,"patchVersion":1,"patchTotal":4},"messages":[{"id":"370427","messageId":"20190301175024.17337-1-alban.gruin@gmail.com","threadId":"50622","inReplyTo":null,"subject":"[RFC PATCH 0/4] name-rev: improve memory usage","fromName":"Alban Gruin","fromEmail":"alban.gruin@gmail.com","sentAt":"2019-03-01T17:50:20Z","receivedAt":"2019-03-01T17:50:39Z","isPatch":true,"sender":{"key":"alban.gruin@gmail.com","avatar":"https://avatars.githubusercontent.com/u/6310153?v=4"},"body":"rafasc reported on IRC that on a repository with a lot of branches,\ntags, remotes, and commits, name-rev --stdin could use a massive amount\nof memory (more than 2GB of RAM) to complete.\n\nThis patch series tries to improve name-rev’s memory usage.\n\nThere is some improvement that could be done, such as reference counting\nthe names attributed to commits. Tell me if it could be worth to pursue\nthis way, or if name-rev’s internals would need a more thorough rewrite.\n\nThis is based on master (8104ec994e, \"Git 2.21\").\n\nThe tip of this series is tagged as \"fix-name-rev-leak-rfc-v1\" in\nhttps://github.com/agrn/git.\n\nAlban Gruin (4):\n name-rev: improve name_rev() memory usage\n commit-list: add a function to check if a commit is in a list\n name-rev: check if a commit should be named before naming it\n name-rev: avoid naming from a ref if it’s not a descendant of any\n commit\n\n builtin/name-rev.c | 124 +++++++++++++++++++++++++++++++++++----------\n commit.c | 12 +++++\n commit.h | 1 +\n 3 files changed, 111 insertions(+), 26 deletions(-)\n\n-- \n2.20.1\n\n"},{"id":"370428","messageId":"20190301175024.17337-2-alban.gruin@gmail.com","threadId":"50622","inReplyTo":"20190301175024.17337-1-alban.gruin@gmail.com","subject":"[RFC PATCH 1/4] name-rev: improve name_rev() memory usage","fromName":"Alban Gruin","fromEmail":"alban.gruin@gmail.com","sentAt":"2019-03-01T17:50:21Z","receivedAt":"2019-03-01T17:50:42Z","isPatch":true,"sender":{"key":"alban.gruin@gmail.com","avatar":"https://avatars.githubusercontent.com/u/6310153?v=4"},"body":"name_rev() is a recursive function. For each commit, it allocates the\nname of its parents, and call itself. A parent may not use a name for\nmultiple reasons, but in any case, the name will not be released. On a\nrepository with a lot of branches, tags, remotes, and commits, it can\nuse more than 2GB of RAM.\n\nTo improve the situation, name_rev() now returns a boolean to its caller\nindicating if it can release the name. The caller may free the name if\nthe commit is too old, or if the new name is not better than the current\nname.\n\nThere a condition that will always be false here when name_rev() calls\nitself for the first parent, but it will become useful when name_rev()\nwill stop to name commits that are not mentionned in the stdin buffer.\nIf the current commit should not be named, its parents may have to be,\nbut they may not. In this case, name_rev() will tell to its caller that\nthe current commit and its first parent has not used the name, and that\nit can be released. However, if the current commit has been named but\nnot its parent, or the reverse, the name will not be released.\n\nSigned-off-by: Alban Gruin \n---\n builtin/name-rev.c | 23 ++++++++++++++---------\n 1 file changed, 14 insertions(+), 9 deletions(-)\n\ndiff --git a/builtin/name-rev.c b/builtin/name-rev.c\nindex f1cb45c227..0719a9388d 100644\n--- a/builtin/name-rev.c\n+++ b/builtin/name-rev.c\n@@ -77,7 +77,7 @@ static int is_better_name(struct rev_name *name,\n \treturn 0;\n }\n \n-static void name_rev(struct commit *commit,\n+static int name_rev(struct commit *commit,\n \t\tconst char *tip_name, timestamp_t taggerdate,\n \t\tint generation, int distance, int from_tag,\n \t\tint deref)\n@@ -86,11 +86,12 @@ static void name_rev(struct commit *commit,\n \tstruct commit_list *parents;\n \tint parent_number = 1;\n \tchar *to_free = NULL;\n+\tint free_alloc = 1;\n \n \tparse_commit(commit);\n \n \tif (commit->date < cutoff)\n-\t\treturn;\n+\t\treturn 1;\n \n \tif (deref) {\n \t\ttip_name = to_free = xstrfmt(\"%s^0\", tip_name);\n@@ -111,9 +112,10 @@ static void name_rev(struct commit *commit,\n \t\tname->generation = generation;\n \t\tname->distance = distance;\n \t\tname->from_tag = from_tag;\n+\t\tfree_alloc = 0;\n \t} else {\n \t\tfree(to_free);\n-\t\treturn;\n+\t\treturn 1;\n \t}\n \n \tfor (parents = commit->parents;\n@@ -131,15 +133,18 @@ static void name_rev(struct commit *commit,\n \t\t\t\tnew_name = xstrfmt(\"%.*s^%d\", (int)len, tip_name,\n \t\t\t\t\t\t parent_number);\n \n-\t\t\tname_rev(parents->item, new_name, taggerdate, 0,\n-\t\t\t\t distance + MERGE_TRAVERSAL_WEIGHT,\n-\t\t\t\t from_tag, 0);\n+\t\t\tif (name_rev(parents->item, new_name, taggerdate, 0,\n+\t\t\t\t distance + MERGE_TRAVERSAL_WEIGHT,\n+\t\t\t\t from_tag, 0))\n+\t\t\t\tfree(new_name);\n \t\t} else {\n-\t\t\tname_rev(parents->item, tip_name, taggerdate,\n-\t\t\t\t generation + 1, distance + 1,\n-\t\t\t\t from_tag, 0);\n+\t\t\tfree_alloc &= name_rev(parents->item, tip_name, taggerdate,\n+\t\t\t\t\t generation + 1, distance + 1,\n+\t\t\t\t\t from_tag, 0);\n \t\t}\n \t}\n+\n+\treturn free_alloc;\n }\n \n static int subpath_matches(const char *path, const char *filter)\n-- \n2.20.1\n\n"},{"id":"370429","messageId":"20190301175024.17337-4-alban.gruin@gmail.com","threadId":"50622","inReplyTo":"20190301175024.17337-1-alban.gruin@gmail.com","subject":"[RFC PATCH 3/4] name-rev: check if a commit should be named before naming it","fromName":"Alban Gruin","fromEmail":"alban.gruin@gmail.com","sentAt":"2019-03-01T17:50:23Z","receivedAt":"2019-03-01T17:50:45Z","isPatch":true,"sender":{"key":"alban.gruin@gmail.com","avatar":"https://avatars.githubusercontent.com/u/6310153?v=4"},"body":"Until now, name_rev() named every commit it found, even it the name\nwould ultimately be unused.\n\nThis makes name_rev() take a commit_list and check if the commit it wants\nto name is part of the list. If it is, the commit is named, and\nname_rev() signals to its caller that the name should not be freed. If\nit is not, the commit is left unnamed. In this case, the name can still\nbe used by the first descendant of this commit (or one of its descendants).\n\nSigned-off-by: Alban Gruin \n---\n builtin/name-rev.c | 18 ++++++++++++------\n 1 file changed, 12 insertions(+), 6 deletions(-)\n\ndiff --git a/builtin/name-rev.c b/builtin/name-rev.c\nindex 0719a9388d..2f89ed50a1 100644\n--- a/builtin/name-rev.c\n+++ b/builtin/name-rev.c\n@@ -80,7 +80,7 @@ static int is_better_name(struct rev_name *name,\n static int name_rev(struct commit *commit,\n \t\tconst char *tip_name, timestamp_t taggerdate,\n \t\tint generation, int distance, int from_tag,\n-\t\tint deref)\n+\t\tint deref, struct commit_list *commits)\n {\n \tstruct rev_name *name = get_commit_rev_name(commit);\n \tstruct commit_list *parents;\n@@ -107,12 +107,18 @@ static int name_rev(struct commit *commit,\n \t} else if (is_better_name(name, tip_name, taggerdate,\n \t\t\t\t generation, distance, from_tag)) {\n copy_data:\n-\t\tname->tip_name = tip_name;\n+\t\tif (commit_list_contains(commits, commit) ||\n+\t\t commit_list_count(commits) == 0) {\n+\t\t\tname->tip_name = tip_name;\n+\t\t\tfree_alloc = 0;\n+\t\t} else {\n+\t\t\tname->tip_name = NULL;\n+\t\t}\n+\n \t\tname->taggerdate = taggerdate;\n \t\tname->generation = generation;\n \t\tname->distance = distance;\n \t\tname->from_tag = from_tag;\n-\t\tfree_alloc = 0;\n \t} else {\n \t\tfree(to_free);\n \t\treturn 1;\n@@ -135,12 +141,12 @@ static int name_rev(struct commit *commit,\n \n \t\t\tif (name_rev(parents->item, new_name, taggerdate, 0,\n \t\t\t\t distance + MERGE_TRAVERSAL_WEIGHT,\n-\t\t\t\t from_tag, 0))\n+\t\t\t\t from_tag, 0, commits))\n \t\t\t\tfree(new_name);\n \t\t} else {\n \t\t\tfree_alloc &= name_rev(parents->item, tip_name, taggerdate,\n \t\t\t\t\t generation + 1, distance + 1,\n-\t\t\t\t\t from_tag, 0);\n+\t\t\t\t\t from_tag, 0, commits);\n \t\t}\n \t}\n \n@@ -279,7 +285,7 @@ static int name_ref(const char *path, const struct object_id *oid, int flags, vo\n \t\t\ttaggerdate = ((struct commit *)o)->date;\n \t\tpath = name_ref_abbrev(path, can_abbreviate_output);\n \t\tname_rev(commit, xstrdup(path), taggerdate, 0, 0,\n-\t\t\t from_tag, deref);\n+\t\t\t from_tag, deref, NULL);\n \t}\n \treturn 0;\n }\n-- \n2.20.1\n\n"},{"id":"370430","messageId":"20190301175024.17337-3-alban.gruin@gmail.com","threadId":"50622","inReplyTo":"20190301175024.17337-1-alban.gruin@gmail.com","subject":"[RFC PATCH 2/4] commit-list: add a function to check if a commit is in a list","fromName":"Alban Gruin","fromEmail":"alban.gruin@gmail.com","sentAt":"2019-03-01T17:50:22Z","receivedAt":"2019-03-01T17:50:47Z","isPatch":true,"sender":{"key":"alban.gruin@gmail.com","avatar":"https://avatars.githubusercontent.com/u/6310153?v=4"},"body":"To avoid naming some commits, name_rev() will need to check if a commit\nis part of a commit list.\n\nSigned-off-by: Alban Gruin \n---\n commit.c | 12 ++++++++++++\n commit.h | 1 +\n 2 files changed, 13 insertions(+)\n\ndiff --git a/commit.c b/commit.c\nindex a5333c7ac6..fcb3e9245f 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -524,6 +524,18 @@ struct commit_list *commit_list_insert(struct commit *item, struct commit_list *\n \treturn new_list;\n }\n \n+int commit_list_contains(const struct commit_list *l, struct commit *commit)\n+{\n+\tconst struct commit_list *item;\n+\n+\tfor (item = l; item != NULL; item = item->next) {\n+\t\tif (oideq(&item->item->object.oid, &commit->object.oid))\n+\t\t\treturn 1;\n+\t}\n+\n+\treturn 0;\n+}\n+\n unsigned commit_list_count(const struct commit_list *l)\n {\n \tunsigned c = 0;\ndiff --git a/commit.h b/commit.h\nindex 42728c2906..c9df613b0e 100644\n--- a/commit.h\n+++ b/commit.h\n@@ -165,6 +165,7 @@ struct commit_list *commit_list_insert(struct commit *item,\n \t\t\t\t\tstruct commit_list **list);\n struct commit_list **commit_list_append(struct commit *commit,\n \t\t\t\t\tstruct commit_list **next);\n+int commit_list_contains(const struct commit_list *l, struct commit *commit);\n unsigned commit_list_count(const struct commit_list *l);\n struct commit_list *commit_list_insert_by_date(struct commit *item,\n \t\t\t\t struct commit_list **list);\n-- \n2.20.1\n\n"},{"id":"370431","messageId":"20190301175024.17337-5-alban.gruin@gmail.com","threadId":"50622","inReplyTo":"20190301175024.17337-1-alban.gruin@gmail.com","subject":"[RFC PATCH 4/4] name-rev: avoid naming from a ref if it’s not a descendant of any commit","fromName":"Alban Gruin","fromEmail":"alban.gruin@gmail.com","sentAt":"2019-03-01T17:50:24Z","receivedAt":"2019-03-01T17:50:48Z","isPatch":true,"sender":{"key":"alban.gruin@gmail.com","avatar":"https://avatars.githubusercontent.com/u/6310153?v=4"},"body":"A ref may not be the descendant of all of the commits mentionned in\nstdin. In this case, we want to avoid naming its parents.\n\nTo do this, find_commits_in_strbuf() is created. It returns a raw list\nof all the commits that have been found in the input buffer. ishex() is\nconverted to an inlined function. Then, we add a raw list of commits in\nthe name_ref_data structure, and call find_commits_in_strbuf() before\nfor_each_ref() if the user wants name-ref to process stdin. Then, for\neach ref, we check if the reachable subset of this commit list is empty\nor not. If it is, we do not call name_rev(), so we don’t name its\nparents.\n\nThe code dealing with stdin after calling for_each_ref() is no longer\nneeded as we already read it. name_rev_line() is renamed name_rev_buf()\nto reflect its new role better.\n\nSigned-off-by: Alban Gruin \n---\n builtin/name-rev.c | 91 ++++++++++++++++++++++++++++++++++++++--------\n 1 file changed, 76 insertions(+), 15 deletions(-)\n\ndiff --git a/builtin/name-rev.c b/builtin/name-rev.c\nindex 2f89ed50a1..f5860f5625 100644\n--- a/builtin/name-rev.c\n+++ b/builtin/name-rev.c\n@@ -8,6 +8,7 @@\n #include \"parse-options.h\"\n #include \"sha1-lookup.h\"\n #include \"commit-slab.h\"\n+#include \"commit-reach.h\"\n \n #define CUTOFF_DATE_SLOP 86400 /* one day */\n \n@@ -183,6 +184,8 @@ struct name_ref_data {\n \tint name_only;\n \tstruct string_list ref_filters;\n \tstruct string_list exclude_filters;\n+\tstruct commit **commits;\n+\tint commits_nr;\n };\n \n static struct tip_table {\n@@ -279,13 +282,21 @@ static int name_ref(const char *path, const struct object_id *oid, int flags, vo\n \t}\n \tif (o && o->type == OBJ_COMMIT) {\n \t\tstruct commit *commit = (struct commit *)o;\n+\t\tstruct commit_list *reachable_commits = NULL;\n \t\tint from_tag = starts_with(path, \"refs/tags/\");\n \n-\t\tif (taggerdate == TIME_MAX)\n-\t\t\ttaggerdate = ((struct commit *)o)->date;\n-\t\tpath = name_ref_abbrev(path, can_abbreviate_output);\n-\t\tname_rev(commit, xstrdup(path), taggerdate, 0, 0,\n-\t\t\t from_tag, deref, NULL);\n+\t\treachable_commits = get_reachable_subset(&commit, 1,\n+\t\t\t\t\t\t\t data->commits, data->commits_nr, 0);\n+\n+\t\tif (commit_list_count(reachable_commits) > 0 || data->commits_nr == 0) {\n+\t\t\tif (taggerdate == TIME_MAX)\n+\t\t\t\ttaggerdate = ((struct commit *)o)->date;\n+\t\t\tpath = name_ref_abbrev(path, can_abbreviate_output);\n+\t\t\tname_rev(commit, xstrdup(path), taggerdate, 0, 0,\n+\t\t\t\t from_tag, deref, reachable_commits);\n+\t\t}\n+\n+\t\tfree_commit_list(reachable_commits);\n \t}\n \treturn 0;\n }\n@@ -369,13 +380,53 @@ static char const * const name_rev_usage[] = {\n \tNULL\n };\n \n-static void name_rev_line(char *p, struct name_ref_data *data)\n+static inline int ishex(char p)\n+{\n+\treturn isdigit(p) || (p >= 'a' && p <= 'f');\n+}\n+\n+static struct commit **find_commits_in_strbuf(struct strbuf *buf, int *count)\n+{\n+\tint forty = 0;\n+\tchar *p;\n+\tstruct commit **commits = NULL;\n+\n+\t*count = 0;\n+\n+\tfor (p = buf->buf; *p; p++) {\n+\t\tif (!ishex(*p))\n+\t\t\tforty = 0;\n+\t\telse if (++forty == GIT_SHA1_HEXSZ &&\n+\t\t\t !ishex(*(p+1))) {\n+\t\t\tstruct object_id oid;\n+\t\t\tchar c = *(p+1);\n+\n+\t\t\t*(p+1) = 0;\n+\t\t\tif (!get_oid(p - (GIT_SHA1_HEXSZ -1), &oid)) {\n+\t\t\t\tstruct object *o =\n+\t\t\t\t\tparse_object(the_repository, &oid);\n+\n+\t\t\t\tif (o && o->type == OBJ_COMMIT) {\n+\t\t\t\t\tstruct commit *c = (struct commit *) o;\n+\n+\t\t\t\t\tREALLOC_ARRAY(commits, (*count) + 1);\n+\t\t\t\t\tcommits[(*count)++] = c;\n+\t\t\t\t\tset_commit_rev_name(c, NULL);\n+\t\t\t\t}\n+\t\t\t}\n+\t\t\t*(p+1) = c;\n+\t\t}\n+\t}\n+\n+\treturn commits;\n+}\n+\n+static void name_rev_buf(char *p, struct name_ref_data *data)\n {\n \tstruct strbuf buf = STRBUF_INIT;\n \tint forty = 0;\n \tchar *p_start;\n \tfor (p_start = p; *p; p++) {\n-#define ishex(x) (isdigit((x)) || ((x) >= 'a' && (x) <= 'f'))\n \t\tif (!ishex(*p))\n \t\t\tforty = 0;\n \t\telse if (++forty == GIT_SHA1_HEXSZ &&\n@@ -419,7 +470,7 @@ int cmd_name_rev(int argc, const char **argv, const char *prefix)\n {\n \tstruct object_array revs = OBJECT_ARRAY_INIT;\n \tint all = 0, transform_stdin = 0, allow_undefined = 1, always = 0, peel_tag = 0;\n-\tstruct name_ref_data data = { 0, 0, STRING_LIST_INIT_NODUP, STRING_LIST_INIT_NODUP };\n+\tstruct name_ref_data data = { 0, 0, STRING_LIST_INIT_NODUP, STRING_LIST_INIT_NODUP, NULL, 0 };\n \tstruct option opts[] = {\n \t\tOPT_BOOL(0, \"name-only\", &data.name_only, N_(\"print only names (no SHA-1)\")),\n \t\tOPT_BOOL(0, \"tags\", &data.tags_only, N_(\"only use tags to name the commits\")),\n@@ -496,20 +547,27 @@ int cmd_name_rev(int argc, const char **argv, const char *prefix)\n \n \tif (cutoff)\n \t\tcutoff = cutoff - CUTOFF_DATE_SLOP;\n-\tfor_each_ref(name_ref, &data);\n \n \tif (transform_stdin) {\n-\t\tchar buffer[2048];\n+\t\tstruct strbuf buf = STRBUF_INIT;\n \n-\t\twhile (!feof(stdin)) {\n-\t\t\tchar *p = fgets(buffer, sizeof(buffer), stdin);\n-\t\t\tif (!p)\n-\t\t\t\tbreak;\n-\t\t\tname_rev_line(p, &data);\n+\t\tstrbuf_read(&buf, STDIN_FILENO, 0);\n+\t\tdata.commits = find_commits_in_strbuf(&buf, &data.commits_nr);\n+\n+\t\tif (data.commits_nr > 0) {\n+\t\t\tfor_each_ref(name_ref, &data);\n+\t\t\tname_rev_buf(buf.buf, &data);\n+\t\t} else {\n+\t\t\tfwrite(buf.buf, buf.len, 1, stdout);\n \t\t}\n+\n+\t\tfree(data.commits);\n+\t\tstrbuf_release(&buf);\n \t} else if (all) {\n \t\tint i, max;\n \n+\t\tfor_each_ref(name_ref, &data);\n+\n \t\tmax = get_max_object_index();\n \t\tfor (i = 0; i < max; i++) {\n \t\t\tstruct object *obj = get_indexed_object(i);\n@@ -520,6 +578,9 @@ int cmd_name_rev(int argc, const char **argv, const char *prefix)\n \t\t}\n \t} else {\n \t\tint i;\n+\n+\t\tfor_each_ref(name_ref, &data);\n+\n \t\tfor (i = 0; i < revs.nr; i++)\n \t\t\tshow_name(revs.objects[i].item, revs.objects[i].name,\n \t\t\t\t always, allow_undefined, data.name_only);\n-- \n2.20.1\n\n"},{"id":"370432","messageId":"CAPig+cQ6-O8hV+7mYFszyFyk0u4aJMe021RqN+tiFn3OS7H0Hw@mail.gmail.com","threadId":"50622","inReplyTo":"20190301175024.17337-2-alban.gruin@gmail.com","subject":"Re: [RFC PATCH 1/4] name-rev: improve name_rev() memory usage","fromName":"Eric Sunshine","fromEmail":"sunshine@sunshineco.com","sentAt":"2019-03-01T18:00:01Z","receivedAt":"2019-03-01T18:00:14Z","isPatch":true,"sender":{"key":"sunshine@sunshineco.com","avatar":"https://avatars.githubusercontent.com/u/163641?v=4"},"body":"On Fri, Mar 1, 2019 at 12:50 PM Alban Gruin wrote:\n> There a condition that will always be false here when name_rev() calls\n> itself for the first parent, but it will become useful when name_rev()\n> will stop to name commits that are not mentionned in the stdin buffer.\n\ns/mentionned/mentioned/\n\n> If the current commit should not be named, its parents may have to be,\n> but they may not. In this case, name_rev() will tell to its caller that\n\ns/tell/report/\n\n> the current commit and its first parent has not used the name, and that\n> it can be released. However, if the current commit has been named but\n> not its parent, or the reverse, the name will not be released.\n>\n> Signed-off-by: Alban Gruin \n"},{"id":"370433","messageId":"CAPig+cQmZOWUZuj2+z+qrrCO-YBMNiEnGic1_FwAcaaj5gA5-w@mail.gmail.com","threadId":"50622","inReplyTo":"20190301175024.17337-4-alban.gruin@gmail.com","subject":"Re: [RFC PATCH 3/4] name-rev: check if a commit should be named before naming it","fromName":"Eric Sunshine","fromEmail":"sunshine@sunshineco.com","sentAt":"2019-03-01T18:05:18Z","receivedAt":"2019-03-01T18:05:31Z","isPatch":true,"sender":{"key":"sunshine@sunshineco.com","avatar":"https://avatars.githubusercontent.com/u/163641?v=4"},"body":"On Fri, Mar 1, 2019 at 12:50 PM Alban Gruin wrote:\n> Until now, name_rev() named every commit it found, even it the name\n\ns/even it/even if/\n\n> would ultimately be unused.\n> [...]\n> Signed-off-by: Alban Gruin \n> ---\n> diff --git a/builtin/name-rev.c b/builtin/name-rev.c\n> @@ -107,12 +107,18 @@ static int name_rev(struct commit *commit,\n> copy_data:\n> - name->tip_name = tip_name;\n> + if (commit_list_contains(commits, commit) ||\n> + commit_list_count(commits) == 0) {\n\nMinor: It would probably be more efficient to check if the count is 0\nfirst, and only search the list if not.\n\nBy the way, how big is 'commits' likely to get? Will the linear scan\ndone by commit_list_contains() become an issue? Should it be using a\nhash table instead?\n\n> + name->tip_name = tip_name;\n> + free_alloc = 0;\n> + } else {\n> + name->tip_name = NULL;\n> + }\n"},{"id":"370434","messageId":"CAPig+cRCSauOKjkEVmyBYdSjXW2215muvC1DqpGAS2hU9x-04w@mail.gmail.com","threadId":"50622","inReplyTo":"20190301175024.17337-5-alban.gruin@gmail.com","subject":"Re: [RFC PATCH 4/4] name-rev: avoid naming from a ref if it’s not a descendant of any commit","fromName":"Eric Sunshine","fromEmail":"sunshine@sunshineco.com","sentAt":"2019-03-01T18:07:01Z","receivedAt":"2019-03-01T18:07:13Z","isPatch":true,"sender":{"key":"sunshine@sunshineco.com","avatar":"https://avatars.githubusercontent.com/u/163641?v=4"},"body":"On Fri, Mar 1, 2019 at 12:50 PM Alban Gruin wrote:\n> A ref may not be the descendant of all of the commits mentionned in\n> stdin. In this case, we want to avoid naming its parents.\n\ns/mentionned/mentioned/\n\n>\n> To do this, find_commits_in_strbuf() is created. It returns a raw list\n> of all the commits that have been found in the input buffer. ishex() is\n> converted to an inlined function. Then, we add a raw list of commits in\n> the name_ref_data structure, and call find_commits_in_strbuf() before\n> for_each_ref() if the user wants name-ref to process stdin. Then, for\n> each ref, we check if the reachable subset of this commit list is empty\n> or not. If it is, we do not call name_rev(), so we don’t name its\n> parents.\n>\n> The code dealing with stdin after calling for_each_ref() is no longer\n> needed as we already read it. name_rev_line() is renamed name_rev_buf()\n> to reflect its new role better.\n>\n> Signed-off-by: Alban Gruin \n"},{"id":"370436","messageId":"992c5d7e-524a-3c92-9f0f-bbefbe151de5@gmail.com","threadId":"50622","inReplyTo":"CAPig+cQmZOWUZuj2+z+qrrCO-YBMNiEnGic1_FwAcaaj5gA5-w@mail.gmail.com","subject":"Re: [RFC PATCH 3/4] name-rev: check if a commit should be named before naming it","fromName":"Alban Gruin","fromEmail":"alban.gruin@gmail.com","sentAt":"2019-03-01T18:22:47Z","receivedAt":"2019-03-01T18:23:04Z","isPatch":true,"sender":{"key":"alban.gruin@gmail.com","avatar":"https://avatars.githubusercontent.com/u/6310153?v=4"},"body":"Hi Eric,\n\nLe 01/03/2019 à 19:05, Eric Sunshine a écrit :\n> On Fri, Mar 1, 2019 at 12:50 PM Alban Gruin wrote:\n> -%<-\n> Minor: It would probably be more efficient to check if the count is 0\n> first, and only search the list if not.\n> \n> By the way, how big is 'commits' likely to get? Will the linear scan\n> done by commit_list_contains() become an issue? Should it be using a\n> hash table instead?\n> \n\nIt depends on the amount of commits mentionned in stdin that are\nreachable from the ref in name_ref(). If there is a lot of commit in\nthe input, it may effectively become a problem.\n\nI thought of adding a field to the rev_name structure for this purpose.\n I think commit slabs are hash maps under the hood?\n\n>> + name->tip_name = tip_name;\n>> + free_alloc = 0;\n>> + } else {\n>> + name->tip_name = NULL;\n>> + }\n\nCheers,\nAlban\n\n"},{"id":"370439","messageId":"20190301183747.GC30847@sigill.intra.peff.net","threadId":"50622","inReplyTo":"992c5d7e-524a-3c92-9f0f-bbefbe151de5@gmail.com","subject":"Re: [RFC PATCH 3/4] name-rev: check if a commit should be named before naming it","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-03-01T18:37:47Z","receivedAt":"2019-03-01T18:37:50Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Mar 01, 2019 at 07:22:47PM +0100, Alban Gruin wrote:\n\n> Le 01/03/2019 à 19:05, Eric Sunshine a écrit :\n> > On Fri, Mar 1, 2019 at 12:50 PM Alban Gruin wrote:\n> > -%<-\n> > Minor: It would probably be more efficient to check if the count is 0\n> > first, and only search the list if not.\n> > \n> > By the way, how big is 'commits' likely to get? Will the linear scan\n> > done by commit_list_contains() become an issue? Should it be using a\n> > hash table instead?\n> > \n> \n> It depends on the amount of commits mentionned in stdin that are\n> reachable from the ref in name_ref(). If there is a lot of commit in\n> the input, it may effectively become a problem.\n\nYeah, I think this is quadratic in the worst case.\n\n> I thought of adding a field to the rev_name structure for this purpose.\n> I think commit slabs are hash maps under the hood?\n\nThey're not hash maps, but they're still O(1). Each commit struct is\nallocated a unique integer id, and the slab just keeps a dynamic array\nof one entry per commit.\n\nSo they're actually faster than a hashmap (it's a pure index, no oideq()\nrequired). The downside is that they can use more memory than a hashmap\nif they're sparsely populated. However in your case, I think you'd load\na couple of \"struct commit\" objects at the start, mark them as \"1\" in\nthe slab, and then never mark any more as you traverse. So you'd only\nallocate entries for those tightly-packed initial ones.\n\nIt seems like an ideal case for using a slab.\n\n-Peff\n"},{"id":"370440","messageId":"20190301184208.GD30847@sigill.intra.peff.net","threadId":"50622","inReplyTo":"20190301175024.17337-1-alban.gruin@gmail.com","subject":"Re: [RFC PATCH 0/4] name-rev: improve memory usage","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-03-01T18:42:08Z","receivedAt":"2019-03-01T18:42:11Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Mar 01, 2019 at 06:50:20PM +0100, Alban Gruin wrote:\n\n> rafasc reported on IRC that on a repository with a lot of branches,\n> tags, remotes, and commits, name-rev --stdin could use a massive amount\n> of memory (more than 2GB of RAM) to complete.\n> \n> This patch series tries to improve name-rev’s memory usage.\n\nHave you tried this?\n\ndiff --git a/builtin/name-rev.c b/builtin/name-rev.c\nindex f1cb45c227..7aaa86f1c0 100644\n--- a/builtin/name-rev.c\n+++ b/builtin/name-rev.c\n@@ -431,6 +431,8 @@ int cmd_name_rev(int argc, const char **argv, const char *prefix)\n \t\tOPT_END(),\n \t};\n \n+\tsave_commit_buffer = 0;\n+\n \tinit_commit_rev_name(&rev_names);\n \tgit_config(git_default_config, NULL);\n \targc = parse_options(argc, argv, prefix, opts, name_rev_usage, 0);\n\nIt seems to lower heap usage of:\n\n git name-rev 1da177e4c3f41524e886b7f1b8a0c1fc7321cac2\n\nin linux.git (that commit is the final one reported by \"git log\", so\nit's traversing all of history) from ~1GB to ~300MB.\n\n-Peff\n"},{"id":"370441","messageId":"20190301184457.GE30847@sigill.intra.peff.net","threadId":"50622","inReplyTo":"20190301175024.17337-2-alban.gruin@gmail.com","subject":"Re: [RFC PATCH 1/4] name-rev: improve name_rev() memory usage","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-03-01T18:44:57Z","receivedAt":"2019-03-01T18:45:00Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Mar 01, 2019 at 06:50:21PM +0100, Alban Gruin wrote:\n\n> name_rev() is a recursive function. For each commit, it allocates the\n> name of its parents, and call itself. A parent may not use a name for\n> multiple reasons, but in any case, the name will not be released. On a\n> repository with a lot of branches, tags, remotes, and commits, it can\n> use more than 2GB of RAM.\n\nI don't know name-rev that well, so I didn't look super carefully at\nyour patch. But if it's recursive in history, that's almost certainly\ngoing to be a problem for some histories on some platforms. We've had to\nde-recursify several other algorithms (e.g., \"tag --contains\") because\nof stack space issues.\n\nWhich isn't to say what you're doing here might not be separately\nuseful, but just know that in the long run that's probably where we'd\nneed to take this.\n\n-Peff\n"},{"id":"370444","messageId":"c496ca1a-d493-64cf-9e9d-d1aa189bd33d@gmail.com","threadId":"50622","inReplyTo":"20190301184208.GD30847@sigill.intra.peff.net","subject":"Re: [RFC PATCH 0/4] name-rev: improve memory usage","fromName":"Alban Gruin","fromEmail":"alban.gruin@gmail.com","sentAt":"2019-03-01T19:14:26Z","receivedAt":"2019-03-01T19:14:36Z","isPatch":true,"sender":{"key":"alban.gruin@gmail.com","avatar":"https://avatars.githubusercontent.com/u/6310153?v=4"},"body":"Hi Jeff,\n\nLe 01/03/2019 à 19:42, Jeff King a écrit :\n> On Fri, Mar 01, 2019 at 06:50:20PM +0100, Alban Gruin wrote:\n> \n>> rafasc reported on IRC that on a repository with a lot of branches,\n>> tags, remotes, and commits, name-rev --stdin could use a massive amount\n>> of memory (more than 2GB of RAM) to complete.\n>>\n>> This patch series tries to improve name-rev’s memory usage.\n> \n> Have you tried this?\n> \n> diff --git a/builtin/name-rev.c b/builtin/name-rev.c\n> index f1cb45c227..7aaa86f1c0 100644\n> --- a/builtin/name-rev.c\n> +++ b/builtin/name-rev.c\n> @@ -431,6 +431,8 @@ int cmd_name_rev(int argc, const char **argv, const char *prefix)\n> \t\tOPT_END(),\n> \t};\n> \n> +\tsave_commit_buffer = 0;\n> +\n> \tinit_commit_rev_name(&rev_names);\n> \tgit_config(git_default_config, NULL);\n> \targc = parse_options(argc, argv, prefix, opts, name_rev_usage, 0);\n> \n> It seems to lower heap usage of:\n> \n> git name-rev 1da177e4c3f41524e886b7f1b8a0c1fc7321cac2\n> \n> in linux.git (that commit is the final one reported by \"git log\", so\n> it's traversing all of history) from ~1GB to ~300MB.\n> \n> -Peff\n> \n\nUnfortunately this does not work in all cases, apparently. On my git\ncopy, I have 3 origins. If I run this:\n\n\tgit log --graph --oneline --abbrev=-1 -5 | git name-rev --stdin\n\nWith or without your change, it uses 3GB of RAM. With this series, it\nuses 25MB of RAM.\n\nWith the first git commit:\n\n\tgit name-rev e83c5163316f89bfbde7d9ab23ca2e25604af290\n\nIt also uses 3GB of RAM. With this series, it uses around 350MB of RAM.\n Which makes me think that I should adapt 4/4 to arguments.\n\nSorry, I should have specified this in the cover letter.\n\nCheers,\nAlban\n\n"},{"id":"370445","messageId":"20190301193912.GA28195@sigill.intra.peff.net","threadId":"50622","inReplyTo":"c496ca1a-d493-64cf-9e9d-d1aa189bd33d@gmail.com","subject":"Re: [RFC PATCH 0/4] name-rev: improve memory usage","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-03-01T19:39:12Z","receivedAt":"2019-03-01T19:39:16Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Mar 01, 2019 at 08:14:26PM +0100, Alban Gruin wrote:\n\n> > diff --git a/builtin/name-rev.c b/builtin/name-rev.c\n> > index f1cb45c227..7aaa86f1c0 100644\n> > --- a/builtin/name-rev.c\n> > +++ b/builtin/name-rev.c\n> > @@ -431,6 +431,8 @@ int cmd_name_rev(int argc, const char **argv, const char *prefix)\n> > \t\tOPT_END(),\n> > \t};\n> > \n> > +\tsave_commit_buffer = 0;\n> > +\n> [...]\n> \n> Unfortunately this does not work in all cases, apparently. On my git\n> copy, I have 3 origins. If I run this:\n> \n> \tgit log --graph --oneline --abbrev=-1 -5 | git name-rev --stdin\n> \n> With or without your change, it uses 3GB of RAM. With this series, it\n> uses 25MB of RAM.\n\nSorry if I was unclear. I meant to try that _in addition_ to your\nchanges. It helps by avoiding keeping the useless commit-object buffers\nin RAM as we traverse. But the most it can save is the total\nuncompressed bytes of all commit objects. I.e., in git.git:\n\n $ git cat-file --batch-check='%(objectsize) %(objecttype)' --batch-all-objects |\n grep commit |\n perl -alne '$total += $F[0]; END { print $total }'\n 74678114\n\nor around 70MB. In linux.git, it's more like 700MB.\n\nBut in your examples, the problem is the inefficiencies in name-rev's\nalgorithm, and you're not actually traversing that many commits. So I\nthink you'd want to turn off save_commit_buffer as an extra patch in\nyour series. It may or not be a big win for any given case, but it's\nquite easy to do.\n\n-Peff\n"},{"id":"370478","messageId":"nycvar.QRO.7.76.6.1903022224480.45@tvgsbejvaqbjf.bet","threadId":"50622","inReplyTo":"20190301175024.17337-2-alban.gruin@gmail.com","subject":"Re: [RFC PATCH 1/4] name-rev: improve name_rev() memory usage","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2019-03-02T21:28:23Z","receivedAt":"2019-03-02T21:28:23Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Alban,\n\nOn Fri, 1 Mar 2019, Alban Gruin wrote:\n\n> name_rev() is a recursive function. For each commit, it allocates the\n> name of its parents, and call itself. A parent may not use a name for\n> multiple reasons, but in any case, the name will not be released. On a\n> repository with a lot of branches, tags, remotes, and commits, it can\n> use more than 2GB of RAM.\n> \n> To improve the situation, name_rev() now returns a boolean to its caller\n> indicating if it can release the name. The caller may free the name if\n> the commit is too old, or if the new name is not better than the current\n> name.\n> \n> There a condition that will always be false here when name_rev() calls\n> itself for the first parent, but it will become useful when name_rev()\n> will stop to name commits that are not mentionned in the stdin buffer.\n> If the current commit should not be named, its parents may have to be,\n> but they may not. In this case, name_rev() will tell to its caller that\n> the current commit and its first parent has not used the name, and that\n> it can be released. However, if the current commit has been named but\n> not its parent, or the reverse, the name will not be released.\n\nMakes sense, and the patch looks mostly good to me, just one suggestion:\n\n> Signed-off-by: Alban Gruin \n> ---\n> builtin/name-rev.c | 23 ++++++++++++++---------\n> 1 file changed, 14 insertions(+), 9 deletions(-)\n> \n> diff --git a/builtin/name-rev.c b/builtin/name-rev.c\n> index f1cb45c227..0719a9388d 100644\n> --- a/builtin/name-rev.c\n> +++ b/builtin/name-rev.c\n> @@ -77,7 +77,7 @@ static int is_better_name(struct rev_name *name,\n> \treturn 0;\n> }\n> \n> -static void name_rev(struct commit *commit,\n> +static int name_rev(struct commit *commit,\n> \t\tconst char *tip_name, timestamp_t taggerdate,\n> \t\tint generation, int distance, int from_tag,\n> \t\tint deref)\n> @@ -86,11 +86,12 @@ static void name_rev(struct commit *commit,\n> \tstruct commit_list *parents;\n> \tint parent_number = 1;\n> \tchar *to_free = NULL;\n> +\tint free_alloc = 1;\n> \n> \tparse_commit(commit);\n> \n> \tif (commit->date < cutoff)\n> -\t\treturn;\n> +\t\treturn 1;\n> \n> \tif (deref) {\n> \t\ttip_name = to_free = xstrfmt(\"%s^0\", tip_name);\n> @@ -111,9 +112,10 @@ static void name_rev(struct commit *commit,\n> \t\tname->generation = generation;\n> \t\tname->distance = distance;\n> \t\tname->from_tag = from_tag;\n> +\t\tfree_alloc = 0;\n> \t} else {\n> \t\tfree(to_free);\n> -\t\treturn;\n> +\t\treturn 1;\n> \t}\n> \n> \tfor (parents = commit->parents;\n> @@ -131,15 +133,18 @@ static void name_rev(struct commit *commit,\n> \t\t\t\tnew_name = xstrfmt(\"%.*s^%d\", (int)len, tip_name,\n> \t\t\t\t\t\t parent_number);\n> \n> -\t\t\tname_rev(parents->item, new_name, taggerdate, 0,\n> -\t\t\t\t distance + MERGE_TRAVERSAL_WEIGHT,\n> -\t\t\t\t from_tag, 0);\n> +\t\t\tif (name_rev(parents->item, new_name, taggerdate, 0,\n> +\t\t\t\t distance + MERGE_TRAVERSAL_WEIGHT,\n> +\t\t\t\t from_tag, 0))\n> +\t\t\t\tfree(new_name);\n> \t\t} else {\n> -\t\t\tname_rev(parents->item, tip_name, taggerdate,\n> -\t\t\t\t generation + 1, distance + 1,\n> -\t\t\t\t from_tag, 0);\n> +\t\t\tfree_alloc &= name_rev(parents->item, tip_name, taggerdate,\n> +\t\t\t\t\t generation + 1, distance + 1,\n> +\t\t\t\t\t from_tag, 0);\n\nThis would be easier to read if it avoided the &=, e.g. by turning it\ninto:\n\n\t\t} else if (!name_rev(parents->item, tip_name, taggerdate,\n\t\t\t\t generation + 1, distance + 1,\n\t\t\t\t from_tag, 0))\n\t\t\tfree_alloc = 0;\n\nCiao,\nDscho\n\n> \t\t}\n> \t}\n> +\n> +\treturn free_alloc;\n> }\n> \n> static int subpath_matches(const char *path, const char *filter)\n> -- \n> 2.20.1\n> \n> \n"},{"id":"370556","messageId":"CAP8UFD1HBbOX7wS664vBT8mxjGUJ4rtWYYJJX9RQqhN20-T8uA@mail.gmail.com","threadId":"50622","inReplyTo":"20190301175024.17337-5-alban.gruin@gmail.com","subject":"Re: [RFC PATCH 4/4] name-rev: avoid naming from a ref if it’s not a descendant of any commit","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2019-03-03T19:33:30Z","receivedAt":"2019-03-03T19:33:45Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"On Fri, Mar 1, 2019 at 7:11 PM Alban Gruin wrote:\n>\n> A ref may not be the descendant of all of the commits mentionned in\n> stdin. In this case, we want to avoid naming its parents.\n\nProperly speaking a ref usually just points to a commit. It is not a\nparent or a descendant of any commit.\n\nAlso if the commit, let's call it C, pointed to by a ref isn't a\ndescendant of a commit, let's call it C', mentioned on stdin, then C'\nisn't a parent of C, though I think we want to avoid naming C' from\nthe ref.\n\nI think it might be clearer with something like:\n\n\"The commit, let's call it C, pointed to by a ref may not be a\ndescendant of all the commits mentioned on stdin. In this case we want\nto avoid naming the commits mentioned on stdin that are not parents of\nC using the ref.\"\n\nOr is there something I misunderstood?\n"},{"id":"370557","messageId":"CAP8UFD0bH--hLSXuc7Z9RN5oLNPWjVdCFS4+zeLo9qXTo93pxA@mail.gmail.com","threadId":"50622","inReplyTo":"CAP8UFD1HBbOX7wS664vBT8mxjGUJ4rtWYYJJX9RQqhN20-T8uA@mail.gmail.com","subject":"Re: [RFC PATCH 4/4] name-rev: avoid naming from a ref if it’s not a descendant of any commit","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2019-03-03T19:46:30Z","receivedAt":"2019-03-03T19:46:44Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"On Sun, Mar 3, 2019 at 8:33 PM Christian Couder\n wrote:\n>\n> On Fri, Mar 1, 2019 at 7:11 PM Alban Gruin wrote:\n> >\n> > A ref may not be the descendant of all of the commits mentionned in\n> > stdin. In this case, we want to avoid naming its parents.\n>\n> Properly speaking a ref usually just points to a commit. It is not a\n> parent or a descendant of any commit.\n>\n> Also if the commit, let's call it C, pointed to by a ref isn't a\n> descendant of a commit, let's call it C', mentioned on stdin, then C'\n> isn't a parent of C, though I think we want to avoid naming C' from\n> the ref.\n>\n> I think it might be clearer with something like:\n>\n> \"The commit, let's call it C, pointed to by a ref may not be a\n> descendant of all the commits mentioned on stdin. In this case we want\n> to avoid naming the commits mentioned on stdin that are not parents of\n> C using the ref.\"\n\nBy the way things might even be clearer by replacing \"parent\" with\n\"ancestor\" in my message.\n"},{"id":"370559","messageId":"10fa15ee-a6f4-805b-bae3-14ea8c50c048@gmail.com","threadId":"50622","inReplyTo":"CAP8UFD1HBbOX7wS664vBT8mxjGUJ4rtWYYJJX9RQqhN20-T8uA@mail.gmail.com","subject":"Re: [RFC PATCH 4/4] name-rev: avoid naming from a ref if it’s not a descendant of any commit","fromName":"Alban Gruin","fromEmail":"alban.gruin@gmail.com","sentAt":"2019-03-03T20:27:59Z","receivedAt":"2019-03-03T20:28:13Z","isPatch":true,"sender":{"key":"alban.gruin@gmail.com","avatar":"https://avatars.githubusercontent.com/u/6310153?v=4"},"body":"Hi Christian,\n\nLe 03/03/2019 à 20:33, Christian Couder a écrit :\n> On Fri, Mar 1, 2019 at 7:11 PM Alban Gruin wrote:\n>>\n>> A ref may not be the descendant of all of the commits mentionned in\n>> stdin. In this case, we want to avoid naming its parents.\n> \n> Properly speaking a ref usually just points to a commit. It is not a\n> parent or a descendant of any commit.\n> \n> Also if the commit, let's call it C, pointed to by a ref isn't a\n> descendant of a commit, let's call it C', mentioned on stdin, then C'\n> isn't a parent of C, though I think we want to avoid naming C' from\n> the ref.\n> \n> I think it might be clearer with something like:\n> \n> \"The commit, let's call it C, pointed to by a ref may not be a\n> descendant of all the commits mentioned on stdin. In this case we want\n> to avoid naming the commits mentioned on stdin that are not parents of\n> C using the ref.\"\n> \n> Or is there something I misunderstood?\n> \n\nIt’s almost this. We do want to name *all* of the commits mentionned in\nstdin, as far as possible. We also want to lower the amount of memory\nallocation, and one of the possibilities is to avoid traversing the tree\nfrom a commit pointed to by a ref if none of its parents are mentionned\nin stdin.\n\nCheers,\nAlban\n\n"}]}