{"thread":{"id":"17933","subject":"[PATCH v2.1 resend] rev-list: estimate number of bisection step left","startedAt":"2009-02-21T08:26:01Z","lastAt":"2009-02-21T17:12:55Z","messageCount":3,"participants":["Christian Couder","Junio C Hamano"],"isPatch":true,"patchVersion":2,"patchTotal":null},"messages":[{"id":"105694","messageId":"20090221092601.45691c3e.chriscool@tuxfamily.org","threadId":"17933","inReplyTo":null,"subject":"[PATCH v2.1 resend] rev-list: estimate number of bisection step left","fromName":"Christian Couder","fromEmail":"chriscool@tuxfamily.org","sentAt":"2009-02-21T08:26:01Z","receivedAt":"2009-02-21T08:26:01Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"This patch teaches \"git rev-list --bisect-vars\" to output an estimate\nof the number of bisection step left _after the current one_ along with\nthe other variables it already outputs.\n\nThis patch also makes \"git-bisect.sh\" display this number of steps left\n_after the current one_, along with the estimate of the number of\nrevisions left to test (after the current one).\n\nHere is a table to help analyse what should be the best estimate for\nthe number of bisect steps left.\n\nN : linear case                    --> probabilities --> best\n-------------------------------------------------------------\n1 : G-B                            --> 0             --> 0\n2 : G-U1-B                         --> 0             --> 0\n3 : G-U1-U2-B                      --> 0(1/3) 1(2/3) --> 1\n4 : G-U1-U2-U3-B                   --> 1             --> 1\n5 : G-U1-U2-U3-U4-B                --> 1(3/5) 2(2/5) --> 1\n6 : G-U1-U2-U3-U4-U5-B             --> 1(2/6) 2(4/6) --> 2\n7 : G-U1-U2-U3-U4-U5-U6-B          --> 1(1/7) 2(6/7) --> 2\n8 : G-U1-U2-U3-U4-U5-U6-U7-B       --> 2             --> 2\n9 : G-U1-U2-U3-U4-U5-U6-U7-U8-B    --> 2(7/9) 3(2/9) --> 2\n10: G-U1-U2-U3-U4-U5-U6-U7-U8-U9-B --> 2(6/10)3(4/10)--> 2\n\nIn the column \"N\", there is the number of revisions that could _now_\nbe the first bad commit we are looking for.\n\nThe \"linear case\" column describes the linear history corresponding to\nthe number in column N. G means good, B means bad, and Ux means\nunknown. Note that the first bad revision we are looking for can be\nany Ux or B.\n\nIn the \"probabilities\" column, there are the different outcomes in\nnumber of steps with the odds of each outcome in parenthesis\ncorresponding to the linear case.\n\nThe \"best\" column gives the most accurate estimate among the different\noutcomes in the \"probabilities\" column.\n\nWe have the following:\n\nbest(2^n) == n - 1\n\nand for any x between 0 included and 2^n excluded, the probability for\nn - 1 steps left looks like:\n\nP(2^n + x) == (2^n - x) / (2^n + x)\n\nand P(2^n + x) < 0.5 means 2^n < 3x\n\nSo the algorithm used in this patch calculates 2^n and x, and then\nchoose between returning n - 1 and n.\n\nSigned-off-by: Christian Couder <chriscool@tuxfamily.org>\n---\n builtin-rev-list.c |   45 +++++++++++++++++++++++++++++++++++++++++++--\n git-bisect.sh      |    2 +-\n 2 files changed, 44 insertions(+), 3 deletions(-)\n\n\tThere should be only a spurious space removed compared to version v2.\n\ndiff --git a/builtin-rev-list.c b/builtin-rev-list.c\nindex 436afa4..40d5fcb 100644\n--- a/builtin-rev-list.c\n+++ b/builtin-rev-list.c\n@@ -574,6 +574,45 @@ static struct commit_list *find_bisection(struct commit_list *list,\n \treturn best;\n }\n \n+static inline int log2i(int n)\n+{\n+\tint log2 = 0;\n+\n+\tfor (; n > 1; n >>= 1)\n+\t\tlog2++;\n+\n+\treturn log2;\n+}\n+\n+static inline int exp2i(int n)\n+{\n+\treturn 1 << n;\n+}\n+\n+/*\n+ * Estimate the number of bisect steps left (after the current step)\n+ *\n+ * For any x between 0 included and 2^n excluded, the probability for\n+ * n - 1 steps left looks like:\n+ *\n+ * P(2^n + x) == (2^n - x) / (2^n + x)\n+ *\n+ * and P(2^n + x) < 0.5 means 2^n < 3x\n+ */\n+static int estimate_bisect_steps(int all)\n+{\n+\tint n, x, e;\n+\n+\tif (all < 3)\n+\t\treturn 0;\n+\n+\tn = log2i(all);\n+\te = exp2i(n);\n+\tx = all - e;\n+\n+\treturn (e < 3 * x) ? n : n - 1;\n+}\n+\n int cmd_rev_list(int argc, const char **argv, const char *prefix)\n {\n \tstruct commit_list *list;\n@@ -688,12 +727,14 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)\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       \"bisect_all=%d\\n\"\n+\t\t\t       \"bisect_steps=%d\\n\",\n \t\t\t       hex,\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\t       all,\n+\t\t\t       estimate_bisect_steps(all));\n \t\t\treturn 0;\n \t\t}\n \t}\ndiff --git a/git-bisect.sh b/git-bisect.sh\nindex 85db4ba..9ea1cdc 100755\n--- a/git-bisect.sh\n+++ b/git-bisect.sh\n@@ -500,7 +500,7 @@ bisect_next() {\n \t# commit is also a \"skip\" commit (see above).\n \texit_if_skipped_commits \"$bisect_rev\"\n \n-\tbisect_checkout \"$bisect_rev\" \"$bisect_nr revisions left to test after this\"\n+\tbisect_checkout \"$bisect_rev\" \"$bisect_nr revisions left to test after this (roughly $bisect_steps steps)\"\n }\n \n bisect_visualize() {\n-- \n1.6.2.rc1.22.g3290.dirty\n"},{"id":"105697","messageId":"7vy6w0qgwr.fsf@gitster.siamese.dyndns.org","threadId":"17933","inReplyTo":"20090221092601.45691c3e.chriscool@tuxfamily.org","subject":"Re: [PATCH v2.1 resend] rev-list: estimate number of bisection step left","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-02-21T09:27:00Z","receivedAt":"2009-02-21T09:27:00Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Christian Couder <chriscool@tuxfamily.org> writes:\n\n> Here is a table to help analyse what should be the best estimate for\n> the number of bisect steps left.\n> ...\n> So the algorithm used in this patch calculates 2^n and x, and then\n> choose between returning n - 1 and n.\n\nTwo dumb questions about the math (because I suck at math).\n\n - Do you mean by \"best estimate\" the best case scenario, or something\n   else (perhaps \"the most accurate\")?\n\n - Is computing based on linear history a good enough approximation?\n\nI am not advocating to make things more precise nor saying your math is\nflawed.  I'd prefer simpler code for things like this --- after all, my\nunderstanding of this whole exercise is to give \"this is more or less the\nnumber you should expect\" ballpack figure and nothing more (correct me if\nthat is not what you are aiming for).\n"},{"id":"105729","messageId":"200902211812.56593.chriscool@tuxfamily.org","threadId":"17933","inReplyTo":"7vy6w0qgwr.fsf@gitster.siamese.dyndns.org","subject":"Re: [PATCH v2.1 resend] rev-list: estimate number of bisection step left","fromName":"Christian Couder","fromEmail":"chriscool@tuxfamily.org","sentAt":"2009-02-21T17:12:55Z","receivedAt":"2009-02-21T17:12:55Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"Le samedi 21 février 2009, Junio C Hamano a écrit :\n> Christian Couder <chriscool@tuxfamily.org> writes:\n> > Here is a table to help analyse what should be the best estimate for\n> > the number of bisect steps left.\n> > ...\n> > So the algorithm used in this patch calculates 2^n and x, and then\n> > choose between returning n - 1 and n.\n>\n> Two dumb questions about the math (because I suck at math).\n>\n>  - Do you mean by \"best estimate\" the best case scenario, or something\n>    else (perhaps \"the most accurate\")?\n\nI mean the number of steps that has the highest frequency of occurrence, if \nwe suppose that:\n\n1) we are in the linear case, and that\n2) the first bad revision has an equal chance of being any of the unknown \n(Ux) and the bad (B) revisions.\n\n>  - Is computing based on linear history a good enough approximation?\n\nI think so. Before I sent patch v1, I tested it on some non linear cases and \nit worked quite well in those cases as well. I think the bisect algorithm \ntries as best as possible to remove half the revisions from the set of the \npossible first bad revisions and this means that all the algorithms based \non log2(all) should be quite good in any case.\n\n> I am not advocating to make things more precise nor saying your math is\n> flawed.  I'd prefer simpler code for things like this --- after all, my\n> understanding of this whole exercise is to give \"this is more or less the\n> number you should expect\" ballpack figure and nothing more (correct me if\n> that is not what you are aiming for).\n\nYes, that's what I am aiming for. And I thought that my first patch was \nquite good at doing that, so when you said that \"at the very low end the \nestimate is a bit too optimistic\", I had another look and found out that \nfor \"all == 3\" indeed the algorithm gave 0 when 1 was better, because 1 \nshould happen on average 2 times out of 3.\n\nSo I came up with the algorithm in v2 which is better because it should \nalways give the best estimate (supposing 1) and 2)). It's also not much \nmore complex compared to v1 or anything based on log2(all), so I don't see \nany reason to use something else.\n\nRegards,\nChristian.\n"}]}