{"thread":{"id":"53759","subject":"Re: [RFC] Metadata vs Generation Data Chunk","startedAt":"2020-06-26T13:46:16Z","lastAt":"2020-06-26T14:40:09Z","messageCount":2,"participants":["Abhishek Kumar","Derrick Stolee"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"400683","messageId":"20200626134422.GA17537@Abhishek-Arch","threadId":"53759","inReplyTo":null,"subject":"Re: [RFC] Metadata vs Generation Data Chunk","fromName":"Abhishek Kumar","fromEmail":"abhishekkumar8222@gmail.com","sentAt":"2020-06-26T13:44:22Z","receivedAt":"2020-06-26T13:46:16Z","isPatch":false,"sender":{"key":"abhishekkumar8222@gmail.com","avatar":"https://avatars.githubusercontent.com/u/31231064?v=4"},"body":"On 22.06.2020 at 13:40, Jakub Narębski wrote:\n> On 22.06.2020 at 11:34, Abhishek Kumar wrote:\n> \n> > One of the remaining pre-requisites for implementing generation number\n> > v2 was distinguishing between corrected commit dates with monotonically\n> > increasing offsets and topological level without incrementing generation\n> > number version.\n> > \n> > Two approaches were proposed [1]:\n> > 1. New chunk for commit data (generation data chunk, \"GDAT\")\n> > 2. Metadata/versioning chunk\n> \n> Actually in [1] there was also proposed another distinct approach,\n> namely to 'rename' the \"CDAT\" chunk to something else, like \"CDA2\"\n> (or proposed here \"GDAT\").\n> \n> If I read the code correctly, with old Git if one of required chunks\n> is missing then Git would continue work as if commit-graph was not\n> present -- as opposed to current handling of unknown commit-graph\n> file format version number, where Git would stop working with an\n> error message.\n> \n\nActually, v2.21.0 (and possibly others) segfault when they encounter a\ncommit-graph without CDAT chunk.\n\nHere's what I did:\n- Create a commit-graph, renaming \"CDAT\" to \"CDA2\" and otherwise\n  identical.\n- Call `git log`.\n- Git segfaults after calling fill_commit_graph_info().\n\nDiff for the hexdump of commit-graph files:\n\n3c3\n< 0000020 4443 3241 0000 0000 0000 a807 0000 0000\n---\n> 0000020 4443 5441 0000 0000 0000 a807 0000 0000\n209,210c209,210\n< 0000dd0 0000 0c00 cd5c d1f7 a34d d713 70d3 114e\n< 0000de0 7b92 131c f605 3b92 856a 2318          \n---\n> 0000dd0 0000 0c00 cd5c d1f7 b474 d280 6b17 2eb2\n> 0000de0 a660 9ed6 04f0 7bed 8cb0 3712          \n\n(They also differ in the hash checksum, but I don't suppose that would\nexplain the segfault.)\n\nWith this, I presume \"CDAT Chunk Replaced With Another Chunk\" is no\nlonger feasible?\n\nThe commit-graph files:\n\"CDA2\" - https://github.com/abhishekkumar2718/GSoC20/blob/master/commit-graph-cda2\n\"CDAT\" - https://github.com/abhishekkumar2718/GSoC20/blob/master/commit-graph-cdat\n\n> \n> > Since both approaches have their advantages and disadvantages, I wrote\n> > up a prototype [2] to investigate their performance.\n> > \n> > [1]: https://lore.kernel.org/git/86mu87qj92.fsf@gmail.com/\n> > [2]: https://github.com/abhishekkumar2718/git/pull/1\n> \n> That's very nice.  Thanks for investigating that.\n> \n> > \n> > TL;DR: I recommend we should use generation data chunk approach.\n> > \n> > Generation Data Chunk\n> > =====================\n> > \n> > We could move the generation number v2 into a separate chunk, storing\n> > topological levels in CDAT and the corrected commit date into a new,\n> > \"GDAT\" chunk.  Thus, old Git would use generation number v1, and\n> > new Git would use corrected commit dates from GDAT.\n> > \n> > Using generation data chunk has the advantage that we would no longer\n> > be restricted to using 30 bits for generation number. It also works\n> > well for commit-graph chains with a mix of v1 and v2 generation numbers.\n> > \n> > However, it increases the time required for I/O as commit data and\n> > generation numbers are no longer contiguous.\n> > \n> > Note: While it also increases disk space required for storing\n> > commit-graph files by 8 bytes per commit, I don't consider it relevant,\n> > especially on modern systems. A repo of the size of Linux repo would be\n> > larger by a mere 7.2 Mb.\n> \n> All right.\n> \n> Another advantage: we don't have to store the corrected committer date\n> _offset_, we can store the date (as epoch) directly.  This saves some\n> calculation, though a minuscule amount.\n> \n> Yet another advantage: we don't need backward-compatibility for\n> generation number v2, i.e. corrected commit date.\n> \n\nThat's actually a great point. This might save us some calculation as we\ndon't need to calculate the \"correction offsets\". \n\n> Another disadvantage: we need to compute both topological levels and\n> corrected commit date when creating a commit-graph file or a chunk of\n> it.  This means that `git commit-graph write` could be slightly more\n> expensive.\n> \n> > \n> > Metadata / Versioning Chunk\n> > ===========================\n> > \n> > We could also introduce an optional metadata chunk to store generation\n> > number version and store corrected date offsets in CDAT. Since the\n> > offsets are backward compatible, Old Git would still yield correct\n> > results by assuming the offsets to be topological levels. New Git would\n> > correctly use the offsets to create corrected commit dates.\n> \n> This also means that we need to use backward-compatible generation\n> number v2, that is corrected commit date with strictly monotonic\n> offsets.  Which may lead to more cases where 30 bits for label is not\n> enough, and thus worse performance (no detailed reachability\n> information for newest commits).\n> \n\nYes, that's definitely possible. Dr. Stolee raised the same point too,\nand I am working on using trace2 API to find the largest offset and the\nnumber of commits for the tests.\n\n> > \n> > It works just as well as generation number v1 in parsing and writing\n> > commit-graph files.\n> > \n> > However, the generation numbers are still restricted to 30 bits in CDAT\n> > chunk and it does not work well with commit-graph chains with a mix of\n> > v1 and v2 generation numbers.\n> \n> \n> CDAT chunk replaced with another chunk\n> ======================================\n> \n> In this approach the \"CDAT\" chunk is missing from the commit-graph file.\n> We can craft the replacement (\"CDA2\") however we like, but it can also\n> look like the \"CDAT\" chunk, only with the offsets for corrected commit\n> date rather than topological level for generation number part (30 bits).\n> \n> If we choose to follow the \"CDAT\" format (modified), then the file\n> size would not change, and neither would change the amount of I/O\n> needed -- there would be the same access structure as in current\n> version.\n> \n> There should be no confusion with a mix of v1 and v2 generation numbers.\n> \n> The disadvantage is of course that older version of Git would no longer\n> be able to make use of serialized commit-graph if the file was written\n> by newer version of Git.\n> \n\nAnother disadvantage is that the CDA2 chunk yet again limits the size of\ngeneration number. Future generation numbers will be restricted to 64\nbits by the design of CDA2.\n\n> > \n> > Performance\n> > ===========\n> \n> What is the repository where those benchmarks took place?\n\nIt's based on the linux repository.\n\n> \n> > | Command                        | Master | Metadata | Generation Data |\n> > |--------------------------------|--------|----------|-----------------|\n> > | git commit-graph write         | 14.45s | 14.28s   | 14.63s          |\n> > | git log --topo-order -10000    | 0.211s | 0.206s   | 0.208s          |\n> > | git log --topo-order -100 A..B | 0.019s | 0.015s   | 0.015s          |\n> > | git merge-base A..B            | 0.137s | 0.137s   | 0.137s          |\n> \n> Nice.\n> \n> How those two (or three) approaches work on gen-test [3] test cases,\n> both in terms of commits walked (extracted via trace2 mechanism) and\n> actual wall-time clock, like in the result above?\n\nSure, will do.\n\n> \n> [3]: https://github.com/derrickstolee/gen-test\n> \n> > - Metadata and generation data chunks perform better than master on\n> >    using commit-graph files since they use corrected commit dates.\n> > \n> > - The increased I/O time for parsing GDAT does not affect performance as\n> >    much as expected.\n> > \n> > - Generation data commit-graph takes longer to write since more\n> >    information is written into the file.\n> > \n> > As using the commit-graph is much more frequent than writing, we can\n> > consider both approaches to perform equally well.\n> > \n> > I prefer generation data chunk approach as it also removes 30-bit length\n> > restriction on generation numbers.\n> \n> Thank you for your work.\n> \n> Best,\n> \n> P.S. I hope I haven't sent it twice...\n> -- \n> Jakub Narębski\n\nThanks\n- Abhishek\n\n----------\n\nMutt has been acting weirdly for replies sent using \"mail\" option. This\nmail is in reply to the following post:\n\nhttps://lore.kernel.org/git/10d99e37-8870-6401-d9aa-21a359b30835@gmail.com/\n"},{"id":"400689","messageId":"3bdbf490-a7ae-2351-9c82-6b19a577b641@gmail.com","threadId":"53759","inReplyTo":"20200626134422.GA17537@Abhishek-Arch","subject":"Re: [RFC] Metadata vs Generation Data Chunk","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2020-06-26T14:40:06Z","receivedAt":"2020-06-26T14:40:09Z","isPatch":false,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 6/26/2020 9:44 AM, Abhishek Kumar wrote:\n> On 22.06.2020 at 13:40, Jakub Narębski wrote:\n>> On 22.06.2020 at 11:34, Abhishek Kumar wrote:\n>>\n>>> One of the remaining pre-requisites for implementing generation number\n>>> v2 was distinguishing between corrected commit dates with monotonically\n>>> increasing offsets and topological level without incrementing generation\n>>> number version.\n>>>\n>>> Two approaches were proposed [1]:\n>>> 1. New chunk for commit data (generation data chunk, \"GDAT\")\n>>> 2. Metadata/versioning chunk\n>>\n>> Actually in [1] there was also proposed another distinct approach,\n>> namely to 'rename' the \"CDAT\" chunk to something else, like \"CDA2\"\n>> (or proposed here \"GDAT\").\n>>\n>> If I read the code correctly, with old Git if one of required chunks\n>> is missing then Git would continue work as if commit-graph was not\n>> present -- as opposed to current handling of unknown commit-graph\n>> file format version number, where Git would stop working with an\n>> error message.\n>>\n> \n> Actually, v2.21.0 (and possibly others) segfault when they encounter a\n> commit-graph without CDAT chunk.\n\nYes, the CDAT chunk is absolutely necessary. It also includes data such as\nthe commit-date, root tree id, and parent information.\n\n> With this, I presume \"CDAT Chunk Replaced With Another Chunk\" is no\n> longer feasible?\n\n\"Replace\" was never on the table (in my mind). Instead, we can\nconsider _adding_ a new chunk that contains the generation number\nv2 data.\n\n\nThanks,\n-Stolee\n"}]}