{"thread":{"id":"53056","subject":"[RFC][GSoC] Implement Generation Number v2","startedAt":"2020-03-22T09:36:36Z","lastAt":"2020-03-26T10:18:17Z","messageCount":12,"participants":["Abhishek Kumar","Jakub Narebski","Junio C Hamano","Derrick Stolee"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"393696","messageId":"20200322093526.GA4718@Abhishek-Arch","threadId":"53056","inReplyTo":null,"subject":"[RFC][GSoC] Implement Generation Number v2","fromName":"Abhishek Kumar","fromEmail":"abhishekkumar8222@gmail.com","sentAt":"2020-03-22T09:35:26Z","receivedAt":"2020-03-22T09:36:36Z","isPatch":false,"sender":{"key":"abhishekkumar8222@gmail.com","avatar":"https://avatars.githubusercontent.com/u/31231064?v=4"},"body":"Hello everyone,\n\nFollowing the discussions between Jakub and Stolee [16], it was decided that\nimplementing \"Corrected Commit Date With Strictly Monotonic Offset\" [17] was\nmore appropriate for a GSoC project.\n\nI would like to work on it. The proposal could still use some work but I\nthought it would be best to get early feedback.\n\nHaving been over most of the related codebase, I think the project can be\nreasonably completed in 8 weeks or so.\n\nTransitioning from SHA1 to SHA3-256 (or at least adding support for it) has\nbeen on the waitlist for a while. Is that something we could pursue as a\npart of this project?\n\nIf not, are there any other related components/ideas that I could work on.\n\nThank you Jakub for proposing this project and the other contributors for\ncontinued interest and discussions.\n\nNote: You can alternatively read this proposal on Github [18].\n\n[16]: https://lore.kernel.org/git/86eeto5x1j.fsf@gmail.com/\n[17]: https://lore.kernel.org/git/86o8ziatb2.fsf_-_@gmail.com/\n[18]: https://github.com/abhishekkumar2718/GSoC20/blob/master/generation_number_v2.md\n\n===============================================================================\n\n# Implement Generation Number v2\n\n## Abstract\n\nGit uses various clever methods for making operations on very large repositories\nfaster, from bitmap indices for git fetch [1], to generation numbers (also known\nas topological levels) in the commit-graph file for commit graph traversal\noperations like git log --graph [2].\n\nHowever, generation numbers do not always improve performance. Stolee has\npreviously explored alternatives for a better generation number [3]. Backward\ncompatible corrected commit date was chosen because of its performance, local\ncomputability, and backward compatibility.\n\n[1]: https://githubengineering.com/counting-objects/\n[2]: https://devblogs.microsoft.com/devops/supercharging-the-git-commit-graph-iii-generations/\n[3]: https://lore.kernel.org/git/6367e30a-1b3a-4fe9-611b-d931f51effef@gmail.com/\n\n## Goals\n\nThis project aims to:\n- Move `generation`, `graph_pos` members of struct commit into a commit slab.\n- Update generation number to v2, modifying all places that reference or\ncompute generation numbers.\n- Use generation numbers to speed up implementation of `--ancestry-path` and\npossibly other commands.\n- Extend Stolee`s performance test suite.\n- Examine performance improvements.\n\n## Overview\n\nGit walks the commit graph for many reasons, including listing and filtering\ncommit history and computing merge bases.\n\nThese operations can become slow as the commit count grows. The two main costs\nhere are decompressing and parsing commits and walking the entire graphs to\nsatisfy topological order constraints.\n\nStolee introduced commit-graph file to accelerate this process. The commit-graph\nfile stores commit graph structure along extra metadata to speed up graph walks.\nA chunk includes commit OID, list of parents, commit date, root tree OID and \ngeneration number.\n\nGeneration number v1 was defined as one more than the length of the longest path\nfrom A to the root commit. Then,\n\n    If A and B are commits with generation numbers N and M, and N <= M, then\n    A cannot reach B.\n\nThis property reduces the time to walk commits and determine topological\nrelationships significantly.\n\n### Performance Regression\n\nWhile testing git v2.19.0-rc1, Stolee came across a performance regression due\nto using topological levels [4]. The discussion can be summarized as:\n\nTopological level changes the order in which the commits are inspected and\ngives a performance regression if it chooses to walk a longer path than\ncompared to date-based heuristic.\n\nFor example, consider the performance before and after using topological levels\non `git merge-base v4.8 v4.9`:\n\n  before topological levels: 0.122s\n   after topological levels: 0.547s\n\n\nThe topology of this can be described as:\n```\n   v4.9\n    |  \\\n    |   \\\n   v4.8  \\\n    | \\   \\\n    |  \\   |\n   ...  A  B\n    |  /  /\n    | /  /\n    |/__/\n    C\n```\n\nHere, the \"...\" means a \"very long line of commits\". A and B have generation\none more than C.\n\nIf we order commits by generation, then commit date, B is removed from the queue\nonly after many commits reachable from v4.8 have been explored.  However, if\nordering by commit date removes A and B from the queue early and C is inserted.\nAs C is processed, the rest of queue is marked as STALE and loop terminates.\n\n[4]: https://lore.kernel.org/git/pull.28.git.gitgitgadget@gmail.com/\n\n### Alternatives to Topological Level\n\nTo improve generation numbers, Stolee investigated other alternative\ndefinitions for generation numbers. The extended exploration and report are\navailable here [5].\n\nCorrected commit date was chosen as the next generation number by overall\nconsensus because of its performance, local computability, and immutability.\n\nHowever, it was not backward compatible with current implementation i.e., older\nclients do not report correct values if they ignore reachability index version.\nExisting clients would fail altogether with commit-graph v2 instead of\nswitching commit-graph feature off, as discovered by Ævar Arnfjörð Bjarmason [6].\n\n[5]: https://lore.kernel.org/git/6367e30a-1b3a-4fe9-611b-d931f51effef@gmail.com/\n[6]: https://lore.kernel.org/git/87a7gdspo4.fsf@evledraar.gmail.com/\n\n### Corrected Commit Date With Strictly Monotonic Offset\n\nJakub later proposed a modification to corrected commit date, _Corrected Commit\nDate with Strictly Monotonic Offset_ defined as follows [7]:\n\nFor a commit C, let its _offset commit date_ (denoted by odate(C))\nbe a commit date plus some offset, i.e. odate(C) = date(C) + offset(C),\nsuch that:\n\n1. Offset commit date is greater than the maximum of the commit date of\n   C and the offset commit dates of its parents.\n\n    If odate(A) < odate(B), then A cannot reach B.\n\n2. The offset of a commit is one more than the maximum offset of a parent, or\n   more.\n\n    If offset(A) < offset(B), then A cannot reach B.\n\nSince the offset are strictly greater than the offset of a parent, the old\nclients give correct values for the odate as well. `git commit-graph verify`\nwould fail since the offsets are not generation numbers in all cases.\n\nThis is an acceptable trade off because users can re-write the commit graph\nafter verify fails.\n \nA rough implementation by Jakub can be read here [8].\n\n[7]: https://lore.kernel.org/git/86o8ziatb2.fsf_-_@gmail.com/\n[8]: https://github.com/derrickstolee/git/pull/10\n\n## Plan\n\n### Community bonding period (April 27 - May 18, 4 weeks)\n\n1. Extend Stolee`s performance test suite.\n\nTo investigate replacements for generation numbers, Stolee implemented\nprototypes and compared performance on a range of queries.\n\nIt currently tests:\n- `git log --topo-order -N`: measures commits walked to determine all possible\nways of arriving at given commit.\n- `git log --topo-order -10 A..B`: measures commits walked to determine commits\nreachable from B but not from A.\n- `git merge-base A B`: measures commits walked to find the lowest (closest)\nancestor for both A and B.\n\nWe can also add tests for:\n- `git branch --[no-]contains A`: measures commits walked to determine if A is\nreachable from the tip of a given branch for all branches (many to one query).\n- `git branch --[no-]merged A`: measures commits walked to determine if the tip\nof a given branch is reachable from A for all branches (one to many query).\n- `git push/fetch`: measures commits walked to compute HAVES/WANTS of a client\n(many to many query) [9].\n\n2. Find other operations that can be optimized using generation numbers.\n\nAs Jakub pointed out in the discussion on generation numbers, --ancestry-path\ncan be optimized using generation numbers [10]. Discuss and find any other\noperation which could use generation numbers.\n\n3. Explore commit, commit-graph, commit-reach, revision\n\n[9]: https://github.blog/2015-09-22-counting-objects/\n[10]: https://lore.kernel.org/git/861s82wdbp.fsf@gmail.com/\n\n### Move `generation`, `graph_pos` into a slab (May 18 - June 8, 3 weeks)\n\nstruct commit is used in many contexts. However, the struct members\n`generation` and `graph_pos` are only used for commit-graph related operations\nand otherwise waste memory.\n\nUsing a commit slab reduces space of an individual commit object, which becomes\ncrucial as we load thousands of them. We can dynamically associate commits\nwith their generation/graph positions when needed.\n\nCommit slab for `generation` is 64 bits wide as it stores odate instead\nof offset [11]. Commit slab for `graph_pos` is simpler, with a straightforward\nallocation of 32 bits.\n\nNote: Commit-graph chunks would still store offset and will be used to compute\ncorrected date on initialization.\n\n[11]: https://lore.kernel.org/git/cfa2c367-5cd7-add5-0293-caa75b103f34@gmail.com/\n\n### Implement backward compatible corrected commit date (June 8 - July 20, 6 weeks)\n\n1. Implement backward compatible corrected commit date (June 8 - June 22, 2 weeks)\n\nTopological levels are computed using a DFS in `compute_generation_numbers` of\ncommit-graph.c. The condition\n\n  generation(C) = max(generation(P)) + 1,\n  where C is a commit and P are its parent(s).\n\nneeds to be redefined as:\n\n  generation(C) = max(max(generation(P)), correction(C)) + 1,\n  where correction(C) is max(cdate(P) - cdate(C), 0). \n\nDefinitions of `GENERATION_NUMBER_{INFINITY, MAX, ZERO}` remain the same.\n\nThe functions `compare_commits_by_gen_then_commit_date` and\n`compare_commits_by_commit_date` can be replaced by `compare_commits_by_gen` as\nall three *should* return the same order.\n\n--> First evaluation (June 15 - June 19)\n\n2. Update existing references (June 22 - July 20, 4 weeks)\n\nThe following functions use generation number or committer date for cutoffs:\n- `contains_tag_algo`\n- `can_all_from_reach_with_flag`\n- `paint_down_to_common`\n- `remove_redundant`\n\nAll of these can be updated with little to no changes.\n\n--> End Semester Exams (June 29 - July 4)\n\n--> Second evaluation (July 13 - July 17)\n\n### Extend generation number to --ancestry-path (July 20 - August 3, 2 weeks)\n\n`--ancestry-path A..B` returns the commits that are both descendants of A and\nancestors of B. The algorithm computes commits that are reachable by B but not\nby A, reverse the graph and walk backwards from A [12].\n\nWe can use generation number to limit walks to find commits reachable by B.\n\n[12]: https://lore.kernel.org/git/0c6b42e4-e825-ff70-a528-e118abf4c435@gmail.com/\n\n### Examine performance improvements (August 3 - August 10, 1 week)\n\n- Compare the performance of generation number v2 versus topological level using\n  performance test suite.\n- Wrap up any existing patches.\n\nThe performance report would be a nice summary my work over the summer.\n\n## Contributions\n\n[Microproject] Consolidate test_cmp_graph logic\n-----\nLog graph comparison logic is duplicated many times. This patch consolidates\ncomparison and sanitation logic in lib-log-graph.\n\nStatus: Merged\n\nPatch: https://lore.kernel.org/git/20200216134750.18947-1-abhishekkumar8222@gmail.com/\n\nCommit: https://github.com/git/git/commit/46703057c1a0f85e24c0144b38c226c6a9ccb737\n\nI have also reviewed patches and discussed queries with other contributors:\n- https://lore.kernel.org/git/CAHk66fskrfcJ0YFDhfimVBTJZB4um7r=GdQuM8heJdZtF8D7UQ@mail.gmail.com/\n- https://lore.kernel.org/git/CAHk66fvt-1RaLK8E7SDpocWM9OMAcA-gP5hjHq6r5N_FbATNgA@mail.gmail.com/\n- https://github.com/git/git/pull/647#issuecomment-591978405\n\nand others.\n\n## Post GSoC\n\nI would love to keep contributing to git after the GSoC period ends. There`s so\nmuch to learn from the community.\n\nHannes`s comment on checks as a penalty that should be paid only by constant\nstrbufs was a perspective I had not considered [13].\n\nInteracting with Kyagi made me rethink the justifications _emphasizing commit\nmessages_. I was at my wit`s end, which makes me appreciate my patient mentors\nmore and want to give back to the community.\n\n[13]: https://lore.kernel.org/git/467c035f-c7cd-01e1-e64c-2c915610de01@kdbg.org/\n\n## About Me\n\nI am Abhishek Kumar, a second-year CSE student at National Institute of\nTechnology Karnataka, India. I have a blog where I talk about my interests -\nprogramming, fiction, and literature [14].\n\nI primarily work with C/C++ and Ruby on Rails. I am a member of my institute`s\nOpen Source Club and student-built University Management System, _IRIS_. I have\nsome experience of mentoring - Creating their code style guide and being an\nactive reviewer [15].\n\n[14]: https://abhishekkumar2718.github.io/\n\n[15]: https://iris.nitk.ac.in/about_us\n\n## Availablity\n\nThe official GSoC coding period runs from April 27 to August 17.\n\nDue to the outbreak of COVID-19 in my country, my college has pre-emptively\nannounced summer vacations from March 17 to June 1. Unfortunately,\nI would have classes for a large part of the coding period. However, I can still\ncontribute 35-40 hours every week due to a low course load (~20 hours a week).\n\nI would not be able to contribute from June 29 to July 4 due to end semester exams.\nIt would be easily compensated during the subsequent week \"semester break\" from\nJuly 5 to July 27.\n\n## Contact Information\n\n```\n     Name: Abhishek Kumar\n    Email: abhishekkumar8222@gmail.com\n    Major: Computer Science And Engineering\n   Degree: Bachelor of Technology\nInstitute: National Institute of Technology Karnataka\n   Github: abhishekkumar2718\n Timezone: UTC+5:30 (IST)\n```\n\nThank you for taking the time to review my proposal!\n"},{"id":"393739","messageId":"86eetkrw8p.fsf@gmail.com","threadId":"53056","inReplyTo":"20200322093526.GA4718@Abhishek-Arch","subject":"Re: [RFC][GSoC] Implement Generation Number v2","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2020-03-22T20:05:26Z","receivedAt":"2020-03-22T20:05:36Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"A few comments.\n\nAbhishek Kumar <abhishekkumar8222@gmail.com> writes:\n\n> Hello everyone,\n>\n> Following the discussions between Jakub and Stolee [16], it was decided that\n> implementing \"Corrected Commit Date With Strictly Monotonic Offset\" [17] was\n> more appropriate for a GSoC project.\n>\n> I would like to work on it. The proposal could still use some work but I\n> thought it would be best to get early feedback.\n\nThank you for your interest in this idea.\n\n[...]\n> ### Corrected Commit Date With Strictly Monotonic Offset\n>\n> Jakub later proposed a modification to corrected commit date, _Corrected Commit\n> Date with Strictly Monotonic Offset_ defined as follows [7]:\n\nI don't remember who originally proposed this idea, but it was not me.\nI have only given it the name you use.\n\n> For a commit C, let its _offset commit date_ (denoted by odate(C))\n> be a commit date plus some offset, i.e. odate(C) = date(C) + offset(C),\n> such that:\n>\n> 1. Offset commit date is greater than the maximum of the commit date of\n>    C and the offset commit dates of its parents.\n>\n>     If odate(A) < odate(B), then A cannot reach B.\n>\n> 2. The offset of a commit is one more than the maximum offset of a parent, or\n>    more.\n>\n>     If offset(A) < offset(B), then A cannot reach B.\n>\n> Since the offset are strictly greater than the offset of a parent, the old\n> clients give correct values for the odate as well. `git commit-graph verify`\n> would fail since the offsets are not generation numbers in all cases.\n>\n> This is an acceptable trade off because users can re-write the commit graph\n> after verify fails.\n\nOne thing to solve is find and implement a way to distinguish between\ncommit-graph with generation number v1 (legacy), and commit-graph with\ngeneration number v2.\n\nUnfortunately for the time being we cannot use commit-graph format\nversion; the idea that was proposed on the mailing list (when we found\nabout the bug in handling commit-graph versioning, during incremental\ncommit-graph implementation), was to create and use metadata chunk or\nversioning chunk (the final version of incremental format do not use\nthis mechanism).  This could be used by gen2 compatibile Git to\ndistinguish between situation where old commit-graph file to be updated\nuses generation number v1, and when it uses v2.\n\nIf you have a better idea, please say so.\n\n[...]\n> ## Contributions\n>\n> [Microproject] Consolidate test_cmp_graph logic\n> -----\n> Log graph comparison logic is duplicated many times. This patch consolidates\n> comparison and sanitation logic in lib-log-graph.\n>\n> Status: Merged\n>\n> Patch: https://lore.kernel.org/git/20200216134750.18947-1-abhishekkumar8222@gmail.com/\n>\n> Commit: https://github.com/git/git/commit/46703057c1a0f85e24c0144b38c226c6a9ccb737\n\nNice, this is related work.\n\nBest,\n-- \nJakub Narębski\n"},{"id":"393754","messageId":"20200323042517.GA1258@Abhishek-Arch","threadId":"53056","inReplyTo":"86eetkrw8p.fsf@gmail.com","subject":"Re: [RFC][GSoC] Implement Generation Number v2","fromName":"Abhishek Kumar","fromEmail":"abhishekkumar8222@gmail.com","sentAt":"2020-03-23T04:25:17Z","receivedAt":"2020-03-23T04:26:27Z","isPatch":false,"sender":{"key":"abhishekkumar8222@gmail.com","avatar":"https://avatars.githubusercontent.com/u/31231064?v=4"},"body":"On Sun, Mar 22, 2020 at 09:05:26PM +0100, Jakub Narebski wrote:\n> A few comments.\n> \n> Abhishek Kumar <abhishekkumar8222@gmail.com> writes:\n> \n> > Hello everyone,\n> >\n> > Following the discussions between Jakub and Stolee [16], it was decided that\n> > implementing \"Corrected Commit Date With Strictly Monotonic Offset\" [17] was\n> > more appropriate for a GSoC project.\n> >\n> > I would like to work on it. The proposal could still use some work but I\n> > thought it would be best to get early feedback.\n> \n> Thank you for your interest in this idea.\n> \n> [...]\n> > ### Corrected Commit Date With Strictly Monotonic Offset\n> >\n> > Jakub later proposed a modification to corrected commit date, _Corrected Commit\n> > Date with Strictly Monotonic Offset_ defined as follows [7]:\n> \n> I don't remember who originally proposed this idea, but it was not me.\n> I have only given it the name you use.\n> \n\nThanks, noted. Will update it.\n\n> > For a commit C, let its _offset commit date_ (denoted by odate(C))\n> > be a commit date plus some offset, i.e. odate(C) = date(C) + offset(C),\n> > such that:\n> >\n> > 1. Offset commit date is greater than the maximum of the commit date of\n> >    C and the offset commit dates of its parents.\n> >\n> >     If odate(A) < odate(B), then A cannot reach B.\n> >\n> > 2. The offset of a commit is one more than the maximum offset of a parent, or\n> >    more.\n> >\n> >     If offset(A) < offset(B), then A cannot reach B.\n> >\n> > Since the offset are strictly greater than the offset of a parent, the old\n> > clients give correct values for the odate as well. `git commit-graph verify`\n> > would fail since the offsets are not generation numbers in all cases.\n> >\n> > This is an acceptable trade off because users can re-write the commit graph\n> > after verify fails.\n> \n> One thing to solve is find and implement a way to distinguish between\n> commit-graph with generation number v1 (legacy), and commit-graph with\n> generation number v2.\n> \n> Unfortunately for the time being we cannot use commit-graph format\n> version; the idea that was proposed on the mailing list (when we found\n> about the bug in handling commit-graph versioning, during incremental\n> commit-graph implementation), was to create and use metadata chunk or\n> versioning chunk (the final version of incremental format do not use\n> this mechanism).  This could be used by gen2 compatibile Git to\n> distinguish between situation where old commit-graph file to be updated\n> uses generation number v1, and when it uses v2.\n> \n> If you have a better idea, please say so.\n> \n\nWe could also use a flag file. Here's how it works:\n\nIf the file `.git/info/generation-number-v2` exists, use gen2.\nOtherwise use gen1.\n\nWe can, of course generalize this to `<dir>/info/generation-number-v2`\nif needed.\n\n1. It is independent of commit-graph format. \n\n2. Switching between versions requires creating/deleting a file, which\nis simpler than reading commit-graph file and modifying (or removing) a\nmetadata chunk.\n\nJohannes used a similar flag file during the conversion of difftool [1].\n\n[1]: https://lore.kernel.org/git/598dcfdbeef4e15d2d439053a0423589182e5f30.1479834051.git.johannes.schindelin@gmx.de/\n\n> [...]\n> > ## Contributions\n> >\n> > [Microproject] Consolidate test_cmp_graph logic\n> > -----\n> > Log graph comparison logic is duplicated many times. This patch consolidates\n> > comparison and sanitation logic in lib-log-graph.\n> >\n> > Status: Merged\n> >\n> > Patch: https://lore.kernel.org/git/20200216134750.18947-1-abhishekkumar8222@gmail.com/\n> >\n> > Commit: https://github.com/git/git/commit/46703057c1a0f85e24c0144b38c226c6a9ccb737\n> \n> Nice, this is related work.\n> \n> Best,\n> -- \n> Jakub Narębski\n\nRegards\nAbhishek\n"},{"id":"393755","messageId":"xmqq369z7i1b.fsf@gitster.c.googlers.com","threadId":"53056","inReplyTo":"20200323042517.GA1258@Abhishek-Arch","subject":"Re: [RFC][GSoC] Implement Generation Number v2","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-03-23T05:32:32Z","receivedAt":"2020-03-23T05:32:37Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Abhishek Kumar <abhishekkumar8222@gmail.com> writes:\n\n>> Unfortunately for the time being we cannot use commit-graph format\n>> version; the idea that was proposed on the mailing list (when we found\n>> about the bug in handling commit-graph versioning, during incremental\n>> commit-graph implementation), was to create and use metadata chunk or\n>> versioning chunk (the final version of incremental format do not use\n>> this mechanism).  This could be used by gen2 compatibile Git to\n>> distinguish between situation where old commit-graph file to be updated\n>> uses generation number v1, and when it uses v2.\n>> \n>> If you have a better idea, please say so.\n>\n> We could also use a flag file. Here's how it works:\n>\n> If the file `.git/info/generation-number-v2` exists, use gen2.\n> Otherwise use gen1.\n\nIf the file is lost then we will try to read the other file that has\nthe commit-graph data as if it were in old format?  And if such a\nfile was created (say, with \"touch .git/info/generation-number-v2\"),\na file in the original format will be read as if it is in new\nformat?  If that is the case, it is likely that we'd see a segfault;\nsounds too brittle to me.\n\nIt appears that the format of \"CDAT\", and the fact that generation\nis represented as higher 30-bit of a be32 integer, is very much\nhardcoded in the design and is hard to change, but your new version\nof graph file can be designed not to use \"CDAT\" chunk at all, and\ninstead have the commit data with new version of generation numbers\nstored in a different chunk (say \"CDA2\") to force older version of\nGit not to use the new graph file---would that work?\n"},{"id":"393760","messageId":"20200323113231.GA22065@Abhishek-Arch","threadId":"53056","inReplyTo":"xmqq369z7i1b.fsf@gitster.c.googlers.com","subject":"Re: [RFC][GSoC] Implement Generation Number v2","fromName":"Abhishek Kumar","fromEmail":"abhishekkumar8222@gmail.com","sentAt":"2020-03-23T11:32:31Z","receivedAt":"2020-03-23T11:33:45Z","isPatch":false,"sender":{"key":"abhishekkumar8222@gmail.com","avatar":"https://avatars.githubusercontent.com/u/31231064?v=4"},"body":"On Sun, Mar 22, 2020 at 10:32:32PM -0700, Junio C Hamano wrote:\n> Abhishek Kumar <abhishekkumar8222@gmail.com> writes:\n> \n> >> Unfortunately for the time being we cannot use commit-graph format\n> >> version; the idea that was proposed on the mailing list (when we found\n> >> about the bug in handling commit-graph versioning, during incremental\n> >> commit-graph implementation), was to create and use metadata chunk or\n> >> versioning chunk (the final version of incremental format do not use\n> >> this mechanism).  This could be used by gen2 compatibile Git to\n> >> distinguish between situation where old commit-graph file to be updated\n> >> uses generation number v1, and when it uses v2.\n> >> \n> >> If you have a better idea, please say so.\n> >\n> > We could also use a flag file. Here's how it works:\n> >\n> > If the file `.git/info/generation-number-v2` exists, use gen2.\n> > Otherwise use gen1.\n> \n> If the file is lost then we will try to read the other file that has\n> the commit-graph data as if it were in old format?  And if such a\n> file was created (say, with \"touch .git/info/generation-number-v2\"),\n> a file in the original format will be read as if it is in new\n> format?  If that is the case, it is likely that we'd see a segfault;\n> sounds too brittle to me.\n\nAgreed. Flag file has too many issues to be pursued further.\n\n> \n> It appears that the format of \"CDAT\", and the fact that generation\n> is represented as higher 30-bit of a be32 integer, is very much\n> hardcoded in the design and is hard to change, but your new version\n> of graph file can be designed not to use \"CDAT\" chunk at all, and\n> instead have the commit data with new version of generation numbers\n> stored in a different chunk (say \"CDA2\") to force older version of\n> Git not to use the new graph file---would that work?\n\nA commit-graph without \"CDAT\" chunk will hard fail on older versions of\nGit. verify_commit_graph_lite() errors out if chunk_commit_data is null.\n\nMetadata chunk seems the way to go.\n\nRegards\nAbhishek\n"},{"id":"393767","messageId":"86mu87qj92.fsf@gmail.com","threadId":"53056","inReplyTo":"xmqq369z7i1b.fsf@gitster.c.googlers.com","subject":"Re: [RFC][GSoC] Implement Generation Number v2","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2020-03-23T13:43:37Z","receivedAt":"2020-03-23T13:43:45Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Junio C Hamano <gitster@pobox.com> writes:\n> Abhishek Kumar <abhishekkumar8222@gmail.com> writes:\n>> Jakub Narębski <jnareb@gmail.com> writes:\n[...]\n>>> Unfortunately for the time being we cannot use commit-graph format\n>>> version; the idea that was proposed on the mailing list (when we found\n>>> about the bug in handling commit-graph versioning, during incremental\n>>> commit-graph implementation), was to create and use metadata chunk or\n>>> versioning chunk (the final version of incremental format do not use\n>>> this mechanism).  This could be used by gen2 compatibile Git to\n>>> distinguish between situation where old commit-graph file to be updated\n>>> uses generation number v1, and when it uses v2.\n>>> \n>>> If you have a better idea, please say so.\n>>\n>> We could also use a flag file. Here's how it works:\n>>\n>> If the file `.git/info/generation-number-v2` exists, use gen2.\n>> Otherwise use gen1.\n>\n> If the file is lost then we will try to read the other file that has\n> the commit-graph data as if it were in old format?  And if such a\n> file was created (say, with \"touch .git/info/generation-number-v2\"),\n> a file in the original format will be read as if it is in new\n> format?  If that is the case, it is likely that we'd see a segfault;\n> sounds too brittle to me.\n>\n> It appears that the format of \"CDAT\", and the fact that generation\n> is represented as higher 30-bit of a be32 integer, is very much\n> hardcoded in the design and is hard to change, but your new version\n> of graph file can be designed not to use \"CDAT\" chunk at all, and\n> instead have the commit data with new version of generation numbers\n> stored in a different chunk (say \"CDA2\") to force older version of\n> Git not to use the new graph file---would that work?\n\nIt looks like there are a few possible ways of handling introduction of\ngeneration numbers v2.  Let's consider them one by one.\n\nThe problem we need to solve is co-existence of old Git (that does not\nunderstand v2, and that hard fails on commit-graph format version bump),\nand new Git (that understands and writes v2, and that I assume soft\nfails that is it simply doesn't use commit-graph if it of unknown\nversion).\n\n\nIf the commit-graph file was written by new Git, and includes generation\nnumbers v2, we want old Git to at least do not crash, possibly do not\nuse commit-graph, best if it can use commit-graph in suboptimal way.  We\nalso need to handle old Git trying to update (in incremental or\nnon-incremental way) the commit-graph file.\n\nIf the commit-graph file was written by old Git, and includes generation\nnmbers v1 (topological levels), we want new Git to recognize this and at\nbest use those old generation numbers in a correct way.  We want new Git\nto be able to update commit-graph file (in incremental or\nnon-incremental way).\n\nDid I miss anything?\n\n\nProposed solutions are:\n - metadata / versioning chunk,\n - flag file: `.git/info/generation-number-v2`,\n - new chunk for commit data: \"CDA2\".\n\nI would like to propose yet another solution: putting generation number\nv2 data in a separate chunk (and possibly keeping generation number v1\nin CDAT commit data chunk).  In this case we could even use ordinary\ncorrected commit date as generation number v2 (storing offsets as 32-bit\nunsigned values), instead of backward-compatibile corrected commit date\nwith monotonic offsets.\n\nEach solution has its advantages and disadvantages.\n\n\nWith the flag file, the problem is (as Junio noticed) that if file gets\naccidentally deleted, new Git would think incorrectly that commit-graph\nuses generation number v1... which while suboptimal should not be bad\nthanks to backward compatibility.  But I think the flag file should have\nsome kind of checksum as its contents (perhaps simply a copy of\ncommit-graph file checksum, or one checksum per file in chain with\nincremental commit-graph), so that it old Git rewrites commit-graph file\nleaving flag file present, new Git would notice this.\n\nMetadata or versioning chunk cannot be deleted by mistake; if old Git\ncopies unknown chunks to new updated commit-graph file instead of\nskipping them we would need to add some kind of checksum (similarly to\nthe case for flag file).  The problem to be solved is what to do if some\nfiles in the chain of commit-graph files have v2 (and this chunk), and\nsome have v1 generation number (and do not have this chunk).\n\nAbout moving commit data with generation number v2 to \"CDA2\" chunk: if\n\"CDAT\" chunk is missing then (I think) old Git would simply not use\ncommit-graph file at all; it may crash, but I don't think so.  If \"CDAT\"\nchunk has zero length... I don't know what would happen then, possibly\nalso old Git would simply not use commit-graph data at all.\n\nPutting generation number v2 into separate chunk (which might be called\n\"GEN2\" or \"OFFS\"/\"DOFF\") has the disadvantage of increasing the on disk\nsize of the commit graph, and possibly also increasing memory\nconsumption (the latter depends on how it would be handled), but has the\nadvantage of being fullly backward compatibile.  Old Git would simply\nuse generation numbers v1 in \"CDAT\", new Git would use generation\nnumbers v2 in \"OFFS\" -- combining commit creation date from \"CDAT\" and\noffset from \"OFFS\"), and there should be no problems with updating\ncommit-graph file (either rewriting, or adding new commit-graph to the\nchain).\n\nI think that's all.\n\nBest,\n-- \nJakub Narębski\n"},{"id":"393776","messageId":"13995fbd-d645-56aa-b647-e9a51d00554e@gmail.com","threadId":"53056","inReplyTo":"86mu87qj92.fsf@gmail.com","subject":"Re: [RFC][GSoC] Implement Generation Number v2","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2020-03-23T15:54:07Z","receivedAt":"2020-03-23T15:54:11Z","isPatch":false,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 3/23/2020 9:43 AM, Jakub Narebski wrote:\n> Junio C Hamano <gitster@pobox.com> writes:\n>> Abhishek Kumar <abhishekkumar8222@gmail.com> writes:\n>>> Jakub Narębski <jnareb@gmail.com> writes:\n> [...]\n>>>> Unfortunately for the time being we cannot use commit-graph format\n>>>> version; the idea that was proposed on the mailing list (when we found\n>>>> about the bug in handling commit-graph versioning, during incremental\n>>>> commit-graph implementation), was to create and use metadata chunk or\n>>>> versioning chunk (the final version of incremental format do not use\n>>>> this mechanism).  This could be used by gen2 compatibile Git to\n>>>> distinguish between situation where old commit-graph file to be updated\n>>>> uses generation number v1, and when it uses v2.\n>>>>\n>>>> If you have a better idea, please say so.\n>>>\n>>> We could also use a flag file. Here's how it works:\n>>>\n>>> If the file `.git/info/generation-number-v2` exists, use gen2.\n>>> Otherwise use gen1.\n>>\n>> If the file is lost then we will try to read the other file that has\n>> the commit-graph data as if it were in old format?  And if such a\n>> file was created (say, with \"touch .git/info/generation-number-v2\"),\n>> a file in the original format will be read as if it is in new\n>> format?  If that is the case, it is likely that we'd see a segfault;\n>> sounds too brittle to me.\n>>\n>> It appears that the format of \"CDAT\", and the fact that generation\n>> is represented as higher 30-bit of a be32 integer, is very much\n>> hardcoded in the design and is hard to change, but your new version\n>> of graph file can be designed not to use \"CDAT\" chunk at all, and\n>> instead have the commit data with new version of generation numbers\n>> stored in a different chunk (say \"CDA2\") to force older version of\n>> Git not to use the new graph file---would that work?\n> \n> It looks like there are a few possible ways of handling introduction of\n> generation numbers v2.  Let's consider them one by one.\n> \n> The problem we need to solve is co-existence of old Git (that does not\n> understand v2, and that hard fails on commit-graph format version bump),\n> and new Git (that understands and writes v2, and that I assume soft\n> fails that is it simply doesn't use commit-graph if it of unknown\n> version).\n> \n> \n> If the commit-graph file was written by new Git, and includes generation\n> numbers v2, we want old Git to at least do not crash, possibly do not\n> use commit-graph, best if it can use commit-graph in suboptimal way.  We\n> also need to handle old Git trying to update (in incremental or\n> non-incremental way) the commit-graph file.\n> \n> If the commit-graph file was written by old Git, and includes generation\n> nmbers v1 (topological levels), we want new Git to recognize this and at\n> best use those old generation numbers in a correct way.  We want new Git\n> to be able to update commit-graph file (in incremental or\n> non-incremental way).\n> \n> Did I miss anything?\n> \n> \n> Proposed solutions are:\n>  - metadata / versioning chunk,\n>  - flag file: `.git/info/generation-number-v2`,\n>  - new chunk for commit data: \"CDA2\".\n> \n> I would like to propose yet another solution: putting generation number\n> v2 data in a separate chunk (and possibly keeping generation number v1\n> in CDAT commit data chunk).  In this case we could even use ordinary\n> corrected commit date as generation number v2 (storing offsets as 32-bit\n> unsigned values), instead of backward-compatibile corrected commit date\n> with monotonic offsets.\n\nI agree that if we are creating a new (optional) chunk, then that gets\naround our versioning issues and could store just the offsets to get\nthe \"corrected commit date\" option instead of the backwards-compatible one.\nBy including yet another version number at the beginning of that chunk,\nwe could present a way to update this \"second reachability index chunk\"\nwith things like your interval mechanism with very little cost.\n\n> Each solution has its advantages and disadvantages.\n> \n> \n> With the flag file, the problem is (as Junio noticed) that if file gets\n> accidentally deleted, new Git would think incorrectly that commit-graph\n> uses generation number v1... which while suboptimal should not be bad\n> thanks to backward compatibility.  But I think the flag file should have\n> some kind of checksum as its contents (perhaps simply a copy of\n> commit-graph file checksum, or one checksum per file in chain with\n> incremental commit-graph), so that it old Git rewrites commit-graph file\n> leaving flag file present, new Git would notice this.\n\nI'm not a fan of the flag file idea. Optional chunks are a good way forward.\nThat _could_ mean the metadata chunk, whose length can grow in the future\nif/when we add more fixed-width metadata values.\n\n> Metadata or versioning chunk cannot be deleted by mistake; if old Git\n> copies unknown chunks to new updated commit-graph file instead of\n> skipping them we would need to add some kind of checksum (similarly to\n> the case for flag file).  The problem to be solved is what to do if some\n> files in the chain of commit-graph files have v2 (and this chunk), and> some have v1 generation number (and do not have this chunk).\n\nThe incremental commit-graph format is newer than our previous tests\nfor generation number v2, which will be a big reason why that old code\ncannot be immediately adapted here.\n\nThe simplest thing to do is usually right: if we try to write a\ngeneration number version that doesn't match the current commit-graph,\nthen we need to flatten the entire chain into one layer and recompute\nthe values from scratch. While it is _technically_ possible to mix\nthe backwards-compatible corrected commit date with generation number\nv1, it requires taking the \"lowest version\" when doing comparisons and\nthat may behave very strangely. Better to avoid that complication.\n\n> About moving commit data with generation number v2 to \"CDA2\" chunk: if\n> \"CDAT\" chunk is missing then (I think) old Git would simply not use\n> commit-graph file at all; it may crash, but I don't think so.  If \"CDAT\"\n> chunk has zero length... I don't know what would happen then, possibly\n> also old Git would simply not use commit-graph data at all.\n\nCDAT is required as it contains more than just generation numbers. It\nhas the commit date, parent int-ids, and root tree oid. The generation\nnumbers _could_ be left as all zeroes, which is a special case for the\nformat before generation numbers were introduced, but it would be better\nto have values there.\n\n> Putting generation number v2 into separate chunk (which might be called\n> \"GEN2\" or \"OFFS\"/\"DOFF\") has the disadvantage of increasing the on disk\n> size of the commit graph, and possibly also increasing memory\n> consumption (the latter depends on how it would be handled), but has the\n> advantage of being fullly backward compatibile.  Old Git would simply\n> use generation numbers v1 in \"CDAT\", new Git would use generation\n> numbers v2 in \"OFFS\" -- combining commit creation date from \"CDAT\" and\n> offset from \"OFFS\"), and there should be no problems with updating\n> commit-graph file (either rewriting, or adding new commit-graph to the\n> chain).\n\nI share these concerns but also the locality of the data within the file.\nAs we parse commits, we need the parent and commit date information out\nof the CDAT chunk anyway, so it is not difficult to grab the nearby\ngeneration number. If we put that data further away in a separate chunk,\nthen it can be more expensive to flip between the CDAT chunk and the\nGEN2 chunk.\n\nIn terms of your prototyping for performance checks, it may be good to\nhave a number of \"GEN<X>\" chunks so you can compute one commit-graph\nthat stores all of the candidate reachability indexes, then use one\nof the chunks based on a config value or environment variable. I think\nthat would only be appropriate for testing if you are evaluating which\nto build, so if you are focusing entirely on backwards-compatible\ncorrected commit date, this is not worth spending time on.\n\nThanks,\n-Stolee\n"},{"id":"393780","messageId":"xmqqtv2f5a6x.fsf@gitster.c.googlers.com","threadId":"53056","inReplyTo":"86mu87qj92.fsf@gmail.com","subject":"Re: [RFC][GSoC] Implement Generation Number v2","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-03-23T16:04:54Z","receivedAt":"2020-03-23T16:05:02Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jakub Narebski <jnareb@gmail.com> writes:\n\n> About moving commit data with generation number v2 to \"CDA2\" chunk: if\n> \"CDAT\" chunk is missing then (I think) old Git would simply not use\n> commit-graph file at all; it may crash, but I don't think so.  If \"CDAT\"\n> chunk has zero length... I don't know what would happen then, possibly\n> also old Git would simply not use commit-graph data at all.\n\nYeah, if it makes it crash, then we cannot use that \"missing CDAT\"\napproach.\n\n> Putting generation number v2 into separate chunk (which might be called\n> \"GEN2\" or \"OFFS\"/\"DOFF\") has the disadvantage of increasing the on disk\n> size of the commit graph, and possibly also increasing memory\n> consumption (the latter depends on how it would be handled), but has the\n> advantage of being fullly backward compatibile.  Old Git would simply\n> use generation numbers v1 in \"CDAT\", new Git would use generation\n> numbers v2 in \"OFFS\" -- combining commit creation date from \"CDAT\" and\n> offset from \"OFFS\"),\n\nDo we have an option *not* to record meaningful generation numbers\nin CDAT and have the current Git binaries understand and still use\nthe rest of the graph file, while not using the optimizations that\nrely on having generation numbers?  If not, then the new version of\nGit that tries to be compatible with old one needs to compute both\ngeneration numbers, and we would need to keep the topological number\nfor quite some time.\n\n> and there should be no problems with updating\n> commit-graph file (either rewriting, or adding new commit-graph to the\n> chain).\n\nWould merging by the current Git also work well (meaning, would\n\"GEN2\" or whatever it does not understand be omitted)?\n\nThanks.\n"},{"id":"393870","messageId":"86eetiqf4r.fsf@gmail.com","threadId":"53056","inReplyTo":"13995fbd-d645-56aa-b647-e9a51d00554e@gmail.com","subject":"Re: [RFC][GSoC] Implement Generation Number v2","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2020-03-24T09:24:52Z","receivedAt":"2020-03-24T09:24:59Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Derrick Stolee <stolee@gmail.com> writes:\n> On 3/23/2020 9:43 AM, Jakub Narebski wrote:\n>> Junio C Hamano <gitster@pobox.com> writes:\n>>> Abhishek Kumar <abhishekkumar8222@gmail.com> writes:\n>>>> Jakub Narębski <jnareb@gmail.com> writes:\n>> [...]\n>> Proposed solutions are:\n>>  - metadata / versioning chunk,\n>>  - flag file: `.git/info/generation-number-v2`,\n>>  - new chunk for commit data: \"CDA2\".\n>> \n>> I would like to propose yet another solution: putting generation number\n>> v2 data in a separate chunk (and possibly keeping generation number v1\n>> in CDAT commit data chunk).  In this case we could even use ordinary\n>> corrected commit date as generation number v2 (storing offsets as 32-bit\n>> unsigned values), instead of backward-compatibile corrected commit date\n>> with monotonic offsets.\n>\n> I agree that if we are creating a new (optional) chunk, then that gets\n> around our versioning issues and could store just the offsets to get\n> the \"corrected commit date\" option instead of the backwards-compatible one.\n> By including yet another version number at the beginning of that chunk,\n> we could present a way to update this \"second reachability index chunk\"\n> with things like your interval mechanism with very little cost.\n\nAll this may be just a transitory phase, waiting until Git versions that\nfail hard on commit-graph format version change die out... then we will\nbe able to use version number as intended (though it has the\ndisadvantage of turning off commit-graph wholly for older Git versions).\n\n>> Each solution has its advantages and disadvantages.\n>> \n>> \n>> With the flag file, the problem is (as Junio noticed) that if file gets\n>> accidentally deleted, new Git would think incorrectly that commit-graph\n>> uses generation number v1... which while suboptimal should not be bad\n>> thanks to backward compatibility.  But I think the flag file should have\n>> some kind of checksum as its contents (perhaps simply a copy of\n>> commit-graph file checksum, or one checksum per file in chain with\n>> incremental commit-graph), so that it old Git rewrites commit-graph file\n>> leaving flag file present, new Git would notice this.\n>\n> I'm not a fan of the flag file idea. Optional chunks are a good way forward.\n> That _could_ mean the metadata chunk, whose length can grow in the future\n> if/when we add more fixed-width metadata values.\n\nSo it looks like metadata / versioning chunk would be the best solution,\nisn't it?\n\n>> Metadata or versioning chunk cannot be deleted by mistake; if old Git\n>> copies unknown chunks to new updated commit-graph file instead of\n>> skipping them we would need to add some kind of checksum (similarly to\n>> the case for flag file).  The problem to be solved is what to do if some\n>> files in the chain of commit-graph files have v2 (and this chunk),\n>> and> some have v1 generation number (and do not have this chunk).\n>\n> The incremental commit-graph format is newer than our previous tests\n> for generation number v2, which will be a big reason why that old code\n> cannot be immediately adapted here.\n>\n> The simplest thing to do is usually right: if we try to write a\n> generation number version that doesn't match the current commit-graph,\n> then we need to flatten the entire chain into one layer and recompute\n> the values from scratch. While it is _technically_ possible to mix\n> the backwards-compatible corrected commit date with generation number\n> v1, it requires taking the \"lowest version\" when doing comparisons and\n> that may behave very strangely. Better to avoid that complication.\n\nRight.\n\n>> About moving commit data with generation number v2 to \"CDA2\" chunk: if\n>> \"CDAT\" chunk is missing then (I think) old Git would simply not use\n>> commit-graph file at all; it may crash, but I don't think so.  If \"CDAT\"\n>> chunk has zero length... I don't know what would happen then, possibly\n>> also old Git would simply not use commit-graph data at all.\n>\n> CDAT is required as it contains more than just generation numbers. It\n> has the commit date, parent int-ids, and root tree oid. The generation\n> numbers _could_ be left as all zeroes, which is a special case for the\n> format before generation numbers were introduced, but it would be better\n> to have values there.\n\nI think (but I might be wrong) that the most expensive part of\ncalculating generation numbers is actually walking the commits.  Because\nboth generation number v1 (topological level) and generation number v2\n(corrected committerdate, with or without monotonic restriction on\noffsets) can be computed at the same time, during the same walk,\npossibly with negligible cost compared to computing single geneation\nnumber.\n\nBut this should be perhaps benchmarked.\n\n>> Putting generation number v2 into separate chunk (which might be called\n>> \"GEN2\" or \"OFFS\"/\"DOFF\") has the disadvantage of increasing the on disk\n>> size of the commit graph, and possibly also increasing memory\n>> consumption (the latter depends on how it would be handled), but has the\n>> advantage of being fullly backward compatibile.  Old Git would simply\n>> use generation numbers v1 in \"CDAT\", new Git would use generation\n>> numbers v2 in \"OFFS\" -- combining commit creation date from \"CDAT\" and\n>> offset from \"OFFS\"), and there should be no problems with updating\n>> commit-graph file (either rewriting, or adding new commit-graph to the\n>> chain).\n>\n> I share these concerns but also the locality of the data within the file.\n> As we parse commits, we need the parent and commit date information out\n> of the CDAT chunk anyway, so it is not difficult to grab the nearby\n> generation number. If we put that data further away in a separate chunk,\n> then it can be more expensive to flip between the CDAT chunk and the\n> GEN2 chunk.\n\nRight, I forgot about this issue, that Git is lazily parsing\ncommit-graph data, so keeping all [possible] commit data close is a good\nidea from the performance point of view.\n\nSo it looks like metadata / versioning chunk would be the best solution\nto the backward-compatibility interoperability problem.\n\n> In terms of your prototyping for performance checks, it may be good to\n> have a number of \"GEN<X>\" chunks so you can compute one commit-graph\n> that stores all of the candidate reachability indexes, then use one\n> of the chunks based on a config value or environment variable. I think\n> that would only be appropriate for testing if you are evaluating which\n> to build, so if you are focusing entirely on backwards-compatible\n> corrected commit date, this is not worth spending time on.\n\nRight, but it looks like there is nobody taking new labelings for GSoC\n2020.\n\nGood idea for prototyping, true.\n\nBest,\n-- \nJakub Narębski\n"},{"id":"393876","messageId":"86k139ahb7.fsf@gmail.com","threadId":"53056","inReplyTo":"xmqqtv2f5a6x.fsf@gitster.c.googlers.com","subject":"Re: [RFC][GSoC] Implement Generation Number v2","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2020-03-24T15:44:28Z","receivedAt":"2020-03-24T15:44:39Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Junio C Hamano <gitster@pobox.com> writes:\n> Jakub Narebski <jnareb@gmail.com> writes:\n>\n>> About moving commit data with generation number v2 to \"CDA2\" chunk: if\n>> \"CDAT\" chunk is missing then (I think) old Git would simply not use\n>> commit-graph file at all; it may crash, but I don't think so.  If \"CDAT\"\n>> chunk has zero length... I don't know what would happen then, possibly\n>> also old Git would simply not use commit-graph data at all.\n>\n> Yeah, if it makes it crash, then we cannot use that \"missing CDAT\"\n> approach.\n\nI have not tested this, but from reading the code it looks like \"missing\nCDAT\" makes Git fail softly -- it would return NULL for the\ncommit-graph, and thus not use commit-graph data at all... which might\nbe too high a price (too high performance penalty for old Git).\n\n>> Putting generation number v2 into separate chunk (which might be called\n>> \"GEN2\" or \"OFFS\"/\"DOFF\") has the disadvantage of increasing the on disk\n>> size of the commit graph, and possibly also increasing memory\n>> consumption (the latter depends on how it would be handled), but has the\n>> advantage of being fullly backward compatibile.  Old Git would simply\n>> use generation numbers v1 in \"CDAT\", new Git would use generation\n>> numbers v2 in \"OFFS\" -- combining commit creation date from \"CDAT\" and\n>> offset from \"OFFS\"),\n>\n> Do we have an option *not* to record meaningful generation numbers\n> in CDAT and have the current Git binaries understand and still use\n> the rest of the graph file, while not using the optimizations that\n> rely on having generation numbers?  If not, then the new version of\n> Git that tries to be compatible with old one needs to compute both\n> generation numbers, and we would need to keep the topological number\n> for quite some time.\n\nWe can, as Derrick Stolee wrote, put zero (GENERATION_NUMBER_ZERO) for\ngeneration number.  Without generation number data we lose some of\nperformance improvements, though.\n\nOn the other hand computing generation number v1 (topological level) and\ngeneration number v2 ([monotonic] offset for corrected commit date)\nshould not be much more costly than calculating single generation\nnumber, assuming that most of the cost is walking the commit graph.  But\nthis would need benchmarking.\n\nAlso, as Stolee wrote, with generation number v2 in separate chunk we\nhave commit data not together, but split into two areas.\n\n>> and there should be no problems with updating\n>> commit-graph file (either rewriting, or adding new commit-graph to the\n>> chain).\n>\n> Would merging by the current Git also work well (meaning, would\n> \"GEN2\" or whatever it does not understand be omitted)?\n\nFrom the analysis of write_commit_graph_file(), it looks like unknown\nchunks are simply skipped (ommitted), but I have not checked it in\npractice.\n\nBest,\n-- \nJakub Narębski\n"},{"id":"393896","messageId":"xmqq8sjp1mnz.fsf@gitster.c.googlers.com","threadId":"53056","inReplyTo":"86k139ahb7.fsf@gmail.com","subject":"Re: [RFC][GSoC] Implement Generation Number v2","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-03-24T21:13:36Z","receivedAt":"2020-03-24T21:13:49Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jakub Narebski <jnareb@gmail.com> writes:\n\n> Junio C Hamano <gitster@pobox.com> writes:\n>> Jakub Narebski <jnareb@gmail.com> writes:\n>>\n>>> About moving commit data with generation number v2 to \"CDA2\" chunk: if\n>>> \"CDAT\" chunk is missing then (I think) old Git would simply not use\n>>> commit-graph file at all; it may crash, but I don't think so.  If \"CDAT\"\n>>> chunk has zero length... I don't know what would happen then, possibly\n>>> also old Git would simply not use commit-graph data at all.\n>>\n>> Yeah, if it makes it crash, then we cannot use that \"missing CDAT\"\n>> approach.\n>\n> I have not tested this, but from reading the code it looks like \"missing\n> CDAT\" makes Git fail softly -- it would return NULL for the\n> commit-graph, and thus not use commit-graph data at all... which might\n> be too high a price (too high performance penalty for old Git).\n\nOh, that would not make me worried an iota.  If anything, it\nencourages adoption of the new version ;-) As long as the\ncorrectness is not violated, it is fine as a fallback behaviour.\n\n> On the other hand computing generation number v1 (topological level) and\n> generation number v2 ([monotonic] offset for corrected commit date)\n> should not be much more costly than calculating single generation\n> number, assuming that most of the cost is walking the commit graph.  But\n> this would need benchmarking.\n\nGood point.  If we can do so cheaply enough, there is no reason to\nomit the v1 data from the file and stuff placeholder 0 in these\nfields.\n\n> Also, as Stolee wrote, with generation number v2 in separate chunk we\n> have commit data not together, but split into two areas.\n\nYes, that is a problem.  The \"empty CDAT with everything not just\ngeneration numbers in CDA2\" approach would help us move forward with\nv2, while not harming older version of Git.  Just like pack bitmap,\ncommit-graph is designed to be a local optimization matter, and\nworrying about older Git not being able to use the optimization\nhints left by newer version of Git is not useful.  Quite honestly,\nthe only two things we should make sure are that the repository does\nnot appear corrupt and unusable by current Git when it has graph\nfiles with new generation number scheme, and that manipulations by\ncurrent Git of a repository with newer graph files will not corrupt\nthe repository for current or newer Git.\n\nThanks.\n"},{"id":"394080","messageId":"20200326101520.GA19326@Abhishek-Arch","threadId":"53056","inReplyTo":"86mu87qj92.fsf@gmail.com","subject":"[GSoC][Proposal v2] Implement Generation Number v2","fromName":"Abhishek Kumar","fromEmail":"abhishekkumar8222@gmail.com","sentAt":"2020-03-26T10:15:20Z","receivedAt":"2020-03-26T10:18:17Z","isPatch":false,"sender":{"key":"abhishekkumar8222@gmail.com","avatar":"https://avatars.githubusercontent.com/u/31231064?v=4"},"body":"Hello,\n\nThanks to Jakub for the discussion on differentiating between generation\nnumbers and the review.\n\nChanges in v2:\n- Add section on distinguishing generation numbers v1 and v2.\n- Update 'Plan' with new GSoC timeline.\n- Fix incorrect attribution of devising backwards compatible corrected\n  commit dates to Jakub.\n\nYou can alternatively read this with markdown rendered:\nhttps://github.com/abhishekkumar2718/GSoC20/blob/master/generation_number_v2.md\n\nThanks\nAbhishek\n---\n\n# Implement Generation Number v2\n\n## Abstract\n\nGit uses various clever methods for making operations on very large repositories\nfaster, from bitmap indices for git fetch [1], to generation numbers (also known\nas topological levels) in the commit-graph file for commit graph traversal\noperations like git log --graph [2].\n\nHowever, generation numbers do not always improve performance. Stolee has\npreviously explored alternatives for a better generation number [3]. Backward\ncompatible corrected commit date was chosen because of its performance, local\ncomputability, and backward compatibility.\n\n[1]: https://githubengineering.com/counting-objects/\n[2]: https://devblogs.microsoft.com/devops/supercharging-the-git-commit-graph-iii-generations/\n[3]: https://lore.kernel.org/git/6367e30a-1b3a-4fe9-611b-d931f51effef@gmail.com/\n\n## Goals\n\nThis project aims to:\n- Move `generation`, `graph_pos` members of struct commit into a commit slab.\n- Examine methods to distinguish commit-graph with legacy generation number and\ngeneration number v2.\n- Update generation number to v2, modifying all places that reference or\ncompute generation numbers.\n- Use generation numbers to speed up implementation of `--ancestry-path` and\npossibly other commands.\n- Extend Stolee`s performance test suite.\n- Examine performance improvements.\n\n## Overview\n\nGit walks the commit graph for many reasons, including listing and filtering\ncommit history and computing merge bases.\n\nThese operations can become slow as the commit count grows. The two main costs\nhere are decompressing and parsing commits and walking the entire graphs to\nsatisfy topological order constraints.\n\nStolee introduced commit-graph file to accelerate this process. The commit-graph\nfile stores commit graph structure along extra metadata to speed up graph walks.\nA chunk includes commit OID, list of parents, commit date, root tree OID and \ngeneration number.\n\nGeneration number v1 was defined as one more than the length of the longest path\nfrom A to the root commit. Then,\n\n    If A and B are commits with generation numbers N and M, and N <= M, then\n    A cannot reach B.\n\nThis property reduces the time to walk commits and determine topological\nrelationships significantly.\n\n### Performance Regression\n\nWhile testing git v2.19.0-rc1, Stolee came across a performance regression due\nto using topological levels [4]. The discussion can be summarized as:\n\nTopological level changes the order in which the commits are inspected and\ngives a performance regression if it chooses to walk a longer path than\ncompared to date-based heuristic.\n\nFor example, consider the performance before and after using topological levels\non `git merge-base v4.8 v4.9`:\n\n  before topological levels: 0.122s\n   after topological levels: 0.547s\n\n\nThe topology of this can be described as:\n```\n   v4.9\n    |  \\\n    |   \\\n   v4.8  \\\n    | \\   \\\n    |  \\   |\n   ...  A  B\n    |  /  /\n    | /  /\n    |/__/\n    C\n```\n\nHere, the \"...\" means a \"very long line of commits\". A and B have generation\none more than C.\n\nIf we order commits by generation, then commit date, B is removed from the queue\nonly after many commits reachable from v4.8 have been explored.  However, if\nordering by commit date removes A and B from the queue early and C is inserted.\nAs C is processed, the rest of queue is marked as STALE and loop terminates.\n\n[4]: https://lore.kernel.org/git/pull.28.git.gitgitgadget@gmail.com/\n\n### Alternatives to Topological Level\n\nTo improve generation numbers, Stolee investigated other alternative\ndefinitions for generation numbers. The extended exploration and report are\navailable here [5].\n\nCorrected commit date was chosen as the next generation number by overall\nconsensus because of its performance, local computability, and immutability.\n\nHowever, it was not backward compatible with current implementation i.e., older\nclients do not report correct values if they ignore reachability index version.\nExisting clients would fail altogether with commit-graph v2 instead of\nswitching commit-graph feature off, as discovered by Ævar Arnfjörð Bjarmason [6].\n\n[5]: https://lore.kernel.org/git/6367e30a-1b3a-4fe9-611b-d931f51effef@gmail.com/\n[6]: https://lore.kernel.org/git/87a7gdspo4.fsf@evledraar.gmail.com/\n\n### Corrected Commit Date With Strictly Monotonic Offset\n\nCorrected commit date was later modified to _Corrected Commit Date With\nStrictly Monotonic Offset_, defined as follows [7]:\n\nFor a commit C, let its _offset commit date_ (denoted by odate(C))\nbe a commit date plus some offset, i.e. odate(C) = date(C) + offset(C),\nsuch that:\n\n1. Offset commit date is greater than the maximum of the commit date of\n   C and the offset commit dates of its parents.\n\n    If odate(A) < odate(B), then A cannot reach B.\n\n2. The offset of a commit is one more than the maximum offset of a parent, or\n   more.\n\n    If offset(A) < offset(B), then A cannot reach B.\n\nSince the offset are strictly greater than the offset of a parent, the old\nclients give correct values for the odate as well. `git commit-graph verify`\nwould fail since the offsets are not generation numbers in all cases.\n\nThis is an acceptable trade off because users can re-write the commit graph\nafter verify fails.\n \nA rough implementation by Jakub can be read here [8].\n\n[7]: https://lore.kernel.org/git/86o8ziatb2.fsf_-_@gmail.com/\n[8]: https://github.com/derrickstolee/git/pull/10\n\n## Distinguishing Generation Numbers\n\nAs explained above, commit-graph format version cannot be used to distinguish\nbetween generation numbers. We want new Git to recognize if commit-graph uses\ngeneration v1, use those generation numbers correctly and update commit-graph\nfile. The solutions suggested are:\n\n- metadata / versioning chunk: Introduce an optional chunk to store generation\nnumber as metadata and store offsets in CDAT. For a chain of commit-graph files\nwith both versions, best choice would be flatten the chain and recompute values\nfrom scratch.\n\n- new chunk for generation number: Introduce an optional chunk to store the\noffset. Fill in CDAT with either generation zero or compute topological level.\nThis removes the restriction of storing generation number in CDAT. However,\nsince Git lazily parses commit data, seperating generation number from CDAT\nwould increase time spent in I/O.\n\nMetadata chunk seems like the better solution for corrected commit date.\nHowever, generation number chunk should be revisited if later versions of\ngeneration numbers require more than 30 bits.\n\n## Plan\n\n### Community bonding period (May 4 - June 1)\n\n1. Extend Stolee`s performance test suite.\n\nTo investigate replacements for generation numbers, Stolee implemented\nprototypes and compared performance on a range of queries.\n\nIt currently tests:\n- `git log --topo-order -N`: measures commits walked to determine all possible\nways of arriving at given commit.\n- `git log --topo-order -10 A..B`: measures commits walked to determine commits\nreachable from B but not from A.\n- `git merge-base A B`: measures commits walked to find the lowest (closest)\nancestor for both A and B.\n\nWe can also add tests for:\n- `git branch --[no-]contains A`: measures commits walked to determine if A is\nreachable from the tip of a given branch for all branches (many to one query).\n- `git branch --[no-]merged A`: measures commits walked to determine if the tip\nof a given branch is reachable from A for all branches (one to many query).\n- `git push/fetch`: measures commits walked to compute HAVES/WANTS of a client\n(many to many query) [9].\n\n2. Find other operations that can be optimized using generation numbers.\n\nAs Jakub pointed out in the discussion on generation numbers, --ancestry-path\ncan be optimized using generation numbers [10]. Discuss and find any other\noperation which could use generation numbers.\n\n3. Explore commit, commit-graph, commit-reach, revision\n\n[9]: https://github.blog/2015-09-22-counting-objects/\n[10]: https://lore.kernel.org/git/861s82wdbp.fsf@gmail.com/\n\n### Move `generation`, `graph_pos` into a slab (June 1 - June 15, 2 weeks)\n\nstruct commit is used in many contexts. However, the struct members\n`generation` and `graph_pos` are only used for commit-graph related operations\nand otherwise waste memory.\n\nUsing a commit slab reduces space of an individual commit object, which becomes\ncrucial as we load thousands of them. We can dynamically associate commits\nwith their generation/graph positions when needed.\n\nCommit slab for `generation` is 64 bits wide as it stores odate instead\nof offset [11]. Commit slab for `graph_pos` is simpler, with a straightforward\nallocation of 32 bits.\n\nNote: Commit-graph chunks would still store offset and will be used to compute\ncorrected date on initialization.\n\n[11]: https://lore.kernel.org/git/cfa2c367-5cd7-add5-0293-caa75b103f34@gmail.com/\n\n### Implement backward compatible corrected commit date (June 15 - August 2, 7 weeks)\n\n1. Implement metadata chunk (June 15 - June 29, 2 week)\n\n2. Implement backward compatible corrected commit date (June 29 - July 13, 2 weeks)\n\nTopological levels are computed using a DFS in `compute_generation_numbers` of\ncommit-graph.c. The condition\n\n  generation(C) = max(generation(P)) + 1,\n  where C is a commit and P are its parent(s).\n\nneeds to be redefined as:\n\n  generation(C) = max(max(generation(P)), correction(C)) + 1,\n  where correction(C) is max(cdate(P) - cdate(C), 0). \n\nDefinitions of `GENERATION_NUMBER_{INFINITY, MAX, ZERO}` remain the same.\n\nThe functions `compare_commits_by_gen_then_commit_date` and\n`compare_commits_by_commit_date` can be replaced by `compare_commits_by_gen` as\nall three *should* return the same order.\n\n--> First evaluation (June 29 - July 3)\n\n--> End Semester Exams (June 29 - July 4)\n\n3. Update existing references (July 13 - August 2 , 3 weeks)\n\nThe following functions use generation number or committer date for cutoffs:\n- `contains_tag_algo`\n- `can_all_from_reach_with_flag`\n- `paint_down_to_common`\n- `remove_redundant`\n\nAll of these can be updated with little to no changes.\n\n--> Second evaluation (July 27 - July 31)\n\n### Extend generation number to --ancestry-path (August 3 - August 16, 2 weeks)\n\n`--ancestry-path A..B` returns the commits that are both descendants of A and\nancestors of B. The algorithm computes commits that are reachable by B but not\nby A, reverse the graph and walk backwards from A [12].\n\nWe can use generation number to limit walks to find commits reachable by B.\n\n[12]: https://lore.kernel.org/git/0c6b42e4-e825-ff70-a528-e118abf4c435@gmail.com/\n\n### Examine performance improvements (August 17 - August 24, 1 week)\n\n- Compare the performance of generation number v2 versus topological level using\n  performance test suite.\n- Wrap up any existing patches.\n\nThe performance report would be a nice summary my work over the summer.\n\n## Contributions\n\n[Microproject] Consolidate test_cmp_graph logic\n-----\nLog graph comparison logic is duplicated many times. This patch consolidates\ncomparison and sanitation logic in lib-log-graph.\n\nStatus: Merged\n\nPatch: https://lore.kernel.org/git/20200216134750.18947-1-abhishekkumar8222@gmail.com/\n\nCommit: https://github.com/git/git/commit/46703057c1a0f85e24c0144b38c226c6a9ccb737\n\nI have also reviewed patches and discussed queries with other contributors:\n- https://lore.kernel.org/git/CAHk66fskrfcJ0YFDhfimVBTJZB4um7r=GdQuM8heJdZtF8D7UQ@mail.gmail.com/\n- https://lore.kernel.org/git/CAHk66fvt-1RaLK8E7SDpocWM9OMAcA-gP5hjHq6r5N_FbATNgA@mail.gmail.com/\n- https://github.com/git/git/pull/647#issuecomment-591978405\n\nand others.\n\n## Post GSoC\n\nI would love to keep contributing to git after the GSoC period ends. There`s so\nmuch to learn from the community.\n\nHannes`s comment on checks as a penalty that should be paid only by constant\nstrbufs was a perspective I had not considered [13].\n\nInteracting with Kyagi made me rethink the justifications _emphasizing commit\nmessages_. I was at my wit`s end, which makes me appreciate my patient mentors\nmore and want to give back to the community.\n\n[13]: https://lore.kernel.org/git/467c035f-c7cd-01e1-e64c-2c915610de01@kdbg.org/\n\n## About Me\n\nI am Abhishek Kumar, a second-year CSE student at National Institute of\nTechnology Karnataka, India. I have a blog where I talk about my interests -\nprogramming, fiction, and literature [14].\n\nI primarily work with C/C++ and Ruby on Rails. I am a member of my institute`s\nOpen Source Club and student-built University Management System, _IRIS_. I have\nsome experience of mentoring - Creating their code style guide and being an\nactive reviewer [15].\n\n[14]: https://abhishekkumar2718.github.io/\n\n[15]: https://iris.nitk.ac.in/about_us\n\n## Availablity\n\nThe official GSoC coding period runs from June 1 to August 24.\n\nDue to the outbreak of COVID-19 in my country, my college has pre-emptively\nannounced summer vacations from March 17 to June 1. Unfortunately,\nI would have classes for a large part of the coding period. However, I can still\ncontribute 35-40 hours every week due to a low course load (~20 hours a week).\n\nI would not be able to contribute from June 29 to July 4 due to end semester\nexams.  It would be easily compensated during the subsequent \"semester break\"\nfrom July 5 to July 27.\n\n## Contact Information\n\n```\n     Name: Abhishek Kumar\n    Email: abhishekkumar8222@gmail.com\n    Major: Computer Science And Engineering\n   Degree: Bachelor of Technology\nInstitute: National Institute of Technology Karnataka\n   Github: abhishekkumar2718\n Timezone: UTC+5:30 (IST)\n```\n\nThank you for taking the time to review my proposal!\n"}]}