Re: [PATCH 4/4] mark_parents_uninteresting(): avoid most allocation
On Mon, May 14, 2018 at 09:25:46AM -0400, Derrick Stolee wrote: > > I think you'd want to go the other way: this is marking uninteresting > > commits, so you'd want origin/master..master, which would make those 70k > > commits uninteresting. > > Thanks for the tip. Running 'git rev-list origin/master..master' 100 times > gave the following times, on average (with ds/generation-numbers): > > PATCH 3/4: 0.19 s > PATCH 4/4: 0.16 s > Rel %: -16% Nifty. I liked it as just a cleanup, but I'm happier still to find that it makes things faster (even if it's pretty small in absolute numbers). -Peff
Re: [PATCH 4/4] mark_parents_uninteresting(): avoid most allocation
On 5/14/2018 9:09 AM, Jeff King wrote: On Mon, May 14, 2018 at 08:47:33AM -0400, Derrick Stolee wrote: On 5/11/2018 2:03 PM, Jeff King wrote: Commit 941ba8db57 (Eliminate recursion in setting/clearing marks in commit list, 2012-01-14) used a clever double-loop to avoid allocations for single-parent chains of history. However, it did so only when following parents of parents (which was an uncommon case), and _always_ incurred at least one allocation to populate the list of pending parents in the first place. We can turn this into zero-allocation in the common case by iterating directly over the initial parent list, and then following up on any pending items we might have discovered. This change appears to improve performance, but I was unable to measure any difference between this commit and the one ahead, even when merging ds/generation-numbers (which significantly reduces the other costs). I was testing 'git status' and 'git rev-list --boundary master...origin/master' in the Linux repo with my copy of master 70,000+ commits behind origin/master. I think you'd want to go the other way: this is marking uninteresting commits, so you'd want origin/master..master, which would make those 70k commits uninteresting. Thanks for the tip. Running 'git rev-list origin/master..master' 100 times gave the following times, on average (with ds/generation-numbers): PATCH 3/4: 0.19 s PATCH 4/4: 0.16 s Rel %: -16% I still doubt it will create that much difference, though. It's more or less saving a single malloc per commit we traverse. Certainly without the .commits file that's a drop in the bucket compared to inflating the object data, but I wouldn't be surprised if we end up with a few mallocs even after your patches. Anyway, thanks for poking at it. :) -Peff
Re: [PATCH 4/4] mark_parents_uninteresting(): avoid most allocation
On 5/11/2018 2:03 PM, Jeff King wrote: Commit 941ba8db57 (Eliminate recursion in setting/clearing marks in commit list, 2012-01-14) used a clever double-loop to avoid allocations for single-parent chains of history. However, it did so only when following parents of parents (which was an uncommon case), and _always_ incurred at least one allocation to populate the list of pending parents in the first place. We can turn this into zero-allocation in the common case by iterating directly over the initial parent list, and then following up on any pending items we might have discovered. This change appears to improve performance, but I was unable to measure any difference between this commit and the one ahead, even when merging ds/generation-numbers (which significantly reduces the other costs). I was testing 'git status' and 'git rev-list --boundary master...origin/master' in the Linux repo with my copy of master 70,000+ commits behind origin/master. It's still a good change, but I was hoping to find a measurable benefit :( Signed-off-by: Jeff King--- Again, try "-w" for more readability. revision.c | 44 +--- 1 file changed, 25 insertions(+), 19 deletions(-) diff --git a/revision.c b/revision.c index 89ff9a99ce..cbe041128e 100644 --- a/revision.c +++ b/revision.c @@ -115,32 +115,38 @@ static void commit_stack_clear(struct commit_stack *stack) stack->nr = stack->alloc = 0; } -void mark_parents_uninteresting(struct commit *commit) +static void mark_one_parent_uninteresting(struct commit *commit, + struct commit_stack *pending) { - struct commit_stack pending = COMMIT_STACK_INIT; struct commit_list *l; + if (commit->object.flags & UNINTERESTING) + return; + commit->object.flags |= UNINTERESTING; + + /* +* Normally we haven't parsed the parent +* yet, so we won't have a parent of a parent +* here. However, it may turn out that we've +* reached this commit some other way (where it +* wasn't uninteresting), in which case we need +* to mark its parents recursively too.. +*/ for (l = commit->parents; l; l = l->next) - commit_stack_push(, l->item); + commit_stack_push(pending, l->item); +} - while (pending.nr > 0) { - struct commit *commit = commit_stack_pop(); +void mark_parents_uninteresting(struct commit *commit) +{ + struct commit_stack pending = COMMIT_STACK_INIT; + struct commit_list *l; - if (commit->object.flags & UNINTERESTING) - return; - commit->object.flags |= UNINTERESTING; + for (l = commit->parents; l; l = l->next) + mark_one_parent_uninteresting(l->item, ); - /* -* Normally we haven't parsed the parent -* yet, so we won't have a parent of a parent -* here. However, it may turn out that we've -* reached this commit some other way (where it -* wasn't uninteresting), in which case we need -* to mark its parents recursively too.. -*/ - for (l = commit->parents; l; l = l->next) - commit_stack_push(, l->item); - } + while (pending.nr > 0) + mark_one_parent_uninteresting(commit_stack_pop(), + ); commit_stack_clear(); }
[PATCH 4/4] mark_parents_uninteresting(): avoid most allocation
Commit 941ba8db57 (Eliminate recursion in setting/clearing marks in commit list, 2012-01-14) used a clever double-loop to avoid allocations for single-parent chains of history. However, it did so only when following parents of parents (which was an uncommon case), and _always_ incurred at least one allocation to populate the list of pending parents in the first place. We can turn this into zero-allocation in the common case by iterating directly over the initial parent list, and then following up on any pending items we might have discovered. Signed-off-by: Jeff King--- Again, try "-w" for more readability. revision.c | 44 +--- 1 file changed, 25 insertions(+), 19 deletions(-) diff --git a/revision.c b/revision.c index 89ff9a99ce..cbe041128e 100644 --- a/revision.c +++ b/revision.c @@ -115,32 +115,38 @@ static void commit_stack_clear(struct commit_stack *stack) stack->nr = stack->alloc = 0; } -void mark_parents_uninteresting(struct commit *commit) +static void mark_one_parent_uninteresting(struct commit *commit, + struct commit_stack *pending) { - struct commit_stack pending = COMMIT_STACK_INIT; struct commit_list *l; + if (commit->object.flags & UNINTERESTING) + return; + commit->object.flags |= UNINTERESTING; + + /* +* Normally we haven't parsed the parent +* yet, so we won't have a parent of a parent +* here. However, it may turn out that we've +* reached this commit some other way (where it +* wasn't uninteresting), in which case we need +* to mark its parents recursively too.. +*/ for (l = commit->parents; l; l = l->next) - commit_stack_push(, l->item); + commit_stack_push(pending, l->item); +} - while (pending.nr > 0) { - struct commit *commit = commit_stack_pop(); +void mark_parents_uninteresting(struct commit *commit) +{ + struct commit_stack pending = COMMIT_STACK_INIT; + struct commit_list *l; - if (commit->object.flags & UNINTERESTING) - return; - commit->object.flags |= UNINTERESTING; + for (l = commit->parents; l; l = l->next) + mark_one_parent_uninteresting(l->item, ); - /* -* Normally we haven't parsed the parent -* yet, so we won't have a parent of a parent -* here. However, it may turn out that we've -* reached this commit some other way (where it -* wasn't uninteresting), in which case we need -* to mark its parents recursively too.. -*/ - for (l = commit->parents; l; l = l->next) - commit_stack_push(, l->item); - } + while (pending.nr > 0) + mark_one_parent_uninteresting(commit_stack_pop(), + ); commit_stack_clear(); } -- 2.17.0.988.gec4b43b3e5