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