Re: [RFC] Possible idea for GSoC 2020

> Hello Philip,
>
> Philip Oakley <philipoakley@iee.email> writes:
>> On 10/03/2020 14:50, Jakub Narebski wrote:
> [...]
>>> ### Graph labelling for speeding up git commands
>>>
>>>  - Language: C
>>>  - Difficulty: hard / difficult
>>>  - Possible mentors: Jakub Narębski
>>>
>>> Git uses various clever methods for making operations on very large
>>> repositories faster, from bitmap indices for git-fetch[1], to generation
>>> numbers (also known as topological levels) in the commit-graph file for
>>> commit graph traversal operations like `git log --graph`[2].
>>>
>>> One possible improvement that can make Git even faster is using min-post
>>> intervals labelling.  The basis of this labelling is post-visit order of
>>> a depth-first search traversal tree of a commit graph, let's call it
>>> 'post(v)'.

>> This, the post(v) number, may need a bit more explanation for those not
>> familiar with graph theory terminology, so that they can get up to speed
>> easily about the method, and it's (hopeful) simplicity.
> All right, I see that it might be not clear for someone who is not
> familiar with graph theory terminology.  The post(v) order is the order
> you encounter commits, assuming that you mark commit 'v' as visited
> after all its parents have been visited.

>
> The positive-cut labeling works also for pre(v) order, where we number
> commits from top, starting from heads, marking commit 'v' as visited
> before any of its parents (you just need to switch from min-post to
> pre-max interval).

>
>>  It isn't clear to me if it is a count along a single string-of-pearls
>> between two branch - merge points, or depth from origin, or whether it
>> can span large chunks of the DAG? Ref 3. has the same problem of
>> starting from an assumed level of knowledge and understanding that may
>> put of non-academics (I'm thinking that the proposed method is this
>> PReaCH [3]).
> The basic method is something simpler, common to all those methods.
> It is described as
> - method from "3.3 Pruning Based on DFS Numbering" in PReaCH[3] paper
>   (only one of full intervals from Figure 3 there), with modifications
> - method from "Interval Indexing" paragraph in "I. Introduction"
>   in FERRARI[4] paper, but using only a single interval (strict or
>   approximate)
> - Fig. 4 Min-Post Labeling, in "GRAIL: A Scalable Index for Reachability
>   Queries in Very Large Graphs" (2012) paper
> - "3.4.1 Positive-Cut Filter" subsubsection in "3.4 Optimizations"
>   in FELINE paper i.e. "Reachability Queries in Very Large Graphs:
>   A Fast Refined Online Search Approach" (2014)
>
>> It's my understanding that 'v' is usually 1...n in the literature, but
>> in reality it just means 'unique label' (and ultimately able to be
>> indexed in a data table). In Git we use the object id as the unique
>> label, so the 1..n is just an abstraction/convenience. The other problem
>> that can happen is if the terminologies of Git doesn't quite match those
>> of the descriptions, such as which end is 'root', or being 'mutually
>> reachable' in a directed acyclic graph.
> Yes, when reading various graph papers, I need to translate 'root',
> 'leaf', 'child' from graph-theory terminology to git terminology.
>
> But 'v' being a node (a commit in a commit graph of revisions) is not
> one of them.

>
>> The Wikipedia article on contraction hierarchies [6] did give some
>> useful clues for more lay readers.
> Ooops.  Actually in my opinion Reachability Contraction Hierarchies
> (RCH) reachability index from PReaCH[3] paper would not work for Git, as
> it assumes bidirectional BFS search.
>
> I have cited PReaCH[3] paper for its Pruning Based on DFS Numbering
> ideas.
>
>>> If for each commit 'v' we would compute and store in the commit-graph
>>> file two numbers: 'post(v)' and the minimum of 'post(u)' for all commits
>>> reachable from 'v', let's call the latter 'min_graph(v)', then the
>>> following condition is true:
>>>
>>>   if 'v' can reach 'u', then min_graph(v) <= post(u) <= post(v)
>>>
>>> If for each commit 'v' we would compute and store in the commit-graph
>>> file two numbers: 'post(v)' and the minimum of 'post(u)' for commits
>>> that were visited during the part of depth-first search that started
>>> from 'v' (which is the minimum of post-order number for subtree of a
>>> spanning tree that starts at 'v').  Let's call the later 'min_tree(v)'.
>>> Then the following condition is true:
>>>
>>>   if min_tree(v) <= post(u) <= post(v), then 'v' can reach 'u'
>>>
>>> The task would be to implement computing such labelling (or a more
>>> involved variant of it[3][4]), storing it in commit-graph file, and
>>> using it for speeding up git commands (starting from a single chosen
>>> command) such as:
>>>
>>>  - git merge-base --is-ancestor A B
>>>  - git branch --contains A
>>>  - git tag --contains A
>>>  - git branch --merged A
>>>  - git tag --merged A
>>>  - git merge-base --all A B
>>>  - git log --topo-sort
>>>
>>> References:
>>>
>>> 1. <http://githubengineering.com/counting-objects/>
>>> 2. <https://devblogs.microsoft.com/devops/supercharging-the-git-commit-graph-iii-generations/>
>>> 3. <https://arxiv.org/abs/1404.4465>
>>> 4. <https://github.com/steps/Ferrari>
>>>
>>> See also discussion in:
>>>
>>> <https://public-inbox.org/git/86tvl0zhos.fsf@gmail.com/t/>  [5]
>> [6] https://en.wikipedia.org/wiki/Contraction_hierarchies
>>
>> [I've been off-list for 2+ ,months, so still catching up]
> Best,