Re: [PATCH] revision.c: implement --reverse=before for walks

From: Tian Yuchen <cat@malon.dev>
Date: Apr 20, 2026, 17:08 UTC
Message-ID: <e071f152-c718-4680-ad15-769591080ac8@malon.dev>
In-Reply-To: <xmqqv7dlr4yz.fsf@gitster.g>

On 4/21/26 00:06, Junio C Hamano wrote:

Show 11 quoted lines

> Tian Yuchen <cat@malon.dev> writes:
> 
>> I think the space complexity here could be reduced a little. After all,
>> since we’re only retrieving a few commits, there’s no need to load the
>> entire reversed commit history into memory.
> 
> Does "we're only retrieving a few commits" come from the fact that
> the command example is "log --reverse -3"?
> 
>   - What should happen when you give "git log --reverse=before"
>     without "--max-count=3"?

I still wanna talk my way out of it ;)

If we maintain a window of length K out of N nodes:

   - If K is small (e.g. 3), The space complexity is strictly O(K), 
which saves a considerable amount compared to the unoptimised one;

   - If K is huge, reduce to traversing all N nodes. At this point, the 
space complexity is the same as when unoptimised (O(N)). At most, there 
is an additional time cost of O(log N) for stack operation, which can be 
disregarded.

It seems like a strategy that could be applied consistently, but...

>   - What should happen without "--max-count" but other limiting
>     options, like "--author=Tian" or "--min-parents=2"?

I must admit you’re absolutely right on this point.

If we were to introduce a new state machine and data structure for every type of parameter, it would indeed be rather cumbersome to maintain and not particularly cost-effective.

Show 5 quoted lines

> It might be that the right way to look at this new feature is not
> that "we are changing where reverse is applied", but "count limit is
> applied much later than usual", which may mean at the UI level, it
> may not be good at the conceptual level to sell this as an extension
> to the "--reverse" option?  I dunno.

That's what I meant to say earlier in the 'nit' section. I couldn’t quite put it into words at that time :((

Thanks, Yuchen