From: Jeff King <peff@peff.net>
Date: Fri, 11 May 2018 18:03:15 +0000 (-0400)
Subject: mark_parents_uninteresting(): avoid most allocation
X-Git-Tag: v2.18.0-rc0~24^2
X-Git-Url: https://git.lorimer.id.au/gitweb.git/diff_plain/8702b30fd7b6c804f1bb59877a4c2f773fbe00f8?ds=sidebyside

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 <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---

diff --git a/revision.c b/revision.c
index 125327062f..c21acb2cb8 100644
--- a/revision.c
+++ b/revision.c
@@ -114,32 +114,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);
 }