{"thread":{"id":"50618","subject":"Questions on GSoC 2019 Ideas","startedAt":"2019-02-28T21:46:49Z","lastAt":"2019-04-07T23:43:34Z","messageCount":24,"participants":["Matheus Tavares Bernardino","Christian Couder","Duy Nguyen","Johannes Schindelin","Thomas Gummerer","Jeff King","Mike Hommey"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"370391","messageId":"CAHd-oW7onvn4ugEjXzAX_OSVEfCboH3-FnGR00dU8iaoc+b8=Q@mail.gmail.com","threadId":"50618","inReplyTo":null,"subject":"Questions on GSoC 2019 Ideas","fromName":"Matheus Tavares Bernardino","fromEmail":"matheus.bernardino@usp.br","sentAt":"2019-02-28T21:46:36Z","receivedAt":"2019-02-28T21:46:49Z","isPatch":false,"sender":{"key":"matheus.tavb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/12701583?v=4"},"body":"Hi, everyone\n\nI've been in the mailing list for a couple weeks now, mainly working\non my gsoc micro-project[1] and in other patches that derived from it.\nI also have been contributing to the Linux Kernel for half an year,\nbut am now mainly just supporting other students here at USP.\n\nI have read the ideas page for the GSoC 2019 and many of them interest\nme. Also, looking around git-dev materials on the web, I got to the\nGSoC 2012 ideas page. And this one got my attention:\nhttps://github.com/peff/git/wiki/SoC-2012-Ideas#improving-parallelism-in-various-commands\n\nI'm interested in parallel computing and that has been my research\ntopic for about an year now. So I would like to ask what's the status\nof this GSoC idea. I've read git-grep and saw that it is already\nparallel, but I was wondering if there is any other section in git in\nwhich it was already considered to bring parallelism, seeking to\nachieve greater performance. And also, if this could, perhaps, be a\nGSoC project.\n\nI'm also interested in the 'convert script to builtin' task, and I was\nwondering if 'git-bisect' would be a good candidate for that.\n\nThanks,\nMatheus Tavares\n\n[1]: https://public-inbox.org/git/20190226051804.10631-1-matheus.bernardino@usp.br/\n"},{"id":"370392","messageId":"CAP8UFD0jF5k31tBhj=bQMGOJKN8-F-Rx7RXF1SHZ22LEgSo9_Q@mail.gmail.com","threadId":"50618","inReplyTo":"CAHd-oW7onvn4ugEjXzAX_OSVEfCboH3-FnGR00dU8iaoc+b8=Q@mail.gmail.com","subject":"Re: Questions on GSoC 2019 Ideas","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2019-02-28T22:07:37Z","receivedAt":"2019-02-28T22:07:53Z","isPatch":false,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"Hi Matheus,\n\nOn Thu, Feb 28, 2019 at 10:46 PM Matheus Tavares Bernardino\n wrote:\n>\n> I've been in the mailing list for a couple weeks now, mainly working\n> on my gsoc micro-project[1] and in other patches that derived from it.\n> I also have been contributing to the Linux Kernel for half an year,\n> but am now mainly just supporting other students here at USP.\n>\n> I have read the ideas page for the GSoC 2019 and many of them interest\n> me. Also, looking around git-dev materials on the web, I got to the\n> GSoC 2012 ideas page. And this one got my attention:\n> https://github.com/peff/git/wiki/SoC-2012-Ideas#improving-parallelism-in-various-commands\n>\n> I'm interested in parallel computing and that has been my research\n> topic for about an year now. So I would like to ask what's the status\n> of this GSoC idea. I've read git-grep and saw that it is already\n> parallel, but I was wondering if there is any other section in git in\n> which it was already considered to bring parallelism, seeking to\n> achieve greater performance. And also, if this could, perhaps, be a\n> GSoC project.\n\nI vaguely remember that we thought at one point that all the low\nhanging fruits had already been taken in this area but I might be\nwrong.\n\n> I'm also interested in the 'convert script to builtin' task, and I was\n> wondering if 'git-bisect' would be a good candidate for that.\n\nThere is an ongoing work on that by Tanushree Tumane, an Outreachy\nintern. The end of the internship is March 5, but it seems to me that\nthere is not a lot of work left on the project, and hopefully\nTanushree or her mentors will take care of that.\n\nBest,\nChristian.\n\n> Thanks,\n> Matheus Tavares\n>\n> [1]: https://public-inbox.org/git/20190226051804.10631-1-matheus.bernardino@usp.br/\n"},{"id":"370410","messageId":"CACsJy8AL7DMbV7hhNeb1beucxQnZBHfgv4xo9dK5T+WCK7Q6yw@mail.gmail.com","threadId":"50618","inReplyTo":"CAP8UFD0jF5k31tBhj=bQMGOJKN8-F-Rx7RXF1SHZ22LEgSo9_Q@mail.gmail.com","subject":"Re: Questions on GSoC 2019 Ideas","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2019-03-01T09:30:47Z","receivedAt":"2019-03-01T09:31:16Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Fri, Mar 1, 2019 at 5:20 AM Christian Couder\n wrote:\n>\n> Hi Matheus,\n>\n> On Thu, Feb 28, 2019 at 10:46 PM Matheus Tavares Bernardino\n> wrote:\n> >\n> > I've been in the mailing list for a couple weeks now, mainly working\n> > on my gsoc micro-project[1] and in other patches that derived from it.\n> > I also have been contributing to the Linux Kernel for half an year,\n> > but am now mainly just supporting other students here at USP.\n> >\n> > I have read the ideas page for the GSoC 2019 and many of them interest\n> > me. Also, looking around git-dev materials on the web, I got to the\n> > GSoC 2012 ideas page. And this one got my attention:\n> > https://github.com/peff/git/wiki/SoC-2012-Ideas#improving-parallelism-in-various-commands\n> >\n> > I'm interested in parallel computing and that has been my research\n> > topic for about an year now. So I would like to ask what's the status\n> > of this GSoC idea. I've read git-grep and saw that it is already\n> > parallel, but I was wondering if there is any other section in git in\n> > which it was already considered to bring parallelism, seeking to\n> > achieve greater performance. And also, if this could, perhaps, be a\n> > GSoC project.\n>\n> I vaguely remember that we thought at one point that all the low\n> hanging fruits had already been taken in this area but I might be\n> wrong.\n\nWe still have to remove some global variables, which is quite easy to\ndo, before one could actually add mutexes and stuff to allow multiple\npack access. I don't know though if the removing global variables is\nthat exciting for GSoC, or if both tasks could fit in one GSoC. The\nadding parallel access is not that hard, I think, once you know\npackfile.c and sha1-file.c relatively well. It's mostly dealing with\ncaches and all the sliding access windows safely.\n-- \nDuy\n"},{"id":"370421","messageId":"nycvar.QRO.7.76.6.1903011611260.41@tvgsbejvaqbjf.bet","threadId":"50618","inReplyTo":"CAP8UFD0jF5k31tBhj=bQMGOJKN8-F-Rx7RXF1SHZ22LEgSo9_Q@mail.gmail.com","subject":"Re: Questions on GSoC 2019 Ideas","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2019-03-01T15:20:16Z","receivedAt":"2019-03-01T15:20:38Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Chris,\n\nOn Thu, 28 Feb 2019, Christian Couder wrote:\n\n> On Thu, Feb 28, 2019 at 10:46 PM Matheus Tavares Bernardino\n> wrote:\n> >\n> > I'm also interested in the 'convert script to builtin' task, and I was\n> > wondering if 'git-bisect' would be a good candidate for that.\n> \n> There is an ongoing work on that by Tanushree Tumane, an Outreachy\n> intern. The end of the internship is March 5, but it seems to me that\n> there is not a lot of work left on the project, and hopefully\n> Tanushree or her mentors will take care of that.\n\nBy \"or their mentors\" you are referring to yourself and to myself.\n\nAnd indeed, there won'y be much to be done to convert the script to a full\nbuilt-in. But there were a couple of things that Tanushree also had on\ntheir radar: Fix how git bisect handle many merge bases.\n\nI think that could still be a Google Summer of Code project.\n\nCiao,\nJohannes\n\n> \n> Best,\n> Christian.\n> \n> > Thanks,\n> > Matheus Tavares\n> >\n> > [1]: https://public-inbox.org/git/20190226051804.10631-1-matheus.bernardino@usp.br/\n> \n"},{"id":"370468","messageId":"20190302150900.GU6085@hank.intra.tgummerer.com","threadId":"50618","inReplyTo":"CACsJy8AL7DMbV7hhNeb1beucxQnZBHfgv4xo9dK5T+WCK7Q6yw@mail.gmail.com","subject":"Re: Questions on GSoC 2019 Ideas","fromName":"Thomas Gummerer","fromEmail":"t.gummerer@gmail.com","sentAt":"2019-03-02T15:09:00Z","receivedAt":"2019-03-02T15:09:05Z","isPatch":false,"sender":{"key":"t.gummerer@gmail.com","avatar":"https://avatars.githubusercontent.com/u/191004?v=4"},"body":"On 03/01, Duy Nguyen wrote:\n> On Fri, Mar 1, 2019 at 5:20 AM Christian Couder\n> wrote:\n> >\n> > Hi Matheus,\n> >\n> > On Thu, Feb 28, 2019 at 10:46 PM Matheus Tavares Bernardino\n> > wrote:\n> > >\n> > > I've been in the mailing list for a couple weeks now, mainly working\n> > > on my gsoc micro-project[1] and in other patches that derived from it.\n> > > I also have been contributing to the Linux Kernel for half an year,\n> > > but am now mainly just supporting other students here at USP.\n> > >\n> > > I have read the ideas page for the GSoC 2019 and many of them interest\n> > > me. Also, looking around git-dev materials on the web, I got to the\n> > > GSoC 2012 ideas page. And this one got my attention:\n> > > https://github.com/peff/git/wiki/SoC-2012-Ideas#improving-parallelism-in-various-commands\n> > >\n> > > I'm interested in parallel computing and that has been my research\n> > > topic for about an year now. So I would like to ask what's the status\n> > > of this GSoC idea. I've read git-grep and saw that it is already\n> > > parallel, but I was wondering if there is any other section in git in\n> > > which it was already considered to bring parallelism, seeking to\n> > > achieve greater performance. And also, if this could, perhaps, be a\n> > > GSoC project.\n> >\n> > I vaguely remember that we thought at one point that all the low\n> > hanging fruits had already been taken in this area but I might be\n> > wrong.\n> \n> We still have to remove some global variables, which is quite easy to\n> do, before one could actually add mutexes and stuff to allow multiple\n> pack access. I don't know though if the removing global variables is\n> that exciting for GSoC, or if both tasks could fit in one GSoC. The\n> adding parallel access is not that hard, I think, once you know\n> packfile.c and sha1-file.c relatively well. It's mostly dealing with\n> caches and all the sliding access windows safely.\n\nI'm not very familiar with what's required here, but reading the above\nmakes me think it's likely too much for a GSoC project. I think I'd\nbe happy with a project that declares removing the global variables as\nthe main goal, and adding parallelism as a potential bonus.\n\nI'm a bit wary of a too large proposal here, as we've historically\noverestimated what kind of project is achievable over a summer (I've\nbeen there myself, as my GSoC project was also more than I was able to\ndo in a summer :)). I'd rather have a project whose goal is rather\nsmall and can be expanded later, than having something that could\npotentially take more than 3 months, where the student (or their\nmentors) have to finish it after GSoC.\n\n> -- \n> Duy\n"},{"id":"370500","messageId":"CAP8UFD31YKt7fm+shWdBxsL4fCSO4dU=97YwFsZ9gZBpEWmRPQ@mail.gmail.com","threadId":"50618","inReplyTo":"20190302150900.GU6085@hank.intra.tgummerer.com","subject":"Re: Questions on GSoC 2019 Ideas","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2019-03-03T07:18:45Z","receivedAt":"2019-03-03T07:19:01Z","isPatch":false,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"On Sat, Mar 2, 2019 at 4:09 PM Thomas Gummerer wrote:\n>\n> On 03/01, Duy Nguyen wrote:\n> > On Fri, Mar 1, 2019 at 5:20 AM Christian Couder\n> > wrote:\n> > >\n> > > Hi Matheus,\n> > >\n> > > On Thu, Feb 28, 2019 at 10:46 PM Matheus Tavares Bernardino\n> > > wrote:\n> > > >\n> > > > I've been in the mailing list for a couple weeks now, mainly working\n> > > > on my gsoc micro-project[1] and in other patches that derived from it.\n> > > > I also have been contributing to the Linux Kernel for half an year,\n> > > > but am now mainly just supporting other students here at USP.\n> > > >\n> > > > I have read the ideas page for the GSoC 2019 and many of them interest\n> > > > me. Also, looking around git-dev materials on the web, I got to the\n> > > > GSoC 2012 ideas page. And this one got my attention:\n> > > > https://github.com/peff/git/wiki/SoC-2012-Ideas#improving-parallelism-in-various-commands\n> > > >\n> > > > I'm interested in parallel computing and that has been my research\n> > > > topic for about an year now. So I would like to ask what's the status\n> > > > of this GSoC idea. I've read git-grep and saw that it is already\n> > > > parallel, but I was wondering if there is any other section in git in\n> > > > which it was already considered to bring parallelism, seeking to\n> > > > achieve greater performance. And also, if this could, perhaps, be a\n> > > > GSoC project.\n> > >\n> > > I vaguely remember that we thought at one point that all the low\n> > > hanging fruits had already been taken in this area but I might be\n> > > wrong.\n> >\n> > We still have to remove some global variables, which is quite easy to\n> > do, before one could actually add mutexes and stuff to allow multiple\n> > pack access. I don't know though if the removing global variables is\n> > that exciting for GSoC, or if both tasks could fit in one GSoC. The\n> > adding parallel access is not that hard, I think, once you know\n> > packfile.c and sha1-file.c relatively well. It's mostly dealing with\n> > caches and all the sliding access windows safely.\n>\n> I'm not very familiar with what's required here, but reading the above\n> makes me think it's likely too much for a GSoC project. I think I'd\n> be happy with a project that declares removing the global variables as\n> the main goal, and adding parallelism as a potential bonus.\n\nYeah, I think that the main issue, now that Duy found something that\ncould be a GSoC project, is that the potential mentors are not\nfamiliar with the pack access code. It means that Matheus would\nprobably not get a lot of help from his mentors when he would work on\nadding parallelism.\n\nThat may not be too big a problem though if Matheus is ok to ask many\ntechnical questions on the mailing list. It seems to me that he could\nsucceed.\n\n> I'm a bit wary of a too large proposal here, as we've historically\n> overestimated what kind of project is achievable over a summer (I've\n> been there myself, as my GSoC project was also more than I was able to\n> do in a summer :)). I'd rather have a project whose goal is rather\n> small and can be expanded later, than having something that could\n> potentially take more than 3 months, where the student (or their\n> mentors) have to finish it after GSoC.\n\nYeah, I agree with your suggestion about a project that declares\nremoving the global variables as the main goal, and adding parallelism\nas a potential bonus.\n\nOne thing I am still worried about is if we are sure that adding\nparallelism is likely to get us a significant performance improvement\nor not. If the performance of this code is bounded by disk or memory\naccess, then adding parallelism might not bring any benefit. (It could\nperhaps decrease performance if memory locality gets worse.) So I'd\nlike some confirmation either by running some tests or by experienced\nGit developers that it is likely to be a win.\n"},{"id":"370505","messageId":"CACsJy8COJg4jGRKFwyi5Fc374To8Z3g3wHx+SD7zQTL5m-TbCg@mail.gmail.com","threadId":"50618","inReplyTo":"20190302150900.GU6085@hank.intra.tgummerer.com","subject":"Re: Questions on GSoC 2019 Ideas","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2019-03-03T10:03:31Z","receivedAt":"2019-03-03T10:04:01Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Sat, Mar 2, 2019 at 10:09 PM Thomas Gummerer wrote:\n>\n> On 03/01, Duy Nguyen wrote:\n> > On Fri, Mar 1, 2019 at 5:20 AM Christian Couder\n> > wrote:\n> > >\n> > > Hi Matheus,\n> > >\n> > > On Thu, Feb 28, 2019 at 10:46 PM Matheus Tavares Bernardino\n> > > wrote:\n> > > >\n> > > > I've been in the mailing list for a couple weeks now, mainly working\n> > > > on my gsoc micro-project[1] and in other patches that derived from it.\n> > > > I also have been contributing to the Linux Kernel for half an year,\n> > > > but am now mainly just supporting other students here at USP.\n> > > >\n> > > > I have read the ideas page for the GSoC 2019 and many of them interest\n> > > > me. Also, looking around git-dev materials on the web, I got to the\n> > > > GSoC 2012 ideas page. And this one got my attention:\n> > > > https://github.com/peff/git/wiki/SoC-2012-Ideas#improving-parallelism-in-various-commands\n> > > >\n> > > > I'm interested in parallel computing and that has been my research\n> > > > topic for about an year now. So I would like to ask what's the status\n> > > > of this GSoC idea. I've read git-grep and saw that it is already\n> > > > parallel, but I was wondering if there is any other section in git in\n> > > > which it was already considered to bring parallelism, seeking to\n> > > > achieve greater performance. And also, if this could, perhaps, be a\n> > > > GSoC project.\n> > >\n> > > I vaguely remember that we thought at one point that all the low\n> > > hanging fruits had already been taken in this area but I might be\n> > > wrong.\n> >\n> > We still have to remove some global variables, which is quite easy to\n> > do, before one could actually add mutexes and stuff to allow multiple\n> > pack access. I don't know though if the removing global variables is\n> > that exciting for GSoC, or if both tasks could fit in one GSoC. The\n> > adding parallel access is not that hard, I think, once you know\n> > packfile.c and sha1-file.c relatively well. It's mostly dealing with\n> > caches and all the sliding access windows safely.\n>\n> I'm not very familiar with what's required here, but reading the above\n> makes me think it's likely too much for a GSoC project. I think I'd\n> be happy with a project that declares removing the global variables as\n> the main goal, and adding parallelism as a potential bonus.\n>\n> I'm a bit wary of a too large proposal here, as we've historically\n> overestimated what kind of project is achievable over a summer (I've\n> been there myself, as my GSoC project was also more than I was able to\n> do in a summer :)). I'd rather have a project whose goal is rather\n> small and can be expanded later, than having something that could\n> potentially take more than 3 months, where the student (or their\n> mentors) have to finish it after GSoC.\n\nThis is why I'm not involved in GSoC. I often mis-estimate the size of\nwork (and yes I would still like your tree-based index format in,\ncan't remember why it never made it).\n\nSo yeah if you find removing global variables (which essentially\nidentifies shared states, a prerequisite for any parallel work)\nreasonable for GSoC, I'd say go for it.\n\nBe also aware that this kind of refactoring work could result in lots\nof patches and it takes time to get them merged, if your GSoC goal is\nto get merged.\n-- \nDuy\n"},{"id":"370506","messageId":"CACsJy8ATKdcDdbTzCdZFhChKEAWhjuYQJBpGXZ9HAVXK1r2pFw@mail.gmail.com","threadId":"50618","inReplyTo":"CAP8UFD31YKt7fm+shWdBxsL4fCSO4dU=97YwFsZ9gZBpEWmRPQ@mail.gmail.com","subject":"Re: Questions on GSoC 2019 Ideas","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2019-03-03T10:12:59Z","receivedAt":"2019-03-03T10:13:28Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Sun, Mar 3, 2019 at 2:18 PM Christian Couder\n wrote:\n> One thing I am still worried about is if we are sure that adding\n> parallelism is likely to get us a significant performance improvement\n> or not. If the performance of this code is bounded by disk or memory\n> access, then adding parallelism might not bring any benefit. (It could\n> perhaps decrease performance if memory locality gets worse.) So I'd\n> like some confirmation either by running some tests or by experienced\n> Git developers that it is likely to be a win.\n\nThis is a good point. My guess is the pack access consists of two\nparts: deflate zlib, resolve delta objects (which is just another form\nof compression) and actual I/O. The former is CPU bound and may take\nadvantage of multiple cores. However, the cache we have kinda helps\nreduce CPU work load already, so perhaps the actual gain is not that\nmuch (or maybe we could just improve this cache to be more efficient).\nI'm adding Jeff, maybe he has done some experiments on parallel pack\naccess, who knows.\n\nThe second good thing from parallel pack access is not about utilizing\nprocessing power from multiple cores, but about _not_ blocking. I\nthink one example use case here is parallel checkout. While one thread\nis blocked by pack access code for whatever reason, the others can\nstill continue doing other stuff (e.g. write the checked out file to\ndisk) or even access the pack again to check more things out.\n-- \nDuy\n"},{"id":"370507","messageId":"CACsJy8A2e3e9JAAN8==PHxjO-5xki2NWLPb6vrFvCr8NLKmHyA@mail.gmail.com","threadId":"50618","inReplyTo":"CACsJy8ATKdcDdbTzCdZFhChKEAWhjuYQJBpGXZ9HAVXK1r2pFw@mail.gmail.com","subject":"Re: Questions on GSoC 2019 Ideas","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2019-03-03T10:17:02Z","receivedAt":"2019-03-03T10:17:31Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Sun, Mar 3, 2019 at 5:12 PM Duy Nguyen wrote:\n> This is a good point. My guess is the pack access consists of two\n> parts: deflate zlib, resolve delta objects (which is just another form\n\ns/deflate/inflate/ (i keep making this mistake)\n-- \nDuy\n"},{"id":"370531","messageId":"20190303161253.GW6085@hank.intra.tgummerer.com","threadId":"50618","inReplyTo":"CACsJy8COJg4jGRKFwyi5Fc374To8Z3g3wHx+SD7zQTL5m-TbCg@mail.gmail.com","subject":"Re: Questions on GSoC 2019 Ideas","fromName":"Thomas Gummerer","fromEmail":"t.gummerer@gmail.com","sentAt":"2019-03-03T16:12:53Z","receivedAt":"2019-03-03T16:12:58Z","isPatch":false,"sender":{"key":"t.gummerer@gmail.com","avatar":"https://avatars.githubusercontent.com/u/191004?v=4"},"body":"On 03/03, Duy Nguyen wrote:\n> On Sat, Mar 2, 2019 at 10:09 PM Thomas Gummerer wrote:\n> > I'm not very familiar with what's required here, but reading the above\n> > makes me think it's likely too much for a GSoC project. I think I'd\n> > be happy with a project that declares removing the global variables as\n> > the main goal, and adding parallelism as a potential bonus.\n> >\n> > I'm a bit wary of a too large proposal here, as we've historically\n> > overestimated what kind of project is achievable over a summer (I've\n> > been there myself, as my GSoC project was also more than I was able to\n> > do in a summer :)). I'd rather have a project whose goal is rather\n> > small and can be expanded later, than having something that could\n> > potentially take more than 3 months, where the student (or their\n> > mentors) have to finish it after GSoC.\n> \n> This is why I'm not involved in GSoC. I often mis-estimate the size of\n> work (and yes I would still like your tree-based index format in,\n> can't remember why it never made it).\n\nSo do I, and that's why I'd like to err on the side of having smaller\nprojects :)\n\nI think the main reason the tree-based index format never made it is\nthat the in-core APIs were not set up to make use of the new index\nformat. I'm also still interested in getting it in, but I haven't\nfound the time for looking at making the index code pluggable yet. It\nwould probably take a similar refactoring as with the refs code to get\nthis done.\n\nAll that said, GSoC was still a great experience for me, and I got to\nlearn a ton over the summer. But I did feel like I let the people\nthat invested a lot of time in the project as well down a bit, by not\nbeing able to finishing the project. And having the feeling of\naccomplishment of actually finishing a project would definitely have\nbeen nice to have as well. So for those reasons I think it would be\nbetter for students to take on smaller projects.\n\n> So yeah if you find removing global variables (which essentially\n> identifies shared states, a prerequisite for any parallel work)\n> reasonable for GSoC, I'd say go for it.\n> \n> Be also aware that this kind of refactoring work could result in lots\n> of patches and it takes time to get them merged, if your GSoC goal is\n> to get merged.\n> -- \n> Duy\n"},{"id":"370664","messageId":"20190305045140.GH19800@sigill.intra.peff.net","threadId":"50618","inReplyTo":"CACsJy8ATKdcDdbTzCdZFhChKEAWhjuYQJBpGXZ9HAVXK1r2pFw@mail.gmail.com","subject":"Re: Questions on GSoC 2019 Ideas","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-03-05T04:51:40Z","receivedAt":"2019-03-05T04:51:44Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Mar 03, 2019 at 05:12:59PM +0700, Duy Nguyen wrote:\n\n> On Sun, Mar 3, 2019 at 2:18 PM Christian Couder\n> wrote:\n> > One thing I am still worried about is if we are sure that adding\n> > parallelism is likely to get us a significant performance improvement\n> > or not. If the performance of this code is bounded by disk or memory\n> > access, then adding parallelism might not bring any benefit. (It could\n> > perhaps decrease performance if memory locality gets worse.) So I'd\n> > like some confirmation either by running some tests or by experienced\n> > Git developers that it is likely to be a win.\n> \n> This is a good point. My guess is the pack access consists of two\n> parts: deflate zlib, resolve delta objects (which is just another form\n> of compression) and actual I/O. The former is CPU bound and may take\n> advantage of multiple cores. However, the cache we have kinda helps\n> reduce CPU work load already, so perhaps the actual gain is not that\n> much (or maybe we could just improve this cache to be more efficient).\n> I'm adding Jeff, maybe he has done some experiments on parallel pack\n> access, who knows.\n\nSorry, I don't have anything intelligent to add here. I do know that\n`index-pack` doesn't scale well with more cores. I don't think I've ever\nlooked at adding parallel access to the packs themselves. I suspect it\nwould be tricky due to a few global variables (the pack windows, the\ndelta cache, etc).\n\n> The second good thing from parallel pack access is not about utilizing\n> processing power from multiple cores, but about _not_ blocking. I\n> think one example use case here is parallel checkout. While one thread\n> is blocked by pack access code for whatever reason, the others can\n> still continue doing other stuff (e.g. write the checked out file to\n> disk) or even access the pack again to check more things out.\n\nI'm not sure if it would help much for packs, because they're organized\nto have pretty good cold-cache read-ahead behavior. But who knows until\nwe measure it.\n\nI do suspect that inflating (and delta reconstruction) done in parallel\ncould be a win for git-grep, especially if you have a really simple\nregex that is quick to search.\n\n-Peff\n"},{"id":"370706","messageId":"CACsJy8D-eQUGFsu4_cB9FE6gAo2d68EF_x2ze3YLXKAxYJfhSQ@mail.gmail.com","threadId":"50618","inReplyTo":"20190305045140.GH19800@sigill.intra.peff.net","subject":"Re: Questions on GSoC 2019 Ideas","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2019-03-05T12:57:18Z","receivedAt":"2019-03-05T12:57:47Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Tue, Mar 5, 2019 at 11:51 AM Jeff King wrote:\n> > processing power from multiple cores, but about _not_ blocking. I\n> > think one example use case here is parallel checkout. While one thread\n> > is blocked by pack access code for whatever reason, the others can\n> > still continue doing other stuff (e.g. write the checked out file to\n> > disk) or even access the pack again to check more things out.\n>\n> I'm not sure if it would help much for packs, because they're organized\n> to have pretty good cold-cache read-ahead behavior. But who knows until\n> we measure it.\n>\n> I do suspect that inflating (and delta reconstruction) done in parallel\n> could be a win for git-grep, especially if you have a really simple\n> regex that is quick to search.\n\nMaybe git-blame too. But this is based purely on me watching CPU\nutilization of one command with hot cache. For git-blame though, diff\ncode as to be thread safe too but that's another story.\n-- \nDuy\n"},{"id":"370760","messageId":"CAHd-oW6rVptPnHn-aoeMTkp0p-TmoQ7fniftpQm9rw+tjukZ_w@mail.gmail.com","threadId":"50618","inReplyTo":"CAP8UFD31YKt7fm+shWdBxsL4fCSO4dU=97YwFsZ9gZBpEWmRPQ@mail.gmail.com","subject":"Re: Questions on GSoC 2019 Ideas","fromName":"Matheus Tavares Bernardino","fromEmail":"matheus.bernardino@usp.br","sentAt":"2019-03-05T23:03:26Z","receivedAt":"2019-03-05T23:03:40Z","isPatch":false,"sender":{"key":"matheus.tavb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/12701583?v=4"},"body":"First of all, I must apologize for not replying during these last\ndays. I'm traveling and I rarely get a connection here. But I'll be\nback March 11th.\n\nOn Sun, Mar 3, 2019 at 4:18 AM Christian Couder\n wrote:\n>\n> On Sat, Mar 2, 2019 at 4:09 PM Thomas Gummerer wrote:\n> >\n> > I'm a bit wary of a too large proposal here, as we've historically\n> > overestimated what kind of project is achievable over a summer (I've\n> > been there myself, as my GSoC project was also more than I was able to\n> > do in a summer :)). I'd rather have a project whose goal is rather\n> > small and can be expanded later, than having something that could\n> > potentially take more than 3 months, where the student (or their\n> > mentors) have to finish it after GSoC.\n>\n\nI totally understand the concern.\n\n> Yeah, I agree with your suggestion about a project that declares\n> removing the global variables as the main goal, and adding parallelism\n> as a potential bonus.\n>\n\nTalking about a delimited scope for GSoC and a potential bonus after,\na potential idea comes to my mind: I'm still trying to define the\nsubject for my undergraduate thesis (which must be in HPC and/or\nparallelism on CPU/GPU). And the idea of bringing more parallelism to\ngit seems to be too big for a GSoC project. So, perhaps, if we manage\nto identify wether parallelism would indeed bring a good performance\ngain to git, I could propose that to my advisor professor as my\nundergraduate thesis and I could work on that during this whole year.\nIt is still an idea to be matured, but do you think it would be\nfeasible?\n"},{"id":"370770","messageId":"CAHd-oW4LsyZOgHYgKaACX8AtzbA8pBpFUPWSF3GF6XxA_HKfjA@mail.gmail.com","threadId":"50618","inReplyTo":"CACsJy8D-eQUGFsu4_cB9FE6gAo2d68EF_x2ze3YLXKAxYJfhSQ@mail.gmail.com","subject":"Re: Questions on GSoC 2019 Ideas","fromName":"Matheus Tavares Bernardino","fromEmail":"matheus.bernardino@usp.br","sentAt":"2019-03-05T23:46:50Z","receivedAt":"2019-03-05T23:47:03Z","isPatch":false,"sender":{"key":"matheus.tavb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/12701583?v=4"},"body":"This exercise of estimating a good spot to gain performance with\nparallelism at git seems more difficult than I thought, firstly. Also,\nI'm not that familiar yet with git packing (neither with the sections\nof it that could benefit from parallelism). So could anyone point me\nsome good references on this, where I could study and maybe come back\nwith more valuable suggestions?\n\nOn Tue, Mar 5, 2019 at 9:57 AM Duy Nguyen wrote:\n>\n> On Tue, Mar 5, 2019 at 11:51 AM Jeff King wrote:\n> > > processing power from multiple cores, but about _not_ blocking. I\n> > > think one example use case here is parallel checkout. While one thread\n> > > is blocked by pack access code for whatever reason, the others can\n> > > still continue doing other stuff (e.g. write the checked out file to\n> > > disk) or even access the pack again to check more things out.\n> >\n\nHmm, you mean distributing the process of inflating, reconstructing\ndeltas and checking out files between the threads? (having each one\ndoing the process for a different file?)\n\n> > I'm not sure if it would help much for packs, because they're organized\n> > to have pretty good cold-cache read-ahead behavior. But who knows until\n> > we measure it.\n> >\n> > I do suspect that inflating (and delta reconstruction) done in parallel\n> > could be a win for git-grep, especially if you have a really simple\n> > regex that is quick to search.\n>\n> Maybe git-blame too. But this is based purely on me watching CPU\n> utilization of one command with hot cache. For git-blame though, diff\n> code as to be thread safe too but that's another story.\n\nI don't know if this relates to parallelizing pack access, but I\nthought that sharing this with you all could perhaps bring some new\ninsights (maybe even on parallelizing some other git section): I asked\nmy friends who contribute to the Linux Kernel what git commands seems\nto take longer during their kernel work, and the answers were:\n- git log and git status, sometimes\n- using pager's search at git log\n- checking out to an old commit\n- git log --oneline --decorate --graph\n"},{"id":"370800","messageId":"CACsJy8Bit46VatYZNB-ZsMBL043_GYDLqZ3fAZ8HzXZ9Kv1Z0g@mail.gmail.com","threadId":"50618","inReplyTo":"CAHd-oW4LsyZOgHYgKaACX8AtzbA8pBpFUPWSF3GF6XxA_HKfjA@mail.gmail.com","subject":"Re: Questions on GSoC 2019 Ideas","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2019-03-06T10:17:17Z","receivedAt":"2019-03-06T10:17:46Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Wed, Mar 6, 2019 at 6:47 AM Matheus Tavares Bernardino\n wrote:\n>\n> This exercise of estimating a good spot to gain performance with\n> parallelism at git seems more difficult than I thought, firstly. Also,\n> I'm not that familiar yet with git packing (neither with the sections\n> of it that could benefit from parallelism). So could anyone point me\n> some good references on this, where I could study and maybe come back\n> with more valuable suggestions?\n\nI think you should skim through\nDocumentation/technical/pack-format.txt to have an idea what we're\ntalking about here (inflation, delta cache...).\n\nThe short (and slightly inaccurate) version is, in order to give the\ncontent of a SHA-1, we need to\n\n1. locate that \"object\" in the pack file (I'm ignoring loose objects)\n\n2. assume (worst case) that this object is a delta object, it contains\nonly modification of another object, so you would need to get the\ncontent of the other object first, then apply these modification (\"the\ndelta\") to get the content. This could repeat many times\n\n3. once you get full content, it's actually zlib compressed, so you\nneed to uncompress/inflate it.\n\nStep 2 would be super slow if you have to uncompress that \"another\nobject\" every single time. So there's a \"delta cache\" which stores the\ncontent of these \"other objects\". Next time you see a delta object on\ntop of one of these in the cache, you can just apply the delta and be\ndone with it. Much faster. This delta cache is of course global and\nnot thread safe.\n\nStep 3 can also be slow when dealing with large blobs.\n\nAnother global state that Jeff mentions is pack windows I think is a\nbit harder to explain quickly. But basically we have many \"windows\" to\nsee the raw content of a pack file, these windows are global (per pack\nactually) and are also not thread safe.\n\nSo all these steps are not thread safe. When a command with multiple\nthread support accesses the pack, all those steps are protected by a\nsingle mutex (it's grep_mutex in builtin/grep.c or read_lock() in\nbuiltin/pack-objects.c). As you can see steps here are CPU-bound (step\n3 is obvious, step 2 will have to inflate the other objects), so if\nyou use a more fine-grained mutex, chances are the inflation step can\nbe done in parallel.\n\nI think the good spots to gain performance are the commands that\nalready have multiple thread support. I mentioned git-grep and\ngit-pack-objects.c above. git-index-pack is the third one but it's\nspecial and I think does not use general pack access code.\n\nI think if we could somehow measure lock contention of those big locks\nabove we can guesstimate how much gain there is. If threads in\ngit-grep for example often have to wait for grep_mutex, then in the\nbest case scenario when you make pack access thread safe, lock\ncontention goes down to near zero.\n\n> On Tue, Mar 5, 2019 at 9:57 AM Duy Nguyen wrote:\n> >\n> > On Tue, Mar 5, 2019 at 11:51 AM Jeff King wrote:\n> > > > processing power from multiple cores, but about _not_ blocking. I\n> > > > think one example use case here is parallel checkout. While one thread\n> > > > is blocked by pack access code for whatever reason, the others can\n> > > > still continue doing other stuff (e.g. write the checked out file to\n> > > > disk) or even access the pack again to check more things out.\n> > >\n>\n> Hmm, you mean distributing the process of inflating, reconstructing\n> deltas and checking out files between the threads? (having each one\n> doing the process for a different file?)\n\nYes. So if one thread hits a giant file (and spends lot of time\ninflating), the other threads can still go on inflate smaller files\nand writing them to disk.\n\n> > > I'm not sure if it would help much for packs, because they're organized\n> > > to have pretty good cold-cache read-ahead behavior. But who knows until\n> > > we measure it.\n> > >\n> > > I do suspect that inflating (and delta reconstruction) done in parallel\n> > > could be a win for git-grep, especially if you have a really simple\n> > > regex that is quick to search.\n> >\n> > Maybe git-blame too. But this is based purely on me watching CPU\n> > utilization of one command with hot cache. For git-blame though, diff\n> > code as to be thread safe too but that's another story.\n>\n> I don't know if this relates to parallelizing pack access, but I\n> thought that sharing this with you all could perhaps bring some new\n> insights (maybe even on parallelizing some other git section): I asked\n> my friends who contribute to the Linux Kernel what git commands seems\n> to take longer during their kernel work, and the answers were:\n> - git log and git status, sometimes\n> - using pager's search at git log\n> - checking out to an old commit\n> - git log --oneline --decorate --graph\n\nSometimes the slowness is not because of serialized pack access. I'm\nsure git-status is not that much impacted by slow pack access.\n\nThe pager search case may be sped up (git-log has to look at lots of\nblobs and trees) but you also need to parallelize diff code as well\nand that I think is way too big to consider.\n\nThe checking out old commit, I think could also be sped up with\nparallel checkout. Again this is really out of scope. But of course it\ncan't be done until pack access is thread safe. Or can be done but not\nas pretty [1]. [1] suggests 30% speedup. That's the share-nothing best\npossible case, I think. But that code is no way optimized so real\nspeedup could be higher.\n\n[1] https://public-inbox.org/git/20160415095139.GA3985@lanh/\n-- \nDuy\n"},{"id":"370836","messageId":"20190306231722.GA6085@hank.intra.tgummerer.com","threadId":"50618","inReplyTo":"CAHd-oW6rVptPnHn-aoeMTkp0p-TmoQ7fniftpQm9rw+tjukZ_w@mail.gmail.com","subject":"Re: Questions on GSoC 2019 Ideas","fromName":"Thomas Gummerer","fromEmail":"t.gummerer@gmail.com","sentAt":"2019-03-06T23:17:22Z","receivedAt":"2019-03-06T23:17:29Z","isPatch":false,"sender":{"key":"t.gummerer@gmail.com","avatar":"https://avatars.githubusercontent.com/u/191004?v=4"},"body":"On 03/05, Matheus Tavares Bernardino wrote:\n> First of all, I must apologize for not replying during these last\n> days. I'm traveling and I rarely get a connection here. But I'll be\n> back March 11th.\n> \n> On Sun, Mar 3, 2019 at 4:18 AM Christian Couder\n> wrote:\n> >\n> > On Sat, Mar 2, 2019 at 4:09 PM Thomas Gummerer wrote:\n> > >\n> > > I'm a bit wary of a too large proposal here, as we've historically\n> > > overestimated what kind of project is achievable over a summer (I've\n> > > been there myself, as my GSoC project was also more than I was able to\n> > > do in a summer :)). I'd rather have a project whose goal is rather\n> > > small and can be expanded later, than having something that could\n> > > potentially take more than 3 months, where the student (or their\n> > > mentors) have to finish it after GSoC.\n> >\n> \n> I totally understand the concern.\n> \n> > Yeah, I agree with your suggestion about a project that declares\n> > removing the global variables as the main goal, and adding parallelism\n> > as a potential bonus.\n> >\n> \n> Talking about a delimited scope for GSoC and a potential bonus after,\n> a potential idea comes to my mind: I'm still trying to define the\n> subject for my undergraduate thesis (which must be in HPC and/or\n> parallelism on CPU/GPU). And the idea of bringing more parallelism to\n> git seems to be too big for a GSoC project. So, perhaps, if we manage\n> to identify wether parallelism would indeed bring a good performance\n> gain to git, I could propose that to my advisor professor as my\n> undergraduate thesis and I could work on that during this whole year.\n> It is still an idea to be matured, but do you think it would be\n> feasible?\n\nI think this idea is generally fine, but your project proposal should\nonly be about the parts that are going to be included in your GSoC\nproject. Of course we love to see GSoC students that are still\nactively participating in the project after GSoC. However that should\nnot be part of the sponsored program. Mentors may also be less\navailable outside of the program, as mentoring can take quite some\ntime commitment.\n\nAnother slight concern here is that the mentors may be less familiar\nwith this project than others (I for one am not very familiar, and\nChristian mentioned similar concerns), so it may be harder to give you\ngood advice.\n\nAll that said, if you are still excited about this project, think\nabout how to address these concerns in your proposal. And feel free\nto discuss the proposal on the mailing list as well, before actually\nsubmitting it.\n"},{"id":"371207","messageId":"CAHd-oW4e6CtcaKXbowqZM-pDAEGJxupHwBvFk2veaaYswt0hmQ@mail.gmail.com","threadId":"50618","inReplyTo":"CACsJy8Bit46VatYZNB-ZsMBL043_GYDLqZ3fAZ8HzXZ9Kv1Z0g@mail.gmail.com","subject":"Re: Questions on GSoC 2019 Ideas","fromName":"Matheus Tavares Bernardino","fromEmail":"matheus.bernardino@usp.br","sentAt":"2019-03-12T00:18:47Z","receivedAt":"2019-03-12T00:19:02Z","isPatch":false,"sender":{"key":"matheus.tavb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/12701583?v=4"},"body":"On Wed, Mar 6, 2019 at 7:17 AM Duy Nguyen wrote:\n>\n> On Wed, Mar 6, 2019 at 6:47 AM Matheus Tavares Bernardino\n> wrote:\n> >\n> > This exercise of estimating a good spot to gain performance with\n> > parallelism at git seems more difficult than I thought, firstly. Also,\n> > I'm not that familiar yet with git packing (neither with the sections\n> > of it that could benefit from parallelism). So could anyone point me\n> > some good references on this, where I could study and maybe come back\n> > with more valuable suggestions?\n>\n> I think you should skim through\n> Documentation/technical/pack-format.txt to have an idea what we're\n> talking about here (inflation, delta cache...).\n\nThanks for the recommendation. It was a very explanatory reading.\n\n> The short (and slightly inaccurate) version is, in order to give the\n> content of a SHA-1, we need to\n>\n> 1. locate that \"object\" in the pack file (I'm ignoring loose objects)\n>\n> 2. assume (worst case) that this object is a delta object, it contains\n> only modification of another object, so you would need to get the\n> content of the other object first, then apply these modification (\"the\n> delta\") to get the content. This could repeat many times\n>\n> 3. once you get full content, it's actually zlib compressed, so you\n> need to uncompress/inflate it.\n>\n> Step 2 would be super slow if you have to uncompress that \"another\n> object\" every single time. So there's a \"delta cache\" which stores the\n> content of these \"other objects\". Next time you see a delta object on\n> top of one of these in the cache, you can just apply the delta and be\n> done with it. Much faster. This delta cache is of course global and\n> not thread safe.\n>\n> Step 3 can also be slow when dealing with large blobs.\n\nThanks for the explanation.\n\n> Another global state that Jeff mentions is pack windows I think is a\n> bit harder to explain quickly. But basically we have many \"windows\" to\n> see the raw content of a pack file, these windows are global (per pack\n> actually) and are also not thread safe.\n>\n> So all these steps are not thread safe. When a command with multiple\n> thread support accesses the pack, all those steps are protected by a\n> single mutex (it's grep_mutex in builtin/grep.c or read_lock() in\n> builtin/pack-objects.c). As you can see steps here are CPU-bound (step\n> 3 is obvious, step 2 will have to inflate the other objects), so if\n> you use a more fine-grained mutex, chances are the inflation step can\n> be done in parallel.\n>\n> I think the good spots to gain performance are the commands that\n> already have multiple thread support. I mentioned git-grep and\n> git-pack-objects.c above. git-index-pack is the third one but it's\n> special and I think does not use general pack access code.\n>\n> I think if we could somehow measure lock contention of those big locks\n> above we can guesstimate how much gain there is. If threads in\n> git-grep for example often have to wait for grep_mutex, then in the\n> best case scenario when you make pack access thread safe, lock\n> contention goes down to near zero.\n\nI've been thinking on how I could implement a test to estimate the\nlock contention but had no success until now. I wanted to try\nmutrace[2] but couldn't install it; I tried valgrind's drd but it\ndidn't seem to report a contention time estimation; And I tried\nmeasuring the time of \"pthread_mutex_lock(&grep_mutex)\" but I don't\nknow how much significative this value is, since we can't directly\ncompare it (the time of many threads at lock) with the overall\nexecution time. Do you have an idea on how we could measure the lock\ncontention here?\n\nAnother thing that is occurring to me right now is whether git-grep,\nas it is implemented today, would really benefit from thread-safe pack\naccess. I may have to study the code more, but it seems to me that\njust the producer thread uses pack access.\n\n[2] http://0pointer.de/blog/projects/mutrace.html\n\n> > On Tue, Mar 5, 2019 at 9:57 AM Duy Nguyen wrote:\n> > >\n> > > On Tue, Mar 5, 2019 at 11:51 AM Jeff King wrote:\n> > > > > processing power from multiple cores, but about _not_ blocking. I\n> > > > > think one example use case here is parallel checkout. While one thread\n> > > > > is blocked by pack access code for whatever reason, the others can\n> > > > > still continue doing other stuff (e.g. write the checked out file to\n> > > > > disk) or even access the pack again to check more things out.\n> > > >\n> >\n> > Hmm, you mean distributing the process of inflating, reconstructing\n> > deltas and checking out files between the threads? (having each one\n> > doing the process for a different file?)\n>\n> Yes. So if one thread hits a giant file (and spends lot of time\n> inflating), the other threads can still go on inflate smaller files\n> and writing them to disk.\n>\n> > > > I'm not sure if it would help much for packs, because they're organized\n> > > > to have pretty good cold-cache read-ahead behavior. But who knows until\n> > > > we measure it.\n> > > >\n> > > > I do suspect that inflating (and delta reconstruction) done in parallel\n> > > > could be a win for git-grep, especially if you have a really simple\n> > > > regex that is quick to search.\n> > >\n> > > Maybe git-blame too. But this is based purely on me watching CPU\n> > > utilization of one command with hot cache. For git-blame though, diff\n> > > code as to be thread safe too but that's another story.\n> >\n> > I don't know if this relates to parallelizing pack access, but I\n> > thought that sharing this with you all could perhaps bring some new\n> > insights (maybe even on parallelizing some other git section): I asked\n> > my friends who contribute to the Linux Kernel what git commands seems\n> > to take longer during their kernel work, and the answers were:\n> > - git log and git status, sometimes\n> > - using pager's search at git log\n> > - checking out to an old commit\n> > - git log --oneline --decorate --graph\n>\n> Sometimes the slowness is not because of serialized pack access. I'm\n> sure git-status is not that much impacted by slow pack access.\n>\n> The pager search case may be sped up (git-log has to look at lots of\n> blobs and trees) but you also need to parallelize diff code as well\n> and that I think is way too big to consider.\n>\n> The checking out old commit, I think could also be sped up with\n> parallel checkout. Again this is really out of scope. But of course it\n> can't be done until pack access is thread safe. Or can be done but not\n> as pretty [1]. [1] suggests 30% speedup. That's the share-nothing best\n> possible case, I think. But that code is no way optimized so real\n> speedup could be higher.\n>\n> [1] https://public-inbox.org/git/20160415095139.GA3985@lanh/\n\nSo, although it would be out of scope for GSoC, checkout, diff and log\n(and maybe others) could all benefit from a thread-safe/parallel pack\naccess, right? If so, it is very motivating the impact this project\ncould, in theory, have :)\n\n> --\n> Duy\n"},{"id":"371231","messageId":"20190312100237.GA20471@ash","threadId":"50618","inReplyTo":"CAHd-oW4e6CtcaKXbowqZM-pDAEGJxupHwBvFk2veaaYswt0hmQ@mail.gmail.com","subject":"Re: Questions on GSoC 2019 Ideas","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2019-03-12T10:02:37Z","receivedAt":"2019-03-12T10:02:48Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Mon, Mar 11, 2019 at 09:18:47PM -0300, Matheus Tavares Bernardino wrote:\n> I've been thinking on how I could implement a test to estimate the\n> lock contention but had no success until now. I wanted to try\n> mutrace[2] but couldn't install it; I tried valgrind's drd but it\n> didn't seem to report a contention time estimation; And I tried\n> measuring the time of \"pthread_mutex_lock(&grep_mutex)\" but I don't\n> know how much significative this value is, since we can't directly\n> compare it (the time of many threads at lock) with the overall\n> execution time. Do you have an idea on how we could measure the lock\n> contention here?\n\n(I'm supposed to be doing something else, but this is more fun :D)\n\nYeah lock contention is probably hard to measure. But at least we can\nmeasure how much time is blocked by mutex. Something like this [1]\ngives me\n\n $ time ~/w/git/temp/git grep --threads=8 abc HEAD >/dev/null\n warning: let's have some fun\n block_time = 20ms\n block_count = 10725\n \n real 0m0,379s\n user 0m0,425s\n sys 0m0,073s\n\nFrom this I know \"git grep\" took 379ms and at least 20ms (probably\nincluding measurement overhead) is wasted on pthread_mutex_lock(). It\ndoes not look that significant, I admit.\n\n> Another thing that is occurring to me right now is whether git-grep,\n> as it is implemented today, would really benefit from thread-safe pack\n> access. I may have to study the code more, but it seems to me that\n> just the producer thread uses pack access.\n\nThat producer I think is just handing out assignments to worker\nthreads. The real work is still done by worker threads.\n\nThe entry point to pack access in this code is protected by\ngrep_read_lock(). I believe the multithread one is in this deep call\nchain (I found it out by gdb)\n\n[main thread] grep_oid() -> add_work() ->\n[worker thread] grep_source() -> grep_source_1() ->\ngrep_source_is_binary() -> grep_source_load() ->\ngrep_source_load_oid() -> read_object_file()\n\nNote that there's another source of pack access, the\nlock_and_read_oid_file() in grep_tree(). This is where we unpack tree\nobjects and traverse to get blob SHA-1.\n\nThis code is currently on the main thread (maybe this is what you\nfound?) so it does not really benefit from multi thread. We could\nstill add some sort of lookahead queue to inflate tree objects in\nadvance in parallel, but I don't know how much gain that will be.\n\nOne thing I didn't notice is we currently force no threads in the case\nwe need pack access, e.g. \"git grep \" or \"git grep\n--cached \". So if you need to experiment, you need to hack it\nand remove that restriction. That's the \"let's have some fun\" code in\n[1].\n\nSo, assuming this is CPU bottleneck, let's have a look at how CPU is used.\n\n perf record git grep --threads=1 abc HEAD >/dev/null\n perf report\n\nshows me the top CPU consumers are\n\n 51,16% git libz.so.1.2.11 [.] inflate_fast\n 19,55% git git [.] bmexec\n\nYou need to do some guessing here. But I believe the top call is from\ninflating objects (either from packs or from loose objects). The\nsecond one is from regular expression engine.\n\nSince the regex here is very short (I deliberately try Jeff's case\nwhere object access dominates), the CPU is mostly used up for object\ninflation. That suggests that if we could spread it out across cores,\nthe gain could be quite good. There aren't many dependencies in grep\ntasks so if we spread the workload on 8 cores, execution time should\nbe reduced by 7 or 8 times.\n\nFor fun, I hacked up a horrible, horrible \"thread safe\" version [2]\nthat probably broke 99% of git and made helgrind extremely unhappy, so\nthese numbers are at best guidelines, but..\n\n $ time ./git grep --threads=1 abc HEAD >/dev/null\n \n real 0m0,253s\n user 0m0,225s\n sys 0m0,029s\n \n $ time ./git grep --threads=8 abc HEAD >/dev/null\n warning: let's have some fun!\n \n real 0m0,157s\n user 0m0,312s\n sys 0m0,089s\n\nYou can see the \"real\" rows show quite good time reduction. Not 8\ntimes reduction, mind you, but that's where serious people dig in and\nreally speed it up ;-)\n\n[1] https://gitlab.com/snippets/1834609\n[2] https://gitlab.com/snippets/1834613\n\n> So, although it would be out of scope for GSoC, checkout, diff and log\n> (and maybe others) could all benefit from a thread-safe/parallel pack\n> access, right? If so, it is very motivating the impact this project\n> could, in theory, have :)\n\nWe have to analyze case by case. It may turn out that there are many\nopportunity to utilize multi threads. I think checkout is definitely a\ngood candidate. For \"git diff\" and \"git log\" maybe you can try \"perf\"\nto see how much workload is locked in pack access (mostly inflation,\nbecause it's easier to spot from the profile report)\n--\nDuy\n"},{"id":"371232","messageId":"CACsJy8C=1dj-1T=5dt92LK5_Ario_YL2hkQWpi2dkhXyYY=_Hw@mail.gmail.com","threadId":"50618","inReplyTo":"20190312100237.GA20471@ash","subject":"Re: Questions on GSoC 2019 Ideas","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2019-03-12T10:11:24Z","receivedAt":"2019-03-12T10:11:53Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Tue, Mar 12, 2019 at 5:02 PM Duy Nguyen wrote:\n> We have to analyze case by case. It may turn out that there are many\n\ns/are/aren't/\n\n> opportunity to utilize multi threads. I think checkout is definitely a\n> good candidate. For \"git diff\" and \"git log\" maybe you can try \"perf\"\n> to see how much workload is locked in pack access (mostly inflation,\n> because it's easier to spot from the profile report)\n-- \nDuy\n"},{"id":"373081","messageId":"CAHd-oW7fXbJyxesgCoiTOWGLH9Tpk5FUN7VsaBrqU842BJpT3Q@mail.gmail.com","threadId":"50618","inReplyTo":"CACsJy8C=1dj-1T=5dt92LK5_Ario_YL2hkQWpi2dkhXyYY=_Hw@mail.gmail.com","subject":"Re: Questions on GSoC 2019 Ideas","fromName":"Matheus Tavares Bernardino","fromEmail":"matheus.bernardino@usp.br","sentAt":"2019-04-04T01:15:21Z","receivedAt":"2019-04-04T01:15:35Z","isPatch":false,"sender":{"key":"matheus.tavb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/12701583?v=4"},"body":"Hi,\n\nI've been studying the codebase and looking for older emails in the ML\nthat discussed what I want to propose as my GSoC project. In\nparticular, I found a thread about slow git commands on chromium, so I\nreached them out at chromium's ML to ask if it's still an issue. I got\nthe following answer:\n\nOn Wed, Apr 3, 2019 at 1:41 PM Erik Chen wrote:\n> Yes, this is absolutely still a problem for Chrome. I filed some bugs for common operations that are slow for Chrome: git blame [1], git stash [2], git status [3]\n> On Linux, blame is the only operation that is really problematic. On macOS and Windows ... it's hard to find a git operation that isn't slow. :(\n\nI don't really know if treading would help stash and status, but I\nthink it could help blame. By the little I've read of blame's code so\nfar, my guess is that the priority queue used for the commits could be\nan interface for a producer-consumer mechanism and that way,\nassign_blame's main loop could be done in parallel. And as we can se\nat [4], that is 90% of the command's time. Does this makes sense?\n\nBut as Duy pointed out, if I recall correctly, for git blame to be\nparallel, pack access and diff code would have to be thread-safe\nfirst. And also, it seems, by what we've talked earlier, that this\nmuch wouldn't fit all together in a single GSoC. So, would it be a\nnice GSoC proposal to try \"making code used by blame thread-safe\",\ntargeting a future parallelism on blame to be done after GSoC? And if\nso, could you please point me out which files should I be studying to\nwrite the planning for this proposal? (Unfortunately I wasn't able to\nstudy pack access and diff code yet. I got carried on looking for\nperformance hostposts and now I'm a bit behind schedule :(\n\nAlso, an implementation for fuzzy blame is being developer right\nnow[5] and Jeff (CC-ed) suggested recently another performance\nimprovement that could be done in blame[6]. So I would like to know\nwether you think it is worthy putting efforts trying to parallelize\nit.\n\nThanks again for all the support.\nMatheus Tavares\n\n[1] https://bugs.chromium.org/p/git/issues/detail?id=18&q=\n[2] https://bugs.chromium.org/p/git/issues/detail?id=17&q=\n[3] https://bugs.chromium.org/p/git/issues/detail?id=16&q=\n[4] https://i.imgur.com/XmyJMuE.png\n[5] https://public-inbox.org/git/20190403160207.149174-1-brho@google.com/T/#mb772910506e99e00337e4606f8377f95ef41c8c6\n[6] https://public-inbox.org/git/87ftqz5osx.fsf@fencepost.gnu.org/T/#m9caa63d35d39de8d2b7c5c6852f331dc2328e1ea\n"},{"id":"373096","messageId":"CAP8UFD33xf8FMuVNakzaUhYXo3A2fnvBAoFgoDQUOKgqnWYQBw@mail.gmail.com","threadId":"50618","inReplyTo":"CAHd-oW7fXbJyxesgCoiTOWGLH9Tpk5FUN7VsaBrqU842BJpT3Q@mail.gmail.com","subject":"Re: Questions on GSoC 2019 Ideas","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2019-04-04T07:56:35Z","receivedAt":"2019-04-04T07:56:52Z","isPatch":false,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"Hi,\n\nOn Thu, Apr 4, 2019 at 3:15 AM Matheus Tavares Bernardino\n wrote:\n>\n> I've been studying the codebase and looking for older emails in the ML\n> that discussed what I want to propose as my GSoC project. In\n> particular, I found a thread about slow git commands on chromium, so I\n> reached them out at chromium's ML to ask if it's still an issue. I got\n> the following answer:\n>\n> On Wed, Apr 3, 2019 at 1:41 PM Erik Chen wrote:\n> > Yes, this is absolutely still a problem for Chrome. I filed some bugs for common operations that are slow for Chrome: git blame [1], git stash [2], git status [3]\n> > On Linux, blame is the only operation that is really problematic. On macOS and Windows ... it's hard to find a git operation that isn't slow. :(\n\nNice investigation. About git status I wonder though if they have\ntried the possible optimizations, like untracked cache or\ncore.fsmonitor.\n\n> I don't really know if treading would help stash and status, but I\n> think it could help blame. By the little I've read of blame's code so\n> far, my guess is that the priority queue used for the commits could be\n> an interface for a producer-consumer mechanism and that way,\n> assign_blame's main loop could be done in parallel. And as we can se\n> at [4], that is 90% of the command's time. Does this makes sense?\n\nI can't really tell as I haven't studied this, but from the links in\nyour email I think it kind of makes sense.\n\nInstead of doing assign_blame()'s main loop in parallel though, if my\nfocus was only making git blame faster, I think I would first try to\ncache xdl_hash_record() results and then if possible to compute\nxdl_hash_record() in parallel as it seems to be a big bottleneck and a\nquite low hanging fruit.\n\n> But as Duy pointed out, if I recall correctly, for git blame to be\n> parallel, pack access and diff code would have to be thread-safe\n> first. And also, it seems, by what we've talked earlier, that this\n> much wouldn't fit all together in a single GSoC. So, would it be a\n> nice GSoC proposal to try \"making code used by blame thread-safe\",\n> targeting a future parallelism on blame to be done after GSoC?\n\nYeah, I think it would be a nice proposal, even though it doesn't seem\nto be the most straightforward way to make git blame faster.\n\nBack in 2008 when we proposed a GSoC about creating a sequencer, it\nwasn't something that would easily fit in a GSoC, and in fact it\ndidn't, but over the long run it has been very fruitful as the\nsequencer is now used by cherry-pick and rebase -i, and there are\nplans to use it even more. So unless people think it's not a good idea\nfor some reason, which hasn't been the case yet, I am ok with a GSoC\nproject like this.\n\n> And if\n> so, could you please point me out which files should I be studying to\n> write the planning for this proposal? (Unfortunately I wasn't able to\n> study pack access and diff code yet. I got carried on looking for\n> performance hostposts and now I'm a bit behind schedule :(\n\nI don't think you need to study everything yet, and I think you\nalready did a lot of studying, so I would suggest you first try to\nsend soon a proposal with the information you have right now, and then\ndepending on the feedback you get and the time left (likely not\nmuch!!!), you might study some parts of the code a bit more later.\n\n> Also, an implementation for fuzzy blame is being developer right\n> now[5] and Jeff (CC-ed) suggested recently another performance\n> improvement that could be done in blame[6]. So I would like to know\n> wether you think it is worthy putting efforts trying to parallelize\n> it.\n\nWhat you would do seems compatible to me with the fuzzy blame effort\nand an effort to cache xdl_hash_record() results.\n\nThanks,\nChristian.\n"},{"id":"373099","messageId":"20190404082048.bocecevbaqfgfmsu@glandium.org","threadId":"50618","inReplyTo":"CAP8UFD33xf8FMuVNakzaUhYXo3A2fnvBAoFgoDQUOKgqnWYQBw@mail.gmail.com","subject":"Re: Questions on GSoC 2019 Ideas","fromName":"Mike Hommey","fromEmail":"mh@glandium.org","sentAt":"2019-04-04T08:20:48Z","receivedAt":"2019-04-04T08:20:54Z","isPatch":false,"sender":{"key":"mh@glandium.org","avatar":"https://avatars.githubusercontent.com/u/1038527?v=4"},"body":"On Thu, Apr 04, 2019 at 09:56:35AM +0200, Christian Couder wrote:\n> Hi,\n> \n> On Thu, Apr 4, 2019 at 3:15 AM Matheus Tavares Bernardino\n> wrote:\n> >\n> > I've been studying the codebase and looking for older emails in the ML\n> > that discussed what I want to propose as my GSoC project. In\n> > particular, I found a thread about slow git commands on chromium, so I\n> > reached them out at chromium's ML to ask if it's still an issue. I got\n> > the following answer:\n> >\n> > On Wed, Apr 3, 2019 at 1:41 PM Erik Chen wrote:\n> > > Yes, this is absolutely still a problem for Chrome. I filed some bugs for common operations that are slow for Chrome: git blame [1], git stash [2], git status [3]\n> > > On Linux, blame is the only operation that is really problematic. On macOS and Windows ... it's hard to find a git operation that isn't slow. :(\n> \n> Nice investigation. About git status I wonder though if they have\n> tried the possible optimizations, like untracked cache or\n> core.fsmonitor.\n\nNote that one known issue on macOS specifically on large repos is that\nthe number of files explodes the inode cache in the kernel, and lstat\nbecomes slow.\n\ne.g. https://groups.google.com/a/chromium.org/forum/#!topic/chromium-dev/p9U4jqz8kxo\n\nMike\n"},{"id":"373219","messageId":"CAHd-oW6iBQJ_SCTbRtDdWrg=NftqcMhyZ=SFkj7Am==OpG3bTA@mail.gmail.com","threadId":"50618","inReplyTo":"CAP8UFD33xf8FMuVNakzaUhYXo3A2fnvBAoFgoDQUOKgqnWYQBw@mail.gmail.com","subject":"Re: Questions on GSoC 2019 Ideas","fromName":"Matheus Tavares Bernardino","fromEmail":"matheus.bernardino@usp.br","sentAt":"2019-04-05T16:28:48Z","receivedAt":"2019-04-05T16:29:02Z","isPatch":false,"sender":{"key":"matheus.tavb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/12701583?v=4"},"body":"On Thu, Apr 4, 2019 at 4:56 AM Christian Couder\n wrote:\n>\n> Hi,\n>\n> On Thu, Apr 4, 2019 at 3:15 AM Matheus Tavares Bernardino\n> wrote:\n> >\n> > I've been studying the codebase and looking for older emails in the ML\n> > that discussed what I want to propose as my GSoC project. In\n> > particular, I found a thread about slow git commands on chromium, so I\n> > reached them out at chromium's ML to ask if it's still an issue. I got\n> > the following answer:\n> >\n> > On Wed, Apr 3, 2019 at 1:41 PM Erik Chen wrote:\n> > > Yes, this is absolutely still a problem for Chrome. I filed some bugs for common operations that are slow for Chrome: git blame [1], git stash [2], git status [3]\n> > > On Linux, blame is the only operation that is really problematic. On macOS and Windows ... it's hard to find a git operation that isn't slow. :(\n>\n> Nice investigation. About git status I wonder though if they have\n> tried the possible optimizations, like untracked cache or\n> core.fsmonitor.\n\nI don't know if they did, but I suggested them to check\ncore.commitGraph, pack.useBitmaps and core.untrackedCache (which Duy\nsuggested me in another thread).\n\n> > I don't really know if treading would help stash and status, but I\n> > think it could help blame. By the little I've read of blame's code so\n> > far, my guess is that the priority queue used for the commits could be\n> > an interface for a producer-consumer mechanism and that way,\n> > assign_blame's main loop could be done in parallel. And as we can se\n> > at [4], that is 90% of the command's time. Does this makes sense?\n>\n> I can't really tell as I haven't studied this, but from the links in\n> your email I think it kind of makes sense.\n>\n> Instead of doing assign_blame()'s main loop in parallel though, if my\n> focus was only making git blame faster, I think I would first try to\n> cache xdl_hash_record() results and then if possible to compute\n> xdl_hash_record() in parallel as it seems to be a big bottleneck and a\n> quite low hanging fruit.\n\nHm, I see. But although it would take more effort to add threading at\nassign_blame(), wouldn't it be better because more work could be done\nin parallel? I think it could be implemented in the same fashion git\ngrep does.\n\n> > But as Duy pointed out, if I recall correctly, for git blame to be\n> > parallel, pack access and diff code would have to be thread-safe\n> > first. And also, it seems, by what we've talked earlier, that this\n> > much wouldn't fit all together in a single GSoC. So, would it be a\n> > nice GSoC proposal to try \"making code used by blame thread-safe\",\n> > targeting a future parallelism on blame to be done after GSoC?\n>\n> Yeah, I think it would be a nice proposal, even though it doesn't seem\n> to be the most straightforward way to make git blame faster.\n>\n> Back in 2008 when we proposed a GSoC about creating a sequencer, it\n> wasn't something that would easily fit in a GSoC, and in fact it\n> didn't, but over the long run it has been very fruitful as the\n> sequencer is now used by cherry-pick and rebase -i, and there are\n> plans to use it even more. So unless people think it's not a good idea\n> for some reason, which hasn't been the case yet, I am ok with a GSoC\n> project like this.\n>\n> > And if\n> > so, could you please point me out which files should I be studying to\n> > write the planning for this proposal? (Unfortunately I wasn't able to\n> > study pack access and diff code yet. I got carried on looking for\n> > performance hostposts and now I'm a bit behind schedule :(\n>\n> I don't think you need to study everything yet, and I think you\n> already did a lot of studying, so I would suggest you first try to\n> send soon a proposal with the information you have right now, and then\n> depending on the feedback you get and the time left (likely not\n> much!!!), you might study some parts of the code a bit more later.\n\nThanks a lot, Christian. I'm writing my proposal and will try to send it today.\n\n> > Also, an implementation for fuzzy blame is being developer right\n> > now[5] and Jeff (CC-ed) suggested recently another performance\n> > improvement that could be done in blame[6]. So I would like to know\n> > wether you think it is worthy putting efforts trying to parallelize\n> > it.\n>\n> What you would do seems compatible to me with the fuzzy blame effort\n> and an effort to cache xdl_hash_record() results.\n>\n> Thanks,\n> Christian.\n"},{"id":"373377","messageId":"CAP8UFD0h6kgSFCp8QsT--LPNNneiFAXOzNY2zxouBc0jBqeN9g@mail.gmail.com","threadId":"50618","inReplyTo":"CAHd-oW6iBQJ_SCTbRtDdWrg=NftqcMhyZ=SFkj7Am==OpG3bTA@mail.gmail.com","subject":"Re: Questions on GSoC 2019 Ideas","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2019-04-07T23:40:51Z","receivedAt":"2019-04-07T23:43:34Z","isPatch":false,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"On Fri, Apr 5, 2019 at 6:29 PM Matheus Tavares Bernardino\n wrote:\n>\n> On Thu, Apr 4, 2019 at 4:56 AM Christian Couder\n> wrote:\n> >\n> > Nice investigation. About git status I wonder though if they have\n> > tried the possible optimizations, like untracked cache or\n> > core.fsmonitor.\n>\n> I don't know if they did, but I suggested them to check\n> core.commitGraph, pack.useBitmaps and core.untrackedCache (which Duy\n> suggested me in another thread).\n\nThanks! It would be nice to know if it has improved things for them.\n\n> > I can't really tell as I haven't studied this, but from the links in\n> > your email I think it kind of makes sense.\n> >\n> > Instead of doing assign_blame()'s main loop in parallel though, if my\n> > focus was only making git blame faster, I think I would first try to\n> > cache xdl_hash_record() results and then if possible to compute\n> > xdl_hash_record() in parallel as it seems to be a big bottleneck and a\n> > quite low hanging fruit.\n>\n> Hm, I see. But although it would take more effort to add threading at\n> assign_blame(), wouldn't it be better because more work could be done\n> in parallel? I think it could be implemented in the same fashion git\n> grep does.\n\nYeah, I agree that it seems to be worth the effort.\n\n> > I don't think you need to study everything yet, and I think you\n> > already did a lot of studying, so I would suggest you first try to\n> > send soon a proposal with the information you have right now, and then\n> > depending on the feedback you get and the time left (likely not\n> > much!!!), you might study some parts of the code a bit more later.\n>\n> Thanks a lot, Christian. I'm writing my proposal and will try to send it today.\n\nGreat!\n"}]}