{"thread":{"id":"53012","subject":"Re: [RFC] Possible idea for GSoC 2020","startedAt":"2020-03-17T18:00:33Z","lastAt":"2020-03-19T12:50:08Z","messageCount":2,"participants":["Abhishek Kumar","Jakub Narebski"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"393364","messageId":"CAHk66fv-fRZdUFC978sKUT_b7VYi6S2f2vdTQ6iB-wcCznnBHg@mail.gmail.com","threadId":"53012","inReplyTo":null,"subject":"Re: [RFC] Possible idea for GSoC 2020","fromName":"Abhishek Kumar","fromEmail":"abhishekkumar8222@gmail.com","sentAt":"2020-03-17T18:00:00Z","receivedAt":"2020-03-17T18:00:33Z","isPatch":false,"sender":{"key":"abhishekkumar8222@gmail.com","avatar":"https://avatars.githubusercontent.com/u/31231064?v=4"},"body":"Greetings Jakub\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?  Which should be\n> put first, then?\n\nI would suggest working on generation number v2 first because:\n- We ship improved performance *sooner*.\n- I find it easier to shift from simpler to more complex systems.\n\nOn a personal note, I would be able to do a better job at working on generation\nnumber v2 than on interval labels. While reading through the papers mentioned\nwas fun and full of a-ha moments, I find building things more\nfulfilling. I would be\nglad if either you or Derrick opt for mentoring it.\n\nYou could read my proposal at the link below. It is very rough and I haven't\nproofread it yet. I will send out a more formal proposal once the direction\nof this project is decided.\n\nhttps://github.com/abhishekkumar2718/GSoC20/blob/master/graph_labelling.md\n\n**Too long, didn't read**\n\n- Commit graphs are small to medium-sized (compared to problem sizes observed in\ngraph-theory literature) sparse graphs. They have unusual properties compared\nto more conventional graphs that can be exploited for better performance.\n\n- Most of git's reachability queries are negative and using a negative-cut\nfilter improves performance more than a positive-cut filter.\n\n- Implementing and maintaining a two-dimensional reachability index is hard\nand does not offer justifiable performance gains.\n\n- We plan to use corrected commit date as the generation number v2 because it is\nlocally computable, immutable and can be incrementally updated.\n\n- If git ever considers a two-dimensional reachability index, either post order\nDFS, GRAIL or an index based on commit date would be good starting\nplaces to explore.\n\nI go in more details about GRAIL, FERRARI and PReaCH, explaining\nbriefly how they work, their advantages, and disadvantages.\n\n> Note that for example \"Convert scripts to builtins\" idea is in similar\n> situation: it is also many projects in one.\n\nRegards\nAbhishek\n"},{"id":"393443","messageId":"86eeto5x1j.fsf@gmail.com","threadId":"53012","inReplyTo":"CAHk66fv-fRZdUFC978sKUT_b7VYi6S2f2vdTQ6iB-wcCznnBHg@mail.gmail.com","subject":"Re: [RFC] Possible idea for GSoC 2020","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2020-03-19T12:50:00Z","receivedAt":"2020-03-19T12:50:08Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Abhishek Kumar <abhishekkumar8222@gmail.com> writes:\n\n> Greetings Jakub\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?  Which should be\n>> put first, then?\n>\n> I would suggest working on generation number v2 first because:\n> - We ship improved performance *sooner*.\n> - I find it easier to shift from simpler to more complex systems.\n\nIt would be also more of an engineering project, than research one.\n\n> On a personal note, I would be able to do a better job at working on generation\n> number v2 than on interval labels. While reading through the papers mentioned\n> was fun and full of a-ha moments, I find building things more\n> fulfilling. I would be glad if either you or Derrick opt for mentoring it.\n\nAll right.  I have added 'Generation number v2' as possible way of\nworking on the \"Commit graph labeling for speeding up git commands\"\nidea.\n\nhttps://git.github.io/SoC-2020-Ideas/#commit-graph-labeling-for-speeding-up-git-commands\n\n\n> You could read my proposal at the link below. It is very rough and I haven't\n> proofread it yet. I will send out a more formal proposal once the direction\n> of this project is decided.\n>\n> https://github.com/abhishekkumar2718/GSoC20/blob/master/graph_labelling.md\n>\n> **Too long, didn't read**\n\nI will comment only on the TLDR version below.\n\n> - Commit graphs are small to medium-sized (compared to problem sizes observed in\n> graph-theory literature) sparse graphs. They have unusual properties compared\n> to more conventional graphs that can be exploited for better performance.\n\nRight.\n\n> - Most of git's reachability queries are negative and using a negative-cut\n> filter improves performance more than a positive-cut filter.\n\nNot exactly.  Most time consuming git graph queries are those that\nreturn a subgraph or otherwise need to walk the commit graph (like\ntopological sorting, or ahead/behind numbers).  Here in most cases\nnegative-cut filters, that reduce the number of commits walked, improve\nperformance more (with rare exceptions, like --ancestry-path query).\n\nThat is what I think, but it is not something I have proven...\n\n> - Implementing and maintaining a two-dimensional reachability index is hard\n> and does not offer justifiable performance gains.\n\nI think it would be better to not mention graph reachability algorithms\nat all, and just talk about generation number v2 as straight performance\nimprovement over generation number v1.\n\n> - We plan to use corrected commit date as the generation number v2 because it is\n> locally computable, immutable and can be incrementally updated.\n\nUnfortunately because of an oopsie with respect to commit-graph file\nformat versioning, at least for the time being generation number v2\nneeds to be also backward compatibile with generation number v1.  See\nfor example:\n  https://git.github.io/rev_news/2019/06/28/edition-52/#reviews\n  https://speakerdeck.com/jnareb/graph-operations-in-git-and-how-to-make-them-faster?slide=74\n\n>\n> - If git ever considers a two-dimensional reachability index, either post order\n> DFS, GRAIL or an index based on commit date would be good starting\n> places to explore.\n>\n> I go in more details about GRAIL, FERRARI and PReaCH, explaining\n> briefly how they work, their advantages, and disadvantages.\n\nAgain, I don't think that is necessary.\n\nBest,\n-- \nJakub Narębski\n"}]}