{"thread":{"id":"55774","subject":"time needed to rebase shortend by using --onto?","startedAt":"2021-05-26T10:09:39Z","lastAt":"2021-05-29T16:59:52Z","messageCount":12,"participants":["Uwe Kleine-König","Bagas Sanjaya","Elijah Newren","Junio C Hamano","Felipe Contreras"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"425558","messageId":"20210526100932.2hw4rbazgvd6mzff@pengutronix.de","threadId":"55774","inReplyTo":null,"subject":"time needed to rebase shortend by using --onto?","fromName":"Uwe Kleine-König","fromEmail":"u.kleine-koenig@pengutronix.de","sentAt":"2021-05-26T10:09:32Z","receivedAt":"2021-05-26T10:09:39Z","isPatch":false,"sender":{"key":"u.kleine-koenig@pengutronix.de","avatar":"https://gravatar.com/avatar/354b5e3ceb2806a2f1e1e382ac29ddbdad18288654da62b61eb13583a857eee7?d=mp&s=160"},"body":"Hello,\n\nI have a kernel topic branch containing 4 patches on top of Linux v5.4.\n(I didn't speak to the affected customer, so I cannot easily share the\npatch stack. If need be I can probably anonymize it or ask if I can\npublish the patches.)\n\nIt rebases clean on v5.10:\n\n\t$ time git rebase v5.10\n\tPerforming inexact rename detection: 100% (36806539/36806539), done.\n\tPerforming inexact rename detection: 100% (36806539/36806539), done.\n\tPerforming inexact rename detection: 100% (36806539/36806539), done.\n\tPerforming inexact rename detection: 100% (36806539/36806539), done.\n\tSuccessfully rebased and updated detached HEAD.\n\n\treal\t3m47.841s\n\tuser\t1m25.706s\n\tsys\t0m11.181s\n\nIf I start with the same rev checked out and explicitly specify the\nmerge base, the rebase process is considerably faster:\n\n\t$ time git rebase --onto v5.10 v5.4\n\tPerforming inexact rename detection: 100% (36806539/36806539), done.\n\tPerforming inexact rename detection: 100% (36806539/36806539), done.\n\tPerforming inexact rename detection: 100% (36806539/36806539), done.\n\tPerforming inexact rename detection: 100% (36806539/36806539), done.\n\tSuccessfully rebased and updated detached HEAD.\n\n\treal\t1m20.588s\n\tuser\t1m12.645s\n\tsys\t0m6.733s\n\nIs there some relevant complexity in the first invocation I'm not seeing\nthat explains it takes more than the double time? I would have expected\nthat\n\n\tgit rebase v5.10\n\ndoes the same as:\n\n\tgit rebase --onto v5.10 $(git merge-base HEAD v5.10)\n\n. (FTR:\n\n\t$ time git merge-base HEAD v5.10\n\t219d54332a09e8d8741c1e1982f5eae56099de85\n\n\treal\t0m0.158s\n\tuser\t0m0.105s\n\tsys\t0m0.052s\n\n, 219d5433 is v5.4 as expected.\n\n\t$ git version\n\tgit version 2.29.2\n\nThat's from the Debian package 1:2.29.2-1~bpo10+1 on a Debian 10 box.)\n\nBest regards\nUwe\n\n-- \nPengutronix e.K.                           | Uwe Kleine-König            |\nIndustrial Linux Solutions                 | https://www.pengutronix.de/ |\n"},{"id":"425561","messageId":"a37840c5-1103-6f38-555e-188878f50e36@gmail.com","threadId":"55774","inReplyTo":"20210526100932.2hw4rbazgvd6mzff@pengutronix.de","subject":"Re: time needed to rebase shortend by using --onto?","fromName":"Bagas Sanjaya","fromEmail":"bagasdotme@gmail.com","sentAt":"2021-05-26T11:04:25Z","receivedAt":"2021-05-26T11:04:37Z","isPatch":false,"sender":{"key":"bagasdotme@gmail.com","avatar":"https://avatars.githubusercontent.com/u/40219486?v=4"},"body":"Hi Uwe,\n\nOn 26/05/21 17.09, Uwe Kleine-König wrote:\n> Hello,\n> \n> I have a kernel topic branch containing 4 patches on top of Linux v5.4.\n> (I didn't speak to the affected customer, so I cannot easily share the\n> patch stack. If need be I can probably anonymize it or ask if I can\n> publish the patches.)\n> \n> It rebases clean on v5.10:\n> \n> \t$ time git rebase v5.10\n> \tPerforming inexact rename detection: 100% (36806539/36806539), done.\n> \tPerforming inexact rename detection: 100% (36806539/36806539), done.\n> \tPerforming inexact rename detection: 100% (36806539/36806539), done.\n> \tPerforming inexact rename detection: 100% (36806539/36806539), done.\n> \tSuccessfully rebased and updated detached HEAD.\n> \n> \treal\t3m47.841s\n> \tuser\t1m25.706s\n> \tsys\t0m11.181s\n> \n> If I start with the same rev checked out and explicitly specify the\n> merge base, the rebase process is considerably faster:\n> \n> \t$ time git rebase --onto v5.10 v5.4\n> \tPerforming inexact rename detection: 100% (36806539/36806539), done.\n> \tPerforming inexact rename detection: 100% (36806539/36806539), done.\n> \tPerforming inexact rename detection: 100% (36806539/36806539), done.\n> \tPerforming inexact rename detection: 100% (36806539/36806539), done.\n> \tSuccessfully rebased and updated detached HEAD.\n> \n> \treal\t1m20.588s\n> \tuser\t1m12.645s\n> \tsys\t0m6.733s\n> \n> Is there some relevant complexity in the first invocation I'm not seeing\n> that explains it takes more than the double time? I would have expected\n> that\n> \n> \tgit rebase v5.10\n> \n> does the same as:\n> \n> \tgit rebase --onto v5.10 $(git merge-base HEAD v5.10)\n> \n> . (FTR:\n> \n> \t$ time git merge-base HEAD v5.10\n> \t219d54332a09e8d8741c1e1982f5eae56099de85\n> \n> \treal\t0m0.158s\n> \tuser\t0m0.105s\n> \tsys\t0m0.052s\n> \n> , 219d5433 is v5.4 as expected.\n> \n> \t$ git version\n> \tgit version 2.29.2\n> \n> That's from the Debian package 1:2.29.2-1~bpo10+1 on a Debian 10 box.)\n> \n> Best regards\n> Uwe\n> \n\nCan you reproduce your findings with latest version (v2.32.0-rc1) please?\n\n-- \nAn old man doll... just what I always wanted! - Clara\n"},{"id":"425569","messageId":"CABPp-BGBY9kwqRQ+soa8=W2F+=8eQRYS3vWS_7UCC0K0qNTW1g@mail.gmail.com","threadId":"55774","inReplyTo":"20210526100932.2hw4rbazgvd6mzff@pengutronix.de","subject":"Re: time needed to rebase shortend by using --onto?","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-05-26T14:38:08Z","receivedAt":"2021-05-26T14:38:21Z","isPatch":false,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Wed, May 26, 2021 at 3:13 AM Uwe Kleine-König\n<u.kleine-koenig@pengutronix.de> wrote:\n>\n> Hello,\n>\n> I have a kernel topic branch containing 4 patches on top of Linux v5.4.\n> (I didn't speak to the affected customer, so I cannot easily share the\n> patch stack. If need be I can probably anonymize it or ask if I can\n> publish the patches.)\n>\n> It rebases clean on v5.10:\n>\n>         $ time git rebase v5.10\n>         Performing inexact rename detection: 100% (36806539/36806539), done.\n>         Performing inexact rename detection: 100% (36806539/36806539), done.\n>         Performing inexact rename detection: 100% (36806539/36806539), done.\n>         Performing inexact rename detection: 100% (36806539/36806539), done.\n>         Successfully rebased and updated detached HEAD.\n>\n>         real    3m47.841s\n>         user    1m25.706s\n>         sys     0m11.181s\n>\n> If I start with the same rev checked out and explicitly specify the\n> merge base, the rebase process is considerably faster:\n>\n>         $ time git rebase --onto v5.10 v5.4\n>         Performing inexact rename detection: 100% (36806539/36806539), done.\n>         Performing inexact rename detection: 100% (36806539/36806539), done.\n>         Performing inexact rename detection: 100% (36806539/36806539), done.\n>         Performing inexact rename detection: 100% (36806539/36806539), done.\n>         Successfully rebased and updated detached HEAD.\n>\n>         real    1m20.588s\n>         user    1m12.645s\n>         sys     0m6.733s\n>\n> Is there some relevant complexity in the first invocation I'm not seeing\n> that explains it takes more than the double time? I would have expected\n> that\n>\n>         git rebase v5.10\n>\n> does the same as:\n>\n>         git rebase --onto v5.10 $(git merge-base HEAD v5.10)\n>\n> . (FTR:\n>\n>         $ time git merge-base HEAD v5.10\n>         219d54332a09e8d8741c1e1982f5eae56099de85\n>\n>         real    0m0.158s\n>         user    0m0.105s\n>         sys     0m0.052s\n>\n> , 219d5433 is v5.4 as expected.\n\nThat does seem surprising, though if an automatic gc completed between\nthe two commands that could certainly explain it.  If that theory is\ncorrect, it would suggest that it'd be difficult for you to reproduce;\nrunning again with either command would give you something closer to\nthe lower time both times.  Is that the case?  (Also, what's the\noutput of \"git count-objects -v\"?)\n\n>\n>         $ git version\n>         git version 2.29.2\n>\n> That's from the Debian package 1:2.29.2-1~bpo10+1 on a Debian 10 box.)\n>\n> Best regards\n> Uwe\n\nI'd love to try this with git-2.32.0-rc1 (or even my not-yet-upstream\npatches that optimize even further) with adding \"--strategy=ort\" to\nyour rebase command to see how much of a timing difference it makes.\nAny chance the patches could either be published, or you could retry\nwith git-2.32.0-rc1 and add the --strategy=ort command line option to\nyour rebase command(s)?\n\nElijah\n"},{"id":"425589","messageId":"xmqqim35b0kz.fsf@gitster.g","threadId":"55774","inReplyTo":"20210526100932.2hw4rbazgvd6mzff@pengutronix.de","subject":"Re: time needed to rebase shortend by using --onto?","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2021-05-26T22:18:52Z","receivedAt":"2021-05-26T22:19:00Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Uwe Kleine-König <u.kleine-koenig@pengutronix.de> writes:\n\n> It rebases clean on v5.10:\n>\n> \t$ time git rebase v5.10\n> \tPerforming inexact rename detection: 100% (36806539/36806539), done.\n> \tPerforming inexact rename detection: 100% (36806539/36806539), done.\n> \tPerforming inexact rename detection: 100% (36806539/36806539), done.\n> \tPerforming inexact rename detection: 100% (36806539/36806539), done.\n> \tSuccessfully rebased and updated detached HEAD.\n>\n> \treal\t3m47.841s\n> \tuser\t1m25.706s\n> \tsys\t0m11.181s\n>\n> If I start with the same rev checked out and explicitly specify the\n> merge base, the rebase process is considerably faster:\n>\n> \t$ time git rebase --onto v5.10 v5.4\n> \tPerforming inexact rename detection: 100% (36806539/36806539), done.\n> \tPerforming inexact rename detection: 100% (36806539/36806539), done.\n> \tPerforming inexact rename detection: 100% (36806539/36806539), done.\n> \tPerforming inexact rename detection: 100% (36806539/36806539), done.\n> \tSuccessfully rebased and updated detached HEAD.\n>\n> \treal\t1m20.588s\n> \tuser\t1m12.645s\n> \tsys\t0m6.733s\n>\n> Is there some relevant complexity in the first invocation I'm not seeing\n> that explains it takes more than the double time? I would have expected\n> that\n>\n> \tgit rebase v5.10\n>\n> does the same as:\n>\n> \tgit rebase --onto v5.10 $(git merge-base HEAD v5.10)\n\nThere is a voodoo called fork-point detection that walks back the\nreflogs and repeatedly computes merge bases, and giving --onto to\nexplicitly give a commit on which the history is transplanted should\nremove the need to do the computation, so that is a possibility.\n\nBut according to the manpage, it should not kick in for invocations\nin the above example that specify the <upstream> (the\nrebase.forkpoint configuration variable can clobber this default).\n"},{"id":"425711","messageId":"20210527215947.g2mnds6zj5uv5mjq@pengutronix.de","threadId":"55774","inReplyTo":"CABPp-BGBY9kwqRQ+soa8=W2F+=8eQRYS3vWS_7UCC0K0qNTW1g@mail.gmail.com","subject":"Re: time needed to rebase shortend by using --onto?","fromName":"Uwe Kleine-König","fromEmail":"u.kleine-koenig@pengutronix.de","sentAt":"2021-05-27T21:59:47Z","receivedAt":"2021-05-27T21:59:55Z","isPatch":false,"sender":{"key":"u.kleine-koenig@pengutronix.de","avatar":"https://gravatar.com/avatar/354b5e3ceb2806a2f1e1e382ac29ddbdad18288654da62b61eb13583a857eee7?d=mp&s=160"},"body":"Hello,\n\nOn Wed, May 26, 2021 at 07:38:08AM -0700, Elijah Newren wrote:\n> On Wed, May 26, 2021 at 3:13 AM Uwe Kleine-König\n> <u.kleine-koenig@pengutronix.de> wrote:\n> > I have a kernel topic branch containing 4 patches on top of Linux v5.4.\n> > (I didn't speak to the affected customer, so I cannot easily share the\n> > patch stack. If need be I can probably anonymize it or ask if I can\n> > publish the patches.)\n> >\n> > It rebases clean on v5.10:\n> >\n> >         $ time git rebase v5.10\n> >         Performing inexact rename detection: 100% (36806539/36806539), done.\n> >         Performing inexact rename detection: 100% (36806539/36806539), done.\n> >         Performing inexact rename detection: 100% (36806539/36806539), done.\n> >         Performing inexact rename detection: 100% (36806539/36806539), done.\n> >         Successfully rebased and updated detached HEAD.\n> >\n> >         real    3m47.841s\n> >         user    1m25.706s\n> >         sys     0m11.181s\n> >\n> > If I start with the same rev checked out and explicitly specify the\n> > merge base, the rebase process is considerably faster:\n> >\n> >         $ time git rebase --onto v5.10 v5.4\n> >         Performing inexact rename detection: 100% (36806539/36806539), done.\n> >         Performing inexact rename detection: 100% (36806539/36806539), done.\n> >         Performing inexact rename detection: 100% (36806539/36806539), done.\n> >         Performing inexact rename detection: 100% (36806539/36806539), done.\n> >         Successfully rebased and updated detached HEAD.\n> >\n> >         real    1m20.588s\n> >         user    1m12.645s\n> >         sys     0m6.733s\n> >\n> > Is there some relevant complexity in the first invocation I'm not seeing\n> > that explains it takes more than the double time? I would have expected\n> > that\n> >\n> >         git rebase v5.10\n> >\n> > does the same as:\n> >\n> >         git rebase --onto v5.10 $(git merge-base HEAD v5.10)\n> >\n> > . (FTR:\n> >\n> >         $ time git merge-base HEAD v5.10\n> >         219d54332a09e8d8741c1e1982f5eae56099de85\n> >\n> >         real    0m0.158s\n> >         user    0m0.105s\n> >         sys     0m0.052s\n> >\n> > , 219d5433 is v5.4 as expected.\n> \n> That does seem surprising, though if an automatic gc completed between\n> the two commands that could certainly explain it.  If that theory is\n> correct, it would suggest that it'd be difficult for you to reproduce;\n\nThis reproduces just fine. The repository is quite big and it is slow at\ntimes. With the same tree on a different machine, the rebase is quicker,\nbut the factor 2 between the two different commands is visible there,\ntoo:\n\nuwe@taurus:~/gsrc/linux$ git checkout bc2e99c9c9e0d29494b1739624554e4f5f979d32\nHEAD is now at bc2e99c9c9e0 [...]\n\nuwe@taurus:~/gsrc/linux$ time git rebase v5.10\nwarning: inexact rename detection was skipped due to too many files.\nwarning: you may want to set your merge.renamelimit variable to at least 8604 and retry the command.\nwarning: inexact rename detection was skipped due to too many files.\nwarning: you may want to set your merge.renamelimit variable to at least 8604 and retry the command.\nwarning: inexact rename detection was skipped due to too many files.\nwarning: you may want to set your merge.renamelimit variable to at least 8604 and retry the command.\nwarning: inexact rename detection was skipped due to too many files.\nwarning: you may want to set your merge.renamelimit variable to at least 8604 and retry the command.\nSuccessfully rebased and updated detached HEAD.\n\nreal\t0m20.737s\nuser\t0m14.188s\nsys\t0m3.767s\n\nuwe@taurus:~/gsrc/linux$ git checkout bc2e99c9c9e0d29494b1739624554e4f5f979d32\nHEAD is now at bc2e99c9c9e0 [...]\n\nuwe@taurus:~/gsrc/linux$ time git rebase --onto v5.10 v5.4\nwarning: inexact rename detection was skipped due to too many files.\nwarning: you may want to set your merge.renamelimit variable to at least 8604 and retry the command.\nwarning: inexact rename detection was skipped due to too many files.\nwarning: you may want to set your merge.renamelimit variable to at least 8604 and retry the command.\nwarning: inexact rename detection was skipped due to too many files.\nwarning: you may want to set your merge.renamelimit variable to at least 8604 and retry the command.\nwarning: inexact rename detection was skipped due to too many files.\nwarning: you may want to set your merge.renamelimit variable to at least 8604 and retry the command.\nSuccessfully rebased and updated detached HEAD.\n\nreal\t0m12.129s\nuser\t0m7.196s\nsys\t0m3.141s\n\n(This is with a slightly newer git: 2.30.2-1 from Debian)\n\nThen I repeated the test with git 2.32.0-rc1 (wgit is just calling\nbin-wrappers/git in my git working copy):\n\nuwe@taurus:~/gsrc/linux$ wgit version\ngit version 2.32.0.rc1\n\nuwe@taurus:~/gsrc/linux$ wgit checkout bc2e99c9c9e0d29494b1739624554e4f5f979d32\nHEAD is now at bc2e99c9c9e0 [...]\n\nuwe@taurus:~/gsrc/linux$ time wgit rebase v5.10\nwarning: inexact rename detection was skipped due to too many files.\nwarning: you may want to set your merge.renamelimit variable to at least 8024 and retry the command.\nwarning: inexact rename detection was skipped due to too many files.\nwarning: you may want to set your merge.renamelimit variable to at least 8024 and retry the command.\nwarning: inexact rename detection was skipped due to too many files.\nwarning: you may want to set your merge.renamelimit variable to at least 8024 and retry the command.\nwarning: inexact rename detection was skipped due to too many files.\nwarning: you may want to set your merge.renamelimit variable to at least 8024 and retry the command.\nSuccessfully rebased and updated detached HEAD.\n\nreal\t0m19.438s\nuser\t0m13.629s\nsys\t0m3.299s\n\nuwe@taurus:~/gsrc/linux$ wgit checkout bc2e99c9c9e0d29494b1739624554e4f5f979d32\nHEAD is now at bc2e99c9c9e0 [...]\n\nuwe@taurus:~/gsrc/linux$ time wgit rebase --onto v5.10 v5.4\nwarning: inexact rename detection was skipped due to too many files.\nwarning: you may want to set your merge.renamelimit variable to at least 8024 and retry the command.\nwarning: inexact rename detection was skipped due to too many files.\nwarning: you may want to set your merge.renamelimit variable to at least 8024 and retry the command.\nwarning: inexact rename detection was skipped due to too many files.\nwarning: you may want to set your merge.renamelimit variable to at least 8024 and retry the command.\nwarning: inexact rename detection was skipped due to too many files.\nwarning: you may want to set your merge.renamelimit variable to at least 8024 and retry the command.\nSuccessfully rebased and updated detached HEAD.\n\nreal\t0m13.848s\nuser\t0m8.315s\nsys\t0m3.182s\n\nSo the surprise persists.\n\n> running again with either command would give you something closer to\n> the lower time both times.  Is that the case?  (Also, what's the\n> output of \"git count-objects -v\"?)\n\nAfter the above commands I have:\n\n\tcount: 3203\n\tsize: 17664\n\tin-pack: 4763753\n\tpacks: 11\n\tsize-pack: 1273957\n\tprune-packable: 19\n\tgarbage: 0\n\tsize-garbage: 0\n\talternate: /home/uwe/var/gitstore/linux.git/objects\n\n(On the repository I did this initially I have:\n\n\twarning: garbage found: .git/objects/pack/pack-864148a84c0524073ed8c8aa1a76155d5c677879.pack.temp\n\twarning: garbage found: /ptx/src/git/linux.git/objects/pack/tmp_pack_X9gHnq\n\tcount: 2652\n\tsize: 14640\n\tin-pack: 2117015\n\tpacks: 8\n\tsize-pack: 574167\n\tprune-packable: 856\n\tgarbage: 2\n\tsize-garbage: 1114236\n\talternate: /ptx/src/git/linux.git/objects\n\n(Is the garbage a reason this is so slow? Can I just remove the two\nfiles pointed out?)\n\n> I'd love to try this with git-2.32.0-rc1 (or even my not-yet-upstream\n> patches that optimize even further) with adding \"--strategy=ort\" to\n> your rebase command to see how much of a timing difference it makes.\n> Any chance the patches could either be published, or you could retry\n> with git-2.32.0-rc1 and add the --strategy=ort command line option to\n> your rebase command(s)?\n\nWith --strategy=ort added I have:\n\nuwe@taurus:~/gsrc/linux$ time wgit rebase --strategy=ort v5.10\nSuccessfully rebased and updated detached HEAD.\n\nreal\t0m19.202s\nuser\t0m12.724s\nsys\t0m2.961s\n\n[...]\n\nuwe@taurus:~/gsrc/linux$ time wgit rebase --strategy=ort --onto v5.10 v5.4\nSuccessfully rebased and updated detached HEAD.\n\nreal\t0m12.395s\nuser\t0m6.638s\nsys\t0m3.284s\n\nSo the warnings about inexact rename detection don't appear and it's a\nbit faster, but I still see the timing difference between these two\ncommands.\n\nI assume you are still interested in seeing this branch? I think\nanonymising it shouldn't be so hard, the patches are not so big. I'll\nmodify the branch to make it shareable and assuming the problem still\nreproduces with it will share it with you.\n\nBest regards\nUwe\n\n-- \nPengutronix e.K.                           | Uwe Kleine-König            |\nIndustrial Linux Solutions                 | https://www.pengutronix.de/ |\n"},{"id":"425713","messageId":"20210527221501.rqw3sr6dzrddh7oe@pengutronix.de","threadId":"55774","inReplyTo":"20210527215947.g2mnds6zj5uv5mjq@pengutronix.de","subject":"Re: time needed to rebase shortend by using --onto?","fromName":"Uwe Kleine-König","fromEmail":"u.kleine-koenig@pengutronix.de","sentAt":"2021-05-27T22:15:01Z","receivedAt":"2021-05-27T22:15:04Z","isPatch":false,"sender":{"key":"u.kleine-koenig@pengutronix.de","avatar":"https://gravatar.com/avatar/354b5e3ceb2806a2f1e1e382ac29ddbdad18288654da62b61eb13583a857eee7?d=mp&s=160"},"body":"On Thu, May 27, 2021 at 11:59:47PM +0200, Uwe Kleine-König wrote:\n> I assume you are still interested in seeing this branch? I think\n> anonymising it shouldn't be so hard, the patches are not so big. I'll\n> modify the branch to make it shareable and assuming the problem still\n> reproduces with it will share it with you.\n\nYou can find the anonymised branch at:\n\n\thttps://git.pengutronix.de/git/ukl/linux rebase-timing\n\nBest regards\nUwe\n\n-- \nPengutronix e.K.                           | Uwe Kleine-König            |\nIndustrial Linux Solutions                 | https://www.pengutronix.de/ |\n"},{"id":"425714","messageId":"20210527221609.khkcmohmtfliykla@pengutronix.de","threadId":"55774","inReplyTo":"xmqqim35b0kz.fsf@gitster.g","subject":"Re: time needed to rebase shortend by using --onto?","fromName":"Uwe Kleine-König","fromEmail":"u.kleine-koenig@pengutronix.de","sentAt":"2021-05-27T22:16:09Z","receivedAt":"2021-05-27T22:16:16Z","isPatch":false,"sender":{"key":"u.kleine-koenig@pengutronix.de","avatar":"https://gravatar.com/avatar/354b5e3ceb2806a2f1e1e382ac29ddbdad18288654da62b61eb13583a857eee7?d=mp&s=160"},"body":"Hello Junio,\n\nOn Thu, May 27, 2021 at 07:18:52AM +0900, Junio C Hamano wrote:\n> Uwe Kleine-König <u.kleine-koenig@pengutronix.de> writes:\n> \n> > It rebases clean on v5.10:\n> >\n> > \t$ time git rebase v5.10\n> > \tPerforming inexact rename detection: 100% (36806539/36806539), done.\n> > \tPerforming inexact rename detection: 100% (36806539/36806539), done.\n> > \tPerforming inexact rename detection: 100% (36806539/36806539), done.\n> > \tPerforming inexact rename detection: 100% (36806539/36806539), done.\n> > \tSuccessfully rebased and updated detached HEAD.\n> >\n> > \treal\t3m47.841s\n> > \tuser\t1m25.706s\n> > \tsys\t0m11.181s\n> >\n> > If I start with the same rev checked out and explicitly specify the\n> > merge base, the rebase process is considerably faster:\n> >\n> > \t$ time git rebase --onto v5.10 v5.4\n> > \tPerforming inexact rename detection: 100% (36806539/36806539), done.\n> > \tPerforming inexact rename detection: 100% (36806539/36806539), done.\n> > \tPerforming inexact rename detection: 100% (36806539/36806539), done.\n> > \tPerforming inexact rename detection: 100% (36806539/36806539), done.\n> > \tSuccessfully rebased and updated detached HEAD.\n> >\n> > \treal\t1m20.588s\n> > \tuser\t1m12.645s\n> > \tsys\t0m6.733s\n> >\n> > Is there some relevant complexity in the first invocation I'm not seeing\n> > that explains it takes more than the double time? I would have expected\n> > that\n> >\n> > \tgit rebase v5.10\n> >\n> > does the same as:\n> >\n> > \tgit rebase --onto v5.10 $(git merge-base HEAD v5.10)\n> \n> There is a voodoo called fork-point detection that walks back the\n> reflogs and repeatedly computes merge bases, and giving --onto to\n> explicitly give a commit on which the history is transplanted should\n> remove the need to do the computation, so that is a possibility.\n> \n> But according to the manpage, it should not kick in for invocations\n> in the above example that specify the <upstream> (the\n> rebase.forkpoint configuration variable can clobber this default).\n\nFTR: I don't have this variable set in the two repositories that show\nthe different timings.\n\nBest regards\nUwe\n\n-- \nPengutronix e.K.                           | Uwe Kleine-König            |\nIndustrial Linux Solutions                 | https://www.pengutronix.de/ |\n"},{"id":"425717","messageId":"CABPp-BEVME5Gx=F4HWHBb_0wn6XJF==DzVLo2i1xj63BB+_jtw@mail.gmail.com","threadId":"55774","inReplyTo":"20210527215947.g2mnds6zj5uv5mjq@pengutronix.de","subject":"Re: time needed to rebase shortend by using --onto?","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-05-27T23:08:32Z","receivedAt":"2021-05-27T23:08:46Z","isPatch":false,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Thu, May 27, 2021 at 2:59 PM Uwe Kleine-König\n<u.kleine-koenig@pengutronix.de> wrote:\n>\n> Hello,\n>\n> On Wed, May 26, 2021 at 07:38:08AM -0700, Elijah Newren wrote:\n> > On Wed, May 26, 2021 at 3:13 AM Uwe Kleine-König\n> > <u.kleine-koenig@pengutronix.de> wrote:\n> > > I have a kernel topic branch containing 4 patches on top of Linux v5.4.\n> > > (I didn't speak to the affected customer, so I cannot easily share the\n> > > patch stack. If need be I can probably anonymize it or ask if I can\n> > > publish the patches.)\n> > >\n> > > It rebases clean on v5.10:\n> > >\n> > >         $ time git rebase v5.10\n> > >         Performing inexact rename detection: 100% (36806539/36806539), done.\n> > >         Performing inexact rename detection: 100% (36806539/36806539), done.\n> > >         Performing inexact rename detection: 100% (36806539/36806539), done.\n> > >         Performing inexact rename detection: 100% (36806539/36806539), done.\n> > >         Successfully rebased and updated detached HEAD.\n> > >\n> > >         real    3m47.841s\n> > >         user    1m25.706s\n> > >         sys     0m11.181s\n> > >\n> > > If I start with the same rev checked out and explicitly specify the\n> > > merge base, the rebase process is considerably faster:\n> > >\n> > >         $ time git rebase --onto v5.10 v5.4\n> > >         Performing inexact rename detection: 100% (36806539/36806539), done.\n> > >         Performing inexact rename detection: 100% (36806539/36806539), done.\n> > >         Performing inexact rename detection: 100% (36806539/36806539), done.\n> > >         Performing inexact rename detection: 100% (36806539/36806539), done.\n> > >         Successfully rebased and updated detached HEAD.\n> > >\n> > >         real    1m20.588s\n> > >         user    1m12.645s\n> > >         sys     0m6.733s\n\nNote: In your original report you had rename detection and it clearly\ntook a significant amount of time...\n\n> > >\n> > > Is there some relevant complexity in the first invocation I'm not seeing\n> > > that explains it takes more than the double time? I would have expected\n> > > that\n> > >\n> > >         git rebase v5.10\n> > >\n> > > does the same as:\n> > >\n> > >         git rebase --onto v5.10 $(git merge-base HEAD v5.10)\n> > >\n> > > . (FTR:\n> > >\n> > >         $ time git merge-base HEAD v5.10\n> > >         219d54332a09e8d8741c1e1982f5eae56099de85\n> > >\n> > >         real    0m0.158s\n> > >         user    0m0.105s\n> > >         sys     0m0.052s\n> > >\n> > > , 219d5433 is v5.4 as expected.\n> >\n> > That does seem surprising, though if an automatic gc completed between\n> > the two commands that could certainly explain it.  If that theory is\n> > correct, it would suggest that it'd be difficult for you to reproduce;\n>\n> This reproduces just fine. The repository is quite big and it is slow at\n> times. With the same tree on a different machine, the rebase is quicker,\n> but the factor 2 between the two different commands is visible there,\n> too:\n>\n> uwe@taurus:~/gsrc/linux$ git checkout bc2e99c9c9e0d29494b1739624554e4f5f979d32\n> HEAD is now at bc2e99c9c9e0 [...]\n>\n> uwe@taurus:~/gsrc/linux$ time git rebase v5.10\n> warning: inexact rename detection was skipped due to too many files.\n> warning: you may want to set your merge.renamelimit variable to at least 8604 and retry the command.\n> warning: inexact rename detection was skipped due to too many files.\n> warning: you may want to set your merge.renamelimit variable to at least 8604 and retry the command.\n> warning: inexact rename detection was skipped due to too many files.\n> warning: you may want to set your merge.renamelimit variable to at least 8604 and retry the command.\n> warning: inexact rename detection was skipped due to too many files.\n> warning: you may want to set your merge.renamelimit variable to at least 8604 and retry the command.\n> Successfully rebased and updated detached HEAD.\n>\n> real    0m20.737s\n> user    0m14.188s\n> sys     0m3.767s\n>\n> uwe@taurus:~/gsrc/linux$ git checkout bc2e99c9c9e0d29494b1739624554e4f5f979d32\n> HEAD is now at bc2e99c9c9e0 [...]\n>\n> uwe@taurus:~/gsrc/linux$ time git rebase --onto v5.10 v5.4\n> warning: inexact rename detection was skipped due to too many files.\n> warning: you may want to set your merge.renamelimit variable to at least 8604 and retry the command.\n> warning: inexact rename detection was skipped due to too many files.\n> warning: you may want to set your merge.renamelimit variable to at least 8604 and retry the command.\n> warning: inexact rename detection was skipped due to too many files.\n> warning: you may want to set your merge.renamelimit variable to at least 8604 and retry the command.\n> warning: inexact rename detection was skipped due to too many files.\n> warning: you may want to set your merge.renamelimit variable to at least 8604 and retry the command.\n> Successfully rebased and updated detached HEAD.\n>\n> real    0m12.129s\n> user    0m7.196s\n> sys     0m3.141s\n>\n> (This is with a slightly newer git: 2.30.2-1 from Debian)\n\nAnd here, there was no rename detection so this isn't the same thing\nanymore.  You could try setting merge.renameLimit higher.\n\nHowever, the 7-8 second difference (and the likely large differences\nbetween 5.4 and 5.10) do suggest that Junio's hunch that fork-point\nbehavior being at play could be an issue in these two commands.\n\n> Then I repeated the test with git 2.32.0-rc1 (wgit is just calling\n> bin-wrappers/git in my git working copy):\n>\n> uwe@taurus:~/gsrc/linux$ wgit version\n> git version 2.32.0.rc1\n>\n> uwe@taurus:~/gsrc/linux$ wgit checkout bc2e99c9c9e0d29494b1739624554e4f5f979d32\n> HEAD is now at bc2e99c9c9e0 [...]\n>\n> uwe@taurus:~/gsrc/linux$ time wgit rebase v5.10\n> warning: inexact rename detection was skipped due to too many files.\n> warning: you may want to set your merge.renamelimit variable to at least 8024 and retry the command.\n> warning: inexact rename detection was skipped due to too many files.\n> warning: you may want to set your merge.renamelimit variable to at least 8024 and retry the command.\n> warning: inexact rename detection was skipped due to too many files.\n> warning: you may want to set your merge.renamelimit variable to at least 8024 and retry the command.\n> warning: inexact rename detection was skipped due to too many files.\n> warning: you may want to set your merge.renamelimit variable to at least 8024 and retry the command.\n> Successfully rebased and updated detached HEAD.\n>\n> real    0m19.438s\n> user    0m13.629s\n> sys     0m3.299s\n>\n> uwe@taurus:~/gsrc/linux$ wgit checkout bc2e99c9c9e0d29494b1739624554e4f5f979d32\n> HEAD is now at bc2e99c9c9e0 [...]\n>\n> uwe@taurus:~/gsrc/linux$ time wgit rebase --onto v5.10 v5.4\n> warning: inexact rename detection was skipped due to too many files.\n> warning: you may want to set your merge.renamelimit variable to at least 8024 and retry the command.\n> warning: inexact rename detection was skipped due to too many files.\n> warning: you may want to set your merge.renamelimit variable to at least 8024 and retry the command.\n> warning: inexact rename detection was skipped due to too many files.\n> warning: you may want to set your merge.renamelimit variable to at least 8024 and retry the command.\n> warning: inexact rename detection was skipped due to too many files.\n> warning: you may want to set your merge.renamelimit variable to at least 8024 and retry the command.\n> Successfully rebased and updated detached HEAD.\n>\n> real    0m13.848s\n> user    0m8.315s\n> sys     0m3.182s\n>\n> So the surprise persists.\n\nYeah, with no rename detection, the newer git version isn't going to\nmake a bit of difference.\n\n> > running again with either command would give you something closer to\n> > the lower time both times.  Is that the case?  (Also, what's the\n> > output of \"git count-objects -v\"?)\n>\n> After the above commands I have:\n>\n>         count: 3203\n>         size: 17664\n>         in-pack: 4763753\n>         packs: 11\n>         size-pack: 1273957\n>         prune-packable: 19\n>         garbage: 0\n>         size-garbage: 0\n\nSo, not freshly packed, but not in need of an automatic gc either.\n\n>         alternate: /home/uwe/var/gitstore/linux.git/objects\n\nYou've got an alternate?  How well packed is it?  (What does \"git\ncount-objects -v\" in that other repo show?)\n\n>\n> (On the repository I did this initially I have:\n>\n>         warning: garbage found: .git/objects/pack/pack-864148a84c0524073ed8c8aa1a76155d5c677879.pack.temp\n>         warning: garbage found: /ptx/src/git/linux.git/objects/pack/tmp_pack_X9gHnq\n>         count: 2652\n>         size: 14640\n>         in-pack: 2117015\n>         packs: 8\n>         size-pack: 574167\n>         prune-packable: 856\n>         garbage: 2\n>         size-garbage: 1114236\n>         alternate: /ptx/src/git/linux.git/objects\n>\n> (Is the garbage a reason this is so slow? Can I just remove the two\n> files pointed out?)\n\nIf there isn't some still-running git operation that is fetching and\nwriting to these files, then yes they can be cleaned out.  I doubt\nthey'd make too much of a difference, though.  I was more curious if\nyou went from say 10000 loose objects to ~0, or from 50+ packs down to\n1 between operations due to an automatic gc completing.\n\n> > I'd love to try this with git-2.32.0-rc1 (or even my not-yet-upstream\n> > patches that optimize even further) with adding \"--strategy=ort\" to\n> > your rebase command to see how much of a timing difference it makes.\n> > Any chance the patches could either be published, or you could retry\n> > with git-2.32.0-rc1 and add the --strategy=ort command line option to\n> > your rebase command(s)?\n>\n> With --strategy=ort added I have:\n>\n> uwe@taurus:~/gsrc/linux$ time wgit rebase --strategy=ort v5.10\n> Successfully rebased and updated detached HEAD.\n>\n> real    0m19.202s\n> user    0m12.724s\n> sys     0m2.961s\n>\n> [...]\n>\n> uwe@taurus:~/gsrc/linux$ time wgit rebase --strategy=ort --onto v5.10 v5.4\n> Successfully rebased and updated detached HEAD.\n>\n> real    0m12.395s\n> user    0m6.638s\n> sys     0m3.284s\n>\n> So the warnings about inexact rename detection don't appear and it's a\n> bit faster, but I still see the timing difference between these two\n> commands.\n\nRight, this says that --strategy=ort WITH rename detection is as fast\nas the default --strategy=recursive WITHOUT rename detection.\n\nIt's not a fair comparison (you'd need to set merge.renameLimit higher\nand re-run the cases where you had warnings), but is interesting\nnonetheless.  It basically suggests that rename detection comes for\nfree with the ort strategy.\n\n> I assume you are still interested in seeing this branch? I think\n> anonymising it shouldn't be so hard, the patches are not so big. I'll\n> modify the branch to make it shareable and assuming the problem still\n> reproduces with it will share it with you.\n\nThanks.\n"},{"id":"425739","messageId":"CABPp-BE48=97k_3tnNqXPjSEfA163F8hoE+HY0Zvz1SWB2B8EA@mail.gmail.com","threadId":"55774","inReplyTo":"20210527221501.rqw3sr6dzrddh7oe@pengutronix.de","subject":"Re: time needed to rebase shortend by using --onto?","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-05-28T05:38:15Z","receivedAt":"2021-05-28T05:39:09Z","isPatch":false,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Thu, May 27, 2021 at 3:15 PM Uwe Kleine-König\n<u.kleine-koenig@pengutronix.de> wrote:\n>\n> On Thu, May 27, 2021 at 11:59:47PM +0200, Uwe Kleine-König wrote:\n> > I assume you are still interested in seeing this branch? I think\n> > anonymising it shouldn't be so hard, the patches are not so big. I'll\n> > modify the branch to make it shareable and assuming the problem still\n> > reproduces with it will share it with you.\n>\n> You can find the anonymised branch at:\n>\n>         https://git.pengutronix.de/git/ukl/linux rebase-timing\n\nCool, this helps.  Short summary:\n\n* I can't reproduce your factor 2 timing difference when rename\ndetection is active.  There still have to be other factors at play\n(e.g. auto-gc).  Can you reproduce those?\n* Your timing of merge-base was likely mistaken, due to where HEAD\npointed (see below).\n* Without --onto, it looks like a huge chunk of time is spent checking\nwhether any of the 4 patches happen to match one of the patches in\nv5.4..v5.10; passing --reapply-cherry-picks will save that time (that\nreally ought to be the default IMO, but backward compatibility makes\nthat impossible).\n* Adding --no-fork-point may have also sped up the timing for your\noriginal report (not your follow-up), depending on what's in your\nlocal reflog.\n* There are almost certainly other optimization opportunities available here.\n\nMore detailed investigation:\n\nYou did a few things that were quite a bit different between your\noriginal report and your follow-up about reproducing.  So I'll try to\nbe clear about what I tried with your repository, but first let me\npoint out possible points of confusion:\n\n1) In the original report, you clearly had merge.renamelimit set high\nenough to detect renames, whereas in the second you didn't.  I can\ncontrol for this and show both with and without having a high enough\nlimit.\n2) It appears in the first report that you were likely on a branch\nwhen you ran rebase, whereas in the second you were clearly using a\ndetached HEAD (by first checking out a specific commit).  Since you\ndidn't use --no-fork-point, your local reflog would be consulted and\nthe history of changes to the branch might add to the overall\ncomputation time.  That's something I won't be able to reproduce since\nI don't have your reflog.\n3) It's hard for me to shake that there might have been an automatic\ngc or something else running on the system that occurred between the\nfirst and second runs of your original report.  I obviously can't\nreproduce anything like that.\n4) The timing of the \"git merge-base HEAD v5.10\" command you ran was\nalmost certainly done AFTER the rebase, which gives misleading\nresults.  When I run the same command AFTER rebasing, I see similarly\nreally low timings:\n$ time git merge-base HEAD v5.10\n2c85ebc57b3e1817b6ce1a6b703928e113a90442\n\nreal 0m0.004s\n\nWhereas BEFORE rebasing, I see significantly bigger times\n\n$ time git merge-base HEAD v5.10\n219d54332a09e8d8741c1e1982f5eae56099de85\n\nreal 0m1.750s\n\nIt would have been clearer to just use the command \"time git\nmerge-base v5.10 origin/rebase-timing\" (or whatever the original\nun-rebased branch was instead of using HEAD).\n\n\n\n\nOkay, with all that out of the way, I cloned your repo and ran a bunch\nof timings.  I first ran:\n    $ git config merge.renamelimit 9999\nto make sure renames are detected.  I'll override it below when I\ndon't want renames detected.\n\nWith this config, on my machine, using git v2.32.0-rc1:\n    53.908s  git rebase v5.10\n    47.668s  git rebase --onto v5.10 v5.4\n\n    18.574s  git -c merge.renamelimit=1000 rebase v5.10\n    11.800s  git -c merge.renamelimit=1000 rebase --onto v5.10 v5.4\n\n    16.610s  git rebase -sort v5.10\n    10.780s  git rebase -sort --onto v5.10 v5.4\n\n    10.670s  git rebase -sort --reapply-cherry-picks v5.10\n    10.589s  git rebase -sort --reapply-cherry-picks --onto v5.10 v5.4\n\nUsing my development version of git (has a few more optimizations):\n    16.073s  git rebase -sort v5.10\n     9.778s  git rebase -sort --onto v5.10 v5.4\n\n     9.541s  git rebase -sort --reapply-cherry-picks v5.10\n     9.062s  git rebase -sort --reapply-cherry-picks --onto v5.10 v5.4\n\nUsing my development version + replacing can_fast_forward() with \"return 0\":\n     9.221s  git rebase -sort --reapply-cherry-picks v5.10\n     8.124s  git rebase -sort --reapply-cherry-picks --onto v5.10 v5.4\n\nNote the following timings too (git version doesn't really matter):\n    6.495s  git switch --quiet --detach v5.10\n    1.741s  git merge-base v5.10 origin/rebase-timing\n\nSo a theoretical lower bound is somewhere around 6.5s with --onto, and\n8s without it, since these operations are just necessary.  fast-rebase\ngets really close to that theoretical lower bound; it involves running\nall three of the following commands (because it won't do the checkout\nfor you and needs a branch name):\n    6.495s  git switch --quiet --detach v5.10\n    0.005s  git branch -f rebase-timing origin/rebase-timing\n    0.176s  test-tool fast-rebase --onto HEAD v5.4 rebase-timing\nfor a combined time of 6.676s.\n\nGoing back to the real rebase command, though (with my\nstill-not-upstream git version), using trace2 and summing across\ncommon region names, I saw the following timings:\n\n$ git switch --quiet --detach origin/rebase-timing && summarize-perf\ngit rebase -sort --reapply-cherry-picks v5.10\nSuccessfully rebased and updated detached HEAD.\nAccumulated times:\n    2.104 : <unmeasured> (21.3%)\n    6.628 : 7 : label:unpack_trees\n       6.354 : <unmeasured> (95.9%)\n       0.192 : 7 : ..label:traverse_trees\n       0.082 : 1 : ..label:update\n       0.000 : 1 : ..label:Filtering content\n    0.515 : 4 : label:refresh\n    0.380 : 6 : label:do_write_index\n/home/newren/floss/uwe-linux/.git/index.lock\n       0.375 : <unmeasured> (98.7%)\n       0.005 : 6 : ..label:write\n    0.103 : 4 : label:preload\n    0.081 : 4 : label:checkout\n       0.000 : <unmeasured> ( 0.2%)\n       0.081 : 4 : ..label:unpack_trees\n          0.014 : <unmeasured> (17.7%)\n          0.065 : 4 : ....label:traverse_trees\n          0.002 : 4 : ....label:update\n          0.000 : 4 : ....label:Filtering content\n    0.069 : 7 : label:do_read_index .git/index\n       0.060 : <unmeasured> (88.0%)\n       0.008 : 7 : ..label:read\n    0.011 : 4 : label:incore_nonrecursive\n       0.000 : <unmeasured> ( 2.8%)\n       0.009 : 4 : ..label:process_entries\n          0.000 : <unmeasured> ( 1.3%)\n          0.008 : 4 : ....label:processing\n          0.000 : 4 : ....label:process_entries setup\n             0.000 : <unmeasured> (21.9%)\n             0.000 : 4 : ......label:plist special sort\n             0.000 : 4 : ......label:plist copy\n             0.000 : 4 : ......label:plist grow\n          0.000 : 4 : ....label:process_entries cleanup\n       0.002 : 4 : ..label:collect_merge_info\n          0.000 : <unmeasured> ( 6.5%)\n          0.002 : 4 : ....label:traverse_trees\n       0.000 : 4 : ..label:merge_start\n          0.000 : <unmeasured> (54.4%)\n          0.000 : 4 : ....label:allocate/init\n          0.000 : 4 : ....label:sanity checks\n       0.000 : 4 : ..label:renames\n    0.000 : 4 : label:write_auto_merge\n    0.000 : 4 : label:record_conflicted\nEstimated measurement overhead (.010 ms/region-measure * 134): 0.00134\nTiming including forking:  9.917 (0.026 additional seconds)\n\nFrom this, the things that stood out to me were:\n    2.104 : <unmeasured> (21.3%)\n\n2.1 of the 9.9 seconds was in rebase somewhere without trace2 regions\nto record it.  From above, clearly one big chunk of this time is from\ncan_fast_forward().  But that's only like 0.5-1.0s.  What's all the\nrest?  And can we get rid of most of it somehow?\n\n    6.628 : 7 : label:unpack_trees\n\nThis corresponds to the time to switch to v5.10 before starting to apply patches\n\n    0.515 : 4 : label:refresh\n\nI think this is wasted time trying to re-sync the data from the fact\nthat rebase shells out to external processes to do work it should do\nin-process (namely, \"git commit\").\n\n    0.380 : 6 : label:do_write_index\n/home/newren/floss/uwe-linux/.git/index.lock\n    0.081 : 4 : label:checkout\n    0.069 : 7 : label:do_read_index .git/index\n\n3/4 of this is wasted time from the fact that rebase updates the\nworking copy and index with every commit instead of just at the end of\nthe operation.  The \"preload\" marker may also belong here, or maybe up\nwith the preload.\n\n    0.011 : 4 : label:incore_nonrecursive\n\nIt only took 11 milliseconds to do the actual merging and creating the\nnew blobs and trees -- and that includes the rename detection time.\n"},{"id":"425843","messageId":"20210528214024.vw4huojcklrm6d27@pengutronix.de","threadId":"55774","inReplyTo":"CABPp-BEVME5Gx=F4HWHBb_0wn6XJF==DzVLo2i1xj63BB+_jtw@mail.gmail.com","subject":"Re: time needed to rebase shortend by using --onto?","fromName":"Uwe Kleine-König","fromEmail":"u.kleine-koenig@pengutronix.de","sentAt":"2021-05-28T21:40:24Z","receivedAt":"2021-05-28T21:40:29Z","isPatch":false,"sender":{"key":"u.kleine-koenig@pengutronix.de","avatar":"https://gravatar.com/avatar/354b5e3ceb2806a2f1e1e382ac29ddbdad18288654da62b61eb13583a857eee7?d=mp&s=160"},"body":"Hello Elijah,\n\nOn Thu, May 27, 2021 at 04:08:32PM -0700, Elijah Newren wrote:\n> On Thu, May 27, 2021 at 2:59 PM Uwe Kleine-König\n> <u.kleine-koenig@pengutronix.de> wrote:\n> > On Wed, May 26, 2021 at 07:38:08AM -0700, Elijah Newren wrote:\n> > > On Wed, May 26, 2021 at 3:13 AM Uwe Kleine-König\n> > > <u.kleine-koenig@pengutronix.de> wrote:\n> > > > I have a kernel topic branch containing 4 patches on top of Linux v5.4.\n> > > > (I didn't speak to the affected customer, so I cannot easily share the\n> > > > patch stack. If need be I can probably anonymize it or ask if I can\n> > > > publish the patches.)\n> > > >\n> > > > It rebases clean on v5.10:\n> > > >\n> > > >         $ time git rebase v5.10\n> > > >         Performing inexact rename detection: 100% (36806539/36806539), done.\n> > > >         Performing inexact rename detection: 100% (36806539/36806539), done.\n> > > >         Performing inexact rename detection: 100% (36806539/36806539), done.\n> > > >         Performing inexact rename detection: 100% (36806539/36806539), done.\n> > > >         Successfully rebased and updated detached HEAD.\n> > > >\n> > > >         real    3m47.841s\n> > > >         user    1m25.706s\n> > > >         sys     0m11.181s\n> > > >\n> > > > If I start with the same rev checked out and explicitly specify the\n> > > > merge base, the rebase process is considerably faster:\n> > > >\n> > > >         $ time git rebase --onto v5.10 v5.4\n> > > >         Performing inexact rename detection: 100% (36806539/36806539), done.\n> > > >         Performing inexact rename detection: 100% (36806539/36806539), done.\n> > > >         Performing inexact rename detection: 100% (36806539/36806539), done.\n> > > >         Performing inexact rename detection: 100% (36806539/36806539), done.\n> > > >         Successfully rebased and updated detached HEAD.\n> > > >\n> > > >         real    1m20.588s\n> > > >         user    1m12.645s\n> > > >         sys     0m6.733s\n> \n> Note: In your original report you had rename detection and it clearly\n> took a significant amount of time...\n\nFTR: My impression is that the repo I used for the first report is slow\nin general. Also git log sometimes takes a considerable time to start\nemitting output.\n\n> > > > Is there some relevant complexity in the first invocation I'm not seeing\n> > > > that explains it takes more than the double time? I would have expected\n> > > > that\n> > > >\n> > > >         git rebase v5.10\n> > > >\n> > > > does the same as:\n> > > >\n> > > >         git rebase --onto v5.10 $(git merge-base HEAD v5.10)\n> > > >\n> > > > . (FTR:\n> > > >\n> > > >         $ time git merge-base HEAD v5.10\n> > > >         219d54332a09e8d8741c1e1982f5eae56099de85\n> > > >\n> > > >         real    0m0.158s\n> > > >         user    0m0.105s\n> > > >         sys     0m0.052s\n> > > >\n> > > > , 219d5433 is v5.4 as expected.\n> > >\n> > > That does seem surprising, though if an automatic gc completed between\n> > > the two commands that could certainly explain it.  If that theory is\n> > > correct, it would suggest that it'd be difficult for you to reproduce;\n> >\n> > This reproduces just fine. The repository is quite big and it is slow at\n> > times. With the same tree on a different machine, the rebase is quicker,\n> > but the factor 2 between the two different commands is visible there,\n> > too:\n> >\n> > uwe@taurus:~/gsrc/linux$ git checkout bc2e99c9c9e0d29494b1739624554e4f5f979d32\n> > HEAD is now at bc2e99c9c9e0 [...]\n> >\n> > uwe@taurus:~/gsrc/linux$ time git rebase v5.10\n> > warning: inexact rename detection was skipped due to too many files.\n> > warning: you may want to set your merge.renamelimit variable to at least 8604 and retry the command.\n> > warning: inexact rename detection was skipped due to too many files.\n> > warning: you may want to set your merge.renamelimit variable to at least 8604 and retry the command.\n> > warning: inexact rename detection was skipped due to too many files.\n> > warning: you may want to set your merge.renamelimit variable to at least 8604 and retry the command.\n> > warning: inexact rename detection was skipped due to too many files.\n> > warning: you may want to set your merge.renamelimit variable to at least 8604 and retry the command.\n> > Successfully rebased and updated detached HEAD.\n> >\n> > real    0m20.737s\n> > user    0m14.188s\n> > sys     0m3.767s\n> >\n> > uwe@taurus:~/gsrc/linux$ git checkout bc2e99c9c9e0d29494b1739624554e4f5f979d32\n> > HEAD is now at bc2e99c9c9e0 [...]\n> >\n> > uwe@taurus:~/gsrc/linux$ time git rebase --onto v5.10 v5.4\n> > warning: inexact rename detection was skipped due to too many files.\n> > warning: you may want to set your merge.renamelimit variable to at least 8604 and retry the command.\n> > warning: inexact rename detection was skipped due to too many files.\n> > warning: you may want to set your merge.renamelimit variable to at least 8604 and retry the command.\n> > warning: inexact rename detection was skipped due to too many files.\n> > warning: you may want to set your merge.renamelimit variable to at least 8604 and retry the command.\n> > warning: inexact rename detection was skipped due to too many files.\n> > warning: you may want to set your merge.renamelimit variable to at least 8604 and retry the command.\n> > Successfully rebased and updated detached HEAD.\n> >\n> > real    0m12.129s\n> > user    0m7.196s\n> > sys     0m3.141s\n> >\n> > (This is with a slightly newer git: 2.30.2-1 from Debian)\n> \n> And here, there was no rename detection so this isn't the same thing\n> anymore.  You could try setting merge.renameLimit higher.\n\nI learned a few things since my last mail, here comes an updated test\nagain on the machine and repo used for the initial report:\n\n\tukl@dude.ptx:~/gsrc/linux$ wgit version\n\tgit version 2.32.0.rc1\n\n\tukl@dude.ptx:~/gsrc/linux$ cat rebasecheck \n\t#!/bin/bash\n\n\tset -e \n\n\t# do it once to heat the caches and ensure all objects are available already to have the next cycles identical.\n\twgit checkout 0091ecb84cfdef0f4cb65810219f5ac9bb4341e5\n\twgit rebase v5.10\n\n\twgit checkout 0091ecb84cfdef0f4cb65810219f5ac9bb4341e5\n\techo \"rebase v5.10\"\n\ttime wgit rebase v5.10\n\n\twgit checkout 0091ecb84cfdef0f4cb65810219f5ac9bb4341e5\n\techo \"rebase --onto v5.10 v5.4\"\n\ttime wgit rebase --onto v5.10 v5.4\n\nI do the rebase now once before the timing for the reasons described in\nthe comment. The second identical command is quite a bit quicker. Also\nnow that the commands are scripted they are done in a smaller time frame\n(which matters as the machine is used heavily among my colleagues and\nme). I run the script a few times in a row, after all colleagues are in\ntheir week-end:\n\n\tukl@dude.ptx:~/gsrc/linux$ bash rebasecheck \n\t...\n\trebase v5.10\n\t...\n\treal\t1m13.579s\n\tuser\t1m2.919s\n\tsys\t0m6.220s\n\t...\n\trebase --onto v5.10 v5.4\n\t...\n\treal\t1m2.852s\n\tuser\t0m53.780s\n\tsys\t0m6.225s\n\n\tukl@dude.ptx:~/gsrc/linux$ bash rebasecheck \n\t...\n\trebase v5.10\n\t...\n\treal\t1m10.816s\n\tuser\t1m3.344s\n\tsys\t0m6.991s\n\t...\n\trebase --onto v5.10 v5.4\n\t...\n\treal\t0m59.695s\n\tuser\t0m53.510s\n\tsys\t0m5.579s\n\n\tukl@dude.ptx:~/gsrc/linux$ bash rebasecheck \n\t...\n\trebase v5.10\n\t...\n\treal\t1m9.688s\n\tuser\t1m3.346s\n\tsys\t0m6.105s\n\t...\n\trebase --onto v5.10 v5.4\n\t...\n\treal\t0m59.981s\n\tuser\t0m52.931s\n\tsys\t0m6.282s\n\nSo it's not a factor 2 any more, but still reproducibly quicker when\n--onto is used.\n\n> However, the 7-8 second difference (and the likely large differences\n> between 5.4 and 5.10) do suggest that Junio's hunch that fork-point\n> behavior being at play could be an issue in these two commands.\n> \n> > Then I repeated the test with git 2.32.0-rc1 (wgit is just calling\n> > bin-wrappers/git in my git working copy):\n> >\n> > uwe@taurus:~/gsrc/linux$ wgit version\n> > git version 2.32.0.rc1\n> >\n> > uwe@taurus:~/gsrc/linux$ wgit checkout bc2e99c9c9e0d29494b1739624554e4f5f979d32\n> > HEAD is now at bc2e99c9c9e0 [...]\n> >\n> > uwe@taurus:~/gsrc/linux$ time wgit rebase v5.10\n> > warning: inexact rename detection was skipped due to too many files.\n> > warning: you may want to set your merge.renamelimit variable to at least 8024 and retry the command.\n> > warning: inexact rename detection was skipped due to too many files.\n> > warning: you may want to set your merge.renamelimit variable to at least 8024 and retry the command.\n> > warning: inexact rename detection was skipped due to too many files.\n> > warning: you may want to set your merge.renamelimit variable to at least 8024 and retry the command.\n> > warning: inexact rename detection was skipped due to too many files.\n> > warning: you may want to set your merge.renamelimit variable to at least 8024 and retry the command.\n> > Successfully rebased and updated detached HEAD.\n> >\n> > real    0m19.438s\n> > user    0m13.629s\n> > sys     0m3.299s\n> >\n> > uwe@taurus:~/gsrc/linux$ wgit checkout bc2e99c9c9e0d29494b1739624554e4f5f979d32\n> > HEAD is now at bc2e99c9c9e0 [...]\n> >\n> > uwe@taurus:~/gsrc/linux$ time wgit rebase --onto v5.10 v5.4\n> > warning: inexact rename detection was skipped due to too many files.\n> > warning: you may want to set your merge.renamelimit variable to at least 8024 and retry the command.\n> > warning: inexact rename detection was skipped due to too many files.\n> > warning: you may want to set your merge.renamelimit variable to at least 8024 and retry the command.\n> > warning: inexact rename detection was skipped due to too many files.\n> > warning: you may want to set your merge.renamelimit variable to at least 8024 and retry the command.\n> > warning: inexact rename detection was skipped due to too many files.\n> > warning: you may want to set your merge.renamelimit variable to at least 8024 and retry the command.\n> > Successfully rebased and updated detached HEAD.\n> >\n> > real    0m13.848s\n> > user    0m8.315s\n> > sys     0m3.182s\n> >\n> > So the surprise persists.\n> \n> Yeah, with no rename detection, the newer git version isn't going to\n> make a bit of difference.\n> \n> > > running again with either command would give you something closer to\n> > > the lower time both times.  Is that the case?  (Also, what's the\n> > > output of \"git count-objects -v\"?)\n> >\n> > After the above commands I have:\n> >\n> >         count: 3203\n> >         size: 17664\n> >         in-pack: 4763753\n> >         packs: 11\n> >         size-pack: 1273957\n> >         prune-packable: 19\n> >         garbage: 0\n> >         size-garbage: 0\n> \n> So, not freshly packed, but not in need of an automatic gc either.\n> \n> >         alternate: /home/uwe/var/gitstore/linux.git/objects\n> \n> You've got an alternate?  How well packed is it?  (What does \"git\n> count-objects -v\" in that other repo show?)\n> \n> >\n> > (On the repository I did this initially I have:\n> >\n> >         warning: garbage found: .git/objects/pack/pack-864148a84c0524073ed8c8aa1a76155d5c677879.pack.temp\n> >         warning: garbage found: /ptx/src/git/linux.git/objects/pack/tmp_pack_X9gHnq\n> >         count: 2652\n> >         size: 14640\n> >         in-pack: 2117015\n> >         packs: 8\n> >         size-pack: 574167\n> >         prune-packable: 856\n> >         garbage: 2\n> >         size-garbage: 1114236\n> >         alternate: /ptx/src/git/linux.git/objects\n\nIn the alternate I have:\n\n\tukl@dude.ptx:/ptx/src/git/linux.git/objects$ wgit count-objects -v\n\twarning: garbage found: /ptx/work/user/git/linux.git/objects/pack/tmp_pack_X9gHnq\n\tcount: 5035\n\tsize: 40720\n\tin-pack: 87083076\n\tpacks: 1108\n\tsize-pack: 51109693\n\tprune-packable: 3050\n\tgarbage: 1\n\tsize-garbage: 1112612\n\nThe alternate tracks\n\n\tgit://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git\n\tgit://git.kernel.org/pub/scm/linux/kernel/git/stable/linux-stable.git\n\tgit://git.kernel.org/pub/scm/linux/kernel/git/rt/linux-stable-rt.git\n\tgit://git.kernel.org/pub/scm/linux/kernel/git/next/linux-next.git\n\n(only the tags for the two latter).\n\n> > (Is the garbage a reason this is so slow? Can I just remove the two\n> > files pointed out?)\n> \n> If there isn't some still-running git operation that is fetching and\n> writing to these files, then yes they can be cleaned out.  I doubt\n> they'd make too much of a difference, though.  I was more curious if\n> you went from say 10000 loose objects to ~0, or from 50+ packs down to\n> 1 between operations due to an automatic gc completing.\n> \n> > > I'd love to try this with git-2.32.0-rc1 (or even my not-yet-upstream\n> > > patches that optimize even further) with adding \"--strategy=ort\" to\n> > > your rebase command to see how much of a timing difference it makes.\n> > > Any chance the patches could either be published, or you could retry\n> > > with git-2.32.0-rc1 and add the --strategy=ort command line option to\n> > > your rebase command(s)?\n> >\n> > With --strategy=ort added I have:\n> >\n> > uwe@taurus:~/gsrc/linux$ time wgit rebase --strategy=ort v5.10\n> > Successfully rebased and updated detached HEAD.\n> >\n> > real    0m19.202s\n> > user    0m12.724s\n> > sys     0m2.961s\n> >\n> > [...]\n> >\n> > uwe@taurus:~/gsrc/linux$ time wgit rebase --strategy=ort --onto v5.10 v5.4\n> > Successfully rebased and updated detached HEAD.\n> >\n> > real    0m12.395s\n> > user    0m6.638s\n> > sys     0m3.284s\n> >\n> > So the warnings about inexact rename detection don't appear and it's a\n> > bit faster, but I still see the timing difference between these two\n> > commands.\n> \n> Right, this says that --strategy=ort WITH rename detection is as fast\n> as the default --strategy=recursive WITHOUT rename detection.\n\nI rerun the script with -sort added:\n\n\tukl@dude.ptx:~/gsrc/linux$ bash rebasecheck\n\t...\n\trebase v5.10\n\t...\n\treal\t0m25.047s\n\tuser\t0m17.652s\n\tsys\t0m5.802s\n\t...\n\trebase --onto v5.10 v5.4\n\t...\n\treal\t0m12.471s\n\tuser\t0m7.854s\n\tsys\t0m4.413s\n\n\tukl@dude.ptx:~/gsrc/linux$ bash rebasecheck\n\t...\n\trebase v5.10\n\t...\n\treal\t0m22.180s\n\tuser\t0m17.219s\n\tsys\t0m4.701s\n\t...\n\trebase --onto v5.10 v5.4\n\t...\n\treal\t0m12.341s\n\tuser\t0m7.308s\n\tsys\t0m4.632s\n\nSo -sort is quite a bit quicker, but the ~10s overhead when not using\n--onto is visible there, too.\n  \nWhen looking at the timing of the output, the 10s time difference occur\nbefore \"Rebasing (1/4)\" is emitted.\n\n\twgit rebase -sort --onto v5.10 v5.10\n\nbehaves like\n\n\twgit rebase -sort v5.10\n\nand if I only rebase the first two patches (instead of four) it still\ntakes nearly the same time. Another test I did was:\n\n\ttime wgit rebase -sort --onto v5.10 v5.7\n\n\treal\t0m17.712s\n\tuser\t0m11.570s\n\tsys\t0m5.396s\n\nSo there seems to be something before the actual rebase is done that\ntakes longer when HEAD..$base contains more objects.\nGiven that\n\n\tukl@dude.ptx:~/gsrc/linux$ time wgit log --oneline --cherry v5.10...0091ecb84cfdef0f4cb65810219f5ac9bb4341e5\n\t+ 0091ecb84cfd (ptx/ukl/rebase-timing) nvmem: core: skip child nodes not matching binding\n\t+ 38af1d38c542 spidev: add \"hxxxxxxx,xxxxxx\" compatible\n\t+ a7edcfb6a968 regmap: fix memory leak in regmap_debugfs_init()\n\t+ b1d90bc89408 pci: add quirk for txxxxx FPGA watchdog\n\n\treal\t0m10.783s\n\tuser\t0m10.346s\n\tsys\t0m0.436s\n\nI guess this range is searched for commits that have the same patch id\nas the patches to rebase?\n\n> It's not a fair comparison (you'd need to set merge.renameLimit higher\n> and re-run the cases where you had warnings), but is interesting\n> nonetheless.  It basically suggests that rename detection comes for\n> free with the ort strategy.\n\nFTR: In the above repo I have:\n\n\tukl@dude.ptx:~/gsrc/linux$ wgit config merge.renameLimit\n\t10000\n\nBest regards\nUwe\n\n-- \nPengutronix e.K.                           | Uwe Kleine-König            |\nIndustrial Linux Solutions                 | https://www.pengutronix.de/ |\n"},{"id":"425847","messageId":"CABPp-BG=nro4ydA9hAdq0A+AGX27_qCsy0sgrqfBLcGfFaQo8A@mail.gmail.com","threadId":"55774","inReplyTo":"20210528214024.vw4huojcklrm6d27@pengutronix.de","subject":"Re: time needed to rebase shortend by using --onto?","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-05-28T22:26:04Z","receivedAt":"2021-05-28T22:26:23Z","isPatch":false,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"Hi Uwe,\n\nOn Fri, May 28, 2021 at 2:40 PM Uwe Kleine-König\n<u.kleine-koenig@pengutronix.de> wrote:\n>\n> Hello Elijah,\n>\n> On Thu, May 27, 2021 at 04:08:32PM -0700, Elijah Newren wrote:\n> > On Thu, May 27, 2021 at 2:59 PM Uwe Kleine-König\n> > <u.kleine-koenig@pengutronix.de> wrote:\n> > > On Wed, May 26, 2021 at 07:38:08AM -0700, Elijah Newren wrote:\n> > > > On Wed, May 26, 2021 at 3:13 AM Uwe Kleine-König\n> > > > <u.kleine-koenig@pengutronix.de> wrote:\n...\n> > Note: In your original report you had rename detection and it clearly\n> > took a significant amount of time...\n>\n> FTR: My impression is that the repo I used for the first report is slow\n> in general. Also git log sometimes takes a considerable time to start\n> emitting output.\n>\n...\n>\n> I learned a few things since my last mail, here comes an updated test\n> again on the machine and repo used for the initial report:\n>\n>         ukl@dude.ptx:~/gsrc/linux$ wgit version\n>         git version 2.32.0.rc1\n>\n>         ukl@dude.ptx:~/gsrc/linux$ cat rebasecheck\n>         #!/bin/bash\n>\n>         set -e\n>\n>         # do it once to heat the caches and ensure all objects are available already to have the next cycles identical.\n>         wgit checkout 0091ecb84cfdef0f4cb65810219f5ac9bb4341e5\n>         wgit rebase v5.10\n>\n>         wgit checkout 0091ecb84cfdef0f4cb65810219f5ac9bb4341e5\n>         echo \"rebase v5.10\"\n>         time wgit rebase v5.10\n>\n>         wgit checkout 0091ecb84cfdef0f4cb65810219f5ac9bb4341e5\n>         echo \"rebase --onto v5.10 v5.4\"\n>         time wgit rebase --onto v5.10 v5.4\n>\n> I do the rebase now once before the timing for the reasons described in\n> the comment. The second identical command is quite a bit quicker. Also\n> now that the commands are scripted they are done in a smaller time frame\n> (which matters as the machine is used heavily among my colleagues and\n> me). I run the script a few times in a row, after all colleagues are in\n> their week-end:\n>\n>         ukl@dude.ptx:~/gsrc/linux$ bash rebasecheck\n>         ...\n>         rebase v5.10\n>         ...\n>         real    1m13.579s\n>         user    1m2.919s\n>         sys     0m6.220s\n>         ...\n>         rebase --onto v5.10 v5.4\n>         ...\n>         real    1m2.852s\n>         user    0m53.780s\n>         sys     0m6.225s\n>\n>         ukl@dude.ptx:~/gsrc/linux$ bash rebasecheck\n>         ...\n>         rebase v5.10\n>         ...\n>         real    1m10.816s\n>         user    1m3.344s\n>         sys     0m6.991s\n>         ...\n>         rebase --onto v5.10 v5.4\n>         ...\n>         real    0m59.695s\n>         user    0m53.510s\n>         sys     0m5.579s\n>\n>         ukl@dude.ptx:~/gsrc/linux$ bash rebasecheck\n>         ...\n>         rebase v5.10\n>         ...\n>         real    1m9.688s\n>         user    1m3.346s\n>         sys     0m6.105s\n>         ...\n>         rebase --onto v5.10 v5.4\n>         ...\n>         real    0m59.981s\n>         user    0m52.931s\n>         sys     0m6.282s\n>\n> So it's not a factor 2 any more, but still reproducibly quicker when\n> --onto is used.\n\nYep, so that looks like the results I was getting.  Adding\n--reapply-cherry-picks should remove most of that time difference as I\nstated in my previous email.\n\n> > However, the 7-8 second difference (and the likely large differences\n> > between 5.4 and 5.10) do suggest that Junio's hunch that fork-point\n> > behavior being at play could be an issue in these two commands.\n\nI don't think --no-fork-point will matter here since you are detaching\nHEAD before running rebase.  fork-point is all about looking up the\nreflog of the current branch to find better matches.\n--reapply-cherry-picks should help you out and erase most of this 7-8\nsecond difference.\n\n> > > > running again with either command would give you something closer to\n> > > > the lower time both times.  Is that the case?  (Also, what's the\n> > > > output of \"git count-objects -v\"?)\n> > >\n> > > After the above commands I have:\n> > >\n> > >         count: 3203\n> > >         size: 17664\n> > >         in-pack: 4763753\n> > >         packs: 11\n> > >         size-pack: 1273957\n> > >         prune-packable: 19\n> > >         garbage: 0\n> > >         size-garbage: 0\n> >\n> > So, not freshly packed, but not in need of an automatic gc either.\n> >\n> > >         alternate: /home/uwe/var/gitstore/linux.git/objects\n> >\n> > You've got an alternate?  How well packed is it?  (What does \"git\n> > count-objects -v\" in that other repo show?)\n> >\n...\n>\n> In the alternate I have:\n>\n>         ukl@dude.ptx:/ptx/src/git/linux.git/objects$ wgit count-objects -v\n>         warning: garbage found: /ptx/work/user/git/linux.git/objects/pack/tmp_pack_X9gHnq\n>         count: 5035\n\nThis is really close to the threshold of needing repacking, but still okay.\n\n>         size: 40720\n>         in-pack: 87083076\n>         packs: 1108\n\n1108 packs!?!?  This will make all kinds of operations slow.  This\nexplains your comment about operations with your original repo being\nslow in general, and why you feel you need to do a warmup run first to\nget a reasonable timing.  50 is the limit where repacking is deemed\nnecessary; you're 2116% beyond that point.  I've only seen repos with\npack counts near this level a couple times and they are excruciatingly\npainful to deal with.\n\nHowever, be careful not to use \"git gc\" or \"git prune\" in this repo,\nsince it's used as an alternate (doing so could corrupt the repos that\ndepend on this one).  Just use \"git repack\" with the appropriate flags\ninstead.\n\n>         size-pack: 51109693\n\n51G.  Wow.  A fresh clone of linux is waaay smaller than that.  3 G, I\nthink?  I would have thought lots of your packs were small, but this\nsuggests you probably have lots of duplicate objects in these packs.\n\n>         prune-packable: 3050\n>         garbage: 1\n>         size-garbage: 1112612\n\nAnd 1 G of garbage that could just be deleted.\n\n> I rerun the script with -sort added:\n>\n>         ukl@dude.ptx:~/gsrc/linux$ bash rebasecheck\n>         ...\n>         rebase v5.10\n>         ...\n>         real    0m25.047s\n>         user    0m17.652s\n>         sys     0m5.802s\n>         ...\n>         rebase --onto v5.10 v5.4\n>         ...\n>         real    0m12.471s\n>         user    0m7.854s\n>         sys     0m4.413s\n>\n>         ukl@dude.ptx:~/gsrc/linux$ bash rebasecheck\n>         ...\n>         rebase v5.10\n>         ...\n>         real    0m22.180s\n>         user    0m17.219s\n>         sys     0m4.701s\n>         ...\n>         rebase --onto v5.10 v5.4\n>         ...\n>         real    0m12.341s\n>         user    0m7.308s\n>         sys     0m4.632s\n>\n> So -sort is quite a bit quicker, but the ~10s overhead when not using\n> --onto is visible there, too.\n\nYeah, try adding --reapply-cherry-picks; I think that flag should\nshrink most of the difference.\n\n> When looking at the timing of the output, the 10s time difference occur\n> before \"Rebasing (1/4)\" is emitted.\n>\n>         wgit rebase -sort --onto v5.10 v5.10\n>\n> behaves like\n>\n>         wgit rebase -sort v5.10\n>\n> and if I only rebase the first two patches (instead of four) it still\n> takes nearly the same time. Another test I did was:\n>\n>         time wgit rebase -sort --onto v5.10 v5.7\n>\n>         real    0m17.712s\n>         user    0m11.570s\n>         sys     0m5.396s\n>\n> So there seems to be something before the actual rebase is done that\n> takes longer when HEAD..$base contains more objects.\n> Given that\n>\n>         ukl@dude.ptx:~/gsrc/linux$ time wgit log --oneline --cherry v5.10...0091ecb84cfdef0f4cb65810219f5ac9bb4341e5\n>         + 0091ecb84cfd (ptx/ukl/rebase-timing) nvmem: core: skip child nodes not matching binding\n>         + 38af1d38c542 spidev: add \"hxxxxxxx,xxxxxx\" compatible\n>         + a7edcfb6a968 regmap: fix memory leak in regmap_debugfs_init()\n>         + b1d90bc89408 pci: add quirk for txxxxx FPGA watchdog\n>\n>         real    0m10.783s\n>         user    0m10.346s\n>         sys     0m0.436s\n>\n> I guess this range is searched for commits that have the same patch id\n> as the patches to rebase?\n\nYep, and --reapply-cherry-picks removes this cherry-searching.  Try it\nand see how it affects your results.  I don't think it'll entirely\neliminate the differences for you (it didn't for me), because there\nappears to be some other weird overhead -- part of it from\ncan_fast_forward() and more that I didn't track down further.  I do\nthink that the --reapply-cherry-picks will remove most of the\ndifferences for you, though.\n\n> FTR: In the above repo I have:\n>\n>         ukl@dude.ptx:~/gsrc/linux$ wgit config merge.renameLimit\n>         10000\n\nYep, so my choice of 9999 to try to reproduce your behavior was a\npretty good pick, eh?  :-)\n\n\nHope that helps,\nElijah\n"},{"id":"425887","messageId":"60b272ff6bfa4_265861208d6@natae.notmuch","threadId":"55774","inReplyTo":"20210528214024.vw4huojcklrm6d27@pengutronix.de","subject":"Re: time needed to rebase shortend by using --onto?","fromName":"Felipe Contreras","fromEmail":"felipe.contreras@gmail.com","sentAt":"2021-05-29T16:59:43Z","receivedAt":"2021-05-29T16:59:52Z","isPatch":false,"sender":{"key":"felipe.contreras@gmail.com","avatar":"https://avatars.githubusercontent.com/u/8358?v=4"},"body":"Uwe Kleine-König wrote:\n> I do the rebase now once before the timing for the reasons described in\n> the comment. The second identical command is quite a bit quicker. Also\n> now that the commands are scripted they are done in a smaller time frame\n> (which matters as the machine is used heavily among my colleagues and\n> me). I run the script a few times in a row, after all colleagues are in\n> their week-end:\n> \n> \tukl@dude.ptx:~/gsrc/linux$ bash rebasecheck \n> \t...\n> \trebase v5.10\n> \t...\n> \treal\t1m13.579s\n> \tuser\t1m2.919s\n> \tsys\t0m6.220s\n> \t...\n> \trebase --onto v5.10 v5.4\n> \t...\n> \treal\t1m2.852s\n> \tuser\t0m53.780s\n> \tsys\t0m6.225s\n> \n> \tukl@dude.ptx:~/gsrc/linux$ bash rebasecheck \n> \t...\n> \trebase v5.10\n> \t...\n> \treal\t1m10.816s\n> \tuser\t1m3.344s\n> \tsys\t0m6.991s\n> \t...\n> \trebase --onto v5.10 v5.4\n> \t...\n> \treal\t0m59.695s\n> \tuser\t0m53.510s\n> \tsys\t0m5.579s\n> \n> \tukl@dude.ptx:~/gsrc/linux$ bash rebasecheck \n> \t...\n> \trebase v5.10\n> \t...\n> \treal\t1m9.688s\n> \tuser\t1m3.346s\n> \tsys\t0m6.105s\n> \t...\n> \trebase --onto v5.10 v5.4\n> \t...\n> \treal\t0m59.981s\n> \tuser\t0m52.931s\n> \tsys\t0m6.282s\n> \n> So it's not a factor 2 any more, but still reproducibly quicker when\n> --onto is used.\n\nYears ago I completely rewrote `git rebase` to use `git cherry-pick`,\nand the result is a very simple command:\n\n  git checkout $onto\n  git cherry-pick --no-merges --right-only --topo-order --do-walk\n    @{upstream}..v5.4\n\nThe difference when you don't specify --onto is basically that both onto\nand upstream are considered the same:\n\n  git checkout $onto\n  git cherry-pick --no-merges --right-only --topo-order --do-walk\n    $onto..v5.4\n\nTherefore it should be more efficient to specify --onto.\n\nExcept git tries to be smart and first tries to check if a fast-forward\nis possible, even if you specify --no-ff (a mistake IMO).\n\nTo check for linear history the old code used to do:\n\n  git rev-list --parents $onto..v5.4 | grep \" .* \"\n\nMaybe that is too slow in your particular situation.\n\nYou could try --restrict-revisions=v5.10 (or anything other than the\nmerge base), but apparently that only works with --interactive.\n\nAnother option is just hack git to disable the linear history check:\n\ndiff --git a/builtin/rebase.c b/builtin/rebase.c\nindex 12f093121d..bdbcfaa58e 100644\n--- a/builtin/rebase.c\n+++ b/builtin/rebase.c\n@@ -1145,6 +1145,10 @@ static int can_fast_forward(struct commit *onto, struct commit *upstream,\n        }\n \n        oidcpy(merge_base, &merge_bases->item->object.oid);\n+\n+       /* Hack to avoid linear history check */\n+       goto done;\n+\n        if (!oideq(merge_base, &onto->object.oid))\n                goto done;\n \n\nCheers.\n\n-- \nFelipe Contreras"}]}