Subject: Re: [PATCH 3/3] pack-bitmap.c: use commit boundary during bitmap traversal

From: Junio C Hamano <[email-masked]>
Date: Tue, 25 Apr 2023 11:52:25 -0700

Taylor Blau <[email-masked]> writes:

>   3. Fall back to the ordinary object traversal if either (a) there are
>      no haves, (b) none of the haves are in the bitmapped pack or MIDX,
>      or (c) there are no wants.

Tangents.  If there are no haves, wouldn't the answer by definition
everything that are reachable from all wants?  Is there a reason why
a bitmapped walk cannot fulfill such a request?  If there are no
wants, wouldn't the answer by definition an empty set?  Again, I am
not sure what the ordinary object traversal is expected to do in
such a case.

These questions are not at all important, as this part is an
explation of what happened in the old code.

> Relaxing the bitmap traversal to allow it to produce over-counted
> results gives us the opportunity to make some significant improvements.
> Instead of the above, the new algorithm only has to walk from the
> *boundary* down to the nearest bitmap, instead of from each of the
> UNINTERESTING tips.

Is it only me, or are all readers equally confused by the use of
the term "boundary" that hasn't been given any definition?

> And is more-or-less equivalent to using the *old* algorithm with this
> invocation:
>
>     $ git rev-list --objects --boundary $WANTS --not $HAVES |

It is especially confusing because the "--boundary" (at least as I
originally had invented it), i.e. a commit that is smudged with
UNINTERESTING bit, whose parent we did not bother to dig further to
paint with the same UNINTERESTING bit, is not something we start our
computation with; it is something we learn _after_ completing the
history traversing.  So I am utterly confused X-<.