{"thread":{"id":"62926","subject":"[PATCH] commit: avoid parent list buildup in clear_commit_marks_many()","startedAt":"2025-02-09T10:41:23Z","lastAt":"2025-02-23T08:26:12Z","messageCount":6,"participants":["René Scharfe","Patrick Steinhardt"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"512159","messageId":"16a7b572-0a3d-4707-9034-0dac69ea99ac@web.de","threadId":"62926","inReplyTo":null,"subject":"[PATCH] commit: avoid parent list buildup in clear_commit_marks_many()","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2025-02-09T10:41:15Z","receivedAt":"2025-02-09T10:41:23Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"clear_commit_marks_1() clears the marks of the first parent and its\nfirst parent and so on, and saves the higher numbered parents in a list\nfor later.  There is no benefit in keeping that list growing with each\nhandled commit.  Clear it after each run to reduce peak memory usage.\n\nSigned-off-by: René Scharfe <l.s.r@web.de>\n---\n commit.c | 8 ++++----\n 1 file changed, 4 insertions(+), 4 deletions(-)\n\ndiff --git a/commit.c b/commit.c\nindex 540660359d..6efdb03997 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -780,14 +780,14 @@ static void clear_commit_marks_1(struct commit_list **plist,\n\n void clear_commit_marks_many(size_t nr, struct commit **commit, unsigned int mark)\n {\n-\tstruct commit_list *list = NULL;\n-\n \tfor (size_t i = 0; i < nr; i++) {\n+\t\tstruct commit_list *list = NULL;\n+\n \t\tclear_commit_marks_1(&list, *commit, mark);\n+\t\twhile (list)\n+\t\t\tclear_commit_marks_1(&list, pop_commit(&list), mark);\n \t\tcommit++;\n \t}\n-\twhile (list)\n-\t\tclear_commit_marks_1(&list, pop_commit(&list), mark);\n }\n\n void clear_commit_marks(struct commit *commit, unsigned int mark)\n--\n2.48.1\n"},{"id":"512295","messageId":"Z6xIPowXnL-awm6g@pks.im","threadId":"62926","inReplyTo":"16a7b572-0a3d-4707-9034-0dac69ea99ac@web.de","subject":"Re: [PATCH] commit: avoid parent list buildup in clear_commit_marks_many()","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2025-02-12T07:05:34Z","receivedAt":"2025-02-12T07:05:44Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Sun, Feb 09, 2025 at 11:41:15AM +0100, René Scharfe wrote:\n> clear_commit_marks_1() clears the marks of the first parent and its\n> first parent and so on, and saves the higher numbered parents in a list\n> for later.  There is no benefit in keeping that list growing with each\n> handled commit.  Clear it after each run to reduce peak memory usage.\n\nOkay. So the issue here is that `clear_commit_marks_1()` only processes\nthe first-parent chain of commits, and any other commits will be added\nto the `struct commit_list` backlog. Consequently, merge-heavy histories\nare very likely to build up quite a backlog of non-first-parent commits.\n\n> Signed-off-by: René Scharfe <l.s.r@web.de>\n> ---\n>  commit.c | 8 ++++----\n>  1 file changed, 4 insertions(+), 4 deletions(-)\n> \n> diff --git a/commit.c b/commit.c\n> index 540660359d..6efdb03997 100644\n> --- a/commit.c\n> +++ b/commit.c\n> @@ -780,14 +780,14 @@ static void clear_commit_marks_1(struct commit_list **plist,\n> \n>  void clear_commit_marks_many(size_t nr, struct commit **commit, unsigned int mark)\n>  {\n> -\tstruct commit_list *list = NULL;\n> -\n>  \tfor (size_t i = 0; i < nr; i++) {\n> +\t\tstruct commit_list *list = NULL;\n> +\n>  \t\tclear_commit_marks_1(&list, *commit, mark);\n> +\t\twhile (list)\n> +\t\t\tclear_commit_marks_1(&list, pop_commit(&list), mark);\n>  \t\tcommit++;\n>  \t}\n> -\twhile (list)\n> -\t\tclear_commit_marks_1(&list, pop_commit(&list), mark);\n>  }\n\nAnd this is fixed by immediately processing all commits that we\ncurrently have in the list. As `clear_commit_marks_1()` only processes\nimmediate children of the handed-in commit we know that it will have\nprocessed the first parent, and `list` will contain remaining commits,\nif any.\n\nWe also end up adding grandchildren to the list, so this change\nessentially converts the algorithm from depth-first to breadth-first. I\nbet we can construct cases where this will perform _worse_ than the\ncurrent algorithm, e.g. when you have branch thickets where every commit\nis a merge: But I assume that for the most common cases this might be an\nimprovement indeed.\n\nThe question to me is: does this actually matter in the real world? It\nwould be nice to maybe get some numbers that demonstrate the improvement\nin a repository.\n\nPatrick\n"},{"id":"512386","messageId":"69909785-7f7a-4164-bdcb-bed61d006cc8@web.de","threadId":"62926","inReplyTo":"Z6xIPowXnL-awm6g@pks.im","subject":"Re: [PATCH] commit: avoid parent list buildup in clear_commit_marks_many()","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2025-02-13T21:38:51Z","receivedAt":"2025-02-13T21:38:59Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 12.02.25 um 08:05 schrieb Patrick Steinhardt:\n> On Sun, Feb 09, 2025 at 11:41:15AM +0100, René Scharfe wrote:\n>> clear_commit_marks_1() clears the marks of the first parent and its\n>> first parent and so on, and saves the higher numbered parents in a list\n>> for later.  There is no benefit in keeping that list growing with each\n>> handled commit.  Clear it after each run to reduce peak memory usage.\n>\n> Okay. So the issue here is that `clear_commit_marks_1()` only processes\n> the first-parent chain of commits, and any other commits will be added\n> to the `struct commit_list` backlog. Consequently, merge-heavy histories\n> are very likely to build up quite a backlog of non-first-parent commits.\n>\n>> Signed-off-by: René Scharfe <l.s.r@web.de>\n>> ---\n>>  commit.c | 8 ++++----\n>>  1 file changed, 4 insertions(+), 4 deletions(-)\n>>\n>> diff --git a/commit.c b/commit.c\n>> index 540660359d..6efdb03997 100644\n>> --- a/commit.c\n>> +++ b/commit.c\n>> @@ -780,14 +780,14 @@ static void clear_commit_marks_1(struct commit_list **plist,\n>>\n>>  void clear_commit_marks_many(size_t nr, struct commit **commit, unsigned int mark)\n>>  {\n>> -\tstruct commit_list *list = NULL;\n>> -\n>>  \tfor (size_t i = 0; i < nr; i++) {\n>> +\t\tstruct commit_list *list = NULL;\n>> +\n>>  \t\tclear_commit_marks_1(&list, *commit, mark);\n>> +\t\twhile (list)\n>> +\t\t\tclear_commit_marks_1(&list, pop_commit(&list), mark);\n>>  \t\tcommit++;\n>>  \t}\n>> -\twhile (list)\n>> -\t\tclear_commit_marks_1(&list, pop_commit(&list), mark);\n>>  }\n>\n> And this is fixed by immediately processing all commits that we\n> currently have in the list. As `clear_commit_marks_1()` only processes\n> immediate children of the handed-in commit we know that it will have\n> processed the first parent, and `list` will contain remaining commits,\n> if any.\n\nclear_commit_marks_1() processes the whole ancestral chain of first\nparents down to the root or first clean ancestor.\n\n> We also end up adding grandchildren to the list, so this change\n> essentially converts the algorithm from depth-first to breadth-first.\n\nIt's still depth-first, but all second and higher numbered parents added\nto the list are cleaned before starting to clean the next commit from\nthe input list.  So we go from \"clean straight down for each input\ncommit first and clean their side branches later\" to \"clean all\nancestors for each input commit\".\n\n> I bet we can construct cases where this will perform _worse_ than the\n> current algorithm, e.g. when you have branch thickets where every commit\n> is a merge: But I assume that for the most common cases this might be an\n> improvement indeed.\n\nI won't bet, but I'd like to see such a case.  Can't imagine one.\n\n> The question to me is: does this actually matter in the real world? It\n> would be nice to maybe get some numbers that demonstrate the improvement\n> in a repository.\n\nWell, the maximum list length for clear_commit_marks_many() calls with\nnr > 1 in the test suite goes from 12 in t6600 to 4 with the patch.  Not\nthat exciting.  The question to me is: Why pile up parents in the list\nwhen we can clean them earlier with no downside?  Or is there any?\n\nRené\n"},{"id":"512498","messageId":"Z7LYI4tqGZzZ2Vaw@pks.im","threadId":"62926","inReplyTo":"69909785-7f7a-4164-bdcb-bed61d006cc8@web.de","subject":"Re: [PATCH] commit: avoid parent list buildup in clear_commit_marks_many()","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2025-02-17T06:33:07Z","receivedAt":"2025-02-17T06:33:13Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Thu, Feb 13, 2025 at 10:38:51PM +0100, René Scharfe wrote:\n> Am 12.02.25 um 08:05 schrieb Patrick Steinhardt:\n> > And this is fixed by immediately processing all commits that we\n> > currently have in the list. As `clear_commit_marks_1()` only processes\n> > immediate children of the handed-in commit we know that it will have\n> > processed the first parent, and `list` will contain remaining commits,\n> > if any.\n> \n> clear_commit_marks_1() processes the whole ancestral chain of first\n> parents down to the root or first clean ancestor.\n> \n> > We also end up adding grandchildren to the list, so this change\n> > essentially converts the algorithm from depth-first to breadth-first.\n> \n> It's still depth-first, but all second and higher numbered parents added\n> to the list are cleaned before starting to clean the next commit from\n> the input list.  So we go from \"clean straight down for each input\n> commit first and clean their side branches later\" to \"clean all\n> ancestors for each input commit\".\n\nAh, fair.\n\n> > I bet we can construct cases where this will perform _worse_ than the\n> > current algorithm, e.g. when you have branch thickets where every commit\n> > is a merge: But I assume that for the most common cases this might be an\n> > improvement indeed.\n> \n> I won't bet, but I'd like to see such a case.  Can't imagine one.\n> \n> > The question to me is: does this actually matter in the real world? It\n> > would be nice to maybe get some numbers that demonstrate the improvement\n> > in a repository.\n> \n> Well, the maximum list length for clear_commit_marks_many() calls with\n> nr > 1 in the test suite goes from 12 in t6600 to 4 with the patch.  Not\n> that exciting.  The question to me is: Why pile up parents in the list\n> when we can clean them earlier with no downside?  Or is there any?\n\nIf it really is without downsides then yes, it's a nice improvement. I\nwas mostly wondering whether you're fixing something where the old way\nof doing things performs _significantly_ worse and where the change\ncould lead to a user-visible improvement. Like, requiring us to store\norders of magnitudes less commits at the same time.\n\nPatrick\n"},{"id":"512880","messageId":"a5be80b2-bcc0-400d-8f83-f537a71d83a4@web.de","threadId":"62926","inReplyTo":"Z7LYI4tqGZzZ2Vaw@pks.im","subject":"Re: [PATCH] commit: avoid parent list buildup in clear_commit_marks_many()","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2025-02-23T08:25:54Z","receivedAt":"2025-02-23T08:25:56Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 17.02.25 um 07:33 schrieb Patrick Steinhardt:\n> On Thu, Feb 13, 2025 at 10:38:51PM +0100, René Scharfe wrote:\n>> Am 12.02.25 um 08:05 schrieb Patrick Steinhardt:\n>>\n>> Well, the maximum list length for clear_commit_marks_many() calls with\n>> nr > 1 in the test suite goes from 12 in t6600 to 4 with the patch.  Not\n>> that exciting.  The question to me is: Why pile up parents in the list\n>> when we can clean them earlier with no downside?  Or is there any?\n>\n> If it really is without downsides then yes, it's a nice improvement. I\n> was mostly wondering whether you're fixing something where the old way\n> of doing things performs _significantly_ worse and where the change\n> could lead to a user-visible improvement. Like, requiring us to store\n> orders of magnitudes less commits at the same time.\n\nYou could construct pathological cases, e.g., cleaning lots of disjoint\nhistories, but I don't expect any dramatic impact to real usage of the\nfunction.  It's just a small improvement.\n\nRené\n\n"},{"id":"512881","messageId":"2bd2d71f-0ee6-405f-bec8-368406ca53c8@web.de","threadId":"62926","inReplyTo":"16a7b572-0a3d-4707-9034-0dac69ea99ac@web.de","subject":"[PATCH resend] commit: avoid parent list buildup in clear_commit_marks_many()","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2025-02-23T08:26:04Z","receivedAt":"2025-02-23T08:26:12Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"clear_commit_marks_1() clears the marks of the first parent and its\nfirst parent and so on, and saves the higher numbered parents in a list\nfor later.  There is no benefit in keeping that list growing with each\nhandled commit.  Clear it after each run to reduce peak memory usage.\n\nSigned-off-by: René Scharfe <l.s.r@web.de>\n---\n commit.c | 8 ++++----\n 1 file changed, 4 insertions(+), 4 deletions(-)\n\ndiff --git a/commit.c b/commit.c\nindex 540660359d..6efdb03997 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -780,14 +780,14 @@ static void clear_commit_marks_1(struct commit_list **plist,\n\n void clear_commit_marks_many(size_t nr, struct commit **commit, unsigned int mark)\n {\n-\tstruct commit_list *list = NULL;\n-\n \tfor (size_t i = 0; i < nr; i++) {\n+\t\tstruct commit_list *list = NULL;\n+\n \t\tclear_commit_marks_1(&list, *commit, mark);\n+\t\twhile (list)\n+\t\t\tclear_commit_marks_1(&list, pop_commit(&list), mark);\n \t\tcommit++;\n \t}\n-\twhile (list)\n-\t\tclear_commit_marks_1(&list, pop_commit(&list), mark);\n }\n\n void clear_commit_marks(struct commit *commit, unsigned int mark)\n--\n2.48.1\n"}]}