{"thread":{"id":"53011","subject":"Re: [RFC] Possible idea for GSoC 2020","startedAt":"2020-03-17T17:00:47Z","lastAt":"2020-03-17T18:05:44Z","messageCount":2,"participants":["Abhishek Kumar","Jakub Narebski"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"393359","messageId":"CAHk66ftx=XTSeVcPe09yA9KMDpHwiKFLKa62cCBFufjeenAbaQ@mail.gmail.com","threadId":"53011","inReplyTo":null,"subject":"Re: [RFC] Possible idea for GSoC 2020","fromName":"Abhishek Kumar","fromEmail":"abhishekkumar8222@gmail.com","sentAt":"2020-03-17T17:00:00Z","receivedAt":"2020-03-17T17:00:47Z","isPatch":false,"sender":{"key":"abhishekkumar8222@gmail.com","avatar":"https://avatars.githubusercontent.com/u/31231064?v=4"},"body":"> 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>\n> [...]\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\nAgreed. I have been through the papers of the involved variants and on graphs\ncomparable to some of the largest git repositories, the performance improves by\nfifty nanoseconds for a random query.\n\nAdditionally:\n1. They require significantly more space per commit.\n2. They require significantly more preprocessing time.\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\nThanks for the recommendation. Reading about how this fits in more\nwith REU on the other thread, I too agree that updating generation\nnumber to use corrected commit date would be more appropriate for a GSoC\nproject.\n\nRegards\nAbhishek\n"},{"id":"393365","messageId":"86sgi66emm.fsf@gmail.com","threadId":"53011","inReplyTo":"CAHk66ftx=XTSeVcPe09yA9KMDpHwiKFLKa62cCBFufjeenAbaQ@mail.gmail.com","subject":"Re: [RFC] Possible idea for GSoC 2020","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2020-03-17T18:05:37Z","receivedAt":"2020-03-17T18:05:44Z","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>> 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>>\n>> [...]\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> Agreed. I have been through the papers of the involved variants and on graphs\n> comparable to some of the largest git repositories, the performance improves by\n> fifty nanoseconds for a random query.\n\nI would recommend extending results for other types of large graphs to\nthe commit graphs with care.  The characteristics of those graphs are\nquite different from characteristics of commit graph: they usually are\nscale-free graphs, with low maximum level, and low connectivity: the\nprobability of two random nodes being connected in order of 10^-3 or\n10^-4; see e.g. https://speakerdeck.com/jnareb/graph-operations-in-git-and-how-to-make-them-faster?slide=99\n\nThe last one, called R-ratio, means that testing on random query\nactually tests mainly negative-cut filters.  That is why some papers\nprovide either separate numbers for negative and for positive queries,\nor separate numbers for random and for balanced queries.\n\n> Additionally:\n> 1. They require significantly more space per commit.\n\nThis depends on the type of the algorithm: is it Label-Only (answering\nreachability queries without consulting graph), or Label+Graph\n(augmented online search algorithms):\nhttps://speakerdeck.com/jnareb/graph-operations-in-git-and-how-to-make-them-faster?slide=78\n\nThe CDAT chunk in current version of commit-graph format takes H+16\nbytes per commit (where H is the size of object id hash).  From those\nH+16 bytes 30 bits (slightly less that 4 bytes) are used for current\nreachability label: the topological level aka generation number.\nhttps://speakerdeck.com/jnareb/graph-operations-in-git-and-how-to-make-them-faster?slide=45\n\nThe proposed min-post interval label would take 8 bytes per commit, that\nis 4 bytes per single number in interval.  That is not much, provided\nthat we get visible performance improvements for at least some often\nused git commands.\n\n\n> 2. They require significantly more preprocessing time.\n\nThis again depends on the type of algorithm: Label-Only or Label+G.\n\nIn the case of min-post interval labels, they can be computed together\nwith generation number, during the same commit-graph walk.  The amount\nof calculations required to compute min-post interval is not much.\nTherefore I think it would be not unreasonable cost.\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> Thanks for the recommendation. Reading about how this fits in more\n> with REU on the other thread, I too agree that updating generation\n> number to use corrected commit date would be more appropriate for a GSoC\n> project.\n\nYou can read about monotonically offset corrected commit date for\nexample on my slides, from page 64 (the problem) to 75 (references):\nhttps://speakerdeck.com/jnareb/graph-operations-in-git-and-how-to-make-them-faster?slide=64\n\nI'll try to update the proposal on SoC 2020 Ideas page soon, perhaps\ntomorrow when I will have more free time.\n\nhttps://git.github.io/SoC-2020-Ideas/\n\nIn the meantime I will refer to what is written at the top of it:\n\n> **Students:** Please consider these ideas as starting points for\n> generating proposals. We are also more than happy to receive proposals\n> for other ideas related to Git. Make sure you have read the “Note\n> about refactoring projects versus projects that implement new\n> features” in the general application information page though.\n\nBest,\n-- \nJakub Narębski\n"}]}