{"thread":{"id":"48467","subject":"[PATCH 0/4] a few mark_parents_uninteresting cleanups","startedAt":"2018-05-11T18:00:35Z","lastAt":"2018-05-14T14:09:06Z","messageCount":11,"participants":["Jeff King","Junio C Hamano","Derrick Stolee"],"isPatch":true,"patchVersion":1,"patchTotal":4},"messages":[{"id":"347371","messageId":"20180511180029.GA11290@sigill.intra.peff.net","threadId":"48467","inReplyTo":null,"subject":"[PATCH 0/4] a few mark_parents_uninteresting cleanups","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-05-11T18:00:30Z","receivedAt":"2018-05-11T18:00:35Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"This is a follow-up to the discussion from February:\n\n  https://public-inbox.org/git/1519522496-73090-1-git-send-email-dstolee@microsoft.com/\n\nThere I theorized that some of these extra has_object_file() checks were\nunnecessary. After poking around a bit, I've convinced myself that this\nis the case, so here are some patches.\n\nAfter Stolee's fix in ebbed3ba04 (revision.c: reduce object database\nqueries, 2018-02-24), I doubt this will provide any noticeable speedup.\nIMHO the value is just in simplifying the logic.\n\nThe first two patches are the actual has_object_file simplifications.\nThe second two are an attempt to fix some head-scratching I had while\nreading mark_parents_uninteresting(). I hope the result is easier to\nfollow, but I may have just shuffled one confusion for another. :)\n\n  [1/4]: mark_tree_contents_uninteresting(): drop missing object check\n  [2/4]: mark_parents_uninteresting(): drop missing object check\n  [3/4]: mark_parents_uninteresting(): replace list with stack\n  [4/4]: mark_parents_uninteresting(): avoid most allocation\n\n revision.c | 90 ++++++++++++++++++++++++++++++------------------------\n 1 file changed, 50 insertions(+), 40 deletions(-)\n\n-Peff\n"},{"id":"347372","messageId":"20180511180055.GA12543@sigill.intra.peff.net","threadId":"48467","inReplyTo":"20180511180029.GA11290@sigill.intra.peff.net","subject":"[PATCH 1/4] mark_tree_contents_uninteresting(): drop missing object check","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-05-11T18:00:55Z","receivedAt":"2018-05-11T18:00:59Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"It's generally acceptable for UNINTERESTING objects in a\ntraversal to be unavailable (e.g., see aeeae1b771). When\nmarking trees UNINTERESTING, we access the object database\ntwice: once to check if the object is missing (and return\nquietly if it is), and then again to actually parse it.\n\nWe can instead just try to parse; if that fails, we can then\nreturn quietly. That halves the effort we spend on locating\nthe object.\n\nNote that this isn't _exactly_ the same as the original\nbehavior, as the parse failure could be due to other\nproblems than a missing object: it could be corrupted, in\nwhich case the original code would have died. But the new\nbehavior is arguably better, as it covers the object being\nunavailable for any reason. We'll also still issue a warning\nto stderr in such a case.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n revision.c | 5 +----\n 1 file changed, 1 insertion(+), 4 deletions(-)\n\ndiff --git a/revision.c b/revision.c\nindex 1cff11833e..ef70f69f08 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -52,12 +52,9 @@ static void mark_tree_contents_uninteresting(struct tree *tree)\n {\n \tstruct tree_desc desc;\n \tstruct name_entry entry;\n-\tstruct object *obj = &tree->object;\n \n-\tif (!has_object_file(&obj->oid))\n+\tif (parse_tree_gently(tree, 1) < 0)\n \t\treturn;\n-\tif (parse_tree(tree) < 0)\n-\t\tdie(\"bad tree %s\", oid_to_hex(&obj->oid));\n \n \tinit_tree_desc(&desc, tree->buffer, tree->size);\n \twhile (tree_entry(&desc, &entry)) {\n-- \n2.17.0.988.gec4b43b3e5\n\n"},{"id":"347373","messageId":"20180511180158.GB12543@sigill.intra.peff.net","threadId":"48467","inReplyTo":"20180511180029.GA11290@sigill.intra.peff.net","subject":"[PATCH 2/4] mark_parents_uninteresting(): drop missing object check","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-05-11T18:01:59Z","receivedAt":"2018-05-11T18:02:03Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"We allow UNINTERESTING objects in a traversal to be\nunavailable. As part of this, mark_parents_uninteresting()\nchecks whether we have a particular uninteresting parent; if\nnot, we will mark it as \"parsed\" so that later code skips\nit.\n\nThis code is redundant and even a little bit harmful, so\nlet's drop it.\n\nIt's redundant because when our parse_object() call in\nadd_parents_to_list() fails, we already quietly skip\nUNINTERESTING parents. This redundancy is a historical\nartifact. The mark_parents_uninteresting() protection is\nfrom 454fbbcde3 (git-rev-list: allow missing objects when\nthe parent is marked UNINTERESTING, 2005-07-10). Much later,\naeeae1b771 (revision traversal: allow UNINTERESTING objects\nto be missing, 2009-01-27) covered more cases by making the\nactual parse more gentle.\n\n  As an aside, even if this weren't redundant, it would be\n  insufficient. The gentle parsing handles both missing and\n  corrupted objects, whereas the has_object_file() check\n  we're getting rid of covers only missing ones.\n\nAnd the code we're dropping is harmful for two reasons:\n\n  1. We spend extra time on the object lookup, even though\n     we don't actually need the information at this point\n     (and will just repeat that lookup later when we parse\n     for the common case that we _do_ have the object).\n\n  2. It \"lies\" about the commit by setting the parsed flag,\n     even though we didn't load any useful data into the\n     struct. This shouldn't matter for the UNINTERESTING\n     case, but we may later clear our flags and do another\n     traversal in the same process. While pretty unlikely,\n     it's possible that we could then look at the same\n     commit without the UNINTERESTING flag, in which case\n     we'd produce the wrong result (we'd think it's a commit\n     with no parents, when in fact we should probably die\n     due to the missing object).\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n revision.c | 12 ------------\n 1 file changed, 12 deletions(-)\n\ndiff --git a/revision.c b/revision.c\nindex ef70f69f08..cee4f3a4b4 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -103,18 +103,6 @@ void mark_parents_uninteresting(struct commit *commit)\n \t\tstruct commit *commit = pop_commit(&parents);\n \n \t\twhile (commit) {\n-\t\t\t/*\n-\t\t\t * A missing commit is ok iff its parent is marked\n-\t\t\t * uninteresting.\n-\t\t\t *\n-\t\t\t * We just mark such a thing parsed, so that when\n-\t\t\t * it is popped next time around, we won't be trying\n-\t\t\t * to parse it and get an error.\n-\t\t\t */\n-\t\t\tif (!commit->object.parsed &&\n-\t\t\t    !has_object_file(&commit->object.oid))\n-\t\t\t\tcommit->object.parsed = 1;\n-\n \t\t\tif (commit->object.flags & UNINTERESTING)\n \t\t\t\tbreak;\n \n-- \n2.17.0.988.gec4b43b3e5\n\n"},{"id":"347374","messageId":"20180511180227.GC12543@sigill.intra.peff.net","threadId":"48467","inReplyTo":"20180511180029.GA11290@sigill.intra.peff.net","subject":"[PATCH 3/4] mark_parents_uninteresting(): replace list with stack","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-05-11T18:02:27Z","receivedAt":"2018-05-11T18:02:31Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"The mark_parents_uninteresting() function uses two loops:\nan outer one to process our queue of pending parents, and an\ninner one to process first-parent chains. This is a clever\noptimization from 941ba8db57 (Eliminate recursion in\nsetting/clearing marks in commit list, 2012-01-14) to limit\nthe number of linked-list allocations when following\nsingle-parent chains.\n\nUnfortunately, this makes the result a little hard to read.\nLet's replace the list with a stack. Then we don't have to\nworry about doing this double-loop optimization, as we'll\njust reuse the top element of the stack as we pop/push.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\nThe diff makes a lot more sense with \"-w\".\n\n revision.c | 67 +++++++++++++++++++++++++++++++++++-------------------\n 1 file changed, 43 insertions(+), 24 deletions(-)\n\ndiff --git a/revision.c b/revision.c\nindex cee4f3a4b4..89ff9a99ce 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -92,38 +92,57 @@ void mark_tree_uninteresting(struct tree *tree)\n \tmark_tree_contents_uninteresting(tree);\n }\n \n-void mark_parents_uninteresting(struct commit *commit)\n+struct commit_stack {\n+\tstruct commit **items;\n+\tsize_t nr, alloc;\n+};\n+#define COMMIT_STACK_INIT { NULL, 0, 0 }\n+\n+static void commit_stack_push(struct commit_stack *stack, struct commit *commit)\n {\n-\tstruct commit_list *parents = NULL, *l;\n+\tALLOC_GROW(stack->items, stack->nr + 1, stack->alloc);\n+\tstack->items[stack->nr++] = commit;\n+}\n \n-\tfor (l = commit->parents; l; l = l->next)\n-\t\tcommit_list_insert(l->item, &parents);\n+static struct commit *commit_stack_pop(struct commit_stack *stack)\n+{\n+\treturn stack->nr ? stack->items[--stack->nr] : NULL;\n+}\n \n-\twhile (parents) {\n-\t\tstruct commit *commit = pop_commit(&parents);\n+static void commit_stack_clear(struct commit_stack *stack)\n+{\n+\tFREE_AND_NULL(stack->items);\n+\tstack->nr = stack->alloc = 0;\n+}\n \n-\t\twhile (commit) {\n-\t\t\tif (commit->object.flags & UNINTERESTING)\n-\t\t\t\tbreak;\n+void mark_parents_uninteresting(struct commit *commit)\n+{\n+\tstruct commit_stack pending = COMMIT_STACK_INIT;\n+\tstruct commit_list *l;\n \n-\t\t\tcommit->object.flags |= UNINTERESTING;\n+\tfor (l = commit->parents; l; l = l->next)\n+\t\tcommit_stack_push(&pending, l->item);\n \n-\t\t\t/*\n-\t\t\t * Normally we haven't parsed the parent\n-\t\t\t * yet, so we won't have a parent of a parent\n-\t\t\t * here. However, it may turn out that we've\n-\t\t\t * reached this commit some other way (where it\n-\t\t\t * wasn't uninteresting), in which case we need\n-\t\t\t * to mark its parents recursively too..\n-\t\t\t */\n-\t\t\tif (!commit->parents)\n-\t\t\t\tbreak;\n+\twhile (pending.nr > 0) {\n+\t\tstruct commit *commit = commit_stack_pop(&pending);\n \n-\t\t\tfor (l = commit->parents->next; l; l = l->next)\n-\t\t\t\tcommit_list_insert(l->item, &parents);\n-\t\t\tcommit = commit->parents->item;\n-\t\t}\n+\t\tif (commit->object.flags & UNINTERESTING)\n+\t\t\treturn;\n+\t\tcommit->object.flags |= UNINTERESTING;\n+\n+\t\t/*\n+\t\t * Normally we haven't parsed the parent\n+\t\t * yet, so we won't have a parent of a parent\n+\t\t * here. However, it may turn out that we've\n+\t\t * reached this commit some other way (where it\n+\t\t * wasn't uninteresting), in which case we need\n+\t\t * to mark its parents recursively too..\n+\t\t */\n+\t\tfor (l = commit->parents; l; l = l->next)\n+\t\t\tcommit_stack_push(&pending, l->item);\n \t}\n+\n+\tcommit_stack_clear(&pending);\n }\n \n static void add_pending_object_with_path(struct rev_info *revs,\n-- \n2.17.0.988.gec4b43b3e5\n\n"},{"id":"347375","messageId":"20180511180314.GD12543@sigill.intra.peff.net","threadId":"48467","inReplyTo":"20180511180029.GA11290@sigill.intra.peff.net","subject":"[PATCH 4/4] mark_parents_uninteresting(): avoid most allocation","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-05-11T18:03:15Z","receivedAt":"2018-05-11T18:03:19Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"Commit 941ba8db57 (Eliminate recursion in setting/clearing\nmarks in commit list, 2012-01-14) used a clever double-loop\nto avoid allocations for single-parent chains of history.\nHowever, it did so only when following parents of parents\n(which was an uncommon case), and _always_ incurred at least\none allocation to populate the list of pending parents in\nthe first place.\n\nWe can turn this into zero-allocation in the common case by\niterating directly over the initial parent list, and then\nfollowing up on any pending items we might have discovered.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\nAgain, try \"-w\" for more readability.\n\n revision.c | 44 +++++++++++++++++++++++++-------------------\n 1 file changed, 25 insertions(+), 19 deletions(-)\n\ndiff --git a/revision.c b/revision.c\nindex 89ff9a99ce..cbe041128e 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -115,32 +115,38 @@ static void commit_stack_clear(struct commit_stack *stack)\n \tstack->nr = stack->alloc = 0;\n }\n \n-void mark_parents_uninteresting(struct commit *commit)\n+static void mark_one_parent_uninteresting(struct commit *commit,\n+\t\t\t\t\t  struct commit_stack *pending)\n {\n-\tstruct commit_stack pending = COMMIT_STACK_INIT;\n \tstruct commit_list *l;\n \n+\tif (commit->object.flags & UNINTERESTING)\n+\t\treturn;\n+\tcommit->object.flags |= UNINTERESTING;\n+\n+\t/*\n+\t * Normally we haven't parsed the parent\n+\t * yet, so we won't have a parent of a parent\n+\t * here. However, it may turn out that we've\n+\t * reached this commit some other way (where it\n+\t * wasn't uninteresting), in which case we need\n+\t * to mark its parents recursively too..\n+\t */\n \tfor (l = commit->parents; l; l = l->next)\n-\t\tcommit_stack_push(&pending, l->item);\n+\t\tcommit_stack_push(pending, l->item);\n+}\n \n-\twhile (pending.nr > 0) {\n-\t\tstruct commit *commit = commit_stack_pop(&pending);\n+void mark_parents_uninteresting(struct commit *commit)\n+{\n+\tstruct commit_stack pending = COMMIT_STACK_INIT;\n+\tstruct commit_list *l;\n \n-\t\tif (commit->object.flags & UNINTERESTING)\n-\t\t\treturn;\n-\t\tcommit->object.flags |= UNINTERESTING;\n+\tfor (l = commit->parents; l; l = l->next)\n+\t\tmark_one_parent_uninteresting(l->item, &pending);\n \n-\t\t/*\n-\t\t * Normally we haven't parsed the parent\n-\t\t * yet, so we won't have a parent of a parent\n-\t\t * here. However, it may turn out that we've\n-\t\t * reached this commit some other way (where it\n-\t\t * wasn't uninteresting), in which case we need\n-\t\t * to mark its parents recursively too..\n-\t\t */\n-\t\tfor (l = commit->parents; l; l = l->next)\n-\t\t\tcommit_stack_push(&pending, l->item);\n-\t}\n+\twhile (pending.nr > 0)\n+\t\tmark_one_parent_uninteresting(commit_stack_pop(&pending),\n+\t\t\t\t\t      &pending);\n \n \tcommit_stack_clear(&pending);\n }\n-- \n2.17.0.988.gec4b43b3e5\n"},{"id":"347479","messageId":"xmqqin7se1jd.fsf@gitster-ct.c.googlers.com","threadId":"48467","inReplyTo":"20180511180158.GB12543@sigill.intra.peff.net","subject":"Re: [PATCH 2/4] mark_parents_uninteresting(): drop missing object check","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-05-13T02:23:50Z","receivedAt":"2018-05-13T02:23:57Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n>   2. It \"lies\" about the commit by setting the parsed flag,\n>      even though we didn't load any useful data into the\n>      struct. This shouldn't matter for the UNINTERESTING\n>      case, but we may later clear our flags and do another\n>      traversal in the same process. While pretty unlikely,\n>      it's possible that we could then look at the same\n>      commit without the UNINTERESTING flag,...\n\nYeah, if two ranges given to tbdiff to be compared are computed\nin-core, uninteresting boundary of one range is likely to be\ninteresting on the other range.\n\n"},{"id":"347592","messageId":"8447da69-d28a-433c-f324-a6380b6ca991@gmail.com","threadId":"48467","inReplyTo":"20180511180314.GD12543@sigill.intra.peff.net","subject":"Re: [PATCH 4/4] mark_parents_uninteresting(): avoid most allocation","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-05-14T12:47:33Z","receivedAt":"2018-05-14T12:47:41Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 5/11/2018 2:03 PM, Jeff King wrote:\n> Commit 941ba8db57 (Eliminate recursion in setting/clearing\n> marks in commit list, 2012-01-14) used a clever double-loop\n> to avoid allocations for single-parent chains of history.\n> However, it did so only when following parents of parents\n> (which was an uncommon case), and _always_ incurred at least\n> one allocation to populate the list of pending parents in\n> the first place.\n>\n> We can turn this into zero-allocation in the common case by\n> iterating directly over the initial parent list, and then\n> following up on any pending items we might have discovered.\n\nThis change appears to improve performance, but I was unable to measure \nany difference between this commit and the one ahead, even when merging \nds/generation-numbers (which significantly reduces the other costs). I \nwas testing 'git status' and 'git rev-list --boundary \nmaster...origin/master' in the Linux repo with my copy of master 70,000+ \ncommits behind origin/master.\n\nIt's still a good change, but I was hoping to find a measurable benefit :(\n\n>\n> Signed-off-by: Jeff King <peff@peff.net>\n> ---\n> Again, try \"-w\" for more readability.\n>\n>   revision.c | 44 +++++++++++++++++++++++++-------------------\n>   1 file changed, 25 insertions(+), 19 deletions(-)\n>\n> diff --git a/revision.c b/revision.c\n> index 89ff9a99ce..cbe041128e 100644\n> --- a/revision.c\n> +++ b/revision.c\n> @@ -115,32 +115,38 @@ static void commit_stack_clear(struct commit_stack *stack)\n>   \tstack->nr = stack->alloc = 0;\n>   }\n>   \n> -void mark_parents_uninteresting(struct commit *commit)\n> +static void mark_one_parent_uninteresting(struct commit *commit,\n> +\t\t\t\t\t  struct commit_stack *pending)\n>   {\n> -\tstruct commit_stack pending = COMMIT_STACK_INIT;\n>   \tstruct commit_list *l;\n>   \n> +\tif (commit->object.flags & UNINTERESTING)\n> +\t\treturn;\n> +\tcommit->object.flags |= UNINTERESTING;\n> +\n> +\t/*\n> +\t * Normally we haven't parsed the parent\n> +\t * yet, so we won't have a parent of a parent\n> +\t * here. However, it may turn out that we've\n> +\t * reached this commit some other way (where it\n> +\t * wasn't uninteresting), in which case we need\n> +\t * to mark its parents recursively too..\n> +\t */\n>   \tfor (l = commit->parents; l; l = l->next)\n> -\t\tcommit_stack_push(&pending, l->item);\n> +\t\tcommit_stack_push(pending, l->item);\n> +}\n>   \n> -\twhile (pending.nr > 0) {\n> -\t\tstruct commit *commit = commit_stack_pop(&pending);\n> +void mark_parents_uninteresting(struct commit *commit)\n> +{\n> +\tstruct commit_stack pending = COMMIT_STACK_INIT;\n> +\tstruct commit_list *l;\n>   \n> -\t\tif (commit->object.flags & UNINTERESTING)\n> -\t\t\treturn;\n> -\t\tcommit->object.flags |= UNINTERESTING;\n> +\tfor (l = commit->parents; l; l = l->next)\n> +\t\tmark_one_parent_uninteresting(l->item, &pending);\n>   \n> -\t\t/*\n> -\t\t * Normally we haven't parsed the parent\n> -\t\t * yet, so we won't have a parent of a parent\n> -\t\t * here. However, it may turn out that we've\n> -\t\t * reached this commit some other way (where it\n> -\t\t * wasn't uninteresting), in which case we need\n> -\t\t * to mark its parents recursively too..\n> -\t\t */\n> -\t\tfor (l = commit->parents; l; l = l->next)\n> -\t\t\tcommit_stack_push(&pending, l->item);\n> -\t}\n> +\twhile (pending.nr > 0)\n> +\t\tmark_one_parent_uninteresting(commit_stack_pop(&pending),\n> +\t\t\t\t\t      &pending);\n>   \n>   \tcommit_stack_clear(&pending);\n>   }\n\n"},{"id":"347593","messageId":"db32fff6-b6f0-a420-bf3e-30b17154bf70@gmail.com","threadId":"48467","inReplyTo":"20180511180029.GA11290@sigill.intra.peff.net","subject":"Re: [PATCH 0/4] a few mark_parents_uninteresting cleanups","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-05-14T12:50:03Z","receivedAt":"2018-05-14T12:50:09Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 5/11/2018 2:00 PM, Jeff King wrote:\n> This is a follow-up to the discussion from February:\n>\n>    https://public-inbox.org/git/1519522496-73090-1-git-send-email-dstolee@microsoft.com/\n>\n> There I theorized that some of these extra has_object_file() checks were\n> unnecessary. After poking around a bit, I've convinced myself that this\n> is the case, so here are some patches.\n>\n> After Stolee's fix in ebbed3ba04 (revision.c: reduce object database\n> queries, 2018-02-24), I doubt this will provide any noticeable speedup.\n> IMHO the value is just in simplifying the logic.\n>\n> The first two patches are the actual has_object_file simplifications.\n> The second two are an attempt to fix some head-scratching I had while\n> reading mark_parents_uninteresting(). I hope the result is easier to\n> follow, but I may have just shuffled one confusion for another. :)\n>\n>    [1/4]: mark_tree_contents_uninteresting(): drop missing object check\n>    [2/4]: mark_parents_uninteresting(): drop missing object check\n>    [3/4]: mark_parents_uninteresting(): replace list with stack\n>    [4/4]: mark_parents_uninteresting(): avoid most allocation\n>\n>   revision.c | 90 ++++++++++++++++++++++++++++++------------------------\n>   1 file changed, 50 insertions(+), 40 deletions(-)\n>\n> -Peff\n\nThis series looks good to me. I found Patch 3 hard to read in the diff, \nso I just looked at the final result and the new arrangement is very \nclear about how it should behave.\n\nReviewed-by: Derrick Stolee <dstolee@microsoft.com>\n"},{"id":"347595","messageId":"20180514130907.GB9219@sigill.intra.peff.net","threadId":"48467","inReplyTo":"8447da69-d28a-433c-f324-a6380b6ca991@gmail.com","subject":"Re: [PATCH 4/4] mark_parents_uninteresting(): avoid most allocation","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-05-14T13:09:07Z","receivedAt":"2018-05-14T13:09:12Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, May 14, 2018 at 08:47:33AM -0400, Derrick Stolee wrote:\n\n> On 5/11/2018 2:03 PM, Jeff King wrote:\n> > Commit 941ba8db57 (Eliminate recursion in setting/clearing\n> > marks in commit list, 2012-01-14) used a clever double-loop\n> > to avoid allocations for single-parent chains of history.\n> > However, it did so only when following parents of parents\n> > (which was an uncommon case), and _always_ incurred at least\n> > one allocation to populate the list of pending parents in\n> > the first place.\n> > \n> > We can turn this into zero-allocation in the common case by\n> > iterating directly over the initial parent list, and then\n> > following up on any pending items we might have discovered.\n> \n> This change appears to improve performance, but I was unable to measure any\n> difference between this commit and the one ahead, even when merging\n> ds/generation-numbers (which significantly reduces the other costs). I was\n> testing 'git status' and 'git rev-list --boundary master...origin/master' in\n> the Linux repo with my copy of master 70,000+ commits behind origin/master.\n\nI think you'd want to go the other way: this is marking uninteresting\ncommits, so you'd want origin/master..master, which would make those 70k\ncommits uninteresting.\n\nI still doubt it will create that much difference, though. It's\nmore or less saving a single malloc per commit we traverse. Certainly\nwithout the .commits file that's a drop in the bucket compared to\ninflating the object data, but I wouldn't be surprised if we end up with\na few mallocs even after your patches.\n\nAnyway, thanks for poking at it. :)\n\n-Peff\n"},{"id":"347597","messageId":"bacb6ac4-637d-43c8-8789-2a345097d42a@gmail.com","threadId":"48467","inReplyTo":"20180514130907.GB9219@sigill.intra.peff.net","subject":"Re: [PATCH 4/4] mark_parents_uninteresting(): avoid most allocation","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-05-14T13:25:46Z","receivedAt":"2018-05-14T13:25:52Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 5/14/2018 9:09 AM, Jeff King wrote:\n> On Mon, May 14, 2018 at 08:47:33AM -0400, Derrick Stolee wrote:\n>\n>> On 5/11/2018 2:03 PM, Jeff King wrote:\n>>> Commit 941ba8db57 (Eliminate recursion in setting/clearing\n>>> marks in commit list, 2012-01-14) used a clever double-loop\n>>> to avoid allocations for single-parent chains of history.\n>>> However, it did so only when following parents of parents\n>>> (which was an uncommon case), and _always_ incurred at least\n>>> one allocation to populate the list of pending parents in\n>>> the first place.\n>>>\n>>> We can turn this into zero-allocation in the common case by\n>>> iterating directly over the initial parent list, and then\n>>> following up on any pending items we might have discovered.\n>> This change appears to improve performance, but I was unable to measure any\n>> difference between this commit and the one ahead, even when merging\n>> ds/generation-numbers (which significantly reduces the other costs). I was\n>> testing 'git status' and 'git rev-list --boundary master...origin/master' in\n>> the Linux repo with my copy of master 70,000+ commits behind origin/master.\n> I think you'd want to go the other way: this is marking uninteresting\n> commits, so you'd want origin/master..master, which would make those 70k\n> commits uninteresting.\n\nThanks for the tip. Running 'git rev-list origin/master..master' 100 \ntimes gave the following times, on average (with ds/generation-numbers):\n\nPATCH 3/4: 0.19 s\nPATCH 4/4: 0.16 s\n     Rel %: -16%\n\n>\n> I still doubt it will create that much difference, though. It's\n> more or less saving a single malloc per commit we traverse. Certainly\n> without the .commits file that's a drop in the bucket compared to\n> inflating the object data, but I wouldn't be surprised if we end up with\n> a few mallocs even after your patches.\n>\n> Anyway, thanks for poking at it. :)\n>\n> -Peff\n\n"},{"id":"347602","messageId":"20180514140900.GA10636@sigill.intra.peff.net","threadId":"48467","inReplyTo":"bacb6ac4-637d-43c8-8789-2a345097d42a@gmail.com","subject":"Re: [PATCH 4/4] mark_parents_uninteresting(): avoid most allocation","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-05-14T14:09:00Z","receivedAt":"2018-05-14T14:09:06Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, May 14, 2018 at 09:25:46AM -0400, Derrick Stolee wrote:\n\n> > I think you'd want to go the other way: this is marking uninteresting\n> > commits, so you'd want origin/master..master, which would make those 70k\n> > commits uninteresting.\n> \n> Thanks for the tip. Running 'git rev-list origin/master..master' 100 times\n> gave the following times, on average (with ds/generation-numbers):\n> \n> PATCH 3/4: 0.19 s\n> PATCH 4/4: 0.16 s\n>     Rel %: -16%\n\nNifty. I liked it as just a cleanup, but I'm happier still to find that\nit makes things faster (even if it's pretty small in absolute numbers).\n\n-Peff\n"}]}