{"thread":{"id":"19515","subject":"RFE: \"git bisect reverse\"","startedAt":"2009-05-26T22:21:36Z","lastAt":"2009-05-31T22:41:47Z","messageCount":18,"participants":["H. Peter Anvin","Sam Vilain","Christian Couder","Nanako Shiraishi","Matthieu Moy","Ealdwulf Wuffinga","Clemens Buchacher"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"114748","messageId":"4A1C6B70.4050501@zytor.com","threadId":"19515","inReplyTo":null,"subject":"RFE: \"git bisect reverse\"","fromName":"H. Peter Anvin","fromEmail":"hpa@zytor.com","sentAt":"2009-05-26T22:21:36Z","receivedAt":"2009-05-26T22:21:36Z","isPatch":false,"sender":{"key":"hpa@zytor.com","avatar":null},"body":"I would like to request the following feature:\n\n\"git bisect reverse\"\n\n... does exactly the same thing as \"git bisect start\", except that it\nflips the meaning of \"good\" and \"bad\".  It is mentally fairly taxing to\ndo a reverse bisection (looking for an antiregression) when one has to\nflip the meaning of \"good\" and \"bad\" (which are very loaded words to our\npsyche), and it's even worse to try to get a user to do it...\n\n\t-hpa\n"},{"id":"114754","messageId":"4A1CACB2.7000702@vilain.net","threadId":"19515","inReplyTo":"4A1C6B70.4050501@zytor.com","subject":"Re: RFE: \"git bisect reverse\"","fromName":"Sam Vilain","fromEmail":"sam@vilain.net","sentAt":"2009-05-27T03:00:02Z","receivedAt":"2009-05-27T03:00:02Z","isPatch":false,"sender":{"key":"sam@vilain.net","avatar":"https://gravatar.com/avatar/8fc840ca854dbf6f7065b4335e3b934951c1dca3b11db688e95e471901f8f4a8?d=mp&s=160"},"body":"H. Peter Anvin wrote:\n> I would like to request the following feature:\n>\n> \"git bisect reverse\"\n>\n> ... does exactly the same thing as \"git bisect start\", except that it\n> flips the meaning of \"good\" and \"bad\".  It is mentally fairly taxing to\n> do a reverse bisection (looking for an antiregression) when one has to\n> flip the meaning of \"good\" and \"bad\" (which are very loaded words to our\n> psyche), and it's even worse to try to get a user to do it...\n>   \n\nOh, yes.  And another thing: 'git bisect run' / 'git bisect skip'\ndoesn't do a very good job of skipping around broken commits (ie when\nthe script returns 126).  It just seems to move to the next one; it\nwould be much better IMHO to first try the commit 1/3rd of the way into\nthe range, then if that fails, the commit 2/3rd of the way through it, etc.\n\nSam.\n"},{"id":"114761","messageId":"4A1CBF7A.3090708@zytor.com","threadId":"19515","inReplyTo":"4A1CACB2.7000702@vilain.net","subject":"Re: RFE: \"git bisect reverse\"","fromName":"H. Peter Anvin","fromEmail":"hpa@zytor.com","sentAt":"2009-05-27T04:20:10Z","receivedAt":"2009-05-27T04:20:10Z","isPatch":false,"sender":{"key":"hpa@zytor.com","avatar":null},"body":"Sam Vilain wrote:\n> \n> Oh, yes.  And another thing: 'git bisect run' / 'git bisect skip'\n> doesn't do a very good job of skipping around broken commits (ie when\n> the script returns 126).  It just seems to move to the next one; it\n> would be much better IMHO to first try the commit 1/3rd of the way into\n> the range, then if that fails, the commit 2/3rd of the way through it, etc.\n> \n\nI posted about that last year:\n\nhttp://marc.info/?l=git&i=48F3DCEB.1060803@zytor.com\n\nAt the time, git bisect was still done in the shell and it was deemed\ntoo difficult.\n\n\t-hpa\n\n-- \nH. Peter Anvin, Intel Open Source Technology Center\nI work for Intel.  I don't speak on their behalf.\n"},{"id":"114768","messageId":"200905270726.59883.chriscool@tuxfamily.org","threadId":"19515","inReplyTo":"4A1CBF7A.3090708@zytor.com","subject":"Re: RFE: \"git bisect reverse\"","fromName":"Christian Couder","fromEmail":"chriscool@tuxfamily.org","sentAt":"2009-05-27T05:26:59Z","receivedAt":"2009-05-27T05:26:59Z","isPatch":false,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"Le Wednesday 27 May 2009, H. Peter Anvin a écrit :\n> Sam Vilain wrote:\n> > Oh, yes.  And another thing: 'git bisect run' / 'git bisect skip'\n> > doesn't do a very good job of skipping around broken commits (ie when\n> > the script returns 126).  It just seems to move to the next one; it\n> > would be much better IMHO to first try the commit 1/3rd of the way into\n> > the range, then if that fails, the commit 2/3rd of the way through it,\n> > etc.\n>\n> I posted about that last year:\n>\n> http://marc.info/?l=git&i=48F3DCEB.1060803@zytor.com\n>\n> At the time, git bisect was still done in the shell and it was deemed\n> too difficult.\n\nYeah, this was also asked by Ingo, and yeah, I think it should be easier to \ndo now that most of the \"git bisect next\" shell code has been ported to C.\n\nI will try to have a look at it soon.\n\nBest regards,\nChristian.\n"},{"id":"114783","messageId":"20090527172233.6117@nanako3.lavabit.com","threadId":"19515","inReplyTo":"4A1C6B70.4050501@zytor.com","subject":"Re: RFE: \"git bisect reverse\"","fromName":"Nanako Shiraishi","fromEmail":"nanako3@lavabit.com","sentAt":"2009-05-27T08:22:33Z","receivedAt":"2009-05-27T08:22:33Z","isPatch":false,"sender":{"key":"nanako3@lavabit.com","avatar":"https://gravatar.com/avatar/3777b9e201c5883a62b1a6fdf7c53f2d712d1d80989146063ea861e33aad72a8?d=mp&s=160"},"body":"Quoting \"H. Peter Anvin\" <hpa@zytor.com>:\n\n> I would like to request the following feature:\n>\n> \"git bisect reverse\"\n>\n> ... does exactly the same thing as \"git bisect start\", except that it\n> flips the meaning of \"good\" and \"bad\".  It is mentally fairly taxing to\n> do a reverse bisection (looking for an antiregression) when one has to\n> flip the meaning of \"good\" and \"bad\" (which are very loaded words to our\n> psyche), and it's even worse to try to get a user to do it...\n\nThere was a discussion on \"fixed\" and \"unfixed\" aliases to find a commit that fixed an old breakage.\n\n  http://thread.gmane.org/gmane.comp.version-control.git/86063/focus=86563\n\n-- \nNanako Shiraishi\nhttp://ivory.ap.teacup.com/nanako3/\n"},{"id":"114833","messageId":"200905272211.59542.chriscool@tuxfamily.org","threadId":"19515","inReplyTo":"4A1CACB2.7000702@vilain.net","subject":"Re: RFE: \"git bisect reverse\"","fromName":"Christian Couder","fromEmail":"chriscool@tuxfamily.org","sentAt":"2009-05-27T20:11:59Z","receivedAt":"2009-05-27T20:11:59Z","isPatch":false,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"Le Wednesday 27 May 2009, Sam Vilain a écrit :\n> H. Peter Anvin wrote:\n> > I would like to request the following feature:\n> >\n> > \"git bisect reverse\"\n> >\n> > ... does exactly the same thing as \"git bisect start\", except that it\n> > flips the meaning of \"good\" and \"bad\".  It is mentally fairly taxing to\n> > do a reverse bisection (looking for an antiregression) when one has to\n> > flip the meaning of \"good\" and \"bad\" (which are very loaded words to\n> > our psyche), and it's even worse to try to get a user to do it...\n>\n> Oh, yes.  And another thing: 'git bisect run' / 'git bisect skip'\n> doesn't do a very good job of skipping around broken commits (ie when\n> the script returns 126).\n\ns/126/125/\n\n> It just seems to move to the next one; it \n> would be much better IMHO to first try the commit 1/3rd of the way into\n> the range, then if that fails, the commit 2/3rd of the way through it,\n> etc.\n\nRegards,\nChristian.\n"},{"id":"114836","messageId":"vpqprdue1ie.fsf@bauges.imag.fr","threadId":"19515","inReplyTo":"20090527172233.6117@nanako3.lavabit.com","subject":"Re: RFE: \"git bisect reverse\"","fromName":"Matthieu Moy","fromEmail":"matthieu.moy@imag.fr","sentAt":"2009-05-27T20:26:01Z","receivedAt":"2009-05-27T20:26:01Z","isPatch":false,"sender":{"key":"git@matthieu-moy.fr","avatar":"https://avatars.githubusercontent.com/u/14709?v=4"},"body":"Nanako Shiraishi <nanako3@lavabit.com> writes:\n\n> Quoting \"H. Peter Anvin\" <hpa@zytor.com>:\n>\n>> I would like to request the following feature:\n>>\n>> \"git bisect reverse\"\n>>\n>> ... does exactly the same thing as \"git bisect start\", except that it\n>> flips the meaning of \"good\" and \"bad\".  It is mentally fairly taxing to\n>> do a reverse bisection (looking for an antiregression) when one has to\n>> flip the meaning of \"good\" and \"bad\" (which are very loaded words to our\n>> psyche), and it's even worse to try to get a user to do it...\n>\n> There was a discussion on \"fixed\" and \"unfixed\" aliases to find a commit that fixed an old breakage.\n>\n>   http://thread.gmane.org/gmane.comp.version-control.git/86063/focus=86563\n\nI think the bzr \"bisect\" plugin uses \"yes\" and \"no\" instead for this\nreason. I find it mentally easier to adapt it to both cases (\"yes,\nit's fixed\" or \"yes, it's broken\" depending on what you search).\n\n-- \nMatthieu\n"},{"id":"114840","messageId":"efe2b6d70905271411g4e1616b5w548141ee9fab2c14@mail.gmail.com","threadId":"19515","inReplyTo":"200905270726.59883.chriscool@tuxfamily.org","subject":"Re: RFE: \"git bisect reverse\"","fromName":"Ealdwulf Wuffinga","fromEmail":"ealdwulf@googlemail.com","sentAt":"2009-05-27T21:11:35Z","receivedAt":"2009-05-27T21:11:35Z","isPatch":false,"sender":{"key":"ealdwulf@googlemail.com","avatar":null},"body":">> Sam Vilain wrote:\n>> > Oh, yes.  And another thing: 'git bisect run' / 'git bisect skip'\n>> > doesn't do a very good job of skipping around broken commits (ie when\n>> > the script returns 126).  It just seems to move to the next one; it\n>> > would be much better IMHO to first try the commit 1/3rd of the way into\n>> > the range, then if that fails, the commit 2/3rd of the way through it,\n>> > etc.\n\nAs I understand it, the idea is that the probability that a commit is\nbroken is greater if it is close in the DAG to a known-broken commit.\nI wonder if this can be made more concrete? Can we derive a formula\nfor, or collect empriical data on, these probabilities?\n\nThe reason I ask is that I am wondering how this feature might be\nimplemented in bbchop\n(http://github.com/Ealdwulf/bbchop/tree/master) which is an extension\nof git-bisect\nto the case where the bug is intermittent. It works by calculating the\nprobability that the\nbug was introduced at each commit, and asking about that commit which\nhas the largest\nexpected information gain. Currently if there is a skip I just set the\nprobability\nfor that commit to zero, so the algorithm is likely to ask next about\nan adjacent one,\njust as in git-bisect. A natural way to extend bbchop to this use case\nwould be for\nthe information gain calculation to take into account the probability\nthat a commit is broken.\n\nSo I would need some plausible way of calculating that probability. It\nis not immediately\nobvious to me what that would be, or what assumptions would be useful.\n\nEaldwulf\n"},{"id":"114841","messageId":"20090527211836.GA14841@localhost","threadId":"19515","inReplyTo":"efe2b6d70905271411g4e1616b5w548141ee9fab2c14@mail.gmail.com","subject":"Re: RFE: \"git bisect reverse\"","fromName":"Clemens Buchacher","fromEmail":"drizzd@aon.at","sentAt":"2009-05-27T21:18:36Z","receivedAt":"2009-05-27T21:18:36Z","isPatch":false,"sender":{"key":"drizzd@gmx.net","avatar":"https://avatars.githubusercontent.com/u/59082?v=4"},"body":"On Wed, May 27, 2009 at 10:11:35PM +0100, Ealdwulf Wuffinga wrote:\n> >> Sam Vilain wrote:\n> >> > Oh, yes.  And another thing: 'git bisect run' / 'git bisect skip'\n> >> > doesn't do a very good job of skipping around broken commits (ie when\n> >> > the script returns 126).  It just seems to move to the next one; it\n> >> > would be much better IMHO to first try the commit 1/3rd of the way into\n> >> > the range, then if that fails, the commit 2/3rd of the way through it,\n> >> > etc.\n> \n> As I understand it, the idea is that the probability that a commit is\n> broken is greater if it is close in the DAG to a known-broken commit.\n> I wonder if this can be made more concrete? Can we derive a formula\n> for, or collect empriical data on, these probabilities?\n\nNo. The idea is that we want to reduce to bisect as close to the middle as\npossible so we only have to do log2(n) tests. But if a commit is skipped,\nthat means we cannot decide whether the test passes or fails for this\ncommit. But if we choose a commit close to the skipped one, we will likely\nhave to skip the that one for the same reason.\n"},{"id":"114844","messageId":"efe2b6d70905271507s187babe9yf19a25268ab0b95e@mail.gmail.com","threadId":"19515","inReplyTo":"20090527211836.GA14841@localhost","subject":"Re: RFE: \"git bisect reverse\"","fromName":"Ealdwulf Wuffinga","fromEmail":"ealdwulf@googlemail.com","sentAt":"2009-05-27T22:07:50Z","receivedAt":"2009-05-27T22:07:50Z","isPatch":false,"sender":{"key":"ealdwulf@googlemail.com","avatar":null},"body":"On Wed, May 27, 2009 at 10:18 PM, Clemens Buchacher <drizzd@aon.at> wrote:\n> On Wed, May 27, 2009 at 10:11:35PM +0100, Ealdwulf Wuffinga wrote:\n>> >> Sam Vilain wrote:\n>> >> > Oh, yes.  And another thing: 'git bisect run' / 'git bisect skip'\n>> >> > doesn't do a very good job of skipping around broken commits (ie when\n>> >> > the script returns 126).  It just seems to move to the next one; it\n>> >> > would be much better IMHO to first try the commit 1/3rd of the way into\n>> >> > the range, then if that fails, the commit 2/3rd of the way through it,\n>> >> > etc.\n>>\n>> As I understand it, the idea is that the probability that a commit is\n>> broken is greater if it is close in the DAG to a known-broken commit.\n>> I wonder if this can be made more concrete? Can we derive a formula\n>> for, or collect empriical data on, these probabilities?\n>\n> No. The idea is that we want to reduce to bisect as close to the middle as\n> possible so we only have to do log2(n) tests. But if a commit is skipped,\n> that means we cannot decide whether the test passes or fails for this\n> commit. But if we choose a commit close to the skipped one, we will likely\n> have to skip the that one for the same reason.\n\nYou say 'no', but your explanation does not appear to contradict what\nI have said.\nI am not sure what you are disagreeing with?\n\nI agree, the whole point is to do the bisection in as few tests as possible.\nThis means that the test must gain the maximum information possible,\nwhich in the\ndeterministic case (git-bisect) means testing in the middle. For the\nnon-deterministic case,\nin bbchop, I directly calculate the information gain of each potential\ntest, then choose the greatest.\n\nThe question is how to avoid skips, which gain no information. You say\n'if we choose a commit close to the skipped one, we will likely have\nto skip the that one'. This is what I meant by 'the idea is that the\nprobability that a commit is broken is greater if it is close in the\nDAG to a known-broken commit'. Maybe you are reading this as 'bad\ncommit', but this is not the sense in which Sam is using the term.\n\nFor git-bisect, Sam and H Peter are proposing a heuristic to trade off\nbetween information gained and likelihood of testing a bad commit. For\nbbchop, I am already doing calculating the information gain directly,\nso if I can incorporate the probability that a commit is broken - has\nto be skipped - then the trade-off will happen automatically.\nTherefore it would be useful to have some plausible theory as to how\nthe probability of a broken commit should be calculated, given some\nknown-broken and known-not-broken commits.\n\nEaldwulf\n"},{"id":"114861","messageId":"4A1DC7D8.2050601@vilain.net","threadId":"19515","inReplyTo":"efe2b6d70905271507s187babe9yf19a25268ab0b95e@mail.gmail.com","subject":"Re: RFE: \"git bisect reverse\"","fromName":"Sam Vilain","fromEmail":"sam@vilain.net","sentAt":"2009-05-27T23:08:08Z","receivedAt":"2009-05-27T23:08:08Z","isPatch":false,"sender":{"key":"sam@vilain.net","avatar":"https://gravatar.com/avatar/8fc840ca854dbf6f7065b4335e3b934951c1dca3b11db688e95e471901f8f4a8?d=mp&s=160"},"body":"Ealdwulf Wuffinga wrote:\n> The question is how to avoid skips, which gain no information. You say\n> 'if we choose a commit close to the skipped one, we will likely have\n> to skip the that one'. This is what I meant by 'the idea is that the\n> probability that a commit is broken is greater if it is close in the\n> DAG to a known-broken commit'. Maybe you are reading this as 'bad\n> commit', but this is not the sense in which Sam is using the term.\n>\n> For git-bisect, Sam and H Peter are proposing a heuristic to trade off\n> between information gained and likelihood of testing a bad commit. For\n> bbchop, I am already doing calculating the information gain directly,\n> so if I can incorporate the probability that a commit is broken - has\n> to be skipped - then the trade-off will happen automatically.\n> Therefore it would be useful to have some plausible theory as to how\n> the probability of a broken commit should be calculated, given some\n> known-broken and known-not-broken commits.\n>   \n\nSounds like interesting stuff, can you make a patch out of it?\n\nActually it occurs to me that for projects which can successfully\nrebuild with just 'make' for each new revision and have a stable commit\npolicy, walking through commits forwards like that is probably the right\nthing to do, because it's relatively cheap and should make progress in\nthe lowest amount of time.  So the current behaviour should probably\nstill be available.\n\nSam\n"},{"id":"114872","messageId":"4A1E00F1.4030709@zytor.com","threadId":"19515","inReplyTo":"efe2b6d70905271507s187babe9yf19a25268ab0b95e@mail.gmail.com","subject":"Re: RFE: \"git bisect reverse\"","fromName":"H. Peter Anvin","fromEmail":"hpa@zytor.com","sentAt":"2009-05-28T03:11:45Z","receivedAt":"2009-05-28T03:11:45Z","isPatch":false,"sender":{"key":"hpa@zytor.com","avatar":null},"body":"Ealdwulf Wuffinga wrote:\n> \n> For git-bisect, Sam and H Peter are proposing a heuristic to trade off\n> between information gained and likelihood of testing a bad commit. For\n> bbchop, I am already doing calculating the information gain directly,\n> so if I can incorporate the probability that a commit is broken - has\n> to be skipped - then the trade-off will happen automatically.\n> Therefore it would be useful to have some plausible theory as to how\n> the probability of a broken commit should be calculated, given some\n> known-broken and known-not-broken commits.\n> \n\nAgain, given a bisection, the information gain by \"bisecting\" at point x\n where 0 < x < 1 is:\n\n\t-(x log2 x)-((1-x) log2 (1-x))\n\nAt x = 0.5 this gives the optimal 1 bit, but the curve is rather flat\nnear the top.  You don't drop to 1/2 bit of information until\nx = 0.11 or 0.89, and it doesn't drop to 1/4 bit of information until\nx = 0.04 or 0.96.\n\nThus, the lack of optimality in searching away from a skip point is much\nsmaller than the potential cost of having to having to skip multiple\nnearby points.\n\n\t-hpa\n\n-- \nH. Peter Anvin, Intel Open Source Technology Center\nI work for Intel.  I don't speak on their behalf.\n"},{"id":"114957","messageId":"efe2b6d70905281329s1ae5a94coe5875714f341d5a9@mail.gmail.com","threadId":"19515","inReplyTo":"4A1DC7D8.2050601@vilain.net","subject":"Re: RFE: \"git bisect reverse\"","fromName":"Ealdwulf Wuffinga","fromEmail":"ealdwulf@googlemail.com","sentAt":"2009-05-28T20:29:26Z","receivedAt":"2009-05-28T20:29:26Z","isPatch":false,"sender":{"key":"ealdwulf@googlemail.com","avatar":null},"body":"On Thu, May 28, 2009 at 12:08 AM, Sam Vilain <sam@vilain.net> wrote:\n> Ealdwulf Wuffinga wrote:\n\n>> [some time back] http://github.com/Ealdwulf/bbchop/tree/master\n\n>> For git-bisect, Sam and H Peter are proposing a heuristic to trade off\n>> between information gained and likelihood of testing a bad commit. For\n>> bbchop, I am already doing calculating the information gain directly,\n>> so if I can incorporate the probability that a commit is broken - has\n>> to be skipped - then the trade-off will happen automatically.\n>> Therefore it would be useful to have some plausible theory as to how\n>> the probability of a broken commit should be calculated, given some\n>> known-broken and known-not-broken commits.\n>>\n>\n> Sounds like interesting stuff, can you make a patch out of it?\n\nThe code as it stands will actually work with an unmodified git.\nWhat it doesn't yet have is a 'git-bisect'-like frontend, which is the only\npart which would actually require modifying (or just adding to) git itself.\n\nIt does already interface to the git plumbing, so you can try it out if you\ndon't mind using a slightly ungitlike  interface.\n\nI assume it's not worth doing a patch which would just copy my tree\ninto the git source tree?\n\nThere was also, last time I mentioned this on the list, some question\nas to whether it was acceptable to add something written in python to\ngit.\n\nEaldwulf\n"},{"id":"114963","messageId":"efe2b6d70905281407x56bb788aq3dba4b27eb91d7a6@mail.gmail.com","threadId":"19515","inReplyTo":"4A1E00F1.4030709@zytor.com","subject":"Re: RFE: \"git bisect reverse\"","fromName":"Ealdwulf Wuffinga","fromEmail":"ealdwulf@googlemail.com","sentAt":"2009-05-28T21:07:29Z","receivedAt":"2009-05-28T21:07:29Z","isPatch":false,"sender":{"key":"ealdwulf@googlemail.com","avatar":null},"body":"On Thu, May 28, 2009 at 4:11 AM, H. Peter Anvin <hpa@zytor.com> wrote:\n\n> Again, given a bisection, the information gain by \"bisecting\" at point x\n>  where 0 < x < 1 is:\n>\n>        -(x log2 x)-((1-x) log2 (1-x))\n>\n> At x = 0.5 this gives the optimal 1 bit, but the curve is rather flat\n> near the top.  You don't drop to 1/2 bit of information until\n> x = 0.11 or 0.89, and it doesn't drop to 1/4 bit of information until\n> x = 0.04 or 0.96.\n>\n> Thus, the lack of optimality in searching away from a skip point is much\n> smaller than the potential cost of having to having to skip multiple\n> nearby points.\n\n\nI understand that. I didn't mean to imply that there was anything\nwrong with your proposal, indeed, it makes sense for git-bisect.\n\nWhat I am interested in is how to extend bisection to the case of\nintermittent bugs; where a test which observes the fault means that it\ncannot have been introduced in subsequent commits, but a test which\ndoes not observe the fault cannot guarantee that it must have been\nintroduced in a subsequent commit.\n\nThe simplest way to deal with this is to try to reduce it to the\ndeterministic case\nby repeating the test some number of times. It turns out, that this is\nrather inefficient.\n\nIn bbchop, the search algorithm does not assume that the test is deterministic.\nTherefore, it has to calculate the probabilities in order to know when it has\naccumulated enough evidence to accuse a particular commit. It turns\nout that it is not much more expensive to calculate which commit we\ncan expect to  gain the most information from by testing it next.\n\nHow can I incorporate your skipping feature into this model? The problem is that\nwhile (just thinking about the linear case for the moment) there is a\nfixed boundary at one end - where we actually saw a fault - on the\nother side there are a bunch of fuzzy probabilities, ultimately\nbounded by wherever we decided the limit of the search was.\nSo when we get a skip we could hop half way toward the limit. That\nwould be reasonable toward the beginning of the search, but towards\nthe end when most of the probability is concentrated in a small number\nof commits, it would make no sense.\n\nIt would fit a lot better into this algorithm to have some model of\nthe probability that a commit will cause a skip. It doesn't actually\nhave to be a very good one, because if it's poor it will only make the\nsearch slightly less efficient, not affect the reliability of the\nfinal result.\n\nEaldwulf\n"},{"id":"114972","messageId":"4A1F07FA.6040008@zytor.com","threadId":"19515","inReplyTo":"efe2b6d70905281407x56bb788aq3dba4b27eb91d7a6@mail.gmail.com","subject":"Re: RFE: \"git bisect reverse\"","fromName":"H. Peter Anvin","fromEmail":"hpa@zytor.com","sentAt":"2009-05-28T21:54:02Z","receivedAt":"2009-05-28T21:54:02Z","isPatch":false,"sender":{"key":"hpa@zytor.com","avatar":null},"body":"Ealdwulf Wuffinga wrote:\n> \n> It would fit a lot better into this algorithm to have some model of\n> the probability that a commit will cause a skip. It doesn't actually\n> have to be a very good one, because if it's poor it will only make the\n> search slightly less efficient, not affect the reliability of the\n> final result.\n> \n\nHow about simply modelling it linearly, with 100% probability for known\nskip point, 0% for a known good/bad point, and a linear gradient in\nbetween?  It's probably a good enough model.  In practice, it will\nvastly overestimate the probability of a skip, so if a linear model\nturns out to be too conservative, I would probably just try to model it\nas a higher-order power function.\n\n\t-hpa\n"},{"id":"114980","messageId":"4A1F628F.9010407@vilain.net","threadId":"19515","inReplyTo":"efe2b6d70905281329s1ae5a94coe5875714f341d5a9@mail.gmail.com","subject":"Re: RFE: \"git bisect reverse\"","fromName":"Sam Vilain","fromEmail":"sam@vilain.net","sentAt":"2009-05-29T04:20:31Z","receivedAt":"2009-05-29T04:20:31Z","isPatch":false,"sender":{"key":"sam@vilain.net","avatar":"https://gravatar.com/avatar/8fc840ca854dbf6f7065b4335e3b934951c1dca3b11db688e95e471901f8f4a8?d=mp&s=160"},"body":"Ealdwulf Wuffinga wrote:\n>> Sounds like interesting stuff, can you make a patch out of it?\n>>     \n>\n> The code as it stands will actually work with an unmodified git.\n> What it doesn't yet have is a 'git-bisect'-like frontend, which is the only\n> part which would actually require modifying (or just adding to) git itself.\n>\n> It does already interface to the git plumbing, so you can try it out if you\n> don't mind using a slightly ungitlike  interface.\n>\n> I assume it's not worth doing a patch which would just copy my tree\n> into the git source tree?\n>\n> There was also, last time I mentioned this on the list, some question\n> as to whether it was acceptable to add something written in python to\n> git.\n>   \n\nI mean, can you port your algorithm from python to the git-bisect C\nsource and therefore make something of benefit to existing 'git bisect'\nusers ?\n\nSam.\n"},{"id":"115167","messageId":"efe2b6d70905311518w4c2d79ecy8cdabd15a8effc7c@mail.gmail.com","threadId":"19515","inReplyTo":"4A1F07FA.6040008@zytor.com","subject":"Re: RFE: \"git bisect reverse\"","fromName":"Ealdwulf Wuffinga","fromEmail":"ealdwulf@googlemail.com","sentAt":"2009-05-31T22:18:20Z","receivedAt":"2009-05-31T22:18:20Z","isPatch":false,"sender":{"key":"ealdwulf@googlemail.com","avatar":null},"body":"On Thu, May 28, 2009 at 10:54 PM, H. Peter Anvin <hpa@zytor.com> wrote:\n\n> How about simply modelling it linearly, with 100% probability for known\n> skip point, 0% for a known good/bad point, and a linear gradient in\n> between?  It's probably a good enough model.  In practice, it will\n> vastly overestimate the probability of a skip, so if a linear model\n> turns out to be too conservative, I would probably just try to model it\n> as a higher-order power function.\n\nSounds plausible. It's not obvious how to generalise it to a DAG, though.\n\nWhat's easier to implement is simple geometric decay (from a\nprobability of 1 at the commit of an actual skip).  It even has a\nplausible rationale - the probability that someone notices the\nbrokenness\nand fixes it is probably a constant, which would lead to geometric\ndecay. That probably doesn't reflect what happens when someone breaks\na whole swath of stuff retrospectively somehow, though.\n\nI've implemented geometric (and arithmetic) decay in bbchop, with a\nconfigurable decay factor. With a factor sufficiently close to one\n(eg, 0.99) it can be persuaded to hop a reasonable distance, which\nseems to scale to a certain extent with the number of commits left, so\nhopefully it won't be necessary to fiddle with the factor a lot.\n\nhttp://github.com/Ealdwulf/bbchop/tree/master\n\nEaldwulf\n"},{"id":"115168","messageId":"efe2b6d70905311541y2576ef0enc66d619672d4ef34@mail.gmail.com","threadId":"19515","inReplyTo":"4A1F628F.9010407@vilain.net","subject":"Re: RFE: \"git bisect reverse\"","fromName":"Ealdwulf Wuffinga","fromEmail":"ealdwulf@googlemail.com","sentAt":"2009-05-31T22:41:47Z","receivedAt":"2009-05-31T22:41:47Z","isPatch":false,"sender":{"key":"ealdwulf@googlemail.com","avatar":null},"body":"On Fri, May 29, 2009 at 5:20 AM, Sam Vilain <sam@vilain.net> wrote:\n\n>\n> I mean, can you port your algorithm from python to the git-bisect C\n> source and therefore make something of benefit to existing 'git bisect'\n> users ?\n\nI haven't really looked at the git bisect code yet, but the algorithms\nare so different that it would likely make the most sense to just add\nmy algorithm in parallel, rather than trying to combine them.\n(Although my algorithm can handle the deterministic case as well,\nyou'd want to keep the original one too, because mine starts to get a\nbit sluggish deciding which commit to test for larger commit ranges. )\nIt could still be driven by git-bisect script, though.\n\nConverting it to C wouldn't be a trivial task, though, so I may not\nget around to it. I'll probably write a more git-like frontend, and\nmaybe submit a patch to add it to  the contrib directory, to get a\nbetter idea of whether\nthere are actually any users for this feature, before deciding whether\nto do the conversion.\n\nEaldwulf\n"}]}