[RFC] Possible idea for GSoC 2020

> A few questions:
> - is it too late to propose a new project idea for GSoC 2020?
> - is it too difficult of a project for GSoC?
> ...
> ### 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)'.
>
> 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/>

> Jakub Narebski <jnareb@gmail.com> writes:
>
>> A few questions:
>> - is it too late to propose a new project idea for GSoC 2020?
>> - is it too difficult of a project for GSoC?
>> ...
>> ### Graph labelling for speeding up git commands
>>
>>  - Language: C
>>  - Difficulty: hard / difficult
>>  - Possible mentors: Jakub Narębski
>
> I am not running the GSoC or participating in it in any way other
> than just being a reviewer-maintainer of the project, but I would
> appreciate a well-thought-out write-up very much.

>> 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)'.
>>
>> 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/>

>>> ### Graph labelling for speeding up git commands
>>>
>>>  - Language: C
>>>  - Difficulty: hard / difficult
>>>  - Possible mentors: Jakub Narębski
>>
>> I am not running the GSoC or participating in it in any way other
>> than just being a reviewer-maintainer of the project, but I would
>> appreciate a well-thought-out write-up very much.
>
> I have prepared slides for "Graph operations in Git version control
> system" (PDF), mainly describing what was already done to improve their
> performance, but they also include a few thoughts about the future (like
> additional graph reachability labelings)... unfortunately the slides are
> in Polish, not in English.
>
> If there is interest, I could translate them, and put the result
> somewhere accessible.

> Jakub Narebski <jnareb@gmail.com> writes:
>>
>> I have prepared slides for "Graph operations in Git version control
>> system" (PDF), mainly describing what was already done to improve their
>> performance, but they also include a few thoughts about the future (like
>> additional graph reachability labelings)... unfortunately the slides are
>> in Polish, not in English.
>>
>> If there is interest, I could translate them, and put the result
>> somewhere accessible.
> 
> Here it is, traanslated into English, but otherwise almost exactly as I
> have presented it on December 2019.  Those slides includes much of
> introductory information, so one would be interested probably in few
> last slides (the "Future work" section).
> 
>    https://drive.google.com/file/d/1psMBVfcRHcZeJ7AewGpdoymrEfFVdXoK/view?usp=sharing
> 
> I will be extending those slides with more information about interval
> labeling, and then I will update the file, and I can post it also on
> SlideShare (or other site, if one can recommend it).
>

>> I will be extending those slides with more information about interval
>> labeling, and then I will update the file, and I can post it also on
>> SlideShare (or other site, if one can recommend it).
>>
> 
> Just wanted to note that Speaker deck[1] is a nice alternative to 
> SlideShare. I've not uploaded slides to it but have seen people sharing 
> slides using Speaker deck. I find the user interface to be more neat and 
> minimalistic than SlideShare. FWIW, their mobile interface a lot better 
> than the SlideShare's interface.
> 

> On 15-03-2020 19:56, Jakub Narebski wrote:
>> Jakub Narebski <jnareb@gmail.com> writes:
>>>
>>> I have prepared slides for "Graph operations in Git version control
>>> system" (PDF), mainly describing what was already done to improve their
>>> performance, but they also include a few thoughts about the future (like
>>> additional graph reachability labelings)... unfortunately the slides are
>>> in Polish, not in English.
>>>
>>> If there is interest, I could translate them, and put the result
>>> somewhere accessible.
>>
>> Here it is, traanslated into English, but otherwise almost exactly as I
>> have presented it on December 2019.  Those slides includes much of
>> introductory information, so one would be interested probably in few
>> last slides (the "Future work" section).
>>
>>    https://drive.google.com/file/d/1psMBVfcRHcZeJ7AewGpdoymrEfFVdXoK/view?usp=sharing
>>
>> I will be extending those slides with more information about interval
>> labeling, and then I will update the file, and I can post it also on
>> SlideShare (or other site, if one can recommend it).
>>
>
> Just wanted to note that Speaker deck[1] is a nice alternative to
> SlideShare. I've not uploaded slides to it but have seen people
> sharing slides using Speaker deck. I find the user interface to be
> more neat and minimalistic than SlideShare. FWIW, their mobile
> interface a lot better than the SlideShare's interface.
>
> [1]: https://speakerdeck.com/

>
> Hello,
>
> Here below is a possible proposal for a more difficult Google Summer of
> Code 2020 project.
>
> A few questions:
> - is it too late to propose a new project idea for GSoC 2020?

> On Tue, Mar 10, 2020 at 3:50 PM Jakub Narebski <jnareb@gmail.com> wrote:
>>
>> Here below is a possible proposal for a more difficult Google Summer of
>> Code 2020 project.
>>
>> A few questions:
>> - is it too late to propose a new project idea for GSoC 2020?
>
> I don't think so. Students have until March 16 to submit a proposal,
> so they could still submit one based on this even if it's late.

