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

[Mirko Faina <mroik@delayed.space>]

On Sat, Apr 18, 2026 at 08:42:15PM +0200, Mirko Faina wrote:
> > 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.
> > 
> > Perhaps we could maintain a window (or perhaps max heap) of finite length?
> 
> Unfortunately since the underlying data structure is a linked list we
> have to traverse the whole tree to get the first one from the tail. The
> way get_revision() loads the next commit is through process_parents().
> Even if we were able to start from the tail we wouldn't have any
> reference to the children.
> 
> I suspect reducing space complexity would require to change a lot of
> inner workings of git to make the history traversable both ways.

Oh, I missunderstood what you meant, sorry. Yes, a window should allow
us to reduce the amount of the memory used. Will do in v2.