{"thread":{"id":"19708","subject":"[PATCH v3 0/3] automatically skip away from broken commits","startedAt":"2009-06-06T04:41:32Z","lastAt":"2009-06-15T13:16:05Z","messageCount":37,"participants":["Christian Couder","Junio C Hamano","H. Peter Anvin","Jakub Narebski"],"isPatch":true,"patchVersion":3,"patchTotal":3},"messages":[{"id":"115601","messageId":"20090606043853.4031.78284.chriscool@tuxfamily.org","threadId":"19708","inReplyTo":null,"subject":"[PATCH v3 0/3] automatically skip away from broken commits","fromName":"Christian Couder","fromEmail":"chriscool@tuxfamily.org","sentAt":"2009-06-06T04:41:32Z","receivedAt":"2009-06-06T04:41:32Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"This patch series makes \"git bisect skip\" skip away from an area where\nthe commits cannot be tested.\n\nThis is done automatically. The user has nothing todo. We alternatively\ntry to test commits 20%, 40% and 60% away from the optimal commit that\nhas been skipped.\n\nSome comments have been added and a left over from v1 has been removed\nsince v2, thanks to Junio.\n\n bisect: add parameters to \"filter_skipped\"\n bisect: when skipping, choose a commit away from a skipped commit\n t6030: test skipping away from an already skipped commit\n\n bisect.c | 88 +++++++++++++++++++++++++++++++++++++++++--\n bisect.h | 4 +-\n builtin-rev-list.c | 4 +-\n t/t6030-bisect-porcelain.sh | 12 ++++++\n 4 files changed, 102 insertions(+), 6 deletions(-)\n"},{"id":"115602","messageId":"20090606044136.4031.97844.chriscool@tuxfamily.org","threadId":"19708","inReplyTo":"20090606043853.4031.78284.chriscool@tuxfamily.org","subject":"[PATCH v3 1/3] bisect: add parameters to \"filter_skipped\"","fromName":"Christian Couder","fromEmail":"chriscool@tuxfamily.org","sentAt":"2009-06-06T04:41:33Z","receivedAt":"2009-06-06T04:41:33Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"because we will need to get more information from this function in\nsome later patches.\n\nThe new \"int *count\" parameter gives the number of commits left after\nthe skipped commit have been filtered out.\n\nThe new \"int *skipped_first\" parameter tells us if the first commit\nin the list has been skipped. Note that using this parameter also\nchanges the behavior of the function if the first commit is indeed\nskipped. Because we assume that in this case we will want all the\nfiltered commits, not just the first one, even if \"show_all\" is not\nset.\n\nSo using a not NULL \"skipped_first\" parameter really means that we\nplan to choose to test another commit than the first non skipped\none if the first commit in the list is skipped. That in turn means\nthat, in case the first commit is skipped, we have to return a\nfully filtered list.\n\nSigned-off-by: Christian Couder \n---\n bisect.c | 40 ++++++++++++++++++++++++++++++++++++----\n bisect.h | 4 +++-\n builtin-rev-list.c | 4 +++-\n 3 files changed, 42 insertions(+), 6 deletions(-)\n\ndiff --git a/bisect.c b/bisect.c\nindex 2c14f4d..115cf5f 100644\n--- a/bisect.c\n+++ b/bisect.c\n@@ -521,14 +521,34 @@ static char *join_sha1_array_hex(struct sha1_array *array, char delim)\n \treturn strbuf_detach(&joined_hexs, NULL);\n }\n \n+/*\n+ * In this function, passing a not NULL skipped_first is very special.\n+ * It means that we want to know if the first commit in the list is\n+ * skipped because we will want to test a commit away from it if it is\n+ * indeed skipped.\n+ * So if the first commit is skipped, we cannot take the shortcut to\n+ * just \"return list\" when we find the first non skipped commit, we\n+ * have to return a fully filtered list.\n+ *\n+ * We use (*skipped_first == -1) to mean \"it has been found that the\n+ * first commit is not skipped\". In this case *skipped_first is set back\n+ * to 0 just before the function returns.\n+ */\n struct commit_list *filter_skipped(struct commit_list *list,\n \t\t\t\t struct commit_list **tried,\n-\t\t\t\t int show_all)\n+\t\t\t\t int show_all,\n+\t\t\t\t int *count,\n+\t\t\t\t int *skipped_first)\n {\n \tstruct commit_list *filtered = NULL, **f = &filtered;\n \n \t*tried = NULL;\n \n+\tif (skipped_first)\n+\t\t*skipped_first = 0;\n+\tif (count)\n+\t\t*count = 0;\n+\n \tif (!skipped_revs.sha1_nr)\n \t\treturn list;\n \n@@ -537,19 +557,31 @@ struct commit_list *filter_skipped(struct commit_list *list,\n \t\tlist->next = NULL;\n \t\tif (0 <= lookup_sha1_array(&skipped_revs,\n \t\t\t\t\t list->item->object.sha1)) {\n+\t\t\tif (skipped_first && !*skipped_first)\n+\t\t\t\t*skipped_first = 1;\n \t\t\t/* Move current to tried list */\n \t\t\t*tried = list;\n \t\t\ttried = &list->next;\n \t\t} else {\n-\t\t\tif (!show_all)\n-\t\t\t\treturn list;\n+\t\t\tif (!show_all) {\n+\t\t\t\tif (!skipped_first || !*skipped_first)\n+\t\t\t\t\treturn list;\n+\t\t\t} else if (skipped_first && !*skipped_first) {\n+\t\t\t\t/* This means we know it's not skipped */\n+\t\t\t\t*skipped_first = -1;\n+\t\t\t}\n \t\t\t/* Move current to filtered list */\n \t\t\t*f = list;\n \t\t\tf = &list->next;\n+\t\t\tif (count)\n+\t\t\t\t(*count)++;\n \t\t}\n \t\tlist = next;\n \t}\n \n+\tif (skipped_first && *skipped_first == -1)\n+\t\t*skipped_first = 0;\n+\n \treturn filtered;\n }\n \n@@ -865,7 +897,7 @@ int bisect_next_all(const char *prefix)\n \n \trevs.commits = find_bisection(revs.commits, &reaches, &all,\n \t\t\t\t !!skipped_revs.sha1_nr);\n-\trevs.commits = filter_skipped(revs.commits, &tried, 0);\n+\trevs.commits = filter_skipped(revs.commits, &tried, 0, NULL, NULL);\n \n \tif (!revs.commits) {\n \t\t/*\ndiff --git a/bisect.h b/bisect.h\nindex fb744fd..82f8fc1 100644\n--- a/bisect.h\n+++ b/bisect.h\n@@ -7,7 +7,9 @@ extern struct commit_list *find_bisection(struct commit_list *list,\n \n extern struct commit_list *filter_skipped(struct commit_list *list,\n \t\t\t\t\t struct commit_list **tried,\n-\t\t\t\t\t int show_all);\n+\t\t\t\t\t int show_all,\n+\t\t\t\t\t int *count,\n+\t\t\t\t\t int *skipped_first);\n \n extern void print_commit_list(struct commit_list *list,\n \t\t\t const char *format_cur,\ndiff --git a/builtin-rev-list.c b/builtin-rev-list.c\nindex 73bff84..69753dc 100644\n--- a/builtin-rev-list.c\n+++ b/builtin-rev-list.c\n@@ -262,7 +262,9 @@ int show_bisect_vars(struct rev_list_info *info, int reaches, int all)\n \tif (!revs->commits && !(flags & BISECT_SHOW_TRIED))\n \t\treturn 1;\n \n-\trevs->commits = filter_skipped(revs->commits, &tried, flags & BISECT_SHOW_ALL);\n+\trevs->commits = filter_skipped(revs->commits, &tried,\n+\t\t\t\t flags & BISECT_SHOW_ALL,\n+\t\t\t\t NULL, NULL);\n \n \t/*\n \t * revs->commits can reach \"reaches\" commits among\n-- \n1.6.3.GIT\n"},{"id":"115604","messageId":"20090606044136.4031.48873.chriscool@tuxfamily.org","threadId":"19708","inReplyTo":"20090606043853.4031.78284.chriscool@tuxfamily.org","subject":"[PATCH v3 2/3] bisect: when skipping, choose a commit away from a skipped commit","fromName":"Christian Couder","fromEmail":"chriscool@tuxfamily.org","sentAt":"2009-06-06T04:41:34Z","receivedAt":"2009-06-06T04:41:34Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"To do that a new function \"apply_skip_ratio\" is added and another\nfunction \"managed_skipped\" is created to wrap both \"filter_skipped\"\nand the previous one.\n\nIn \"managed_skipped\" we detect when we should choose a commit away\nfrom a skipped one and then we automatically choose a skip ratio\nto pass to \"apply_skip_ratio\".\n\nThe ratio is choosen so that it alternates between 1/5, 2/5 and\n3/5.\n\nIn \"apply_skip_ratio\", we ignore a given ratio of all the commits\nthat could be tested.\n\nSigned-off-by: Christian Couder \n---\n bisect.c | 50 +++++++++++++++++++++++++++++++++++++++++++++++++-\n 1 files changed, 49 insertions(+), 1 deletions(-)\n\ndiff --git a/bisect.c b/bisect.c\nindex 115cf5f..6fdff05 100644\n--- a/bisect.c\n+++ b/bisect.c\n@@ -585,6 +585,54 @@ 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+{\n+\tint index, i;\n+\tstruct commit_list *cur, *previous;\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+\t\t\tif (hashcmp(cur->item->object.sha1, current_bad_sha1))\n+\t\t\t\treturn cur;\n+\t\t\tif (previous)\n+\t\t\t\treturn previous;\n+\t\t\treturn list;\n+\t\t}\n+\t\tprevious = cur;\n+\t}\n+\n+\treturn list;\n+}\n+\n+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+\tif (!skipped_revs.sha1_nr)\n+\t\treturn list;\n+\n+\tlist = filter_skipped(list, tried, 0, &count, &skipped_first);\n+\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+}\n+\n static void bisect_rev_setup(struct rev_info *revs, const char *prefix,\n \t\t\t const char *bad_format, const char *good_format,\n \t\t\t int read_paths)\n@@ -897,7 +945,7 @@ int bisect_next_all(const char *prefix)\n \n \trevs.commits = find_bisection(revs.commits, &reaches, &all,\n \t\t\t\t !!skipped_revs.sha1_nr);\n-\trevs.commits = filter_skipped(revs.commits, &tried, 0, NULL, NULL);\n+\trevs.commits = managed_skipped(revs.commits, &tried);\n \n \tif (!revs.commits) {\n \t\t/*\n-- \n1.6.3.GIT\n"},{"id":"115603","messageId":"20090606044136.4031.97840.chriscool@tuxfamily.org","threadId":"19708","inReplyTo":"20090606043853.4031.78284.chriscool@tuxfamily.org","subject":"[PATCH v3 3/3] t6030: test skipping away from an already skipped commit","fromName":"Christian Couder","fromEmail":"chriscool@tuxfamily.org","sentAt":"2009-06-06T04:41:35Z","receivedAt":"2009-06-06T04:41:35Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"\nSigned-off-by: Christian Couder \n---\n t/t6030-bisect-porcelain.sh | 12 ++++++++++++\n 1 files changed, 12 insertions(+), 0 deletions(-)\n\ndiff --git a/t/t6030-bisect-porcelain.sh b/t/t6030-bisect-porcelain.sh\nindex 5254b23..4556cdd 100755\n--- a/t/t6030-bisect-porcelain.sh\n+++ b/t/t6030-bisect-porcelain.sh\n@@ -555,6 +555,18 @@ test_expect_success 'restricting bisection on one dir and a file' '\n \tgrep \"$PARA_HASH4 is first bad commit\" my_bisect_log.txt\n '\n \n+test_expect_success 'skipping away from skipped commit' '\n+\tgit bisect start $PARA_HASH7 $HASH1 &&\n+\tpara4=$(git rev-parse --verify HEAD) &&\n+\ttest \"$para4\" = \"$PARA_HASH4\" &&\n+ git bisect skip &&\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+'\n+\n #\n #\n test_done\n-- \n1.6.3.GIT\n"},{"id":"115663","messageId":"7vskidcf9s.fsf@alter.siamese.dyndns.org","threadId":"19708","inReplyTo":"20090606043853.4031.78284.chriscool@tuxfamily.org","subject":"Re: [PATCH v3 0/3] automatically skip away from broken commits","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-06-06T19:51:11Z","receivedAt":"2009-06-06T19:51:11Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Here is a fairly unscientific test to see how these three patches improve\nthings. It involves two test scripts:\n\n - ./+runme is a \"bisect run\" script. It says \"tests OK\" for all the\n commits given, except that it says \"untestable\" for all commits that\n are on the side branch of a merge that we first test. I think this\n reflects what happens in the real world setting very well, in that a\n merge brings in a topic whose breakge is irrelevant to the bug we are\n hunting.\n\n - ./+runall is run in one git tree with two parameters (bad commit and\n good commit); it assumes that\n\n - ./+runme script above is in /var/tmp/+runme;\n\n - a version of git without these three patches is installed with\n prefix=/var/tmp/cc-original;\n\n - a version of git with these three patches is installed with\n prefix=/var/tmp/cc-updated;\n\n and runs the bisection using both versions of git.\n\nThe results are not that great; these three patches do not give clear win\nas we hoped:\n\n $ linux-2.6/master; /var/tmp/+runall v2.6.30-rc8 v2.6.30-rc1\n Total 2681 commits...\n Marked 254 commits as untestable\n Took 14 rounds with cc-updated\n Marked 254 commits as untestable\n Took 13 rounds with cc-original\n $ linux-2.6/master; /var/tmp/+runall v2.6.30-rc8 v2.6.29\n Total 12917 commits...\n Marked 141 commits as untestable\n Took 15 rounds with cc-updated\n Marked 141 commits as untestable\n Took 15 rounds with cc-original\n $ linux-2.6/master; /var/tmp/+runall v2.6.30-rc1 v2.6.29\n Total 10236 commits...\n Marked 7749 commits as untestable\n Took 15 rounds with cc-updated\n Marked 7749 commits as untestable\n Took 14 rounds with cc-original\n\nI think this shows that the \"skip ratio\" heuristics based on the distance\nin the \"goodness scale\" space does not help in avoiding commits that are\nclose in topological space. There may be cases where the version with\npatch gives fewer rounds especially when the history is very linear, but I\nwas mostly interested in the number of commits at least in the thousands,\nwhich I think is what we should optimize things for, not a toy history of\nlinear 100 commits.\n\nHere are the test scripts you can use to reproduce the results.\n\ndiff --git a/+runall b/+runall\nnew file mode 100755\nindex 0000000..291d000\n--- /dev/null\n+++ b/+runall\n@@ -0,0 +1,23 @@\n+#!/bin/sh\n+\n+BAD=${1?BAD}\n+GOOD=${2?GOOD}\n+TOTAL=$(git rev-list $GOOD..$BAD | wc -l)\n+\n+echo Total $TOTAL commits...\n+\n+for git in cc-updated cc-original\n+do\n+\tlogfile=/var/tmp/log-$git-$BAD-$GOOD\n+\t(\n+\t\tPATH=/var/tmp/$git/bin:$PATH\n+\t\texport PATH\n+\t\trm -f .git/UNTESTABLE\n+\t\tgit bisect reset\n+\t\tgit bisect start $BAD $GOOD\n+\t\tgit bisect run /var/tmp/+runme\n+\t\tgit bisect reset\n+\t) >$logfile 2>&1\n+\tgrep \"^Marked \" $logfile\n+\techo Took $(grep -c \"Bisecting:\" $logfile) rounds with $git\n+done\ndiff --git a/+runme b/+runme\nnew file mode 100755\nindex 0000000..7b77338\n--- /dev/null\n+++ b/+runme\n@@ -0,0 +1,23 @@\n+#!/bin/sh\n+\n+# Pretend that the first merged branch were untestable\n+\n+THIS=$(git rev-parse HEAD)\n+\n+if ! test -f .git/UNTESTABLE\n+then\n+\tif MERGED=$(git rev-parse HEAD^2 2>/dev/null)\n+\tthen\n+\t\tgit rev-list HEAD^ ^$MERGED >.git/UNTESTABLE\n+\t\techo Marked $(wc -l <.git/UNTESTABLE) commits as untestable\n+\t\texit 125\n+\telse\n+\t\texit 0\n+\tfi\n+fi\n+\n+if grep \"$THIS\" .git/UNTESTABLE >/dev/null\n+then\n+\texit 125\n+fi\n+exit 0\n\n\n\n\n \n"},{"id":"115688","messageId":"200906070932.36913.chriscool@tuxfamily.org","threadId":"19708","inReplyTo":"7vskidcf9s.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH v3 0/3] automatically skip away from broken commits","fromName":"Christian Couder","fromEmail":"chriscool@tuxfamily.org","sentAt":"2009-06-07T07:32:36Z","receivedAt":"2009-06-07T07:32:36Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"Le Saturday 06 June 2009, Junio C Hamano a écrit :\n> Here is a fairly unscientific test to see how these three patches improve\n> things. It involves two test scripts:\n>\n> - ./+runme is a \"bisect run\" script. It says \"tests OK\" for all the\n> commits given, except that it says \"untestable\" for all commits that\n> are on the side branch of a merge that we first test. I think this\n> reflects what happens in the real world setting very well, in that a\n> merge brings in a topic whose breakge is irrelevant to the bug we are\n> hunting.\n>\n> - ./+runall is run in one git tree with two parameters (bad commit and\n> good commit); it assumes that\n>\n> - ./+runme script above is in /var/tmp/+runme;\n>\n> - a version of git without these three patches is installed with\n> prefix=/var/tmp/cc-original;\n>\n> - a version of git with these three patches is installed with\n> prefix=/var/tmp/cc-updated;\n>\n> and runs the bisection using both versions of git.\n>\n> The results are not that great; these three patches do not give clear win\n> as we hoped:\n>\n> $ linux-2.6/master; /var/tmp/+runall v2.6.30-rc8 v2.6.30-rc1\n> Total 2681 commits...\n> Marked 254 commits as untestable\n> Took 14 rounds with cc-updated\n> Marked 254 commits as untestable\n> Took 13 rounds with cc-original\n> $ linux-2.6/master; /var/tmp/+runall v2.6.30-rc8 v2.6.29\n> Total 12917 commits...\n> Marked 141 commits as untestable\n> Took 15 rounds with cc-updated\n> Marked 141 commits as untestable\n> Took 15 rounds with cc-original\n> $ linux-2.6/master; /var/tmp/+runall v2.6.30-rc1 v2.6.29\n> Total 10236 commits...\n> Marked 7749 commits as untestable\n> Took 15 rounds with cc-updated\n> Marked 7749 commits as untestable\n> Took 14 rounds with cc-original\n>\n> I think this shows that the \"skip ratio\" heuristics based on the distance\n> in the \"goodness scale\" space does not help in avoiding commits that are\n> close in topological space. There may be cases where the version with\n> patch gives fewer rounds especially when the history is very linear, but\n> I was mostly interested in the number of commits at least in the\n> thousands, which I think is what we should optimize things for, not a toy\n> history of linear 100 commits.\n\nI get the same results as yours, and I think that in these tests cases \"git \nbisect\" was not stuck with having only untestable commits with the \nhighest \"goodness\" values. So in these cases the original behavior does \nquite well and that's why the updated behavior can't do better.\n\n> Here are the test scripts you can use to reproduce the results.\n>\n> diff --git a/+runall b/+runall\n> new file mode 100755\n> index 0000000..291d000\n> --- /dev/null\n> +++ b/+runall\n> @@ -0,0 +1,23 @@\n> +#!/bin/sh\n> +\n> +BAD=${1?BAD}\n> +GOOD=${2?GOOD}\n> +TOTAL=$(git rev-list $GOOD..$BAD | wc -l)\n> +\n> +echo Total $TOTAL commits...\n> +\n> +for git in cc-updated cc-original\n> +do\n> +\tlogfile=/var/tmp/log-$git-$BAD-$GOOD\n> +\t(\n> +\t\tPATH=/var/tmp/$git/bin:$PATH\n> +\t\texport PATH\n> +\t\trm -f .git/UNTESTABLE\n> +\t\tgit bisect reset\n> +\t\tgit bisect start $BAD $GOOD\n> +\t\tgit bisect run /var/tmp/+runme\n> +\t\tgit bisect reset\n> +\t) >$logfile 2>&1\n> +\tgrep \"^Marked \" $logfile\n> +\techo Took $(grep -c \"Bisecting:\" $logfile) rounds with $git\n> +done\n> diff --git a/+runme b/+runme\n> new file mode 100755\n> index 0000000..7b77338\n> --- /dev/null\n> +++ b/+runme\n> @@ -0,0 +1,23 @@\n> +#!/bin/sh\n> +\n> +# Pretend that the first merged branch were untestable\n> +\n> +THIS=$(git rev-parse HEAD)\n> +\n> +if ! test -f .git/UNTESTABLE\n> +then\n> +\tif MERGED=$(git rev-parse HEAD^2 2>/dev/null)\n> +\tthen\n> +\t\tgit rev-list HEAD^ ^$MERGED >.git/UNTESTABLE\n> +\t\techo Marked $(wc -l <.git/UNTESTABLE) commits as untestable\n> +\t\texit 125\n> +\telse\n> +\t\texit 0\n> +\tfi\n> +fi\n> +\n> +if grep \"$THIS\" .git/UNTESTABLE >/dev/null\n> +then\n> +\texit 125\n> +fi\n> +exit 0\n\nThanks.\n\nI renamed your +runme to +runme-good and created a +runme-bad script with \nthe following changes:\n\n$ diff -u +runme-good +runme-bad\n--- +runme-good 2009-06-07 03:53:08.000000000 +0200\n+++ +runme-bad 2009-06-07 08:11:33.000000000 +0200\n@@ -12,7 +12,7 @@\n echo Marked $(wc -l <.git/UNTESTABLE) commits as untestable\n exit 125\n else\n- exit 0\n+ exit 1\n fi\n fi\n\n@@ -20,4 +20,4 @@\n then\n exit 125\n fi\n-exit 0\n+exit 1\n\nSo that the +runme-bad says \"tests KO\" (instead of \"tests OK\" for \n+runme-good) for all the commits given, except that it says \"untestable\" \nfor all commits that are on the side branch of a merge that we first test.\n\nThen I created the \"+runme -> +runme-bad\" symlink and tried your examples:\n\n$ /var/tmp/+runall v2.6.30-rc8 v2.6.30-rc1\nTotal 2681 commits...\nMarked 254 commits as untestable\nTook 11 rounds with cc-updated\nMarked 254 commits as untestable\nTook 12 rounds with cc-original\n\n$ /var/tmp/+runall v2.6.30-rc8 v2.6.29\nTotal 12917 commits...\nMarked 141 commits as untestable\nTook 15 rounds with cc-updated\nMarked 141 commits as untestable\nTook 15 rounds with cc-original\n\n$ /var/tmp/+runall v2.6.30-rc1 v2.6.29\nTotal 10236 commits...\nMarked 1777 commits as untestable\nTook 9 rounds with cc-updated\nMarked 1777 commits as untestable\nTook 492 rounds with cc-original\n\nThe last one is very interesting. It seems that the original implementation \ngot stuck while the updated one did a great job...\n\nBest regards,\nChristian.\n"},{"id":"115767","messageId":"4A2CAA56.1030707@zytor.com","threadId":"19708","inReplyTo":"200906070932.36913.chriscool@tuxfamily.org","subject":"Re: [PATCH v3 0/3] automatically skip away from broken commits","fromName":"H. Peter Anvin","fromEmail":"hpa@zytor.com","sentAt":"2009-06-08T06:06:14Z","receivedAt":"2009-06-08T06:06:14Z","isPatch":true,"sender":{"key":"hpa@zytor.com","avatar":null},"body":"Christian Couder wrote:\n>>\n>> I think this shows that the \"skip ratio\" heuristics based on the distance\n>> in the \"goodness scale\" space does not help in avoiding commits that are\n>> close in topological space. There may be cases where the version with\n>> patch gives fewer rounds especially when the history is very linear, but\n>> I was mostly interested in the number of commits at least in the\n>> thousands, which I think is what we should optimize things for, not a toy\n>> history of linear 100 commits.\n> \n> I get the same results as yours, and I think that in these tests cases \"git \n> bisect\" was not stuck with having only untestable commits with the \n> highest \"goodness\" values. So in these cases the original behavior does \n> quite well and that's why the updated behavior can't do better.\n> \n\nIt's not entirely clear to me that this is any better than simply\nrandomly picking a commit from the list of plausible commits -- in other\nwords, eliminate the commits we can totally rule out, and then just pick\na random commit among the list of plausible commits. This is not\n*quite* as crazy as it sounds; it has the advantage of being an\nextremely simple algorithm which shouldn't have any pathological behaviours.\n\nThe average information gain for a randomly picked commit is 1/(2 ln 2)\n=~ 0.7213 bits, or an increase in the total bisect time by 39% over a\npure binary search.\n\n\t-hpa\n\n-- \nH. Peter Anvin, Intel Open Source Technology Center\nI work for Intel. I don't speak on their behalf.\n"},{"id":"115775","messageId":"7vws7n6vcf.fsf@alter.siamese.dyndns.org","threadId":"19708","inReplyTo":"4A2CAA56.1030707@zytor.com","subject":"Re: [PATCH v3 0/3] automatically skip away from broken commits","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-06-08T07:25:04Z","receivedAt":"2009-06-08T07:25:04Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"H. Peter Anvin\" writes:\n\n> It's not entirely clear to me that this is any better than simply\n> randomly picking a commit from the list of plausible commits -- in other\n> words, eliminate the commits we can totally rule out, and then just pick\n> a random commit among the list of plausible commits. This is not\n> *quite* as crazy as it sounds; it has the advantage of being an\n> extremely simple algorithm which shouldn't have any pathological behaviours.\n\nThat is essentially what Christian's patch does. It does not try to go\naway from untestable commits in topological space. Instead, when we find\nthat the commit with the best \"goodness\" value is known to be untestable,\nwe step away from that commit by some alternating distance _in the\ngoodness value space_ (which does not have much to do with how commit\nancestry topology is laid out). Viewed in the topology space, it is quite\nsimilar to picking a different commit randomly, except for a very special\ncase where the remaining history is completely linear, in which case the\ngoodness value space and ancestry topology have a direct correlation.\n\nThat special case, and the deterministic hence repeatable nature of the\nalgorithm, are the two main advantages over picking a completely random\ncommit among the list of plausible commits.\n"},{"id":"115831","messageId":"4A2D337C.70203@zytor.com","threadId":"19708","inReplyTo":"7vws7n6vcf.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH v3 0/3] automatically skip away from broken commits","fromName":"H. Peter Anvin","fromEmail":"hpa@zytor.com","sentAt":"2009-06-08T15:51:24Z","receivedAt":"2009-06-08T15:51:24Z","isPatch":true,"sender":{"key":"hpa@zytor.com","avatar":null},"body":"Junio C Hamano wrote:\n> \"H. Peter Anvin\" writes:\n> \n>> It's not entirely clear to me that this is any better than simply\n>> randomly picking a commit from the list of plausible commits -- in other\n>> words, eliminate the commits we can totally rule out, and then just pick\n>> a random commit among the list of plausible commits. This is not\n>> *quite* as crazy as it sounds; it has the advantage of being an\n>> extremely simple algorithm which shouldn't have any pathological behaviours.\n> \n> That is essentially what Christian's patch does. It does not try to go\n> away from untestable commits in topological space. Instead, when we find\n> that the commit with the best \"goodness\" value is known to be untestable,\n> we step away from that commit by some alternating distance _in the\n> goodness value space_ (which does not have much to do with how commit\n> ancestry topology is laid out). Viewed in the topology space, it is quite\n> similar to picking a different commit randomly, except for a very special\n> case where the remaining history is completely linear, in which case the\n> goodness value space and ancestry topology have a direct correlation.\n> \n> That special case, and the deterministic hence repeatable nature of the\n> algorithm, are the two main advantages over picking a completely random\n> commit among the list of plausible commits.\n\nWell, the cyclic \"stepping distance\" is pretty much a really lame PRNG\nin this case. In the linear case I think the distances are rather\narbitrary (and suboptimal), and I'm not sure it wouldn't simply be\nbetter to actually use a PRNG (which can be unseeded and therefore\nrepeateable, or perhaps even better seeded with some combination of the\nhash values involved.)\n\nThe advantage of that -- and I have to admit I don't know if it will\never matter in practice -- is that using an actual PRNG:\n\na) is less likely to get into pathological capture behaviors.\nb) doesn't make people think later that there is something magic to the\n arbitrary chosen numbers.\n\n\t-hpa\n\n-- \nH. Peter Anvin, Intel Open Source Technology Center\nI work for Intel. I don't speak on their behalf.\n"},{"id":"115841","messageId":"7vzlcixwue.fsf@alter.siamese.dyndns.org","threadId":"19708","inReplyTo":"4A2D337C.70203@zytor.com","subject":"Re: [PATCH v3 0/3] automatically skip away from broken commits","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-06-08T21:02:49Z","receivedAt":"2009-06-08T21:02:49Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"H. Peter Anvin\" writes:\n\n> The advantage of that -- and I have to admit I don't know if it will\n> ever matter in practice -- is that using an actual PRNG:\n>\n> a) is less likely to get into pathological capture behaviors.\n> b) doesn't make people think later that there is something magic to the\n> arbitrary chosen numbers.\n\nMy gut feeling agrees with you that both are likely to be true; these are\ngood points.\n\nChristian, what do you think?\n"},{"id":"115842","messageId":"4A2D7E3A.9060701@zytor.com","threadId":"19708","inReplyTo":"7vzlcixwue.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH v3 0/3] automatically skip away from broken commits","fromName":"H. Peter Anvin","fromEmail":"hpa@zytor.com","sentAt":"2009-06-08T21:10:18Z","receivedAt":"2009-06-08T21:10:18Z","isPatch":true,"sender":{"key":"hpa@zytor.com","avatar":null},"body":"Junio C Hamano wrote:\n> \"H. Peter Anvin\" writes:\n> \n>> The advantage of that -- and I have to admit I don't know if it will\n>> ever matter in practice -- is that using an actual PRNG:\n>>\n>> a) is less likely to get into pathological capture behaviors.\n>> b) doesn't make people think later that there is something magic to the\n>> arbitrary chosen numbers.\n> \n> My gut feeling agrees with you that both are likely to be true; these are\n> good points.\n> \n> Christian, what do you think?\n\nNote: I do believe we should keep the obvious optimization of \"if there\nare no skip points in the plausible range, use the best point.\" We\ndon't want a 39% increase in bisect time when not using skip.\n\n\t-hpa\n"},{"id":"115869","messageId":"c07716ae0906082124n4a5bfe88md80ba8076c928b76@mail.gmail.com","threadId":"19708","inReplyTo":"7vzlcixwue.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH v3 0/3] automatically skip away from broken commits","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2009-06-09T04:24:04Z","receivedAt":"2009-06-09T04:24:04Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"On Mon, Jun 8, 2009 at 11:02 PM, Junio C Hamano wrote:\n> \"H. Peter Anvin\" writes:\n>\n>> The advantage of that -- and I have to admit I don't know if it will\n>> ever matter in practice -- is that using an actual PRNG:\n>>\n>> a) is less likely to get into pathological capture behaviors.\n>> b) doesn't make people think later that there is something magic to the\n>>    arbitrary chosen numbers.\n>\n> My gut feeling agrees with you that both are likely to be true; these are\n> good points.\n>\n> Christian, what do you think?\n\nHere are some reasons why I think my algorithm might be better:\n\n- using HPA's formula I get on average 0.86 bits of information at\neach step when alternating (against 0.72 when using a PRNG)\n- I think that if the branches in the graph merge often between each\nother, then on a big scale it's like when you are on the linear case\n- I don't think we should try too hard to avoid pathological capture\nbehaviors, because I think we can't avoid them anyway in some cases,\nlike if the first bad commit is near many untestable commits\n\nIn the end I think that when you have too many long and completely\nuntestable branches for example, the right solution would be to have\nsomething that lets you cut them off your graph and bisect on a much\ncleaner graph, that's why I started working on \"git replace\" in the\nfirst place.\n\nI think we should not penalize people who have a quite clean graph\nbecause some other people have a much dirtier one.\n\nSo I would be ok to implement a config option or a switch to \"git\nbisect start\" to let people use a PRNG instead of my algorithm but I\nthink something like my algorithm should be the default.\n\nBest regards,\nChristian.\n"},{"id":"115895","messageId":"m3prdd4t6s.fsf@localhost.localdomain","threadId":"19708","inReplyTo":"c07716ae0906082124n4a5bfe88md80ba8076c928b76@mail.gmail.com","subject":"Re: [PATCH v3 0/3] automatically skip away from broken commits","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2009-06-09T10:02:02Z","receivedAt":"2009-06-09T10:02:02Z","isPatch":true,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Christian Couder writes:\n> On Mon, Jun 8, 2009 at 11:02 PM, Junio C Hamano wrote:\n>> \"H. Peter Anvin\" writes:\n>>\n>>> The advantage of that -- and I have to admit I don't know if it will\n>>> ever matter in practice -- is that using an actual PRNG:\n>>>\n>>> a) is less likely to get into pathological capture behaviors.\n>>> b) doesn't make people think later that there is something magic to the\n>>>    arbitrary chosen numbers.\n>>\n>> My gut feeling agrees with you that both are likely to be true; these are\n>> good points.\n>>\n>> Christian, what do you think?\n> \n> Here are some reasons why I think my algorithm might be better:\n> \n> - using HPA's formula I get on average 0.86 bits of information at\n> each step when alternating (against 0.72 when using a PRNG)\n> - I think that if the branches in the graph merge often between each\n> other, then on a big scale it's like when you are on the linear case\n> - I don't think we should try too hard to avoid pathological capture\n> behaviors, because I think we can't avoid them anyway in some cases,\n> like if the first bad commit is near many untestable commits\n\n\nBy the way, I have asked question about best algorithm for \"bisect skip\"\non StackOverflow[1], but didn't get (yet) any good responses...\n\n[1]: http://stackoverflow.com/questions/959324/\n\n-- \nJakub Narebski\nPoland\nShadeHawk on #git\n"},{"id":"115903","messageId":"c07716ae0906090526i714bb6c9g4e3d8cf61021af77@mail.gmail.com","threadId":"19708","inReplyTo":"c07716ae0906082124n4a5bfe88md80ba8076c928b76@mail.gmail.com","subject":"Re: [PATCH v3 0/3] automatically skip away from broken commits","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2009-06-09T12:26:15Z","receivedAt":"2009-06-09T12:26:15Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"On Tue, Jun 9, 2009 at 6:24 AM, Christian\nCouder wrote:\n>\n> So I would be ok to implement a config option or a switch to \"git\n> bisect start\" to let people use a PRNG instead of my algorithm but I\n> think something like my algorithm should be the default.\n\nAnother reason to have 2 algorithms is that when you use \"git bisect\nrun\" you might want to use the PRNG one because:\n\n- you don't care much if the bisection use some more steps (as long as\nit does not get stuck)\n- you can't do much if it get stuck\n\nOn the other hand, when you bisect manually:\n\n- you probably won't like it if you are asked to test some commits\nthat won't give a lot of information\n- if it get stuck, you can manually use \"git bisect visualize\" and/or\n\"git bisect skip \" and/or some other manual commands to do\nsomething about it\n\nRegards,\nChristian.\n"},{"id":"115928","messageId":"4A2E7BA7.8000901@zytor.com","threadId":"19708","inReplyTo":"m3prdd4t6s.fsf@localhost.localdomain","subject":"Re: [PATCH v3 0/3] automatically skip away from broken commits","fromName":"H. Peter Anvin","fromEmail":"hpa@zytor.com","sentAt":"2009-06-09T15:11:35Z","receivedAt":"2009-06-09T15:11:35Z","isPatch":true,"sender":{"key":"hpa@zytor.com","avatar":null},"body":"Jakub Narebski wrote:\n> \n> By the way, I have asked question about best algorithm for \"bisect skip\"\n> on StackOverflow[1], but didn't get (yet) any good responses...\n> \n> [1]: http://stackoverflow.com/questions/959324/\n> \n\nI don't think there is a \"best\" algorithm, but I concur with the poster\nthat said broken commits tend to cluster.\n\n\t-hpa\n\n-- \nH. Peter Anvin, Intel Open Source Technology Center\nI work for Intel. I don't speak on their behalf.\n"},{"id":"115927","messageId":"4A2E7EEC.2050807@zytor.com","threadId":"19708","inReplyTo":"c07716ae0906090526i714bb6c9g4e3d8cf61021af77@mail.gmail.com","subject":"Re: [PATCH v3 0/3] automatically skip away from broken commits","fromName":"H. Peter Anvin","fromEmail":"hpa@zytor.com","sentAt":"2009-06-09T15:25:32Z","receivedAt":"2009-06-09T15:25:32Z","isPatch":true,"sender":{"key":"hpa@zytor.com","avatar":null},"body":"Christian Couder wrote:\n> On Tue, Jun 9, 2009 at 6:24 AM, Christian\n> Couder wrote:\n>> So I would be ok to implement a config option or a switch to \"git\n>> bisect start\" to let people use a PRNG instead of my algorithm but I\n>> think something like my algorithm should be the default.\n> \n> Another reason to have 2 algorithms is that when you use \"git bisect\n> run\" you might want to use the PRNG one because:\n> \n> - you don't care much if the bisection use some more steps (as long as\n> it does not get stuck)\n> - you can't do much if it get stuck\n> \n> On the other hand, when you bisect manually:\n> \n> - you probably won't like it if you are asked to test some commits\n> that won't give a lot of information\n> - if it get stuck, you can manually use \"git bisect visualize\" and/or\n> \"git bisect skip \" and/or some other manual commands to do\n> something about it\n> \n\nSort-of-kind-of. I doubt most users will be able to recover from a\nstuck situation, and unless we have extremely high cost of testing\n(which is true for some applications) then expecting the user to\noptimizing manually is really bad user design.\n\nMy main objection to the \"skip in goodness space\" is exactly the same as\nJunio's... it doesn't really buy you what it claims to sell.\n\n\t-hpa\n\n-- \nH. Peter Anvin, Intel Open Source Technology Center\nI work for Intel. I don't speak on their behalf.\n"},{"id":"115933","messageId":"7vljo1mf09.fsf@alter.siamese.dyndns.org","threadId":"19708","inReplyTo":"4A2E7EEC.2050807@zytor.com","subject":"Re: [PATCH v3 0/3] automatically skip away from broken commits","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-06-09T18:35:50Z","receivedAt":"2009-06-09T18:35:50Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"H. Peter Anvin\" writes:\n\n> My main objection to the \"skip in goodness space\" is exactly the same as\n> Junio's... it doesn't really buy you what it claims to sell.\n\nIt is no worse than the original \"pick the next best in goodness space\";\nneither try to avoid the ones close to untestable ones.\n\nSo as long as it does not claim \"we intelligently try to skip away from\nuntestable ones\", I am actually Ok with Christian's patch. It might do\nworse than the random walk in pathological cases, but I suspect not by a\nbig margin.\n"},{"id":"115936","messageId":"4A2EAD1D.7010201@zytor.com","threadId":"19708","inReplyTo":"7vljo1mf09.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH v3 0/3] automatically skip away from broken commits","fromName":"H. Peter Anvin","fromEmail":"hpa@zytor.com","sentAt":"2009-06-09T18:42:37Z","receivedAt":"2009-06-09T18:42:37Z","isPatch":true,"sender":{"key":"hpa@zytor.com","avatar":null},"body":"Junio C Hamano wrote:\n> \"H. Peter Anvin\" writes:\n> \n>> My main objection to the \"skip in goodness space\" is exactly the same as\n>> Junio's... it doesn't really buy you what it claims to sell.\n> \n> It is no worse than the original \"pick the next best in goodness space\";\n> neither try to avoid the ones close to untestable ones.\n> \n\nWell, it's certainly better than \"next best in goodness space\", which is\nprovably pessimal in many common cases.\n\n> So as long as it does not claim \"we intelligently try to skip away from\n> untestable ones\", I am actually Ok with Christian's patch. It might do\n> worse than the random walk in pathological cases, but I suspect not by a\n> big margin.\n\n\t-hpa\n"},{"id":"115941","messageId":"c07716ae0906091228s708058d4vea986239a6b458de@mail.gmail.com","threadId":"19708","inReplyTo":"4A2E7EEC.2050807@zytor.com","subject":"Re: [PATCH v3 0/3] automatically skip away from broken commits","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2009-06-09T19:28:25Z","receivedAt":"2009-06-09T19:28:25Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"On Tue, Jun 9, 2009 at 5:25 PM, H. Peter Anvin wrote:\n> Christian Couder wrote:\n>> On Tue, Jun 9, 2009 at 6:24 AM, Christian\n>> Couder wrote:\n>>> So I would be ok to implement a config option or a switch to \"git\n>>> bisect start\" to let people use a PRNG instead of my algorithm but I\n>>> think something like my algorithm should be the default.\n>>\n>> Another reason to have 2 algorithms is that when you use \"git bisect\n>> run\" you might want to use the PRNG one because:\n>>\n>> - you don't care much if the bisection use some more steps (as long as\n>> it does not get stuck)\n>> - you can't do much if it get stuck\n>>\n>> On the other hand, when you bisect manually:\n>>\n>> - you probably won't like it if you are asked to test some commits\n>> that won't give a lot of information\n>> - if it get stuck, you can manually use \"git bisect visualize\" and/or\n>> \"git bisect skip \" and/or some other manual commands to do\n>> something about it\n>>\n>\n> Sort-of-kind-of. I doubt most users will be able to recover from a\n> stuck situation, and unless we have extremely high cost of testing\n> (which is true for some applications) then expecting the user to\n> optimizing manually is really bad user design.\n\nMy opinion is that we should not penalize all the people working on\n\"quite clean\" projects and also people working on \"not clean\" projects\nwho are able to recover, on the pretence that there are other people\non these \"not clean\" projects who are not.\n\nI think it's the projects maintainers' responsibility to keep their\nprojects graphs quite clean (and they have the right to ask git\ndevelopers for the tools to do that). If they don't do so, then their\nusers will suffer anyway. So it's not a big deal to ask them to teach\ntheir users to add a \"--prng\" option to \"git bisect start\" for example\nor something like that to try to work around the \"not cleanliness\" of\ntheir graphs.\n\nBest regards,\nChristian.\n"},{"id":"115944","messageId":"4A2EB8E9.5040207@zytor.com","threadId":"19708","inReplyTo":"c07716ae0906091228s708058d4vea986239a6b458de@mail.gmail.com","subject":"Re: [PATCH v3 0/3] automatically skip away from broken commits","fromName":"H. Peter Anvin","fromEmail":"hpa@zytor.com","sentAt":"2009-06-09T19:32:57Z","receivedAt":"2009-06-09T19:32:57Z","isPatch":true,"sender":{"key":"hpa@zytor.com","avatar":null},"body":"Christian Couder wrote:\n>>>\n>> Sort-of-kind-of. I doubt most users will be able to recover from a\n>> stuck situation, and unless we have extremely high cost of testing\n>> (which is true for some applications) then expecting the user to\n>> optimizing manually is really bad user design.\n> \n> My opinion is that we should not penalize all the people working on\n> \"quite clean\" projects and also people working on \"not clean\" projects\n> who are able to recover, on the pretence that there are other people\n> on these \"not clean\" projects who are not.\n> \n> I think it's the projects maintainers' responsibility to keep their\n> projects graphs quite clean (and they have the right to ask git\n> developers for the tools to do that).\n\nNo, it's not. This is saying \"it's the user's responsibility to make up\nfor shortcomings in the tools\", which is completely bass-ackwards.\n\n> If they don't do so, then their\n> users will suffer anyway. So it's not a big deal to ask them to teach\n> their users to add a \"--prng\" option to \"git bisect start\" for example\n> or something like that to try to work around the \"not cleanliness\" of\n> their graphs.\n\nLet's see... we can penalize the default user by 19% (the amount of\ndifference) if and only if they have skip points (at which point your\n\"project manager's responsibility\" has already failed) or we can risk an\ninexperienced user getting stuck?\n\n\t-hpa\n"},{"id":"115951","messageId":"7viqj5kutl.fsf@alter.siamese.dyndns.org","threadId":"19708","inReplyTo":"c07716ae0906091228s708058d4vea986239a6b458de@mail.gmail.com","subject":"Re: [PATCH v3 0/3] automatically skip away from broken commits","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-06-09T20:37:10Z","receivedAt":"2009-06-09T20:37:10Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Christian Couder writes:\n\n> My opinion is that we should not penalize all the people working on\n> \"quite clean\" projects and also people working on \"not clean\" projects\n> who are able to recover, on the pretence that there are other people\n> on these \"not clean\" projects who are not.\n>\n> I think it's the projects maintainers' responsibility to keep their\n> projects graphs quite clean (and they have the right to ask git\n> developers for the tools to do that).\n\nYou seem to be saying that a completely linear history is the only one\nthat is clean.\n\nIn an earlier message, I illustrated a case where two people independently\nworked on unrelated topic and ended up merging their branches together, to\nillustrate why your \"not adjacent in goodness space\" algorithm does not\ngive \"away from untestable ones in topology space\".\n\nWith your definition, that history is _not_ clean. I do not think any\nproject wnats that kind of cleanness in their history. You just made the\nword \"clean\" to describe the history meaningless.\n\nMy take on the issue you mentioned above is that we should not penalize\nthe codepath's simplicity too much, only to cater to pathological\nbehaviour exhibited on an uninteresting special case of competely linear\nhistory.\n\nYour algorithm is Ok as an initial cut, in that it is an improvement over\nthe \"next in goodness space, not even bother to avoid the pathological\ncase\" algorithm. But I do not think it is much better than HPA's \"try the\nbest one if it is not skipped, otherwise pick one randomly\", and if we\nwanted to do better and to claim that we pick ones that are _away_ from\nuntestable ones, we do need to take topology into account. That is all I\nam saying.\n"},{"id":"115961","messageId":"200906092355.51244.jnareb@gmail.com","threadId":"19708","inReplyTo":"4A2E7BA7.8000901@zytor.com","subject":"Re: [PATCH v3 0/3] automatically skip away from broken commits","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2009-06-09T21:55:49Z","receivedAt":"2009-06-09T21:55:49Z","isPatch":true,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"On Tue, 9 June 2009, H. Peter Anvin wrote:\n> Jakub Narebski wrote:\n> > \n> > By the way, I have asked question about best algorithm for \"bisect skip\"\n> > on StackOverflow[1], but didn't get (yet) any good responses...\n> > \n> > [1]: http://stackoverflow.com/questions/959324/\n> > \n> \n> I don't think there is a \"best\" algorithm, but I concur with the poster\n> that said broken commits tend to cluster.\n\nWell, I guess that there might be, at least if we had some reasonable\nassumption on probability distribution of bad commits.\n\n\nNote: the idea sketched below is just handwaving currently...\n\nLet us assume that we are currently at some untestable commit. Let us\nalso assume that we have some halfway reasonable model of probability\nthat a given commit is untestable, given it distance from known\nuntestable commit. \"git rev-list --bisect-all\" (or its inner equivalent)\nwould give us list of commits in the searched range, sorted in \ndescending order by distance from edges (endpoints) of range:\n\n commit \"goodness\" \n --------------------\n c21d2e5* (dist=60)\n 94d6d14 (dist=59)\n ccb06f4 (dist=59)\n d1a1610 (dist=58)\n d4bf4b4 (dist=58)\n 16c5646 (dist=57)\n\nLet us assume that \"c21d2e5\" is untestable, and that we can easily \ncalculate distance from it, substituting 0/0 (undef) if a commit\nis not in straight line from \"c21d2e5\".\n\n commit \"goodness\" d\n -------------------------\n c21d2e5* (dist=60) 0\n 94d6d14 (dist=59) 1\n ccb06f4 (dist=59) --\n d1a1610 (dist=58) --\n d4bf4b4 (dist=58) 2\n 16c5646 (dist=57) 3\n\nLet us also assume that we have some model of probability that a commit\nis untestable. In the example below numbers are ad hoc, and unrealistic.\n\n commit \"goodness\" d P(untestable)\n ----------------------------------------\n c21d2e5* (dist=60) 0 100%\n 94d6d14 (dist=59) 1 75%\n ccb06f4 (dist=59) -- 0%\n d1a1610 (dist=58) -- 0%\n d4bf4b4 (dist=58) 2 33%\n 16c5646 (dist=57) 3 25%\n\nWe can now calculate average number of bits of information would bring\n(IIRC it was HPA and Christian that was writing about 'average information\ngain' and 'bits of information at each step'; I don't quote know how it\nis to be calculated)\n\n commit \"goodness\" d P(untestable) avg. gain\n ----------------------------------------\n c21d2e5* (dist=60) 0 100% 0.0001\n 94d6d14 (dist=59) 1 75% 0.45\n ccb06f4 (dist=59) -- 0% 0.98\n d1a1610 (dist=58) -- 0% 0.95\n d4bf4b4 (dist=58) 2 33% 0.65\n 16c5646 (dist=57) 3 25% 0.66\n\nHere 'avg. gain' numbers are totally handwaving... but the idea is to\npick up as next test point the commit with mist average information\ngain.\n\nWhat do you think of this algorithm (after of course it is made into\nproper algorithm :-))?\n-- \nJakub Narebski\nPoland\n"},{"id":"115966","messageId":"4A2EE825.1020200@zytor.com","threadId":"19708","inReplyTo":"200906092355.51244.jnareb@gmail.com","subject":"Re: [PATCH v3 0/3] automatically skip away from broken commits","fromName":"H. Peter Anvin","fromEmail":"hpa@zytor.com","sentAt":"2009-06-09T22:54:29Z","receivedAt":"2009-06-09T22:54:29Z","isPatch":true,"sender":{"key":"hpa@zytor.com","avatar":null},"body":"Jakub Narebski wrote:\n> \n> Let us also assume that we have some model of probability that a commit\n> is untestable. In the example below numbers are ad hoc, and unrealistic.\n> \n\nWhat I mostly meant was that there simply is no such model that will be\nideal (since we simply don't have that information, almost by\ndefinition), so therefore the overall algorithm can't be ideal, either.\n\nHowever, Christian and you do make a very good point that instead of a\nlinear-probability random selection, it probably makes sense to bias the\nrandomness in favor of the commits that are more likely to provide\nhigher information gain. This is effectively what Christian's patch\ndoes in a somewhat clumsy way.\n\nOne of the nice things about combining a random algorithm with bias is\nthat the bias doesn't have to be perfect, it just have to be good\nenough. For example, we can take dramatic shortcuts like not taking\ntopology into accounts.\n\nA logical bias function would indeed be an estimate of the information\ngain. One way we can calculate the effective information gain is by\ntake the list in \"goodness order\" that we already have, and treat it as\nif it had originally been a linear history -- this will usually not be\nthe case, but we're probabilistically getting away with murder here.\n\nThe sorting in \"goodness order\" of a linear history means sorting\nmiddlemost first, so the modified information density function with x\nbeing the position in the list (x = 0 for best, x = 1 for worst) looks like:\n\n- 1/(2 ln 2) * [ (1-x) ln (1-x) + (1+x) ln (1+x) - 2 ln 2 ]\n\nI'd have to brush up some more of my calculus in order to remember how\nto come up with a transformation function which would take a random\nnumber and give us this exact probability distribution, but again, I\ndon't think it's hugely important; I suspect any function which gives us\na probability distribution that's even in the right neighborhood would\ngive us excellent results.\n\n\t-hpa\n"},{"id":"115996","messageId":"c07716ae0906100114n61ca5553k2f54918dd32afbb4@mail.gmail.com","threadId":"19708","inReplyTo":"4A2EB8E9.5040207@zytor.com","subject":"Re: [PATCH v3 0/3] automatically skip away from broken commits","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2009-06-10T08:14:22Z","receivedAt":"2009-06-10T08:14:22Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"On Tue, Jun 9, 2009 at 9:32 PM, H. Peter Anvin wrote:\n> Christian Couder wrote:\n>>>>\n>>> Sort-of-kind-of.  I doubt most users will be able to recover from a\n>>> stuck situation, and unless we have extremely high cost of testing\n>>> (which is true for some applications) then expecting the user to\n>>> optimizing manually is really bad user design.\n>>\n>> My opinion is that we should not penalize all the people working on\n>> \"quite clean\" projects and also people working on \"not clean\" projects\n>> who are able to recover, on the pretence that there are other people\n>> on these \"not clean\" projects who are not.\n\nBy the way, if for example you have a project with 10% chance to land\nin a \"stuck area\" of the graph, then with my algorithm the chance to\nget stuck when you hit an untestable commit is 0.1^3 that is 0.1%. So\nin this kind of projects the chance that the first bad commit is near\na lot untestable commits is much higher than that.\n\nIn fact I think that it's probably very hard to find a kind of project\nwhere the chance to get stuck when using my algorithm is not dwarfed\nby the chance of the first bad commit to be near or among many\nuntestable commits.\n\n>> I think it's the projects maintainers' responsibility to keep their\n>> projects graphs quite clean (and they have the right to ask git\n>> developers for the tools to do that).\n>\n> No, it's not.  This is saying \"it's the user's responsibility to make up\n> for shortcomings in the tools\", which is completely bass-ackwards.\n\nI think that what I said is just the opposite that. If you find\nshortcomings in the tools then you are welcome to ask us to fix them.\n\nAnd if users find shortcomings in the cleanliness of the project\ngraph, they should be welcome to ask the maintainers to provide them\nwith ways to work around them, like for example a file that contains\nmany commits and range of commits that should always be skipped and\nthat can be used like for example:\n\n$ git bisect start\n$ git bisect skip $(cat always_skipped_file)\n$ git bisect good ...\n$ git bisect bad ...\n...\n\nOr the maintainers can in turn ask git developers what's going on with\n\"git replace\" if they would prefer using that instead of such a\nfile...\n\n>> If they don't do so, then their\n>> users will suffer anyway. So it's not a big deal to ask them to teach\n>> their users to add a \"--prng\" option to \"git bisect start\" for example\n>> or something like that to try to work around the \"not cleanliness\" of\n>> their graphs.\n>\n> Let's see... we can penalize the default user by 19% (the amount of\n> difference) if and only if they have skip points (at which point your\n> \"project manager's responsibility\" has already failed) or we can risk an\n> inexperienced user getting stuck?\n\nI am not sure I understand you very well but as I said above I think\nwith a \"reasonably clean\" graph the risk of the inexperienced user\ngetting stuck because of my algorithm is very low compared to the risk\nof getting stuck because the first bad commit happens to be near many\nuntestable ones.\n\nBest regards,\nChristian.\n"},{"id":"116030","messageId":"c07716ae0906101237o5038fc4dle9f11b6f2216652a@mail.gmail.com","threadId":"19708","inReplyTo":"7viqj5kutl.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH v3 0/3] automatically skip away from broken commits","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2009-06-10T19:37:57Z","receivedAt":"2009-06-10T19:37:57Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"On Tue, Jun 9, 2009 at 10:37 PM, Junio C Hamano wrote:\n> Christian Couder writes:\n>\n>> My opinion is that we should not penalize all the people working on\n>> \"quite clean\" projects and also people working on \"not clean\" projects\n>> who are able to recover, on the pretence that there are other people\n>> on these \"not clean\" projects who are not.\n>>\n>> I think it's the projects maintainers' responsibility to keep their\n>> projects graphs quite clean (and they have the right to ask git\n>> developers for the tools to do that).\n>\n> You seem to be saying that a completely linear history is the only one\n> that is clean.\n\nI was thinking about projects that use test suites to make sure new\ncommits don't break a lot of things.\nBut I should have said \"to keep their projects graph quite clean or to\nprovide specific information about how to work around potential\nproblems when bisecting.\"\n\n> In an earlier message, I illustrated a case where two people independently\n> worked on unrelated topic and ended up merging their branches together, to\n> illustrate why your \"not adjacent in goodness space\" algorithm does not\n> give \"away from untestable ones in topology space\".\n>\n> With your definition, that history is _not_ clean. I do not think any\n> project wnats that kind of cleanness in their history. You just made the\n> word \"clean\" to describe the history meaningless.\n\nWhen I wrote \"clean\", I just mean with not too many untestable commits.\n\n> My take on the issue you mentioned above is that we should not penalize\n> the codepath's simplicity too much, only to cater to pathological\n> behaviour exhibited on an uninteresting special case of competely linear\n> history.\n\nI tried to make a short yet efficient implementation, not to favor a\nspecial case.\n\n> Your algorithm is Ok as an initial cut, in that it is an improvement over\n> the \"next in goodness space, not even bother to avoid the pathological\n> case\" algorithm. But I do not think it is much better than HPA's \"try the\n> best one if it is not skipped, otherwise pick one randomly\", and if we\n> wanted to do better and to claim that we pick ones that are _away_ from\n> untestable ones, we do need to take topology into account. That is all I\n> am saying.\n\nOk. I started working on optionaly using a PRNG but I am not sure that\nyou will want to add another one.\n\nBest regards,\nChristian.\n"},{"id":"116033","messageId":"7vtz2nlrfs.fsf@alter.siamese.dyndns.org","threadId":"19708","inReplyTo":"c07716ae0906101237o5038fc4dle9f11b6f2216652a@mail.gmail.com","subject":"Re: [PATCH v3 0/3] automatically skip away from broken commits","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-06-10T21:17:11Z","receivedAt":"2009-06-10T21:17:11Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Christian Couder writes:\n\n> On Tue, Jun 9, 2009 at 10:37 PM, Junio C Hamano wrote:\n>> Christian Couder writes:\n>>\n>>> My opinion is that we should not penalize all the people working on\n>>> \"quite clean\" projects and also people working on \"not clean\" projects\n>>> who are able to recover, on the pretence that there are other people\n>>> on these \"not clean\" projects who are not.\n> ...\n> When I wrote \"clean\", I just mean with not too many untestable commits.\n\nOk, then the \"opinion\" in the above paragraph was simply stating the\nobvious: we should have a good \"bisect skip\". I obviously agree with that\n;-).\n\nIn other words, you were not arguing against my observation that your\nalgorithm would not be much better than randomly picking the next commit\nwhen the best one is untestable, unless the history is linear. I guess\nthat was what I was confused with. I thought you were saying that we\nshould give preferential treatment to people with linear history. \n\n> Ok. I started working on optionaly using a PRNG but I am not sure that\n> you will want to add another one.\n\nIt may still make sense to replace, not add to, that \"fixed alternating\ndistance in goodness space\" with a randomized one, for the reasons HPA\nstated, especially for avoiding to give a false impression that the magic\nconstants are picked for some reason.\n"},{"id":"116047","messageId":"4A303723.4060805@zytor.com","threadId":"19708","inReplyTo":"7vtz2nlrfs.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH v3 0/3] automatically skip away from broken commits","fromName":"H. Peter Anvin","fromEmail":"hpa@zytor.com","sentAt":"2009-06-10T22:43:47Z","receivedAt":"2009-06-10T22:43:47Z","isPatch":true,"sender":{"key":"hpa@zytor.com","avatar":null},"body":"Junio C Hamano wrote:\n> Christian Couder writes:\n> \n>> On Tue, Jun 9, 2009 at 10:37 PM, Junio C Hamano wrote:\n>>> Christian Couder writes:\n>>>\n>>>> My opinion is that we should not penalize all the people working on\n>>>> \"quite clean\" projects and also people working on \"not clean\" projects\n>>>> who are able to recover, on the pretence that there are other people\n>>>> on these \"not clean\" projects who are not.\n>> ...\n>> When I wrote \"clean\", I just mean with not too many untestable commits.\n> \n> Ok, then the \"opinion\" in the above paragraph was simply stating the\n> obvious: we should have a good \"bisect skip\". I obviously agree with that\n> ;-).\n> \n> In other words, you were not arguing against my observation that your\n> algorithm would not be much better than randomly picking the next commit\n> when the best one is untestable, unless the history is linear. I guess\n> that was what I was confused with. I thought you were saying that we\n> should give preferential treatment to people with linear history. \n> \n>> Ok. I started working on optionaly using a PRNG but I am not sure that\n>> you will want to add another one.\n> \n> It may still make sense to replace, not add to, that \"fixed alternating\n> distance in goodness space\" with a randomized one, for the reasons HPA\n> stated, especially for avoiding to give a false impression that the magic\n> constants are picked for some reason.\n> \n\nThat being said, Christian's observation that a biased selection would\nbe better than a linear random pick is a good one.\n\n\t-hpa\n"},{"id":"116057","messageId":"200906110602.54861.chriscool@tuxfamily.org","threadId":"19708","inReplyTo":"7vtz2nlrfs.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH v3 0/3] automatically skip away from broken commits","fromName":"Christian Couder","fromEmail":"chriscool@tuxfamily.org","sentAt":"2009-06-11T04:02:54Z","receivedAt":"2009-06-11T04:02:54Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"Le Wednesday 10 June 2009, Junio C Hamano a écrit :\n> Christian Couder writes:\n> > On Tue, Jun 9, 2009 at 10:37 PM, Junio C Hamano \nwrote:\n> >> Christian Couder writes:\n> >>> My opinion is that we should not penalize all the people working on\n> >>> \"quite clean\" projects and also people working on \"not clean\"\n> >>> projects who are able to recover, on the pretence that there are\n> >>> other people on these \"not clean\" projects who are not.\n> >\n> > ...\n> > When I wrote \"clean\", I just mean with not too many untestable commits.\n>\n> Ok, then the \"opinion\" in the above paragraph was simply stating the\n> obvious: we should have a good \"bisect skip\". I obviously agree with\n> that ;-).\n>\n> In other words, you were not arguing against my observation that your\n> algorithm would not be much better than randomly picking the next commit\n> when the best one is untestable, unless the history is linear.\n\nI think my algorithm is better enough than a random one to be worth using by \ndefault. Like HPA says it's in practice like a random one with a bias.\n\nThat's because the \"goodness\" value is something that has a relationship \nwith the graph topology. The \"goodness\" value is some kind of distance from \neither the good or the bad commits. The farther from the good and bad \ncommits the higher is the \"goodness\" value. And my algorithm tries to avoid \ncommits with low \"goodness\" value because they should be those near the \ngood and bad commits and we know that those near the good and bad commits \nwont give a lot of information.\n\n> I guess \n> that was what I was confused with. I thought you were saying that we\n> should give preferential treatment to people with linear history.\n>\n> > Ok. I started working on optionaly using a PRNG but I am not sure that\n> > you will want to add another one.\n>\n> It may still make sense to replace, not add to, that \"fixed alternating\n> distance in goodness space\" with a randomized one, for the reasons HPA\n> stated, especially for avoiding to give a false impression that the magic\n> constants are picked for some reason.\n\nBut there _is_ a reason.\n\nBest regards,\nChristian.\n"},{"id":"116058","messageId":"4A308B5D.2010704@zytor.com","threadId":"19708","inReplyTo":"200906110602.54861.chriscool@tuxfamily.org","subject":"Re: [PATCH v3 0/3] automatically skip away from broken commits","fromName":"H. Peter Anvin","fromEmail":"hpa@zytor.com","sentAt":"2009-06-11T04:43:09Z","receivedAt":"2009-06-11T04:43:09Z","isPatch":true,"sender":{"key":"hpa@zytor.com","avatar":null},"body":"Christian Couder wrote:\n> \n> I think my algorithm is better enough than a random one to be worth using by \n> default. Like HPA says it's in practice like a random one with a bias.\n> \n\nBut it's a really poor such. Using an actual biased PRNG will give the\nbest of both variants (a bias to prefer better commits, and still all\ncommits reachable.)\n\nAfter playing around with Wolfram Alpha for way too long, it seems that\na suitable bias function would be to take the fourth root of the PRNG\nvalue, i.e. raise it to the power 0.25.\n\n\t-hpa\n\n-- \nH. Peter Anvin, Intel Open Source Technology Center\nI work for Intel. I don't speak on their behalf.\n"},{"id":"116059","messageId":"4A309083.9090907@zytor.com","threadId":"19708","inReplyTo":"4A308B5D.2010704@zytor.com","subject":"Re: [PATCH v3 0/3] automatically skip away from broken commits","fromName":"H. Peter Anvin","fromEmail":"hpa@zytor.com","sentAt":"2009-06-11T05:05:07Z","receivedAt":"2009-06-11T05:05:07Z","isPatch":true,"sender":{"key":"hpa@zytor.com","avatar":null},"body":"H. Peter Anvin wrote:\n> \n> After playing around with Wolfram Alpha for way too long, it seems that\n> a suitable bias function would be to take the fourth root of the PRNG\n> value, i.e. raise it to the power 0.25.\n> \n\nUrk, I managed to get myself completely confused -- I did the series\napproximation on the wrong side of inverting the function. The correct\npower is actually 1.5 (over the range 0 to 1), a value > 1 is necessary\nto bias the PRNG toward the beginning (x = 0) of the list.\n\n\t-hpa\n\n-- \nH. Peter Anvin, Intel Open Source Technology Center\nI work for Intel. I don't speak on their behalf.\n"},{"id":"116142","messageId":"c07716ae0906120456j1a14af52n47c3a3542201aaf@mail.gmail.com","threadId":"19708","inReplyTo":"4A309083.9090907@zytor.com","subject":"Re: [PATCH v3 0/3] automatically skip away from broken commits","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2009-06-12T11:56:29Z","receivedAt":"2009-06-12T11:56:29Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"On Thu, Jun 11, 2009 at 7:05 AM, H. Peter Anvin wrote:\n>\n> Urk, I managed to get myself completely confused -- I did the series\n> approximation on the wrong side of inverting the function.  The correct\n> power is actually 1.5 (over the range 0 to 1), a value > 1 is necessary\n> to bias the PRNG toward the beginning (x = 0) of the list.\n\nI started working on this, but I wonder if it's better to add a\n#include and link with -lm than to provide a custom sqrt\nimplementation. Too bad the best power is not 2.\n\nTo implement the PRNG, I guess that using something based on the\nfunction given by \"man 3 rand\" should be ok:\n\nint get_prn(int count) {\n count = count * 1103515245 + 12345;\n return((unsigned)(count/65536) % 32768);\n}\n\nwhere the \"count\" we pass is the count of elements in the list rather\nthan the static seed.\n\nBest regards,\nChristian.\n"},{"id":"116215","messageId":"200906130950.47832.chriscool@tuxfamily.org","threadId":"19708","inReplyTo":"200906070932.36913.chriscool@tuxfamily.org","subject":"Re: [PATCH v3 0/3] automatically skip away from broken commits","fromName":"Christian Couder","fromEmail":"chriscool@tuxfamily.org","sentAt":"2009-06-13T07:50:47Z","receivedAt":"2009-06-13T07:50:47Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"Le Sunday 07 June 2009, Christian Couder a écrit :\n> Le Saturday 06 June 2009, Junio C Hamano a écrit :\n> > Here is a fairly unscientific test to see how these three patches\n> > improve things. It involves two test scripts:\n> >\n> > - ./+runme is a \"bisect run\" script. It says \"tests OK\" for all the\n> > commits given, except that it says \"untestable\" for all commits that\n> > are on the side branch of a merge that we first test. I think this\n> > reflects what happens in the real world setting very well, in that a\n> > merge brings in a topic whose breakge is irrelevant to the bug we\n> > are hunting.\n> >\n> > - ./+runall is run in one git tree with two parameters (bad commit and\n> > good commit); it assumes that\n> >\n> > - ./+runme script above is in /var/tmp/+runme;\n> >\n> > - a version of git without these three patches is installed with\n> > prefix=/var/tmp/cc-original;\n> >\n> > - a version of git with these three patches is installed with\n> > prefix=/var/tmp/cc-updated;\n> >\n> > and runs the bisection using both versions of git.\n> >\n> > The results are not that great; these three patches do not give clear\n> > win as we hoped:\n> >\n> > $ linux-2.6/master; /var/tmp/+runall v2.6.30-rc8 v2.6.30-rc1\n> > Total 2681 commits...\n> > Marked 254 commits as untestable\n> > Took 14 rounds with cc-updated\n> > Marked 254 commits as untestable\n> > Took 13 rounds with cc-original\n> > $ linux-2.6/master; /var/tmp/+runall v2.6.30-rc8 v2.6.29\n> > Total 12917 commits...\n> > Marked 141 commits as untestable\n> > Took 15 rounds with cc-updated\n> > Marked 141 commits as untestable\n> > Took 15 rounds with cc-original\n> > $ linux-2.6/master; /var/tmp/+runall v2.6.30-rc1 v2.6.29\n> > Total 10236 commits...\n> > Marked 7749 commits as untestable\n> > Took 15 rounds with cc-updated\n> > Marked 7749 commits as untestable\n> > Took 14 rounds with cc-original\n> >\n> > I think this shows that the \"skip ratio\" heuristics based on the\n> > distance in the \"goodness scale\" space does not help in avoiding\n> > commits that are close in topological space. There may be cases where\n> > the version with patch gives fewer rounds especially when the history\n> > is very linear, but I was mostly interested in the number of commits at\n> > least in the thousands, which I think is what we should optimize things\n> > for, not a toy history of linear 100 commits.\n>\n> I get the same results as yours, and I think that in these tests cases\n> \"git bisect\" was not stuck with having only untestable commits with the\n> highest \"goodness\" values. So in these cases the original behavior does\n> quite well and that's why the updated behavior can't do better.\n>\n> > Here are the test scripts you can use to reproduce the results.\n> >\n> > diff --git a/+runall b/+runall\n> > new file mode 100755\n> > index 0000000..291d000\n> > --- /dev/null\n> > +++ b/+runall\n> > @@ -0,0 +1,23 @@\n> > +#!/bin/sh\n> > +\n> > +BAD=${1?BAD}\n> > +GOOD=${2?GOOD}\n> > +TOTAL=$(git rev-list $GOOD..$BAD | wc -l)\n> > +\n> > +echo Total $TOTAL commits...\n> > +\n> > +for git in cc-updated cc-original\n> > +do\n> > +\tlogfile=/var/tmp/log-$git-$BAD-$GOOD\n> > +\t(\n> > +\t\tPATH=/var/tmp/$git/bin:$PATH\n> > +\t\texport PATH\n> > +\t\trm -f .git/UNTESTABLE\n> > +\t\tgit bisect reset\n> > +\t\tgit bisect start $BAD $GOOD\n> > +\t\tgit bisect run /var/tmp/+runme\n> > +\t\tgit bisect reset\n> > +\t) >$logfile 2>&1\n> > +\tgrep \"^Marked \" $logfile\n> > +\techo Took $(grep -c \"Bisecting:\" $logfile) rounds with $git\n> > +done\n> > diff --git a/+runme b/+runme\n> > new file mode 100755\n> > index 0000000..7b77338\n> > --- /dev/null\n> > +++ b/+runme\n> > @@ -0,0 +1,23 @@\n> > +#!/bin/sh\n> > +\n> > +# Pretend that the first merged branch were untestable\n> > +\n> > +THIS=$(git rev-parse HEAD)\n> > +\n> > +if ! test -f .git/UNTESTABLE\n> > +then\n> > +\tif MERGED=$(git rev-parse HEAD^2 2>/dev/null)\n> > +\tthen\n> > +\t\tgit rev-list HEAD^ ^$MERGED >.git/UNTESTABLE\n> > +\t\techo Marked $(wc -l <.git/UNTESTABLE) commits as untestable\n> > +\t\texit 125\n> > +\telse\n> > +\t\texit 0\n> > +\tfi\n> > +fi\n> > +\n> > +if grep \"$THIS\" .git/UNTESTABLE >/dev/null\n> > +then\n> > +\texit 125\n> > +fi\n> > +exit 0\n>\n> Thanks.\n>\n> I renamed your +runme to +runme-good and created a +runme-bad script with\n> the following changes:\n>\n> $ diff -u +runme-good +runme-bad\n> --- +runme-good 2009-06-07 03:53:08.000000000 +0200\n> +++ +runme-bad 2009-06-07 08:11:33.000000000 +0200\n> @@ -12,7 +12,7 @@\n> echo Marked $(wc -l <.git/UNTESTABLE) commits as\n> untestable exit 125\n> else\n> - exit 0\n> + exit 1\n> fi\n> fi\n>\n> @@ -20,4 +20,4 @@\n> then\n> exit 125\n> fi\n> -exit 0\n> +exit 1\n>\n> So that the +runme-bad says \"tests KO\" (instead of \"tests OK\" for\n> +runme-good) for all the commits given, except that it says \"untestable\"\n> for all commits that are on the side branch of a merge that we first\n> test.\n>\n> Then I created the \"+runme -> +runme-bad\" symlink and tried your\n> examples:\n>\n> $ /var/tmp/+runall v2.6.30-rc8 v2.6.30-rc1\n> Total 2681 commits...\n> Marked 254 commits as untestable\n> Took 11 rounds with cc-updated\n> Marked 254 commits as untestable\n> Took 12 rounds with cc-original\n>\n> $ /var/tmp/+runall v2.6.30-rc8 v2.6.29\n> Total 12917 commits...\n> Marked 141 commits as untestable\n> Took 15 rounds with cc-updated\n> Marked 141 commits as untestable\n> Took 15 rounds with cc-original\n>\n> $ /var/tmp/+runall v2.6.30-rc1 v2.6.29\n> Total 10236 commits...\n> Marked 1777 commits as untestable\n> Took 9 rounds with cc-updated\n> Marked 1777 commits as untestable\n> Took 492 rounds with cc-original\n>\n> The last one is very interesting. It seems that the original\n> implementation got stuck while the updated one did a great job...\n\nWith the patch I just posted that use a PRNG with a bias, I get the \nfollowing results.\n\nWith the \"+runme -> +runme-good\" symlink:\n\n$ /var/tmp/+runall v2.6.30-rc8 v2.6.30-rc1\nTotal 2681 commits...\nMarked 254 commits as untestable\nTook 13 rounds with cc-updated\nMarked 254 commits as untestable\nTook 13 rounds with cc-original\n\n$ /var/tmp/+runall v2.6.30-rc8 v2.6.29\nTotal 12917 commits...\nMarked 141 commits as untestable\nTook 15 rounds with cc-updated\nMarked 141 commits as untestable\nTook 15 rounds with cc-original\n\n$ /var/tmp/+runall v2.6.30-rc1 v2.6.29\nTotal 10236 commits...\nMarked 7749 commits as untestable\nTook 14 rounds with cc-updated\nMarked 7749 commits as untestable\nTook 14 rounds with cc-original\n\nAnd with the \"+runme -> +runme-bad\" symlink:\n\n$ /var/tmp/+runall v2.6.30-rc8 v2.6.30-rc1\nTotal 2681 commits...\nMarked 254 commits as untestable\nTook 13 rounds with cc-updated\nMarked 254 commits as untestable\nTook 12 rounds with cc-original\n\n$ /var/tmp/+runall v2.6.30-rc8 v2.6.29\nTotal 12917 commits...\nMarked 141 commits as untestable\nTook 15 rounds with cc-updated\nMarked 141 commits as untestable\nTook 15 rounds with cc-original\n\n$ /var/tmp/+runall v2.6.30-rc1 v2.6.29\nTotal 10236 commits...\nMarked 1777 commits as untestable\nTook 12 rounds with cc-updated\nMarked 1777 commits as untestable\nTook 492 rounds with cc-original\n\nSo there the results are quite similar to my alternating between 3 ratios \nalgorithm.\n\nBest regards,\nChristian.\n"},{"id":"116246","messageId":"4A33F7E4.4020201@zytor.com","threadId":"19708","inReplyTo":"c07716ae0906120456j1a14af52n47c3a3542201aaf@mail.gmail.com","subject":"Re: [PATCH v3 0/3] automatically skip away from broken commits","fromName":"H. Peter Anvin","fromEmail":"hpa@zytor.com","sentAt":"2009-06-13T19:03:00Z","receivedAt":"2009-06-13T19:03:00Z","isPatch":true,"sender":{"key":"hpa@zytor.com","avatar":null},"body":"Christian Couder wrote:\n> On Thu, Jun 11, 2009 at 7:05 AM, H. Peter Anvin wrote:\n>> Urk, I managed to get myself completely confused -- I did the series\n>> approximation on the wrong side of inverting the function. The correct\n>> power is actually 1.5 (over the range 0 to 1), a value > 1 is necessary\n>> to bias the PRNG toward the beginning (x = 0) of the list.\n> \n> I started working on this, but I wonder if it's better to add a\n> #include and link with -lm than to provide a custom sqrt\n> implementation. Too bad the best power is not 2.\n> \n\nThat's what I would do. It's not like sqrt() is a strange, unportable\nfunction.\n\n> To implement the PRNG, I guess that using something based on the\n> function given by \"man 3 rand\" should be ok:\n> \n> int get_prn(int count) {\n> count = count * 1103515245 + 12345;\n> return((unsigned)(count/65536) % 32768);\n> }\n> \n> where the \"count\" we pass is the count of elements in the list rather\n> than the static seed.\n\nYes, or perhaps better we could use some combination of the SHA-1s\ninvolved as seeds... they are rather nice for this as they are wide and\nmuch better PRNGs than most classical algorithms.\n\nThe main problem with the above algorithm is that it only produces 16\nbits of output, which when biased can turn into a fairly significant\ngranularity.\n\n\t-hpa\n\n-- \nH. Peter Anvin, Intel Open Source Technology Center\nI work for Intel. I don't speak on their behalf.\n"},{"id":"116249","messageId":"m3r5xo2ajc.fsf@localhost.localdomain","threadId":"19708","inReplyTo":"4A33F7E4.4020201@zytor.com","subject":"Re: [PATCH v3 0/3] automatically skip away from broken commits","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2009-06-13T19:35:47Z","receivedAt":"2009-06-13T19:35:47Z","isPatch":true,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"\"H. Peter Anvin\" writes:\n> Christian Couder wrote:\n>> On Thu, Jun 11, 2009 at 7:05 AM, H. Peter Anvin wrote:\n\n>> To implement the PRNG, I guess that using something based on the\n>> function given by \"man 3 rand\" should be ok:\n>> \n>> int get_prn(int count) {\n>> count = count * 1103515245 + 12345;\n>> return((unsigned)(count/65536) % 32768);\n>> }\n>> \n>> where the \"count\" we pass is the count of elements in the list rather\n>> than the static seed.\n> \n> Yes, or perhaps better we could use some combination of the SHA-1s\n> involved as seeds... they are rather nice for this as they are wide and\n> much better PRNGs than most classical algorithms.\n> \n> The main problem with the above algorithm is that it only produces 16\n> bits of output, which when biased can turn into a fairly significant\n> granularity.\n\nWhy not borrow one of algorithms, e.g. taus[1] from GSL (GNU\nScientific Library)?\n\nIf I understand \"Random Number Generator Performance\" chapter in GSL\nManual it is of comparable performance of the above BSD `rand`\ngenerator, and is of simulation quality.\n\n[1] maximally equidistributed combined Tausworthe generator by L'Ecuyer\n\n-- \nJakub Narebski\nPoland\nShadeHawk on #git\n"},{"id":"116250","messageId":"4A3404B2.5080700@zytor.com","threadId":"19708","inReplyTo":"m3r5xo2ajc.fsf@localhost.localdomain","subject":"Re: [PATCH v3 0/3] automatically skip away from broken commits","fromName":"H. Peter Anvin","fromEmail":"hpa@zytor.com","sentAt":"2009-06-13T19:57:38Z","receivedAt":"2009-06-13T19:57:38Z","isPatch":true,"sender":{"key":"hpa@zytor.com","avatar":null},"body":"Jakub Narebski wrote:\n> \n> Why not borrow one of algorithms, e.g. taus[1] from GSL (GNU\n> Scientific Library)?\n> \n> If I understand \"Random Number Generator Performance\" chapter in GSL\n> Manual it is of comparable performance of the above BSD `rand`\n> generator, and is of simulation quality.\n> \n> [1] maximally equidistributed combined Tausworthe generator by L'Ecuyer\n> \n\nInteresting paper (the algorithm is on page 8):\n\nhttp://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=F2BD39FF5C24221B424E12D9ED4E68B7?doi=10.1.1.43.4155&rep=rep1&type=pdf\n\nThe reason I suggested SHA-1 is because we already have SHA-1 code\ninvolved (in fact, we even have a bunch of precalculated SHA-1s\navailable to us) and performance matters not one iota in this application.\n\n\t-hpa\n\n-- \nH. Peter Anvin, Intel Open Source Technology Center\nI work for Intel. I don't speak on their behalf.\n"},{"id":"116321","messageId":"c07716ae0906150059m7f9706x6f9022afde15d3b0@mail.gmail.com","threadId":"19708","inReplyTo":"4A33F7E4.4020201@zytor.com","subject":"Re: [PATCH v3 0/3] automatically skip away from broken commits","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2009-06-15T07:59:57Z","receivedAt":"2009-06-15T07:59:57Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"On Sat, Jun 13, 2009 at 9:03 PM, H. Peter Anvin wrote:\n> Christian Couder wrote:\n>> On Thu, Jun 11, 2009 at 7:05 AM, H. Peter Anvin wrote:\n>>> Urk, I managed to get myself completely confused -- I did the series\n>>> approximation on the wrong side of inverting the function.  The correct\n>>> power is actually 1.5 (over the range 0 to 1), a value > 1 is necessary\n>>> to bias the PRNG toward the beginning (x = 0) of the list.\n>>\n>> I started working on this, but I wonder if it's better to add a\n>> #include and link with -lm than to provide a custom sqrt\n>> implementation. Too bad the best power is not 2.\n>>\n>\n> That's what I would do.  It's not like sqrt() is a strange, unportable\n> function.\n\nYes, but I feared that there could be rounding related differences\nbetween platforms.\n\nBy the way, could you explain why power 1.5 is better than 2? It would\nbe much simpler if we could avoid square rooting anything in the first\nplace.\n\n>> To implement the PRNG, I guess that using something based on the\n>> function given by \"man 3 rand\" should be ok:\n>>\n>> int get_prn(int count) {\n>>     count = count * 1103515245 + 12345;\n>>     return((unsigned)(count/65536) % 32768);\n>> }\n>>\n>> where the \"count\" we pass is the count of elements in the list rather\n>> than the static seed.\n>\n> Yes, or perhaps better we could use some combination of the SHA-1s\n> involved as seeds... they are rather nice for this as they are wide and\n> much better PRNGs than most classical algorithms.\n>\n> The main problem with the above algorithm is that it only produces 16\n> bits of output, which when biased can turn into a fairly significant\n> granularity.\n\nI don't think this is a real problem for this application. In fact I\nthink it's already quite overkill and there are better things to do,\nlike looking for a commit on a different branch among the first ones\nin the list, if we want to improve the current behavior.\n\nSo unless there is a real flaw, I am going to work on something else.\n\nBest regards,\nChristian.\n"},{"id":"116336","messageId":"4A364995.2010703@zytor.com","threadId":"19708","inReplyTo":"c07716ae0906150059m7f9706x6f9022afde15d3b0@mail.gmail.com","subject":"Re: [PATCH v3 0/3] automatically skip away from broken commits","fromName":"H. Peter Anvin","fromEmail":"hpa@zytor.com","sentAt":"2009-06-15T13:16:05Z","receivedAt":"2009-06-15T13:16:05Z","isPatch":true,"sender":{"key":"hpa@zytor.com","avatar":null},"body":"Christian Couder wrote:\n> Yes, but I feared that there could be rounding related differences\n> between platforms.\n\nDoesn't matter for this application. Really. Anything you're going to\ndo yourself will be much worse. Realistically, you might have a\ndifference in the 53rd bit.\n\n> By the way, could you explain why power 1.5 is better than 2? It would\n> be much simpler if we could avoid square rooting anything in the first\n> place.\n\nIt is the power function that most closely creates a distribution which\nmatches the value curve (rounded to a small fraction.)\n\n> I don't think this is a real problem for this application. In fact I\n> think it's already quite overkill and there are better things to do,\n> like looking for a commit on a different branch among the first ones\n> in the list, if we want to improve the current behavior.\n> \n> So unless there is a real flaw, I am going to work on something else.\n\nMakes sense.\n\n\t-hpa\n\n-- \nH. Peter Anvin, Intel Open Source Technology Center\nI work for Intel. I don't speak on their behalf.\n"}]}