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/[email protected]/t/>

Quoted 6 lines · Jakub Narebski

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

Quoted 3 lines

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

Quoted 41 lines

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:

Quoted 8 lines

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/[email protected]/t/>

Cc Stolee, Heba, Jonathan T., Emily Shaffer.

Quoted 1 line · Junio C Hamano

Jakub Narebski <[email protected]> writes:

Quoted 9 lines

Quoted 5 lines

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

Or I could try to make this information into blog post -- this topic would really gain from using images (like Derrick Stolee series of articles on commit-graph).

Quoted 9 lines · Jakub Narebski

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

Quoted 4 lines

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.

Quoted 16 lines · Jakub Narebski

Quoted 9 lines · Jakub Narebski

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

Quoted 6 lines

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?

- is it too difficult of a project for GSoC?

Quoted 6 lines · Jakub Narebski

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.

Quoted 1 line

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

Quoted 5 lines

Quoted 2 lines

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.

Quoted 7 lines

Quoted 1 line

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

P.S. I wonder if Derrick Stolee would agree to be co-mentor (if he is not too busy with working on Scalar).

Quoted 10 lines · Jakub Narebski

Quoted 5 lines

Quoted 2 lines

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.

Quoted 9 lines

Quoted 7 lines

Quoted 1 line

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

Quoted 2 lines

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.

Quoted 1 line · Christian Couder

On Wed, Mar 11, 2020 at 10:30 PM Jakub Narebski <[email protected]> wrote:

Quoted 6 lines

Quoted 4 lines

Quoted 2 lines

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

Quoted 2 lines · Jakub Narebski

Quoted 1 line · Christian Couder

On Wed, Mar 11, 2020 at 10:30 PM Jakub Narebski <[email protected]> wrote:

[...]

Quoted 7 lines

Quoted 6 lines

Quoted 4 lines

Quoted 2 lines

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!

Quoted 2 lines

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/[email protected]/t/> [5]

On 10/03/2020 14:50, Jakub Narebski wrote:

Quoted 11 lines

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

Quoted 5 lines

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.

The Wikipedia article on contraction hierarchies [6] did give some useful clues for more lay readers.

Quoted 36 lines

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>

Quoted 3 lines

See also discussion in:

<https://public-inbox.org/git/[email protected]/t/> [5]

[6] https://en.wikipedia.org/wiki/Contraction_hierarchies

[I've been off-list for 2+ ,months, so still catching up]

Hello Philip,

Quoted 1 line · Philip Oakley

On 10/03/2020 14:50, Jakub Narebski wrote:

[...]

Quoted 15 lines

Quoted 15 lines

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

Quoted 3 lines

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

Quoted 7 lines

 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)

Quoted 7 lines

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.

Quoted 3 lines

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.

Quoted 36 lines

Quoted 36 lines

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>

Quoted 6 lines

Quoted 3 lines

See also discussion in:

<https://public-inbox.org/git/[email protected]/t/> [5]

[6] https://en.wikipedia.org/wiki/Contraction_hierarchies

[I've been off-list for 2+ ,months, so still catching up]

Best,

Quoted 14 lines · Jakub Narebski

Quoted 1 line · Philip Oakley

On 10/03/2020 14:50, Jakub Narebski wrote:

[...]

Quoted 11 lines

Quoted 11 lines

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

Quoted 4 lines

Quoted 4 lines

Quoted 4 lines

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;-)

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)

potential orderings, based on alternate parental choices.

abcdefgwxm
abcdewxgfm
abcmdefgwx
abcmdewxgf

All 4 orderings are equally valid implementations.(?)

Quoted 4 lines

Quoted 4 lines

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.

Quoted 4 lines

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?)

Quoted 6 lines

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.

Quoted 31 lines

Quoted 6 lines

 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)

Quoted 7 lines

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.

Quoted 2 lines

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

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)

Hello, Philip

Thank you for your continued interest in this topic.

Quoted 19 lines · Philip Oakley

Quoted 18 lines · Jakub Narebski

Quoted 1 line · Philip Oakley

On 10/03/2020 14:50, Jakub Narebski wrote:

[...]

Quoted 15 lines

