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 <peff@xxxxxxxx>
---
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);
}