>> - is it too difficult of a project for GSoC?
>
> I guess it depends on how much you as a mentor would help the student
> getting started.
>
> I think it's interesting and worth adding it anyway. Can you add it to
> SoC-2020-Ideas.md?

> >> A few questions:
> >> - is it too late to propose a new project idea for GSoC 2020?
> >
> > I don't think so. Students have until March 16 to submit a proposal,
> > so they could still submit one based on this even if it's late.
>
> If I understand Google Summer of Code 2020 Timeline correctly
> https://developers.google.com/open-source/gsoc/timeline
> March 16 is the date when students might start to submit
> proposals, and the deadline is March 20.

> >> - is it too difficult of a project for GSoC?
> >
> > I guess it depends on how much you as a mentor would help the student
> > getting started.
> >
> > I think it's interesting and worth adding it anyway. Can you add it to
> > SoC-2020-Ideas.md?
>
> All right, I'll do it.

> On Wed, Mar 11, 2020 at 10:30 PM Jakub Narebski <jnareb@gmail.com> wrote:
>
>>>> A few questions:
>>>> - is it too late to propose a new project idea for GSoC 2020?
>>>
>>> I don't think so. Students have until March 16 to submit a proposal,
>>> so they could still submit one based on this even if it's late.
>>
>> If I understand Google Summer of Code 2020 Timeline correctly
>> https://developers.google.com/open-source/gsoc/timeline
>> March 16 is the date when students might start to submit
>> proposals, and the deadline is March 20.
>
> Yeah, sorry about the confusion, the timeline says:
>
> March 16 18:00 UTC Student application period begins
> March 31 18:00 UTC Student application deadline
>
> So technically we could add ideas until March 31, but I think it makes
> no sense, especially as we ask students to submit proposals well in
> advance. So we should give ourselves March 16 as our actual deadline
> to add ideas.

>>>> - is it too difficult of a project for GSoC?
>>>
>>> I guess it depends on how much you as a mentor would help the student
>>> getting started.
>>>
>>> I think it's interesting and worth adding it anyway. Can you add it to
>>> SoC-2020-Ideas.md?
>>
>> All right, I'll do it.
>
> Great, thanks!

>> P.S. I wonder if Derrick Stolee would agree to be co-mentor (if he is
>> not too busy with working on Scalar).
>
> I am adding Heba in Cc as she said she would be ok to co-mentor. Emily
> and Jonathan T. might be interested too, so I'm adding them too.

>>>> I think it's interesting and worth adding it anyway. Can you add it to
>>>> SoC-2020-Ideas.md?
>>>
>>> All right, I'll do it.
>>
>> Great, thanks!
>
> Added with some modifications in commit 6b5edec6557
> https://github.com/git/git.github.io/commit/6b5edec6557930888441c626f9272dc2be0c769e

> Jakub Narebski <jnareb@gmail.com> writes:
>> Christian Couder <christian.couder@gmail.com> writes:
>>> On Wed, Mar 11, 2020 at 10:30 PM Jakub Narebski <jnareb@gmail.com> wrote:
> [...]
>>>>> I think it's interesting and worth adding it anyway. Can you add it to
>>>>> SoC-2020-Ideas.md?
>>>>
>>>> All right, I'll do it.
>>>
>>> Great, thanks!
>>
>> Added with some modifications in commit 6b5edec6557
>> https://github.com/git/git.github.io/commit/6b5edec6557930888441c626f9272dc2be0c769e
>
> And it failed to build.  Was it caused by accidentally deleting two
> trailing empty lines at the end of the file?
>
> page_build_id=168669405

> Hello,
>
> Here below is a possible proposal for a more difficult Google Summer of
> Code 2020 project.
>
> A few questions:
> - is it too late to propose a new project idea for GSoC 2020?
> - is it too difficult of a project for GSoC?
>
> Best,
>
>   Jakub Narębski
>
> --------------------------------------------------
>
> ### 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)'.

> 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]

>> ### 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.

>  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]).

> 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.

>> 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]

> 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,

> On 13/03/2020 14:34, Jakub Narebski wrote:
>> 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)'.
>
> So post(v) is the (increasing) number for the visited commits, starting
> with 1 at the initial branch tip (not root!), as the graph is traversed,
> depth first, with backtracking to the most recent commit that still has
> unvisited parents when either the root commit, or an already visited
> commit is found. (phew, that took a lot of words;-)

> potential orderings, based on alternate parental choices.
>
> abcdefgwxm
> abcdewxgfm
> abcmdefgwx
> abcmdewxgf
>
> All 4 orderings are equally valid implementations.(?)

