Re: [PATCH v4 00/13] Serialized Git Commit Graph

[Derrick Stolee <stolee@gmail.com>]

On 4/2/2018 1:35 PM, Stefan Beller wrote:
> On Mon, Apr 2, 2018 at 8:02 AM, Derrick Stolee <stolee@gmail.com> wrote:
>>>> I would be happy to review any effort to extend the commit-graph
>>>> format to include such indexes, as long as the performance benefits
>>>> outweigh the complexity to create them.
>>>>
>>>> [2]
>>>> http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.719.8396&rep=rep1&type=pdf
>>> The complexity of calculating FELINE index is O(|V| log(|V|) + |E|), the
>>> storage complexity is 2*|V|.
>>>
>> This would be very easy to add as an optional chunk, since it can use one
>> row per commit.
> Given this discussion, I wonder if we want to include generation numbers
> as a first class citizen in the current format. They could also go as
> an optional
> chunk and we may want to discuss further if we want generation numbers or
> FELINE numbers or GRAIL or SCARAB, which are all graph related speedup
> mechanism AFAICT.
> In case we decide against generation numbers in the long run,
> the row of mandatory generation numbers would be dead weight
> that we'd need to carry.

Currently, the format includes 8 bytes to share between the generation 
number and commit date. Due to alignment concerns, we will want to keep 
this as 8 bytes or truncate it to 4-bytes. Either we would be wasting at 
least 3 bytes or truncating dates too much (presenting the 2038 problem 
[1] since dates are signed).

> I only glanced at the paper, but it looks like a "more advanced 2d
> generation number" that seems to be able to answer questions
> that gen numbers can answer, but that paper also refers
> to SCARAB as well as GRAIL as the state of the art, so maybe
> there are even more papers to explore?

The biggest reason I can say to advance this series (and the small 
follow-up series that computes and consumes generation numbers) is that 
generation numbers are _extremely simple_. You only need to know your 
parents and their generation numbers to compute your own. These other 
reachability indexes require examining the entire graph to create "good" 
index values.

The hard part about using generation numbers (or any other reachability 
index) in Git is refactoring the revision-walk machinery to take 
advantage of them; current code requires O(reachable commits) to 
topo-order instead of O(commits that will be output). I think we should 
table any discussion of these advanced indexes until that work is done 
and a valuable comparison can be done. "Premature optimization is the 
root of all evil" and all that.

Thanks,
-Stolee

[1] https://en.wikipedia.org/wiki/Year_2038_problem