From: Mirko Faina <mroik@delayed.space>
Date: Sat, 18 Apr 2026 18:51:12 GMT
Subject: Re: [PATCH] revision.c: implement --reverse=before for walks
Message-ID: <aePSGXu5l9x-NKVG@exploit>
In-Reply-To: <aePNILp-yB_8gfiY@exploit>

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.