{"thread":{"id":"52965","subject":"[RFC] Possible idea for GSoC 2020","startedAt":"2020-03-10T14:50:38Z","lastAt":"2020-03-19T12:52:24Z","messageCount":27,"participants":["Jakub Narebski","Junio C Hamano","Christian Couder","Philip Oakley","Derrick Stolee","Kaartic Sivaraam"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"392998","messageId":"86mu8o8dsf.fsf@gmail.com","threadId":"52965","inReplyTo":null,"subject":"[RFC] Possible idea for GSoC 2020","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2020-03-10T14:50:24Z","receivedAt":"2020-03-10T14:50:38Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Hello,\n\nHere below is a possible proposal for a more difficult Google Summer of\nCode 2020 project.\n\nA few questions:\n- is it too late to propose a new project idea for GSoC 2020?\n- is it too difficult of a project for GSoC?\n\nBest,\n\n Jakub Narębski\n\n--------------------------------------------------\n\n### Graph labelling for speeding up git commands\n\n - Language: C\n - Difficulty: hard / difficult\n - Possible mentors: Jakub Narębski\n\nGit uses various clever methods for making operations on very large\nrepositories faster, from bitmap indices for git-fetch[1], to generation\nnumbers (also known as topological levels) in the commit-graph file for\ncommit graph traversal operations like `git log --graph`[2].\n\nOne possible improvement that can make Git even faster is using min-post\nintervals labelling. The basis of this labelling is post-visit order of\na depth-first search traversal tree of a commit graph, let's call it\n'post(v)'.\n\nIf for each commit 'v' we would compute and store in the commit-graph\nfile two numbers: 'post(v)' and the minimum of 'post(u)' for all commits\nreachable from 'v', let's call the latter 'min_graph(v)', then the\nfollowing condition is true:\n\n if 'v' can reach 'u', then min_graph(v) <= post(u) <= post(v)\n\nIf for each commit 'v' we would compute and store in the commit-graph\nfile two numbers: 'post(v)' and the minimum of 'post(u)' for commits\nthat were visited during the part of depth-first search that started\nfrom 'v' (which is the minimum of post-order number for subtree of a\nspanning tree that starts at 'v'). Let's call the later 'min_tree(v)'.\nThen the following condition is true:\n\n if min_tree(v) <= post(u) <= post(v), then 'v' can reach 'u'\n\nThe task would be to implement computing such labelling (or a more\ninvolved variant of it[3][4]), storing it in commit-graph file, and\nusing it for speeding up git commands (starting from a single chosen\ncommand) such as:\n\n - git merge-base --is-ancestor A B\n - git branch --contains A\n - git tag --contains A\n - git branch --merged A\n - git tag --merged A\n - git merge-base --all A B\n - git log --topo-sort\n\nReferences:\n\n1. \n2. \n3. \n4. \n\nSee also discussion in:\n\n\n"},{"id":"393069","messageId":"xmqqo8t2hfxj.fsf@gitster.c.googlers.com","threadId":"52965","inReplyTo":"86mu8o8dsf.fsf@gmail.com","subject":"Re: [RFC] Possible idea for GSoC 2020","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-03-11T19:03:52Z","receivedAt":"2020-03-11T19:04:00Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jakub Narebski writes:\n\n> A few questions:\n> - is it too late to propose a new project idea for GSoC 2020?\n> - is it too difficult of a project for GSoC?\n> ...\n> ### Graph labelling for speeding up git commands\n>\n> - Language: C\n> - Difficulty: hard / difficult\n> - Possible mentors: Jakub Narębski\n\nI am not running the GSoC or participating in it in any way other\nthan just being a reviewer-maintainer of the project, but I would\nappreciate a well-thought-out write-up very much.\n\n> Git uses various clever methods for making operations on very large\n> repositories faster, from bitmap indices for git-fetch[1], to generation\n> numbers (also known as topological levels) in the commit-graph file for\n> commit graph traversal operations like `git log --graph`[2].\n>\n> One possible improvement that can make Git even faster is using min-post\n> intervals labelling. The basis of this labelling is post-visit order of\n> a depth-first search traversal tree of a commit graph, let's call it\n> 'post(v)'.\n>\n> If for each commit 'v' we would compute and store in the commit-graph\n> file two numbers: 'post(v)' and the minimum of 'post(u)' for all commits\n> reachable from 'v', let's call the latter 'min_graph(v)', then the\n> following condition is true:\n>\n> if 'v' can reach 'u', then min_graph(v) <= post(u) <= post(v)\n>\n> If for each commit 'v' we would compute and store in the commit-graph\n> file two numbers: 'post(v)' and the minimum of 'post(u)' for commits\n> that were visited during the part of depth-first search that started\n> from 'v' (which is the minimum of post-order number for subtree of a\n> spanning tree that starts at 'v'). Let's call the later 'min_tree(v)'.\n> Then the following condition is true:\n>\n> if min_tree(v) <= post(u) <= post(v), then 'v' can reach 'u'\n>\n> The task would be to implement computing such labelling (or a more\n> involved variant of it[3][4]), storing it in commit-graph file, and\n> using it for speeding up git commands (starting from a single chosen\n> command) such as:\n>\n> - git merge-base --is-ancestor A B\n> - git branch --contains A\n> - git tag --contains A\n> - git branch --merged A\n> - git tag --merged A\n> - git merge-base --all A B\n> - git log --topo-sort\n>\n> References:\n>\n> 1. \n> 2. \n> 3. \n> 4. \n>\n> See also discussion in:\n>\n> \n"},{"id":"393092","messageId":"CAP8UFD31+sK5zyLLgkOvJ4fj=PC3FTa9nXcpPeM-fWm9ByoKjQ@mail.gmail.com","threadId":"52965","inReplyTo":"86mu8o8dsf.fsf@gmail.com","subject":"Re: [RFC] Possible idea for GSoC 2020","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2020-03-11T20:29:28Z","receivedAt":"2020-03-11T20:29:43Z","isPatch":false,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"Hi,\n\nOn Tue, Mar 10, 2020 at 3:50 PM Jakub Narebski wrote:\n>\n> Hello,\n>\n> Here below is a possible proposal for a more difficult Google Summer of\n> Code 2020 project.\n>\n> A few questions:\n> - is it too late to propose a new project idea for GSoC 2020?\n\nI don't think so. Students have until March 16 to submit a proposal,\nso they could still submit one based on this even if it's late.\n\n> - is it too difficult of a project for GSoC?\n\nI guess it depends on how much you as a mentor would help the student\ngetting started.\n\nI think it's interesting and worth adding it anyway. Can you add it to\nSoC-2020-Ideas.md?\n\nThanks for the idea,\nChristian.\n"},{"id":"393096","messageId":"86eety4m1m.fsf@gmail.com","threadId":"52965","inReplyTo":"CAP8UFD31+sK5zyLLgkOvJ4fj=PC3FTa9nXcpPeM-fWm9ByoKjQ@mail.gmail.com","subject":"Re: [RFC] Possible idea for GSoC 2020","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2020-03-11T21:30:13Z","receivedAt":"2020-03-11T21:30:20Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Hi,\n\nChristian Couder writes:\n> On Tue, Mar 10, 2020 at 3:50 PM Jakub Narebski wrote:\n>>\n>> Here below is a possible proposal for a more difficult Google Summer of\n>> Code 2020 project.\n>>\n>> A few questions:\n>> - is it too late to propose a new project idea for GSoC 2020?\n>\n> I don't think so. Students have until March 16 to submit a proposal,\n> so they could still submit one based on this even if it's late.\n\nIf I understand Google Summer of Code 2020 Timeline correctly\nhttps://developers.google.com/open-source/gsoc/timeline\nMarch 16 is the date when students might start to submit\nproposals, and the deadline is March 20.\n\n>> - is it too difficult of a project for GSoC?\n>\n> I guess it depends on how much you as a mentor would help the student\n> getting started.\n>\n> I think it's interesting and worth adding it anyway. Can you add it to\n> SoC-2020-Ideas.md?\n\nAll right, I'll do it.\n\n\nP.S. I wonder if Derrick Stolee would agree to be co-mentor (if he is\nnot too busy with working on Scalar).\n\nBest,\n-- \nJakub Narębski\n"},{"id":"393097","messageId":"CAP8UFD0cLrxic6tjGC5UQjX1pNHBzZhVyoddWbhETReFaLK4nw@mail.gmail.com","threadId":"52965","inReplyTo":"86eety4m1m.fsf@gmail.com","subject":"Re: [RFC] Possible idea for GSoC 2020","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2020-03-11T21:48:23Z","receivedAt":"2020-03-11T21:48:39Z","isPatch":false,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"On Wed, Mar 11, 2020 at 10:30 PM Jakub Narebski wrote:\n\n> >> A few questions:\n> >> - is it too late to propose a new project idea for GSoC 2020?\n> >\n> > I don't think so. Students have until March 16 to submit a proposal,\n> > so they could still submit one based on this even if it's late.\n>\n> If I understand Google Summer of Code 2020 Timeline correctly\n> https://developers.google.com/open-source/gsoc/timeline\n> March 16 is the date when students might start to submit\n> proposals, and the deadline is March 20.\n\nYeah, sorry about the confusion, the timeline says:\n\nMarch 16 18:00 UTC Student application period begins\nMarch 31 18:00 UTC Student application deadline\n\nSo technically we could add ideas until March 31, but I think it makes\nno sense, especially as we ask students to submit proposals well in\nadvance. So we should give ourselves March 16 as our actual deadline\nto add ideas.\n\n> >> - is it too difficult of a project for GSoC?\n> >\n> > I guess it depends on how much you as a mentor would help the student\n> > getting started.\n> >\n> > I think it's interesting and worth adding it anyway. Can you add it to\n> > SoC-2020-Ideas.md?\n>\n> All right, I'll do it.\n\nGreat, thanks!\n\n> P.S. I wonder if Derrick Stolee would agree to be co-mentor (if he is\n> not too busy with working on Scalar).\n\nI am adding Heba in Cc as she said she would be ok to co-mentor. Emily\nand Jonathan T. might be interested too, so I'm adding them too.\n"},{"id":"393122","messageId":"868sk54vj9.fsf@gmail.com","threadId":"52965","inReplyTo":"CAP8UFD0cLrxic6tjGC5UQjX1pNHBzZhVyoddWbhETReFaLK4nw@mail.gmail.com","subject":"Re: [RFC] Possible idea for GSoC 2020","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2020-03-12T12:17:30Z","receivedAt":"2020-03-12T12:17:37Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Hello,\n\nChristian Couder writes:\n> On Wed, Mar 11, 2020 at 10:30 PM Jakub Narebski wrote:\n>\n>>>> A few questions:\n>>>> - is it too late to propose a new project idea for GSoC 2020?\n>>>\n>>> I don't think so. Students have until March 16 to submit a proposal,\n>>> so they could still submit one based on this even if it's late.\n>>\n>> If I understand Google Summer of Code 2020 Timeline correctly\n>> https://developers.google.com/open-source/gsoc/timeline\n>> March 16 is the date when students might start to submit\n>> proposals, and the deadline is March 20.\n>\n> Yeah, sorry about the confusion, the timeline says:\n>\n> March 16 18:00 UTC Student application period begins\n> March 31 18:00 UTC Student application deadline\n>\n> So technically we could add ideas until March 31, but I think it makes\n> no sense, especially as we ask students to submit proposals well in\n> advance. So we should give ourselves March 16 as our actual deadline\n> to add ideas.\n\nRight.\n\n>>>> - is it too difficult of a project for GSoC?\n>>>\n>>> I guess it depends on how much you as a mentor would help the student\n>>> getting started.\n>>>\n>>> I think it's interesting and worth adding it anyway. Can you add it to\n>>> SoC-2020-Ideas.md?\n>>\n>> All right, I'll do it.\n>\n> Great, thanks!\n\nAdded with some modifications in commit 6b5edec6557\nhttps://github.com/git/git.github.io/commit/6b5edec6557930888441c626f9272dc2be0c769e\n\n>> P.S. I wonder if Derrick Stolee would agree to be co-mentor (if he is\n>> not too busy with working on Scalar).\n>\n> I am adding Heba in Cc as she said she would be ok to co-mentor. Emily\n> and Jonathan T. might be interested too, so I'm adding them too.\n\nAdded Heba as possible co-maintainer in SoC-2020-Ideas.md.\nIf I hear from Stolee, Emily or Jonathan T, I can add them too.\n\nBest,\n-- \nJakub Narębski\n"},{"id":"393124","messageId":"8636ad4t5y.fsf@gmail.com","threadId":"52965","inReplyTo":"868sk54vj9.fsf@gmail.com","subject":"Re: [RFC] Possible idea for GSoC 2020","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2020-03-12T13:08:41Z","receivedAt":"2020-03-12T13:08:48Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Jakub Narebski writes:\n> Christian Couder writes:\n>> On Wed, Mar 11, 2020 at 10:30 PM Jakub Narebski wrote:\n[...]\n>>>> I think it's interesting and worth adding it anyway. Can you add it to\n>>>> SoC-2020-Ideas.md?\n>>>\n>>> All right, I'll do it.\n>>\n>> Great, thanks!\n>\n> Added with some modifications in commit 6b5edec6557\n> https://github.com/git/git.github.io/commit/6b5edec6557930888441c626f9272dc2be0c769e\n\nAnd it failed to build. Was it caused by accidentally deleting two\ntrailing empty lines at the end of the file?\n\npage_build_id=168669405\n\n-- \nJakub Narębski\n"},{"id":"393196","messageId":"86tv2s34lo.fsf@gmail.com","threadId":"52965","inReplyTo":"xmqqo8t2hfxj.fsf@gitster.c.googlers.com","subject":"Re: [RFC] Possible idea for GSoC 2020","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2020-03-13T10:56:51Z","receivedAt":"2020-03-13T10:57:02Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Cc: Stolee, Heba, Jonathan T., Emily Shaffer. \n\nJunio C Hamano writes:\n> Jakub Narebski writes:\n>\n>> A few questions:\n>> - is it too late to propose a new project idea for GSoC 2020?\n>> - is it too difficult of a project for GSoC?\n>> ...\n>> ### Graph labelling for speeding up git commands\n>>\n>> - Language: C\n>> - Difficulty: hard / difficult\n>> - Possible mentors: Jakub Narębski\n>\n> I am not running the GSoC or participating in it in any way other\n> than just being a reviewer-maintainer of the project, but I would\n> appreciate a well-thought-out write-up very much.\n\nI have prepared slides for \"Graph operations in Git version control\nsystem\" (PDF), mainly describing what was already done to improve their\nperformance, but they also include a few thoughts about the future (like\nadditional graph reachability labelings)... unfortunately the slides are\nin Polish, not in English.\n\nIf there is interest, I could translate them, and put the result\nsomewhere accessible.\n\nOr I could try to make this information into blog post -- this topic\nwould really gain from using images (like Derrick Stolee series of\narticles on commit-graph).\n\n>> Git uses various clever methods for making operations on very large\n>> repositories faster, from bitmap indices for git-fetch[1], to generation\n>> numbers (also known as topological levels) in the commit-graph file for\n>> commit graph traversal operations like `git log --graph`[2].\n>>\n>> One possible improvement that can make Git even faster is using min-post\n>> intervals labelling. The basis of this labelling is post-visit order of\n>> a depth-first search traversal tree of a commit graph, let's call it\n>> 'post(v)'.\n>>\n>> If for each commit 'v' we would compute and store in the commit-graph\n>> file two numbers: 'post(v)' and the minimum of 'post(u)' for all commits\n>> reachable from 'v', let's call the latter 'min_graph(v)', then the\n>> following condition is true:\n>>\n>> if 'v' can reach 'u', then min_graph(v) <= post(u) <= post(v)\n>>\n>> If for each commit 'v' we would compute and store in the commit-graph\n>> file two numbers: 'post(v)' and the minimum of 'post(u)' for commits\n>> that were visited during the part of depth-first search that started\n>> from 'v' (which is the minimum of post-order number for subtree of a\n>> spanning tree that starts at 'v'). Let's call the later 'min_tree(v)'.\n>> Then the following condition is true:\n>>\n>> if min_tree(v) <= post(u) <= post(v), then 'v' can reach 'u'\n>>\n>> The task would be to implement computing such labelling (or a more\n>> involved variant of it[3][4]), storing it in commit-graph file, and\n>> using it for speeding up git commands (starting from a single chosen\n>> command) such as:\n>>\n>> - git merge-base --is-ancestor A B\n>> - git branch --contains A\n>> - git tag --contains A\n>> - git branch --merged A\n>> - git tag --merged A\n>> - git merge-base --all A B\n>> - git log --topo-sort\n>>\n>> References:\n>>\n>> 1. \n>> 2. \n>> 3. \n>> 4. \n>>\n>> See also discussion in:\n>>\n>> \n\nP.S. A bit more expanded writeup now available\nat https://git.github.io/SoC-2020-Ideas/\n\nBest,\n-- \nJakub Narębski\n"},{"id":"393197","messageId":"86o8t034hy.fsf@gmail.com","threadId":"52965","inReplyTo":"8636ad4t5y.fsf@gmail.com","subject":"Re: [RFC] Possible idea for GSoC 2020","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2020-03-13T10:59:05Z","receivedAt":"2020-03-13T10:59:11Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Jakub Narebski writes:\n> Jakub Narebski writes:\n>> Christian Couder writes:\n>>> On Wed, Mar 11, 2020 at 10:30 PM Jakub Narebski wrote:\n> [...]\n>>>>> I think it's interesting and worth adding it anyway. Can you add it to\n>>>>> SoC-2020-Ideas.md?\n>>>>\n>>>> All right, I'll do it.\n>>>\n>>> Great, thanks!\n>>\n>> Added with some modifications in commit 6b5edec6557\n>> https://github.com/git/git.github.io/commit/6b5edec6557930888441c626f9272dc2be0c769e\n>\n> And it failed to build. Was it caused by accidentally deleting two\n> trailing empty lines at the end of the file?\n>\n> page_build_id=168669405\n\nFixed now (somehow).\n\nhttps://git.github.io/SoC-2020-Ideas/#commit-graph-labeling-for-speeding-up-git-commands\n\n-- \nJakub Narębski\n"},{"id":"393206","messageId":"66dc369f-cd83-e39c-1310-32a9c003d114@iee.email","threadId":"52965","inReplyTo":"86mu8o8dsf.fsf@gmail.com","subject":"Re: [RFC] Possible idea for GSoC 2020","fromName":"Philip Oakley","fromEmail":"philipoakley@iee.email","sentAt":"2020-03-13T13:08:33Z","receivedAt":"2020-03-13T13:08:39Z","isPatch":false,"sender":{"key":"philipoakley@iee.email","avatar":"https://avatars.githubusercontent.com/u/914343?v=4"},"body":"Hi Jakub,\n\nOn 10/03/2020 14:50, Jakub Narebski wrote:\n> Hello,\n>\n> Here below is a possible proposal for a more difficult Google Summer of\n> Code 2020 project.\n>\n> A few questions:\n> - is it too late to propose a new project idea for GSoC 2020?\n> - is it too difficult of a project for GSoC?\n>\n> Best,\n>\n> Jakub Narębski\n>\n> --------------------------------------------------\n>\n> ### Graph labelling for speeding up git commands\n>\n> - Language: C\n> - Difficulty: hard / difficult\n> - Possible mentors: Jakub Narębski\n>\n> Git uses various clever methods for making operations on very large\n> repositories faster, from bitmap indices for git-fetch[1], to generation\n> numbers (also known as topological levels) in the commit-graph file for\n> commit graph traversal operations like `git log --graph`[2].\n>\n> One possible improvement that can make Git even faster is using min-post\n> intervals labelling. The basis of this labelling is post-visit order of\n> a depth-first search traversal tree of a commit graph, let's call it\n> 'post(v)'.\nThis, the post(v) number, may need a bit more explanation for those not\nfamiliar with graph theory terminology, so that they can get up to speed\neasily about the method, and it's (hopeful) simplicity.\n\n It isn't clear to me if it is a count along a single string-of-pearls\nbetween two branch - merge points, or depth from origin, or whether it\ncan span large chunks of the DAG? Ref 3. has the same problem of\nstarting from an assumed level of knowledge and understanding that may\nput of non-academics (I'm thinking that the proposed method is this\nPReaCH [3]).\n\nIt's my understanding that 'v' is usually 1...n in the literature, but\nin reality it just means 'unique label' (and ultimately able to be\nindexed in a data table). In Git we use the object id as the unique\nlabel, so the 1..n is just an abstraction/convenience. The other problem\nthat can happen is if the terminologies of Git doesn't quite match those\nof the descriptions, such as which end is 'root', or being 'mutually\nreachable' in a directed acyclic graph.\n\nThe Wikipedia article on contraction hierarchies [6] did give some\nuseful clues for more lay readers.\n\n> If for each commit 'v' we would compute and store in the commit-graph\n> file two numbers: 'post(v)' and the minimum of 'post(u)' for all commits\n> reachable from 'v', let's call the latter 'min_graph(v)', then the\n> following condition is true:\n>\n> if 'v' can reach 'u', then min_graph(v) <= post(u) <= post(v)\n>\n> If for each commit 'v' we would compute and store in the commit-graph\n> file two numbers: 'post(v)' and the minimum of 'post(u)' for commits\n> that were visited during the part of depth-first search that started\n> from 'v' (which is the minimum of post-order number for subtree of a\n> spanning tree that starts at 'v'). Let's call the later 'min_tree(v)'.\n> Then the following condition is true:\n>\n> if min_tree(v) <= post(u) <= post(v), then 'v' can reach 'u'\n>\n> The task would be to implement computing such labelling (or a more\n> involved variant of it[3][4]), storing it in commit-graph file, and\n> using it for speeding up git commands (starting from a single chosen\n> command) such as:\n>\n> - git merge-base --is-ancestor A B\n> - git branch --contains A\n> - git tag --contains A\n> - git branch --merged A\n> - git tag --merged A\n> - git merge-base --all A B\n> - git log --topo-sort\n>\n> References:\n>\n> 1. \n> 2. \n> 3. \n> 4. \n>\n> See also discussion in:\n>\n> [5]\nPhilip\n\n[6] https://en.wikipedia.org/wiki/Contraction_hierarchies\n\n[I've been off-list for 2+ ,months, so still catching up]\n"},{"id":"393207","messageId":"86ftec2ui8.fsf@gmail.com","threadId":"52965","inReplyTo":"66dc369f-cd83-e39c-1310-32a9c003d114@iee.email","subject":"Re: [RFC] Possible idea for GSoC 2020","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2020-03-13T14:34:55Z","receivedAt":"2020-03-13T14:35:06Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Hello Philip,\n\nPhilip Oakley writes:\n> On 10/03/2020 14:50, Jakub Narebski wrote:\n[...]\n>> ### Graph labelling for speeding up git commands\n>>\n>> - Language: C\n>> - Difficulty: hard / difficult\n>> - Possible mentors: Jakub Narębski\n>>\n>> Git uses various clever methods for making operations on very large\n>> repositories faster, from bitmap indices for git-fetch[1], to generation\n>> numbers (also known as topological levels) in the commit-graph file for\n>> commit graph traversal operations like `git log --graph`[2].\n>>\n>> One possible improvement that can make Git even faster is using min-post\n>> intervals labelling. The basis of this labelling is post-visit order of\n>> a depth-first search traversal tree of a commit graph, let's call it\n>> 'post(v)'.\n>>\n> This, the post(v) number, may need a bit more explanation for those not\n> familiar with graph theory terminology, so that they can get up to speed\n> easily about the method, and it's (hopeful) simplicity.\n\nAll right, I see that it might be not clear for someone who is not\nfamiliar with graph theory terminology. The post(v) order is the order\nyou encounter commits, assuming that you mark commit 'v' as visited\nafter all its parents have been visited.\n\nThe positive-cut labeling works also for pre(v) order, where we number\ncommits from top, starting from heads, marking commit 'v' as visited\nbefore any of its parents (you just need to switch from min-post to\npre-max interval).\n\n> It isn't clear to me if it is a count along a single string-of-pearls\n> between two branch - merge points, or depth from origin, or whether it\n> can span large chunks of the DAG? Ref 3. has the same problem of\n> starting from an assumed level of knowledge and understanding that may\n> put of non-academics (I'm thinking that the proposed method is this\n> PReaCH [3]).\n\nThe basic method is something simpler, common to all those methods.\nIt is described as\n- method from \"3.3 Pruning Based on DFS Numbering\" in PReaCH[3] paper\n (only one of full intervals from Figure 3 there), with modifications\n- method from \"Interval Indexing\" paragraph in \"I. Introduction\"\n in FERRARI[4] paper, but using only a single interval (strict or\n approximate)\n- Fig. 4 Min-Post Labeling, in \"GRAIL: A Scalable Index for Reachability\n Queries in Very Large Graphs\" (2012) paper\n- \"3.4.1 Positive-Cut Filter\" subsubsection in \"3.4 Optimizations\"\n in FELINE paper i.e. \"Reachability Queries in Very Large Graphs:\n A Fast Refined Online Search Approach\" (2014)\n\n> It's my understanding that 'v' is usually 1...n in the literature, but\n> in reality it just means 'unique label' (and ultimately able to be\n> indexed in a data table). In Git we use the object id as the unique\n> label, so the 1..n is just an abstraction/convenience. The other problem\n> that can happen is if the terminologies of Git doesn't quite match those\n> of the descriptions, such as which end is 'root', or being 'mutually\n> reachable' in a directed acyclic graph.\n\nYes, when reading various graph papers, I need to translate 'root',\n'leaf', 'child' from graph-theory terminology to git terminology.\n\nBut 'v' being a node (a commit in a commit graph of revisions) is not\none of them.\n\n>\n> The Wikipedia article on contraction hierarchies [6] did give some\n> useful clues for more lay readers.\n\nOoops. Actually in my opinion Reachability Contraction Hierarchies\n(RCH) reachability index from PReaCH[3] paper would not work for Git, as\nit assumes bidirectional BFS search.\n\nI have cited PReaCH[3] paper for its Pruning Based on DFS Numbering\nideas.\n\n>> If for each commit 'v' we would compute and store in the commit-graph\n>> file two numbers: 'post(v)' and the minimum of 'post(u)' for all commits\n>> reachable from 'v', let's call the latter 'min_graph(v)', then the\n>> following condition is true:\n>>\n>> if 'v' can reach 'u', then min_graph(v) <= post(u) <= post(v)\n>>\n>> If for each commit 'v' we would compute and store in the commit-graph\n>> file two numbers: 'post(v)' and the minimum of 'post(u)' for commits\n>> that were visited during the part of depth-first search that started\n>> from 'v' (which is the minimum of post-order number for subtree of a\n>> spanning tree that starts at 'v'). Let's call the later 'min_tree(v)'.\n>> Then the following condition is true:\n>>\n>> if min_tree(v) <= post(u) <= post(v), then 'v' can reach 'u'\n>>\n>> The task would be to implement computing such labelling (or a more\n>> involved variant of it[3][4]), storing it in commit-graph file, and\n>> using it for speeding up git commands (starting from a single chosen\n>> command) such as:\n>>\n>> - git merge-base --is-ancestor A B\n>> - git branch --contains A\n>> - git tag --contains A\n>> - git branch --merged A\n>> - git tag --merged A\n>> - git merge-base --all A B\n>> - git log --topo-sort\n>>\n>> References:\n>>\n>> 1. \n>> 2. \n>> 3. \n>> 4. \n>>\n>> See also discussion in:\n>>\n>> [5]\n>\n> [6] https://en.wikipedia.org/wiki/Contraction_hierarchies\n>\n> [I've been off-list for 2+ ,months, so still catching up]\n\nBest,\n-- \nJakub Narębski\n"},{"id":"393268","messageId":"86zhch7kyz.fsf@gmail.com","threadId":"52965","inReplyTo":"86tv2s34lo.fsf@gmail.com","subject":"Re: [RFC] Possible idea for GSoC 2020","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2020-03-15T14:26:28Z","receivedAt":"2020-03-15T14:26:38Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Cc: Abhishek Kumar\n\nJakub Narebski writes:\n\n> Cc: Stolee, Heba, Jonathan T., Emily Shaffer. \n>\n> Junio C Hamano writes:\n>> Jakub Narebski writes:\n[...]\n>>> ### Graph labelling for speeding up git commands\n>>>\n>>> - Language: C\n>>> - Difficulty: hard / difficult\n>>> - Possible mentors: Jakub Narębski\n>>\n>> I am not running the GSoC or participating in it in any way other\n>> than just being a reviewer-maintainer of the project, but I would\n>> appreciate a well-thought-out write-up very much.\n>\n> I have prepared slides for \"Graph operations in Git version control\n> system\" (PDF), mainly describing what was already done to improve their\n> performance, but they also include a few thoughts about the future (like\n> additional graph reachability labelings)... unfortunately the slides are\n> in Polish, not in English.\n>\n> If there is interest, I could translate them, and put the result\n> somewhere accessible.\n\nHere it is, traanslated into English, but otherwise almost exactly as I\nhave presented it on December 2019. Those slides includes much of\nintroductory information, so one would be interested probably in few\nlast slides (the \"Future work\" section).\n\n https://drive.google.com/file/d/1psMBVfcRHcZeJ7AewGpdoymrEfFVdXoK/view?usp=sharing\n\nI will be extending those slides with more information about interval\nlabeling, and then I will update the file, and I can post it also on\nSlideShare (or other site, if one can recommend it).\n\n> Or I could try to make this information into blog post -- this topic\n> would really gain from using images (like Derrick Stolee series of\n> articles on commit-graph).\n\nThis would take a bit, I'll try to do it when I would have some more\nfree time.\n\nRegards,\n-- \nJakub Narębski\n"},{"id":"393282","messageId":"076acb45-5360-6ee4-7c65-907488300ef3@iee.email","threadId":"52965","inReplyTo":"86ftec2ui8.fsf@gmail.com","subject":"Re: [RFC] Possible idea for GSoC 2020","fromName":"Philip Oakley","fromEmail":"philipoakley@iee.email","sentAt":"2020-03-15T18:57:34Z","receivedAt":"2020-03-15T18:57:50Z","isPatch":false,"sender":{"key":"philipoakley@iee.email","avatar":"https://avatars.githubusercontent.com/u/914343?v=4"},"body":"Hi Jakub,\nsome comments on potential misreading by being over-pedantic...\n\nadded Abhishek for GSoC comments\n\nOn 13/03/2020 14:34, Jakub Narebski wrote:\n> Hello Philip,\n>\n> Philip Oakley writes:\n>> On 10/03/2020 14:50, Jakub Narebski wrote:\n> [...]\n>>> ### Graph labelling for speeding up git commands\n>>>\n>>> - Language: C\n>>> - Difficulty: hard / difficult\n>>> - Possible mentors: Jakub Narębski\n>>>\n>>> Git uses various clever methods for making operations on very large\n>>> repositories faster, from bitmap indices for git-fetch[1], to generation\n>>> numbers (also known as topological levels) in the commit-graph file for\n>>> commit graph traversal operations like `git log --graph`[2].\n>>>\n>>> One possible improvement that can make Git even faster is using min-post\n>>> intervals labelling. The basis of this labelling is post-visit order of\n>>> a depth-first search traversal tree of a commit graph, let's call it\n>>> 'post(v)'.\nSo post(v) is the (increasing) number for the visited commits, starting\nwith 1 at the initial branch tip (not root!), as the graph is traversed,\ndepth first, with backtracking to the most recent commit that still has\nunvisited parents when either the root commit, or an already visited\ncommit is found. (phew, that took a lot of words;-)\n\ne.g. (with 'a' as a branch tip)\n\na - b - c - d - e - f - g\n \\m/ \\w - x/ (m spans c-d; w-x spans e-g)\n\npotential orderings, based on alternate parental choices.\nabcdefgwxm\nabcdewxgfm\nabcmdefgwx\nabcmdewxgf\n\nAll 4 orderings are equally valid implementations.(?)\n>> This, the post(v) number, may need a bit more explanation for those not\n>> familiar with graph theory terminology, so that they can get up to speed\n>> easily about the method, and it's (hopeful) simplicity.\n> All right, I see that it might be not clear for someone who is not\n> familiar with graph theory terminology. The post(v) order is the order\n> you encounter commits, assuming that you mark commit 'v' as visited\n> after all its parents have been visited.\n\nThe 'all' can be misunderstood as meaning 'skip' a commit if it has\nmultiple parents, until the last visit. I don't think that's what is\nmeant. (or is it?)\n\n>\n> The positive-cut labeling works also for pre(v) order, where we number\n> commits from top, starting from heads, marking commit 'v' as visited\n> before any of its parents (you just need to switch from min-post to\n> pre-max interval).\nI'm not sure I understood that. Is this the same as my comment above.\n\n>\n>> It isn't clear to me if it is a count along a single string-of-pearls\n>> between two branch - merge points, or depth from origin, or whether it\n>> can span large chunks of the DAG? Ref 3. has the same problem of\n>> starting from an assumed level of knowledge and understanding that may\n>> put of non-academics (I'm thinking that the proposed method is this\n>> PReaCH [3]).\n> The basic method is something simpler, common to all those methods.\n> It is described as\n> - method from \"3.3 Pruning Based on DFS Numbering\" in PReaCH[3] paper\n> (only one of full intervals from Figure 3 there), with modifications\n> - method from \"Interval Indexing\" paragraph in \"I. Introduction\"\n> in FERRARI[4] paper, but using only a single interval (strict or\n> approximate)\n> - Fig. 4 Min-Post Labeling, in \"GRAIL: A Scalable Index for Reachability\n> Queries in Very Large Graphs\" (2012) paper\n> - \"3.4.1 Positive-Cut Filter\" subsubsection in \"3.4 Optimizations\"\n> in FELINE paper i.e. \"Reachability Queries in Very Large Graphs:\n> A Fast Refined Online Search Approach\" (2014)\n>\n>> It's my understanding that 'v' is usually 1...n in the literature, but\n>> in reality it just means 'unique label' (and ultimately able to be\n>> indexed in a data table). In Git we use the object id as the unique\n>> label, so the 1..n is just an abstraction/convenience. The other problem\n>> that can happen is if the terminologies of Git doesn't quite match those\n>> of the descriptions, such as which end is 'root', or being 'mutually\n>> reachable' in a directed acyclic graph.\n> Yes, when reading various graph papers, I need to translate 'root',\n> 'leaf', 'child' from graph-theory terminology to git terminology.\n>\n> But 'v' being a node (a commit in a commit graph of revisions) is not\n> one of them.\nI'd agree that 'node' is ok, it's just the available values for 'v' that\ncan be presumptuous.\n(i.e. the academics already labelling v->1..n, that often just happens\nto be the order they end up with:: `Given with nodes\n1..n, then ` The PReaCH paper does that.)\n\nPlus our DAGs are, in a sense, backward (only children know who their\nparents are!), so all the counting levels feel wrong (we count edges\nfrom the wrong end)\n>\n>> The Wikipedia article on contraction hierarchies [6] did give some\n>> useful clues for more lay readers.\n> Ooops. Actually in my opinion Reachability Contraction Hierarchies\n> (RCH) reachability index from PReaCH[3] paper would not work for Git, as\n> it assumes bidirectional BFS search.\n>\n> I have cited PReaCH[3] paper for its Pruning Based on DFS Numbering\n> ideas.\n>\n>>> If for each commit 'v' we would compute and store in the commit-graph\n>>> file two numbers: 'post(v)' and the minimum of 'post(u)' for all commits\n>>> reachable from 'v', let's call the latter 'min_graph(v)', then the\n>>> following condition is true:\n>>>\n>>> if 'v' can reach 'u', then min_graph(v) <= post(u) <= post(v)\n>>>\n>>> If for each commit 'v' we would compute and store in the commit-graph\n>>> file two numbers: 'post(v)' and the minimum of 'post(u)' for commits\n>>> that were visited during the part of depth-first search that started\n>>> from 'v' (which is the minimum of post-order number for subtree of a\n>>> spanning tree that starts at 'v'). Let's call the later 'min_tree(v)'.\n>>> Then the following condition is true:\n>>>\n>>> if min_tree(v) <= post(u) <= post(v), then 'v' can reach 'u'\n>>>\n>>> The task would be to implement computing such labelling (or a more\n>>> involved variant of it[3][4]), storing it in commit-graph file, and\n>>> using it for speeding up git commands (starting from a single chosen\n>>> command) such as:\n>>>\n>>> - git merge-base --is-ancestor A B\n>>> - git branch --contains A\n>>> - git tag --contains A\n>>> - git branch --merged A\n>>> - git tag --merged A\n>>> - git merge-base --all A B\n>>> - git log --topo-sort\n>>>\n>>> References:\n>>>\n>>> 1. \n>>> 2. \n>>> 3. \n>>> 4. \n>>>\n>>> See also discussion in:\n>>>\n>>> [5]\n>> [6] https://en.wikipedia.org/wiki/Contraction_hierarchies\n>>\n>> [I've been off-list for 2+ ,months, so still catching up]\n> Best,\nThanks for the feedback\nPhilip\n"},{"id":"393285","messageId":"86k13l722n.fsf@gmail.com","threadId":"52965","inReplyTo":"076acb45-5360-6ee4-7c65-907488300ef3@iee.email","subject":"Re: [RFC] Possible idea for GSoC 2020","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2020-03-15T21:14:40Z","receivedAt":"2020-03-15T21:14:50Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Hello, Philip\n\nThank you for your continued interest in this topic.\n\nPhilip Oakley writes:\n> On 13/03/2020 14:34, Jakub Narebski wrote:\n>> Philip Oakley writes:\n>>> On 10/03/2020 14:50, Jakub Narebski wrote:\n>> [...]\n>>>> ### Graph labelling for speeding up git commands\n>>>>\n>>>> - Language: C\n>>>> - Difficulty: hard / difficult\n>>>> - Possible mentors: Jakub Narębski\n>>>>\n>>>> Git uses various clever methods for making operations on very large\n>>>> repositories faster, from bitmap indices for git-fetch[1], to generation\n>>>> numbers (also known as topological levels) in the commit-graph file for\n>>>> commit graph traversal operations like `git log --graph`[2].\n>>>>\n>>>> One possible improvement that can make Git even faster is using min-post\n>>>> intervals labelling. The basis of this labelling is post-visit order of\n>>>> a depth-first search traversal tree of a commit graph, let's call it\n>>>> 'post(v)'.\n>\n> So post(v) is the (increasing) number for the visited commits, starting\n> with 1 at the initial branch tip (not root!), as the graph is traversed,\n> depth first, with backtracking to the most recent commit that still has\n> unvisited parents when either the root commit, or an already visited\n> commit is found. (phew, that took a lot of words;-)\n\nNo, if we start at branch tip (source node), and number in the order of\nvisiting during DFS traversal, with node numbered _before_ its out\nneighbours (parents in Git terms), that would be pre(v) numbering.\n\nFor post(v) you number nodes (commits) in the order of backtracking,\nthat is with 1 at some parentless root commit, not 1 at some branch\ntip. This can be done e.g. during computing of generation numbers.\n\nAn example of such post(v) labeling can be found on slides 57-58/64 and\n59/64 in v1.1 version of my slides:\n https://drive.google.com/open?id=1psMBVfcRHcZeJ7AewGpdoymrEfFVdXoK\n\n> e.g. (with 'a' as a branch tip)\n>\n> a - b - c - d - e - f - g\n> \\m/ \\w - x/ (m spans c-d; w-x spans e-g)\n\nWe usually order commits left-to-right, or bottom-to-top, with most\nrecent commits and branch tips respectively on the far right, or on the\ntop. This is the reverse notation.\n\n> potential orderings, based on alternate parental choices.\n>\n> abcdefgwxm\n> abcdewxgfm\n> abcmdefgwx\n> abcmdewxgf\n>\n> All 4 orderings are equally valid implementations.(?)\n\nYes, this is true. There are various heuristics to select the best\nordering, but as most of those require additional work to be done\nupfront (e.g. computing in-degrees, or topological sort, or generation\nnumbers i.e. topological levels), we can start with simple rule: walk\nthe graph in parents order.\n\n>>> This, the post(v) number, may need a bit more explanation for those not\n>>> familiar with graph theory terminology, so that they can get up to speed\n>>> easily about the method, and it's (hopeful) simplicity.\n>>>\n>> All right, I see that it might be not clear for someone who is not\n>> familiar with graph theory terminology. The post(v) order is the order\n>> you encounter commits, assuming that you mark commit 'v' as visited\n>> after all its parents have been visited.\n>\n> The 'all' can be misunderstood as meaning 'skip' a commit if it has\n> multiple parents, until the last visit. I don't think that's what is\n> meant. (or is it?)\n\nDuring the depth-first search (DFS) traversal of the commit graph we\nwalk all reachable commits. What I meant here is that the node (commit)\ngets it post(v) number only after all of its parents have been visited,\nand we backtracked to this commit.\n\nAgain, I will refer to the frame 59/64 in v1.1 version of my slides:\n https://drive.google.com/open?id=1psMBVfcRHcZeJ7AewGpdoymrEfFVdXoK\n\n>>\n>> The positive-cut labeling works also for pre(v) order, where we number\n>> commits from top, starting from heads, marking commit 'v' as visited\n>> before any of its parents (you just need to switch from min-post to\n>> pre-max interval).\n>>\n> I'm not sure I understood that. Is this the same as my comment above.\n\nWhat I wanted to say here, is that if you label commits with pre(v)\nnumber, that is number them in the order of visiting, commit before its\nparents, then we can use pre-max interval instead. The interval would\nbe [pre(v), max_{p \\in parents(v)} pre(p)], and the positive-cut filter\nwould work the same: if one interval is contained in the other, then\nthere is path from one commit to the other.\n\n>>> It isn't clear to me if it is a count along a single string-of-pearls\n>>> between two branch - merge points, or depth from origin, or whether it\n>>> can span large chunks of the DAG? Ref 3. has the same problem of\n>>> starting from an assumed level of knowledge and understanding that may\n>>> put of non-academics (I'm thinking that the proposed method is this\n>>> PReaCH [3]).\n>>\n>> The basic method is something simpler, common to all those methods.\n>> It is described as\n>> - method from \"3.3 Pruning Based on DFS Numbering\" in PReaCH[3] paper\n>> (only one of full intervals from Figure 3 there), with modifications\n>> - method from \"Interval Indexing\" paragraph in \"I. Introduction\"\n>> in FERRARI[4] paper, but using only a single interval (strict or\n>> approximate)\n>> - Fig. 4 Min-Post Labeling, in \"GRAIL: A Scalable Index for Reachability\n>> Queries in Very Large Graphs\" (2012) paper\n>> - \"3.4.1 Positive-Cut Filter\" subsubsection in \"3.4 Optimizations\"\n>> in FELINE paper i.e. \"Reachability Queries in Very Large Graphs:\n>> A Fast Refined Online Search Approach\" (2014)\n>>\n>>> It's my understanding that 'v' is usually 1...n in the literature, but\n>>> in reality it just means 'unique label' (and ultimately able to be\n>>> indexed in a data table). In Git we use the object id as the unique\n>>> label, so the 1..n is just an abstraction/convenience. The other problem\n>>> that can happen is if the terminologies of Git doesn't quite match those\n>>> of the descriptions, such as which end is 'root', or being 'mutually\n>>> reachable' in a directed acyclic graph.\n>>\n>> Yes, when reading various graph papers, I need to translate 'root',\n>> 'leaf', 'child' from graph-theory terminology to git terminology.\n>>\n>> But 'v' being a node (a commit in a commit graph of revisions) is not\n>> one of them.\n>\n> I'd agree that 'node' is ok, it's just the available values for 'v' that\n> can be presumptuous.\n> (i.e. the academics already labelling v->1..n, that often just happens\n> to be the order they end up with:: `Given with nodes\n> 1..n, then ` The PReaCH paper does that.)\n\nNo, in academics paper usually define graph as a set of vertices V and\nset of edges E. Numbering vertices (nodes) is something extra.\n\n> Plus our DAGs are, in a sense, backward (only children know who their\n> parents are!), so all the counting levels feel wrong (we count edges\n> from the wrong end)\n\nNo, our DAGs are not backward, only our terminology is different.\nOn the other hand we cannot assume that we can get reverse graph\neasily (many graph reachability algorithms do assume that).\n\n graph theory | git documentation | meaning\n ------------------------------------------------------------------\n roots | branch tips, heads | no incoming edges\n leaves | root commits | no outgoing edges\n children | parents | [out] neighbours\n\nBest,\n-- \nJakub Narębski\n"},{"id":"393300","messageId":"7d6a84c7-6b16-c2a9-11a1-3397422064d1@gmail.com","threadId":"52965","inReplyTo":"86mu8o8dsf.fsf@gmail.com","subject":"Re: [RFC] Possible idea for GSoC 2020","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2020-03-16T12:44:54Z","receivedAt":"2020-03-16T12:44:59Z","isPatch":false,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 3/10/2020 10:50 AM, Jakub Narebski wrote:\n> Hello,\n> \n> Here below is a possible proposal for a more difficult Google Summer of\n> Code 2020 project.\n> \n> A few questions:\n> - is it too late to propose a new project idea for GSoC 2020?\n> - is it too difficult of a project for GSoC?\n> \n> Best,\n> \n> Jakub Narębski\n> \n> --------------------------------------------------\n> \n> ### Graph labelling for speeding up git commands\n> \n> - Language: C\n> - Difficulty: hard / difficult\n> - Possible mentors: Jakub Narębski\n> \n> Git uses various clever methods for making operations on very large\n> repositories faster, from bitmap indices for git-fetch[1], to generation\n> numbers (also known as topological levels) in the commit-graph file for\n> commit graph traversal operations like `git log --graph`[2].\n> \n> One possible improvement that can make Git even faster is using min-post\n> intervals labelling. The basis of this labelling is post-visit order of\n> a depth-first search traversal tree of a commit graph, let's call it\n> 'post(v)'.\n> \n> If for each commit 'v' we would compute and store in the commit-graph\n> file two numbers: 'post(v)' and the minimum of 'post(u)' for all commits\n> reachable from 'v', let's call the latter 'min_graph(v)', then the\n> following condition is true:\n> \n> if 'v' can reach 'u', then min_graph(v) <= post(u) <= post(v)\n\nI haven't thought too hard about it, but I'm assuming that if v is not\nin a commit-graph file, then post(v) would be \"infinite\" and min_graph(v)\nwould be zero.\n\nWe already have the second inequality (f(u) <= f(v)) where the function\n'f' is the generation of v. The success of this approach over generation\nnumbers relies entirely on how often the inequality min_graph(v) <= post(u)\nfails when gen(u) <= gen(v) holds.\n\n> If for each commit 'v' we would compute and store in the commit-graph\n> file two numbers: 'post(v)' and the minimum of 'post(u)' for commits\n> that were visited during the part of depth-first search that started\n> from 'v' (which is the minimum of post-order number for subtree of a\n> spanning tree that starts at 'v'). Let's call the later 'min_tree(v)'.\n> Then the following condition is true:\n> \n> if min_tree(v) <= post(u) <= post(v), then 'v' can reach 'u'\n\nHow many places in Git do we ask \"can v reach u?\" and how many would\nreturn immediately without needing a walk in this new approach? My\nguess is that we will have a very narrow window where this query\nreturns a positive result.\n\nI believe we discussed this concept briefly when planning \"generation\nnumber v2\" and the main concern I have with this plan is that the\nvalues are not stable. The value of post(v) and min_tree(v) depend\non the entire graph as a whole, not just what is reachable from v\n(and preferably only the parents of v).\n\nBefore starting to implement this, I would consider how such labels\ncould be computed across incremental commit-graph boundaries. That is,\nif I'm only adding a layer of commits to the commit-graph without\nmodifying the existing layers of the commit-graph chain, can I still\ncompute values with these properties? How expensive is it? Do I need\nto walk the entire reachable set of commits?\n \n> The task would be to implement computing such labelling (or a more\n> involved variant of it[3][4]), storing it in commit-graph file, and\n> using it for speeding up git commands (starting from a single chosen\n> command) such as:\n> \n> - git merge-base --is-ancestor A B\n> - git branch --contains A\n> - git tag --contains A\n> - git branch --merged A\n> - git tag --merged A\n> - git merge-base --all A B\n> - git log --topo-sort\n\nHaving such a complicated two-dimensional system would need to\njustify itself by being measurably faster than that one-dimensional\nsystem in these example commands.\n\nThe point of generation number v2 [1] was to allow moving to \"exact\"\nalgorithms for things like merge-base where we still use commit time\nas a heuristic, and could be wrong because of special data shapes.\nWe don't use generation number in these examples because using only\ngeneration number can lead to a large increase in number of commits\nwalked. The example we saw in the Linux kernel repository was a bug\nfix created on top of a very old commit, so there was a commit of\nlow generation with very high commit-date that caused extra walking.\n(See [2] for a detailed description of the data shape.)\n\nMy _prediction_ is that the two-dimensional system will be more\ncomplicated to write and use, and will not have any measurable\ndifference. I'd be happy to be wrong, but I also would not send\nanyone down this direction only to find out I'm right and that\neffort was wasted.\n\nMy recommendation is that a GSoC student update the\ngeneration number to \"v2\" based on the definition you made in [1].\nThat proposal is also more likely to be effective in Git because\nit makes use of extra heuristic information (commit date) to\nassist the types of algorithms we care about.\n\nIn that case, the \"difficult\" part is moving the \"generation\"\nmember of struct commit into a slab before making it a 64-bit\nvalue. (This is likely necessary for your plan, anyway.) Updating\nthe generation number to v2 is relatively straight-forward after\nthat, as someone can follow all places that reference or compute\ngeneration numbers and apply a diff\n\nThanks,\n-Stolee\n\n[1] https://lore.kernel.org/git/86o8ziatb2.fsf_-_@gmail.com/\n [RFC/PATCH] commit-graph: generation v5 (backward compatible date ceiling)\n\n[2] https://lore.kernel.org/git/efa3720fb40638e5d61c6130b55e3348d8e4339e.1535633886.git.gitgitgadget@gmail.com/\n [PATCH 1/1] commit: don't use generation numbers if not needed\n"},{"id":"393302","messageId":"b391e9e4-fdff-a2ee-df62-80f9adb9ff0f@iee.email","threadId":"52965","inReplyTo":"86k13l722n.fsf@gmail.com","subject":"Re: [RFC] Possible idea for GSoC 2020","fromName":"Philip Oakley","fromEmail":"philipoakley@iee.email","sentAt":"2020-03-16T14:47:32Z","receivedAt":"2020-03-16T14:47:40Z","isPatch":false,"sender":{"key":"philipoakley@iee.email","avatar":"https://avatars.githubusercontent.com/u/914343?v=4"},"body":"Hi Jakub,\nThanks for the explanations. Some comments in line.\nOn 15/03/2020 21:14, Jakub Narebski wrote:\n> Hello, Philip\n>\n> Thank you for your continued interest in this topic.\n>\n> Philip Oakley writes:\n>> On 13/03/2020 14:34, Jakub Narebski wrote:\n>>> Philip Oakley writes:\n>>>> On 10/03/2020 14:50, Jakub Narebski wrote:\n>>> [...]\n>>>>> ### Graph labelling for speeding up git commands\n>>>>>\n>>>>> - Language: C\n>>>>> - Difficulty: hard / difficult\n>>>>> - Possible mentors: Jakub Narębski\n>>>>>\n>>>>> Git uses various clever methods for making operations on very large\n>>>>> repositories faster, from bitmap indices for git-fetch[1], to generation\n>>>>> numbers (also known as topological levels) in the commit-graph file for\n>>>>> commit graph traversal operations like `git log --graph`[2].\n>>>>>\n>>>>> One possible improvement that can make Git even faster is using min-post\n>>>>> intervals labelling. The basis of this labelling is post-visit order of\n>>>>> a depth-first search traversal tree of a commit graph, let's call it\n>>>>> 'post(v)'.\n>> So post(v) is the (increasing) number for the visited commits, starting\n>> with 1 at the initial branch tip (not root!), as the graph is traversed,\n>> depth first, with backtracking to the most recent commit that still has\n>> unvisited parents when either the root commit, or an already visited\n>> commit is found. (phew, that took a lot of words;-)\n> No, if we start at branch tip (source node), and number in the order of\n> visiting during DFS traversal, with node numbered _before_ its out\n> neighbours (parents in Git terms), that would be pre(v) numbering.\nSo I've described pre(v) numbering.\n>\n> For post(v) you number nodes (commits) in the order of backtracking,\n> that is with 1 at some parentless root commit, not 1 at some branch\n> tip. This can be done e.g. during computing of generation numbers.\nI didn't easily understand the wording.\n>\n> An example of such post(v) labeling can be found on slides 57-58/64 and\n> 59/64 in v1.1 version of my slides:\n> https://drive.google.com/open?id=1psMBVfcRHcZeJ7AewGpdoymrEfFVdXoK\nAh, I had an older version (picked up from the other thread) that only\nhad 60 slides (84 pdf pages). I had got all the way to the end.\nI've have a better read of that.\n\n>> e.g. (with 'a' as a branch tip)\n>>\n>> a - b - c - d - e - f - g\n>> \\m/ \\w - x/ (m spans c-d; w-x spans e-g)\n> We usually order commits left-to-right, or bottom-to-top, with most\n> recent commits and branch tips respectively on the far right, or on the\n> top. This is the reverse notation.\nTrue. It was for the convenience of following the Git DAG linkage. It's\neasy to make mistakes with right to left reading, especially for those\nwho aren't yet sure what they are looking at.\n>\n>> potential orderings, based on alternate parental choices.\n>>\n>> abcdefgwxm\n>> abcdewxgfm\n>> abcmdefgwx\n>> abcmdewxgf\n>>\n>> All 4 orderings are equally valid implementations.(?)\n> Yes, this is true. There are various heuristics to select the best\n> ordering, but as most of those require additional work to be done\n> upfront (e.g. computing in-degrees, or topological sort, or generation\n> numbers i.e. topological levels), we can start with simple rule: walk\n> the graph in parents order.\nThanks for confirming.\n>>>> This, the post(v) number, may need a bit more explanation for those not\n>>>> familiar with graph theory terminology, so that they can get up to speed\n>>>> easily about the method, and it's (hopeful) simplicity.\n>>>>\n>>> All right, I see that it might be not clear for someone who is not\n>>> familiar with graph theory terminology. The post(v) order is the order\n>>> you encounter commits, assuming that you mark commit 'v' as visited\n>>> after all its parents have been visited.\n>> The 'all' can be misunderstood as meaning 'skip' a commit if it has\n>> multiple parents, until the last visit. I don't think that's what is\n>> meant. (or is it?)\n> During the depth-first search (DFS) traversal of the commit graph we\n> walk all reachable commits. What I meant here is that the node (commit)\n> gets it post(v) number only after all of its parents have been visited,\n> and we backtracked to this commit.\n>\n> Again, I will refer to the frame 59/64 in v1.1 version of my slides:\n> https://drive.google.com/open?id=1psMBVfcRHcZeJ7AewGpdoymrEfFVdXoK\n>\n>>> The positive-cut labeling works also for pre(v) order, where we number\n>>> commits from top, starting from heads, marking commit 'v' as visited\n>>> before any of its parents (you just need to switch from min-post to\n>>> pre-max interval).\n>>>\n>> I'm not sure I understood that. Is this the same as my comment above.\n> What I wanted to say here, is that if you label commits with pre(v)\n> number, that is number them in the order of visiting, commit before its\n> parents, then we can use pre-max interval instead. The interval would\n> be [pre(v), max_{p \\in parents(v)} pre(p)], and the positive-cut filter\n> would work the same: if one interval is contained in the other, then\n> there is path from one commit to the other.\n>\n>>>> It isn't clear to me if it is a count along a single string-of-pearls\n>>>> between two branch - merge points, or depth from origin, or whether it\n>>>> can span large chunks of the DAG? Ref 3. has the same problem of\n>>>> starting from an assumed level of knowledge and understanding that may\n>>>> put of non-academics (I'm thinking that the proposed method is this\n>>>> PReaCH [3]).\n>>> The basic method is something simpler, common to all those methods.\n>>> It is described as\n>>> - method from \"3.3 Pruning Based on DFS Numbering\" in PReaCH[3] paper\n>>> (only one of full intervals from Figure 3 there), with modifications\n>>> - method from \"Interval Indexing\" paragraph in \"I. Introduction\"\n>>> in FERRARI[4] paper, but using only a single interval (strict or\n>>> approximate)\n>>> - Fig. 4 Min-Post Labeling, in \"GRAIL: A Scalable Index for Reachability\n>>> Queries in Very Large Graphs\" (2012) paper\n>>> - \"3.4.1 Positive-Cut Filter\" subsubsection in \"3.4 Optimizations\"\n>>> in FELINE paper i.e. \"Reachability Queries in Very Large Graphs:\n>>> A Fast Refined Online Search Approach\" (2014)\n>>>\n>>>> It's my understanding that 'v' is usually 1...n in the literature, but\n>>>> in reality it just means 'unique label' (and ultimately able to be\n>>>> indexed in a data table). In Git we use the object id as the unique\n>>>> label, so the 1..n is just an abstraction/convenience. The other problem\n>>>> that can happen is if the terminologies of Git doesn't quite match those\n>>>> of the descriptions, such as which end is 'root', or being 'mutually\n>>>> reachable' in a directed acyclic graph.\n>>> Yes, when reading various graph papers, I need to translate 'root',\n>>> 'leaf', 'child' from graph-theory terminology to git terminology.\n>>>\n>>> But 'v' being a node (a commit in a commit graph of revisions) is not\n>>> one of them.\n>> I'd agree that 'node' is ok, it's just the available values for 'v' that\n>> can be presumptuous.\n>> (i.e. the academics already labelling v->1..n, that often just happens\n>> to be the order they end up with:: `Given with nodes\n>> 1..n, then ` The PReaCH paper does that.)\n> No, in academics paper usually define graph as a set of vertices V and\n> set of edges E. Numbering vertices (nodes) is something extra.\nUsually it is mid paper where they do this about some property of an\norder (or at least _appear_ to do). I think they omit the \"given an\norder\" in f->1.n with (order) properties x,y,z, then we see p,q,r\nproperties.\n>> Plus our DAGs are, in a sense, backward (only children know who their\n>> parents are!), so all the counting levels feel wrong (we count edges\n>> from the wrong end)\n> No, our DAGs are not backward, only our terminology is different.\n> On the other hand we cannot assume that we can get reverse graph\n> easily (many graph reachability algorithms do assume that).\n>\n> graph theory | git documentation | meaning\n> ------------------------------------------------------------------\n> roots | branch tips, heads | no incoming edges\n> leaves | root commits | no outgoing edges\n> children | parents | [out] neighbours\nYes, I was surprised at the root-tip-root swap. It's a bit of a\npushmi-pullyu type of animal, but backwards;-).\n\n> Best,\nThanks. Back to reading the updated slide deck\n"},{"id":"393342","messageId":"86d09b7jx6.fsf@gmail.com","threadId":"52965","inReplyTo":"7d6a84c7-6b16-c2a9-11a1-3397422064d1@gmail.com","subject":"Re: [RFC] Possible idea for GSoC 2020","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2020-03-17T03:13:41Z","receivedAt":"2020-03-17T03:13:54Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Added other people who might be interested to Cc.\n\nDerrick Stolee writes:\n> On 3/10/2020 10:50 AM, Jakub Narebski wrote:\n\n>> Here below is a possible proposal for a more difficult Google Summer of\n>> Code 2020 project.\n>> \n>> A few questions:\n>> - is it too late to propose a new project idea for GSoC 2020?\n>> - is it too difficult of a project for GSoC?\n>> \n>> Best,\n>> \n>> Jakub Narębski\n\nhttps://git.github.io/SoC-2020-Ideas/#commit-graph-labeling-for-speeding-up-git-commands\n\n>> --------------------------------------------------\n>> \n>> ### Graph labelling for speeding up git commands\n>> \n>> - Language: C\n>> - Difficulty: hard / difficult\n>> - Possible mentors: Jakub Narębski\n>> \n>> Git uses various clever methods for making operations on very large\n>> repositories faster, from bitmap indices for git-fetch[1], to generation\n>> numbers (also known as topological levels) in the commit-graph file for\n>> commit graph traversal operations like `git log --graph`[2].\n>> \n>> One possible improvement that can make Git even faster is using min-post\n>> intervals labelling. The basis of this labelling is post-visit order of\n>> a depth-first search traversal tree of a commit graph, let's call it\n>> 'post(v)'.\n>> \n>> If for each commit 'v' we would compute and store in the commit-graph\n>> file two numbers: 'post(v)' and the minimum of 'post(u)' for all commits\n>> reachable from 'v', let's call the latter 'min_graph(v)', then the\n>> following condition is true:\n>> \n>> if 'v' can reach 'u', then min_graph(v) <= post(u) <= post(v)\n>\n> I haven't thought too hard about it, but I'm assuming that if v is not\n> in a commit-graph file, then post(v) would be \"infinite\" and min_graph(v)\n> would be zero.\n\nOr we can simply add a check if v is in a commit-graph file; this might\nbe not a good idea from the performance point of view.\n\n> We already have the second inequality (f(u) <= f(v)) where the function\n> 'f' is the generation of v. The success of this approach over generation\n> numbers relies entirely on how often the inequality min_graph(v) <= post(u)\n> fails when gen(u) <= gen(v) holds.\n\nTrue. It may turn out that additional negative-cut filters do not bring\nenough performance improvements over topological levels or corrected\ncommit date (or monotonically increasing corrected commit date) to be\nworth it.\n\nI think they can help in wide commit graphs (many concurrently developed\nbranches with many commits and few merges), and when there is orphan\nbranch (like 'todo' in the git.git, or 'gh-pages' for storing\nper-project GitHub Pages) that is somehow entangled in query.\n\n>> If for each commit 'v' we would compute and store in the commit-graph\n>> file two numbers: 'post(v)' and the minimum of 'post(u)' for commits\n>> that were visited during the part of depth-first search that started\n>> from 'v' (which is the minimum of post-order number for subtree of a\n>> spanning tree that starts at 'v'). Let's call the later 'min_tree(v)'.\n>> Then the following condition is true:\n>> \n>> if min_tree(v) <= post(u) <= post(v), then 'v' can reach 'u'\n>\n> How many places in Git do we ask \"can v reach u?\" and how many would\n> return immediately without needing a walk in this new approach? My\n> guess is that we will have a very narrow window where this query\n> returns a positive result.\n\nAs I wrote below, such positive-cut filter would be directly helpful in\nperforming the following commands:\n\n - `git merge-base --is-ancestor`\n - `git branch --contains`\n - `git tag --contains`\n - `git branch --merged`\n - `git tag --merged`\n\nIt would be also useful for tag autofollow in git-fetch; is is N-to-M\nequivalent to 1-to-N / N-to-1 `--contains` queries.\n\nI am quite sure that positive-cut filter would make `--ancestry-path`\nwalk faster.\n\nI think, but I am not sure, that positive-cut filter can make parts of\ntopological sort and merge base algorithms at least a tiny bit faster.\n\n> I believe we discussed this concept briefly when planning \"generation\n> number v2\" and the main concern I have with this plan is that the\n> values are not stable. The value of post(v) and min_tree(v) depend\n> on the entire graph as a whole, not just what is reachable from v\n> (and preferably only the parents of v).\n>\n> Before starting to implement this, I would consider how such labels\n> could be computed across incremental commit-graph boundaries. That is,\n> if I'm only adding a layer of commits to the commit-graph without\n> modifying the existing layers of the commit-graph chain, can I still\n> compute values with these properties? How expensive is it? Do I need\n> to walk the entire reachable set of commits?\n\nI think it would be possible to compute post(v) and min_tree(v) using\nincremental updates, and to make it compatibile with incremental\ncommit-graph format (with the commit-graph chain). But I have not\nproven it.\n\nThis incremental update would find _a_ post(v) number and min-post\ninterval labeling, but that might not be exactly the same as one would\nget if it was computed in one shot, from scratch. The result may be\nsuboptimal, but perhaps it would be still good enough.\n\nI have added the explanation of this idea to v1.2 of my slides:\n\nhttps://drive.google.com/open?id=1psMBVfcRHcZeJ7AewGpdoymrEfFVdXoK\nhttps://drive.google.com/file/d/1psMBVfcRHcZeJ7AewGpdoymrEfFVdXoK/view?usp=sharing\n\nhttps://www.slideshare.net/JakubNarbski/graph-operations-in-git-version-control-system-how-the-performance-was-improved-for-large-repositories-how-can-it-be-further-improved\n\nThere you can find on slides 65/58 and later (page 90 out of 99)\n*illustrated* explanation of the idea.\n\nExcerpt:\n========\n\nFor each layer in the \\texttt{commit-graph} chain store (in relevant chunks):\n - min--post interval labels\n - list of tips (heads) in the commit-graph; possibly also list of their intervals\n - for each layer in chain, except for base layer,\n store ajustments for 'post(v)' labels for previous layer\n (only needed for tips)\n \n - adjusting values of labels consist of adding a constant value to\n both sides of interval for a whole subtrees starting from\n old branch tips\n\nHTH\n\n>> The task would be to implement computing such labelling (or a more\n>> involved variant of it[3][4]), storing it in commit-graph file, and\n>> using it for speeding up git commands (starting from a single chosen\n>> command) such as:\n>> \n>> - git merge-base --is-ancestor A B\n>> - git branch --contains A\n>> - git tag --contains A\n>> - git branch --merged A\n>> - git tag --merged A\n>> - git merge-base --all A B\n>> - git log --topo-sort\n>\n> Having such a complicated two-dimensional system would need to\n> justify itself by being measurably faster than that one-dimensional\n> system in these example commands.\n\nThat is true. Git is certainly fast already thank to serialized commit\ngraph and generation numbers. Such extra positive-cut / negative-cut\nfilter subsystem would be maintenance burdern (though I think it could\nbe nicely isolated with a good API).\n\nOn the other hand repositories re gettting larger and larger...\n\n>\n> The point of generation number v2 [1] was to allow moving to \"exact\"\n> algorithms for things like merge-base where we still use commit time\n> as a heuristic, and could be wrong because of special data shapes.\n> We don't use generation number in these examples because using only\n> generation number can lead to a large increase in number of commits\n> walked. The example we saw in the Linux kernel repository was a bug\n> fix created on top of a very old commit, so there was a commit of\n> low generation with very high commit-date that caused extra walking.\n> (See [2] for a detailed description of the data shape.)\n>\n> My _prediction_ is that the two-dimensional system will be more\n> complicated to write and use, and will not have any measurable\n> difference. I'd be happy to be wrong, but I also would not send\n> anyone down this direction only to find out I'm right and that\n> effort was wasted.\n\nThat might be a problem.\n\nThis is a bit of a \"moonshot\" / research project, moreso than others.\nThough it would be still valuable, in my opionion, even if the code\nwouldn't ultimately get merged and added into Git.\n\n>\n> My recommendation is that a GSoC student update the\n> generation number to \"v2\" based on the definition you made in [1].\n> That proposal is also more likely to be effective in Git because\n> it makes use of extra heuristic information (commit date) to\n> assist the types of algorithms we care about.\n>\n> In that case, the \"difficult\" part is moving the \"generation\"\n> member of struct commit into a slab before making it a 64-bit\n> value. (This is likely necessary for your plan, anyway.) Updating\n> the generation number to v2 is relatively straight-forward after\n> that, as someone can follow all places that reference or compute\n> generation numbers and apply a diff\n\nGood idea! Though I am not sure if it is not too late to add it to the\nhttps://git.github.io/SoC-2020-Ideas/ as the self imposed deadline of\nMarch 16 (where students can start submitting proposals to GSoC) has\njust passed. Christian, what do you think?\n\nWould you agree, Stolee, to be a _possible_ mentor or co-mentor for\n\"Generation number v2\" project?\n\n> [1] https://lore.kernel.org/git/86o8ziatb2.fsf_-_@gmail.com/\n> [RFC/PATCH] commit-graph: generation v5 (backward compatible date ceiling)\n>\n> [2]\n> https://lore.kernel.org/git/efa3720fb40638e5d61c6130b55e3348d8e4339e.1535633886.git.gitgitgadget@gmail.com/\n> [PATCH 1/1] commit: don't use generation numbers if not needed\n\nBest,\n-- \nJakub Narębski\n"},{"id":"393344","messageId":"CAP8UFD3BeS8bj8OGKJmVyKeDTCvqhCpBxLhTwuQ3zffejQkj7g@mail.gmail.com","threadId":"52965","inReplyTo":"86d09b7jx6.fsf@gmail.com","subject":"Re: [RFC] Possible idea for GSoC 2020","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2020-03-17T07:24:22Z","receivedAt":"2020-03-17T07:24:40Z","isPatch":false,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"On Tue, Mar 17, 2020 at 4:13 AM Jakub Narebski wrote:\n\n[...]\n\n> >> ### Graph labelling for speeding up git commands\n\n[...]\n\n> > We already have the second inequality (f(u) <= f(v)) where the function\n> > 'f' is the generation of v. The success of this approach over generation\n> > numbers relies entirely on how often the inequality min_graph(v) <= post(u)\n> > fails when gen(u) <= gen(v) holds.\n>\n> True. It may turn out that additional negative-cut filters do not bring\n> enough performance improvements over topological levels or corrected\n> commit date (or monotonically increasing corrected commit date) to be\n> worth it.\n>\n> I think they can help in wide commit graphs (many concurrently developed\n> branches with many commits and few merges), and when there is orphan\n> branch (like 'todo' in the git.git, or 'gh-pages' for storing\n> per-project GitHub Pages) that is somehow entangled in query.\n>\n> >> If for each commit 'v' we would compute and store in the commit-graph\n> >> file two numbers: 'post(v)' and the minimum of 'post(u)' for commits\n> >> that were visited during the part of depth-first search that started\n> >> from 'v' (which is the minimum of post-order number for subtree of a\n> >> spanning tree that starts at 'v'). Let's call the later 'min_tree(v)'.\n> >> Then the following condition is true:\n> >>\n> >> if min_tree(v) <= post(u) <= post(v), then 'v' can reach 'u'\n> >\n> > How many places in Git do we ask \"can v reach u?\" and how many would\n> > return immediately without needing a walk in this new approach? My\n> > guess is that we will have a very narrow window where this query\n> > returns a positive result.\n>\n> As I wrote below, such positive-cut filter would be directly helpful in\n> performing the following commands:\n>\n> - `git merge-base --is-ancestor`\n> - `git branch --contains`\n> - `git tag --contains`\n> - `git branch --merged`\n> - `git tag --merged`\n>\n> It would be also useful for tag autofollow in git-fetch; is is N-to-M\n> equivalent to 1-to-N / N-to-1 `--contains` queries.\n>\n> I am quite sure that positive-cut filter would make `--ancestry-path`\n> walk faster.\n>\n> I think, but I am not sure, that positive-cut filter can make parts of\n> topological sort and merge base algorithms at least a tiny bit faster.\n\nIs there an easy way to check that it would provide significant\nperformance improvements at least in some cases? Can we ask the\nstudent to do that at the beginning of the GSoC?\n\n> > I believe we discussed this concept briefly when planning \"generation\n> > number v2\" and the main concern I have with this plan is that the\n> > values are not stable. The value of post(v) and min_tree(v) depend\n> > on the entire graph as a whole, not just what is reachable from v\n> > (and preferably only the parents of v).\n> >\n> > Before starting to implement this, I would consider how such labels\n> > could be computed across incremental commit-graph boundaries. That is,\n> > if I'm only adding a layer of commits to the commit-graph without\n> > modifying the existing layers of the commit-graph chain, can I still\n> > compute values with these properties? How expensive is it? Do I need\n> > to walk the entire reachable set of commits?\n>\n> I think it would be possible to compute post(v) and min_tree(v) using\n> incremental updates, and to make it compatibile with incremental\n> commit-graph format (with the commit-graph chain). But I have not\n> proven it.\n\nWould it be difficult to prove? What would be required? And again can\nwe ask the student to do that at the beginning of the GSoC?\n\n[...]\n\n> > The point of generation number v2 [1] was to allow moving to \"exact\"\n> > algorithms for things like merge-base where we still use commit time\n> > as a heuristic, and could be wrong because of special data shapes.\n> > We don't use generation number in these examples because using only\n> > generation number can lead to a large increase in number of commits\n> > walked. The example we saw in the Linux kernel repository was a bug\n> > fix created on top of a very old commit, so there was a commit of\n> > low generation with very high commit-date that caused extra walking.\n> > (See [2] for a detailed description of the data shape.)\n> >\n> > My _prediction_ is that the two-dimensional system will be more\n> > complicated to write and use, and will not have any measurable\n> > difference. I'd be happy to be wrong, but I also would not send\n> > anyone down this direction only to find out I'm right and that\n> > effort was wasted.\n>\n> That might be a problem.\n>\n> This is a bit of a \"moonshot\" / research project, moreso than others.\n> Though it would be still valuable, in my opionion, even if the code\n> wouldn't ultimately get merged and added into Git.\n\nI agree that it feels like a \"moonshot\" / research project.\n\n> > My recommendation is that a GSoC student update the\n> > generation number to \"v2\" based on the definition you made in [1].\n> > That proposal is also more likely to be effective in Git because\n> > it makes use of extra heuristic information (commit date) to\n> > assist the types of algorithms we care about.\n> >\n> > In that case, the \"difficult\" part is moving the \"generation\"\n> > member of struct commit into a slab before making it a 64-bit\n> > value. (This is likely necessary for your plan, anyway.) Updating\n> > the generation number to v2 is relatively straight-forward after\n> > that, as someone can follow all places that reference or compute\n> > generation numbers and apply a diff\n>\n> Good idea! Though I am not sure if it is not too late to add it to the\n> https://git.github.io/SoC-2020-Ideas/ as the self imposed deadline of\n> March 16 (where students can start submitting proposals to GSoC) has\n> just passed. Christian, what do you think?\n\nWould that be a different project idea or part of your \"Graph labeling\nfor speeding up git commands\" project idea?\n\nI am very reluctant to add new project ideas at that time. I don't\nthink student will have time to properly research it and get it\nreviewed.\n\nIt could be part of your research project though, to check if that\napproach is better or good enough compared to what you suggest in the\ncurrent version of your project.\n\n> Would you agree, Stolee, to be a _possible_ mentor or co-mentor for\n> \"Generation number v2\" project?\n\nAt this point I think it might be best if you are both willing to\nco-mentor a \"moonshot\" / research project to find what is the best way\nforward by bench-marking the different approaches that you both\nsuggest for different commands/use cases.\n"},{"id":"393347","messageId":"d1572a9f-e665-f417-c6ee-28bc8d88d60c@gmail.com","threadId":"52965","inReplyTo":"CAP8UFD3BeS8bj8OGKJmVyKeDTCvqhCpBxLhTwuQ3zffejQkj7g@mail.gmail.com","subject":"Re: [RFC] Possible idea for GSoC 2020","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2020-03-17T11:49:07Z","receivedAt":"2020-03-17T11:49:13Z","isPatch":false,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 3/17/2020 3:24 AM, Christian Couder wrote:\n> On Tue, Mar 17, 2020 at 4:13 AM Jakub Narebski wrote:\n> It could be part of your research project though, to check if that\n> approach is better or good enough compared to what you suggest in the\n> current version of your project.\n> \n>> Would you agree, Stolee, to be a _possible_ mentor or co-mentor for\n>> \"Generation number v2\" project?\n> \n> At this point I think it might be best if you are both willing to\n> co-mentor a \"moonshot\" / research project to find what is the best way\n> forward by bench-marking the different approaches that you both\n> suggest for different commands/use cases.\n \nIf a student wants to take this on with the full expectation that they\nwill mostly be doing research and gathering data which _might_ result\nin an acceptable patch, then I could co-mentor.\n\nWith that expectation in mind, this project becomes closer to an REU\n(Research Experience for Undergraduates) than a software engineering\ninternship. Are we sure that fits into GSoC?\n\nThanks,\n-Stolee\n"},{"id":"393348","messageId":"d1a4998d-039f-65da-f18b-12ec714ec532@gmail.com","threadId":"52965","inReplyTo":"86zhch7kyz.fsf@gmail.com","subject":"Re: [RFC] Possible idea for GSoC 2020","fromName":"Kaartic Sivaraam","fromEmail":"kaartic.sivaraam@gmail.com","sentAt":"2020-03-17T12:24:27Z","receivedAt":"2020-03-17T12:25:25Z","isPatch":false,"sender":{"key":"kaartic.sivaraam@gmail.com","avatar":"https://avatars.githubusercontent.com/u/12448084?v=4"},"body":"Hi Jakub,\n\nOn 15-03-2020 19:56, Jakub Narebski wrote:\n> Jakub Narebski writes:\n>>\n>> I have prepared slides for \"Graph operations in Git version control\n>> system\" (PDF), mainly describing what was already done to improve their\n>> performance, but they also include a few thoughts about the future (like\n>> additional graph reachability labelings)... unfortunately the slides are\n>> in Polish, not in English.\n>>\n>> If there is interest, I could translate them, and put the result\n>> somewhere accessible.\n> \n> Here it is, traanslated into English, but otherwise almost exactly as I\n> have presented it on December 2019. Those slides includes much of\n> introductory information, so one would be interested probably in few\n> last slides (the \"Future work\" section).\n> \n> https://drive.google.com/file/d/1psMBVfcRHcZeJ7AewGpdoymrEfFVdXoK/view?usp=sharing\n> \n> I will be extending those slides with more information about interval\n> labeling, and then I will update the file, and I can post it also on\n> SlideShare (or other site, if one can recommend it).\n>\n\nJust wanted to note that Speaker deck[1] is a nice alternative to \nSlideShare. I've not uploaded slides to it but have seen people sharing \nslides using Speaker deck. I find the user interface to be more neat and \nminimalistic than SlideShare. FWIW, their mobile interface a lot better \nthan the SlideShare's interface.\n\n[1]: https://speakerdeck.com/\n\n-- \nSivaraam\n"},{"id":"393349","messageId":"6158e62f-ad7a-c3cc-5e5d-9fde5d9ba34c@gmail.com","threadId":"52965","inReplyTo":"d1a4998d-039f-65da-f18b-12ec714ec532@gmail.com","subject":"Re: [RFC] Possible idea for GSoC 2020","fromName":"Kaartic Sivaraam","fromEmail":"kaartic.sivaraam@gmail.com","sentAt":"2020-03-17T12:39:37Z","receivedAt":"2020-03-17T12:40:35Z","isPatch":false,"sender":{"key":"kaartic.sivaraam@gmail.com","avatar":"https://avatars.githubusercontent.com/u/12448084?v=4"},"body":"On 17-03-2020 17:54, Kaartic Sivaraam wrote:\n>> I will be extending those slides with more information about interval\n>> labeling, and then I will update the file, and I can post it also on\n>> SlideShare (or other site, if one can recommend it).\n>>\n> \n> Just wanted to note that Speaker deck[1] is a nice alternative to \n> SlideShare. I've not uploaded slides to it but have seen people sharing \n> slides using Speaker deck. I find the user interface to be more neat and \n> minimalistic than SlideShare. FWIW, their mobile interface a lot better \n> than the SlideShare's interface.\n> \n\nOh, and forgot to mention that you can also share links to a specific \nslide like this:\n\nhttps://speakerdeck.com/lemire/parsing-json-really-quickly-lessons-learned?slide=13\n\nI'm really surprised to realize that SlideShare doesn't have an option \nto do this.\n\n-- \nSivaraam\n"},{"id":"393354","messageId":"867dzj6p4y.fsf@gmail.com","threadId":"52965","inReplyTo":"CAP8UFD3BeS8bj8OGKJmVyKeDTCvqhCpBxLhTwuQ3zffejQkj7g@mail.gmail.com","subject":"Re: [RFC] Possible idea for GSoC 2020","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2020-03-17T14:18:37Z","receivedAt":"2020-03-17T14:18:48Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Christian Couder writes:\n> On Tue, Mar 17, 2020 at 4:13 AM Jakub Narebski wrote:\n>\n> [...]\n>\n>>>> ### Graph labelling for speeding up git commands\n>\n> [...]\n>\n>>> We already have the second inequality (f(u) <= f(v)) where the function\n>>> 'f' is the generation of v. The success of this approach over generation\n>>> numbers relies entirely on how often the inequality min_graph(v) <= post(u)\n>>> fails when gen(u) <= gen(v) holds.\n>>\n>> True. It may turn out that additional negative-cut filters do not bring\n>> enough performance improvements over topological levels or corrected\n>> commit date (or monotonically increasing corrected commit date) to be\n>> worth it.\n>>\n>> I think they can help in wide commit graphs (many concurrently developed\n>> branches with many commits and few merges), and when there is orphan\n>> branch (like 'todo' in the git.git, or 'gh-pages' for storing\n>> per-project GitHub Pages) that is somehow entangled in query.\n>>\n>>>> If for each commit 'v' we would compute and store in the commit-graph\n>>>> file two numbers: 'post(v)' and the minimum of 'post(u)' for commits\n>>>> that were visited during the part of depth-first search that started\n>>>> from 'v' (which is the minimum of post-order number for subtree of a\n>>>> spanning tree that starts at 'v'). Let's call the later 'min_tree(v)'.\n>>>> Then the following condition is true:\n>>>>\n>>>> if min_tree(v) <= post(u) <= post(v), then 'v' can reach 'u'\n>>>\n>>> How many places in Git do we ask \"can v reach u?\" and how many would\n>>> return immediately without needing a walk in this new approach? My\n>>> guess is that we will have a very narrow window where this query\n>>> returns a positive result.\n>>\n>> As I wrote below, such positive-cut filter would be directly helpful in\n>> performing the following commands:\n>>\n>> - `git merge-base --is-ancestor`\n>> - `git branch --contains`\n>> - `git tag --contains`\n>> - `git branch --merged`\n>> - `git tag --merged`\n>>\n>> It would be also useful for tag autofollow in git-fetch; is is N-to-M\n>> equivalent to 1-to-N / N-to-1 `--contains` queries.\n>>\n>> I am quite sure that positive-cut filter would make `--ancestry-path`\n>> walk faster.\n>>\n>> I think, but I am not sure, that positive-cut filter can make parts of\n>> topological sort and merge base algorithms at least a tiny bit faster.\n>\n> Is there an easy way to check that it would provide significant\n> performance improvements at least in some cases? Can we ask the\n> student to do that at the beginning of the GSoC?\n\nThe \"Reachability labels for version control graphs.ipynb\" Jupyter\nNotebook on Google Colaboratory was created to answer this question\n(originally for the FELINE reachability index). Among others it can\nmin-post interval labels and topological levels (generation numbers),\nuse them for reachability queries, and load Linux kernel\ncommit-graph. The exploration didn't get finished, but it would be not\nthat difficult, I think, to at least find the amount of false negatives\nfor min-post interval labeling for git.git or Linux kernel repo.\n\n https://colab.research.google.com/drive/1V-U7_slu5Z3s5iEEMFKhLXtaxSu5xyzg\n\nAs Jupyter Notebook, it is run in the web browser. It can either use\nlocal runtime, or run on Google Cloud runtime. On the other hand it\nrequires at least some knowledge of Python...\n\n>>> I believe we discussed this concept briefly when planning \"generation\n>>> number v2\" and the main concern I have with this plan is that the\n>>> values are not stable. The value of post(v) and min_tree(v) depend\n>>> on the entire graph as a whole, not just what is reachable from v\n>>> (and preferably only the parents of v).\n>>>\n>>> Before starting to implement this, I would consider how such labels\n>>> could be computed across incremental commit-graph boundaries. That is,\n>>> if I'm only adding a layer of commits to the commit-graph without\n>>> modifying the existing layers of the commit-graph chain, can I still\n>>> compute values with these properties? How expensive is it? Do I need\n>>> to walk the entire reachable set of commits?\n>>\n>> I think it would be possible to compute post(v) and min_tree(v) using\n>> incremental updates, and to make it compatibile with incremental\n>> commit-graph format (with the commit-graph chain). But I have not\n>> proven it.\n>\n> Would it be difficult to prove? What would be required? And again can\n> we ask the student to do that at the beginning of the GSoC?\n\nFormal mathematical proof by induction would be not that difficult. The\nproblem is, I think, in finding all possible classes of initial spanning\nforest arrangements, and all possible classes of commit-graph growth by\none commit -- and examining how this affect the spanning forest.\n\n> [...]\n>\n>>> The point of generation number v2 [1] was to allow moving to \"exact\"\n>>> algorithms for things like merge-base where we still use commit time\n>>> as a heuristic, and could be wrong because of special data shapes.\n>>> We don't use generation number in these examples because using only\n>>> generation number can lead to a large increase in number of commits\n>>> walked. The example we saw in the Linux kernel repository was a bug\n>>> fix created on top of a very old commit, so there was a commit of\n>>> low generation with very high commit-date that caused extra walking.\n>>> (See [2] for a detailed description of the data shape.)\n>>>\n>>> My _prediction_ is that the two-dimensional system will be more\n>>> complicated to write and use, and will not have any measurable\n>>> difference. I'd be happy to be wrong, but I also would not send\n>>> anyone down this direction only to find out I'm right and that\n>>> effort was wasted.\n>>\n>> That might be a problem.\n>>\n>> This is a bit of a \"moonshot\" / research project, moreso than others.\n>> Though it would be still valuable, in my opionion, even if the code\n>> wouldn't ultimately get merged and added into Git.\n>\n> I agree that it feels like a \"moonshot\" / research project.\n>\n>>> My recommendation is that a GSoC student update the\n>>> generation number to \"v2\" based on the definition you made in [1].\n>>> That proposal is also more likely to be effective in Git because\n>>> it makes use of extra heuristic information (commit date) to\n>>> assist the types of algorithms we care about.\n>>>\n>>> In that case, the \"difficult\" part is moving the \"generation\"\n>>> member of struct commit into a slab before making it a 64-bit\n>>> value. (This is likely necessary for your plan, anyway.) Updating\n>>> the generation number to v2 is relatively straight-forward after\n>>> that, as someone can follow all places that reference or compute\n>>> generation numbers and apply a diff\n>>\n>> Good idea! Though I am not sure if it is not too late to add it to the\n>> https://git.github.io/SoC-2020-Ideas/ as the self imposed deadline of\n>> March 16 (where students can start submitting proposals to GSoC) has\n>> just passed. Christian, what do you think?\n>\n> Would that be a different project idea or part of your \"Graph labeling\n> for speeding up git commands\" project idea?\n>\n> I am very reluctant to add new project ideas at that time. I don't\n> think student will have time to properly research it and get it\n> reviewed.\n>\n> It could be part of your research project though, to check if that\n> approach is better or good enough compared to what you suggest in the\n> current version of your project.\n>\n>> Would you agree, Stolee, to be a _possible_ mentor or co-mentor for\n>> \"Generation number v2\" project?\n>\n> At this point I think it might be best if you are both willing to\n> co-mentor a \"moonshot\" / research project to find what is the best way\n> forward by bench-marking the different approaches that you both\n> suggest for different commands/use cases.\n\nSo perhaps we should expand \"Commit graph labeling for speeding up git\ncommands\" idea, splitting it into two possible ways of working in this\nproject: the more technical 'Generation number v2', and 'Interval labels\nfor commit graph' which is more of research project? Which should be\nput first, then?\n\nNote that for example \"Convert scripts to builtins\" idea is in similar\nsituation: it is also many projects in one.\n\nRegards,\n-- \nJakub Narębski\n"},{"id":"393355","messageId":"861rpr6oy8.fsf@gmail.com","threadId":"52965","inReplyTo":"d1a4998d-039f-65da-f18b-12ec714ec532@gmail.com","subject":"Re: [RFC] Possible idea for GSoC 2020","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2020-03-17T14:22:39Z","receivedAt":"2020-03-17T14:22:45Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Hello,\n\nKaartic Sivaraam writes:\n> On 15-03-2020 19:56, Jakub Narebski wrote:\n>> Jakub Narebski writes:\n>>>\n>>> I have prepared slides for \"Graph operations in Git version control\n>>> system\" (PDF), mainly describing what was already done to improve their\n>>> performance, but they also include a few thoughts about the future (like\n>>> additional graph reachability labelings)... unfortunately the slides are\n>>> in Polish, not in English.\n>>>\n>>> If there is interest, I could translate them, and put the result\n>>> somewhere accessible.\n>>\n>> Here it is, traanslated into English, but otherwise almost exactly as I\n>> have presented it on December 2019. Those slides includes much of\n>> introductory information, so one would be interested probably in few\n>> last slides (the \"Future work\" section).\n>>\n>> https://drive.google.com/file/d/1psMBVfcRHcZeJ7AewGpdoymrEfFVdXoK/view?usp=sharing\n>>\n>> I will be extending those slides with more information about interval\n>> labeling, and then I will update the file, and I can post it also on\n>> SlideShare (or other site, if one can recommend it).\n>>\n>\n> Just wanted to note that Speaker deck[1] is a nice alternative to\n> SlideShare. I've not uploaded slides to it but have seen people\n> sharing slides using Speaker deck. I find the user interface to be\n> more neat and minimalistic than SlideShare. FWIW, their mobile\n> interface a lot better than the SlideShare's interface.\n>\n> [1]: https://speakerdeck.com/\n\nThanks for the suggestion. The slides (which are at version 1.2) are\nnow also available on SlideShare[2] and on SpeakerDeck[3], in addition\nto being on Google Drive:\n\n[2]: https://www.slideshare.net/JakubNarbski/graph-operations-in-git-version-control-system-how-the-performance-was-improved-for-large-repositories-how-can-it-be-further-improved\n[3]: https://speakerdeck.com/jnareb/graph-operations-in-git-slides-2019\n\nThe only disadvantage with SpeakerDeck is that bitmap images (PNG, JPEG)\nare a bit blocky/pixelated in HTML-ized version of slides.\n\nP.S. I am not sure if I put my slids in correct category...\n-- \nJakub Narębski\n"},{"id":"393360","messageId":"CAP8UFD1ihR1PtM2y24HTKa2woGXMVFq9MoVSj1cHVZCNWSH7EA@mail.gmail.com","threadId":"52965","inReplyTo":"867dzj6p4y.fsf@gmail.com","subject":"Re: [RFC] Possible idea for GSoC 2020","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2020-03-17T17:04:23Z","receivedAt":"2020-03-17T17:04:40Z","isPatch":false,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"On Tue, Mar 17, 2020 at 3:18 PM Jakub Narebski wrote:\n>\n> Christian Couder writes:\n> > On Tue, Mar 17, 2020 at 4:13 AM Jakub Narebski wrote:\n\n> >>>> If for each commit 'v' we would compute and store in the commit-graph\n> >>>> file two numbers: 'post(v)' and the minimum of 'post(u)' for commits\n> >>>> that were visited during the part of depth-first search that started\n> >>>> from 'v' (which is the minimum of post-order number for subtree of a\n> >>>> spanning tree that starts at 'v'). Let's call the later 'min_tree(v)'.\n> >>>> Then the following condition is true:\n> >>>>\n> >>>> if min_tree(v) <= post(u) <= post(v), then 'v' can reach 'u'\n> >>>\n> >>> How many places in Git do we ask \"can v reach u?\" and how many would\n> >>> return immediately without needing a walk in this new approach? My\n> >>> guess is that we will have a very narrow window where this query\n> >>> returns a positive result.\n> >>\n> >> As I wrote below, such positive-cut filter would be directly helpful in\n> >> performing the following commands:\n> >>\n> >> - `git merge-base --is-ancestor`\n> >> - `git branch --contains`\n> >> - `git tag --contains`\n> >> - `git branch --merged`\n> >> - `git tag --merged`\n> >>\n> >> It would be also useful for tag autofollow in git-fetch; is is N-to-M\n> >> equivalent to 1-to-N / N-to-1 `--contains` queries.\n> >>\n> >> I am quite sure that positive-cut filter would make `--ancestry-path`\n> >> walk faster.\n> >>\n> >> I think, but I am not sure, that positive-cut filter can make parts of\n> >> topological sort and merge base algorithms at least a tiny bit faster.\n> >\n> > Is there an easy way to check that it would provide significant\n> > performance improvements at least in some cases? Can we ask the\n> > student to do that at the beginning of the GSoC?\n>\n> The \"Reachability labels for version control graphs.ipynb\" Jupyter\n> Notebook on Google Colaboratory was created to answer this question\n> (originally for the FELINE reachability index). Among others it can\n> min-post interval labels and topological levels (generation numbers),\n> use them for reachability queries, and load Linux kernel\n> commit-graph. The exploration didn't get finished, but it would be not\n> that difficult, I think, to at least find the amount of false negatives\n> for min-post interval labeling for git.git or Linux kernel repo.\n>\n> https://colab.research.google.com/drive/1V-U7_slu5Z3s5iEEMFKhLXtaxSu5xyzg\n>\n> As Jupyter Notebook, it is run in the web browser. It can either use\n> local runtime, or run on Google Cloud runtime. On the other hand it\n> requires at least some knowledge of Python...\n\nOk, if that's a possible approach to the project, then please add it\nto the description.\n\n> >> I think it would be possible to compute post(v) and min_tree(v) using\n> >> incremental updates, and to make it compatibile with incremental\n> >> commit-graph format (with the commit-graph chain). But I have not\n> >> proven it.\n> >\n> > Would it be difficult to prove? What would be required? And again can\n> > we ask the student to do that at the beginning of the GSoC?\n>\n> Formal mathematical proof by induction would be not that difficult. The\n> problem is, I think, in finding all possible classes of initial spanning\n> forest arrangements, and all possible classes of commit-graph growth by\n> one commit -- and examining how this affect the spanning forest.\n\nOk.\n\n> >>> The point of generation number v2 [1] was to allow moving to \"exact\"\n> >>> algorithms for things like merge-base where we still use commit time\n> >>> as a heuristic, and could be wrong because of special data shapes.\n> >>> We don't use generation number in these examples because using only\n> >>> generation number can lead to a large increase in number of commits\n> >>> walked. The example we saw in the Linux kernel repository was a bug\n> >>> fix created on top of a very old commit, so there was a commit of\n> >>> low generation with very high commit-date that caused extra walking.\n> >>> (See [2] for a detailed description of the data shape.)\n> >>>\n> >>> My _prediction_ is that the two-dimensional system will be more\n> >>> complicated to write and use, and will not have any measurable\n> >>> difference. I'd be happy to be wrong, but I also would not send\n> >>> anyone down this direction only to find out I'm right and that\n> >>> effort was wasted.\n> >>\n> >> That might be a problem.\n> >>\n> >> This is a bit of a \"moonshot\" / research project, moreso than others.\n> >> Though it would be still valuable, in my opionion, even if the code\n> >> wouldn't ultimately get merged and added into Git.\n> >\n> > I agree that it feels like a \"moonshot\" / research project.\n> >\n> >>> My recommendation is that a GSoC student update the\n> >>> generation number to \"v2\" based on the definition you made in [1].\n> >>> That proposal is also more likely to be effective in Git because\n> >>> it makes use of extra heuristic information (commit date) to\n> >>> assist the types of algorithms we care about.\n> >>>\n> >>> In that case, the \"difficult\" part is moving the \"generation\"\n> >>> member of struct commit into a slab before making it a 64-bit\n> >>> value. (This is likely necessary for your plan, anyway.) Updating\n> >>> the generation number to v2 is relatively straight-forward after\n> >>> that, as someone can follow all places that reference or compute\n> >>> generation numbers and apply a diff\n> >>\n> >> Good idea! Though I am not sure if it is not too late to add it to the\n> >> https://git.github.io/SoC-2020-Ideas/ as the self imposed deadline of\n> >> March 16 (where students can start submitting proposals to GSoC) has\n> >> just passed. Christian, what do you think?\n> >\n> > Would that be a different project idea or part of your \"Graph labeling\n> > for speeding up git commands\" project idea?\n> >\n> > I am very reluctant to add new project ideas at that time. I don't\n> > think student will have time to properly research it and get it\n> > reviewed.\n> >\n> > It could be part of your research project though, to check if that\n> > approach is better or good enough compared to what you suggest in the\n> > current version of your project.\n> >\n> >> Would you agree, Stolee, to be a _possible_ mentor or co-mentor for\n> >> \"Generation number v2\" project?\n> >\n> > At this point I think it might be best if you are both willing to\n> > co-mentor a \"moonshot\" / research project to find what is the best way\n> > forward by bench-marking the different approaches that you both\n> > suggest for different commands/use cases.\n>\n> So perhaps we should expand \"Commit graph labeling for speeding up git\n> commands\" idea, splitting it into two possible ways of working in this\n> project: the more technical 'Generation number v2', and 'Interval labels\n> for commit graph' which is more of research project?\n\nOk for that.\n\n> Which should be\n> put first, then?\n\nWhich ever you prefer. If you say that any part could be done\nseparately, that doesn't matter much.\n\nBest,\nChristian.\n"},{"id":"393394","messageId":"86mu8d6a39.fsf@gmail.com","threadId":"52965","inReplyTo":"CAP8UFD1ihR1PtM2y24HTKa2woGXMVFq9MoVSj1cHVZCNWSH7EA@mail.gmail.com","subject":"Re: [RFC] Possible idea for GSoC 2020","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2020-03-18T13:55:54Z","receivedAt":"2020-03-18T13:56:04Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Christian Couder writes:\n> On Tue, Mar 17, 2020 at 3:18 PM Jakub Narebski wrote:\n>> Christian Couder writes:\n>>> On Tue, Mar 17, 2020 at 4:13 AM Jakub Narebski wrote:\n[...]\n>>>> As I wrote below, such positive-cut filter would be directly helpful in\n>>>> performing the following commands:\n>>>>\n>>>> - `git merge-base --is-ancestor`\n>>>> - `git branch --contains`\n>>>> - `git tag --contains`\n>>>> - `git branch --merged`\n>>>> - `git tag --merged`\n>>>>\n>>>> It would be also useful for tag autofollow in git-fetch; is is N-to-M\n>>>> equivalent to 1-to-N / N-to-1 `--contains` queries.\n>>>>\n>>>> I am quite sure that positive-cut filter would make `--ancestry-path`\n>>>> walk faster.\n>>>>\n>>>> I think, but I am not sure, that positive-cut filter can make parts of\n>>>> topological sort and merge base algorithms at least a tiny bit faster.\n>>>\n>>> Is there an easy way to check that it would provide significant\n>>> performance improvements at least in some cases? Can we ask the\n>>> student to do that at the beginning of the GSoC?\n>>\n>> The \"Reachability labels for version control graphs.ipynb\" Jupyter\n>> Notebook on Google Colaboratory was created to answer this question\n>> (originally for the FELINE reachability index). Among others it can\n>> min-post interval labels and topological levels (generation numbers),\n>> use them for reachability queries, and load Linux kernel\n>> commit-graph. The exploration didn't get finished, but it would be not\n>> that difficult, I think, to at least find the amount of false negatives\n>> for min-post interval labeling for git.git or Linux kernel repo.\n>>\n>> https://colab.research.google.com/drive/1V-U7_slu5Z3s5iEEMFKhLXtaxSu5xyzg\n>>\n>> As Jupyter Notebook, it is run in the web browser. It can either use\n>> local runtime, or run on Google Cloud runtime. On the other hand it\n>> requires at least some knowledge of Python...\n>\n> Ok, if that's a possible approach to the project, then please add it\n> to the description.\n\nAdded as a new paragraph in the 'interval labels' subtask description\nhttps://github.com/git/git.github.io/commit/ac526b18b97e53a431767ce147f27eaf6af0aa76\n\n[...]\n>>>>> My recommendation is that a GSoC student update the\n>>>>> generation number to \"v2\" based on the definition you made in [1].\n>>>>> That proposal is also more likely to be effective in Git because\n>>>>> it makes use of extra heuristic information (commit date) to\n>>>>> assist the types of algorithms we care about.\n>>>>>\n>>>>> In that case, the \"difficult\" part is moving the \"generation\"\n>>>>> member of struct commit into a slab before making it a 64-bit\n>>>>> value. (This is likely necessary for your plan, anyway.) Updating\n>>>>> the generation number to v2 is relatively straight-forward after\n>>>>> that, as someone can follow all places that reference or compute\n>>>>> generation numbers and apply a diff\n>>>>\n>>>> Good idea! Though I am not sure if it is not too late to add it to the\n>>>> https://git.github.io/SoC-2020-Ideas/ as the self imposed deadline of\n>>>> March 16 (where students can start submitting proposals to GSoC) has\n>>>> just passed. Christian, what do you think?\n>>>\n>>> Would that be a different project idea or part of your \"Graph labeling\n>>> for speeding up git commands\" project idea?\n>>>\n>>> I am very reluctant to add new project ideas at that time. I don't\n>>> think student will have time to properly research it and get it\n>>> reviewed.\n[...]\n\n>> So perhaps we should expand \"Commit graph labeling for speeding up git\n>> commands\" idea, splitting it into two possible ways of working in this\n>> project: the more technical 'Generation number v2', and 'Interval labels\n>> for commit graph' which is more of research project?\n>\n> Ok for that.\n>\n>> Which should be\n>> put first, then?\n>\n> Which ever you prefer. If you say that any part could be done\n> separately, that doesn't matter much.\n\nI have added 'Generation number v2' as one of alternative ways of\nworking on the more generic \"Commit graph labeling for speeding up git\ncommands\" idea -- as first task, because it fit better the narrative:\nhttps://github.com/git/git.github.io/commit/a6d59820709417081c334a5120342987ff046f1a\n\nCould you (or Stolee) check current proposal, so that it can be merged\nin? Thanks in advance.\n\n https://github.com/git/git.github.io/blob/soc-2020-idea-jnareb/SoC-2020-Ideas.md\n\nBest,\n-- \nJakub Narębski\n"},{"id":"393398","messageId":"4c063495-0b01-dd0d-eb87-61e31a774cde@gmail.com","threadId":"52965","inReplyTo":"86mu8d6a39.fsf@gmail.com","subject":"Re: [RFC] Possible idea for GSoC 2020","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2020-03-18T15:25:42Z","receivedAt":"2020-03-18T15:25:49Z","isPatch":false,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 3/18/2020 9:55 AM, Jakub Narebski wrote:\n> I have added 'Generation number v2' as one of alternative ways of\n> working on the more generic \"Commit graph labeling for speeding up git\n> commands\" idea -- as first task, because it fit better the narrative:\n> https://github.com/git/git.github.io/commit/a6d59820709417081c334a5120342987ff046f1a\n> \n> Could you (or Stolee) check current proposal, so that it can be merged\n> in? Thanks in advance.\n> \n> https://github.com/git/git.github.io/blob/soc-2020-idea-jnareb/SoC-2020-Ideas.md\n\nThanks for the updated write-up. I think the narrative is helpful, describing how\nwe landed on the definition of \"generation number v2\" before going into the interval\nmethods.\n\nThe only comment I have is about this statement at the end, which seems to be a\ncarry-over from your perspective of wanting intervals instead of v2:\n\n\tBefore starting on this task, at the beginning of the GSoC, it might be\n\t[a (sic)] good idea to check that interval labels would provide significant\n\tperformance improvements at least in some cases (and if it is not the case,\n\tswitch to working on generation numbers v2).\n\nThe final parenthetical (switch to working on...) is a bit presumptive. Instead,\nplease recommend an exploration period to determine which methods have which\nperformance improvements using prototypes and/or the Python notebook. I'm usually\nof the opinion that a prototype is more informative as it compares the results in\ncontext, and the student would learn about the code that needs to change before\ncreating review-quality patches.\n\nThanks,\n-Stolee\n"},{"id":"393444","messageId":"868sjw5wxp.fsf@gmail.com","threadId":"52965","inReplyTo":"4c063495-0b01-dd0d-eb87-61e31a774cde@gmail.com","subject":"Re: [RFC] Possible idea for GSoC 2020","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2020-03-19T12:52:18Z","receivedAt":"2020-03-19T12:52:24Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Derrick Stolee writes:\n> On 3/18/2020 9:55 AM, Jakub Narebski wrote:\n\n>> I have added 'Generation number v2' as one of alternative ways of\n>> working on the more generic \"Commit graph labeling for speeding up git\n>> commands\" idea -- as first task, because it fit better the narrative:\n>> https://github.com/git/git.github.io/commit/a6d59820709417081c334a5120342987ff046f1a\n>> \n>> Could you (or Stolee) check current proposal, so that it can be merged\n>> in? Thanks in advance.\n>> \n>> https://github.com/git/git.github.io/blob/soc-2020-idea-jnareb/SoC-2020-Ideas.md\n>\n> Thanks for the updated write-up. I think the narrative is helpful, describing how\n> we landed on the definition of \"generation number v2\" before going into the interval\n> methods.\n>\n> The only comment I have is about this statement at the end, which seems to be a\n> carry-over from your perspective of wanting intervals instead of v2:\n>\n> \tBefore starting on this task, at the beginning of the GSoC, it might be\n> \t[a (sic)] good idea to check that interval labels would provide significant\n> \tperformance improvements at least in some cases (and if it is not the case,\n> \tswitch to working on generation numbers v2).\n>\n> The final parenthetical (switch to working on...) is a bit presumptive. Instead,\n> please recommend an exploration period to determine which methods have which\n> performance improvements using prototypes and/or the Python notebook. I'm usually\n> of the opinion that a prototype is more informative as it compares the results in\n> context, and the student would learn about the code that needs to change before\n> creating review-quality patches.\n\nThanks, I took it into account in the final version\n\n https://git.github.io/SoC-2020-Ideas/\n\nBest,\n-- \nJakub Narębski\n"}]}