{"thread":{"id":"19797","subject":"[PATCH] bisect: use a PRNG with a bias when skipping away from untestable commits","startedAt":"2009-06-13T05:21:06Z","lastAt":"2009-06-13T05:21:06Z","messageCount":1,"participants":["Christian Couder"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"116212","messageId":"20090613052107.4190.71471.chriscool@tuxfamily.org","threadId":"19797","inReplyTo":null,"subject":"[PATCH] bisect: use a PRNG with a bias when skipping away from untestable commits","fromName":"Christian Couder","fromEmail":"chriscool@tuxfamily.org","sentAt":"2009-06-13T05:21:06Z","receivedAt":"2009-06-13T05:21:06Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"Using a PRNG (pseudo random number generator) with a bias should be better\nthan alternating between 3 fixed ratios.\n\nIn repositories with many untestable commits it should prevent alternating\nbetween areas where many commits are untestable. The bias should favor\ncommits that can give more information, so that the bisection process\nshould not loose much efficiency.\n\nHPA suggested to use a PRNG and found that the best bias is to raise a\nratio between 0 and 1 given by the PRNG to the power 1.5.\n\nAn integer square root function is implemented to avoid including\n<math.h> and linking with -lm.\n\nA PRNG function is implemented to get the same number sequence on\ndifferent machines as suggested by \"man 3 rand\".\n\nSigned-off-by: Christian Couder <chriscool@tuxfamily.org>\n---\n bisect.c                    |   50 +++++++++++++++++++++++++++++++++---------\n t/t6030-bisect-porcelain.sh |    4 +-\n 2 files changed, 41 insertions(+), 13 deletions(-)\n\ndiff --git a/bisect.c b/bisect.c\nindex 6fdff05..095b55e 100644\n--- a/bisect.c\n+++ b/bisect.c\n@@ -585,16 +585,49 @@ struct commit_list *filter_skipped(struct commit_list *list,\n \treturn filtered;\n }\n \n-static struct commit_list *apply_skip_ratio(struct commit_list *list,\n-\t\t\t\t\t    int count,\n-\t\t\t\t\t    int skip_num, int skip_denom)\n+#define PRN_MODULO 32768\n+\n+/*\n+ * This is a pseudo random number generator based on \"man 3 rand\".\n+ * It is not used properly because the seed is the argument and it\n+ * is increased by one between each call, but that should not matter\n+ * for this application.\n+ */\n+int get_prn(int count) {\n+\tcount = count * 1103515245 + 12345;\n+\treturn ((unsigned)(count/65536) % PRN_MODULO);\n+}\n+\n+/*\n+ * Custom integer square root from\n+ * http://en.wikipedia.org/wiki/Integer_square_root\n+ */\n+static int sqrti(int val)\n+{\n+\tfloat d, x = val;\n+\n+\tif (val == 0)\n+\t\treturn 0;\n+\n+\tdo {\n+\t\tfloat y = (x + (float)val / x) / 2;\n+\t\td = (y > x) ? y - x : x - y;\n+\t\tx = y;\n+\t} while (d >= 0.5);\n+\n+\treturn (int)x;\n+}\n+\n+static struct commit_list *skip_away(struct commit_list *list, int count)\n {\n-\tint index, i;\n \tstruct commit_list *cur, *previous;\n+\tint prn, index, i;\n+\n+\tprn = get_prn(count);\n+\tindex = (count * prn / PRN_MODULO) * sqrti(prn) / sqrti(PRN_MODULO);\n \n \tcur = list;\n \tprevious = NULL;\n-\tindex = count * skip_num / skip_denom;\n \n \tfor (i = 0; cur; cur = cur->next, i++) {\n \t\tif (i == index) {\n@@ -614,7 +647,6 @@ static struct commit_list *managed_skipped(struct commit_list *list,\n \t\t\t\t\t   struct commit_list **tried)\n {\n \tint count, skipped_first;\n-\tint skip_num, skip_denom;\n \n \t*tried = NULL;\n \n@@ -626,11 +658,7 @@ static struct commit_list *managed_skipped(struct commit_list *list,\n \tif (!skipped_first)\n \t\treturn list;\n \n-\t/* Use alternatively 1/5, 2/5 and 3/5 as skip ratio. */\n-\tskip_num = count % 3 + 1;\n-\tskip_denom = 5;\n-\n-\treturn apply_skip_ratio(list, count, skip_num, skip_denom);\n+\treturn skip_away(list, count);\n }\n \n static void bisect_rev_setup(struct rev_info *revs, const char *prefix,\ndiff --git a/t/t6030-bisect-porcelain.sh b/t/t6030-bisect-porcelain.sh\nindex 4556cdd..1315bab 100755\n--- a/t/t6030-bisect-porcelain.sh\n+++ b/t/t6030-bisect-porcelain.sh\n@@ -563,8 +563,8 @@ test_expect_success 'skipping away from skipped commit' '\n \thash7=$(git rev-parse --verify HEAD) &&\n \ttest \"$hash7\" = \"$HASH7\" &&\n         git bisect skip &&\n-\thash3=$(git rev-parse --verify HEAD) &&\n-\ttest \"$hash3\" = \"$HASH3\"\n+\tpara3=$(git rev-parse --verify HEAD) &&\n+\ttest \"$para3\" = \"$PARA_HASH3\"\n '\n \n #\n-- \n1.6.3.GIT\n"}]}