>>> 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 'all' can be misunderstood as meaning 'skip' a commit if it has
> multiple parents, until the last visit. I don't think that's what is
> meant. (or is it?)

>>
>> 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).
>>
> I'm not sure I understood that. Is this the same as my comment above.

>>>  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.
>
> I'd agree that 'node' is ok, it's just the available values for 'v' that
> can be presumptuous.
> (i.e. the academics already labelling v->1..n, that often just happens
> to be the order they end up with:: `Given <type of graph> with nodes
> 1..n, then <some assertions based on n>` The PReaCH paper does that.)

> Hello, Philip
>
> Thank you for your continued interest in this topic.
>
> Philip Oakley <philipoakley@iee.email> writes:
>> On 13/03/2020 14:34, Jakub Narebski wrote:
>>> 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)'.
>> So post(v) is the (increasing) number for the visited commits, starting
>> with 1 at the initial branch tip (not root!), as the graph is traversed,
>> depth first, with backtracking to the most recent commit that still has
>> unvisited parents when either the root commit, or an already visited
>> commit is found. (phew, that took a lot of words;-)
> No, if we start at branch tip (source node), and number in the order of
> visiting during DFS traversal, with node numbered _before_ its out
> neighbours (parents in Git terms), that would be pre(v) numbering.

>> e.g. (with 'a' as a branch tip)
>>
>> a - b - c - d - e - f - g
>>          \m/     \w - x/         (m spans c-d;  w-x spans e-g)
> We usually order commits left-to-right, or bottom-to-top, with most
> recent commits and branch tips respectively on the far right, or on the
> top.  This is the reverse notation.

>
>> potential orderings, based on alternate parental choices.
>>
>> abcdefgwxm
>> abcdewxgfm
>> abcmdefgwx
>> abcmdewxgf
>>
>> All 4 orderings are equally valid implementations.(?)
> Yes, this is true.  There are various heuristics to select the best
> ordering, but as most of those require additional work to be done
> upfront (e.g. computing in-degrees, or topological sort, or generation
> numbers i.e. topological levels), we can start with simple rule: walk
> the graph in parents order.

>>>> 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 'all' can be misunderstood as meaning 'skip' a commit if it has
>> multiple parents, until the last visit. I don't think that's what is
>> meant. (or is it?)
> During the depth-first search (DFS) traversal of the commit graph we
> walk all reachable commits.  What I meant here is that the node (commit)
> gets it post(v) number only after all of its parents have been visited,
> and we backtracked to this commit.
>
> Again, I will refer to the frame 59/64 in v1.1 version of my slides:
>   https://drive.google.com/open?id=1psMBVfcRHcZeJ7AewGpdoymrEfFVdXoK
>
>>> 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).
>>>
>> I'm not sure I understood that. Is this the same as my comment above.
> What I wanted to say here, is that if you label commits with pre(v)
> number, that is number them in the order of visiting, commit before its
> parents, then we can use pre-max interval instead.  The interval would
> be [pre(v), max_{p \in parents(v)} pre(p)], and the positive-cut filter
> would work the same: if one interval is contained in the other, then
> there is path from one commit to the other.
>
>>>>  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.
>> I'd agree that 'node' is ok, it's just the available values for 'v' that
>> can be presumptuous.
>> (i.e. the academics already labelling v->1..n, that often just happens
>> to be the order they end up with:: `Given <type of graph> with nodes
>> 1..n, then <some assertions based on n>` The PReaCH paper does that.)
> No, in academics paper usually define graph as a set of vertices V and
> set of edges E.  Numbering vertices (nodes) is something extra.

>> Plus our DAGs are, in a sense, backward (only children know who their
>> parents are!), so all the counting levels feel wrong (we count edges
>> from the wrong end)
> No, our DAGs are not backward, only our terminology is different.
> On the other hand we cannot assume that we can get reverse graph
> easily (many graph reachability algorithms do assume that).
>
>   graph theory        |  git documentation     |  meaning
>   ------------------------------------------------------------------
>   roots               |  branch tips, heads    |  no incoming edges
>   leaves              |  root commits          |  no outgoing edges
>   children            |  parents               |  [out] neighbours

> Hello,
> 
> Here below is a possible proposal for a more difficult Google Summer of
> Code 2020 project.
> 
> A few questions:
> - is it too late to propose a new project idea for GSoC 2020?
> - is it too difficult of a project for GSoC?
> 
> Best,
> 
>   Jakub Narębski
> 
> --------------------------------------------------
> 
> ### 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)'.
> 
> 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

>> Here below is a possible proposal for a more difficult Google Summer of
>> Code 2020 project.
>> 
>> A few questions:
>> - is it too late to propose a new project idea for GSoC 2020?
>> - is it too difficult of a project for GSoC?
>> 
>> Best,
>> 
>>   Jakub Narębski

