commit-reach: cleanups in can_all_from_reach...

Commit Message

Derrick Stolee Sept. 25, 2018, 1:27 p.m. UTC

From: Derrick Stolee <[e-mail]>

Due to a regression introduced by 4fbcca4e "commit-reach: make
can_all_from_reach... linear" the series including b67f6b26
"commit-reach: properly peel tags" was merged to master quickly.

There were a few more cleanups left to apply in the series, which
are included by this change:

1. Clean up a comment that is in the incorrect style.

2. Replace multiple calls to clear_commit_marks() with one call to
   clear_commit_marks_many().

Signed-off-by: Derrick Stolee <[e-mail]>
---
 commit-reach.c | 8 +++-----
 1 file changed, 3 insertions(+), 5 deletions(-)


base-commit: 4067a64672f9db8ca38d5a2682a7cdba7938c18b

Comments

Junio C Hamano Sept. 25, 2018, 6:06 p.m. UTC | #1

Derrick Stolee <[e-mail]> writes:

> @@ -622,10 +623,7 @@ int can_all_from_reach_with_flag(struct object_array *from,
>  	}
>  
>  cleanup:
> -	for (i = 0; i < nr_commits; i++) {
> -		clear_commit_marks(list[i], RESULT);
> -		clear_commit_marks(list[i], assign_flag);
> -	}
> +	clear_commit_marks_many(nr_commits, list, RESULT | assign_flag);
>  	free(list);
>  
>  	for (i = 0; i < from->nr; i++)
>
> base-commit: 4067a64672f9db8ca38d5a2682a7cdba7938c18b

This change looks good to me. 

This is a tangent, but while re-reading clear_commit_marks() and its
helpers to refresh my memory, I found that the bottom-most helper in
the callchain was written in a very confusing way, but it is not a
fault of this clean-up.  I however suspect that it would not help us
all that much to use clear_commit_marks_many() with its current
implementation.  It first clears all commits on the first-parent
chain from each list[] element, while accumulating the parent
commits that are yet to be processed in a commit_list in LIFO order,
and then consumes these accumulated side parents the same way.  We
probably would benefit by rewriting clear_commit_marks_many() to
traverse from all the tips given in list[] taking advantage of the
generation numbers, using a prio queue to manage the commits
yet-to-be-cleared, or something.

Derrick Stolee Sept. 25, 2018, 6:13 p.m. UTC | #2

On 9/25/2018 2:06 PM, Junio C Hamano wrote:
> Derrick Stolee <[e-mail]> writes:
>
>> @@ -622,10 +623,7 @@ int can_all_from_reach_with_flag(struct object_array *from,
>>   	}
>>   
>>   cleanup:
>> -	for (i = 0; i < nr_commits; i++) {
>> -		clear_commit_marks(list[i], RESULT);
>> -		clear_commit_marks(list[i], assign_flag);
>> -	}
>> +	clear_commit_marks_many(nr_commits, list, RESULT | assign_flag);
>>   	free(list);
>>   
>>   	for (i = 0; i < from->nr; i++)
>>
>> base-commit: 4067a64672f9db8ca38d5a2682a7cdba7938c18b
> This change looks good to me.
>
> This is a tangent, but while re-reading clear_commit_marks() and its
> helpers to refresh my memory, I found that the bottom-most helper in
> the callchain was written in a very confusing way, but it is not a
> fault of this clean-up.  I however suspect that it would not help us
> all that much to use clear_commit_marks_many() with its current
> implementation.  It first clears all commits on the first-parent
> chain from each list[] element, while accumulating the parent
> commits that are yet to be processed in a commit_list in LIFO order,
> and then consumes these accumulated side parents the same way.  We
> probably would benefit by rewriting clear_commit_marks_many() to
> traverse from all the tips given in list[] taking advantage of the
> generation numbers, using a prio queue to manage the commits
> yet-to-be-cleared, or something.

Another commit walk that could be improved by generation numbers? It's 
like my bat-signal!

Thanks for pointing me in that direction. I'll take a look.

-Stolee

Junio C Hamano Sept. 25, 2018, 8:29 p.m. UTC | #3

Derrick Stolee <[e-mail]> writes:

> Another commit walk that could be improved by generation numbers? It's
> like my bat-signal!

Ah, nevermind.  The "traversal" done by these helper functions is
the most stupid kind (not the algorthim, but the need).  It's not
like there is an opportunity to optimize by not traversing the
remainder if we choose the order of traversal intelligently, so any
algorithm that does not visit the same node twice and does not do
the most naive recursion would work, and what we currently have
there is just fine.

Patch

diff --git a/commit-reach.c b/commit-reach.c
index 5a845440a9..66aa41262c 100644
--- a/commit-reach.c
+++ b/commit-reach.c
@@ -558,7 +558,8 @@  int can_all_from_reach_with_flag(struct object_array *from,
 		from_one = deref_tag(the_repository, from_one,
 				     "a from object", 0);
 		if (!from_one || from_one->type != OBJ_COMMIT) {
-			/* no way to tell if this is reachable by
+			/*
+			 * no way to tell if this is reachable by
 			 * looking at the ancestry chain alone, so
 			 * leave a note to ourselves not to worry about
 			 * this object anymore.
@@ -622,10 +623,7 @@  int can_all_from_reach_with_flag(struct object_array *from,
 	}
 
 cleanup:
-	for (i = 0; i < nr_commits; i++) {
-		clear_commit_marks(list[i], RESULT);
-		clear_commit_marks(list[i], assign_flag);
-	}
+	clear_commit_marks_many(nr_commits, list, RESULT | assign_flag);
 	free(list);
 
 	for (i = 0; i < from->nr; i++)