{"thread":{"id":"966","subject":"git-rev-list: \"--bisect\" flag","startedAt":"2005-06-18T06:31:37Z","lastAt":"2005-06-20T14:37:52Z","messageCount":19,"participants":["Linus Torvalds","Jon Seymour","Jan Harkes","David Lang","Ingo Molnar"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"5014","messageId":"Pine.LNX.4.58.0506172306210.2268@ppc970.osdl.org","threadId":"966","inReplyTo":null,"subject":"git-rev-list: \"--bisect\" flag","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-06-18T06:31:37Z","receivedAt":"2005-06-18T06:31:37Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nOk, I just added a feature to \"git-rev-list\" that I hereby nominate to be\nthe coolest feature ever, namely the \"--bisect\" flag, which basically\ntries to split the list of revisions in two, and prints out just the \"most\nmiddle\" commit.\n\nThe idea is that you want to do binary-search for a bug, but since the git\nhistory isn't a nice linear thing, you don't know where the hell the\nmid-point is between two commits, and even if you _do_ know where it is,\nit gets even more complicated when you have 3 points (on different\nbranches) that are known good, and one point that is known bad.\n\nNow, assuming you have three known-good points, and one known bad point, \nthe way to get all commits in between is\n\n\tgit-rev-list bad ^good1 ^good2 ^good3\n\nand with the new flag you can now trivially get an estimate for what the \nmid-point is in this list. So you just do\n\n\tgit-rev-list --bisect bad ^good1 ^good2 ^good3\n\nand you now have the point to test. If testing shows that mid-way-point \nwas bad, you just continue with that as a \"new bad\":\n\n\tgit-rev-list --bisect new-bad ^good1 ^good2 ^good3\n\nbut if it shows that that point was still good, you instead just add it to \nthe list of uninteresting commits, and do\n\n\tgit-rev-list --bisect bad ^good1 ^good2 ^good3 ^new-good\n\ninstead. Every iteration you basically cut down the number of commits by \nhalf - you're bisecting the set, and binary-searching for the first bad \ncommit.\n\nNote that git also makes resetting to the test-point be really trivial: \nyou just do\n\n\tgit-read-tree -m -u \n\nwhere \"prev-point\" was your previous state (ie usually \"HEAD\" the first \ntime, but the previous test-point otherwise), and \"test-point\" is the new \npoint you want to test.\n\nI haven't scripted this, but it should basically be pretty easy to add a\ncouple of simple scripts to make it very easy to do the binary search be\ntotally automated, assuming just a simple \"mark test as failed/good\" \ninterface. Even without the scripting, it shouldn't be that hard to do\nentirely by hand.\n\nThe idea being that if you notice that something doesn't work (usually in \nHEAD), but you know it used to work in the previous release, you just \nstart the whole thing going with\n\n\t# set up initial state\n\tcat .git/HEAD > .git/BAD\n\tcat .git/HEAD > .git/CURRENT\n\techo \"^v2.6.12\" > .git/GOOD\n\nand then you just do something like:\n\n\t# iterate\n\tgit-rev-list --bisect BAD $(cat .git/BAD) > .git/HALFWAY\n\tif [ ! -s .git/HALFWAY ]; then\n\t\techo FOUND IT:\n\t\tcat .git/CURRENT\n\t\texit 1\n\tfi\n\tgit-read-tree -m -u CURRENT HALFWAY\n\tcat .git/HALFWAY > .git/CURRENT\n\n\tmake ..\n\n\n\t# if good\n\techo '^'$(cat .git/CURENT) >> .git/GOOD\n\t.. iterate ..\n\n\t# if bad\n\tcat .git/CURRENT > .git/BAD\n\t.. iterate ..\n\nuntil it says \"FOUND IT\".\n\n(The above is untested, but the --bisect behaviour itself I tested, and it \nseems to do the right thing).\n\nNOTE! I'm not convinced I actually find a particularly good place to split \nat, but I think my stupid \"halfway point\" decision is good enough in \npractice. So it might not really be a real binary search, but I think it \ncomes pretty close to it unless you have some really odd cases.\n\n\t\t\tLinus\n"},{"id":"5025","messageId":"2cfc403205061817181e4d6d5e@mail.gmail.com","threadId":"966","inReplyTo":"Pine.LNX.4.58.0506172306210.2268@ppc970.osdl.org","subject":"Re: git-rev-list: \"--bisect\" flag","fromName":"Jon Seymour","fromEmail":"jon.seymour@gmail.com","sentAt":"2005-06-19T00:18:45Z","receivedAt":"2005-06-19T00:18:45Z","isPatch":false,"sender":{"key":"jon.seymour@gmail.com","avatar":"https://avatars.githubusercontent.com/u/207131?v=4"},"body":"On 6/18/05, Linus Torvalds wrote:\n> \n> Ok, I just added a feature to \"git-rev-list\" that I hereby nominate to be\n> the coolest feature ever, namely the \"--bisect\" flag, which basically\n> tries to split the list of revisions in two, and prints out just the \"most\n> middle\" commit.\n> \n\nPerhaps in answering this question, you can help me understand the\nintended behaviour of your bisection algorithm a little better. The\nquestion is this: for your purposes, given a rev-list output, why not\nsimply use the literal middle element of the outputed list?\n\njon.\n"},{"id":"5026","messageId":"20050619033821.GB24982@delft.aura.cs.cmu.edu","threadId":"966","inReplyTo":"2cfc403205061817181e4d6d5e@mail.gmail.com","subject":"Re: git-rev-list: \"--bisect\" flag","fromName":"Jan Harkes","fromEmail":"jaharkes@cs.cmu.edu","sentAt":"2005-06-19T03:38:22Z","receivedAt":"2005-06-19T03:38:22Z","isPatch":false,"sender":{"key":"jaharkes@cs.cmu.edu","avatar":"https://gravatar.com/avatar/cf95aecd150ca8ef33d6edc337ac4bb9e13aa4246fc3679257d578c7fddc1633?d=mp&s=160"},"body":"On Sun, Jun 19, 2005 at 10:18:45AM +1000, Jon Seymour wrote:\n> On 6/18/05, Linus Torvalds wrote:\n> > \n> > Ok, I just added a feature to \"git-rev-list\" that I hereby nominate to be\n> > the coolest feature ever, namely the \"--bisect\" flag, which basically\n> > tries to split the list of revisions in two, and prints out just the \"most\n> > middle\" commit.\n> > \n> \n> Perhaps in answering this question, you can help me understand the\n> intended behaviour of your bisection algorithm a little better. The\n> question is this: for your purposes, given a rev-list output, why not\n> simply use the literal middle element of the outputed list?\n\nA was known good, parallel development for commits B and C, finally\nmerged into D. A bug got introduced in B, which we discover by the time\nwe have a checked out copy of D.\n\n .--- B ---.\n / \\\n A D\n \\ /\n `--- C ---'\n\ngit-rev-list E ^A shows this as BCD. Pick the halfway point C, and this\none checks out ok. So at this point we would decide that the bug got\nintroduced by the C->D change.\n\nMy guess is that Linus's bisect algorithm considers the branches, so\nonce C is cleared as good, we get a rev-list that looks like BD, and as\nsuch can still find the exact bad commit B.\n\nJan\n"},{"id":"5027","messageId":"Pine.LNX.4.58.0506182022130.2268@ppc970.osdl.org","threadId":"966","inReplyTo":"2cfc403205061817181e4d6d5e@mail.gmail.com","subject":"Re: git-rev-list: \"--bisect\" flag","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-06-19T03:43:04Z","receivedAt":"2005-06-19T03:43:04Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sun, 19 Jun 2005, Jon Seymour wrote:\n> \n> Perhaps in answering this question, you can help me understand the\n> intended behaviour of your bisection algorithm a little better. The\n> question is this: for your purposes, given a rev-list output, why not\n> simply use the literal middle element of the outputed list?\n\nThe literal middle tends to be in the middle _timewise_, but that's\nirrelevant. It might be just a single step away from one of the commits\nthat has already been marked \"good\", and as such, testing that one might\nwell be totally pointless: if you have a thousand commits (not at all\nunlikely), testing whether they are good or not one at a time is just not\nreasonable.\n\nWhat we want to get is the commit that basically bisects the other commits \nfrom a \"reachability graph\" angle. We want something that when selected as \nthe new \"top\" will have roughly half the commits in it.\n\nPut another way: let's say that we have those thousand commits that _may_ \nhave introduced a bug, but we don't know which one. What do we want? We \nwant to find a new head that contains roughly five hundred of the unknown \ncommits. No more, no less. Maybe we won't find a 500/500 split, but we \ndefinitely want a 600/400 split over a 1/999 split, since the 1/999 split \nisn't likely to get us any closer to the answer.\n\nNow, I say \"roughly\", because there may not _be_ any commit that exactly \nbisects the case. For a trivial case, let's say that we know that 'A' is \nbad, and 'B' is good, but the graph in between them looks like this:\n\n\n A\n / |\n a | \n | b\n | | \\\n c d e\n \\ | /\n B\n\nso the bug might have been introduced by any of a-e, and we just don't\nknow which one was the cause.\n\nNow, selecting either 'a' or 'b' as the new tip is a good choice, 'a'\nreaches two unknowns (a+c) while b reaches 3 unknowns (b+d+e) but the\nothers only reach a single unknown.\n\nAnd notice how the two good bisection places were both _recent_. They were \nnot in the middle \"time-wise\".\n\nAlso note that we do NOT want to reach the maximal amount of commits: we \nwant to reach _half_ the commits. If we select a commit that reaches a lot \nof other unknown commits ('A' is the maximal here, of course), then we're \nnot actually bisecting the thing at all: we're just testing close to a \n\"known bad\" case.\n\nBut let's say that 'c' didn't actually exist (or, alternatively, we have\ntested that one and know that \"B+c\" is good, which basically makes 'c'\nirrelevant for bug-hunting): in that case there is no good bisection,\nsince whichever of the remaining ones we choose (a,b,d or e) we'll always\nhave split it up so that we basically test the addition or subtraction of\njust one single commit. There's not anything \"--bisect\" can do about that, \nand it will just happen to pick one of them. And that's what I mean\nby \"there may not be any commit that is nicely in the middle\".\n\n\t\tLinus\n"},{"id":"5028","messageId":"2cfc40320506182107755d1b3e@mail.gmail.com","threadId":"966","inReplyTo":"20050619033821.GB24982@delft.aura.cs.cmu.edu","subject":"Re: git-rev-list: \"--bisect\" flag","fromName":"Jon Seymour","fromEmail":"jon.seymour@gmail.com","sentAt":"2005-06-19T04:07:15Z","receivedAt":"2005-06-19T04:07:15Z","isPatch":false,"sender":{"key":"jon.seymour@gmail.com","avatar":"https://avatars.githubusercontent.com/u/207131?v=4"},"body":"On 6/19/05, Jan Harkes wrote:\n> On Sun, Jun 19, 2005 at 10:18:45AM +1000, Jon Seymour wr\n> A was known good, parallel development for commits B and C, finally\n> merged into D. A bug got introduced in B, which we discover by the time\n> we have a checked out copy of D.\n> \n> .--- B ---.\n> / \\\n> A D\n> \\ /\n> `--- C ---'\n> \n> git-rev-list E ^A shows this as BCD. Pick the halfway point C, and this\n\nI assume you mean git-rev-list D ^A\n\n> one checks out ok. So at this point we would decide that the bug got\n> introduced by the C->D change.\n\nI think you misunderstood the intent of my original question which was\nimplicitly referring to the implementation of the bisection algorithm,\nnot to the bug blatt algorithm that makes use of the bisection\nalgorithm.\n\nMy actual question was: \"Why is the bisection algorithm itself the way it is? \"\n\nA simple bisection algorithm which simply chooses the middle of the\ngit-rev-list output chooses a point which one could in principle argue\nis as good as the one chosen by the current bisection algorithm.\nHowever, I must admit that I don't quite understand the subtleties of\nLinus' bisection algorithm, hence the question - why is his bisection\nalgorithm better than simply choosing the literal middle?\n\nI'll post a patch that I have already sent to Linus which demonstrates\nan implementation of --bisect that chooses the literal middle. This\npatch also includes a demonstration of Linus' binary bug blatting\ntechnique (see t/t6001-rev-list-merge-order.sh)\n\njon.\n"},{"id":"5031","messageId":"Pine.LNX.4.58.0506182141400.2268@ppc970.osdl.org","threadId":"966","inReplyTo":"Pine.LNX.4.58.0506182022130.2268@ppc970.osdl.org","subject":"Re: git-rev-list: \"--bisect\" flag","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-06-19T05:03:20Z","receivedAt":"2005-06-19T05:03:20Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sat, 18 Jun 2005, Linus Torvalds wrote:\n> \n> Now, I say \"roughly\", because there may not _be_ any commit that exactly \n> bisects the case. For a trivial case, let's say that we know that 'A' is \n> bad, and 'B' is good, but the graph in between them looks like this:\n\nLet's make a different case, just to make it even more obvious.\n\nLet's say that the graph is\n\n\n A\n / \\\n a1 b1\n | |\n a2 b2\n | |\n a3 b3\n | |\n a4 b4\n | |\n a5 b5\n | |\n a6 b6\n | |\n a7 b7\n | |\n a8 b8\n | |\n a9 b9\n \\ /\n B\n\nand we know that \"A\" is bad, and \"B\" is good, but we don't know which of \na1-a9/b1-b9 are buggy.\n\nWhere do we start testing?\n\nWe start testing at either 'a1' or 'b1', because those are the two values \nthat bisect the list either into the \"a1-a9\" series, or the \"b1-b9\" \nseries. Any other starting point would be a bug.\n\nOr, let's say that the graph is\n\n A\n / \\\n | b1\n | |\n | b2\n | |\n | b3\n | |\n a1 b4\n | |\n a2 b5\n | |\n a3 b6\n | |\n | b7\n | |\n | b8\n | |\n | b9\n \\ /\n B\n\n\nand in this case the right place to pick is 'b4', because that's the one\nthat reaches 6 commits (b4-b9), while it leaves 6 commits unreachable\n(a1-a3, b1-b3): that's a perfect bisection, and now it's totally \nunambiguous (in the previous case a1 and b1 were equally good choices, in \nthis case there is only one valid choice).\n\nIt gets more interesting when you have intermediate merges:\n\n A\n / \\\n | b1\n | |\n | b2\n | |\n | b3\n | |\n a1 b4\n | |\n a2 b5\n | / |\n a3 b6\n | |\n | b7\n | |\n | b8\n | |\n | b9\n \\ /\n B\n\nThe above graph _looks_ very similar, but now the right place to bisect is\n'b5', because that reaches six commits (a3 + b5-b9), and again there are\nsix commits unreachable (a1-a2 + b1-b4). Again, this is unambiguous -\nthere is one clearly superior choice.\n\nThe current --bisect algorithm may not always pick that best choice: I\nthink I should subtract one from the total number of commits, since right\nnow it counts the \"good\" commit too, ie 'A'. But I think it's at most\noff-by-one.\n\nThe bigger problem is that the algorithm is something like O(N^3) in cost\n- albeit with a fairly cheap constant factor. In other words, it might not\nbe worthwhile bisecting three years worth of development with it, and you\nmigth be better off starting with a rougher half-way-point algorithm\n(\"let's try some release a year and a half ago first\").\n\nThe performance problem seems to really be pretty theoretical: I can\nbisect the developemnt from 2.6.12-rc2 to current head in 0.59 seconds, so\nit's not like it's horribly slow for something like a couple of months\nworth of development.\n\n\t\t\tLinus\n"},{"id":"5032","messageId":"Pine.LNX.4.62.0506182204350.11617@qynat.qvtvafvgr.pbz","threadId":"966","inReplyTo":"Pine.LNX.4.58.0506182141400.2268@ppc970.osdl.org","subject":"Re: git-rev-list: \"--bisect\" flag","fromName":"David Lang","fromEmail":"david.lang@digitalinsight.com","sentAt":"2005-06-19T05:05:40Z","receivedAt":"2005-06-19T05:05:40Z","isPatch":false,"sender":{"key":"david.lang@digitalinsight.com","avatar":null},"body":"On Sat, 18 Jun 2005, Linus Torvalds wrote:\n\n> The performance problem seems to really be pretty theoretical: I can\n> bisect the developemnt from 2.6.12-rc2 to current head in 0.59 seconds, so\n> it's not like it's horribly slow for something like a couple of months\n> worth of development.\n\nif it takes you about as long to type the command (and scan it to make \nsure you didn't mistype it) as it does to execute you don't have a \nperformance problem :-)\n\nDavid Lang\n\n-- \nThere are two ways of constructing a software design. One way is to make it so simple that there are obviously no deficiencies. And the other way is to make it so complicated that there are no obvious deficiencies.\n -- C.A.R. Hoare\n"},{"id":"5033","messageId":"Pine.LNX.4.58.0506182218180.2268@ppc970.osdl.org","threadId":"966","inReplyTo":"Pine.LNX.4.62.0506182204350.11617@qynat.qvtvafvgr.pbz","subject":"Re: git-rev-list: \"--bisect\" flag","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-06-19T05:30:36Z","receivedAt":"2005-06-19T05:30:36Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sat, 18 Jun 2005, David Lang wrote:\n> \n> if it takes you about as long to type the command (and scan it to make \n> sure you didn't mistype it) as it does to execute you don't have a \n> performance problem :-)\n\nYeah, well, in all honesty, I haven't actually verified that my bisection \ngives the right answer.\n\nI verified \"visually\" that it does something half-way sane with this:\n\n git-rev-list --bisect HEAD ^v2.6.12-rc2 > .git/refs/tags/bisect-1\n git-rev-list --bisect HEAD ^v2.6.12-rc2 ^bisect-1 > .git/refs/tags/bisect-2\n git-rev-list --bisect HEAD ^v2.6.12-rc2 ^bisect-1 ^bisect-2 > .git/refs/tags/bisect-3\n git-rev-list --bisect HEAD ^v2.6.12-rc2 ^bisect-1 ^bisect-2 ^bisect-3 > .git/refs/tags/bisect-4\n git-rev-list --bisect HEAD ^v2.6.12-rc2 ^bisect-1 ^bisect-2 ^bisect-3 ^bisect-4 > .git/refs/tags/bisect-5\n gitk\n\nand it looked sane (ie \"bisect-1\" should show up as a tag about half-way, \nand the others should get progressively closer to the HEAD). But when I \nnow tried it again (I did the above originally with plain 2.6.12), I get \nerrors from \"gitk\":\n\n\tERROR: none of the pending commits can be done yet:\n\t bd6ae2f6d61da0f90c6b66e9a4ab6c53ef8c159a\n\t 2512809255d018744fe6c2f5e996c83769846c07\n\t 88d7bd8cb9eb8d64bf7997600b0d64f7834047c5\n\t b3214970abbe983cd89842ae24ea00e21bba79f6\n\nwhich looks like the current kernel overflows gitk some way (there's \nsuddenly a lot more parallellism, since there were a number of merges that \nwere pending, waiting for the 2.6.12 release).\n\n\t\tLinus\n"},{"id":"5036","messageId":"2cfc403205061903155a6090db@mail.gmail.com","threadId":"966","inReplyTo":"Pine.LNX.4.58.0506182141400.2268@ppc970.osdl.org","subject":"Re: git-rev-list: \"--bisect\" flag","fromName":"Jon Seymour","fromEmail":"jon.seymour@gmail.com","sentAt":"2005-06-19T10:15:02Z","receivedAt":"2005-06-19T10:15:02Z","isPatch":false,"sender":{"key":"jon.seymour@gmail.com","avatar":"https://avatars.githubusercontent.com/u/207131?v=4"},"body":"FWIW, I accept that Linus' bisection algorithm does have better worst\ncase performance (in terms of number of build/test iterations) on at\nleast some examples than the literal middle bisection algorithm and\nthat the \"literal middle\" bisection algorithm has degenerate cases\nwhich mean that its performance is sometimes worse than O(log 2 N).\n\nI don't actually have a good feel for what the actual bound on Linus'\nalgorithm is, but I'll measure it on the 2.6 kernel and post the\nresults.\n\nRegards,\n\njon.\n\nOn 6/19/05, Linus Torvalds wrote:\n> \n> \n> On Sat, 18 Jun 2005, Linus Torvalds wrote:\n> >\n> > Now, I say \"roughly\", because there may not _be_ any commit that exactly\n> > bisects the case. For a trivial case, let's say that we know that 'A' is\n> > bad, and 'B' is good, but the graph in between them looks like this:\n> \n> Let's make a different case, just to make it even more obvious.\n> \n> Let's say that the graph is\n> \n> \n> A\n> / \\\n> a1 b1\n> | |\n> a2 b2\n> | |\n> a3 b3\n> | |\n> a4 b4\n> | |\n> a5 b5\n> | |\n> a6 b6\n> | |\n> a7 b7\n> | |\n> a8 b8\n> | |\n> a9 b9\n> \\ /\n> B\n> \n> and we know that \"A\" is bad, and \"B\" is good, but we don't know which of\n> a1-a9/b1-b9 are buggy.\n> \n> Where do we start testing?\n> \n> We start testing at either 'a1' or 'b1', because those are the two values\n> that bisect the list either into the \"a1-a9\" series, or the \"b1-b9\"\n> series. Any other starting point would be a bug.\n> \n> Or, let's say that the graph is\n> \n> A\n> / \\\n> | b1\n> | |\n> | b2\n> | |\n> | b3\n> | |\n> a1 b4\n> | |\n> a2 b5\n> | |\n> a3 b6\n> | |\n> | b7\n> | |\n> | b8\n> | |\n> | b9\n> \\ /\n> B\n> \n> \n> and in this case the right place to pick is 'b4', because that's the one\n> that reaches 6 commits (b4-b9), while it leaves 6 commits unreachable\n> (a1-a3, b1-b3): that's a perfect bisection, and now it's totally\n> unambiguous (in the previous case a1 and b1 were equally good choices, in\n> this case there is only one valid choice).\n> \n> It gets more interesting when you have intermediate merges:\n> \n> A\n> / \\\n> | b1\n> | |\n> | b2\n> | |\n> | b3\n> | |\n> a1 b4\n> | |\n> a2 b5\n> | / |\n> a3 b6\n> | |\n> | b7\n> | |\n> | b8\n> | |\n> | b9\n> \\ /\n> B\n> \n> The above graph _looks_ very similar, but now the right place to bisect is\n> 'b5', because that reaches six commits (a3 + b5-b9), and again there are\n> six commits unreachable (a1-a2 + b1-b4). Again, this is unambiguous -\n> there is one clearly superior choice.\n> \n> The current --bisect algorithm may not always pick that best choice: I\n> think I should subtract one from the total number of commits, since right\n> now it counts the \"good\" commit too, ie 'A'. But I think it's at most\n> off-by-one.\n> \n> The bigger problem is that the algorithm is something like O(N^3) in cost\n> - albeit with a fairly cheap constant factor. In other words, it might not\n> be worthwhile bisecting three years worth of development with it, and you\n> migth be better off starting with a rougher half-way-point algorithm\n> (\"let's try some release a year and a half ago first\").\n> \n> The performance problem seems to really be pretty theoretical: I can\n> bisect the developemnt from 2.6.12-rc2 to current head in 0.59 seconds, so\n> it's not like it's horribly slow for something like a couple of months\n> worth of development.\n> \n> Linus\n> \n\n\n-- \nhomepage: http://www.zeta.org.au/~jon/\nblog: http://orwelliantremors.blogspot.com/\n"},{"id":"5041","messageId":"2cfc40320506190741409f3a5@mail.gmail.com","threadId":"966","inReplyTo":"2cfc403205061903155a6090db@mail.gmail.com","subject":"Re: git-rev-list: \"--bisect\" flag","fromName":"Jon Seymour","fromEmail":"jon.seymour@gmail.com","sentAt":"2005-06-19T14:41:41Z","receivedAt":"2005-06-19T14:41:41Z","isPatch":false,"sender":{"key":"jon.seymour@gmail.com","avatar":"https://avatars.githubusercontent.com/u/207131?v=4"},"body":"Linus,\n\nWould I be correct in stating that an intuitive reason why your\nalgorithm is better than selecting the linear middle is the following:\n\nIf you concentrate on testing merges, rather than non-merges, the\nchances are you are going to eliminate N-times as many possible good\ncommits as if you pick a random commit, where N is the average fan-out\nof the commit graph.\n\nWith the linear middle algorithm, it doesn't really matter if you pick\na child of a merge - that is almost as good as picking the merge\nitself. But if you happen to pick a parent of merge, then if it is\ngood and the parent is also good, you have wasted the opportunity to\nclean up the peer branches of the parent you chose.\n\nSo the heuristic should be:\n\n- focus on branches until there are no branches left, then keep\nbisecting the list that remains.\n\nBuilding on this insight, though, I'd like to point out that if you\nwant to eliminate things on a large scale, the things to focus on\nfirst are epoch boundaries. Epoch boundaries are defined in such a way\nthat if an epoch boundary is good then everything reachable from an\nepoch boundary is also good [ assuming exactly one fault ].\n\nIf you happen to choose a child of an epoch boundary, that's ok on\none-level, but on another level it's not ok. In particular, you\nhaven't eliminated everything beyond the epoch boundary so the open\nlist will be longer than it strictly needs to be.\n\nSo, I propose a modification to my \"linear middle\" bisection algorithm\n as follows:\n\nIf there is more than one epoch boundary in the interesting graph,\nchoose the literal middle epoch boundary, otherwise, if there is more\nthan one merge in the interesting graph, chose the literal middle\nmerge, otherwise if there are no merges in the interesting graph,\nchoose the literal middle of the remaining list.\n\nI am going to build a version of my linear middle code that\ndemonstrates this algorithm and then test it against the Linux 2.6\nkernel.\n\nFWIW: my measurements of your algorithm thus far show that if the bug\nexists in the first 1070 of the 2119 commits between HEAD and\nv2.6.12-rc2 it consistently (very consistently) takes between 11 and\n13 iterations of git-bug-blatt-script to find the bug.\n\nSpecifically: average (12.10), median (12), stdev(0.412), max(13), min(11).\n\nThis compares with my naive literal middle algorithm (measurements\nonly for the first 619 commits):\n\naverage(21), median(16), stdev(10.6), max(49), min(8).\n\nThe number of commits is 2118, the number with a fanout > 1 is 173.\nThe average fanout of those with fanout is 2. My average is currently\n2 times worse than yours and my worst case is 4-5 times worse than\nyours.\n\nSo, you will be pleased to know that your intuition about the\ncorrectness of your own algorithm has been objectively verified.\n\nMy intuition at this point is that my revised algorithm won't\nsignificantly differ from your algorithm. I am thinking it will\nrequire ~ 3 epoch boundary tests to identify the relevant epoch, 5\nmerge tests to identify the relevant segment and 4 bisections of a\nlinear segment to identify the correct merge which ends up being 12\niterations of the bug-blatt algorithm which really is no different to\nyours. I suspect my algorithm might be better for really, really, big\nrepositories, with long histories, but I judge that the chance an\ninteresting bug will be deep in the long history is somewhat remote.\n\nBoth algorithms will benefit, however, if the intuition that most bugs\nare recent is correct. git-bug-blatt-script could be modified to test\nthe first epoch boundary before recursively bisecting things. This\nwill make the typical bug search ~ 9 iterations long (since the\naverage epoch appears to be less than 512 commits and more than 256\ncommits big).\n\njon.\n"},{"id":"5045","messageId":"Pine.LNX.4.58.0506190951330.2268@ppc970.osdl.org","threadId":"966","inReplyTo":"2cfc40320506190741409f3a5@mail.gmail.com","subject":"Re: git-rev-list: \"--bisect\" flag","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-06-19T17:20:39Z","receivedAt":"2005-06-19T17:20:39Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Mon, 20 Jun 2005, Jon Seymour wrote:\n> \n> Would I be correct in stating that an intuitive reason why your\n> algorithm is better than selecting the linear middle is the following:\n> \n> If you concentrate on testing merges, rather than non-merges, the\n> chances are you are going to eliminate N-times as many possible good\n> commits as if you pick a random commit, where N is the average fan-out\n> of the commit graph.\n\nNo. You really shouldn't concentrate on merges either.\n\nThe thing is, you do _not_ want to test as many commits as possible, or as \nfew commits as possible.\n\nThis is _not_ a \"try to eliminate as many commits as possible\" problem. \nIt's really one of trying to eliminate _half_ the commits. Not more, not \nless. \n\nSo to some degree you want to _avoid_ merges, because they pick up a lot \nof commits, and that might take you over the limit. But at the same time \nyou need to be very aware of merges, since if you ignore them, you'll pick \nup too _few_ commits.\n\nSo in a very real sense, whether you pick a merge or not doesn't depend on \nwhether that one entry is a merge itself - it really depends on the whole \nflow. You can't do any local measurements.\n\nThe reason my algorithm is so horrid (O(3)) is that you can't even cache \nthe dang thing sanely: you can't optimize if by remembering how many \ninteresting commits are reachable from one commit, and then doing \"this \ncommit reaches commits X and Y, so I can reach X.count + Y.count commits \nfrom it\". That's just not true, because often (basically always) there is \nlots of common commits in X.count and Y.count..\n\nSo that's why I do that strange full reachability thing for _each_ commit,\nand then clear the reachability flags and start with the next commit. It's\nhorrid, but I can't see a sane way to avoid it (I could do the clearing\nless often by introducing the notion of \"generations\" in the reachability,\nbut I didn't want to add a new counter to the data structures - and it\nwouldn't really change anything fundamental).\n\nIn your measurements:\n\n> FWIW: my measurements of your algorithm thus far show that if the bug\n> exists in the first 1070 of the 2119 commits between HEAD and\n> v2.6.12-rc2 it consistently (very consistently) takes between 11 and\n> 13 iterations of git-bug-blatt-script to find the bug.\n> \n> Specifically: average (12.10), median (12), stdev(0.412), max(13), \n> min(11).\n\nYes. Consistency is the name of the game. A low standard deviation is what\nit's all about, because that's how binary searches work. The point about\nbinary searching for a bug is that you're not really looking for \"the one\" \ncommit, you're really looking for the _range_ of two adjacent commits: it\ndoesn't even help if you happen to pick the buggy commit on the first try,\nbecause the only thing that matters is when you have zeroed in on the\n\"buggy and previous\" one.\n\nIn other words, in a traditional search, when you pick an entry, you know \nthat you got it right: you might be lucky and pick it first, and you'll be \nhappy. But in the \"search for a bug\" case, you always have to go the \n_full_ \"log2()\" thing, because you will always have to not just pick the \nright entry, you will also have had to \"bisect to zero\" so that you know \nthat the entry before it was not buggy.\n\nThis is because the \"is it buggy\" is not a unique thing, it's really just \na partial ordering in the set (if you're really unlucky, you might have \ntwo bugs that interact, and you'll not actually find \"the commit\" at all, \nbut the one you do end up zeroing in on should at least be _one_ border \ncondition for the bug, so it should help you somewhat regardless). \n\nSo you basically cannot avoid doing \"ceil(log2(N))\" tests, and with 2119\ncommits, you should pretty much _always_ get 12, and basically a standard\ndeviation of zero.\n\nThe reason you don't get that is that _occasionally_ you can't get close\nenough to \"half-way\", and depending on whether the bug was in the smaller\nset or bigger set, you might be lucky or unlucky. The problem here is that\nby definition you'll be unlucky more of the time: the bigger set (the\nunlucky case) is _bigger_, so it's more likely to have the bug, so what\nyou should see statistically is that you can't actually do _better_ than\nceil(log2(N)).\n\n(\"cannot do better\" obviously is true only in the statistical sense. You\ncan always be lucky in any individual test, and if you are intelligent and\nchoose the commits to test based on the symptoms of the bug you can always\ndo better, of course).\n\nNOTE NOTE NOTE! The above is all based on random distribution of bugs,\nwhere all commits count equally, which is obviously not even true. You \ncoudl try to do a \"weighted bisection\", where you weigh commits \ndifferently: you might say, for example, that if the author field matches \nthe string \"torvalds\", then the likelihood of a bug is obviously \nminiscule, so such a commit only counts as 0.1.\n\nOr you could argue that a pure merge seldom introduces a bug (which is \nprobably not true, but hey, this is theory), and you could decide that \nwhen you \"count commits\", then normal commits count as two, and merges \ncount as one, and the bisection is trying to get equal \"weights\" on both \nsides, not \"equal number of commits\".\n\nHowever, that's where \"consistency\" has another advantage: maybe it's\npossible to get better results on average by taking statistical bug\ndistribution behaviour into account (like \"bugs are likely new - try to\nweigh the bisection 60% reachable / 40% unreachable instead of 50-50\"), \nbut that means that then occasionally you do worse, and from a \npsychological angle I think that's unacceptable. I think most bug hunters \nwould much prefer to know that \"I need to reboot 7 times and I'll get it\", \nover \"I probably need to reboot only 5 times, but it might be 10 if I'm \nunlucky\".\n\n> This compares with my naive literal middle algorithm (measurements\n> only for the first 619 commits):\n> \n> average(21), median(16), stdev(10.6), max(49), min(8).\n\nYes. I really don't believe you can do better than 12, unless you start \ndepending on knowledge of the distribution of bugs.\n\n\t\tLinus\n"},{"id":"5046","messageId":"20050619173634.GA25768@elte.hu","threadId":"966","inReplyTo":"Pine.LNX.4.58.0506190951330.2268@ppc970.osdl.org","subject":"Re: git-rev-list: \"--bisect\" flag","fromName":"Ingo Molnar","fromEmail":"mingo@elte.hu","sentAt":"2005-06-19T17:36:34Z","receivedAt":"2005-06-19T17:36:34Z","isPatch":false,"sender":{"key":"mingo@elte.hu","avatar":null},"body":"\n* Linus Torvalds wrote:\n\n> NOTE NOTE NOTE! The above is all based on random distribution of bugs, \n> where all commits count equally, which is obviously not even true. You \n> coudl try to do a \"weighted bisection\", where you weigh commits \n> differently: you might say, for example, that if the author field \n> matches the string \"torvalds\", then the likelihood of a bug is \n> obviously miniscule, so such a commit only counts as 0.1.\n\nanother assumption is that the number of testsystems is a power of two \nminus 1. With 2 or more testsystems (and automated testing) you could \ndissect the search space into 3, 5 or more roughly equal pieces in the \nfirst step (2, 4, 8 ... sections are already supported via the bisect \nflag). To decrease the time needed to find a bug it makes sense to \nincrease the number of testsystems, especially if it takes minutes to \nboot - or if it takes minutes (or hours) to reproduce a bug. If each box \nruns a separate kernel then statistically, if one of them triggers the \nbug, only half of them have to be rebooted with new kernels, the others \nwould still be kept running in a \"commit space of interest\".\n\nBut i guess it's not a big degradation to just round the test method to \nthe nearest power-of-2 bisection method.\n\n\tIngo\n"},{"id":"5047","messageId":"Pine.LNX.4.58.0506191153350.2268@ppc970.osdl.org","threadId":"966","inReplyTo":"20050619173634.GA25768@elte.hu","subject":"Re: git-rev-list: \"--bisect\" flag","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-06-19T19:01:33Z","receivedAt":"2005-06-19T19:01:33Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sun, 19 Jun 2005, Ingo Molnar wrote:\n> \n> another assumption is that the number of testsystems is a power of two \n> minus 1. With 2 or more testsystems (and automated testing) you could \n> dissect the search space into 3, 5 or more roughly equal pieces in the \n> first step (2, 4, 8 ... sections are already supported via the bisect \n> flag).\n\nYeah. I don't think it matters much, though, since the \"more testsystems\" \nthing will only really end up helping by a fairly small amount, at the\ncost of much more complexity. The difference between \"log2(N)\" and\n\"log5(N)\" isn't _that_ big, and it's even smaller when you just do the\npower-of-two thing and use 4 systems instead of 5 (ie now it's \"log4(N)\" \nvs \"log5(N)\").\n\nAlso, to use multiple test-systems efficiently, they all end up having to\nbe synchronized (ie the next iteration needs to get the result from all\nthe test-systems from the previous one), so it's quite a lot of bother for\nnot a lot of improvement. It also assumes you can partition the problem\nspace well into roughly equal pieces - which may or may not be true.\n\nMore importantly, quite often the nasty problems are the ones that only \nhappen for one machine. Trying to make it easy for non-developers to test \ndifferent kernels is what this is about: I started thinking about this \nwhen we had the \"x86-64 SIGSEGV's for me\" issue, where bisection was \nfairly easy in the -mm series due to a nice linear series, but even then \nyou had to have tools to apply/unapply different patches etc.\n\n\t\tLinus\n"},{"id":"5049","messageId":"2cfc4032050619125537dee354@mail.gmail.com","threadId":"966","inReplyTo":"Pine.LNX.4.58.0506190951330.2268@ppc970.osdl.org","subject":"Re: git-rev-list: \"--bisect\" flag","fromName":"Jon Seymour","fromEmail":"jon.seymour@gmail.com","sentAt":"2005-06-19T19:55:19Z","receivedAt":"2005-06-19T19:55:19Z","isPatch":false,"sender":{"key":"jon.seymour@gmail.com","avatar":"https://avatars.githubusercontent.com/u/207131?v=4"},"body":"On 6/20/05, Linus Torvalds wrote:\n> \n> \n> On Mon, 20 Jun 2005, Jon Seymour wrote:\n> >\n> > Would I be correct in stating that an intuitive reason why your\n> > algorithm is better than selecting the linear middle is the following:\n> >\n> > If you concentrate on testing merges, rather than non-merges, the\n> > chances are you are going to eliminate N-times as many possible good\n> > commits as if you pick a random commit, where N is the average fan-out\n> > of the commit graph.\n> \n> No. You really shouldn't concentrate on merges either.\n> \n> The thing is, you do _not_ want to test as many commits as possible, or as\n> few commits as possible.\n> \n> This is _not_ a \"try to eliminate as many commits as possible\" problem.\n> It's really one of trying to eliminate _half_ the commits. Not more, not\n> less.\n> \n\nYep, ok, so the node you are looking for is one that can reach as\nclose to half of the rest of the graph as possible - that's what you\nmean by half-way reachability. If the graph was N nodes deep (no\nfan-out) that would be the literal middle. If it was N nodes wide\n(e.g. fanout N), there is no good node and you basically have to test\neverything since one test doesn't imply anything about the other N-1\nnodes.\n\nA typical commit graph is worse than O(log2 N) by a factor that is\ndetermined by some measure of the parallel branching in the graph.\n\n> \n> The reason my algorithm is so horrid (O(3)) is that you can't even cache\n> the dang thing sanely: you can't optimize if by remembering how many\n> interesting commits are reachable from one commit, and then doing \"this\n> commit reaches commits X and Y, so I can reach X.count + Y.count commits\n> from it\". That's just not true, because often (basically always) there is\n> lots of common commits in X.count and Y.count..\n\nI presume you mean O(N^3)?\n \nWill you accept a patch that can reduce the worst case cost to some\nlower order? I have a hunch (conceivably wrong, of course) that it can\nbe done in O(N).\n\n> > This compares with my naive literal middle algorithm (measurements\n> > only for the first 619 commits):\n> >\n> > average(21), median(16), stdev(10.6), max(49), min(8).\n> \n> Yes. I really don't believe you can do better than 12, unless you start\n> depending on knowledge of the distribution of bugs.\n> \n\nAgreed. \n\njon.\n"},{"id":"5068","messageId":"Pine.LNX.4.58.0506192002240.2268@ppc970.osdl.org","threadId":"966","inReplyTo":"2cfc4032050619125537dee354@mail.gmail.com","subject":"Re: git-rev-list: \"--bisect\" flag","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-06-20T03:09:44Z","receivedAt":"2005-06-20T03:09:44Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Mon, 20 Jun 2005, Jon Seymour wrote:\n>\n> Yep, ok, so the node you are looking for is one that can reach as\n> close to half of the rest of the graph as possible - that's what you\n> mean by half-way reachability. If the graph was N nodes deep (no\n> fan-out) that would be the literal middle. If it was N nodes wide\n> (e.g. fanout N), there is no good node and you basically have to test\n> everything since one test doesn't imply anything about the other N-1\n> nodes.\n\nExactly.\n\n> A typical commit graph is worse than O(log2 N) by a factor that is\n> determined by some measure of the parallel branching in the graph.\n\nYes. In many cases it's ok to have parallellism, and the fact that any \nnormal merges will always be two-way (ie there's never a commit in \npractice that has a very high fan-in), I do believe that you normally get \npretty close to that O(log2N) behaviour. In fact, your numbers seemed to \nsay that we're normally within 10% of it.\n\n> I presume you mean O(N^3)?\n\nYup again.\n\n> Will you accept a patch that can reduce the worst case cost to some\n> lower order? I have a hunch (conceivably wrong, of course) that it can\n> be done in O(N).\n\nWell, it depends on how nasty it ends up being. I thought my stupid\nalgorithm would suck horribly, but considering that it can trivially\nbisect all of the git history so far in basically zero time, it doesn't\nseem to be that bad. You're more likely to have problems with having to\nbring in all the commits from disk in the cold-cache case than you are to\nhave problems with the current algorithm performance.\n\nEven at O(N^3) it shouldn't be too nasty even if some crazy person tried\nto bisect a years worth of development (which really isn't very reasonable\nbehaviour anyway, it's just not sensible to not try a few standard\nreleases in between first).\n\n\t\t\tLinus\n"},{"id":"5069","messageId":"2cfc403205061920272ee47166@mail.gmail.com","threadId":"966","inReplyTo":"Pine.LNX.4.58.0506192002240.2268@ppc970.osdl.org","subject":"Re: git-rev-list: \"--bisect\" flag","fromName":"Jon Seymour","fromEmail":"jon.seymour@gmail.com","sentAt":"2005-06-20T03:27:21Z","receivedAt":"2005-06-20T03:27:21Z","isPatch":false,"sender":{"key":"jon.seymour@gmail.com","avatar":"https://avatars.githubusercontent.com/u/207131?v=4"},"body":"> Well, it depends on how nasty it ends up being. I thought my stupid\n> algorithm would suck horribly, but considering that it can trivially\n> bisect all of the git history so far in basically zero time, it doesn't\n> seem to be that bad. You're more likely to have problems with having to\n> bring in all the commits from disk in the cold-cache case than you are to\n> have problems with the current algorithm performance.\n> \n\nI'll give you a sketch of the algorithm. \n\nFirst, recall that merge-order code uses an incremental topological\nsort whose key idea is to employ a conservation of mass analogy. A\nsimilar analogy can help here.\n\n1. count all visible nodes [ i.e. nodes that git-rev-list would print\n], call this value N\n2. at the top node inject N units of mass\n3. traverse the visible graph, in topological order\n4. at each node, send all the mass received from parents minus 1 unit\nonto visible parents. Record how much mass you have sent downstream.\nKeep a record of the nodes that have seen nearest to half of that\nmass.\n5. when the traversal completes, choose the node that saw closest to\n1/2 of the original mass [ or pick one at random if there is more than\none ]. It must be able to reach close to 1/2 of the visible graph,\n'cos all that mass it has seen has to drain somewhere!\n\nThis algorithm is demonstrably O(V+E) because the traversal is O(V+E)\n\nMy intention is to add this algorithm to my refactored\nepoch.c/traversal.c, since this is a much better framework for doing\ntraversals than the current epoch.c.\n\nDo you have any objections to me doing that?\n\njon.\n-- \nhomepage: http://www.zeta.org.au/~jon/\nblog: http://orwelliantremors.blogspot.com/\n"},{"id":"5070","messageId":"2cfc40320506192030290187af@mail.gmail.com","threadId":"966","inReplyTo":"2cfc403205061920272ee47166@mail.gmail.com","subject":"Re: git-rev-list: \"--bisect\" flag","fromName":"Jon Seymour","fromEmail":"jon.seymour@gmail.com","sentAt":"2005-06-20T03:30:57Z","receivedAt":"2005-06-20T03:30:57Z","isPatch":false,"sender":{"key":"jon.seymour@gmail.com","avatar":"https://avatars.githubusercontent.com/u/207131?v=4"},"body":"> 1. count all visible nodes [ i.e. nodes that git-rev-list would print\n> ], call this value N\n> 2. at the top node inject N units of mass\n> 3. traverse the visible graph, in topological order\n> 4. at each node, send all the mass received from parents minus 1 unit\n> onto visible parents. Record how much mass you have sent downstream.\n> Keep a record of the nodes that have seen nearest to half of that\n> mass.\n\nCorrection - at each node, send all mass received from _children_\n"},{"id":"5074","messageId":"2cfc403205062003292db2b457@mail.gmail.com","threadId":"966","inReplyTo":"2cfc40320506192030290187af@mail.gmail.com","subject":"Re: git-rev-list: \"--bisect\" flag","fromName":"Jon Seymour","fromEmail":"jon.seymour@gmail.com","sentAt":"2005-06-20T10:29:56Z","receivedAt":"2005-06-20T10:29:56Z","isPatch":false,"sender":{"key":"jon.seymour@gmail.com","avatar":"https://avatars.githubusercontent.com/u/207131?v=4"},"body":"On 6/20/05, Jon Seymour wrote:\n> > 1. count all visible nodes [ i.e. nodes that git-rev-list would print\n> > ], call this value N\n> > 2. at the top node inject N units of mass\n> > 3. traverse the visible graph, in topological order\n> > 4. at each node, send all the mass received from parents minus 1 unit\n> > onto visible parents. Record how much mass you have sent downstream.\n> > Keep a record of the nodes that have seen nearest to half of that\n> > mass.\n> \n> Correction - at each node, send all mass received from _children_\n> \n\nThis is a little too simple. It would work if the all nodes in the\nvisible graph were all connected to the base of an epoch. However, the\npruning behaviour of known goods effectively installs blockages into\nthe network and causes \"backflow\" which complicates things somewhat -\na plumbers nightmare!\n\nI am exploring another variation of the idea which is even simpler.\nExperimentally it seems quite similar to your average case\nperformance, but doesn't yet approach your low std deviations.\nHowever, I think I know why that is, so I will, after a few games of\npool and a similar number of beers, have another crack at it.\n\njon.\n-- \nhomepage: http://www.zeta.org.au/~jon/\nblog: http://orwelliantremors.blogspot.com/\n"},{"id":"5079","messageId":"2cfc40320506200737113caa9f@mail.gmail.com","threadId":"966","inReplyTo":"2cfc403205062003292db2b457@mail.gmail.com","subject":"Re: git-rev-list: \"--bisect\" flag","fromName":"Jon Seymour","fromEmail":"jon.seymour@gmail.com","sentAt":"2005-06-20T14:37:52Z","receivedAt":"2005-06-20T14:37:52Z","isPatch":false,"sender":{"key":"jon.seymour@gmail.com","avatar":"https://avatars.githubusercontent.com/u/207131?v=4"},"body":"> I am exploring another variation of the idea which is even simpler.\n> Experimentally it seems quite similar to your average case\n> performance, but doesn't yet approach your low std deviations.\n> However, I think I know why that is, so I will, after a few games of\n> pool and a similar number of beers, have another crack at it.\n> \n\nOk, just for information, I have a linear bisection algorithm which\nresults in a bug-blatt algorithm with the following characteristics on\nthe Linux 2.6 kernel:\n\nAVERAGE\t13.64589235\nMEDIAN\t13\nMAX\t28\nMIN\t9\nSTDEV\t2.171923221\n\nThese results were derived by running the algorithm over the full 2118\ncommits of the\ncurrent Linux 2.6 source.\n\nI'll document what this algorithm is and what its flaws are.\n\nThe algorithm is as follows:\n\nConsider the graph as a closed network of pipes with N reservoirs of 1\nunit of volume. Rotate this graph so the head is at the top. Now, pour\nN units of liquid into the top of the network of pipes. The liquid\npercolates through the network of pipes and ends up in the reservoirs.\nThe selected bisection point is the node that saw as close to N/2\nunits of liquid as any other node.\n\nNow, why isn't this as good (in terms of average and stdev) as Linus'\nalgorithm? The flaw with this algorithm is that some liquid from peer\nnodes reaches the lower half of the network before the liquid that\nwent through the selected node. As a result, the selected node is\nelevated \"above\" the ideal bisection point, by a factor that I believe\nwould be sufficient to explain the higher average and also the greater\nstandard deviation.\n\nStill, my algorithm is very simple and very linear, so it's very good a start.\n\nAs it happens, I believe I have (re-?)discovered a precise way to\ndiscover the bisection points in O(n). I am in the midst of\nimplementing that now.\n\njon.\n"}]}