>> --------------------------------------------------
>> 
>> ### 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)'.
>> 
>> 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)
>
> I haven't thought too hard about it, but I'm assuming that if v is not
> in a commit-graph file, then post(v) would be "infinite" and min_graph(v)
> would be zero.

>> 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'
>
> How many places in Git do we ask "can v reach u?" and how many would
> return immediately without needing a walk in this new approach? My
> guess is that we will have a very narrow window where this query
> returns a positive result.

> I believe we discussed this concept briefly when planning "generation
> number v2" and the main concern I have with this plan is that the
> values are not stable. The value of post(v) and min_tree(v) depend
> on the entire graph as a whole, not just what is reachable from v
> (and preferably only the parents of v).
>
> Before starting to implement this, I would consider how such labels
> could be computed across incremental commit-graph boundaries. That is,
> if I'm only adding a layer of commits to the commit-graph without
> modifying the existing layers of the commit-graph chain, can I still
> compute values with these properties? How expensive is it? Do I need
> to walk the entire reachable set of commits?

>> 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
>
> Having such a complicated two-dimensional system would need to
> justify itself by being measurably faster than that one-dimensional
> system in these example commands.

>
> The point of generation number v2 [1] was to allow moving to "exact"
> algorithms for things like merge-base where we still use commit time
> as a heuristic, and could be wrong because of special data shapes.
> We don't use generation number in these examples because using only
> generation number can lead to a large increase in number of commits
> walked. The example we saw in the Linux kernel repository was a bug
> fix created on top of a very old commit, so there was a commit of
> low generation with very high commit-date that caused extra walking.
> (See [2] for a detailed description of the data shape.)
>
> My _prediction_ is that the two-dimensional system will be more
> complicated to write and use, and will not have any measurable
> difference. I'd be happy to be wrong, but I also would not send
> anyone down this direction only to find out I'm right and that
> effort was wasted.

>
> My recommendation is that a GSoC student update the
> generation number to "v2" based on the definition you made in [1].
> That proposal is also more likely to be effective in Git because
> it makes use of extra heuristic information (commit date) to
> assist the types of algorithms we care about.
>
> In that case, the "difficult" part is moving the "generation"
> member of struct commit into a slab before making it a 64-bit
> value. (This is likely necessary for your plan, anyway.) Updating
> the generation number to v2 is relatively straight-forward after
> that, as someone can follow all places that reference or compute
> generation numbers and apply a diff

> [1] https://lore.kernel.org/git/86o8ziatb2.fsf_-_@gmail.com/
>     [RFC/PATCH] commit-graph: generation v5 (backward compatible date ceiling)
>
> [2]
> https://lore.kernel.org/git/efa3720fb40638e5d61c6130b55e3348d8e4339e.1535633886.git.gitgitgadget@gmail.com/
>     [PATCH 1/1] commit: don't use generation numbers if not needed

> > We already have the second inequality (f(u) <= f(v)) where the function
> > 'f' is the generation of v. The success of this approach over generation
> > numbers relies entirely on how often the inequality min_graph(v) <= post(u)
> > fails when gen(u) <= gen(v) holds.
>
> True.  It may turn out that additional negative-cut filters do not bring
> enough performance improvements over topological levels or corrected
> commit date (or monotonically increasing corrected commit date) to be
> worth it.
>
> I think they can help in wide commit graphs (many concurrently developed
> branches with many commits and few merges), and when there is orphan
> branch (like 'todo' in the git.git, or 'gh-pages' for storing
> per-project GitHub Pages) that is somehow entangled in query.
>
> >> 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'
> >
> > How many places in Git do we ask "can v reach u?" and how many would
> > return immediately without needing a walk in this new approach? My
> > guess is that we will have a very narrow window where this query
> > returns a positive result.
>
> As I wrote below, such positive-cut filter would be directly helpful in
> performing the following commands:
>
>  - `git merge-base --is-ancestor`
>  - `git branch --contains`
>  - `git tag --contains`
>  - `git branch --merged`
>  - `git tag --merged`
>
> It would be also useful for tag autofollow in git-fetch; is is N-to-M
> equivalent to 1-to-N / N-to-1 `--contains` queries.
>
> I am quite sure that positive-cut filter would make `--ancestry-path`
> walk faster.
>
> I think, but I am not sure, that positive-cut filter can make parts of
> topological sort and merge base algorithms at least a tiny bit faster.

