{"thread":{"id":"54903","subject":"[PATCH] revision: trace topo-walk statistics","startedAt":"2020-12-30T04:32:53Z","lastAt":"2021-01-07T11:10:12Z","messageCount":5,"participants":["Derrick Stolee via GitGitGadget","Junio C Hamano","Derrick Stolee"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"413162","messageId":"pull.828.git.1609302714183.gitgitgadget@gmail.com","threadId":"54903","inReplyTo":null,"subject":"[PATCH] revision: trace topo-walk statistics","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-12-30T04:31:53Z","receivedAt":"2020-12-30T04:32:53Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee <dstolee@microsoft.com>\n\nWe trace statistics about the effectiveness of changed-path Bloom\nfilters since 42e50e78 (revision.c: add trace2 stats around Bloom\nfilter usage, 2020-04-06). Add similar tracing for the topo-walk\nalgorithm that uses generation numbers to limit the walk size.\n\nThis information can help investigate and describe benefits to\nheuristics and other changes.\n\nThe information that is printed is in JSON format and can be formatted\nnicely to present as follows:\n\n    {\n\t\"count_explort_walked\":2603,\n\t\"count_indegree_walked\":2603,\n\t\"count_topo_walked\":473\n    }\n\nEach of these values count the number of commits are visited by each of\nthe three \"stages\" of the topo-walk as detailed in b4542418 (revision.c:\ngeneration-based topo-order algorithm, 2018-11-01).\n\nSigned-off-by: Derrick Stolee <dstolee@microsoft.com>\n---\n    revision: trace topo-walk statistics\n    \n    Here is a patch I thought useful when investigating the performance\n    implications of Abhishek's series [1]\n    \n    [1]\n    https://lore.kernel.org/git/pull.676.v5.git.1609154168.gitgitgadget@gmail.com/\n\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-828%2Fderrickstolee%2Ftrace2-topo-walk-v1\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-828/derrickstolee/trace2-topo-walk-v1\nPull-Request: https://github.com/gitgitgadget/git/pull/828\n\n revision.c | 31 +++++++++++++++++++++++++++++++\n 1 file changed, 31 insertions(+)\n\ndiff --git a/revision.c b/revision.c\nindex 9dff845bed6..1bb590ece78 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -3308,6 +3308,26 @@ struct topo_walk_info {\n \tstruct author_date_slab author_date;\n };\n \n+static int topo_walk_atexit_registered;\n+static unsigned int count_explore_walked;\n+static unsigned int count_indegree_walked;\n+static unsigned int count_topo_walked;\n+\n+static void trace2_topo_walk_statistics_atexit(void)\n+{\n+\tstruct json_writer jw = JSON_WRITER_INIT;\n+\n+\tjw_object_begin(&jw, 0);\n+\tjw_object_intmax(&jw, \"count_explore_walked\", count_explore_walked);\n+\tjw_object_intmax(&jw, \"count_indegree_walked\", count_indegree_walked);\n+\tjw_object_intmax(&jw, \"count_topo_walked\", count_topo_walked);\n+\tjw_end(&jw);\n+\n+\ttrace2_data_json(\"topo_walk\", the_repository, \"statistics\", &jw);\n+\n+\tjw_release(&jw);\n+}\n+\n static inline void test_flag_and_insert(struct prio_queue *q, struct commit *c, int flag)\n {\n \tif (c->object.flags & flag)\n@@ -3329,6 +3349,8 @@ static void explore_walk_step(struct rev_info *revs)\n \tif (repo_parse_commit_gently(revs->repo, c, 1) < 0)\n \t\treturn;\n \n+\tcount_explore_walked++;\n+\n \tif (revs->sort_order == REV_SORT_BY_AUTHOR_DATE)\n \t\trecord_author_date(&info->author_date, c);\n \n@@ -3367,6 +3389,8 @@ static void indegree_walk_step(struct rev_info *revs)\n \tif (repo_parse_commit_gently(revs->repo, c, 1) < 0)\n \t\treturn;\n \n+\tcount_indegree_walked++;\n+\n \texplore_to_depth(revs, commit_graph_generation(c));\n \n \tfor (p = c->parents; p; p = p->next) {\n@@ -3476,6 +3500,11 @@ static void init_topo_walk(struct rev_info *revs)\n \t */\n \tif (revs->sort_order == REV_SORT_IN_GRAPH_ORDER)\n \t\tprio_queue_reverse(&info->topo_queue);\n+\n+\tif (trace2_is_enabled() && !topo_walk_atexit_registered) {\n+\t\tatexit(trace2_topo_walk_statistics_atexit);\n+\t\ttopo_walk_atexit_registered = 1;\n+\t}\n }\n \n static struct commit *next_topo_commit(struct rev_info *revs)\n@@ -3502,6 +3531,8 @@ static void expand_topo_walk(struct rev_info *revs, struct commit *commit)\n \t\t\t    oid_to_hex(&commit->object.oid));\n \t}\n \n+\tcount_topo_walked++;\n+\n \tfor (p = commit->parents; p; p = p->next) {\n \t\tstruct commit *parent = p->item;\n \t\tint *pi;\n\nbase-commit: 71ca53e8125e36efbda17293c50027d31681a41f\n-- \ngitgitgadget\n"},{"id":"413631","messageId":"xmqqh7nto7ck.fsf@gitster.c.googlers.com","threadId":"54903","inReplyTo":"pull.828.git.1609302714183.gitgitgadget@gmail.com","subject":"Re: [PATCH] revision: trace topo-walk statistics","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2021-01-07T01:37:15Z","receivedAt":"2021-01-07T01:38:00Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Derrick Stolee via GitGitGadget\" <gitgitgadget@gmail.com> writes:\n\n> diff --git a/revision.c b/revision.c\n> index 9dff845bed6..1bb590ece78 100644\n> --- a/revision.c\n> +++ b/revision.c\n> @@ -3308,6 +3308,26 @@ struct topo_walk_info {\n>  \tstruct author_date_slab author_date;\n>  };\n>  \n> +static int topo_walk_atexit_registered;\n> +static unsigned int count_explore_walked;\n> +static unsigned int count_indegree_walked;\n> +static unsigned int count_topo_walked;\n\nThe revision walk machinery is designed to be callable more than\nonce during the lifetime of a process.  These make readers wonder\nif they should be defined in \"struct rev_info\" to allow stats\ncollected per traversal.\n\n"},{"id":"413634","messageId":"cbc17f1b-57fc-497f-f1ab-baa8cc84620d@gmail.com","threadId":"54903","inReplyTo":"xmqqh7nto7ck.fsf@gitster.c.googlers.com","subject":"Re: [PATCH] revision: trace topo-walk statistics","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2021-01-07T02:04:21Z","receivedAt":"2021-01-07T02:05:02Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 1/6/2021 8:37 PM, Junio C Hamano wrote:\n> \"Derrick Stolee via GitGitGadget\" <gitgitgadget@gmail.com> writes:\n> \n>> diff --git a/revision.c b/revision.c\n>> index 9dff845bed6..1bb590ece78 100644\n>> --- a/revision.c\n>> +++ b/revision.c\n>> @@ -3308,6 +3308,26 @@ struct topo_walk_info {\n>>  \tstruct author_date_slab author_date;\n>>  };\n>>  \n>> +static int topo_walk_atexit_registered;\n>> +static unsigned int count_explore_walked;\n>> +static unsigned int count_indegree_walked;\n>> +static unsigned int count_topo_walked;\n> \n> The revision walk machinery is designed to be callable more than\n> once during the lifetime of a process.  These make readers wonder\n> if they should be defined in \"struct rev_info\" to allow stats\n> collected per traversal.\n\nThat's possible, but the use of an at-exit method means we only\nreport one set of statistics and the 'struct rev_info' might\nbe defunct.\n\nIt does limit how useful the statistics can be when there are\nmultiple 'struct rev_info's in use, but we also cannot trust\nthat the rev_infos are being cleaned up properly at the end\nof the process to trigger the stats logging.\n\nOf course, maybe that _is_ something we could guarantee, or\nrather _should_ guarantee by patching any leaks. Seems like\na lot of work when these aggregate statistics will be\neffective enough. But maybe I'm judging the potential work\ntoo harshly?\n\nThanks,\n-Stolee\n"},{"id":"413637","messageId":"xmqq7dopo4xb.fsf@gitster.c.googlers.com","threadId":"54903","inReplyTo":"cbc17f1b-57fc-497f-f1ab-baa8cc84620d@gmail.com","subject":"Re: [PATCH] revision: trace topo-walk statistics","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2021-01-07T02:29:36Z","receivedAt":"2021-01-07T02:30:38Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Derrick Stolee <stolee@gmail.com> writes:\n\n> On 1/6/2021 8:37 PM, Junio C Hamano wrote:\n>> \"Derrick Stolee via GitGitGadget\" <gitgitgadget@gmail.com> writes:\n>> \n>>> diff --git a/revision.c b/revision.c\n>>> index 9dff845bed6..1bb590ece78 100644\n>>> --- a/revision.c\n>>> +++ b/revision.c\n>>> @@ -3308,6 +3308,26 @@ struct topo_walk_info {\n>>>  \tstruct author_date_slab author_date;\n>>>  };\n>>>  \n>>> +static int topo_walk_atexit_registered;\n>>> +static unsigned int count_explore_walked;\n>>> +static unsigned int count_indegree_walked;\n>>> +static unsigned int count_topo_walked;\n>> \n>> The revision walk machinery is designed to be callable more than\n>> once during the lifetime of a process.  These make readers wonder\n>> if they should be defined in \"struct rev_info\" to allow stats\n>> collected per traversal.\n>\n> That's possible, but the use of an at-exit method means we only\n> report one set of statistics and the 'struct rev_info' might\n> be defunct.\n\nAh, sorry for the noise.  Even after making multiple traversal we\nwant to report the aggregate.\n\n> It does limit how useful the statistics can be when there are\n> multiple 'struct rev_info's in use, but we also cannot trust\n> that the rev_infos are being cleaned up properly at the end\n> of the process to trigger the stats logging.\n>\n> Of course, maybe that _is_ something we could guarantee, or\n> rather _should_ guarantee by patching any leaks. Seems like\n> a lot of work when these aggregate statistics will be\n> effective enough. But maybe I'm judging the potential work\n> too harshly?\n\nBut different subsystems would have different \"per-invocation\"\nstructure (e.g. \"diff\" uses \"struct diff_options\") and some may not\neven have an appropriate structure to hang these stats on.  We may\nwant to design a more general mechanism that can be used to annotate\nthe subsystems uniformly.  While that could be a worthy longer term\ngoal, it certainly does not have to be part of this single-patch\ntopic, I would think.\n"},{"id":"413680","messageId":"ed723456-fb5d-74f4-26f0-0b37071ff212@gmail.com","threadId":"54903","inReplyTo":"xmqq7dopo4xb.fsf@gitster.c.googlers.com","subject":"Re: [PATCH] revision: trace topo-walk statistics","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2021-01-07T11:08:28Z","receivedAt":"2021-01-07T11:10:12Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 1/6/2021 9:29 PM, Junio C Hamano wrote:\n> But different subsystems would have different \"per-invocation\"\n> structure (e.g. \"diff\" uses \"struct diff_options\") and some may not\n> even have an appropriate structure to hang these stats on.  We may\n> want to design a more general mechanism that can be used to annotate\n> the subsystems uniformly.  While that could be a worthy longer term\n> goal, it certainly does not have to be part of this single-patch\n> topic, I would think.\n \nI will give this further thought.\n\nThanks,\n-Stolee\n"}]}