{"thread":{"id":"29989","subject":"Feature request: don't require both bad and good when bisecting","startedAt":"2012-03-18T21:29:57Z","lastAt":"2012-03-19T16:49:21Z","messageCount":6,"participants":["darxus@chaosreigns.com","Andreas Ericsson","Jeff King","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"187216","messageId":"20120318212957.GS1219@chaosreigns.com","threadId":"29989","inReplyTo":null,"subject":"Feature request: don't require both bad and good when bisecting","fromName":"","fromEmail":"darxus@chaosreigns.com","sentAt":"2012-03-18T21:29:57Z","receivedAt":"2012-03-18T21:29:57Z","isPatch":false,"sender":{"key":"darxus@chaosreigns.com","avatar":null},"body":"I'd like to be able to tell get only that I know the latest commit is bad,\nand have it go find a good commit, then do the bisecting.  Maybe something\nlike the opposite of a binary search, start with the last commit, then\nsecond to last, then 4th to last, 8th to last, etc., till it finds a good\ncommit.\n\n-- \n\"This hurts quite a bit. Very painful.\"\n\"Think of the sensation as reassurance that you are not dead yet. What\nyou are feeling is life in you!\" - Johnny The Homicidal Maniac\nhttp://www.ChaosReigns.com\n"},{"id":"187250","messageId":"4F67468B.4070502@op5.se","threadId":"29989","inReplyTo":"20120318212957.GS1219@chaosreigns.com","subject":"Re: Feature request: don't require both bad and good when bisecting","fromName":"Andreas Ericsson","fromEmail":"ae@op5.se","sentAt":"2012-03-19T14:45:31Z","receivedAt":"2012-03-19T14:45:31Z","isPatch":false,"sender":{"key":"ae@op5.se","avatar":"https://gravatar.com/avatar/426e89595c75a8f5252dd0c989e5fabe5bcac616e68557427ad9aef6b0ca342a?d=mp&s=160"},"body":"On 03/18/2012 10:29 PM, darxus@chaosreigns.com wrote:\n> I'd like to be able to tell get only that I know the latest commit is bad,\n> and have it go find a good commit, then do the bisecting.  Maybe something\n> like the opposite of a binary search, start with the last commit, then\n> second to last, then 4th to last, 8th to last, etc., till it finds a good\n> commit.\n> \n\nAssuming the good commit is the 13'th from HEAD, you'd get the same nr\nof attempts by just specifying a commit 100 revisions in the past and\ndoing the already implemented binary search as you would from trying 4\ncommits at a time to get at the good one.\n\nBinary search is a \"divide and conquer\" algorithm (running in O(log n)\ntime), so it handles extremely large datasets very efficiently. As such,\nit's (almost) always easier to just specify a revision really far back\nin history and let it get to work. If you specify a range of 1000000\ncommits, it will take 20 attempts to find the right one (\"git bisect\"\nhas to exclude all possible candidates for both sides, so it always\nruns in worst-case time, even when it hits the correct commit on the\nfirst check).\n\n-- \nAndreas Ericsson                   andreas.ericsson@op5.se\nOP5 AB                             www.op5.se\nTel: +46 8-230225                  Fax: +46 8-230231\n\nConsidering the successes of the wars on alcohol, poverty, drugs and\nterror, I think we should give some serious thought to declaring war\non peace.\n"},{"id":"187252","messageId":"20120319153006.GD24848@sigill.intra.peff.net","threadId":"29989","inReplyTo":"4F67468B.4070502@op5.se","subject":"Re: Feature request: don't require both bad and good when bisecting","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-03-19T15:30:06Z","receivedAt":"2012-03-19T15:30:06Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Mar 19, 2012 at 03:45:31PM +0100, Andreas Ericsson wrote:\n\n> On 03/18/2012 10:29 PM, darxus@chaosreigns.com wrote:\n> > I'd like to be able to tell get only that I know the latest commit is bad,\n> > and have it go find a good commit, then do the bisecting.  Maybe something\n> > like the opposite of a binary search, start with the last commit, then\n> > second to last, then 4th to last, 8th to last, etc., till it finds a good\n> > commit.\n> > \n> \n> Assuming the good commit is the 13'th from HEAD, you'd get the same nr\n> of attempts by just specifying a commit 100 revisions in the past and\n> doing the already implemented binary search as you would from trying 4\n> commits at a time to get at the good one.\n> \n> Binary search is a \"divide and conquer\" algorithm (running in O(log n)\n> time), so it handles extremely large datasets very efficiently.\n\nYeah. The OP's suggestion is to search backwards, increasing the stride\nexponentially. That would end up finding a good commit in O(lg n),\nthough not with any great accuracy (e.g., for an old bug, you'd end up\nconsidering the whole first half of history as a single stride).  Since\nbisection would then narrow the result in O(lg n), I think\nasymptotically you are not any better off than you would be just\narbitrarily checking the root commit[1], and then starting the bisection\nfrom there.\n\nBut both schemes run into a problem where old commits are often not very\ntestable. For example, when I am bisecting in git.git, I will run into\nsomething like this:\n\n  1. Some feature is introduced in v1.7.0.\n\n  2. A bug in the feature is introduced in v1.7.2.\n\n  3. Somebody notices and reports the bug in v1.7.5.\n\nThere is no point in testing anything prior to v1.7.0, as your test\ncannot succeed before the feature existed. And worse, it will actively\nbreak a bisection. Pre-v1.7.0 versions will appear buggy, but it is in\nfact a _different_ bug than the one you are searching for (the bug is\nthat the feature isn't there yet). This has been discussed many times on\nthe list, but the short of it is that you will not get sensible\nbisection results if you have multiple bugs (or a bug that comes and\ngoes throughout history).\n\nSo bisect really needs some input from the user to find a sensible\nboundary. And finding that boundary (if the user doesn't already know\nit) is generally a manual thing. Because it is usually easy for a human\nto recognize that the failure mode for points (1) and points (3) above\nare different, but hard to write a script that correctly tests for it.\n\nIOW, my procedure for a bug like the above is usually to walk backwards\nalong major tagged versions, manually interpreting the results. When I\ntry v1.6.0 and my test blows up (because the feature isn't implemented),\nI recognize it, dig a little with \"git log\" to find where it was\nimplemented, and only then write a script for automated bisection.\n\n-Peff\n\n[1] There can also be multiple roots, which makes a backwards-walking\n    algorithm much more complex. I think instead you could simply test\n    and mark all the roots, and then start the bisection from there. But\n    again, you are unlikely to have written a test script that will work\n    on such antique versions of the project.\n"},{"id":"187256","messageId":"4F675DD3.3040004@op5.se","threadId":"29989","inReplyTo":"20120319153006.GD24848@sigill.intra.peff.net","subject":"Re: Feature request: don't require both bad and good when bisecting","fromName":"Andreas Ericsson","fromEmail":"ae@op5.se","sentAt":"2012-03-19T16:24:51Z","receivedAt":"2012-03-19T16:24:51Z","isPatch":false,"sender":{"key":"ae@op5.se","avatar":"https://gravatar.com/avatar/426e89595c75a8f5252dd0c989e5fabe5bcac616e68557427ad9aef6b0ca342a?d=mp&s=160"},"body":"On 03/19/2012 04:30 PM, Jeff King wrote:\n> On Mon, Mar 19, 2012 at 03:45:31PM +0100, Andreas Ericsson wrote:\n> \n>> On 03/18/2012 10:29 PM, darxus@chaosreigns.com wrote:\n>>> I'd like to be able to tell get only that I know the latest commit is bad,\n>>> and have it go find a good commit, then do the bisecting.  Maybe something\n>>> like the opposite of a binary search, start with the last commit, then\n>>> second to last, then 4th to last, 8th to last, etc., till it finds a good\n>>> commit.\n>>>\n>>\n>> Assuming the good commit is the 13'th from HEAD, you'd get the same nr\n>> of attempts by just specifying a commit 100 revisions in the past and\n>> doing the already implemented binary search as you would from trying 4\n>> commits at a time to get at the good one.\n>>\n>> Binary search is a \"divide and conquer\" algorithm (running in O(log n)\n>> time), so it handles extremely large datasets very efficiently.\n> \n> Yeah. The OP's suggestion is to search backwards, increasing the stride\n> exponentially. That would end up finding a good commit in O(lg n),\n> though not with any great accuracy (e.g., for an old bug, you'd end up\n> considering the whole first half of history as a single stride).  Since\n> bisection would then narrow the result in O(lg n), I think\n> asymptotically you are not any better off than you would be just\n> arbitrarily checking the root commit[1], and then starting the bisection\n> from there.\n> \n> But both schemes run into a problem where old commits are often not very\n> testable. For example, when I am bisecting in git.git, I will run into\n> something like this:\n> \n>    1. Some feature is introduced in v1.7.0.\n> \n>    2. A bug in the feature is introduced in v1.7.2.\n> \n>    3. Somebody notices and reports the bug in v1.7.5.\n> \n> There is no point in testing anything prior to v1.7.0, as your test\n> cannot succeed before the feature existed. And worse, it will actively\n> break a bisection.\n\nNot \"break\", as such, but it's naturally left to the user to discover\nwhen the feature the bug is in existed. Usually, that leaves a short-ish\nwindow.\n\nIt's sort of beside the point though. Using git as experiment (again),\nwe're looking at less than 30000 revisions and 289 non-rc tags. With only\n30k revisions, you'll do *worse* testing 15 tags sequentially than you\nwould by just letting the bisection machinery get on with it and use\nthe full history as base for bisection.\n\nOfcourse, if the project is large (as in \"huge tree\"), checking out\neach version will become increasingly expensive the further apart \neach version is, but the time it takes us to diminish the scope is\ngenerally a lot quicker than the time it takes me to remember which\ntag is next to try and then type the command to check it out, so\nover-all, I've found it much more convenient to just give a range\nI know is sufficiently large and then bisecting manually until I\nget in the ballpark of the right range.\n\nAutomatic bisection is a different beast, naturally, since writing\na test-script that handles all corner cases (feature not added,\nfeature added but different bug found, feature added and right bug\nfound, etc) can be cumbersome, but that doesn't always apply, and\ndarxus didn't mention it. He only mentioned \"let's test 4 revisions\nback in history so I can find the good commit!\", and I pointed out\nthat it's ridiculous to do so regardless of whether one has a hunch\nof where the breakage is or not, since it will (almost) always be\n100 times faster to just double the scanned range and let git get\non with it, even if it means doing a manual bisect first to find\nwhen the feature was introduced and then an automated one to find\nwhen the bug came alive.\n\n> Pre-v1.7.0 versions will appear buggy, but it is in\n> fact a _different_ bug than the one you are searching for (the bug is\n> that the feature isn't there yet). This has been discussed many times on\n> the list, but the short of it is that you will not get sensible\n> bisection results if you have multiple bugs (or a bug that comes and\n> goes throughout history).\n> \n> So bisect really needs some input from the user to find a sensible\n> boundary. And finding that boundary (if the user doesn't already know\n> it) is generally a manual thing. Because it is usually easy for a human\n> to recognize that the failure mode for points (1) and points (3) above\n> are different, but hard to write a script that correctly tests for it.\n> \n> IOW, my procedure for a bug like the above is usually to walk backwards\n> along major tagged versions, manually interpreting the results. When I\n> try v1.6.0 and my test blows up (because the feature isn't implemented),\n> I recognize it, dig a little with \"git log\" to find where it was\n> implemented, and only then write a script for automated bisection.\n> \n\nThat means you've tested 81 tags (discarding rc tags between 1.7.6 and\n1.6.0). Compared to binary search, that would correspond to a history\nholding 1208925819614629174706176 revisions. Discarding maint releases,\nwe're down to 14 tags, and you gain (at most) one search on bisection\nat the expense of more typing. Truly a toss-up.\n\nWhat I was getting at is that trying to be more efficient than O(log n)\nis hard and usually requires a really good educated guess to succeed.\nPicking a random number of jumps to go backwards certainly isn't the\nright way to do it, and especially since the problems you mentioned\n(feature missing) will still exist with such a solution.\n\nI managed to use a lot of text to get to that final paragraph. Sorry.\n\n-- \nAndreas Ericsson                   andreas.ericsson@op5.se\nOP5 AB                             www.op5.se\nTel: +46 8-230225                  Fax: +46 8-230231\n\nConsidering the successes of the wars on alcohol, poverty, drugs and\nterror, I think we should give some serious thought to declaring war\non peace.\n"},{"id":"187258","messageId":"20120319164510.GA27601@sigill.intra.peff.net","threadId":"29989","inReplyTo":"4F675DD3.3040004@op5.se","subject":"Re: Feature request: don't require both bad and good when bisecting","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-03-19T16:45:10Z","receivedAt":"2012-03-19T16:45:10Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Mar 19, 2012 at 05:24:51PM +0100, Andreas Ericsson wrote:\n\n> >> On 03/18/2012 10:29 PM, darxus@chaosreigns.com wrote:\n> >>> I'd like to be able to tell get only that I know the latest commit is bad,\n> >>> and have it go find a good commit, then do the bisecting.  Maybe something\n> >>> like the opposite of a binary search, start with the last commit, then\n> >>> second to last, then 4th to last, 8th to last, etc., till it finds a good\n> >>> commit.\n> [...]\n> Automatic bisection is a different beast, naturally, since writing\n> a test-script that handles all corner cases (feature not added,\n> feature added but different bug found, feature added and right bug\n> found, etc) can be cumbersome, but that doesn't always apply, and\n> darxus didn't mention it. He only mentioned \"let's test 4 revisions\n> back in history so I can find the good commit!\", and I pointed out\n> that it's ridiculous to do so regardless of whether one has a hunch\n> of where the breakage is or not, since it will (almost) always be\n> 100 times faster to just double the scanned range and let git get\n> on with it, even if it means doing a manual bisect first to find\n> when the feature was introduced and then an automated one to find\n> when the bug came alive.\n\nHmm. What he wrote is confusing, since he uses \"last\" to refer to the\nlast commit, which would give strides of 2, 2, and then 4. Which makes\nlittle sense to me. I took it to mean \"2nd from the last tested, then\n4th from the last tested, then 8th from the last tested\". I.e., doubling\nthe stride each time.\n\nIf you take it to mean a fixed-size stride (e.g., maxing out at going\nback 4 commits each time), then yes, that is absolutely horrible and\nwill do hundreds of times more work. I took it to mean exponential,\nwhich has OK asymptotic behavior, but IMHO is _still_ not worth it.\n\n> > IOW, my procedure for a bug like the above is usually to walk backwards\n> > along major tagged versions, manually interpreting the results. When I\n> > try v1.6.0 and my test blows up (because the feature isn't implemented),\n> > I recognize it, dig a little with \"git log\" to find where it was\n> > implemented, and only then write a script for automated bisection.\n> \n> That means you've tested 81 tags (discarding rc tags between 1.7.6 and\n> 1.6.0).\n\nActually, I would usually try v1.7.0, then v1.6.0, and so on, depending\non the bug (and then possibly look at minor versions manually). But my\nmain point was that I am using some domain-specific knowledge about what\nconstitutes a good break-point when features might have been added, or\nhow far back is \"reasonable\". For some projects and some features, v0.99\nmight be a reasonable place to look. For git, it is generally not, and\nanything before v1.5.0 is not even worth bisecting.\n\n> What I was getting at is that trying to be more efficient than O(log n)\n> is hard and usually requires a really good educated guess to succeed.\n> Picking a random number of jumps to go backwards certainly isn't the\n> right way to do it, and especially since the problems you mentioned\n> (feature missing) will still exist with such a solution.\n\nOh, absolutely. I should have been more clear in my email: I was\nagreeing with you that the OP's plan was not a good one. My goal wasn't\nto do better than O(log n), but to eliminate the need for the user to\nworry about picking bisection boundaries in the first place.\n\nThat is, in theory, you could have something like this:\n\n  git bisect start-run test.sh\n\nwhich would test HEAD (which generally has the bug, or why are you\nbisecting?), as well as all of the roots (which generally don't,\notherwise there is nothing to bisect). And it isn't much more work to\nbisect because of the logarithmic nature of bisection (e.g., even if you\ninclude 10 times as many commits, that's only ~3 extra bisection steps).\n\nHowever, in practice that does not work because writing a test script to\nhandle antique code-bases automatically is at least as much work as just\nfinding a reasonable bisection boundary in the first place.\n\n> I managed to use a lot of text to get to that final paragraph. Sorry.\n\nThat's OK. I read fast, and I may be guilty of verbosity from time to\ntime, as well. :)\n\n-Peff\n"},{"id":"187259","messageId":"7vobrsbkoe.fsf@alter.siamese.dyndns.org","threadId":"29989","inReplyTo":"4F675DD3.3040004@op5.se","subject":"Re: Feature request: don't require both bad and good when bisecting","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-03-19T16:49:21Z","receivedAt":"2012-03-19T16:49:21Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Andreas Ericsson <ae@op5.se> writes:\n\n> It's sort of beside the point though. Using git as experiment (again),\n> we're looking at less than 30000 revisions and 289 non-rc tags. With only\n> 30k revisions, you'll do *worse* testing 15 tags sequentially than you\n> would by just letting the bisection machinery get on with it and use\n> the full history as base for bisection.\n\nI think you are missing the primary point in what Jeff said.\n\nIt does not matter if you inspect increasingly older versions based on\nexponentially longer strides or if you test tagged releases. What matters\nis to making intelligent determination after seeing a failure, between the\nfailure due to \"the feature being tested did not even exist\" and \"the\nfeature when introduced was good but at this commit it is broken\".\n"}]}