{"thread":{"id":"53776","subject":"Re: [RFC] Metadata vs Generation Data Chunk","startedAt":"2020-06-30T15:03:07Z","lastAt":"2020-07-03T08:30:56Z","messageCount":3,"participants":["Abhishek Kumar","Derrick Stolee"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"400815","messageId":"20200630150056.GA4111@Abhishek-Arch","threadId":"53776","inReplyTo":null,"subject":"Re: [RFC] Metadata vs Generation Data Chunk","fromName":"Abhishek Kumar","fromEmail":"abhishekkumar8222@gmail.com","sentAt":"2020-06-30T15:00:56Z","receivedAt":"2020-06-30T15:03:07Z","isPatch":false,"sender":{"key":"abhishekkumar8222@gmail.com","avatar":"https://avatars.githubusercontent.com/u/31231064?v=4"},"body":"Hello everyone,\n\nI have finished all tests that I can think of and instead of throwing\nperformance numbers at you, I am going to try and tell you a story.\n\nWRITING COMMIT GRAPH\n====================\n\nThe run time of writing a commit-graph is affected by time taken to\ncompute generation number(s) and write them to the file.\n\nWe had the following possible ideas for writing commit-graph:\n\nMO: Calculate generation number V5 and write the offset into CDAT\n    (along with a metadata chunk).\n\nG5O: Calculate generation number V5 and write the corrected date into\n    Generation Data chunk.\n\nG5D: Calculate generation number V5 and write the offset into Generation\n    Data chunk.\n\nG3IO: Calculate generation number V3 and write GENERATION_NUMBER_MAX into\n    CDAT and the offset into Generation Data chunk.\n\nG3ID: Calculate generation number V3 and write GENERATION_NUMBER_MAX into\n    CDAT and the corrected date into Generation Data chunk.\n\nG3TO: Calculate generation number V3 and generation number V0, write\n    topological levels into CDAT and the offset into Generation Data\n    chunk.\n\nG3TD: Calculate generation number V3 and generation number V0, write\n    topological levels into CDAT and the offset into Generation Data\n    chunk.\n\nKey:\n- M -> Metadata, G -> Generation\n- 5 -> Generation Number V5, 3 -> Generation Number V3,\n- T -> Topological level, I (for infinity) -> Generation Number Max\n- O -> Offset, D -> Date\n\nOn the Linux repo with HEAD at 08bf1a27, time is taken by different\nversions:\n\n| Version | time Taken      |\n|---------|-----------------|\n| master  | 14.200s         |\n| MO      | 14.094s         |\n| G5D     | 14.406s         |\n| G5O     | 14.323s         |\n| G3IO    | 14.175s         |\n| G3ID    | 14.258s         |\n| G3TO    | 14.331s         |\n| G3TD    | 14.419s         |\n\nObservations:\n\n- Writing offset (i.e., 32-bits) is faster than writing corrected date \n  (which are 64-bit long). However, we would have to deal with overflow\n  issues.\n\n  The largest offset value observed was of the order 2 ** 29. Assuming\n  no further \"skips\" in offset, we can store around ~635 million\n  commits without overflows. This, however, might not be true for other\n  repositories.\n\n  A repository with a commit with Unix epoch '0' will overflow.\n  If we choose some sane default like commit date must be higher than\n  the release date of git, we can store around 110 million commits even\n  with '0' epoch.\n\n- Calculating topological levels with generation number V3 takes nearly\n  the same time as calculating generation number V5.\n\n- The commit-graph file is larger by 4 Mb (+8%) and 8 Mb (+16%) when\n  storing offsets and dates.\n\nReading Commit Graph\n====================\n\nThe time taken in using commit-graph to answer queries depends on:\n- The number of commits walked.\n- The time taken to load commit data from commit-graph.\n\nNumber of commits walked for different commands:\n\n| Command                         | Master |   V3   |   V5   |\n|---------------------------------|--------|--------|--------|\n| log --topo-order -10000         |  48011 |  49954 |  49933 |\n| log --topo-order -100 v5.4 v5.5 |   3794 |   3314 |   3312 |\n| log --topo-order -100 v4.8 v4.9 |   5736 |   3887 |   3625 |\n| merge-base v5.4 v5.5            |  55053 |  57097 |  55109 |\n| merge-base v4.8 v4.9            | 635579 | 167468 | 506577 |\n\n- For log --topo-order, V3, and V5 walk 35% fewer commits than\n  the topological level when comparing v4.8 and v4.9.\n\n- V3 walks far fewer commits than V5 when comparing by generation\n  numbers and then date for paint_down_to_common(). This is unusual\n  and is probably due to my implementation. Based on log --topo-order,\n  we might expect V5 to perform better than V3.\n \n- V3 walks the same number of commits when compared using commit\n  date for merge-base.\n\nThe time taken for each command rough corresponds to the number of\ncommits walked, with no difference between Metadata chunk and Generation\nData chunk approaches.\n\n| Command                         | Master  |    V3   |   V5   |\n|---------------------------------|---------|---------|--------|\n| log --topo-order -10000         |  0.210s |  0.209s | 0.207s |\n| log --topo-order -100 v5.4 v5.5 |  0.013s |  0.013s | 0.013s |\n| log --topo-order -100 v4.8 v4.9 |  0.015s |  0.013s | 0.013s |\n| merge-base v5.4 v5.5            |  0.048s |  0.047s | 0.047s |\n| merge-base v4.8 v4.9            |  0.135s |  0.133s | 0.134s |\n\nCONCLUSION\n==========\n\nWith all this, my inital recommendation becomes more specific as:\n\n- If overflows are unlikely to happen and not accounted for, implement\n  generation number V5 using metadata chunk. It has the lowest write\n  time and walks just as few commits as V3.\n\n- If overflows are a concern, implement generation number V5 with\n  generation data chunk, storing offsets in generation data chunk.\n\nThanks\n- Abhishek\n"},{"id":"400853","messageId":"cf230320-b661-cc15-ce46-9cdc0250ee1c@gmail.com","threadId":"53776","inReplyTo":"20200630150056.GA4111@Abhishek-Arch","subject":"Re: [RFC] Metadata vs Generation Data Chunk","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2020-06-30T20:46:46Z","receivedAt":"2020-06-30T20:46:53Z","isPatch":false,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 6/30/2020 11:00 AM, Abhishek Kumar wrote:\n> Hello everyone,\n> \n> I have finished all tests that I can think of and instead of throwing\n> performance numbers at you, I am going to try and tell you a story.\n> \n> WRITING COMMIT GRAPH\n> ====================\n> \n> The run time of writing a commit-graph is affected by time taken to\n> compute generation number(s) and write them to the file.\n\nAs you continue, you use V0, V3, and V5 without (re)introducing\nthem. Please ensure these are defined well. This message has \"Re:\"\nin the title, but was removed from the thread somehow in my\ninbox. I don't see a definition of these terms in the thread [1],\neither.\n\n[1] https://lore.kernel.org/git/20200630150056.GA4111@Abhishek-Arch/T/#u\n\nIIRC, we have these modes:\n\nV0: The current generation number gen(C) defined as one more than the\n    maximum gen(P) among parents P of C.\n\nV3: The corrected commit-date given by ccd_3(C) = offset_3(C) + date(C)\n    where offset_3(C) is the minimum non-negative integer such that\n    offset_3(C) + date(C) > offset_3(P) + date(P) for all parents P of C.\n\nV5: The backwards-compatible corrected commit-date is given by\n    ccd_5(C) = offset_5(C) + date(C) where the inequality\n    offset_5(C) + date(C) > offset_5(P) + date(P) holds, but also\n    offset_5(C) > offset_(P) for all parents P of C.\n\nPlease correct me if I am wrong about these definitions.\n\n> We had the following possible ideas for writing commit-graph:\n\nThe options here seem to be a little bit of overkill. Here are the\nones that I would seriously consider:\n \n> MO: Calculate generation number V5 and write the offset into CDAT\n>     (along with a metadata chunk).\n>\n> G3TO: Calculate generation number V3 and generation number V0, write\n>     topological levels into CDAT and the offset into Generation Data\n>     chunk.\n> \n> G3TD: Calculate generation number V3 and generation number V0, write\n>     topological levels into CDAT and the offset into Generation Data\n>     chunk.\n\nI think this last option you meant s/the offset/the corrected date/.\nThis means you are storing the date+offset in the file instead of just\nthe offset.\n\n> | Version | time Taken      |\n> |---------|-----------------|\n> | master  | 14.200s         |\n> | MO      | 14.094s         |\n> | G3TO    | 14.331s         |\n> | G3TD    | 14.419s         |\n\nI don't consider write _time_ to be a huge issue, especially not with\nthese relative values. The SPACE taken by the commit-graph is more\nimportant, and is probably a higher relative change than this time.\n \n> Observations:\n> \n> - Writing offset (i.e., 32-bits) is faster than writing corrected date \n>   (which are 64-bit long). However, we would have to deal with overflow\n>   issues.\n\nPlease keep in mind that the CDAT chunk has a 64-bit \"column\" that\nis split between commit date (34 bits) and generation number (30 bits).\nSo having 32-bit offsets in a new chunk adds some extra flexibility.\n\n>   The largest offset value observed was of the order 2 ** 29. Assuming\n>   no further \"skips\" in offset, we can store around ~635 million\n>   commits without overflows. This, however, might not be true for other\n>   repositories.\n\nWas this the largest required offset for a single commit->parent skew,\nor the cumulative effect of many offsets needing to grow, along with\nthe natural generation number growth? I'm guessing this is just the\nlargest offset that you computed in your write.\n\nSince V3 doesn't require offset_3(C) > offset_3(P), the offsets should\nnaturally \"fix\" themselves over time by decreasing as time moves ahead.\nSo in that sense, I'm rather surprised to see that a 2^29 offset is\nnecessary.\n\nThis does make it seem like V5 should be abandoned because the CDAT\nis running out of room for these offsets, so repos that grow enough\nto overflow will lose any performance benefits from this approach.\n\n>   A repository with a commit with Unix epoch '0' will overflow.\n>   If we choose some sane default like commit date must be higher than\n>   the release date of git, we can store around 110 million commits even\n>   with '0' epoch.\n\nThis really depends on a commit with date '0' having a parent with a\n~30-bit timestamp, OR having many of these kinds of shifts with more\nreasonable dates.\n\n> - Calculating topological levels with generation number V3 takes nearly\n>   the same time as calculating generation number V5.\n> \n> - The commit-graph file is larger by 4 Mb (+8%) and 8 Mb (+16%) when\n>   storing offsets and dates.\n\n8-16% is noticeable, but also not too bad. Thanks for reporting\nthese stats!\n\n> Number of commits walked for different commands:\n> \n> | Command                         | Master |   V3   |   V5   |\n> |---------------------------------|--------|--------|--------|\n> | log --topo-order -10000         |  48011 |  49954 |  49933 |\n> | log --topo-order -100 v5.4 v5.5 |   3794 |   3314 |   3312 |\n> | log --topo-order -100 v4.8 v4.9 |   5736 |   3887 |   3625 |\n> | merge-base v5.4 v5.5            |  55053 |  57097 |  55109 |\n> | merge-base v4.8 v4.9            | 635579 | 167468 | 506577 |\n\nThis last data point is extremely valuable. I think the fact\nthat V5 is closer to V0 here speaks to the negative effect\nof requiring offset_3(C) > offset_3(P).\n \n> - For log --topo-order, V3, and V5 walk 35% fewer commits than\n>   the topological level when comparing v4.8 and v4.9.\n> \n> - V3 walks far fewer commits than V5 when comparing by generation\n>   numbers and then date for paint_down_to_common(). This is unusual\n>   and is probably due to my implementation. Based on log --topo-order,\n>   we might expect V5 to perform better than V3.\n\nThe v4.8 to v4.9 case is particularly nasty in a way that\ndoesn't cause issues with topo-order walks. This is the\nbig reason we are pursuing this at all!\n\n> - V3 walks the same number of commits when compared using commit\n>   date for merge-base.\n> \n> The time taken for each command rough corresponds to the number of\n> commits walked, with no difference between Metadata chunk and Generation\n> Data chunk approaches.\n> \n> | Command                         | Master  |    V3   |   V5   |\n> |---------------------------------|---------|---------|--------|\n> | log --topo-order -10000         |  0.210s |  0.209s | 0.207s |\n> | log --topo-order -100 v5.4 v5.5 |  0.013s |  0.013s | 0.013s |\n> | log --topo-order -100 v4.8 v4.9 |  0.015s |  0.013s | 0.013s |\n> | merge-base v5.4 v5.5            |  0.048s |  0.047s | 0.047s |\n> | merge-base v4.8 v4.9            |  0.135s |  0.133s | 0.134s |\n\nAre you sure these timings are correct for the last row? It\nseems that the times would be more significantly different\nfor the number of commits that were walked. Keep in mind that\nwe should be reporting these merge-base timings when\npaint_down_to_common() has its priority queue set to pull\nthe maximum generation number (V0, V3, or V5) in order to\nreally compare. It seems like that was done correctly in\nthe commit count, but this data seems to imply something\nelse.\n\n> - If overflows are unlikely to happen and not accounted for, implement\n>   generation number V5 using metadata chunk. It has the lowest write\n>   time and walks just as few commits as V3.\n\n(For the \"merge-base v4.8 v4.9\" case, this is untrue.)\n \n> - If overflows are a concern, implement generation number V5 with\n>   generation data chunk, storing offsets in generation data chunk.\n\nHere is an excellent time to be REALLY clear about what you mean\nabout V3 and V5.\n\nDo you have these prototypes available somewhere so others can\ntest? That would also help in verifying these results. It\nwould be enough to push the code to a public Git hosting service\nso we can fetch your commits, build, and test. These don't need\nto be submission-ready patches.\n\nThanks for doing all this work! We are getting closer and closer\nto a final direction.\n\n-Stolee\n"},{"id":"401007","messageId":"20200703082842.GA28027@Abhishek-Arch","threadId":"53776","inReplyTo":"cf230320-b661-cc15-ce46-9cdc0250ee1c@gmail.com","subject":"Re: [RFC] Metadata vs Generation Data Chunk","fromName":"Abhishek Kumar","fromEmail":"abhishekkumar8222@gmail.com","sentAt":"2020-07-03T08:29:02Z","receivedAt":"2020-07-03T08:30:56Z","isPatch":false,"sender":{"key":"abhishekkumar8222@gmail.com","avatar":"https://avatars.githubusercontent.com/u/31231064?v=4"},"body":"On Tue, Jun 30, 2020 at 04:46:46PM -0400, Derrick Stolee wrote:\n> On 6/30/2020 11:00 AM, Abhishek Kumar wrote:\n> > Hello everyone,\n> > \n> > I have finished all tests that I can think of and instead of throwing\n> > performance numbers at you, I am going to try and tell you a story.\n> > \n> > WRITING COMMIT GRAPH\n> > ====================\n> > \n> > The run time of writing a commit-graph is affected by time taken to\n> > compute generation number(s) and write them to the file.\n> \n> As you continue, you use V0, V3, and V5 without (re)introducing\n> them. Please ensure these are defined well. This message has \"Re:\"\n> in the title, but was removed from the thread somehow in my\n> inbox. I don't see a definition of these terms in the thread [1],\n> either.\n> \n> [1] https://lore.kernel.org/git/20200630150056.GA4111@Abhishek-Arch/T/#u\n> \n> IIRC, we have these modes:\n> \n> V0: The current generation number gen(C) defined as one more than the\n>     maximum gen(P) among parents P of C.\n> \n> V3: The corrected commit-date given by ccd_3(C) = offset_3(C) + date(C)\n>     where offset_3(C) is the minimum non-negative integer such that\n>     offset_3(C) + date(C) > offset_3(P) + date(P) for all parents P of C.\n> \n> V5: The backwards-compatible corrected commit-date is given by\n>     ccd_5(C) = offset_5(C) + date(C) where the inequality\n>     offset_5(C) + date(C) > offset_5(P) + date(P) holds, but also\n>     offset_5(C) > offset_(P) for all parents P of C.\n> \n> Please correct me if I am wrong about these definitions.\n> \n\nYes, these are correct.\n\n> > We had the following possible ideas for writing commit-graph:\n> \n> The options here seem to be a little bit of overkill. Here are the\n> ones that I would seriously consider:\n>  \n> > MO: Calculate generation number V5 and write the offset into CDAT\n> >     (along with a metadata chunk).\n> >\n> > G3TO: Calculate generation number V3 and generation number V0, write\n> >     topological levels into CDAT and the offset into Generation Data\n> >     chunk.\n> > \n> > G3TD: Calculate generation number V3 and generation number V0, write\n> >     topological levels into CDAT and the offset into Generation Data\n> >     chunk.\n> \n> I think this last option you meant s/the offset/the corrected date/.\n> This means you are storing the date+offset in the file instead of just\n> the offset.\n\nRight, thanks for correcting.\n\n> \n> > | Version | time Taken      |\n> > |---------|-----------------|\n> > | master  | 14.200s         |\n> > | MO      | 14.094s         |\n> > | G3TO    | 14.331s         |\n> > | G3TD    | 14.419s         |\n> \n> I don't consider write _time_ to be a huge issue, especially not with\n> these relative values. The SPACE taken by the commit-graph is more\n> important, and is probably a higher relative change than this time.\n>  \n> > Observations:\n> > \n> > - Writing offset (i.e., 32-bits) is faster than writing corrected date \n> >   (which are 64-bit long). However, we would have to deal with overflow\n> >   issues.\n> \n> Please keep in mind that the CDAT chunk has a 64-bit \"column\" that\n> is split between commit date (34 bits) and generation number (30 bits).\n> So having 32-bit offsets in a new chunk adds some extra flexibility.\n\nHuh, I didn't think of that at all. Do we have some possible use in\nmind?\n\n> \n> >   The largest offset value observed was of the order 2 ** 29. Assuming\n> >   no further \"skips\" in offset, we can store around ~635 million\n> >   commits without overflows. This, however, might not be true for other\n> >   repositories.\n> \n> Was this the largest required offset for a single commit->parent skew,\n> or the cumulative effect of many offsets needing to grow, along with\n> the natural generation number growth? I'm guessing this is just the\n> largest offset that you computed in your write.\n> \n> Since V3 doesn't require offset_3(C) > offset_3(P), the offsets should\n> naturally \"fix\" themselves over time by decreasing as time moves ahead.\n> So in that sense, I'm rather surprised to see that a 2^29 offset is\n> necessary.\n> \n\nThis was the cumulative effect of both of offsets and the generation\nnumber growth. If we require just ccd(C) > ccd(P), the largest offset\nwas 25960236, merely of the order 2 ^ 25.\n\n> This does make it seem like V5 should be abandoned because the CDAT\n> is running out of room for these offsets, so repos that grow enough\n> to overflow will lose any performance benefits from this approach.\n> \n> >   A repository with a commit with Unix epoch '0' will overflow.\n> >   If we choose some sane default like commit date must be higher than\n> >   the release date of git, we can store around 110 million commits even\n> >   with '0' epoch.\n> \n> This really depends on a commit with date '0' having a parent with a\n> ~30-bit timestamp, OR having many of these kinds of shifts with more\n> reasonable dates.\n> \n> > - Calculating topological levels with generation number V3 takes nearly\n> >   the same time as calculating generation number V5.\n> > \n> > - The commit-graph file is larger by 4 Mb (+8%) and 8 Mb (+16%) when\n> >   storing offsets and dates.\n> \n> 8-16% is noticeable, but also not too bad. Thanks for reporting\n> these stats!\n> \n> > Number of commits walked for different commands:\n> > \n> > | Command                         | Master |   V3   |   V5   |\n> > |---------------------------------|--------|--------|--------|\n> > | log --topo-order -10000         |  48011 |  49954 |  49933 |\n> > | log --topo-order -100 v5.4 v5.5 |   3794 |   3314 |   3312 |\n> > | log --topo-order -100 v4.8 v4.9 |   5736 |   3887 |   3625 |\n> > | merge-base v5.4 v5.5            |  55053 |  57097 |  55109 |\n> > | merge-base v4.8 v4.9            | 635579 | 167468 | 506577 |\n> \n> This last data point is extremely valuable. I think the fact\n> that V5 is closer to V0 here speaks to the negative effect\n> of requiring offset_3(C) > offset_3(P).\n>  \n\nWoah! I was working more or less with the assumption that V5 performs at\nleast as well as V3 and blamed my implementation of it.\n\n> > - For log --topo-order, V3, and V5 walk 35% fewer commits than\n> >   the topological level when comparing v4.8 and v4.9.\n> > \n> > - V3 walks far fewer commits than V5 when comparing by generation\n> >   numbers and then date for paint_down_to_common(). This is unusual\n> >   and is probably due to my implementation. Based on log --topo-order,\n> >   we might expect V5 to perform better than V3.\n> \n> The v4.8 to v4.9 case is particularly nasty in a way that\n> doesn't cause issues with topo-order walks. This is the\n> big reason we are pursuing this at all!\n> \n>\n> > - V3 walks the same number of commits when compared using commit\n> >   date for merge-base.\n> > \n> > The time taken for each command rough corresponds to the number of\n> > commits walked, with no difference between Metadata chunk and Generation\n> > Data chunk approaches.\n> > \n> > | Command                         | Master  |    V3   |   V5   |\n> > |---------------------------------|---------|---------|--------|\n> > | log --topo-order -10000         |  0.210s |  0.209s | 0.207s |\n> > | log --topo-order -100 v5.4 v5.5 |  0.013s |  0.013s | 0.013s |\n> > | log --topo-order -100 v4.8 v4.9 |  0.015s |  0.013s | 0.013s |\n> > | merge-base v5.4 v5.5            |  0.048s |  0.047s | 0.047s |\n> > | merge-base v4.8 v4.9            |  0.135s |  0.133s | 0.134s |\n> \n> Are you sure these timings are correct for the last row? It\n> seems that the times would be more significantly different\n> for the number of commits that were walked. Keep in mind that\n> we should be reporting these merge-base timings when\n> paint_down_to_common() has its priority queue set to pull\n> the maximum generation number (V0, V3, or V5) in order to\n> really compare. It seems like that was done correctly in\n> the commit count, but this data seems to imply something\n> else.\n\nI hadn't timed it correctly. Forgot to set the env variable for stric\ncomparision by generation numbers.\n\nThe number of commits walked:\n\n| merge-base v5.4 v5.5 |  55053 |  55109 |  57098 |\n| merge-base v4.8 v4.9 | 635579 | 506577 | 167496 |\n\nThe timings:\n\n| merge-base v5.4 v5.5 | 0.046s | 0.046s | 0.049s |\n| merge-base v4.8 v4.9 | 0.670s | 0.499s | 0.157s |\n\nWhich neatly corresponds to the number of commits walked.\n\n> \n> > - If overflows are unlikely to happen and not accounted for, implement\n> >   generation number V5 using metadata chunk. It has the lowest write\n> >   time and walks just as few commits as V3.\n> \n> (For the \"merge-base v4.8 v4.9\" case, this is untrue.)\n>  \n> > - If overflows are a concern, implement generation number V5 with\n> >   generation data chunk, storing offsets in generation data chunk.\n> \n> Here is an excellent time to be REALLY clear about what you mean\n> about V3 and V5.\n\nWith the clarity that corrected commit dates with monotonic offset does\nnot perform better than corrected commit dates (and my implementation\nwas probably correct), we should implement store topological levels into\nCDAT and the (not strictly monotonic) offsets into generation data\nchunk.\n\n> \n> Do you have these prototypes available somewhere so others can\n> test? That would also help in verifying these results. It\n> would be enough to push the code to a public Git hosting service\n> so we can fetch your commits, build, and test. These don't need\n> to be submission-ready patches.\n> \n\nYeah, I do. Added better instructions and more information now.\n\nIt should build, and you can replicate the tests by setting $linux_dir\nand running gen_perf.sh. The script would print the timing results and\ncreate tracer reports with filenames `master.perf`, `gen_v3.perf` and\n`gen_v5.perf`.\n\n[1]: https://github.com/abhishekkumar2718/git/pull/1\n\n> Thanks for doing all this work! We are getting closer and closer\n> to a final direction.\n> \n> -Stolee\n\nThanks for the reviews and the discussion!\nAbhishek\n"}]}