{"thread":{"id":"53803","subject":"[GSOC] Blog about weeks 4, 5","startedAt":"2020-07-07T02:26:21Z","lastAt":"2020-07-14T06:25:40Z","messageCount":3,"participants":["Abhishek Kumar","Jakub Narębski"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"401065","messageId":"20200707022425.GA1649@Abhishek-Arch","threadId":"53803","inReplyTo":"20200706182213.GA51227@Abhishek-Arch","subject":"[GSOC] Blog about weeks 4, 5","fromName":"Abhishek Kumar","fromEmail":"abhishekkumar8222@gmail.com","sentAt":"2020-07-07T02:24:25Z","receivedAt":"2020-07-07T02:26:21Z","isPatch":false,"sender":{"key":"abhishekkumar8222@gmail.com","avatar":"https://avatars.githubusercontent.com/u/31231064?v=4"},"body":"Hello everyone!\n\nOver the last two weeks, I have worked on refining the performance\nreport on generation numbers. Here are our conclusions:\n\n- Corrected Commit Dates With Monotonically Offset (i.e.  generation\n  number v5) performs better than topological levels but is still walks\n  too many commits when compared with Corrected Commit Dates.\n\nNumber of commits walked (git merge-base v4.8 v4.9, on linux repository):\n\nTopological Level                          : 635579\nCorrected Commit Date                      : 167468\nCorrected Commit Date With Monotonic Offset: 506577\n\nAs such, I am expecting that we will store Corrected Commit Date in an\nadditional chunk (called \"generation data chunk\") and store topological\nlevels into CDAT. Thus, old Git clients can operate as expected, with\nnew Git clients using the better generation number.\n\n- Using a new chunk does affect the locality of reference but did not\n  impact the performance appreciably.\n- This does increase the size of commit graph file by nearly 5%.\n\nYou can read more in my report [1] and the pull request with\ninstructions to replicate the results [2].\n\n[1]: https://lore.kernel.org/git/20200703082842.GA28027@Abhishek-Arch/T/#mda33f6e13873df55901768e8fd6d774282002146\n[2]: https://github.com/abhishekkumar2718/git/pull/1\n\nI talk a bit more about a patch I worked on, trying to improve\nperformance of commit graph write using buffers which ultimately did not\nwork and is dropped. Up next is actually implementing the generation\nnumber and take care of all little details.\n\nhttps://abhishekkumar2718.github.io/programming/2020/07/05/gsoc-weeks-4-5.html\n\nFeedback and suggestions welcome!\n\nThanks\n- Abhishek\n\n--------\n\nRe-sending this email as I forgot to cc git@vger.kernel.org\n"},{"id":"401508","messageId":"85imerqj7g.fsf@gmail.com","threadId":"53803","inReplyTo":"20200707022425.GA1649@Abhishek-Arch","subject":"Re: [GSOC] Blog about weeks 4, 5","fromName":"Jakub Narębski","fromEmail":"jnareb@gmail.com","sentAt":"2020-07-13T20:00:03Z","receivedAt":"2020-07-13T20:00:10Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Abhishek Kumar <abhishekkumar8222@gmail.com> writes:\n\n> Hello everyone!\n>\n> Over the last two weeks, I have worked on refining the performance\n> report on generation numbers. Here are our conclusions:\n>\n> - Corrected Commit Dates With Monotonically Offset (i.e.  generation\n>   number v5) performs better than topological levels but is still walks\n>   too many commits when compared with Corrected Commit Dates.\n\nThank you for your work examining different approaches to introducing\ngeneration number v2.\n\n> Number of commits walked (git merge-base v4.8 v4.9, on linux repository):\n>\n> Topological Level                          : 635579\n> Corrected Commit Date                      : 167468\n> Corrected Commit Date With Monotonic Offset: 506577\n\nIt is a bit strange that requiring monotonic offsets leads to so much\nof a difference in performance (in commits walked).\n\n>\n> As such, I am expecting that we will store Corrected Commit Date in an\n> additional chunk (called \"generation data chunk\") and store topological\n> levels into CDAT. Thus, old Git clients can operate as expected, with\n> new Git clients using the better generation number.\n>\n> - Using a new chunk does affect the locality of reference but did not\n>   impact the performance appreciably.\n> - This does increase the size of commit graph file by nearly 5%.\n\nAll right, it seems like it is the way to go.\n\n> You can read more in my report [1] and the pull request with\n> instructions to replicate the results [2].\n>\n> [1]: https://lore.kernel.org/git/20200703082842.GA28027@Abhishek-Arch/T/#mda33f6e13873df55901768e8fd6d774282002146\n> [2]: https://github.com/abhishekkumar2718/git/pull/1\n>\n> I talk a bit more about a patch I worked on, trying to improve\n> performance of commit graph write using buffers which ultimately did not\n> work and is dropped. Up next is actually implementing the generation\n> number and take care of all little details.\n>\n> https://abhishekkumar2718.github.io/programming/2020/07/05/gsoc-weeks-4-5.html\n>\n> Feedback and suggestions welcome!\n\nSome comments about the blog entry contents:\n\nAK> Dr. Stolee pointed out ... [to] use the number of commits as a\nAK> metric instead of wall clock timing (which can be influenced by other\nAK> factors like CPU usage at the time).\n\nThere are a few factors.  If we compare similar algorithms, that might\nbe a good decision.\n\nFirst, one can try to reduce the influence of random factors on the wall\nclock timing by using statistics.  For example one can try to detect and\nremove outliers by using robust statistics measures to detect them, like\ntools like for example Dumbbench [3], hyperfine [4] or bench [5].  After\nwarmup, one approach is to compute the robust estimate of value, e.g.\nmedian, and robust estimate of dispersion, e.g. MAD = median absolute\ndeviation, and use those to detect outliers, e.g. rescale MAD and mark\nas outlier and remove entries that are more than \"three sigma\" of robust\ndispersion away from robust estimate of value.  Dumbbench [3] has good\nexplanation.\n\n[3]: https://metacpan.org/pod/Dumbbench#HOW-IT-WORKS-AND-WHY-IT-DOESN'T\n[4]: https://github.com/sharkdp/hyperfine\n[5]: https://github.com/Gabriel439/bench\n\nSecond, because of pecularities of current processor architecture\n(caches, data prefetching, branch prediction) performing more operations\nmight in admittedly rare cases be faster than doing less operations. One\nsuch example can be found in the CppCon 2019 talk by Andrei Alexandrescu\n\"Speed Is Found In The Minds of People\" [6][7] about 'small sort', where\ndoing more operations results in, on average, faster sort.  This of\ncourse has a possibility to happen only if difference with the number of\noperations is small enough... nevertheless it might be a good idea to at\nleast check that the wall clock time agrees with conclusions from the\nnumber of commits walked, for at least a few examples.\n\n[6]: https://www.youtube.com/watch?v=FJJTYQYB1JQ\n[7]: https://github.com/CppCon/CppCon2019/blob/master/Presentations/speed_is_found_in_the_minds_of_people/speed_is_found_in_the_minds_of_people__andrei_alexandrescu__cppcon_2019.pdf\n\nAK> With the second report, storing corrected commit date in GDAT as\nAK> well as computing topological levels seems like a no-brainer. I have\nAK> started working on the patch and will push to the mailing list after\nAK> some discussion on the report.\n\nDo you have any numbers how much does providing backward compatibility\ncost at `git commit-graph write`, that is how much more time it takes to\ncomputer topological levels during computation of corrected\ncommitterdate compared to storing GENERATION_NUMBER_MAX in place of\ntopological level, and whether having topological level (as tie-breaker)\nhelps with Git performance when using commit-graphh for querying?  Does\nhaving topological levels as tie-breaker or secondary negative-cut\nreachability index helps at all?\n\n\nThank you for your work and for the report.\n\nP.S. Would it be possible to put GSoC entries into separate 'GSoC'\ncategory instead of generic 'Programming' one, or add a 'GSoC' tag?\n\nBest,\n--\nJakub Narębski\n"},{"id":"401539","messageId":"20200714062339.GA10242@Abhishek-Arch","threadId":"53803","inReplyTo":"85imerqj7g.fsf@gmail.com","subject":"Re: [GSOC] Blog about weeks 4, 5","fromName":"Abhishek Kumar","fromEmail":"abhishekkumar8222@gmail.com","sentAt":"2020-07-14T06:23:39Z","receivedAt":"2020-07-14T06:25:40Z","isPatch":false,"sender":{"key":"abhishekkumar8222@gmail.com","avatar":"https://avatars.githubusercontent.com/u/31231064?v=4"},"body":"On Mon, Jul 13, 2020 at 10:00:03PM +0200, Jakub Narębski wrote:\n> Abhishek Kumar <abhishekkumar8222@gmail.com> writes:\n> \n> > Hello everyone!\n> >\n> > Over the last two weeks, I have worked on refining the performance\n> > report on generation numbers. Here are our conclusions:\n> >\n> > - Corrected Commit Dates With Monotonically Offset (i.e.  generation\n> >   number v5) performs better than topological levels but is still walks\n> >   too many commits when compared with Corrected Commit Dates.\n> \n> Thank you for your work examining different approaches to introducing\n> generation number v2.\n> \n> > Number of commits walked (git merge-base v4.8 v4.9, on linux repository):\n> >\n> > Topological Level                          : 635579\n> > Corrected Commit Date                      : 167468\n> > Corrected Commit Date With Monotonic Offset: 506577\n> \n> It is a bit strange that requiring monotonic offsets leads to so much\n> of a difference in performance (in commits walked).\n> \n> >\n> > As such, I am expecting that we will store Corrected Commit Date in an\n> > additional chunk (called \"generation data chunk\") and store topological\n> > levels into CDAT. Thus, old Git clients can operate as expected, with\n> > new Git clients using the better generation number.\n> >\n> > - Using a new chunk does affect the locality of reference but did not\n> >   impact the performance appreciably.\n> > - This does increase the size of commit graph file by nearly 5%.\n> \n> All right, it seems like it is the way to go.\n> \n> > You can read more in my report [1] and the pull request with\n> > instructions to replicate the results [2].\n> >\n> > [1]: https://lore.kernel.org/git/20200703082842.GA28027@Abhishek-Arch/T/#mda33f6e13873df55901768e8fd6d774282002146\n> > [2]: https://github.com/abhishekkumar2718/git/pull/1\n> >\n> > I talk a bit more about a patch I worked on, trying to improve\n> > performance of commit graph write using buffers which ultimately did not\n> > work and is dropped. Up next is actually implementing the generation\n> > number and take care of all little details.\n> >\n> > https://abhishekkumar2718.github.io/programming/2020/07/05/gsoc-weeks-4-5.html\n> >\n> > Feedback and suggestions welcome!\n> \n> Some comments about the blog entry contents:\n> \n> AK> Dr. Stolee pointed out ... [to] use the number of commits as a\n> AK> metric instead of wall clock timing (which can be influenced by other\n> AK> factors like CPU usage at the time).\n> \n> There are a few factors.  If we compare similar algorithms, that might\n> be a good decision.\n> \n> First, one can try to reduce the influence of random factors on the wall\n> clock timing by using statistics.  For example one can try to detect and\n> remove outliers by using robust statistics measures to detect them, like\n> tools like for example Dumbbench [3], hyperfine [4] or bench [5].  After\n> warmup, one approach is to compute the robust estimate of value, e.g.\n> median, and robust estimate of dispersion, e.g. MAD = median absolute\n> deviation, and use those to detect outliers, e.g. rescale MAD and mark\n> as outlier and remove entries that are more than \"three sigma\" of robust\n> dispersion away from robust estimate of value.  Dumbbench [3] has good\n> explanation.\n> \n> [3]: https://metacpan.org/pod/Dumbbench#HOW-IT-WORKS-AND-WHY-IT-DOESN'T\n> [4]: https://github.com/sharkdp/hyperfine\n> [5]: https://github.com/Gabriel439/bench\n\nThat's interesting. When you think about it, medians are a better\nmeasure than average because medians are robust to the outliers.\n\n> \n> Second, because of pecularities of current processor architecture\n> (caches, data prefetching, branch prediction) performing more operations\n> might in admittedly rare cases be faster than doing less operations. One\n> such example can be found in the CppCon 2019 talk by Andrei Alexandrescu\n> \"Speed Is Found In The Minds of People\" [6][7] about 'small sort', where\n> doing more operations results in, on average, faster sort.  This of\n> course has a possibility to happen only if difference with the number of\n> operations is small enough... nevertheless it might be a good idea to at\n> least check that the wall clock time agrees with conclusions from the\n> number of commits walked, for at least a few examples.\n> \n> [6]: https://www.youtube.com/watch?v=FJJTYQYB1JQ\n> [7]: https://github.com/CppCon/CppCon2019/blob/master/Presentations/speed_is_found_in_the_minds_of_people/speed_is_found_in_the_minds_of_people__andrei_alexandrescu__cppcon_2019.pdf\n> \n> AK> With the second report, storing corrected commit date in GDAT as\n> AK> well as computing topological levels seems like a no-brainer. I have\n> AK> started working on the patch and will push to the mailing list after\n> AK> some discussion on the report.\n> \n> Do you have any numbers how much does providing backward compatibility\n> cost at `git commit-graph write`, that is how much more time it takes to\n> computer topological levels during computation of corrected\n> committerdate compared to storing GENERATION_NUMBER_MAX in place of\n> topological level, and whether having topological level (as tie-breaker)\n> helps with Git performance when using commit-graphh for querying?  Does\n> having topological levels as tie-breaker or secondary negative-cut\n> reachability index helps at all?\n> \nWe do have timings comparing the time to compute topological levels as\ncompared to storing GENERATION_NUMBER_MAX in place [1]:\n\nWriting GENERATION_NUMBER_MAX to commit-graph: 14.175s\nWriting topological levels to commit-graph:    14.331s\n\nThat's around 160ms and 1% percent faster.\n\nI do think there's a case to be made for GENERATION_NUMBER_MAX because\nthe performance degradation for old Git would help in faster adoption\n(Junio was in favor of this, the last time we discussed alternatives [2]).\nIt is a double-edged sword as we force people who cannot upgrade git\ninto worse performance.\n\nI do not have anything for using topological level as a tie-breaker.\nWill benchmark and get back to you.\n\n[1]: https://lore.kernel.org/git/20200630150056.GA4111@Abhishek-Arch/\n[2]: https://lore.kernel.org/git/xmqq8sjp1mnz.fsf@gitster.c.googlers.com/\n\n> \n> Thank you for your work and for the report.\n> \n> P.S. Would it be possible to put GSoC entries into separate 'GSoC'\n> category instead of generic 'Programming' one, or add a 'GSoC' tag?\n> \n\nGreat idea! Try this out: https://abhishekkumar2718.github.io/gsoc/\n\n> Best,\n> --\n> Jakub Narębski\n"}]}