{"thread":{"id":"13016","subject":"git bisect on multiple cores","startedAt":"2008-04-08T10:58:47Z","lastAt":"2008-04-09T08:27:00Z","messageCount":8,"participants":["A B","David Symonds","Junio C Hamano","Christian Couder","Karl Hasselström","Matthieu Moy"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"73843","messageId":"dbbf25900804080358o6b1ada20pfb94f68f06a23f83@mail.gmail.com","threadId":"13016","inReplyTo":null,"subject":"git bisect on multiple cores","fromName":"A B","fromEmail":"gentosaker@gmail.com","sentAt":"2008-04-08T10:58:47Z","receivedAt":"2008-04-08T10:58:47Z","isPatch":false,"sender":{"key":"gentosaker@gmail.com","avatar":null},"body":"git bisect is really cool. I use it for the first time.\nJust a thought, if you have a multiple core computer, can't you make\ngit build new versions in the background while testing the previuos\nversion? Alright, if you build 2 versions, one of them will never be\ntested, but you will perhaps save some time by letting it build in the\nbackground?\n\nJust a thought...\n"},{"id":"73844","messageId":"ee77f5c20804080550h251918d6n73d73a1de8ec6c09@mail.gmail.com","threadId":"13016","inReplyTo":"dbbf25900804080358o6b1ada20pfb94f68f06a23f83@mail.gmail.com","subject":"Re: git bisect on multiple cores","fromName":"David Symonds","fromEmail":"dsymonds@gmail.com","sentAt":"2008-04-08T12:50:34Z","receivedAt":"2008-04-08T12:50:34Z","isPatch":false,"sender":{"key":"dsymonds@gmail.com","avatar":"https://gravatar.com/avatar/b22f5051cbfc11836e36cf7a690e6cde4e225d835e13295ff98d15c7a9ee3c0f?d=mp&s=160"},"body":"On Tue, Apr 8, 2008 at 8:58 PM, A B wrote:\n\n> git bisect is really cool. I use it for the first time.\n> Just a thought, if you have a multiple core computer, can't you make\n> git build new versions in the background while testing the previuos\n> version? Alright, if you build 2 versions, one of them will never be\n> tested, but you will perhaps save some time by letting it build in the\n> background?\n\nGit is used to track more than just source code that can be \"built\",\nand git bisect can be used for more than just tracking down bugs.\n\nI'm not convinced the considerable extra complexity would be\nworthwhile. You'd have to have git bisect do checkouts to new\ntemporary directories, track them and clean them up.\n\nIt might be interesting if you approached it as a tri-section or a\ngeneral N-section where you try to divide the interval into N parts\nand concurrently test N-1 commits. But really, do you find git bisect\nall that slow in practice? You probably have a reasonable guess as to\nwhere a regression has come in, and so even 1000 revisions needs at\nmost 10 bisections to find the culprit.\n\n\nDave.\n"},{"id":"73863","messageId":"7vhcecmb90.fsf@gitster.siamese.dyndns.org","threadId":"13016","inReplyTo":"ee77f5c20804080550h251918d6n73d73a1de8ec6c09@mail.gmail.com","subject":"Re: git bisect on multiple cores","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-04-08T18:50:51Z","receivedAt":"2008-04-08T18:50:51Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"David Symonds\" writes:\n\n> Git is used to track more than just source code that can be \"built\",\n> and git bisect can be used for more than just tracking down bugs.\n>\n> I'm not convinced the considerable extra complexity would be\n> worthwhile. You'd have to have git bisect do checkouts to new\n> temporary directories, track them and clean them up.\n\nI personally think \"git bisect\" Porcelain does a bit too much. For\nexample, it always checks the revision out, but some non-build checks can\nbe done without having a checkout.\n\nThe core idea of bisect, which is really about how to effectively use \"git\nrev-list --bisect\", is quite simple. You start by one bad and zero or\nmore \"good\" ones, where the \"bad\" one is a descendant of the good ones,\nand hunt for a _single_ change that changed a \"good\" state into a \"bad\"\none.\n\nThis last point is important. The only thing \"bisect\" can find is a\nsingle flip where all of its ancestors are \"good\" and where all of its\ndescendants are \"bad\". Think of a bad gene introduced by a mutation at a\nparticular commit (i.e. \"generation\") and that contaminates all of its\nchildren and descendants forever.\n\nIf you visualize the commit ancestry graph growing from left to right like\nwe usually draw in our documentation and e-mails, and if you paint\nknown-to-be-good ones blue, known-to-be-bad ones red, and unknown ones\nyellow, you will get a picture not unlike the ones shown on pp.111-115 of \nhttp://userweb.kernel.org/~junio/200607-ols.pdf\n\nThe underlying \"git rev-list --bisect\" takes a set of \"good\" commits and a\nsingle \"bad\" commit, computes the set of commits that are unknown\n(\"yellow\"), and gives one of them that lies halfway from \"good\" ones\n(\"blue\") and the \"bad\" one (\"red\").\n\nThe way \"git bisect\" operates is:\n\n (0) Prime the process by getting a single \"bad\" and zero or more \"good\";\n switch to \"bisect\" branch.\n\n (1) Ask \"rev-list --bisect\" the midpoint; check out that revision for you\n to test.\n\n (2) It's your turn to give more information to \"git bisect\".\n\n (2-a) If you say \"good\", it is added to the set of \"good\"; go back to (1)\n\n (2-b) If you say \"bad\", it is set to \"bad\" (because of the way bisection\n works, this is always an ancestor of the previous \"bad\", and\n because the only thing we do is to find a single flip, keeping a\n single \"bad\" that is an ancestor of all the commits previously\n known-to-be-bad is sufficient); go back to (1)\n\nOne thing to note is that in (2-a) or (2-b), you do not necessarily have\nto say the commit the command gave you in step (1) is good or bad. If the\nrevision given by (1) is untestable, you can reset to another yellow one,\ntest that, and tell the command \"This is good/bad\".\n\nSo one way to speed up your bisection process would be:\n\n * Have multiple work trees (e.g. contrib/workdir/git-new-workdir);\n\n * Run bisect in one repository;\n\n * In step (1) of each round, look at gitk output and pick another commit\n that is distant from the one you are going to test. In another work\n tree, check that one out and test it in parallel.\n\n * You can feed the good/bad information you obtained from the test you\n run in the neighbouring work tree, in addition to what you learn in\n your main tree, with \"git bisect good $it\" or \"git bisect bad $it\".\n\n> It might be interesting if you approached it as a tri-section or a\n> general N-section where you try to divide the interval into N parts\n> and concurrently test N-1 commits. But really, do you find git bisect\n> all that slow in practice? You probably have a reasonable guess as to\n> where a regression has come in, and so even 1000 revisions needs at\n> most 10 bisections to find the culprit.\n\nI think adding N-section to \"rev-list --bisect\" would generally be an\ninteresting thing to do. For one thing, it would allow you to automate\nthe step to \"pick another commit that is distant from the one you are\ngoing to test\" in the above sequence.\n"},{"id":"73917","messageId":"200804090629.29122.chriscool@tuxfamily.org","threadId":"13016","inReplyTo":"dbbf25900804080358o6b1ada20pfb94f68f06a23f83@mail.gmail.com","subject":"Re: git bisect on multiple cores","fromName":"Christian Couder","fromEmail":"chriscool@tuxfamily.org","sentAt":"2008-04-09T04:29:28Z","receivedAt":"2008-04-09T04:29:28Z","isPatch":false,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"Le mardi 8 avril 2008, A B a écrit :\n> git bisect is really cool. I use it for the first time.\n> Just a thought, if you have a multiple core computer, can't you make\n> git build new versions in the background while testing the previuos\n> version? Alright, if you build 2 versions, one of them will never be\n> tested, but you will perhaps save some time by letting it build in the\n> background?\n\nYes, you can do that.\n\nIf you have cloned your repository twice (or more), then you can bisect \ncompile and test at the same time in your 3 repositories (or more if you \nreally want).\n\nFor example if bisecting in one repo asks you to test revision X, then you \ncan bisect and then build (and even maybe start testing) in another repo \nassuming revision X is good, and in yet in another one assuming revision X \nis bad.\n\n(In the repo where you assume X is good you use:\n\n\"git bisect start CURRENT-BAD X\"\n\nand in the third one, where you assume X is bad, you use:\n\n\"git bisect start X CURRENT-GOOD\")\n\nWhen you know that X was good then you can kill the build or test processes \nand \"git bisect reset\" in the repository where you assumed wrongly X was \nbad. You can then assume something else with \"git bisect start B G\" and \nbuild and test in this repo again.\n\nIn the repo that told you X was good, then you need only to use \"git bisect \ngood\" or \"git bisect bad\" without building and testing to assume something \nabout the revision that should be built and tested.\n\nRegards,\nChristian.\n"},{"id":"73920","messageId":"200804090747.23596.chriscool@tuxfamily.org","threadId":"13016","inReplyTo":"200804090629.29122.chriscool@tuxfamily.org","subject":"Re: git bisect on multiple cores","fromName":"Christian Couder","fromEmail":"chriscool@tuxfamily.org","sentAt":"2008-04-09T05:47:23Z","receivedAt":"2008-04-09T05:47:23Z","isPatch":false,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"Le mercredi 9 avril 2008, Christian Couder a écrit :\n> Le mardi 8 avril 2008, A B a écrit :\n> > git bisect is really cool. I use it for the first time.\n> > Just a thought, if you have a multiple core computer, can't you make\n> > git build new versions in the background while testing the previuos\n> > version? Alright, if you build 2 versions, one of them will never be\n> > tested, but you will perhaps save some time by letting it build in the\n> > background?\n>\n> Yes, you can do that.\n>\n> If you have cloned your repository twice (or more), then you can bisect\n> compile and test at the same time in your 3 repositories (or more if you\n> really want).\n>\n> For example if bisecting in one repo asks you to test revision X, then\n> you can bisect and then build (and even maybe start testing) in another\n> repo assuming revision X is good, and in yet in another one assuming\n> revision X is bad.\n>\n> (In the repo where you assume X is good you use:\n>\n> \"git bisect start CURRENT-BAD X\"\n>\n> and in the third one, where you assume X is bad, you use:\n>\n> \"git bisect start X CURRENT-GOOD\")\n\nIn fact, you have to give all the good revisions you have, not just the last \none. So it should be \n\n\"git bisect start CURRENT-BAD X GOOD1 GOOD2 ...\"\n\nor\n\n\"git bisect start X GOOD1 GOOD2 ...\"\n\ninstead of the above.\n\n> When you know that X was good then you can kill the build or test\n> processes and \"git bisect reset\" in the repository where you assumed\n> wrongly X was bad. You can then assume something else with \"git bisect\n> start B G\" and build and test in this repo again.\n\nAbove also you must give all the good ones, so it is:\n\n\"git bisect start B G1 G2...\"\n\n> In the repo that told you X was good, then you need only to use \"git\n> bisect good\" or \"git bisect bad\" without building and testing to assume\n> something about the revision that should be built and tested.\n\nRegards,\nChristian.\n"},{"id":"73932","messageId":"20080409071750.GA23211@diana.vm.bytemark.co.uk","threadId":"13016","inReplyTo":"dbbf25900804080358o6b1ada20pfb94f68f06a23f83@mail.gmail.com","subject":"Re: git bisect on multiple cores","fromName":"Karl Hasselström","fromEmail":"kha@treskal.com","sentAt":"2008-04-09T07:17:50Z","receivedAt":"2008-04-09T07:17:50Z","isPatch":false,"sender":{"key":"kha@treskal.com","avatar":"https://gravatar.com/avatar/f0120c734b5279b345075a28521e1ac66acb20c9913ffe9bf6ae97e53f7f3f13?d=mp&s=160"},"body":"On 2008-04-08 12:58:47 +0200, A B wrote:\n\n> git bisect is really cool. I use it for the first time. Just a\n> thought, if you have a multiple core computer, can't you make git\n> build new versions in the background while testing the previuos\n> version? Alright, if you build 2 versions, one of them will never be\n> tested, but you will perhaps save some time by letting it build in\n> the background?\n\nAdding parallelism to a binary search scales very badly -- I'd say\nabout logarithmically, but I haven't thought hard about it. If it's\npossible to use the extra cores to speed up the build+test cycle,\nthat's vastly preferable.\n\n-- \nKarl Hasselström, kha@treskal.com\n www.treskal.com/kalle\n"},{"id":"73934","messageId":"vpq63ure9j6.fsf@bauges.imag.fr","threadId":"13016","inReplyTo":"20080409071750.GA23211@diana.vm.bytemark.co.uk","subject":"Re: git bisect on multiple cores","fromName":"Matthieu Moy","fromEmail":"matthieu.moy@imag.fr","sentAt":"2008-04-09T08:07:25Z","receivedAt":"2008-04-09T08:07:25Z","isPatch":false,"sender":{"key":"git@matthieu-moy.fr","avatar":"https://avatars.githubusercontent.com/u/14709?v=4"},"body":"Karl Hasselström writes:\n\n> On 2008-04-08 12:58:47 +0200, A B wrote:\n>\n>> git bisect is really cool. I use it for the first time. Just a\n>> thought, if you have a multiple core computer, can't you make git\n>> build new versions in the background while testing the previuos\n>> version? Alright, if you build 2 versions, one of them will never be\n>> tested, but you will perhaps save some time by letting it build in\n>> the background?\n>\n> Adding parallelism to a binary search scales very badly -- I'd say\n> about logarithmically, but I haven't thought hard about it. If it's\n> possible to use the extra cores to speed up the build+test cycle,\n> that's vastly preferable.\n\nProbably logarithmically with the number of cores. But for reasonable\nmachines, this number is relatively low, so the log is not so costly.\nFor a binary search, using just 2 cores, you can try the next in the\nlist in case of a \"git bisect good\" for example, and if the hypothesis\nis true, you've just gained a factor 2 (assuming it happens 50% of\ntimes, that should be a 50% speedup). Similarly, you should get a\nfactor 2 with 3 cores.\n\nAnd as said before, you can also try trisection or N-section. But no,\nI won't claim this is simple to implement ;-).\n\n-- \nMatthieu\n"},{"id":"73935","messageId":"20080409082700.GA24195@diana.vm.bytemark.co.uk","threadId":"13016","inReplyTo":"vpq63ure9j6.fsf@bauges.imag.fr","subject":"Re: git bisect on multiple cores","fromName":"Karl Hasselström","fromEmail":"kha@treskal.com","sentAt":"2008-04-09T08:27:00Z","receivedAt":"2008-04-09T08:27:00Z","isPatch":false,"sender":{"key":"kha@treskal.com","avatar":"https://gravatar.com/avatar/f0120c734b5279b345075a28521e1ac66acb20c9913ffe9bf6ae97e53f7f3f13?d=mp&s=160"},"body":"On 2008-04-09 10:07:25 +0200, Matthieu Moy wrote:\n\n> Karl Hasselström writes:\n>\n> > Adding parallelism to a binary search scales very badly -- I'd say\n> > about logarithmically, but I haven't thought hard about it. If\n> > it's possible to use the extra cores to speed up the build+test\n> > cycle, that's vastly preferable.\n>\n> Probably logarithmically with the number of cores. But for\n> reasonable machines, this number is relatively low, so the log is\n> not so costly. For a binary search, using just 2 cores, you can try\n> the next in the list in case of a \"git bisect good\" for example, and\n> if the hypothesis is true, you've just gained a factor 2 (assuming\n> it happens 50% of times, that should be a 50% speedup). Similarly,\n> you should get a factor 2 with 3 cores.\n\nYeah. But to get a factor 3, you need 7 cores; and for 4, you need 15.\nIt goes downhill from there. If your build+test cycle is\nparallelizable at all, I don't think you'll find those numbers hard to\nbeat.\n\n(There's also the fact that testing several revisions at once assumes\nthat the whole build+test cycle is automated, or at least most of it.\nOtherwise you need more people as well as more cores.)\n\n-- \nKarl Hasselström, kha@treskal.com\n www.treskal.com/kalle\n"}]}