> > I believe we discussed this concept briefly when planning "generation
> > number v2" and the main concern I have with this plan is that the
> > values are not stable. The value of post(v) and min_tree(v) depend
> > on the entire graph as a whole, not just what is reachable from v
> > (and preferably only the parents of v).
> >
> > Before starting to implement this, I would consider how such labels
> > could be computed across incremental commit-graph boundaries. That is,
> > if I'm only adding a layer of commits to the commit-graph without
> > modifying the existing layers of the commit-graph chain, can I still
> > compute values with these properties? How expensive is it? Do I need
> > to walk the entire reachable set of commits?
>
> I think it would be possible to compute post(v) and min_tree(v) using
> incremental updates, and to make it compatibile with incremental
> commit-graph format (with the commit-graph chain).  But I have not
> proven it.

> > The point of generation number v2 [1] was to allow moving to "exact"
> > algorithms for things like merge-base where we still use commit time
> > as a heuristic, and could be wrong because of special data shapes.
> > We don't use generation number in these examples because using only
> > generation number can lead to a large increase in number of commits
> > walked. The example we saw in the Linux kernel repository was a bug
> > fix created on top of a very old commit, so there was a commit of
> > low generation with very high commit-date that caused extra walking.
> > (See [2] for a detailed description of the data shape.)
> >
> > My _prediction_ is that the two-dimensional system will be more
> > complicated to write and use, and will not have any measurable
> > difference. I'd be happy to be wrong, but I also would not send
> > anyone down this direction only to find out I'm right and that
> > effort was wasted.
>
> That might be a problem.
>
> This is a bit of a "moonshot" / research project, moreso than others.
> Though it would be still valuable, in my opionion, even if the code
> wouldn't ultimately get merged and added into Git.

> > My recommendation is that a GSoC student update the
> > generation number to "v2" based on the definition you made in [1].
> > That proposal is also more likely to be effective in Git because
> > it makes use of extra heuristic information (commit date) to
> > assist the types of algorithms we care about.
> >
> > In that case, the "difficult" part is moving the "generation"
> > member of struct commit into a slab before making it a 64-bit
> > value. (This is likely necessary for your plan, anyway.) Updating
> > the generation number to v2 is relatively straight-forward after
> > that, as someone can follow all places that reference or compute
> > generation numbers and apply a diff
>
> Good idea!  Though I am not sure if it is not too late to add it to the
> https://git.github.io/SoC-2020-Ideas/ as the self imposed deadline of
> March 16 (where students can start submitting proposals to GSoC) has
> just passed.  Christian, what do you think?

> On Tue, Mar 17, 2020 at 4:13 AM Jakub Narebski <jnareb@gmail.com> wrote:
> It could be part of your research project though, to check if that
> approach is better or good enough compared to what you suggest in the
> current version of your project.
> 
>> Would you agree, Stolee, to be a _possible_ mentor or co-mentor for
>> "Generation number v2" project?
> 
> At this point I think it might be best if you are both willing to
> co-mentor a "moonshot" / research project to find what is the best way
> forward by bench-marking the different approaches that you both
> suggest for different commands/use cases.

> On Tue, Mar 17, 2020 at 4:13 AM Jakub Narebski <jnareb@gmail.com> wrote:
>
> [...]
>
>>>> ### Graph labelling for speeding up git commands
>
> [...]
>
>>> We already have the second inequality (f(u) <= f(v)) where the function
>>> 'f' is the generation of v. The success of this approach over generation
>>> numbers relies entirely on how often the inequality min_graph(v) <= post(u)
>>> fails when gen(u) <= gen(v) holds.
>>
>> True.  It may turn out that additional negative-cut filters do not bring
>> enough performance improvements over topological levels or corrected
>> commit date (or monotonically increasing corrected commit date) to be
>> worth it.
>>
>> I think they can help in wide commit graphs (many concurrently developed
>> branches with many commits and few merges), and when there is orphan
>> branch (like 'todo' in the git.git, or 'gh-pages' for storing
>> per-project GitHub Pages) that is somehow entangled in query.
>>
>>>> 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'
>>>
>>> How many places in Git do we ask "can v reach u?" and how many would
>>> return immediately without needing a walk in this new approach? My
>>> guess is that we will have a very narrow window where this query
>>> returns a positive result.
>>
>> As I wrote below, such positive-cut filter would be directly helpful in
>> performing the following commands:
>>
>>  - `git merge-base --is-ancestor`
>>  - `git branch --contains`
>>  - `git tag --contains`
>>  - `git branch --merged`
>>  - `git tag --merged`
>>
>> It would be also useful for tag autofollow in git-fetch; is is N-to-M
>> equivalent to 1-to-N / N-to-1 `--contains` queries.
>>
>> I am quite sure that positive-cut filter would make `--ancestry-path`
>> walk faster.
>>
>> I think, but I am not sure, that positive-cut filter can make parts of
>> topological sort and merge base algorithms at least a tiny bit faster.
>
> Is there an easy way to check that it would provide significant
> performance improvements at least in some cases? Can we ask the
> student to do that at the beginning of the GSoC?