Quoted 15 lines

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

Quoted 5 lines

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.

For post(v) you number nodes (commits) in the order of backtracking, that is with 1 at some parentless root commit, not 1 at some branch tip. This can be done e.g. during computing of generation numbers.

An example of such post(v) labeling can be found on slides 57-58/64 and 59/64 in v1.1 version of my slides:
https://drive.google.com/open?id=1psMBVfcRHcZeJ7AewGpdoymrEfFVdXoK

Quoted 4 lines

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.

Quoted 8 lines

potential orderings, based on alternate parental choices.

abcdefgwxm
abcdewxgfm
abcmdefgwx
abcmdewxgf

Quoted 1 line

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.

Quoted 11 lines

Quoted 8 lines

Quoted 4 lines

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

Quoted 6 lines

Quoted 5 lines

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.

Quoted 31 lines

Quoted 31 lines

Quoted 6 lines

 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)

Quoted 7 lines

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.

Quoted 5 lines

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.

Quoted 3 lines

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

Best,

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

Quoted 3 lines · Jakub Narebski

Here below is a possible proposal for a more difficult Google Summer of Code 2020 project.

Quoted 7 lines

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

Quoted 23 lines

--------------------------------------------------

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

Quoted 1 line

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.

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.

Quoted 7 lines

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:

Quoted 1 line

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?

Quoted 5 lines

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:

Quoted 7 lines

- 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/[email protected]/
[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

Quoted 1 line

Quoted 1 line

### Graph labelling for speeding up git commands

Quoted 4 lines

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.

Quoted 7 lines

Quoted 7 lines

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:

Quoted 6 lines

Quoted 1 line

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.

Quoted 6 lines

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

Quoted 6 lines

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.

Quoted 10 lines

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

Quoted 5 lines

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.

Quoted 6 lines

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.

Quoted 6 lines

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 you agree, Stolee, to be a _possible_ mentor or co-mentor for "Generation number v2" project?

On Tue, Mar 17, 2020 at 4:13 AM Jakub Narebski <[email protected]> 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.

Quoted 2 lines

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 <[email protected]> wrote:

[...]

Quoted 1 line

Quoted 1 line

Quoted 1 line

### Graph labelling for speeding up git commands

[...]

Quoted 44 lines

Quoted 4 lines

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.

Quoted 7 lines

Quoted 7 lines

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:

Quoted 6 lines

Quoted 1 line

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.

Quoted 2 lines

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?

Quoted 13 lines

Quoted 12 lines

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?

Quoted 4 lines

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?

[...]

Quoted 16 lines

Quoted 10 lines

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

Quoted 5 lines

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.

Quoted 5 lines

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.

Quoted 13 lines

Quoted 6 lines

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.

Quoted 6 lines

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

Quoted 4 lines

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.

Quoted 2 lines

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.

Quoted 31 lines · Christian Couder

Quoted 29 lines · Jakub Narebski

Quoted 7 lines

Quoted 7 lines

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:

Quoted 6 lines

Quoted 1 line

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.

Quoted 6 lines

Quoted 2 lines

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

Quoted 5 lines

Quoted 4 lines

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.

Quoted 2 lines

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.

Quoted 53 lines

Quoted 16 lines

Quoted 10 lines

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

Quoted 5 lines

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.

Quoted 5 lines

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.

Quoted 13 lines

Quoted 6 lines

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.

Quoted 6 lines

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

Quoted 4 lines

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.

Quoted 7 lines

Quoted 2 lines

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?

Which should be
put first, then?

Quoted 2 lines · Jakub Narebski

Quoted 1 line · Christian Couder

On Tue, Mar 17, 2020 at 4:13 AM Jakub Narebski <[email protected]> wrote:

Quoted 31 lines

Quoted 15 lines

Quoted 15 lines

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.

Quoted 6 lines

Quoted 2 lines

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.

Quoted 5 lines

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.

Quoted 24 lines

Quoted 24 lines

Quoted 13 lines

Quoted 6 lines

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.

Quoted 6 lines

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

Quoted 4 lines

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.

Quoted 4 lines

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.

Quoted 2 lines

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

Quoted 9 lines · Jakub Narebski

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.