{"thread":{"id":"54506","subject":"[Outreachy][Proposal] Accelerate rename detection and the range-diff","startedAt":"2020-10-26T07:50:04Z","lastAt":"2020-11-02T18:35:34Z","messageCount":5,"participants":["Sangeeta NB","Elijah Newren","Kaartic Sivaraam"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"408383","messageId":"CAHjREB6Hh+urW3j2c9p45ZudSdDv0rUP28Lb4e4TZasqTzRmDA@mail.gmail.com","threadId":"54506","inReplyTo":null,"subject":"[Outreachy][Proposal] Accelerate rename detection and the range-diff","fromName":"Sangeeta NB","fromEmail":"sangunb09@gmail.com","sentAt":"2020-10-26T07:49:50Z","receivedAt":"2020-10-26T07:50:04Z","isPatch":false,"sender":{"key":"sangunb09@gmail.com","avatar":"https://avatars.githubusercontent.com/u/64827599?v=4"},"body":"Hey Everyone,\n\nI would love to participate in outreachy this year with Git in the\nproject \"Accelerate rename detection and the range-diff command in\nGit\". I have contributed to the microproject \"Unify the meaning of\ndirty between diff and describe\"[1] which is still under review, but\nthrough the process, I have got myself familiar with the mailing list\nand patch review system. I am also contributing to another issue[2]\nwhich is still under discussion[3] about `git bisect` and `git\nrebase`.\n\n[1] https://lore.kernel.org/git/pull.751.git.1602781723670.gitgitgadget@gmail.com\n[2] https://github.com/gitgitgadget/git/issues/486\n[3] https://lore.kernel.org/git/pull.765.git.1603271344522.gitgitgadget@gmail.com/\n\nComing to the project, I have read more about it[4] and have created\nthe initial version for the timeline. I would really love to have\ncomments on it.\n\n[4] https://github.com/gitgitgadget/git/issues/519\n\nAlso, there's a column for community-specific questions in the final\napplication. Is there anything specific that I have to fill in that?\n\nPlease let me know if I missed anything.\n\nLooking forward to working and learning with you all.\n\nThanks and Regards,\nSangeeta\n\n=================================================\n\nLink to docs: https://docs.google.com/document/d/15mgqy4id1fXZWE1NvBEERWvET9zy-ZEfhp4x0NNv_d4/edit?usp=sharing\n\n=================================================\n\n## Accelerate rename detection and the range-diff command in Git\n\n# Timeline\n\n## Nov 23 - Dec 1(Before intern officially starts)\n\n* Getting to know the mentors.\n* Bonding with the community.\n* Understanding the structure of the code and familiarizing myself\nwith the requirements during the internship period.\n* Create a concrete workflow for outreachy tasks.\n\n\n## Dec 1 - Dec 20\n\n* Study about various Approximate Nearest Neighbor Search algorithms.\n* There are various comparisons for the Approximate Nearest Neighbor\nalgorithm like:\n* [ANN benchmarks](http://ann-benchmarks.com/)\n* [How to benchmark ANN\nalgorithms](https://medium.com/gsi-technology/how-to-benchmark-ann-algorithms-a9f1cef6be08)\n\n* Would compare all the algorithms and would narrow down to one or two\nbest algorithms for our use case.\n\n## Dec 11: Initial point of feedback\n\n* Would take feedback from the mentors and would ask about all the\nexpectations that mentors and the community have from me.\n\n## Dec 21 - Jan 05\n\n* Would study how Locality Sensitive Hashing (data-independent) or\nLocality Preserving Hashing (data-dependent) can improve our accuracy\n(or even complexity).\n* Would study various hashing algorithms and combine them with our\nnearest neighbor search algorithm.\n\n## Jan 06 - Jan 20\n* Study if a pre-trained Support Vector Machine can add something to\nour use case.\n* Study how different organizations(eg Gerrit) decide if two commits\nare similar or not.\n* SVM’s have accuracy disadvantage as compared to nearest neighbor\nalgorithms. Therefore, I would look into ways if we can create a\nhybrid algorithm which uses SVM’s and nearest neighbor algorithms and\nget better accuracy. There are also some research papers on the same.\nI would study that and would finalize the algorithm after discussion\nwith mentors and the community.\n\n## Jan 12: Midpoint feedback\n* Would take feedback from the mentors and would ask about ways where\nI can improve or places where I was lagging.\n\n## Jan 21 - Feb 15\n* Implement the finalized algorithm.\n* Benchmark its accuracy and complexity against existing methods.\n* Use it for the rename detection and for commit matching in `git range-diff`.\n* Update the documentation for the same.\n\n\n## Feb 16 - Mar 02 ( Wrap up)\n* Buffer period for incomplete work.\n* Wrap up the code.\n* Implement the reviews and suggestions given by mentors.\n* Write documentation for the code if required.\n* Get my patches merged.\n\n\n## Mar 02: Final feedback\n* Would take the final feedback from the mentors and would ask about\nways where I could have improved on.\n* Would talk about ways to connect even after the Outreachy period.\n\n\n## Post-Outreachy\n* I intend to keep contributing even after the Outreachy period ends.\n* Would love to co-mentor(if possible) in the next outreachy and GSoC rounds.\n* Would love to review patches of other contributors and take part in\nthe mailing list discussions.\n\n\n# Other Involvements\n* Blogging is an important part of Outreachy, therefore I would love\nto write a blog every weekend or every fortnight, as discussed with\nmentors, writing in it the summary of work done so far, anything I\nlearned in that week, and my experience.\n* I would also be glad to help other contributors and users solve\ntheir issues and help the maintainers in reviewing patches over the\noutreachy period and even after that.\n"},{"id":"408407","messageId":"CABPp-BF3MEAkJmmLv_0fWBJV_2AMqh_8P7Dqk62c2_Uz9Pa3Lw@mail.gmail.com","threadId":"54506","inReplyTo":"CAHjREB6Hh+urW3j2c9p45ZudSdDv0rUP28Lb4e4TZasqTzRmDA@mail.gmail.com","subject":"Re: [Outreachy][Proposal] Accelerate rename detection and the range-diff","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2020-10-26T16:52:30Z","receivedAt":"2020-10-26T16:52:44Z","isPatch":false,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"Hi and welcome!\n\nOn Mon, Oct 26, 2020 at 1:44 AM Sangeeta NB <sangunb09@gmail.com> wrote:\n>\n> Hey Everyone,\n>\n> I would love to participate in outreachy this year with Git in the\n> project \"Accelerate rename detection and the range-diff command in\n> Git\". I have contributed to the microproject \"Unify the meaning of\n> dirty between diff and describe\"[1] which is still under review, but\n> through the process, I have got myself familiar with the mailing list\n> and patch review system. I am also contributing to another issue[2]\n> which is still under discussion[3] about `git bisect` and `git\n> rebase`.\n>\n> [1] https://lore.kernel.org/git/pull.751.git.1602781723670.gitgitgadget@gmail.com\n> [2] https://github.com/gitgitgadget/git/issues/486\n> [3] https://lore.kernel.org/git/pull.765.git.1603271344522.gitgitgadget@gmail.com/\n>\n> Coming to the project, I have read more about it[4] and have created\n> the initial version for the timeline. I would really love to have\n> comments on it.\n>\n> [4] https://github.com/gitgitgadget/git/issues/519\n\nI might be the bearer of some bad or concerning news.  This email is\ndirected more to the mentors and others on the git mailing list, but\nobviously may affect you as well:\n\nI apologize for not stating my concerns more forcefully earlier, but I\ndidn't have as many details at the time or have an idea how fast\nmerge-ort could be upstreamed.  Anyway, I'm still concerned that this\nmight not be a good project for Outreachy due to two factors: unclear\nbenefit, and conflicts:\n\n1) I've got merges down to the point where even if there is a massive\nrename of 26000 files (e.g. renaming \"drivers/\" to \"pilots/\" in the\nlinux kernel), rename detection is NOT the long tent pole in a merge.\nSo although this project is interesting, it's not clear that this\nproject will help us much.  It might be better to get my changes\nmerged down and see if there's enough need for additional\noptimizations first.\n\n2) Ignoring what I've already submitted, the remaining diffstat for\nmerge-ort is about 5500 lines....\n  2a) If I break that ~5500 lines into patches with 50 lines each,\nthat's 111 patches.  If I assume I can send 10-20 patches per week\nwithout overwhelming folks, that's 6-11 weeks, pulling us somewhere\ninto mid-December or mid-January.  10-20 patches per week might be\nover-optimistic on reviewer fatigue, which would push it out even\nfurther.\n  2b) Work is going to soon rotate me onto other non-git projects,\nmeaning even if the mailing list can review my changes aggressively,\nthere's a chance I might not be able to keep up on feeding them to the\nlist.\n  2c) diffcore-rename.c is only ~700 lines right now.  My 5500 lines\nof changes includes over 1000 new lines for diffcore-rename.c and\nabout 150 line removals for it.  These changes are spread all over the\nfile; only four small functions remain untouched.  In fact, I even\nmade big changes to struct diff_rename_dst too, so any new uses of it\nwould almost certainly have textual conflicts.\n  2d) My diffcore-rename.c changes probably do not make logical sense\nto submit first.  They should come after some groundwork is laid for\nmerge-ort.\n\nEven though at a high level this project is complementary to the\noptimizations I made in my 'merge-ort' work, I fear there will be LOTS\nof intermediate conflicts as we both make changes to the same areas\nduring the same time and make a mess of things.\n\nIf you all think this is still a good project to have an intern work\non, I'll defer to you, but I am concerned.\n\n\nElijah\n"},{"id":"408722","messageId":"6dfa865d-cb32-47fa-b9b4-fe3901a0cf63@gmail.com","threadId":"54506","inReplyTo":"CABPp-BF3MEAkJmmLv_0fWBJV_2AMqh_8P7Dqk62c2_Uz9Pa3Lw@mail.gmail.com","subject":"Re: [Outreachy][Proposal] Accelerate rename detection and the range-diff","fromName":"Kaartic Sivaraam","fromEmail":"kaartic.sivaraam@gmail.com","sentAt":"2020-10-30T09:02:11Z","receivedAt":"2020-10-30T09:02:17Z","isPatch":false,"sender":{"key":"kaartic.sivaraam@gmail.com","avatar":"https://avatars.githubusercontent.com/u/12448084?v=4"},"body":"Hi Elijah,\n\nOn 26/10/20 10:22 pm, Elijah Newren wrote:\n> \n> On Mon, Oct 26, 2020 at 1:44 AM Sangeeta NB <sangunb09@gmail.com> wrote:\n>>\n>> I would love to participate in outreachy this year with Git in the\n>> project \"Accelerate rename detection and the range-diff command in\n>> Git\". I have contributed to the microproject \"Unify the meaning of\n>> dirty between diff and describe\"[1] which is still under review, but\n>> through the process, I have got myself familiar with the mailing list\n>> and patch review system. I am also contributing to another issue[2]\n>> which is still under discussion[3] about `git bisect` and `git\n>> rebase`.\n>>\n>> [1] https://lore.kernel.org/git/pull.751.git.1602781723670.gitgitgadget@gmail.com\n>> [2] https://github.com/gitgitgadget/git/issues/486\n>> [3] https://lore.kernel.org/git/pull.765.git.1603271344522.gitgitgadget@gmail.com/\n>>\n>> Coming to the project, I have read more about it[4] and have created\n>> the initial version for the timeline. I would really love to have\n>> comments on it.\n>>\n>> [4] https://github.com/gitgitgadget/git/issues/519\n> \n> I might be the bearer of some bad or concerning news.  This email is\n> directed more to the mentors and others on the git mailing list, but\n> obviously may affect you as well:\n> \n> I apologize for not stating my concerns more forcefully earlier, but I\n> didn't have as many details at the time or have an idea how fast\n> merge-ort could be upstreamed.  Anyway, I'm still concerned that this\n> might not be a good project for Outreachy due to two factors: unclear\n> benefit, and conflicts:\n> \n> 1) I've got merges down to the point where even if there is a massive\n> rename of 26000 files (e.g. renaming \"drivers/\" to \"pilots/\" in the\n> linux kernel), rename detection is NOT the long tent pole in a merge.\n> So although this project is interesting, it's not clear that this\n> project will help us much.  It might be better to get my changes\n> merged down and see if there's enough need for additional\n> optimizations first.\n> \n> 2) Ignoring what I've already submitted, the remaining diffstat for\n> merge-ort is about 5500 lines....\n>    2a) If I break that ~5500 lines into patches with 50 lines each,\n> that's 111 patches.  If I assume I can send 10-20 patches per week\n> without overwhelming folks, that's 6-11 weeks, pulling us somewhere\n> into mid-December or mid-January.  10-20 patches per week might be\n> over-optimistic on reviewer fatigue, which would push it out even\n> further.\n>    2b) Work is going to soon rotate me onto other non-git projects,\n> meaning even if the mailing list can review my changes aggressively,\n> there's a chance I might not be able to keep up on feeding them to the\n> list.\n>    2c) diffcore-rename.c is only ~700 lines right now.  My 5500 lines\n> of changes includes over 1000 new lines for diffcore-rename.c and\n> about 150 line removals for it.  These changes are spread all over the\n> file; only four small functions remain untouched.  In fact, I even\n> made big changes to struct diff_rename_dst too, so any new uses of it\n> would almost certainly have textual conflicts.\n>    2d) My diffcore-rename.c changes probably do not make logical sense\n> to submit first.  They should come after some groundwork is laid for\n> merge-ort.\n> \n> Even though at a high level this project is complementary to the\n> optimizations I made in my 'merge-ort' work, I fear there will be LOTS\n> of intermediate conflicts as we both make changes to the same areas\n> during the same time and make a mess of things.\n> \n\nThanks for the detailed concerns. Some thoughts:\n\n- Given that a major portion of the project would be to evaluate\n   various algorithms and identifying the most suitable one, I believe\n   implementation conflict shouldn't be a problem as it's expected to\n   start only by late-January. Also, as Christian pointed out elsewhere\n   it might be a good learning experience.\n\n- I do have a concern about one thing, though. For evaluating the\n   algorithm in the context of Git, we might need to do some experimental\n   implementations to get some metrics which would serve as the data that\n   we could use to identify the optimal algorithm. I'm  wondering whether\n   your planned changes might affect that. In the sense that, is there a\n   chance for the evaluation to become obsolete as a consequence of those\n   changes? If yes, what could we do to overcome that? Any thoughts on\n   this would be helpful.\n\n> If you all think this is still a good project to have an intern work\n> on, I'll defer to you, but I am concerned.\n> \n\n-- \nSivaraam\n"},{"id":"408800","messageId":"CABPp-BE7+9_AiYCP+m7TOY85d4FWHG4rORk16Z6bsnAWxVPwCg@mail.gmail.com","threadId":"54506","inReplyTo":"6dfa865d-cb32-47fa-b9b4-fe3901a0cf63@gmail.com","subject":"Re: [Outreachy][Proposal] Accelerate rename detection and the range-diff","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2020-10-31T20:31:21Z","receivedAt":"2020-10-31T20:31:35Z","isPatch":false,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"Hi,\n\nOn Fri, Oct 30, 2020 at 2:02 AM Kaartic Sivaraam\n<kaartic.sivaraam@gmail.com> wrote:\n>\n> Hi Elijah,\n>\n> On 26/10/20 10:22 pm, Elijah Newren wrote:\n> >\n> > On Mon, Oct 26, 2020 at 1:44 AM Sangeeta NB <sangunb09@gmail.com> wrote:\n> >>\n> >> I would love to participate in outreachy this year with Git in the\n> >> project \"Accelerate rename detection and the range-diff command in\n> >> Git\". I have contributed to the microproject \"Unify the meaning of\n> >> dirty between diff and describe\"[1] which is still under review, but\n> >> through the process, I have got myself familiar with the mailing list\n> >> and patch review system. I am also contributing to another issue[2]\n> >> which is still under discussion[3] about `git bisect` and `git\n> >> rebase`.\n> >>\n> >> [1] https://lore.kernel.org/git/pull.751.git.1602781723670.gitgitgadget@gmail.com\n> >> [2] https://github.com/gitgitgadget/git/issues/486\n> >> [3] https://lore.kernel.org/git/pull.765.git.1603271344522.gitgitgadget@gmail.com/\n> >>\n> >> Coming to the project, I have read more about it[4] and have created\n> >> the initial version for the timeline. I would really love to have\n> >> comments on it.\n> >>\n> >> [4] https://github.com/gitgitgadget/git/issues/519\n> >\n> > I might be the bearer of some bad or concerning news.  This email is\n> > directed more to the mentors and others on the git mailing list, but\n> > obviously may affect you as well:\n> >\n> > I apologize for not stating my concerns more forcefully earlier, but I\n> > didn't have as many details at the time or have an idea how fast\n> > merge-ort could be upstreamed.  Anyway, I'm still concerned that this\n> > might not be a good project for Outreachy due to two factors: unclear\n> > benefit, and conflicts:\n> >\n> > 1) I've got merges down to the point where even if there is a massive\n> > rename of 26000 files (e.g. renaming \"drivers/\" to \"pilots/\" in the\n> > linux kernel), rename detection is NOT the long tent pole in a merge.\n> > So although this project is interesting, it's not clear that this\n> > project will help us much.  It might be better to get my changes\n> > merged down and see if there's enough need for additional\n> > optimizations first.\n> >\n> > 2) Ignoring what I've already submitted, the remaining diffstat for\n> > merge-ort is about 5500 lines....\n> >    2a) If I break that ~5500 lines into patches with 50 lines each,\n> > that's 111 patches.  If I assume I can send 10-20 patches per week\n> > without overwhelming folks, that's 6-11 weeks, pulling us somewhere\n> > into mid-December or mid-January.  10-20 patches per week might be\n> > over-optimistic on reviewer fatigue, which would push it out even\n> > further.\n> >    2b) Work is going to soon rotate me onto other non-git projects,\n> > meaning even if the mailing list can review my changes aggressively,\n> > there's a chance I might not be able to keep up on feeding them to the\n> > list.\n> >    2c) diffcore-rename.c is only ~700 lines right now.  My 5500 lines\n> > of changes includes over 1000 new lines for diffcore-rename.c and\n> > about 150 line removals for it.  These changes are spread all over the\n> > file; only four small functions remain untouched.  In fact, I even\n> > made big changes to struct diff_rename_dst too, so any new uses of it\n> > would almost certainly have textual conflicts.\n> >    2d) My diffcore-rename.c changes probably do not make logical sense\n> > to submit first.  They should come after some groundwork is laid for\n> > merge-ort.\n> >\n> > Even though at a high level this project is complementary to the\n> > optimizations I made in my 'merge-ort' work, I fear there will be LOTS\n> > of intermediate conflicts as we both make changes to the same areas\n> > during the same time and make a mess of things.\n> >\n>\n> Thanks for the detailed concerns. Some thoughts:\n>\n> - Given that a major portion of the project would be to evaluate\n>    various algorithms and identifying the most suitable one, I believe\n>    implementation conflict shouldn't be a problem as it's expected to\n>    start only by late-January. Also, as Christian pointed out elsewhere\n>    it might be a good learning experience.\n\n\"late-January\" _might_ be okay, but I'm worried that relying on\noptimistic timelines is a bad idea.  However, if the primary purpose\nis a good learning experience, or if the primary purpose is to\nevaluate different algorithms (i.e. we're not relying on the timelines\nto avoid conflict, it's just a bonus if they don't), then sure, no\nproblem there.\n\n> - I do have a concern about one thing, though. For evaluating the\n>    algorithm in the context of Git, we might need to do some experimental\n>    implementations to get some metrics which would serve as the data that\n>    we could use to identify the optimal algorithm. I'm  wondering whether\n>    your planned changes might affect that. In the sense that, is there a\n>    chance for the evaluation to become obsolete as a consequence of those\n>    changes? If yes, what could we do to overcome that? Any thoughts on\n>    this would be helpful.\n\nThat is certainly a possibility, yes.  One way to address that concern\nis for me to freeze some branch (likely some version that I deploy\ninternally at $DAYJOB for testing), and for you to build on that.  If\nall the new merge backend code gets reviewed and upstreamed fast\nenough, and the areas you depend on don't change too drastically based\non reviewer comments, then building on merge-ort creates no\nimpediments for the Outreachy project to get upstreamed at the normal\ntime.  I can understand, though, if that plan seems worrisome due to\nworries about how fast the new backend will be upstreamed or how much\nit needs to change in the process; that is, after all, why I raised my\nconcerns in the first place.\n"},{"id":"408875","messageId":"af22d119-7ab9-d49e-279c-c912786098dd@gmail.com","threadId":"54506","inReplyTo":"CABPp-BE7+9_AiYCP+m7TOY85d4FWHG4rORk16Z6bsnAWxVPwCg@mail.gmail.com","subject":"Re: [Outreachy][Proposal] Accelerate rename detection and the range-diff","fromName":"Kaartic Sivaraam","fromEmail":"kaartic.sivaraam@gmail.com","sentAt":"2020-11-02T18:35:29Z","receivedAt":"2020-11-02T18:35:34Z","isPatch":false,"sender":{"key":"kaartic.sivaraam@gmail.com","avatar":"https://avatars.githubusercontent.com/u/12448084?v=4"},"body":"Hi Elijah,\n\nOn 01/11/20 2:01 am, Elijah Newren wrote:\n> \n> On Fri, Oct 30, 2020 at 2:02 AM Kaartic Sivaraam\n> <kaartic.sivaraam@gmail.com> wrote:\n>>\n>> Thanks for the detailed concerns. Some thoughts:\n>>\n>> - Given that a major portion of the project would be to evaluate\n>>     various algorithms and identifying the most suitable one, I believe\n>>     implementation conflict shouldn't be a problem as it's expected to\n>>     start only by late-January. Also, as Christian pointed out elsewhere\n>>     it might be a good learning experience.\n> \n> \"late-January\" _might_ be okay, but I'm worried that relying on\n> optimistic timelines is a bad idea.  However, if the primary purpose\n> is a good learning experience, or if the primary purpose is to\n> evaluate different algorithms (i.e. we're not relying on the timelines\n> to avoid conflict, it's just a bonus if they don't), then sure, no\n> problem there.\n> \n\nYeah. I believe a good part of this project would be evaluating the \nvarious algorithms. Implementation would be a part of it, sure. I don't \nthink it would be too time sensitive, though. So, I hope we can work \nthrough the timelines as the project and your work progress.\n\n>> - I do have a concern about one thing, though. For evaluating the\n>>     algorithm in the context of Git, we might need to do some experimental\n>>     implementations to get some metrics which would serve as the data that\n>>     we could use to identify the optimal algorithm. I'm  wondering whether\n>>     your planned changes might affect that. In the sense that, is there a\n>>     chance for the evaluation to become obsolete as a consequence of those\n>>     changes? If yes, what could we do to overcome that? Any thoughts on\n>>     this would be helpful.\n> \n> That is certainly a possibility, yes.  One way to address that concern\n> is for me to freeze some branch (likely some version that I deploy\n> internally at $DAYJOB for testing), and for you to build on that.  If\n> all the new merge backend code gets reviewed and upstreamed fast\n> enough, and the areas you depend on don't change too drastically based\n> on reviewer comments, then building on merge-ort creates no\n> impediments for the Outreachy project to get upstreamed at the normal\n> time.\n\nThanks. That does sound like a good way to overcome that problem. We can \ndiscuss more about that once the intern is selected and their internship \nperiod begins.\n\n> I can understand, though, if that plan seems worrisome due to\n> worries about how fast the new backend will be upstreamed or how much\n> it needs to change in the process; that is, after all, why I raised my\n> concerns in the first place.\n> \n\nWhich indeed is very helpful for planning the project. Thanks for that! \nIts pretty clear now that closely following your work and adapting the \ntimeline accordingly as time progresses is a part of the project. That \nmight indeed be an interesting experience in and of itself for the \nintern who would be working on this project.\n\n-- \nSivaraam\n"}]}