{"thread":{"id":"17888","subject":"[PATCH v2] rev-list: estimate number of bisection step left","startedAt":"2009-02-19T07:03:52Z","lastAt":"2009-02-19T07:03:52Z","messageCount":1,"participants":["Christian Couder"],"isPatch":true,"patchVersion":2,"patchTotal":null},"messages":[{"id":"105398","messageId":"20090219080352.9b07fca0.chriscool@tuxfamily.org","threadId":"17888","inReplyTo":null,"subject":"[PATCH v2] rev-list: estimate number of bisection step left","fromName":"Christian Couder","fromEmail":"chriscool@tuxfamily.org","sentAt":"2009-02-19T07:03:52Z","receivedAt":"2009-02-19T07:03:52Z","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\ndiff --git a/builtin-rev-list.c b/builtin-rev-list.c\nindex 436afa4..9dfffac 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.rc0.98.g055ea\n"}]}