>>> I believe we discussed this concept briefly when planning "generation
>>> number v2" and the main concern I have with this plan is that the
>>> values are not stable. The value of post(v) and min_tree(v) depend
>>> on the entire graph as a whole, not just what is reachable from v
>>> (and preferably only the parents of v).
>>>
>>> Before starting to implement this, I would consider how such labels
>>> could be computed across incremental commit-graph boundaries. That is,
>>> if I'm only adding a layer of commits to the commit-graph without
>>> modifying the existing layers of the commit-graph chain, can I still
>>> compute values with these properties? How expensive is it? Do I need
>>> to walk the entire reachable set of commits?
>>
>> I think it would be possible to compute post(v) and min_tree(v) using
>> incremental updates, and to make it compatibile with incremental
>> commit-graph format (with the commit-graph chain).  But I have not
>> proven it.
>
> Would it be difficult to prove? What would be required? And again can
> we ask the student to do that at the beginning of the GSoC?

> [...]
>
>>> The point of generation number v2 [1] was to allow moving to "exact"
>>> algorithms for things like merge-base where we still use commit time
>>> as a heuristic, and could be wrong because of special data shapes.
>>> We don't use generation number in these examples because using only
>>> generation number can lead to a large increase in number of commits
>>> walked. The example we saw in the Linux kernel repository was a bug
>>> fix created on top of a very old commit, so there was a commit of
>>> low generation with very high commit-date that caused extra walking.
>>> (See [2] for a detailed description of the data shape.)
>>>
>>> My _prediction_ is that the two-dimensional system will be more
>>> complicated to write and use, and will not have any measurable
>>> difference. I'd be happy to be wrong, but I also would not send
>>> anyone down this direction only to find out I'm right and that
>>> effort was wasted.
>>
>> That might be a problem.
>>
>> This is a bit of a "moonshot" / research project, moreso than others.
>> Though it would be still valuable, in my opionion, even if the code
>> wouldn't ultimately get merged and added into Git.
>
> I agree that it feels like a "moonshot" / research project.
>
>>> My recommendation is that a GSoC student update the
>>> generation number to "v2" based on the definition you made in [1].
>>> That proposal is also more likely to be effective in Git because
>>> it makes use of extra heuristic information (commit date) to
>>> assist the types of algorithms we care about.
>>>
>>> In that case, the "difficult" part is moving the "generation"
>>> member of struct commit into a slab before making it a 64-bit
>>> value. (This is likely necessary for your plan, anyway.) Updating
>>> the generation number to v2 is relatively straight-forward after
>>> that, as someone can follow all places that reference or compute
>>> generation numbers and apply a diff
>>
>> Good idea!  Though I am not sure if it is not too late to add it to the
>> https://git.github.io/SoC-2020-Ideas/ as the self imposed deadline of
>> March 16 (where students can start submitting proposals to GSoC) has
>> just passed.  Christian, what do you think?
>
> Would that be a different project idea or part of your "Graph labeling
> for speeding up git commands" project idea?
>
> I am very reluctant to add new project ideas at that time. I don't
> think student will have time to properly research it and get it
> reviewed.
>
> It could be part of your research project though, to check if that
> approach is better or good enough compared to what you suggest in the
> current version of your project.
>
>> Would you agree, Stolee, to be a _possible_ mentor or co-mentor for
>> "Generation number v2" project?
>
> At this point I think it might be best if you are both willing to
> co-mentor a "moonshot" / research project to find what is the best way
> forward by bench-marking the different approaches that you both
> suggest for different commands/use cases.

> >>>> 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'
> >>>
> >>> How many places in Git do we ask "can v reach u?" and how many would
> >>> return immediately without needing a walk in this new approach? My
> >>> guess is that we will have a very narrow window where this query
> >>> returns a positive result.
> >>
> >> As I wrote below, such positive-cut filter would be directly helpful in
> >> performing the following commands:
> >>
> >>  - `git merge-base --is-ancestor`
> >>  - `git branch --contains`
> >>  - `git tag --contains`
> >>  - `git branch --merged`
> >>  - `git tag --merged`
> >>
> >> It would be also useful for tag autofollow in git-fetch; is is N-to-M
> >> equivalent to 1-to-N / N-to-1 `--contains` queries.
> >>
> >> I am quite sure that positive-cut filter would make `--ancestry-path`
> >> walk faster.
> >>
> >> I think, but I am not sure, that positive-cut filter can make parts of
> >> topological sort and merge base algorithms at least a tiny bit faster.
> >
> > Is there an easy way to check that it would provide significant
> > performance improvements at least in some cases? Can we ask the
> > student to do that at the beginning of the GSoC?
>
> The "Reachability labels for version control graphs.ipynb" Jupyter
> Notebook on Google Colaboratory was created to answer this question
> (originally for the FELINE reachability index).  Among others it can
> min-post interval labels and topological levels (generation numbers),
> use them for reachability queries, and load Linux kernel
> commit-graph. The exploration didn't get finished, but it would be not
> that difficult, I think, to at least find the amount of false negatives
> for min-post interval labeling for git.git or Linux kernel repo.
>
>   https://colab.research.google.com/drive/1V-U7_slu5Z3s5iEEMFKhLXtaxSu5xyzg
>
> As Jupyter Notebook, it is run in the web browser.  It can either use
> local runtime, or run on Google Cloud runtime.  On the other hand it
> requires at least some knowledge of Python...

