[PATCH 4/4] mark_parents_uninteresting(): avoid most allocation
- From
Jeff King <peff@peff.net>
- Date
- May 11, 2018, 18:03 UTC
- Message-ID
- <20180511180314.GD12543@sigill.intra.peff.net>
- In-Reply-To
- <20180511180029.GA11290@sigill.intra.peff.net>
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 <peff@peff.net> --- 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(&pending, l->item); + commit_stack_push(pending, l->item); +} - while (pending.nr > 0) { - struct commit *commit = commit_stack_pop(&pending); +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, &pending); - /* - * 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(&pending, l->item); - } + while (pending.nr > 0) + mark_one_parent_uninteresting(commit_stack_pop(&pending), + &pending); commit_stack_clear(&pending); }
-- 2.17.0.988.gec4b43b3e5