Re: [RFC] Other chunks for commit-graph, part 1 - Bloom filters, topo order, etc.

From: Johannes Schindelin <johannes.schindelin@gmx.de>
Date: May 15, 2018, 10:01 UTC
Message-ID: <nycvar.QRO.7.76.6.1805151155160.77@tvgsbejvaqbjf.bet>
In-Reply-To: <864lja2buq.fsf@gmail.com>

Hi Kuba,

On Mon, 14 May 2018, Jakub Narebski wrote:

Show 38 quoted lines

> [... lots and lots of discussions...]
>
> All right.
> 
> Here is my [allegedly] improved version, which assumes that we always
> want to start from commit with maximum generation number (there may be
> more than one such commit).
> 
> Let's add one more data structure:
> 
>   RRQ : A queue, for storing remaining commits from R (starting point).
>   It is a priority queue ordered by generation number.
> 
> 
> InitializeTopoOrder(R):
>     Initialize IDQ, IDV, TOQ, RRQ
> 
>     max_generation = 0
>     visit_order = 0
> 
>     for each commit c in R:
>         max_generation = max(max_generation, generation(c))
>         unless IsRedundantFilter(R / c, c): # optional
>             RRQ.Enqueue(c, generation(c))
> 
>     while RRQ.Max == max_generation:
>         c = RRQ.Dequeue()
>         IDV[c] = 0  # commits with max gen have in-degree of 0
>         IDQ.Enqueue(c, generation(c))
> 
>     # this would be almost no-op
>     AdvanceInDegreeWalk(IDQ, IDV, max_generation)
> 
>     for each commit c in reversed R:
>         if generation(c) == max_generation: # then IDV[c] == 0
>             TOQ.Enqueue(c, visit_order++)
> 
>     return (IDQ, IDV, TOQ, RRQ, visit_order)

Isn't it premature to throw out code at this stage? My impression from the side lines is that Stolee is trying to get concrete code implemented, code that can be tested against concrete repositories, so that the question of singularly overall importance can be asked: is it worth it, is it really faster? And by how much?

It may not be the best idea to distract Stolee from said implementation (i.e. step 1) by getting ahead ourselves with steps 17, 18 or 19. The next steps would seem to be step 2 and 3, and I am sure that Stolee would appreciate your help in implementing them.

So at this point it would maybe make a lot more sense to help Stolee e.g. by refactoring the rev-list code that is a *mess* around the topo order, so that all kinds of cute algorithms can be implemented *directly* in Git, and put to the ultimate test.

Ciao, Dscho