{"thread":{"id":"7271","subject":"[BUG] bisecting miscounts revisions left to test","startedAt":"2007-03-16T16:14:21Z","lastAt":"2007-03-22T06:42:40Z","messageCount":18,"participants":["Uwe Kleine-König","Johannes Schindelin","Junio C Hamano","Linus Torvalds"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"37249","messageId":"20070316161421.GA24584@lala","threadId":"7271","inReplyTo":null,"subject":"[BUG] bisecting miscounts revisions left to test","fromName":"Uwe Kleine-König","fromEmail":"ukleinek@informatik.uni-freiburg.de","sentAt":"2007-03-16T16:14:21Z","receivedAt":"2007-03-16T16:14:21Z","isPatch":false,"sender":{"key":"u.kleine-koenig@pengutronix.de","avatar":"https://gravatar.com/avatar/354b5e3ceb2806a2f1e1e382ac29ddbdad18288654da62b61eb13583a857eee7?d=mp&s=160"},"body":"Hello,\n\nI'm just bisecting in the kernel, the last commands + output are:\n\nzeisberg@cassiopeia:~/gsrc/linux-2.6$ git bisect good\nBisecting: 2 revisions left to test after this\n[e7b0d26a86943370c04d6833c6edba2a72a6e240] sysfs: reinstate exclusion between method calls and attribute unregistration\n\nzeisberg@cassiopeia:~/gsrc/linux-2.6$ git bisect good\nBisecting: 2 revisions left to test after this\n[b810cdfcf91d76f603fd48023aede48ced8e6bed] Merge branch 'upstream-linus' of master.kernel.org:/pub/scm/linux/kernel/git/jgarzik/netdev-2.6\n\nSo after having 2 revisions left to test and an addional test I still\nhave to test 2 revisions.\n\nFor reproducibility:\n\nzeisberg@cassiopeia:~/gsrc/linux-2.6$ git bisect log\ngit-bisect start\n# good: [08e15e81a40e3241ce93b4a43886f3abda184aa6] Linux 2.6.21-rc3\ngit-bisect good 08e15e81a40e3241ce93b4a43886f3abda184aa6\n# bad: [bac6eefe96204d0ad67d144f2511a6fc487aa594] Linux 2.6.21-rc4\ngit-bisect bad bac6eefe96204d0ad67d144f2511a6fc487aa594\n# good: [bdf3aaf9519ddd8a026b5e04e713d2fa673532e5] Pull bugzilla-8066 into release branch\ngit-bisect good bdf3aaf9519ddd8a026b5e04e713d2fa673532e5\n# good: [2cb8a57b9851805883dfe92cf5d88a726134a384] Fix vmi time header bug\ngit-bisect good 2cb8a57b9851805883dfe92cf5d88a726134a384\n# good: [a7c999114ecd0c69bd3970272b64d8842b765b21] BLK_DEV_IDE_CELLEB dependency fix\ngit-bisect good a7c999114ecd0c69bd3970272b64d8842b765b21\n# good: [0bdd0f385a44344f83409b9e00797bfe2596faf8] Merge master.kernel.org:/pub/scm/linux/kernel/git/wim/linux-2.6-watchdog\ngit-bisect good 0bdd0f385a44344f83409b9e00797bfe2596faf8\n# good: [6ab27c6bf38d5ff71dafeca77b79e7c284804b75] Merge branch 'for-linus' of master.kernel.org:/pub/scm/linux/kernel/git/jikos/hid\ngit-bisect good 6ab27c6bf38d5ff71dafeca77b79e7c284804b75\n# good: [069f8256362b7a17da532f0631cee73b4cfee65b] natsemi: Fix NAPI for interrupt sharing\ngit-bisect good 069f8256362b7a17da532f0631cee73b4cfee65b\n# good: [e7b0d26a86943370c04d6833c6edba2a72a6e240] sysfs: reinstate exclusion between method calls and attribute unregistration\ngit-bisect good e7b0d26a86943370c04d6833c6edba2a72a6e240\n\nzeisberg@cassiopeia:~/gsrc/linux-2.6$ git version\ngit version 1.5.0.3\n\nThis is git from the Debian package.\n\nBest regards\nUwe\n\n-- \nUwe Kleine-König\n\ncal 9 1752 | grep 10\n"},{"id":"37292","messageId":"Pine.LNX.4.63.0703170139110.22628@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"7271","inReplyTo":"20070316161421.GA24584@lala","subject":"Re: [BUG] bisecting miscounts revisions left to test","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2007-03-17T00:50:11Z","receivedAt":"2007-03-17T00:50:11Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Fri, 16 Mar 2007, Uwe Kleine-König wrote:\n\n> zeisberg@cassiopeia:~/gsrc/linux-2.6$ git bisect good\n> Bisecting: 2 revisions left to test after this\n> [e7b0d26a86943370c04d6833c6edba2a72a6e240] sysfs: reinstate exclusion between method calls and attribute unregistration\n> \n> zeisberg@cassiopeia:~/gsrc/linux-2.6$ git bisect good\n> Bisecting: 2 revisions left to test after this\n> [b810cdfcf91d76f603fd48023aede48ced8e6bed] Merge branch 'upstream-linus' of master.kernel.org:/pub/scm/linux/kernel/git/jgarzik/netdev-2.6\n\nThe problem is that after the first git-bisect good, it looks like this:\n\ng1 - b2 - b1 - M - B\n             /\n     g2 - b3\n\nwhere both g1 and g2 are good, and B is bad. The bisection point is b1. \n(Which makes sense, absolutely.)\n\nAfter the second git-bisect good, it looks like this:\n\n     g3 - M - B\n        /\ng2 - b3\n\nand the bisection point is M.\n\nYour problem, of course, is that it is not possible to pick a commit \n_exactly_ in the middle. So, the number is just an _expected_ number of \nrevisions to test. I am not sure if it is necessary to make this clearer, \nthough, as I fully expect that you just said \"What the heck\" and continued \nbisecting just fine.\n\nCiao,\nDscho\n\nP.S.: if Momo's turtle thinks that your name contains no non-ASCIIs, why \nshould I?\n"},{"id":"37312","messageId":"20070317134639.GA10968@informatik.uni-freiburg.de","threadId":"7271","inReplyTo":"Pine.LNX.4.63.0703170139110.22628@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: [BUG] bisecting miscounts revisions left to test","fromName":"Uwe Kleine-König","fromEmail":"ukleinek@informatik.uni-freiburg.de","sentAt":"2007-03-17T13:46:39Z","receivedAt":"2007-03-17T13:46:39Z","isPatch":false,"sender":{"key":"u.kleine-koenig@pengutronix.de","avatar":"https://gravatar.com/avatar/354b5e3ceb2806a2f1e1e382ac29ddbdad18288654da62b61eb13583a857eee7?d=mp&s=160"},"body":"Hello,\n\nJohannes Schindelin wrote:\n> Hi,\n> \n> On Fri, 16 Mar 2007, Uwe Kleine-König wrote:\n> \n> > zeisberg@cassiopeia:~/gsrc/linux-2.6$ git bisect good\n> > Bisecting: 2 revisions left to test after this\n> > [e7b0d26a86943370c04d6833c6edba2a72a6e240] sysfs: reinstate exclusion between method calls and attribute unregistration\n> > \n> > zeisberg@cassiopeia:~/gsrc/linux-2.6$ git bisect good\n> > Bisecting: 2 revisions left to test after this\n> > [b810cdfcf91d76f603fd48023aede48ced8e6bed] Merge branch 'upstream-linus' of master.kernel.org:/pub/scm/linux/kernel/git/jgarzik/netdev-2.6\n> \n> The problem is that after the first git-bisect good, it looks like this:\n> \n> g1 - b2 - b1 - M - B\n>              /\n>      g2 - b3\nI wonder if bisect really knows that B is bad.  git bisect visualize\ndoesn't mark B (i.e. bac6eefe96204d0ad67d144f2511a6fc487aa594) bad.\nMaybe the problem is, that this is a tag and not a commit?\n\nAfter 2 more \"bisect good\"s I once more get B to test.  If I mark that\nas good, I get \"... was both good and bad\"?\n\nThe commandline is:\n\n\tgit-rev-list --bisect '^069f8256362b7a17da532f0631cee73b4cfee65b' '^08e15e81a40e3241ce93b4a43886f3abda184aa6' '^0bdd0f385a44344f83409b9e00797bfe2596faf8' '^2cb8a57b9851805883dfe92cf5d88a726134a384' '^6ab27c6bf38d5ff71dafeca77b79e7c284804b75' '^a7c999114ecd0c69bd3970272b64d8842b765b21' '^b810cdfcf91d76f603fd48023aede48ced8e6bed' '^bdf3aaf9519ddd8a026b5e04e713d2fa673532e5' '^e7b0d26a86943370c04d6833c6edba2a72a6e240' bac6eefe96204d0ad67d144f2511a6fc487aa594 --\n\nMaybe better \"git-rev-list --bisect $good $bad^ --\" should be used to\nfind the bisection point?\n\n> P.S.: if Momo's turtle thinks that your name contains no non-ASCIIs, why \n> should I?\nYou should differentiate between my user name and my real name.\n\nBest regards\nUwe\n\n-- \nUwe Kleine-König\n\n$ dc << EOF\n[d1-d1<a]sa99d1<a1[rdn555760928P*pz1<a]salax\nEOF\n"},{"id":"37313","messageId":"20070317141209.GA7838@cepheus","threadId":"7271","inReplyTo":"Pine.LNX.4.63.0703170139110.22628@wbgn013.biozentrum.uni-wuerzburg.de","subject":"[PATCH] calculate the maximal number of revisions to test","fromName":"Uwe Kleine-König","fromEmail":"ukleinek@informatik.uni-freiburg.de","sentAt":"2007-03-17T14:12:09Z","receivedAt":"2007-03-17T14:12:09Z","isPatch":true,"sender":{"key":"u.kleine-koenig@pengutronix.de","avatar":"https://gravatar.com/avatar/354b5e3ceb2806a2f1e1e382ac29ddbdad18288654da62b61eb13583a857eee7?d=mp&s=160"},"body":"Up to now the number printed was correct given that the current revision to\ntest is bad.\n\nMoreover I think the number printed was always one to high, this is fixed, too.\n\nSigned-off-by: Uwe Kleine-König <ukleinek@informatik.uni-freiburg.de>\n---\n git-bisect.sh |   10 ++++++++--\n 1 files changed, 8 insertions(+), 2 deletions(-)\n\ndiff --git a/git-bisect.sh b/git-bisect.sh\nindex b1c3a6b..a5b4fdd 100755\n--- a/git-bisect.sh\n+++ b/git-bisect.sh\n@@ -150,8 +150,14 @@ bisect_next() {\n \t    git-diff-tree --pretty $rev\n \t    exit 0\n \tfi\n-\tnr=$(eval \"git-rev-list $rev $good -- $(cat $GIT_DIR/BISECT_NAMES)\" | wc -l) || exit\n-\techo \"Bisecting: $nr revisions left to test after this\"\n+\tnr_bad=$(eval \"git-rev-list $rev^ $good -- $(cat $GIT_DIR/BISECT_NAMES)\" | wc -l) || exit\n+\tnr_good=$(eval \"git-rev-list $bad^ ^$rev $good -- $(cat $GIT_DIR/BISECT_NAMES)\" | wc -l) || exit\n+\tif test \"$nr_bad\" -ge \"$nr_good\"; then\n+\t\tnr=\"$nr_bad\";\n+\telse\n+\t\tnr=\"$nr_good\";\n+\tfi;\n+\techo \"Bisecting: maximal $nr revisions left to test after this\"\n \techo \"$rev\" > \"$GIT_DIR/refs/heads/new-bisect\"\n \tgit checkout -q new-bisect || exit\n \tmv \"$GIT_DIR/refs/heads/new-bisect\" \"$GIT_DIR/refs/heads/bisect\" &&\n-- \n1.5.0.2.260.g2eb065\n\n\n-- \nUwe Kleine-König\n\nhttp://www.google.com/search?q=Planck%27s+constant%3D\n"},{"id":"37323","messageId":"Pine.LNX.4.63.0703171845541.22628@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"7271","inReplyTo":"20070317141209.GA7838@cepheus","subject":"Re: [PATCH] calculate the maximal number of revisions to test","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2007-03-17T17:49:45Z","receivedAt":"2007-03-17T17:49:45Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi zeisberg,\n\nthe subject really could use a \"bisect:\" prefix, and maybe be a little \nclearer to begin with? Imagine how much sense it makes to read the commit \nmessages, and see that some maximal number of revisions is calculated.\n\nOn Sat, 17 Mar 2007, Uwe Kleine-König wrote:\n\n> diff --git a/git-bisect.sh b/git-bisect.sh\n> index b1c3a6b..a5b4fdd 100755\n> --- a/git-bisect.sh\n> +++ b/git-bisect.sh\n> @@ -150,8 +150,14 @@ bisect_next() {\n>  \t    git-diff-tree --pretty $rev\n>  \t    exit 0\n>  \tfi\n> -\tnr=$(eval \"git-rev-list $rev $good -- $(cat $GIT_DIR/BISECT_NAMES)\" | wc -l) || exit\n> -\techo \"Bisecting: $nr revisions left to test after this\"\n> +\tnr_bad=$(eval \"git-rev-list $rev^ $good -- $(cat $GIT_DIR/BISECT_NAMES)\" | wc -l) || exit\n> +\tnr_good=$(eval \"git-rev-list $bad^ ^$rev $good -- $(cat $GIT_DIR/BISECT_NAMES)\" | wc -l) || exit\n> +\tif test \"$nr_bad\" -ge \"$nr_good\"; then\n> +\t\tnr=\"$nr_bad\";\n> +\telse\n> +\t\tnr=\"$nr_good\";\n> +\tfi;\n> +\techo \"Bisecting: maximal $nr revisions left to test after this\"\n\nHow about this instead:\n\n-\techo \"Bisecting: $nr revisions left to test after this\"\n+\techo \"Bisecting: approx. $nr revisions left to test after this\"\n\nsince your version is an approximation (although a conservative one) \nanyway. Hmm?\n\nCiao,\nDscho\n"},{"id":"37330","messageId":"20070317195840.GA20735@informatik.uni-freiburg.de","threadId":"7271","inReplyTo":"Pine.LNX.4.63.0703171845541.22628@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: [PATCH] calculate the maximal number of revisions to test","fromName":"Uwe Kleine-König","fromEmail":"ukleinek@informatik.uni-freiburg.de","sentAt":"2007-03-17T19:58:40Z","receivedAt":"2007-03-17T19:58:40Z","isPatch":true,"sender":{"key":"u.kleine-koenig@pengutronix.de","avatar":"https://gravatar.com/avatar/354b5e3ceb2806a2f1e1e382ac29ddbdad18288654da62b61eb13583a857eee7?d=mp&s=160"},"body":"Hi gene099,\n\n> the subject really could use a \"bisect:\" prefix, and maybe be a little \n> clearer to begin with? Imagine how much sense it makes to read the commit \n> messages, and see that some maximal number of revisions is calculated.\nOK, you're right.  I think the patch is not as complete as it could be.\nI will fix that and resend with a better log.\n \n> > diff --git a/git-bisect.sh b/git-bisect.sh\n> > index b1c3a6b..a5b4fdd 100755\n> > --- a/git-bisect.sh\n> > +++ b/git-bisect.sh\n> > @@ -150,8 +150,14 @@ bisect_next() {\n> >  \t    git-diff-tree --pretty $rev\n> >  \t    exit 0\n> >  \tfi\n> > -\tnr=$(eval \"git-rev-list $rev $good -- $(cat $GIT_DIR/BISECT_NAMES)\" | wc -l) || exit\n> > -\techo \"Bisecting: $nr revisions left to test after this\"\n> > +\tnr_bad=$(eval \"git-rev-list $rev^ $good -- $(cat $GIT_DIR/BISECT_NAMES)\" | wc -l) || exit\n> > +\tnr_good=$(eval \"git-rev-list $bad^ ^$rev $good -- $(cat $GIT_DIR/BISECT_NAMES)\" | wc -l) || exit\n> > +\tif test \"$nr_bad\" -ge \"$nr_good\"; then\n> > +\t\tnr=\"$nr_bad\";\n> > +\telse\n> > +\t\tnr=\"$nr_good\";\n> > +\tfi;\n> > +\techo \"Bisecting: maximal $nr revisions left to test after this\"\n> \n> How about this instead:\n> \n> -\techo \"Bisecting: $nr revisions left to test after this\"\n> +\techo \"Bisecting: approx. $nr revisions left to test after this\"\n> \n> since your version is an approximation (although a conservative one) \n> anyway. Hmm?\nI prefer a wording that points out a maximum.  Earlier today I thougt\nabout this, too, but currently I don't remember my alternative.\n\nBest regards\nUwe\n\n-- \nUwe Kleine-König\n\nhttp://www.google.com/search?q=12+divided+by+3\n"},{"id":"37695","messageId":"20070321210454.GA2844@lala","threadId":"7271","inReplyTo":"20070317195840.GA20735@informatik.uni-freiburg.de","subject":"[PATCH] Bisect: fix calculation of the number of suspicious revisions","fromName":"Uwe Kleine-König","fromEmail":"ukleinek@informatik.uni-freiburg.de","sentAt":"2007-03-21T21:04:54Z","receivedAt":"2007-03-21T21:04:54Z","isPatch":true,"sender":{"key":"u.kleine-koenig@pengutronix.de","avatar":"https://gravatar.com/avatar/354b5e3ceb2806a2f1e1e382ac29ddbdad18288654da62b61eb13583a857eee7?d=mp&s=160"},"body":"Up to now the number printed was calculated assuming that the current revision\nto test is bad.  Given that it's not possible that this always matches the\nnumber of suspicious revs if the current one is good, the maximum of both is\ntaken now.\n\nMoreover I think the number printed was always one to high, this is fixed, too.\n\nSigned-off-by: Uwe Kleine-König <ukleinek@informatik.uni-freiburg.de>\n---\nIn the mail before I wrote that the former version of this patch was not\ncomplete.  This turned out to be a thinko.  So now I only used a better\nSubject, a more verbose log and a hopefully more clear output.\n\n git-bisect.sh |   10 ++++++++--\n 1 files changed, 8 insertions(+), 2 deletions(-)\n\ndiff --git a/git-bisect.sh b/git-bisect.sh\nindex b1c3a6b..aeff732 100755\n--- a/git-bisect.sh\n+++ b/git-bisect.sh\n@@ -150,8 +150,14 @@ bisect_next() {\n \t    git-diff-tree --pretty $rev\n \t    exit 0\n \tfi\n-\tnr=$(eval \"git-rev-list $rev $good -- $(cat $GIT_DIR/BISECT_NAMES)\" | wc -l) || exit\n-\techo \"Bisecting: $nr revisions left to test after this\"\n+\tnr_bad=$(eval \"git-rev-list $rev^ $good -- $(cat $GIT_DIR/BISECT_NAMES)\" | wc -l) || exit\n+\tnr_good=$(eval \"git-rev-list $bad^ ^$rev $good -- $(cat $GIT_DIR/BISECT_NAMES)\" | wc -l) || exit\n+\tif test \"$nr_bad\" -ge \"$nr_good\"; then\n+\t\tnr=\"$nr_bad\";\n+\telse\n+\t\tnr=\"$nr_good\";\n+\tfi;\n+\techo \"Bisecting: up to $nr suspicious revisions left after this test\"\n \techo \"$rev\" > \"$GIT_DIR/refs/heads/new-bisect\"\n \tgit checkout -q new-bisect || exit\n \tmv \"$GIT_DIR/refs/heads/new-bisect\" \"$GIT_DIR/refs/heads/bisect\" &&\n-- \n1.5.0.3\n\n-- \nUwe Kleine-König\n\nhttp://www.google.com/search?q=1+hertz+in+sec**-1\n"},{"id":"37697","messageId":"7vodmmz3wy.fsf@assigned-by-dhcp.cox.net","threadId":"7271","inReplyTo":"20070321210454.GA2844@lala","subject":"Re: [PATCH] Bisect: fix calculation of the number of suspicious revisions","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2007-03-21T21:23:57Z","receivedAt":"2007-03-21T21:23:57Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Uwe Kleine-König  <ukleinek@informatik.uni-freiburg.de> writes:\n\n> Up to now the number printed was calculated assuming that the\n> current revision to test is bad.  Given that it's not possible\n> that this always matches the number of suspicious revs if the\n> current one is good, the maximum of both is taken now.\n>\n> Moreover I think the number printed was always one to high,\n> this is fixed, too.\n\nI know you mean well, but is it really worth an extra rev-list\nfor this off-by-one, I wonder?\n"},{"id":"37698","messageId":"20070321213450.GB17632@informatik.uni-freiburg.de","threadId":"7271","inReplyTo":"20070321210454.GA2844@lala","subject":"Re: [PATCH] Bisect: fix calculation of the number of suspicious revisions","fromName":"Uwe Kleine-König","fromEmail":"ukleinek@informatik.uni-freiburg.de","sentAt":"2007-03-21T21:34:50Z","receivedAt":"2007-03-21T21:34:50Z","isPatch":true,"sender":{"key":"u.kleine-koenig@pengutronix.de","avatar":"https://gravatar.com/avatar/354b5e3ceb2806a2f1e1e382ac29ddbdad18288654da62b61eb13583a857eee7?d=mp&s=160"},"body":"Hello,\n\nUwe Kleine-König wrote:\n>  \tmv \"$GIT_DIR/refs/heads/new-bisect\" \"$GIT_DIR/refs/heads/bisect\" &&\nindependant of my suggested patch, I wonder if that line should better\nuse update-ref.  (This line is older than update-ref.)\n\nBest regards\nUwe\n\n-- \nUwe Kleine-König\n\n$ dc -e \"5735816763073014741799356604682P\"\n"},{"id":"37699","messageId":"20070321213956.GC17632@informatik.uni-freiburg.de","threadId":"7271","inReplyTo":"7vodmmz3wy.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] Bisect: fix calculation of the number of suspicious revisions","fromName":"Uwe Kleine-König","fromEmail":"ukleinek@informatik.uni-freiburg.de","sentAt":"2007-03-21T21:39:56Z","receivedAt":"2007-03-21T21:39:56Z","isPatch":true,"sender":{"key":"u.kleine-koenig@pengutronix.de","avatar":"https://gravatar.com/avatar/354b5e3ceb2806a2f1e1e382ac29ddbdad18288654da62b61eb13583a857eee7?d=mp&s=160"},"body":"Hello Junio,\n\nJunio C Hamano wrote:\n> Uwe Kleine-König  <ukleinek@informatik.uni-freiburg.de> writes:\n> \n> > Up to now the number printed was calculated assuming that the\n> > current revision to test is bad.  Given that it's not possible\n> > that this always matches the number of suspicious revs if the\n> > current one is good, the maximum of both is taken now.\n> >\n> > Moreover I think the number printed was always one to high,\n> > this is fixed, too.\n> \n> I know you mean well, but is it really worth an extra rev-list\n> for this off-by-one, I wonder?\nIt may be more than one.  E.g. \n   b\n  / \\\n /   \\\na--c--e\n \\   /\n  \\ /\n   d\n\nGiven a is bad, e is bad, b is rev to test.\n\nI didn't verify it, but I think the current code gives one (as it\nassumes b is bad and counts one to much).  If b is good there are two\nsuspicious left.  I'm sure you can construct an example where it differs\nstill more.\n\nBest regards\nUwe\n\n-- \nUwe Kleine-König\n\nhttp://www.google.com/search?q=half+a+cup+in+teaspoons\n"},{"id":"37700","messageId":"7vk5xaz2qn.fsf@assigned-by-dhcp.cox.net","threadId":"7271","inReplyTo":"20070321213450.GB17632@informatik.uni-freiburg.de","subject":"Re: [PATCH] Bisect: fix calculation of the number of suspicious revisions","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2007-03-21T21:49:20Z","receivedAt":"2007-03-21T21:49:20Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Uwe Kleine-König  <ukleinek@informatik.uni-freiburg.de> writes:\n\n> Uwe Kleine-König wrote:\n>>  \tmv \"$GIT_DIR/refs/heads/new-bisect\" \"$GIT_DIR/refs/heads/bisect\" &&\n> independant of my suggested patch, I wonder if that line should better\n> use update-ref.  (This line is older than update-ref.)\n\nYup.  If we can clean things up to use update-ref and\nsymbolic-ref properly that would be nice.  Re-counting is an\nindependent issue as you say.\n\nAlso we may perhaps want to stop using bisect branch but use\ndetached HEAD (but still refs/bisect hierarchy)?  This one I am\nnot so sure, but one less reserved name.\n"},{"id":"37701","messageId":"Pine.LNX.4.64.0703211521290.6730@woody.linux-foundation.org","threadId":"7271","inReplyTo":"20070321210454.GA2844@lala","subject":"Re: [PATCH] Bisect: fix calculation of the number of suspicious revisions","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-03-21T22:27:29Z","receivedAt":"2007-03-21T22:27:29Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Wed, 21 Mar 2007, Uwe Kleine-König wrote:\n>\n> Up to now the number printed was calculated assuming that the current revision\n> to test is bad.  Given that it's not possible that this always matches the\n> number of suspicious revs if the current one is good, the maximum of both is\n> taken now.\n\nHow about adding a new flag to \"git-rev-list\", to make it count both ways? \nDoing this whole\n\n\tnr = $(eval \"git-rev-list ... | wc -l\")\n\nwas ugly to begin with, and you just made it doubly ugly.\n\nAnd the thing is, \"git-rev-list --bisect\" will obviously already have \ncalculated these numbers just to _pick_ the revision in the first place, \nso it's a bit sad then execute it twice more (giving it back the result \n*it* gave us in the first place!).\n\nSo we could perhaps change the original\n\n\trev=$(eval \"git-rev-list --bisect $good $bad -- $(cat $GIT_DIR/BISECT_NAMES)\")\n\nwith something nicer.\n\n(In fact, I would also suggest we drop or try to fix BISECT_NAMES support, \nwhile at it - it never really worked, and iirc it was partly exactly \n*because* of the end-condition not being handled right).\n\n\t\tLinus"},{"id":"37708","messageId":"7vlkhqxefy.fsf@assigned-by-dhcp.cox.net","threadId":"7271","inReplyTo":"Pine.LNX.4.64.0703211521290.6730@woody.linux-foundation.org","subject":"Re: [PATCH] Bisect: fix calculation of the number of suspicious revisions","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2007-03-22T01:19:29Z","receivedAt":"2007-03-22T01:19:29Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds <torvalds@linux-foundation.org> writes:\n\n> (In fact, I would also suggest we drop or try to fix BISECT_NAMES support, \n> while at it - it never really worked, and iirc it was partly exactly \n> *because* of the end-condition not being handled right).\n\nI am not opposed to dropping bisect-names.\n\nI was having fun with this patch, which made an experiment to\nbisect between v1.0.0 and v1.5.0 in git.git repository by\nalternately saying good and bad go from 3.68 seconds to 1.26\nseconds.  Bisecting the kernel between v2.6.18 and v2.6.20 with\nthe same test script takes 21.84 seconds vs 4.22 seconds.\n\nThe idea is that count_distance() is expensive and we would want\nto avoid it when we can.  When a commit has only one relevant\nparent commit, then the number of commits that commit can reach\nis exactly one more than the number of commits that the parent\ncan reach, so we can avoid running count_distance() on commits\nthat are on straight single strand of pearls.  On the other\nhand, for a merge commit, because the commits reachable from one\nparent can be reachable from another parent, you cannot just add\nthe parents' up (plus one for yourself).\n\nSo the patch runs count_distance() on merges (and uses util\nfield to remember them), and then builds the rest by going\nbackwards, finding each commit whose distance is not yet known\nbut the distance of its (sole) parent is known, add one to that,\nuntil we count distance for everybody.\n\nAnother small optimization is whenever we find a half-way (that\nis, a commit whose distance is half of the number of all\ncommits), we say that is good enough.\n\n---\n\nHere is the test script that I ran /usr/bin/time on to\nbenchmark.  It takes three params: path to git-rev-list, a good\ncommit (i.e. older one), and a bad commit.  The script\nalternately says \"bisect good\" and \"bisect bad\" and finishes\nwhen it narrows down the suspects to one.\n\nEven with the \"half is good enough\" optimization in place,\nsomehow I am getting the same bisect sequence to narrow down\nbetween v2.6.18 and v2.6.20 (the kernel) and v1.0.0 and v1.5.0\n(git).\n\n-- >8 -- test script -- >8 --\n#!/bin/sh\ncmd=$1\ngood=$(git rev-parse --verify \"$2\")\nbad=$(git rev-parse --verify \"$3\")\nflip=good\n\nrun_one () {\n\tbisect=$($cmd --bisect $bad --not $good)\n\tifgood=$(git-rev-list $bad --not $good $bisect | wc -l)\n\tifbad=$(git-rev-list $bisect --not $good | wc -l)\n\techo \"bad $bad\"\n\techo \"good $good\"\n\techo \"ifgood $ifgood\"\n\techo \"ifbad $ifbad\"\n\techo\n\n\tif test \"$bisect\" = \"$bad\"\n\tthen\n\t\tfalse\n\telse\n\t\tcase \"$flip\" in\n\t\tgood)\n\t\t\tgood=\"$good $bisect\"\n\t\t\tflip=bad\n\t\t\t;;\n\t\tbad)\n\t\t\tbad=\"$bisect\"\n\t\t\tflip=good\n\t\t\t;;\n\t\tesac\n\t\ttrue\n\tfi\n}\n\n\nwhile run_one\ndo\n\t:\ndone\n-- >8 -- end of test script -- >8 --\n\n builtin-rev-list.c |  169 +++++++++++++++++++++++++++++++++++++++++++++++++++-\n 1 files changed, 167 insertions(+), 2 deletions(-)\n\ndiff --git a/builtin-rev-list.c b/builtin-rev-list.c\nindex c2db5a5..c43d88d 100644\n--- a/builtin-rev-list.c\n+++ b/builtin-rev-list.c\n@@ -203,6 +203,167 @@ static struct commit_list *find_bisection(struct commit_list *list)\n \treturn best;\n }\n \n+static inline int commit_interesting(struct commit_list *elem)\n+{\n+\tunsigned flags = elem->item->object.flags;\n+\tif (flags & UNINTERESTING)\n+\t\treturn 0;\n+\treturn (!revs.prune_fn || (flags & TREECHANGE));\n+}\n+\n+static inline int weight(struct commit_list *elem)\n+{\n+\treturn *((int*)(elem->item->util));\n+}\n+\n+static inline void weight_set(struct commit_list *elem, int weight)\n+{\n+\t*((int*)(elem->item->util)) = weight;\n+}\n+\n+static int count_interesting_parents(struct commit_list *elem)\n+{\n+\tint cnt = 0;\n+\tif (!elem->item->parents)\n+\t\treturn cnt;\n+\tfor (elem = elem->item->parents; elem; elem = elem->next) {\n+\t\tif (commit_interesting(elem))\n+\t\t\tcnt++;\n+\t}\n+\treturn cnt;\n+}\n+\n+static struct commit_list *find_bisection_2(struct commit_list *list)\n+{\n+\tint n, nr, last_counted, counted, distance;\n+\tstruct commit_list *p, *best;\n+\tint *weights;\n+\n+\tfor (nr = 0, p = list; p; p = p->next) {\n+\t\tif (commit_interesting(p))\n+\t\t\tnr++;\n+\t}\n+\tweights = xcalloc(nr, sizeof(int*));\n+\tcounted = 0;\n+\n+\tfor (n = 0, p = list; p; p = p->next) {\n+\t\tif (!commit_interesting(p))\n+\t\t\tcontinue;\n+\t\tif (commit_interesting(p)) {\n+\t\t\t/*\n+\t\t\t * positive weight is the number of interesting\n+\t\t\t * commits it can reach, including itself.\n+\t\t\t * weight = 0 means it has one parent and\n+\t\t\t * its distance is unknown.\n+\t\t\t * weight < 0 means it has more than one\n+\t\t\t * parent and its distance is unknown.\n+\t\t\t */\n+\t\t\tp->item->util = &weights[n++];\n+\t\t\tswitch (count_interesting_parents(p)) {\n+\t\t\tcase 0:\n+\t\t\t\tweight_set(p, 1);\n+\t\t\t\tcounted++;\n+\t\t\t\tbreak;\n+\t\t\tcase 1:\n+\t\t\t\tweight_set(p, 0);\n+\t\t\t\tbreak;\n+\t\t\tdefault:\n+\t\t\t\tweight_set(p, -1);\n+\t\t\t\tbreak;\n+\t\t\t}\n+\t\t}\n+\t}\n+\n+\t/*\n+\t * If you have only one parent in the resulting set\n+\t * then you can reach one commit more than that parent\n+\t * can reach.  So we do not have to run the expensive\n+\t * count_distance() for single strand of pearls.\n+\t *\n+\t * However, if you have more than one parents, you cannot\n+\t * just add their distance and one for yourself, since\n+\t * they usually reach the same ancestor and you would\n+\t * end up counting them twice that way.\n+\t *\n+\t * So we will first count distance of merges the usual\n+\t * way, and then fill the blanks using cheaper algorithm.\n+\t */\n+\tfor (p = list; p; p = p->next) {\n+\t\tif (!commit_interesting(p))\n+\t\t\tcontinue;\n+\t\tn = weight(p);\n+\t\tif (0 <= n)\n+\t\t\tcontinue;\n+\t\tdistance = count_distance(p);\n+\t\tclear_distance(p);\n+\t\tweight_set(p, distance);\n+\t\tdistance = weight(p) * 2;\n+\t\tif (nr == distance || (nr+1) == distance) {\n+\t\t\tp->next = NULL;\n+\t\t\tfree(weights);\n+\t\t\treturn p;\n+\t\t}\n+\t\tcounted++;\n+\t}\n+\n+\twhile (counted < nr) {\n+\t\tdo {\n+\t\t\tlast_counted = counted;\n+\t\t\tfor (p = list; p; p = p->next) {\n+\t\t\t\tstruct commit_list *q;\n+\n+\t\t\t\tif (!commit_interesting(p) || 0 < weight(p))\n+\t\t\t\t\tcontinue;\n+\t\t\t\tif (weight(p) < 0)\n+\t\t\t\t\tdie(\"OOPS\");\n+\t\t\t\tfor (q = p->item->parents;\n+\t\t\t\t     q;\n+\t\t\t\t     q = q->next)\n+\t\t\t\t\tif (commit_interesting(q) &&\n+\t\t\t\t\t    0 < weight(q))\n+\t\t\t\t\t\tbreak;\n+\t\t\t\tif (!q)\n+\t\t\t\t\tcontinue;\n+\t\t\t\tweight_set(p, weight(q)+1);\n+\t\t\t\tcounted++;\n+\n+\t\t\t\t/*\n+\t\t\t\t * Do we happen to have found one that\n+\t\t\t\t * has the desired half-weight?\n+\t\t\t\t */\n+\t\t\t\tdistance = weight(p) * 2;\n+\t\t\t\tif (nr == distance || (nr+1) == distance) {\n+\t\t\t\t\tp->next = NULL;\n+\t\t\t\t\tfree(weights);\n+\t\t\t\t\treturn p;\n+\t\t\t\t}\n+\t\t\t}\n+\t\t} while (counted != last_counted);\n+\n+\t}\n+\n+\t/* Then find the best one */\n+\tcounted = 0;\n+\tbest = list;\n+\tfor (p = list; p; p = p->next) {\n+\t\tif (!commit_interesting(p))\n+\t\t\tcontinue;\n+\t\tdistance = weight(p);\n+\t\tif (nr - distance < distance)\n+\t\t\tdistance = nr - distance;\n+\t\tif (distance > counted) {\n+\t\t\tbest = p;\n+\t\t\tcounted = distance;\n+\t\t}\n+\t}\n+\tif (best) {\n+\t\tbest->next = NULL;\n+\t}\n+\tfree(weights);\n+\treturn best;\n+}\n+\n+\n static void read_revisions_from_stdin(struct rev_info *revs)\n {\n \tchar line[1000];\n@@ -285,8 +446,12 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)\n \tif (revs.tree_objects)\n \t\tmark_edges_uninteresting(revs.commits, &revs, show_edge);\n \n-\tif (bisect_list)\n-\t\trevs.commits = find_bisection(revs.commits);\n+\tif (bisect_list) {\n+\t\tif (!revs.prune_fn)\n+\t\t\trevs.commits = find_bisection_2(revs.commits);\n+\t\telse\n+\t\t\trevs.commits = find_bisection(revs.commits);\n+\t}\n \n \ttraverse_commit_list(&revs, show_commit, show_object);\n \n"},{"id":"37709","messageId":"Pine.LNX.4.63.0703220240590.4045@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"7271","inReplyTo":"Pine.LNX.4.64.0703211521290.6730@woody.linux-foundation.org","subject":"[PATCH] bisect: show the maximal number of commits to be tested","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2007-03-22T01:43:18Z","receivedAt":"2007-03-22T01:43:18Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"\nSince git-bisect already asks rev-list to find the midpoint (and rev-list\nconsequently counts the number of commits), rev-list can pass it the\nmaximal number of commits.\n\nAs a bonus, this avoids an extra call to rev-list.\n\nMiscalculation noticed by Uwe, implementation suggested by Linus.\n\nSigned-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>\n---\n\n\tOn Wed, 21 Mar 2007, Linus Torvalds wrote:\n\n\t> On Wed, 21 Mar 2007, Uwe Kleine-König wrote:\n\t> >\n\t> > Up to now the number printed was calculated assuming that the \n\t> > current revision to test is bad.  Given that it's not possible \n\t> > that this always matches the number of suspicious revs if the \n\t> > current one is good, the maximum of both is taken now.\n\t> \n\t> How about adding a new flag to \"git-rev-list\", to make it count \n\t> both ways?\n\n\tDid I understand you correctly?\n\n Documentation/git-rev-list.txt |    8 ++++++++\n builtin-rev-list.c             |   40 +++++++++++++++++++++++++++++++++-------\n git-bisect.sh                  |    7 +++----\n 3 files changed, 44 insertions(+), 11 deletions(-)\n\ndiff --git a/Documentation/git-rev-list.txt b/Documentation/git-rev-list.txt\nindex 4f145ea..5f6f2a3 100644\n--- a/Documentation/git-rev-list.txt\n+++ b/Documentation/git-rev-list.txt\n@@ -26,6 +26,7 @@ SYNOPSIS\n \t     [ [\\--objects | \\--objects-edge] [ \\--unpacked ] ]\n \t     [ \\--pretty | \\--header ]\n \t     [ \\--bisect ]\n+\t     [ \\--bisect-vars ]\n \t     [ \\--merge ]\n \t     [ \\--reverse ]\n \t     [ \\--walk-reflogs ]\n@@ -249,6 +250,13 @@ introduces a regression is thus reduced to a binary search: repeatedly\n generate and test new 'midpoint's until the commit chain is of length\n one.\n \n+--bisect-vars::\n+\n+This calculates the same as --bisect, but outputs a line ready to be\n+eval'ed by the shell. This line will assign the name of the midpoint\n+revision to the variable 'rev', and the maximal number of commits to\n+be tested after this revision to 'nr'.\n+\n --\n \n Commit Ordering\ndiff --git a/builtin-rev-list.c b/builtin-rev-list.c\nindex c2db5a5..b653975 100644\n--- a/builtin-rev-list.c\n+++ b/builtin-rev-list.c\n@@ -36,12 +36,12 @@ static const char rev_list_usage[] =\n \"    --abbrev=nr | --no-abbrev\\n\"\n \"    --abbrev-commit\\n\"\n \"  special purpose:\\n\"\n-\"    --bisect\"\n+\"    --bisect\\n\"\n+\"    --bisect-vars\"\n ;\n \n static struct rev_info revs;\n \n-static int bisect_list;\n static int show_timestamp;\n static int hdr_termination;\n static const char *header_prefix;\n@@ -168,7 +168,8 @@ static void clear_distance(struct commit_list *list)\n \t}\n }\n \n-static struct commit_list *find_bisection(struct commit_list *list)\n+static struct commit_list *find_bisection(struct commit_list *list,\n+\tint *nr_bad, int *nr_good)\n {\n \tint nr, closest;\n \tstruct commit_list *p, *best;\n@@ -198,8 +199,20 @@ static struct commit_list *find_bisection(struct commit_list *list)\n \t\t\tclosest = distance;\n \t\t}\n \t}\n-\tif (best)\n+\tif (best) {\n \t\tbest->next = NULL;\n+\t\t/*\n+\t\t * The variable nr_bad holds the number of revisions\n+\t\t * to be tested if \"best\" is marked as bad, and nr_good\n+\t\t * the number if \"best\" is marked as good.\n+\t\t *\n+\t\t * Since the given range is <good>..<bad>, we have to\n+\t\t * subtract one, because both <good> and <bad> were\n+\t\t * already tested.\n+\t\t */\n+\t\t*nr_bad = nr - closest - 1;\n+\t\t*nr_good = closest - 1;\n+\t}\n \treturn best;\n }\n \n@@ -224,7 +237,7 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)\n {\n \tstruct commit_list *list;\n \tint i;\n-\tint read_from_stdin = 0;\n+\tint read_from_stdin = 0, bisect_list = 0, bisect_show_vars = 0;\n \n \tgit_config(git_default_config);\n \tinit_revisions(&revs, prefix);\n@@ -247,6 +260,11 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)\n \t\t\tbisect_list = 1;\n \t\t\tcontinue;\n \t\t}\n+\t\tif (!strcmp(arg, \"--bisect-vars\")) {\n+\t\t\tbisect_list = 1;\n+\t\t\tbisect_show_vars = 1;\n+\t\t\tcontinue;\n+\t\t}\n \t\tif (!strcmp(arg, \"--stdin\")) {\n \t\t\tif (read_from_stdin++)\n \t\t\t\tdie(\"--stdin given twice?\");\n@@ -285,8 +303,16 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)\n \tif (revs.tree_objects)\n \t\tmark_edges_uninteresting(revs.commits, &revs, show_edge);\n \n-\tif (bisect_list)\n-\t\trevs.commits = find_bisection(revs.commits);\n+\tif (bisect_list) {\n+\t\tint nr_bad = 0, nr_good = 0;\n+\t\trevs.commits = find_bisection(revs.commits, &nr_bad, &nr_good);\n+\t\tif (bisect_show_vars) {\n+\t\t\tprintf(\"rev=%s;nr=%d;\\n\", !revs.commits ? \"\" :\n+\t\t\t\tsha1_to_hex(revs.commits->item->object.sha1),\n+\t\t\t\tnr_bad > nr_good ? nr_bad : nr_good);\n+\t\t\treturn 0;\n+\t\t}\n+\t}\n \n \ttraverse_commit_list(&revs, show_commit, show_object);\n \ndiff --git a/git-bisect.sh b/git-bisect.sh\nindex b1c3a6b..cd5e3c9 100755\n--- a/git-bisect.sh\n+++ b/git-bisect.sh\n@@ -138,9 +138,9 @@ bisect_next() {\n \tbisect_autostart\n \tbisect_next_check fail\n \tbad=$(git-rev-parse --verify refs/bisect/bad) &&\n-\tgood=$(git-rev-parse --sq --revs-only --not \\\n-\t\t$(cd \"$GIT_DIR\" && ls refs/bisect/good-*)) &&\n-\trev=$(eval \"git-rev-list --bisect $good $bad -- $(cat $GIT_DIR/BISECT_NAMES)\") || exit\n+\tgood=$(git-rev-parse --revs-only --not \\\n+\t\t$(cd \"$GIT_DIR\" && ls refs/bisect/good-*)) || exit\n+\teval \"$(git-rev-list --bisect-vars $good $bad -- $(cat $GIT_DIR/BISECT_NAMES))\" || exit\n \tif [ -z \"$rev\" ]; then\n \t    echo \"$bad was both good and bad\"\n \t    exit 1\n@@ -150,7 +150,6 @@ bisect_next() {\n \t    git-diff-tree --pretty $rev\n \t    exit 0\n \tfi\n-\tnr=$(eval \"git-rev-list $rev $good -- $(cat $GIT_DIR/BISECT_NAMES)\" | wc -l) || exit\n \techo \"Bisecting: $nr revisions left to test after this\"\n \techo \"$rev\" > \"$GIT_DIR/refs/heads/new-bisect\"\n \tgit checkout -q new-bisect || exit\n-- \n1.5.1.rc1.2306.g3d2f\n"},{"id":"37711","messageId":"7vhcsexcc3.fsf@assigned-by-dhcp.cox.net","threadId":"7271","inReplyTo":"Pine.LNX.4.63.0703220240590.4045@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: [PATCH] bisect: show the maximal number of commits to be tested","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2007-03-22T02:05:00Z","receivedAt":"2007-03-22T02:05:00Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:\n\n> Since git-bisect already asks rev-list to find the midpoint (and rev-list\n> consequently counts the number of commits), rev-list can pass it the\n> maximal number of commits.\n>\n> As a bonus, this avoids an extra call to rev-list.\n>\n> Miscalculation noticed by Uwe, implementation suggested by Linus.\n>\n> Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>\n> ---\n>\n> \tOn Wed, 21 Mar 2007, Linus Torvalds wrote:\n>\n> \t> On Wed, 21 Mar 2007, Uwe Kleine-König wrote:\n> \t> >\n> \t> > Up to now the number printed was calculated assuming that the \n> \t> > current revision to test is bad.  Given that it's not possible \n> \t> > that this always matches the number of suspicious revs if the \n> \t> > current one is good, the maximum of both is taken now.\n> \t> \n> \t> How about adding a new flag to \"git-rev-list\", to make it count \n> \t> both ways?\n>\n> \tDid I understand you correctly?\n\nWhy not show both, or at least total?\n\nThis and the earlier optimization patch steps on each others\ntoes, ouch ;-).\n"},{"id":"37712","messageId":"Pine.LNX.4.63.0703220314440.4045@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"7271","inReplyTo":"7vhcsexcc3.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] bisect: show the maximal number of commits to be tested","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2007-03-22T02:15:20Z","receivedAt":"2007-03-22T02:15:20Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Wed, 21 Mar 2007, Junio C Hamano wrote:\n\n> Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:\n> \n> > Since git-bisect already asks rev-list to find the midpoint (and rev-list\n> > consequently counts the number of commits), rev-list can pass it the\n> > maximal number of commits.\n> >\n> > As a bonus, this avoids an extra call to rev-list.\n> >\n> > Miscalculation noticed by Uwe, implementation suggested by Linus.\n> >\n> > Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>\n> > ---\n> >\n> > \tOn Wed, 21 Mar 2007, Linus Torvalds wrote:\n> >\n> > \t> On Wed, 21 Mar 2007, Uwe Kleine-König wrote:\n> > \t> >\n> > \t> > Up to now the number printed was calculated assuming that the \n> > \t> > current revision to test is bad.  Given that it's not possible \n> > \t> > that this always matches the number of suspicious revs if the \n> > \t> > current one is good, the maximum of both is taken now.\n> > \t> \n> > \t> How about adding a new flag to \"git-rev-list\", to make it count \n> > \t> both ways?\n> >\n> > \tDid I understand you correctly?\n> \n> Why not show both, or at least total?\n> \n> This and the earlier optimization patch steps on each others\n> toes, ouch ;-).\n\nYes... on both accounts. I'll let your patches settle first, and resubmit.\n\nCiao,\nDscho\n"},{"id":"37720","messageId":"7v7it9yecm.fsf_-_@assigned-by-dhcp.cox.net","threadId":"7271","inReplyTo":"Pine.LNX.4.63.0703220240590.4045@wbgn013.biozentrum.uni-wuerzburg.de","subject":"[PATCH 1/2] git-rev-list: add --bisect-vars option.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2007-03-22T06:36:09Z","receivedAt":"2007-03-22T06:36:09Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"This adds --bisect-vars option to rev-list.  The output is suitable\nfor `eval` in shell and defines five variables:\n\n - bisect_rev is the next revision to test.\n - bisect_nr is the expected number of commits to test after\n   bisect_rev is tested.\n - bisect_good is the expected number of commits to test\n   if bisect_rev turns out to be good.\n - bisect_bad is the expected number of commits to test\n   if bisect_rev turns out to be bad.\n - bisect_all is the number of commits we are bisecting right now.\n\nThe documentation text was partly stolen from Joahnnes\nSchindelin's patch.\n\nSigned-off-by: Junio C Hamano <junkio@cox.net>\n---\n\n * This comes first, on top of 'master', without any of my\n   optimization hack.\n\n Documentation/git-rev-list.txt |   13 +++++++++\n builtin-rev-list.c             |   54 +++++++++++++++++++++++++++++++++++----\n 2 files changed, 61 insertions(+), 6 deletions(-)\n\ndiff --git a/Documentation/git-rev-list.txt b/Documentation/git-rev-list.txt\nindex 4f145ea..3fa45b8 100644\n--- a/Documentation/git-rev-list.txt\n+++ b/Documentation/git-rev-list.txt\n@@ -26,6 +26,7 @@ SYNOPSIS\n \t     [ [\\--objects | \\--objects-edge] [ \\--unpacked ] ]\n \t     [ \\--pretty | \\--header ]\n \t     [ \\--bisect ]\n+\t     [ \\--bisect-vars ]\n \t     [ \\--merge ]\n \t     [ \\--reverse ]\n \t     [ \\--walk-reflogs ]\n@@ -249,6 +250,18 @@ introduces a regression is thus reduced to a binary search: repeatedly\n generate and test new 'midpoint's until the commit chain is of length\n one.\n \n+--bisect-vars::\n+\n+This calculates the same as `--bisect`, but outputs text ready\n+to be eval'ed by the shell. These lines will assign the name of\n+the midpoint revision to the variable `bisect_rev`, and the\n+expected number of commits to be tested after `bisect_rev` is\n+tested to `bisect_nr`, the expected number of commits to be\n+tested if `bisect_rev` turns out to be good to `bisect_good`,\n+the expected number of commits to be tested if `bisect_rev`\n+turns out to be bad to `bisect_bad`, and the number of commits\n+we are bisecting right now to `bisect_all`.\n+\n --\n \n Commit Ordering\ndiff --git a/builtin-rev-list.c b/builtin-rev-list.c\nindex c2db5a5..723e4d4 100644\n--- a/builtin-rev-list.c\n+++ b/builtin-rev-list.c\n@@ -36,7 +36,8 @@ static const char rev_list_usage[] =\n \"    --abbrev=nr | --no-abbrev\\n\"\n \"    --abbrev-commit\\n\"\n \"  special purpose:\\n\"\n-\"    --bisect\"\n+\"    --bisect\\n\"\n+\"    --bisect-vars\"\n ;\n \n static struct rev_info revs;\n@@ -168,7 +169,8 @@ static void clear_distance(struct commit_list *list)\n \t}\n }\n \n-static struct commit_list *find_bisection(struct commit_list *list)\n+static struct commit_list *find_bisection(struct commit_list *list,\n+\t\t\t\t\t  int *reaches, int *all)\n {\n \tint nr, closest;\n \tstruct commit_list *p, *best;\n@@ -180,21 +182,23 @@ static struct commit_list *find_bisection(struct commit_list *list)\n \t\t\tnr++;\n \t\tp = p->next;\n \t}\n+\t*all = nr;\n \tclosest = 0;\n \tbest = list;\n \n \tfor (p = list; p; p = p->next) {\n-\t\tint distance;\n+\t\tint distance, reach;\n \n \t\tif (revs.prune_fn && !(p->item->object.flags & TREECHANGE))\n \t\t\tcontinue;\n \n-\t\tdistance = count_distance(p);\n+\t\tdistance = reach = count_distance(p);\n \t\tclear_distance(list);\n \t\tif (nr - distance < distance)\n \t\t\tdistance = nr - distance;\n \t\tif (distance > closest) {\n \t\t\tbest = p;\n+\t\t\t*reaches = reach;\n \t\t\tclosest = distance;\n \t\t}\n \t}\n@@ -225,6 +229,7 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)\n \tstruct commit_list *list;\n \tint i;\n \tint read_from_stdin = 0;\n+\tint bisect_show_vars = 0;\n \n \tgit_config(git_default_config);\n \tinit_revisions(&revs, prefix);\n@@ -247,6 +252,11 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)\n \t\t\tbisect_list = 1;\n \t\t\tcontinue;\n \t\t}\n+\t\tif (!strcmp(arg, \"--bisect-vars\")) {\n+\t\t\tbisect_list = 1;\n+\t\t\tbisect_show_vars = 1;\n+\t\t\tcontinue;\n+\t\t}\n \t\tif (!strcmp(arg, \"--stdin\")) {\n \t\t\tif (read_from_stdin++)\n \t\t\t\tdie(\"--stdin given twice?\");\n@@ -285,8 +295,40 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)\n \tif (revs.tree_objects)\n \t\tmark_edges_uninteresting(revs.commits, &revs, show_edge);\n \n-\tif (bisect_list)\n-\t\trevs.commits = find_bisection(revs.commits);\n+\tif (bisect_list) {\n+\t\tint reaches = reaches, all = all;\n+\n+\t\trevs.commits = find_bisection(revs.commits,\n+\t\t\t\t\t      &reaches, &all);\n+\t\tif (bisect_show_vars) {\n+\t\t\tint cnt;\n+\t\t\tif (!revs.commits)\n+\t\t\t\treturn 1;\n+\t\t\t/*\n+\t\t\t * revs.commits can reach \"reaches\" commits among\n+\t\t\t * \"all\" commits.  If it is good, then there are\n+\t\t\t * (all-reaches) commits left to be bisected.\n+\t\t\t * On the other hand, if it is bad, then the set\n+\t\t\t * to bisect is \"reaches\".\n+\t\t\t * A bisect set of size N has (N-1) commits further\n+\t\t\t * to test, as we already know one bad one.\n+\t\t\t */\n+\t\t\tcnt = all-reaches;\n+\t\t\tif (cnt < reaches)\n+\t\t\t\tcnt = reaches;\n+\t\t\tprintf(\"bisect_rev=%s\\n\"\n+\t\t\t       \"bisect_nr=%d\\n\"\n+\t\t\t       \"bisect_good=%d\\n\"\n+\t\t\t       \"bisect_bad=%d\\n\"\n+\t\t\t       \"bisect_all=%d\\n\",\n+\t\t\t       sha1_to_hex(revs.commits->item->object.sha1),\n+\t\t\t       cnt - 1,\n+\t\t\t       all - reaches - 1,\n+\t\t\t       reaches - 1,\n+\t\t\t       all);\n+\t\t\treturn 0;\n+\t\t}\n+\t}\n \n \ttraverse_commit_list(&revs, show_commit, show_object);\n \n-- \n1.5.1.rc1.610.g3ba7\n"},{"id":"37721","messageId":"7vvegtwzhb.fsf_-_@assigned-by-dhcp.cox.net","threadId":"7271","inReplyTo":"Pine.LNX.4.63.0703220240590.4045@wbgn013.biozentrum.uni-wuerzburg.de","subject":"[PATCH 2/2] git-rev-list --bisect: optimization","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2007-03-22T06:42:40Z","receivedAt":"2007-03-22T06:42:40Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"This improves the performance of revision bisection.\n\nThe idea is to avoid rather expensive count_distance() function,\nwhich counts the number of commits that are reachable from any\ngiven commit (including itself) in the set.  When a commit has\nonly one relevant parent commit, the number of commits the\ncommit can reach is exactly the number of commits that the\nparent can reach plus one; instead of running count_distance()\non commits that are on straight single strand of pearls, we can\njust add one to the parents' count.\n\nOn the other hand, for a merge commit, because the commits\nreachable from one parent can be reachable from another parent,\nyou cannot just add the parents' counts up plus one for the\ncommit itself; that would overcount ancestors that are reachable\nfrom more than one parents.\n\nThe algorithm used in the patch runs count_distance() on merge\ncommits, and uses the util field of commit objects to remember\nthem.  After that, the number of commits reachable from each of\nthe remaining commits is counted by finding a commit whose count\nis not yet known but the count for its (sole) parent is known,\nand adding one to the parent's count, until we assign numbers to\neverybody.\n\nAnother small optimization is whenever we find a half-way (that\nis, a commit that can reach exactly half of the commits in the\nset), we stop giving counts to remaining commits.\n\nThe performance to bisect between v1.0.0 and v1.5.0 in git.git\nrepository was improved by saying good and bad in turns from\n3.68 seconds down to 1.26 seconds.  Bisecting the kernel between\nv2.6.18 and v2.6.20 was sped up from 21.84 seconds down to 4.22\nseconds.\n\nSigned-off-by: Junio C Hamano <junkio@cox.net>\n---\n\n * This is a rebase on top of updated Johannes's patch, which is\n   [1/2] of this series.\n\n   I am not enabling this for path limited case, so it is still\n   in a WIP state.  I am not sure if parent rewriting is doing\n   the right thing (if so, then we should be able to assume that\n   \"interesting\" commits are already made contiguous and we can\n   keep giving the number one higher than the parent to commits\n   on a single-strand-of-pearls like this patch does).\n\n builtin-rev-list.c |  162 +++++++++++++++++++++++++++++++++++++++++++++++++++-\n 1 files changed, 160 insertions(+), 2 deletions(-)\n\ndiff --git a/builtin-rev-list.c b/builtin-rev-list.c\nindex 723e4d4..111ba60 100644\n--- a/builtin-rev-list.c\n+++ b/builtin-rev-list.c\n@@ -207,6 +207,160 @@ static struct commit_list *find_bisection(struct commit_list *list,\n \treturn best;\n }\n \n+static inline int commit_interesting(struct commit_list *elem)\n+{\n+\tunsigned flags = elem->item->object.flags;\n+\tif (flags & UNINTERESTING)\n+\t\treturn 0;\n+\treturn (!revs.prune_fn || (flags & TREECHANGE));\n+}\n+\n+static inline int weight(struct commit_list *elem)\n+{\n+\treturn *((int*)(elem->item->util));\n+}\n+\n+static inline void weight_set(struct commit_list *elem, int weight)\n+{\n+\t*((int*)(elem->item->util)) = weight;\n+}\n+\n+static int count_interesting_parents(struct commit_list *elem)\n+{\n+\tint cnt = 0;\n+\tif (!elem->item->parents)\n+\t\treturn cnt;\n+\tfor (elem = elem->item->parents; elem; elem = elem->next) {\n+\t\tif (commit_interesting(elem))\n+\t\t\tcnt++;\n+\t}\n+\treturn cnt;\n+}\n+\n+static struct commit_list *find_bisection_2(struct commit_list *list,\n+\t\t\t\t\t    int *reaches, int *all)\n+{\n+\tint n, nr, counted, distance;\n+\tstruct commit_list *p, *best;\n+\tint *weights;\n+\n+\tfor (nr = 0, p = list; p; p = p->next) {\n+\t\tif (commit_interesting(p))\n+\t\t\tnr++;\n+\t}\n+\t*all = nr;\n+\tweights = xcalloc(nr, sizeof(int*));\n+\tcounted = 0;\n+\n+\tfor (n = 0, p = list; p; p = p->next) {\n+\t\tif (!commit_interesting(p))\n+\t\t\tcontinue;\n+\t\tif (commit_interesting(p)) {\n+\t\t\t/*\n+\t\t\t * positive weight is the number of interesting\n+\t\t\t * commits it can reach, including itself.\n+\t\t\t * weight = 0 means it has one parent and\n+\t\t\t * its distance is unknown.\n+\t\t\t * weight < 0 means it has more than one\n+\t\t\t * parent and its distance is unknown.\n+\t\t\t */\n+\t\t\tp->item->util = &weights[n++];\n+\t\t\tswitch (count_interesting_parents(p)) {\n+\t\t\tcase 0:\n+\t\t\t\tweight_set(p, 1);\n+\t\t\t\tcounted++;\n+\t\t\t\tbreak;\n+\t\t\tcase 1:\n+\t\t\t\tweight_set(p, 0);\n+\t\t\t\tbreak;\n+\t\t\tdefault:\n+\t\t\t\tweight_set(p, -1);\n+\t\t\t\tbreak;\n+\t\t\t}\n+\t\t}\n+\t}\n+\n+\t/*\n+\t * If you have only one parent in the resulting set\n+\t * then you can reach one commit more than that parent\n+\t * can reach.  So we do not have to run the expensive\n+\t * count_distance() for single strand of pearls.\n+\t *\n+\t * However, if you have more than one parents, you cannot\n+\t * just add their distance and one for yourself, since\n+\t * they usually reach the same ancestor and you would\n+\t * end up counting them twice that way.\n+\t *\n+\t * So we will first count distance of merges the usual\n+\t * way, and then fill the blanks using cheaper algorithm.\n+\t */\n+\tfor (p = list; p; p = p->next) {\n+\t\tif (!commit_interesting(p))\n+\t\t\tcontinue;\n+\t\tn = weight(p);\n+\t\tif (0 <= n)\n+\t\t\tcontinue;\n+\t\tdistance = count_distance(p);\n+\t\tclear_distance(p);\n+\t\tweight_set(p, distance);\n+\n+\t\t/* Is it happen to be at exactly half-way? */\n+\t\tdistance *= 2;\n+\t\tif (nr == distance || (nr+1) == distance) {\n+\t\t\tp->next = NULL;\n+\t\t\t*reaches = weight(p);\n+\t\t\tfree(weights);\n+\t\t\treturn p;\n+\t\t}\n+\t\tcounted++;\n+\t}\n+\n+\twhile (counted < nr) {\n+\t\tfor (p = list; p; p = p->next) {\n+\t\t\tstruct commit_list *q;\n+\n+\t\t\tif (!commit_interesting(p) || 0 < weight(p))\n+\t\t\t\tcontinue;\n+\t\t\tfor (q = p->item->parents; q; q = q->next)\n+\t\t\t\tif (commit_interesting(q) && 0 < weight(q))\n+\t\t\t\t\tbreak;\n+\t\t\tif (!q)\n+\t\t\t\tcontinue;\n+\t\t\tweight_set(p, weight(q)+1);\n+\t\t\tcounted++;\n+\n+\t\t\t/* Is it happen to be at exactly half-way? */\n+\t\t\tdistance = weight(p) * 2;\n+\t\t\tif (nr == distance || (nr+1) == distance) {\n+\t\t\t\tp->next = NULL;\n+\t\t\t\t*reaches = weight(p);\n+\t\t\t\tfree(weights);\n+\t\t\t\treturn p;\n+\t\t\t}\n+\t\t}\n+\t}\n+\n+\t/* Then find the best one */\n+\tcounted = 0;\n+\tbest = list;\n+\tfor (p = list; p; p = p->next) {\n+\t\tif (!commit_interesting(p))\n+\t\t\tcontinue;\n+\t\tdistance = weight(p);\n+\t\tif (nr - distance < distance)\n+\t\t\tdistance = nr - distance;\n+\t\tif (distance > counted) {\n+\t\t\tbest = p;\n+\t\t\tcounted = distance;\n+\t\t\t*reaches = weight(p);\n+\t\t}\n+\t}\n+\tif (best)\n+\t\tbest->next = NULL;\n+\tfree(weights);\n+\treturn best;\n+}\n+\n static void read_revisions_from_stdin(struct rev_info *revs)\n {\n \tchar line[1000];\n@@ -298,8 +452,12 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)\n \tif (bisect_list) {\n \t\tint reaches = reaches, all = all;\n \n-\t\trevs.commits = find_bisection(revs.commits,\n-\t\t\t\t\t      &reaches, &all);\n+\t\tif (!revs.prune_fn)\n+\t\t\trevs.commits = find_bisection_2(revs.commits,\n+\t\t\t\t\t\t\t&reaches, &all);\n+\t\telse\n+\t\t\trevs.commits = find_bisection(revs.commits,\n+\t\t\t\t\t\t      &reaches, &all);\n \t\tif (bisect_show_vars) {\n \t\t\tint cnt;\n \t\t\tif (!revs.commits)\n-- \n1.5.1.rc1.610.g3ba7\n"}]}