> >> I think it would be possible to compute post(v) and min_tree(v) using
> >> incremental updates, and to make it compatibile with incremental
> >> commit-graph format (with the commit-graph chain).  But I have not
> >> proven it.
> >
> > Would it be difficult to prove? What would be required? And again can
> > we ask the student to do that at the beginning of the GSoC?
>
> Formal mathematical proof by induction would be not that difficult.  The
> problem is, I think, in finding all possible classes of initial spanning
> forest arrangements, and all possible classes of commit-graph growth by
> one commit -- and examining how this affect the spanning forest.

> >>> The point of generation number v2 [1] was to allow moving to "exact"
> >>> algorithms for things like merge-base where we still use commit time
> >>> as a heuristic, and could be wrong because of special data shapes.
> >>> We don't use generation number in these examples because using only
> >>> generation number can lead to a large increase in number of commits
> >>> walked. The example we saw in the Linux kernel repository was a bug
> >>> fix created on top of a very old commit, so there was a commit of
> >>> low generation with very high commit-date that caused extra walking.
> >>> (See [2] for a detailed description of the data shape.)
> >>>
> >>> My _prediction_ is that the two-dimensional system will be more
> >>> complicated to write and use, and will not have any measurable
> >>> difference. I'd be happy to be wrong, but I also would not send
> >>> anyone down this direction only to find out I'm right and that
> >>> effort was wasted.
> >>
> >> That might be a problem.
> >>
> >> This is a bit of a "moonshot" / research project, moreso than others.
> >> Though it would be still valuable, in my opionion, even if the code
> >> wouldn't ultimately get merged and added into Git.
> >
> > I agree that it feels like a "moonshot" / research project.
> >
> >>> My recommendation is that a GSoC student update the
> >>> generation number to "v2" based on the definition you made in [1].
> >>> That proposal is also more likely to be effective in Git because
> >>> it makes use of extra heuristic information (commit date) to
> >>> assist the types of algorithms we care about.
> >>>
> >>> In that case, the "difficult" part is moving the "generation"
> >>> member of struct commit into a slab before making it a 64-bit
> >>> value. (This is likely necessary for your plan, anyway.) Updating
> >>> the generation number to v2 is relatively straight-forward after
> >>> that, as someone can follow all places that reference or compute
> >>> generation numbers and apply a diff
> >>
> >> Good idea!  Though I am not sure if it is not too late to add it to the
> >> https://git.github.io/SoC-2020-Ideas/ as the self imposed deadline of
> >> March 16 (where students can start submitting proposals to GSoC) has
> >> just passed.  Christian, what do you think?
> >
> > Would that be a different project idea or part of your "Graph labeling
> > for speeding up git commands" project idea?
> >
> > I am very reluctant to add new project ideas at that time. I don't
> > think student will have time to properly research it and get it
> > reviewed.
> >
> > It could be part of your research project though, to check if that
> > approach is better or good enough compared to what you suggest in the
> > current version of your project.
> >
> >> Would you agree, Stolee, to be a _possible_ mentor or co-mentor for
> >> "Generation number v2" project?
> >
> > At this point I think it might be best if you are both willing to
> > co-mentor a "moonshot" / research project to find what is the best way
> > forward by bench-marking the different approaches that you both
> > suggest for different commands/use cases.
>
> So perhaps we should expand "Commit graph labeling for speeding up git
> commands" idea, splitting it into two possible ways of working in this
> project: the more technical 'Generation number v2', and 'Interval labels
> for commit graph' which is more of research project?

