{"thread":{"id":"56090","subject":"[RFC] Bump {diff,merge}.renameLimit ?","startedAt":"2021-07-11T00:28:57Z","lastAt":"2021-07-12T21:41:43Z","messageCount":9,"participants":["Elijah Newren","Ævar Arnfjörð Bjarmason","Jeff King","Felipe Contreras"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"429659","messageId":"CABPp-BFzp3TCWiF1QAVSfywDLYrz=GOQszVM-sw5p0rSB8RWvw@mail.gmail.com","threadId":"56090","inReplyTo":null,"subject":"[RFC] Bump {diff,merge}.renameLimit ?","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-07-11T00:28:43Z","receivedAt":"2021-07-11T00:28:57Z","isPatch":false,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"[CC'ing folks I've seen comment on these limits.]\n\nHi everyone,\n\nI'm considering bumping {diff,merge}.renameLimit, which control the\nquadratic portion of rename/copy detection. Should they be bumped?\nIf so, moderately higher, or much higher?\n\nI lean towards a moderate bump for diff.renameLimit, and preferably\nmore than just a moderate bump for merge.renameLimit. I have\ncalculations for what \"moderate\" translates to, based on a number of\nassumptions. But there's several reasons to break with past\nguideposts for how these limits were picked. See below for various\narguments in each of the directions.\n\nSo...thoughts?\n\nThanks,\nElijah\n\n\n==> Arguments for bumping MUCH higher:\n\n* Linus said the real reason for the renameLimit was excessive memory\n usage (not perf)[1]. But Junio dropped the memory requirements to\n linear in commit 6d24ad971c81 (Optimize rename detection for a huge\n diff, 2008-01-29)\n\n* Linus oft recommends setting diff.renameLimit=0 [2,3,4,5,6,7,8,9,10,11]\n (which maps to 32767 [12]).\n\n* My colleagues happily raised merge.renameLimit beyond 32767 when the\n artificial cap was removed. 10 minute waits were annoying, but much\n less so than having to manually cherry-pick commits (especially given\n the risk of getting it wrong).[13]\n\n\n==> Arguments for bumping MODERATELY higher:\n\n* We have bumped the limits twice before (in 2008 and 2011), both times\n stating performance as the limiting factor. Processors are faster\n today than then.[14,15]\n\n* Peff's computations for performance in the last two bumps used \"the\n average size of a file in the linux-2.6 repository\"[16], for which I\n assume average==mean, but the file selected was actually ~2x larger\n than the mean file size according to my calculations[17].\n\n* I think the median file size is a better predictor of rename\n performance than mean file size, and median file size is ~2.5x smaller\n than the mean[18].\n\n\n==> Arguments for not bumping either limit:\n\n* The feedback about the limit is better today than when we last changed\n the limits, and folks can configure a higher limit relatively easily.\n Many already have.\n\n* This issue won't come up nearly as much any more once we switch the\n default merge backend to ort, due to my performance work[19] (many\n renames can be outright skipped without affecting merge quality, and\n many others can be detected in linear time -- the cherry-picks that\n used to require merge.renameLimit=48941 and took 10 minutes can now\n complete in less than a second with the default merge.renameLimit of\n 1000.)\n\n* It'd take too long to read all the footnotes in this email, so screw\n it. :-)\n\n\n==> Footnotes:\n\n[1] https://lore.kernel.org/git/AANLkTimKp+Z==QXJg2Bagot+Df4REeANuxwVi7bpPCXr@mail.gmail.com/\n\n[2] https://lore.kernel.org/git/alpine.LFD.0.999.0710161030430.6887@woody.linux-foundation.org/\n 2007-10-16\n[3] https://lore.kernel.org/git/alpine.LFD.2.00.0811032021210.3419@nehalem.linux-foundation.org/\n 2008-11-03\n[4] https://lore.kernel.org/git/AANLkTimKp+Z==QXJg2Bagot+Df4REeANuxwVi7bpPCXr@mail.gmail.com/\n 2011-02-18\n[5] https://lore.kernel.org/lkml/alpine.LFD.0.999.0710111944120.6887@woody.linux-foundation.org/\n 2007-10-11\n[6] https://lore.kernel.org/lkml/alpine.LFD.1.10.0808052157400.15995@nehalem.linux-foundation.org/\n 2008-08-05\n[7] https://lore.kernel.org/lkml/alpine.LFD.2.01.0909160813400.4950@localhost.localdomain/\n 2009-09-16\n[8] https://lore.kernel.org/lkml/CA+55aFw1GVvszqoC_f0RAvG5t1xj0CSYLhLU=y0gQ+_54Gsomw@mail.gmail.com/\n 2011-10-25\n[9] https://lore.kernel.org/lkml/CA+55aFyWefZ1jJLMJKXhy0Qif-iBmjG6n-evcbvkbWS5mDrs0g@mail.gmail.com/\n 2015-02-16\n[10] https://lore.kernel.org/lkml/CA+55aFxODGv7-AvnqFmxrXBcS2w0XzHuZ7UuRi3EMQz4-oeLJA@mail.gmail.com/\n 2018-04-11\n[11] https://lore.kernel.org/lkml/CAHk-=wg=CTtNrxPeFzkDw053dY3urchiyxevHnUXHhTGbK=9OQ@mail.gmail.com/\n 2020-06-03\n\n[12] 89973554b52c (diffcore-rename: make diff-tree -l0 mean -l,\n 2017-11-29)\n\n[13] https://lore.kernel.org/git/20171110173956.25105-3-newren@gmail.com/\n\n[14] 50705915eae8 (bump rename limit defaults, 2008-04-30)\n[15] 92c57e5c1d29 (bump rename limit defaults (again), 2011-02-19)\n\n[16] https://lore.kernel.org/git/20080211113516.GB6344@coredump.intra.peff.net/\n\n[17] Calculated and compared as follows (num files, mean size, size Peff used):\n $ git ls-tree -rl v2.6.25 | wc -l\n 23810\n $ git ls-tree -rl v2.6.25 | awk '{sum += $4} END{print sum/23810}'\n 11150.3\n $ git show v2.6.25:arch/m68k/Kconfig | wc -c\n 20977\n\n[18] Calculated as 4198 as follows (note: 11905 = 23810/2):\n $ git ls-tree -rl v2.6.25 | sort -n -k 4 | head -n 11905 | tail -n 1\n 100644 blob 29510dc515109ad5dd8a16b5936f1f6086ae417c 4198\nDocumentation/lguest/lguest.txt\n\n[19] See \"Overall Results\" from https://github.com/gitgitgadget/git/pull/990\n"},{"id":"429707","messageId":"87a6ms4wgw.fsf@evledraar.gmail.com","threadId":"56090","inReplyTo":"CABPp-BFzp3TCWiF1QAVSfywDLYrz=GOQszVM-sw5p0rSB8RWvw@mail.gmail.com","subject":"Re: [RFC] Bump {diff,merge}.renameLimit ?","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2021-07-11T16:42:49Z","receivedAt":"2021-07-11T17:00:20Z","isPatch":false,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Sat, Jul 10 2021, Elijah Newren wrote:\n\n> I'm considering bumping {diff,merge}.renameLimit, which control the\n> quadratic portion of rename/copy detection. Should they be bumped?\n> If so, moderately higher, or much higher?\n>\n> I lean towards a moderate bump for diff.renameLimit, and preferably\n> more than just a moderate bump for merge.renameLimit. I have\n> calculations for what \"moderate\" translates to, based on a number of\n> assumptions. But there's several reasons to break with past\n> guideposts for how these limits were picked. See below for various\n> arguments in each of the directions.\n>\n> So...thoughts?\n\nI think the most relevant is something you didn't state: That when this\nlimit was introduced (well, diff.*, not merge.*) there was no progress\noutput in git.\n\nWe should err entirely on producing consistent and predictable results,\nand not change how git works when we it hits some arbitrary limit. To\nthe extent that this is needed it's sufficient to opt-in to it, i.e. we\ndo/should show a progress bar, advice() etc. showing why we're doing\nthis much work, so those users can adjust the limit (or not).\n"},{"id":"429757","messageId":"CABPp-BGE+8spsq9HZ6KNwWk_hYy5pj5vjJ8NQQuQiUN7qz7GCA@mail.gmail.com","threadId":"56090","inReplyTo":"87a6ms4wgw.fsf@evledraar.gmail.com","subject":"Re: [RFC] Bump {diff,merge}.renameLimit ?","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-07-12T15:23:18Z","receivedAt":"2021-07-12T15:23:32Z","isPatch":false,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"Hi Ævar,\n\nThanks for reading and commenting. You certainly brought a new angle\nto the question...\n\nOn Sun, Jul 11, 2021 at 10:00 AM Ævar Arnfjörð Bjarmason\n wrote:\n>\n> On Sat, Jul 10 2021, Elijah Newren wrote:\n>\n> > I'm considering bumping {diff,merge}.renameLimit, which control the\n> > quadratic portion of rename/copy detection. Should they be bumped?\n> > If so, moderately higher, or much higher?\n> >\n> > I lean towards a moderate bump for diff.renameLimit, and preferably\n> > more than just a moderate bump for merge.renameLimit. I have\n> > calculations for what \"moderate\" translates to, based on a number of\n> > assumptions. But there's several reasons to break with past\n> > guideposts for how these limits were picked. See below for various\n> > arguments in each of the directions.\n> >\n> > So...thoughts?\n>\n> I think the most relevant is something you didn't state: That when this\n> limit was introduced (well, diff.*, not merge.*) there was no progress\n> output in git.\n\nI am convinced that good progress output is very important. I've\nsubmitted multiple patches for progress output specifically for rename\ndetection[1]\n\nHowever, I am not convinced that the lack of progress output in git\nwhen this limit was introduced is the most relevant thing. If it\nwere, then the lively thread when Peff posted his past series to both\nintroduce the progress output for rename detection and simultaneously\nbump the limits probably would have spurred comments about not needing\nboth[2].\n\n> We should err entirely on producing consistent and predictable results,\n> and not change how git works when we it hits some arbitrary limit. To\n> the extent that this is needed it's sufficient to opt-in to it, i.e. we\n> do/should show a progress bar, advice() etc. showing why we're doing\n> this much work, so those users can adjust the limit (or not).\n\nSo I've read and re-read your response multiple times, but I am still\nnot sure what you're advocating for. I think you're either advocating\nfor rename detection to be turned off by default, or for a new\n\"unlimited\" mode to be introduced and be the default (maybe even\nredefining what the value of \"0\" means in order to implement this),\nbut I can't tell which. Could you clarify?\n\n\n[1] In particular:\n d6861d0258df (progress: fix progress meters when dealing with lots\nof work, 2017-11-13)\n 9268cf4a2ef6 (sequencer: show rename progress during cherry picks,\n2017-11-13)\n 81c4bf02964e (diffcore-rename: reduce jumpiness in progress\ncounters, 2020-12-11)\n\n[2] See https://lore.kernel.org/git/20110219101936.GB20577@sigill.intra.peff.net/\n"},{"id":"429774","messageId":"871r834gqz.fsf@evledraar.gmail.com","threadId":"56090","inReplyTo":"CABPp-BGE+8spsq9HZ6KNwWk_hYy5pj5vjJ8NQQuQiUN7qz7GCA@mail.gmail.com","subject":"Re: [RFC] Bump {diff,merge}.renameLimit ?","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2021-07-12T16:48:50Z","receivedAt":"2021-07-12T16:52:08Z","isPatch":false,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Mon, Jul 12 2021, Elijah Newren wrote:\n\n> Hi Ævar,\n>\n> Thanks for reading and commenting. You certainly brought a new angle\n> to the question...\n>\n> On Sun, Jul 11, 2021 at 10:00 AM Ævar Arnfjörð Bjarmason\n> wrote:\n>>\n>> On Sat, Jul 10 2021, Elijah Newren wrote:\n>>\n>> > I'm considering bumping {diff,merge}.renameLimit, which control the\n>> > quadratic portion of rename/copy detection. Should they be bumped?\n>> > If so, moderately higher, or much higher?\n>> >\n>> > I lean towards a moderate bump for diff.renameLimit, and preferably\n>> > more than just a moderate bump for merge.renameLimit. I have\n>> > calculations for what \"moderate\" translates to, based on a number of\n>> > assumptions. But there's several reasons to break with past\n>> > guideposts for how these limits were picked. See below for various\n>> > arguments in each of the directions.\n>> >\n>> > So...thoughts?\n>>\n>> I think the most relevant is something you didn't state: That when this\n>> limit was introduced (well, diff.*, not merge.*) there was no progress\n>> output in git.\n>\n> I am convinced that good progress output is very important. I've\n> submitted multiple patches for progress output specifically for rename\n> detection[1]\n>\n> However, I am not convinced that the lack of progress output in git\n> when this limit was introduced is the most relevant thing. If it\n> were, then the lively thread when Peff posted his past series to both\n> introduce the progress output for rename detection and simultaneously\n> bump the limits probably would have spurred comments about not needing\n> both[2].\n\nI see I had a dead-end reply in that thread in 2011 (didn't spot the\nprogress patch there).\n\n...\n\n>> We should err entirely on producing consistent and predictable results,\n>> and not change how git works when we it hits some arbitrary limit. To\n>> the extent that this is needed it's sufficient to opt-in to it, i.e. we\n>> do/should show a progress bar, advice() etc. showing why we're doing\n>> this much work, so those users can adjust the limit (or not).\n\n> So I've read and re-read your response multiple times, but I am still\n> not sure what you're advocating for. I think you're either advocating\n> for rename detection to be turned off by default, or for a new\n> \"unlimited\" mode to be introduced and be the default (maybe even\n> redefining what the value of \"0\" means in order to implement this),\n> but I can't tell which. Could you clarify?\n\nI'm advocating for an \"unlimited\" default as long as we have\nprogress/advice or whatever other output would direct users for whom\nit's very slow to tweaking the setting (or not).\n\nAnyway, yes some may disagree with this stance. I'm not saying it's\ndemonstrably obvious that we should have \"unlimited\".\n\nI do think that it's much better if git behaves that way, i.e. that we\ndon't have arbitrary limits that completely change behavior once they're\ntripped.\n\nBetter to spend more CPU, and if it's too slow for someone they can\ntweak the limits.\n\n> [1] In particular:\n> d6861d0258df (progress: fix progress meters when dealing with lots\n> of work, 2017-11-13)\n> 9268cf4a2ef6 (sequencer: show rename progress during cherry picks,\n> 2017-11-13)\n> 81c4bf02964e (diffcore-rename: reduce jumpiness in progress\n> counters, 2020-12-11)\n>\n> [2] See https://lore.kernel.org/git/20110219101936.GB20577@sigill.intra.peff.net/\n\n"},{"id":"429779","messageId":"YOx43fqGyQMy7+tR@coredump.intra.peff.net","threadId":"56090","inReplyTo":"CABPp-BFzp3TCWiF1QAVSfywDLYrz=GOQszVM-sw5p0rSB8RWvw@mail.gmail.com","subject":"Re: [RFC] Bump {diff,merge}.renameLimit ?","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2021-07-12T17:16:13Z","receivedAt":"2021-07-12T17:16:15Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"tl;dr Bumping the limit seems like a good idea to me.\n\nOn Sat, Jul 10, 2021 at 05:28:43PM -0700, Elijah Newren wrote:\n\n> * My colleagues happily raised merge.renameLimit beyond 32767 when the\n> artificial cap was removed. 10 minute waits were annoying, but much\n> less so than having to manually cherry-pick commits (especially given\n> the risk of getting it wrong).[13]\n\nOne tricky thing here is that waiting 10 minutes may be worth it _if the\nrename detection finds something_. If it doesn't, then it's just\nannoying.\n\nI do think progress meters help a bit there, because then at least the\nuser understands what's going on. I'll go into more detail in the\nsub-thread there. :)\n\n> ==> Arguments for bumping MODERATELY higher:\n> \n> * We have bumped the limits twice before (in 2008 and 2011), both times\n> stating performance as the limiting factor. Processors are faster\n> today than then.[14,15]\n\nYeah, it is definitely time to revisit the default numbers. I think at\none point we talked about letting it run for N wallclock seconds before\ngiving up, but we've been hesitant to introduce that kind of time-based\nlimit, because it ends up with non-deterministic results (plus you don't\nrealize you're not going to finish until you've already wasted a bunch\nof time, whereas the static limits can avoid even beginning the work).\n\n> * Peff's computations for performance in the last two bumps used \"the\n> average size of a file in the linux-2.6 repository\"[16], for which I\n> assume average==mean, but the file selected was actually ~2x larger\n> than the mean file size according to my calculations[17].\n> [...]\n> [17] Calculated and compared as follows (num files, mean size, size Peff used):\n> $ git ls-tree -rl v2.6.25 | wc -l\n> 23810\n> $ git ls-tree -rl v2.6.25 | awk '{sum += $4} END{print sum/23810}'\n> 11150.3\n> $ git show v2.6.25:arch/m68k/Kconfig | wc -c\n> 20977\n\nI don't remember my methodology at this point, but perhaps it was based\non blobs in the graph, not just one tree, like:\n\n $ git rev-list --objects v2.6.25 |\n git cat-file --batch-check='%(objecttype) %(objectsize) %(rest)' |\n awk '\n /^blob/ { sum += $2; total += 1 }\n END { print sum / total }\n '\n 27535.8\n\nI suspect the difference versus a single tree is that there is a\nquadratic-ish property going on with file size: the bigger the file, the\nmore likely it is to be touched (so total storage is closer to bytes^2).\n\nLooking at single-tree blob sizes is probably better though, as rename\ndetection will happen between two single trees.\n\n> * I think the median file size is a better predictor of rename\n> performance than mean file size, and median file size is ~2.5x smaller\n> than the mean[18].\n\nThere you might get hit with the quadratic-update thing again, though.\nThe big files are more likely to be touched, so could be weighted more\n(though are they more likely to have been added/delete/renamed? Who\nknows).\n\nI don't think file size matters all _that_ much, though, as it has a\nlinear relationship to time spent. Whereas the number of entries is\nquadratic. And of course the whole experiment is ball-parking in the\nfirst place. We're looking for order-of-magnitude approximations, I'd\nthink.\n\n> * The feedback about the limit is better today than when we last changed\n> the limits, and folks can configure a higher limit relatively easily.\n> Many already have.\n\nI can't remember the last time I saw the limit kick in in practice, but\nthen I don't generally work with super-large repos (and my workflows\ntypically do not encourage merging across big segments of history).\nNor do I remember the topic coming up on the list after the last bump.\nSo maybe that means that people are happily bumping the limits\nthemselves via config.\n\nBut I don't think that's really an argument against at least a moderate\nbump. If it helps even a few people avoid having to learn about the\nconfig, that's time saved. And it's a trivial code change on our end.\n\n-Peff\n"},{"id":"429782","messageId":"YOx+Ok/EYvLqRMzJ@coredump.intra.peff.net","threadId":"56090","inReplyTo":"871r834gqz.fsf@evledraar.gmail.com","subject":"Re: [RFC] Bump {diff,merge}.renameLimit ?","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2021-07-12T17:39:06Z","receivedAt":"2021-07-12T17:39:08Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Jul 12, 2021 at 06:48:50PM +0200, Ævar Arnfjörð Bjarmason wrote:\n\n> > So I've read and re-read your response multiple times, but I am still\n> > not sure what you're advocating for. I think you're either advocating\n> > for rename detection to be turned off by default, or for a new\n> > \"unlimited\" mode to be introduced and be the default (maybe even\n> > redefining what the value of \"0\" means in order to implement this),\n> > but I can't tell which. Could you clarify?\n> \n> I'm advocating for an \"unlimited\" default as long as we have\n> progress/advice or whatever other output would direct users for whom\n> it's very slow to tweaking the setting (or not).\n> \n> Anyway, yes some may disagree with this stance. I'm not saying it's\n> demonstrably obvious that we should have \"unlimited\".\n> \n> I do think that it's much better if git behaves that way, i.e. that we\n> don't have arbitrary limits that completely change behavior once they're\n> tripped.\n> \n> Better to spend more CPU, and if it's too slow for someone they can\n> tweak the limits.\n\nThis seems like a reasonable view to me for merges. As noted, we already\nshow progress for rename detection there, so at least the use knows that\nwe're working.\n\nIt might be nice to provide similar advice to what we show now when the\nlimit kicks in. I.e., now we say \"we turned off rename detection\nbecause this merge is huge; you can bump this config to enable it\". But\nwe may want to say \"woah, this rename detection is taking a long time;\nyou can skip it by tweaking this config\". Probably with a much higher\nlimit than the progress meter kicking in (I'm thinking something like\n30+ seconds).\n\nFor diffs we don't ever show progress. There are two things that make\nthat a bit hairy:\n\n 1. Most diff operations use the pager, and we send stderr there. That\n gets weird with our \"\\r\" overwriting.\n\n 2. Traversing via git-log, etc, will show a series of diffs, which\n means an unbounded number of progress meters. And potentially we're\n doing work that doesn't match what the user is looking at in the\n pager (e.g., they are looking at commit X, but we are computing\n X~30 while the pager has buffered all points in between; showing a\n progress meter for X~30 is distracting at that point).\n\nI posted a series back in 2011 to try to deal with these. It's in the\nsub-thread at:\n\n https://lore.kernel.org/git/20110324174556.GA30661@sigill.intra.peff.net/\n\nIt's also been part of my \"rebase forward and merge into my custom\nbuild\" strategy for the past 10+ years (even though I had totally\nforgotten it existed). So you can get working current patches by\nfetching:\n\n https://github/com/peff/git jk/rename-progress\n\nThey do work, and running:\n\n git -c diff.renamelimit=65535 diff v2.6.12 --raw\n\nin linux.git is very satisfying. I think one sticking point is that\nsending separate lines to stderr (outside of the pager) only looks good\nif your pager is careful not to take over the terminal until there's\nsomething to show. \"less\" does this, and I'd expect most traditional\npagers to do so. But there may be those that don't, so we'd probably\nneed another config option to give an escape hatch.\n\n-Peff\n"},{"id":"429827","messageId":"CABPp-BEdUmxXVCx=5pb0=LN-0YBtrEB-wngPC5vys6fjVctgaQ@mail.gmail.com","threadId":"56090","inReplyTo":"YOx43fqGyQMy7+tR@coredump.intra.peff.net","subject":"Re: [RFC] Bump {diff,merge}.renameLimit ?","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-07-12T20:23:38Z","receivedAt":"2021-07-12T20:23:52Z","isPatch":false,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Mon, Jul 12, 2021 at 10:16 AM Jeff King wrote:\n>\n> tl;dr Bumping the limit seems like a good idea to me.\n\n:-)\n\n> On Sat, Jul 10, 2021 at 05:28:43PM -0700, Elijah Newren wrote:\n>\n> > * My colleagues happily raised merge.renameLimit beyond 32767 when the\n> > artificial cap was removed. 10 minute waits were annoying, but much\n> > less so than having to manually cherry-pick commits (especially given\n> > the risk of getting it wrong).[13]\n>\n> One tricky thing here is that waiting 10 minutes may be worth it _if the\n> rename detection finds something_. If it doesn't, then it's just\n> annoying.\n>\n> I do think progress meters help a bit there, because then at least the\n> user understands what's going on. I'll go into more detail in the\n> sub-thread there. :)\n\nAnother thing that helps here (at least for merges rather than diffs)\nis that we can determine a priori whether individual renames will have\nno effect on the merge result and just exclude those particular\nrenames from the detection machinery. Well, at least we can do this\nwith the new merge-ort backend. That should dramatically reduce the\nannoyance factor once we make it the default.\n\n...\n> Yeah, it is definitely time to revisit the default numbers. I think at\n> one point we talked about letting it run for N wallclock seconds before\n> giving up, but we've been hesitant to introduce that kind of time-based\n> limit, because it ends up with non-deterministic results (plus you don't\n> realize you're not going to finish until you've already wasted a bunch\n> of time, whereas the static limits can avoid even beginning the work).\n\nYeah, I'm kinda glad we didn't go that route; seems problematic to me.\n\n...\n> I don't remember my methodology at this point, but perhaps it was based\n> on blobs in the graph, not just one tree, like:\n>\n> $ git rev-list --objects v2.6.25 |\n> git cat-file --batch-check='%(objecttype) %(objectsize) %(rest)' |\n> awk '\n> /^blob/ { sum += $2; total += 1 }\n> END { print sum / total }\n> '\n> 27535.8\n>\n> I suspect the difference versus a single tree is that there is a\n> quadratic-ish property going on with file size: the bigger the file, the\n> more likely it is to be touched (so total storage is closer to bytes^2).\n\nAh, gotcha. That makes sense.\n\n> Looking at single-tree blob sizes is probably better though, as rename\n> detection will happen between two single trees.\n\nAgreed.\n\n> > * I think the median file size is a better predictor of rename\n> > performance than mean file size, and median file size is ~2.5x smaller\n> > than the mean[18].\n>\n> There you might get hit with the quadratic-update thing again, though.\n> The big files are more likely to be touched, so could be weighted more\n> (though are they more likely to have been added/delete/renamed? Who\n> knows).\n\nI'll agree that big files are more likely to be updated, but I don't\nthink renames are weighted towards bigger files. In fact, I wrote a\nquick script to look at the sizes of all the renamed files in the\nhistory of v2.6.25, and the mean (8034.1) and median (3866) of the\nrenamed files sizes in that history are comparable to the mean\n(11150.3) and median (4198) of the files sizes in the v2.6.25 tree.\n\nI re-did the calculations using v5.5, and found that the mean\n(12495.1) and median (3702) sizes of renames in all linux history up\nto that point again were a bit less than the mean (13449.2) and median\n(3860) file size of a file in the final v5.5 tree.\n\nGranted, this is a bit hand-wavy (what about creations or deletions?\nIs there too much bias from the fact that I did rename sizes over all\nhistory (due to needing enough to get statistics) while just grabbing\nregular file sizes just in the end tree?), but I think it provides\npretty good first order approximation suggesting that mean/median\nsizes of files involved in rename detection will be similar to the\nmean/median sizes of other files within the relevant trees.\n\n> I don't think file size matters all _that_ much, though, as it has a\n> linear relationship to time spent. Whereas the number of entries is\n> quadratic. And of course the whole experiment is ball-parking in the\n> first place. We're looking for order-of-magnitude approximations, I'd\n> think.\n\nI agree that the number of entries is what's important; in fact,\nthat's why I think the median file size is more important than the\nmean file size:\n\nIn the case of the linux kernel, since the mean is 2.5x bigger than\nthe median file size...\n => diffcore-rename checks file sizes before comparing content\n => Files more than 2x different in size can't be more than 50% similar\n => Therefore, files of the mean size will not be compared to files\nof the median size (or less)\n => Therefore, we automatically know that files of mean size will not\nbe compared to more than half the files.\n\n> > * The feedback about the limit is better today than when we last changed\n> > the limits, and folks can configure a higher limit relatively easily.\n> > Many already have.\n>\n> I can't remember the last time I saw the limit kick in in practice, but\n> then I don't generally work with super-large repos (and my workflows\n> typically do not encourage merging across big segments of history).\n> Nor do I remember the topic coming up on the list after the last bump.\n> So maybe that means that people are happily bumping the limits\n> themselves via config.\n\nIt might also mean that you're missing more emails than you used to,\nor just forgot them. :-)\n\ne.g.:\nhttps://lore.kernel.org/git/20171129201154.192379-1-jonathantanmy@google.com/\nhttps://lore.kernel.org/git/20171113201600.24878-1-newren@gmail.com/\n\nBut I do certainly suspect it's come up less often than it would have before.\n\n> But I don't think that's really an argument against at least a moderate\n> bump. If it helps even a few people avoid having to learn about the\n> config, that's time saved. And it's a trivial code change on our end.\n\n:-)\n"},{"id":"429836","messageId":"60ecad0dadf2c_a68ed208e7@natae.notmuch","threadId":"56090","inReplyTo":"CABPp-BEdUmxXVCx=5pb0=LN-0YBtrEB-wngPC5vys6fjVctgaQ@mail.gmail.com","subject":"Re: [RFC] Bump {diff,merge}.renameLimit ?","fromName":"Felipe Contreras","fromEmail":"felipe.contreras@gmail.com","sentAt":"2021-07-12T20:58:53Z","receivedAt":"2021-07-12T20:59:00Z","isPatch":false,"sender":{"key":"felipe.contreras@gmail.com","avatar":"https://avatars.githubusercontent.com/u/8358?v=4"},"body":"Elijah Newren wrote:\n> On Mon, Jul 12, 2021 at 10:16 AM Jeff King wrote:\n\n> > > * I think the median file size is a better predictor of rename\n> > > performance than mean file size, and median file size is ~2.5x smaller\n> > > than the mean[18].\n> >\n> > There you might get hit with the quadratic-update thing again, though.\n> > The big files are more likely to be touched, so could be weighted more\n> > (though are they more likely to have been added/delete/renamed? Who\n> > knows).\n> \n> I'll agree that big files are more likely to be updated, but I don't\n> think renames are weighted towards bigger files. In fact, I wrote a\n> quick script to look at the sizes of all the renamed files in the\n> history of v2.6.25, and the mean (8034.1) and median (3866) of the\n> renamed files sizes in that history are comparable to the mean\n> (11150.3) and median (4198) of the files sizes in the v2.6.25 tree.\n> \n> I re-did the calculations using v5.5, and found that the mean\n> (12495.1) and median (3702) sizes of renames in all linux history up\n> to that point again were a bit less than the mean (13449.2) and median\n> (3860) file size of a file in the final v5.5 tree.\n> \n> Granted, this is a bit hand-wavy (what about creations or deletions?\n> Is there too much bias from the fact that I did rename sizes over all\n> history (due to needing enough to get statistics) while just grabbing\n> regular file sizes just in the end tree?), but I think it provides\n> pretty good first order approximation suggesting that mean/median\n> sizes of files involved in rename detection will be similar to the\n> mean/median sizes of other files within the relevant trees.\n> \n> > I don't think file size matters all _that_ much, though, as it has a\n> > linear relationship to time spent. Whereas the number of entries is\n> > quadratic. And of course the whole experiment is ball-parking in the\n> > first place. We're looking for order-of-magnitude approximations, I'd\n> > think.\n> \n> I agree that the number of entries is what's important; in fact,\n> that's why I think the median file size is more important than the\n> mean file size:\n\nThat is almost always the case (except in unskewed distributions where\nthe mean is equal to the median).\n\nAnother option instead of an opaque configuration like 'renamelimit'\n--which is almost entirely arbitrary for most users--would be to have\n'renamelevel'. A renamelevel of 5 would be the median, so that's already\nmore meaningul than any value of renamelimit.\n\nA renamelevel of 9 would be the equivalent of the 9th decile, so that\nwould catch 90% of renames.\n\nIf the distribution follows a Pareto distribution (which is often the\ncase), the formula to calculate the different deciles is trivial, but it\nwould also be possible to hard-code all the different levels.\n\n-- \nFelipe Contreras\n"},{"id":"429840","messageId":"YOy3Eo+NuODKDjXf@coredump.intra.peff.net","threadId":"56090","inReplyTo":"CABPp-BEdUmxXVCx=5pb0=LN-0YBtrEB-wngPC5vys6fjVctgaQ@mail.gmail.com","subject":"Re: [RFC] Bump {diff,merge}.renameLimit ?","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2021-07-12T21:41:38Z","receivedAt":"2021-07-12T21:41:43Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Jul 12, 2021 at 01:23:38PM -0700, Elijah Newren wrote:\n\n> > > * The feedback about the limit is better today than when we last changed\n> > > the limits, and folks can configure a higher limit relatively easily.\n> > > Many already have.\n> >\n> > I can't remember the last time I saw the limit kick in in practice, but\n> > then I don't generally work with super-large repos (and my workflows\n> > typically do not encourage merging across big segments of history).\n> > Nor do I remember the topic coming up on the list after the last bump.\n> > So maybe that means that people are happily bumping the limits\n> > themselves via config.\n> \n> It might also mean that you're missing more emails than you used to,\n> or just forgot them. :-)\n> \n> e.g.:\n> https://lore.kernel.org/git/20171129201154.192379-1-jonathantanmy@google.com/\n> https://lore.kernel.org/git/20171113201600.24878-1-newren@gmail.com/\n> \n> But I do certainly suspect it's come up less often than it would have before.\n\nOh, indeed. Thanks for some counterexamples. :)\n\n-Peff\n"}]}