>>>> As I wrote below, such positive-cut filter would be directly helpful in
>>>> performing the following commands:
>>>>
>>>>  - `git merge-base --is-ancestor`
>>>>  - `git branch --contains`
>>>>  - `git tag --contains`
>>>>  - `git branch --merged`
>>>>  - `git tag --merged`
>>>>
>>>> It would be also useful for tag autofollow in git-fetch; is is N-to-M
>>>> equivalent to 1-to-N / N-to-1 `--contains` queries.
>>>>
>>>> I am quite sure that positive-cut filter would make `--ancestry-path`
>>>> walk faster.
>>>>
>>>> I think, but I am not sure, that positive-cut filter can make parts of
>>>> topological sort and merge base algorithms at least a tiny bit faster.
>>>
>>> Is there an easy way to check that it would provide significant
>>> performance improvements at least in some cases? Can we ask the
>>> student to do that at the beginning of the GSoC?
>>
>> The "Reachability labels for version control graphs.ipynb" Jupyter
>> Notebook on Google Colaboratory was created to answer this question
>> (originally for the FELINE reachability index).  Among others it can
>> min-post interval labels and topological levels (generation numbers),
>> use them for reachability queries, and load Linux kernel
>> commit-graph. The exploration didn't get finished, but it would be not
>> that difficult, I think, to at least find the amount of false negatives
>> for min-post interval labeling for git.git or Linux kernel repo.
>>
>>   https://colab.research.google.com/drive/1V-U7_slu5Z3s5iEEMFKhLXtaxSu5xyzg
>>
>> As Jupyter Notebook, it is run in the web browser.  It can either use
>> local runtime, or run on Google Cloud runtime.  On the other hand it
>> requires at least some knowledge of Python...
>
> Ok, if that's a possible approach to the project, then please add it
> to the description.

>>>>> My recommendation is that a GSoC student update the
>>>>> generation number to "v2" based on the definition you made in [1].
>>>>> That proposal is also more likely to be effective in Git because
>>>>> it makes use of extra heuristic information (commit date) to
>>>>> assist the types of algorithms we care about.
>>>>>
>>>>> In that case, the "difficult" part is moving the "generation"
>>>>> member of struct commit into a slab before making it a 64-bit
>>>>> value. (This is likely necessary for your plan, anyway.) Updating
>>>>> the generation number to v2 is relatively straight-forward after
>>>>> that, as someone can follow all places that reference or compute
>>>>> generation numbers and apply a diff
>>>>
>>>> Good idea!  Though I am not sure if it is not too late to add it to the
>>>> https://git.github.io/SoC-2020-Ideas/ as the self imposed deadline of
>>>> March 16 (where students can start submitting proposals to GSoC) has
>>>> just passed.  Christian, what do you think?
>>>
>>> Would that be a different project idea or part of your "Graph labeling
>>> for speeding up git commands" project idea?
>>>
>>> I am very reluctant to add new project ideas at that time. I don't
>>> think student will have time to properly research it and get it
>>> reviewed.

>> So perhaps we should expand "Commit graph labeling for speeding up git
>> commands" idea, splitting it into two possible ways of working in this
>> project: the more technical 'Generation number v2', and 'Interval labels
>> for commit graph' which is more of research project?
>
> Ok for that.
>
>>  Which should be
>> put first, then?
>
> Which ever you prefer. If you say that any part could be done
> separately, that doesn't matter much.

> I have added 'Generation number v2' as one of alternative ways of
> working on the more generic "Commit graph labeling for speeding up git
> commands" idea -- as first task, because it fit better the narrative:
> https://github.com/git/git.github.io/commit/a6d59820709417081c334a5120342987ff046f1a
> 
> Could you (or Stolee) check current proposal, so that it can be merged
> in?  Thanks in advance.
> 
>   https://github.com/git/git.github.io/blob/soc-2020-idea-jnareb/SoC-2020-Ideas.md

>> I have added 'Generation number v2' as one of alternative ways of
>> working on the more generic "Commit graph labeling for speeding up git
>> commands" idea -- as first task, because it fit better the narrative:
>> https://github.com/git/git.github.io/commit/a6d59820709417081c334a5120342987ff046f1a
>> 
>> Could you (or Stolee) check current proposal, so that it can be merged
>> in?  Thanks in advance.
>> 
>>   https://github.com/git/git.github.io/blob/soc-2020-idea-jnareb/SoC-2020-Ideas.md
>
> Thanks for the updated write-up. I think the narrative is helpful, describing how
> we landed on the definition of "generation number v2" before going into the interval
> methods.
>
> The only comment I have is about this statement at the end, which seems to be a
> carry-over from your perspective of wanting intervals instead of v2:
>
> 	Before starting on this task, at the beginning of the GSoC, it might be
> 	[a (sic)] good idea to check that interval labels would provide significant
> 	performance improvements at least in some cases (and if it is not the case,
> 	switch to working on generation numbers v2).
>
> The final parenthetical (switch to working on...) is a bit presumptive. Instead,
> please recommend an exploration period to determine which methods have which
> performance improvements using prototypes and/or the Python notebook. I'm usually
> of the opinion that a prototype is more informative as it compares the results in
> context, and the student would learn about the code that needs to change before
> creating review-quality patches.