{"thread":{"id":"56938","subject":"[PATCH 04/27] bisect: Fixup bisect-porcelain/32","startedAt":"2021-11-18T16:49:51Z","lastAt":"2021-11-22T13:31:27Z","messageCount":43,"participants":["Jan Kara","Chris Torek","Taylor Blau","Johannes Schindelin","Christian Couder"],"isPatch":true,"patchVersion":1,"patchTotal":27},"messages":[{"id":"441617","messageId":"20211118164940.8818-5-jack@suse.cz","threadId":"56938","inReplyTo":"20211118164940.8818-1-jack@suse.cz","subject":"[PATCH 04/27] bisect: Fixup bisect-porcelain/32","fromName":"Jan Kara","fromEmail":"jack@suse.cz","sentAt":"2021-11-18T16:49:17Z","receivedAt":"2021-11-18T16:49:51Z","isPatch":true,"sender":{"key":"jack@suse.cz","avatar":null},"body":"Test 32 from t6030-bisect-porcelain.sh assumes that bisection algorithm\nsuggests HASH6 after HASH4 when HASH5 is an equivalent choice. Fix the\ntest to work in both cases.\n\nSigned-off-by: Jan Kara \n---\n t/t6030-bisect-porcelain.sh | 8 ++++++--\n 1 file changed, 6 insertions(+), 2 deletions(-)\n\ndiff --git a/t/t6030-bisect-porcelain.sh b/t/t6030-bisect-porcelain.sh\nindex 13f7deea4d81..d693c0002098 100755\n--- a/t/t6030-bisect-porcelain.sh\n+++ b/t/t6030-bisect-porcelain.sh\n@@ -395,9 +395,13 @@ test_expect_success 'bisect does not create a \"bisect\" branch' '\n \ttest \"$rev_hash4\" = \"$HASH4\" &&\n \tgit branch -D bisect &&\n \tgit bisect good &&\n+\trev_hash=$(git rev-parse --verify HEAD) &&\n+\tif [ $rev_hash == \"$HASH5\" ]; then\n+\t\tgit bisect good &&\n+\t\trev_hash=$(git rev-parse --verify HEAD)\n+\tfi &&\n \tgit branch bisect &&\n-\trev_hash6=$(git rev-parse --verify HEAD) &&\n-\ttest \"$rev_hash6\" = \"$HASH6\" &&\n+\ttest \"$rev_hash\" = \"$HASH6\" &&\n \tgit bisect good > my_bisect_log.txt &&\n \tgrep \"$HASH7 is the first bad commit\" my_bisect_log.txt &&\n \tgit bisect reset &&\n-- \n2.26.2\n\n"},{"id":"441618","messageId":"20211118164940.8818-3-jack@suse.cz","threadId":"56938","inReplyTo":"20211118164940.8818-1-jack@suse.cz","subject":"[PATCH 02/27] bisect: Fixup bisect-porcelain/17","fromName":"Jan Kara","fromEmail":"jack@suse.cz","sentAt":"2021-11-18T16:49:15Z","receivedAt":"2021-11-18T16:49:52Z","isPatch":true,"sender":{"key":"jack@suse.cz","avatar":null},"body":"Test 17 from t6030-bisect-porcelain.sh assumes that bisection algorithm\nsuggests first HASH3 where HASH2 and HASH3 are equivalent choices. Make\nsure test correctly handles both choices, add test variant to properly\ntest commit skipping in the second case.\n\nSigned-off-by: Jan Kara \n---\n t/t6030-bisect-porcelain.sh | 18 +++++++++++++++++-\n 1 file changed, 17 insertions(+), 1 deletion(-)\n\ndiff --git a/t/t6030-bisect-porcelain.sh b/t/t6030-bisect-porcelain.sh\nindex 1be85d064e76..f8cfdd3c36d2 100755\n--- a/t/t6030-bisect-porcelain.sh\n+++ b/t/t6030-bisect-porcelain.sh\n@@ -197,11 +197,27 @@ test_expect_success 'bisect skip: successful result' '\n \ttest_when_finished git bisect reset &&\n \tgit bisect reset &&\n \tgit bisect start $HASH4 $HASH1 &&\n-\tgit bisect skip &&\n+\tif [ $(git rev-parse HEAD) == $HASH3 ]; then\n+\t\tgit bisect skip\n+\tfi &&\n \tgit bisect bad > my_bisect_log.txt &&\n \tgrep \"$HASH2 is the first bad commit\" my_bisect_log.txt\n '\n \n+# $HASH1 is good, $HASH4 is bad, we skip $HASH2\n+# but $HASH3 is good,\n+# so we should find $HASH4 as the first bad commit\n+test_expect_success 'bisect skip: successful result' '\n+\ttest_when_finished git bisect reset &&\n+\tgit bisect reset &&\n+\tgit bisect start $HASH4 $HASH1 &&\n+\tif [ $(git rev-parse HEAD) == $HASH2 ]; then\n+\t\tgit bisect skip\n+\tfi &&\n+\tgit bisect good > my_bisect_log.txt &&\n+\tgrep \"$HASH4 is the first bad commit\" my_bisect_log.txt\n+'\n+\n # $HASH1 is good, $HASH4 is bad, we skip $HASH3 and $HASH2\n # so we should not be able to tell the first bad commit\n # among $HASH2, $HASH3 and $HASH4\n-- \n2.26.2\n\n"},{"id":"441619","messageId":"20211118164940.8818-4-jack@suse.cz","threadId":"56938","inReplyTo":"20211118164940.8818-1-jack@suse.cz","subject":"[PATCH 03/27] bisect: Fixup test bisect-porcelain/20","fromName":"Jan Kara","fromEmail":"jack@suse.cz","sentAt":"2021-11-18T16:49:16Z","receivedAt":"2021-11-18T16:49:53Z","isPatch":true,"sender":{"key":"jack@suse.cz","avatar":null},"body":"Test 20 from t6030-bisect-porcelain.sh fails if the bisection algorithm\npicks HASH2 instead of HASH3 as the first step although these are\nequivalent. Fix the test to work in both cases.\n\nSigned-off-by: Jan Kara \n---\n t/t6030-bisect-porcelain.sh | 9 +++++++--\n 1 file changed, 7 insertions(+), 2 deletions(-)\n\ndiff --git a/t/t6030-bisect-porcelain.sh b/t/t6030-bisect-porcelain.sh\nindex f8cfdd3c36d2..13f7deea4d81 100755\n--- a/t/t6030-bisect-porcelain.sh\n+++ b/t/t6030-bisect-porcelain.sh\n@@ -240,8 +240,13 @@ test_expect_success 'bisect skip: cannot tell between 3 commits' '\n test_expect_success 'bisect skip: cannot tell between 2 commits' '\n \ttest_when_finished git bisect reset &&\n \tgit bisect start $HASH4 $HASH1 &&\n-\tgit bisect skip &&\n-\ttest_expect_code 2 git bisect good >my_bisect_log.txt &&\n+\tif [ $(git rev-parse HEAD) == $HASH2 ]; then\n+\t\tresults=('good' 'skip')\n+\telse\n+\t\tresults=('skip' 'good')\n+\tfi &&\n+\tgit bisect ${results[0]} &&\n+\ttest_expect_code 2 git bisect ${results[1]} >my_bisect_log.txt &&\n \tgrep \"first bad commit could be any of\" my_bisect_log.txt &&\n \t! grep $HASH1 my_bisect_log.txt &&\n \t! grep $HASH2 my_bisect_log.txt &&\n-- \n2.26.2\n\n"},{"id":"441620","messageId":"20211118164940.8818-2-jack@suse.cz","threadId":"56938","inReplyTo":"20211118164940.8818-1-jack@suse.cz","subject":"[PATCH 01/27] bisect: Fixup test rev-list-bisect/02","fromName":"Jan Kara","fromEmail":"jack@suse.cz","sentAt":"2021-11-18T16:49:14Z","receivedAt":"2021-11-18T16:49:54Z","isPatch":true,"sender":{"key":"jack@suse.cz","avatar":null},"body":"Test 2 from t6002-rev-list-bisect.sh expects 'c2' as the bisection point\nbut b2 is an equivalent choice. Improve the test to accept both.\n\nSigned-off-by: Jan Kara \n---\n t/t6002-rev-list-bisect.sh | 5 +++--\n 1 file changed, 3 insertions(+), 2 deletions(-)\n\ndiff --git a/t/t6002-rev-list-bisect.sh b/t/t6002-rev-list-bisect.sh\nindex b95a0212adff..48db52447fd3 100755\n--- a/t/t6002-rev-list-bisect.sh\n+++ b/t/t6002-rev-list-bisect.sh\n@@ -247,8 +247,9 @@ test_expect_success 'set up fake --bisect refs' '\n test_expect_success 'rev-list --bisect can default to good/bad refs' '\n \t# the only thing between c3 and c1 is c2\n \tgit rev-parse c2 >expect &&\n-\tgit rev-list --bisect >actual &&\n-\ttest_cmp expect actual\n+\tgit rev-parse b2 >>expect &&\n+\tactual=$(git rev-list --bisect) &&\n+\tgrep &>/dev/null $actual expect\n '\n \n test_expect_success 'rev-parse --bisect can default to good/bad refs' '\n-- \n2.26.2\n\n"},{"id":"441621","messageId":"20211118164940.8818-1-jack@suse.cz","threadId":"56938","inReplyTo":null,"subject":"Stochastic bisection support","fromName":"Jan Kara","fromEmail":"jack@suse.cz","sentAt":"2021-11-18T16:49:13Z","receivedAt":"2021-11-18T16:49:55Z","isPatch":false,"sender":{"key":"jack@suse.cz","avatar":null},"body":"Hello,\n\nIn some cases regressions (or generally changes) we are trying to bisect have\nprobabilistic nature. This can for example happen for hard to trigger race\ncondition where it is difficult to distinguish working state from just not\nhitting the race or it can happen for performance regressions where it is\nsometimes difficult to distinguish random workload fluctuations from the\nregression we are looking for. With standard bisection the only option we have\nis to repeatedly test suggested bisection point until we are sure enough which\nway to go. This leads to rather long bisection times and still a single wrong\ndecision whether a commit is good to bad renders the whole bisection useless.\n\nStochastic bisection tries to address these problems. When deciding whether a\ncommit is good or bad, you can also specify your confidence in the decision.\nFor performance tests you can usually directly infer this confidence from the\ndistance of your current result from good/bad values, for hard to reproduce\nraces you are usually 100% confident for bad commits, for good commits you need\nto somehow estimate your confidence based on past experience with reproducing\nthe issue. The stochastic bisection algorithm then uses these test results\nand confidences to suggest next commit to try, tracking for each commit the\nprobability the commit is the bad one given current test results. Once some\ncommit reaches high enough probability (set when starting bisection) of being\nthe bad one, we stop bisecting and annouce this commit.\n\nExample:\n\nConsider an example of a stochastic bisection of the following commits:\n\nA--B--C--D-----F-----H--------K\n \\ \\ \\-E-/ / /\n \\ \\--------G-/ /\n \\------------------I--J-/\n\nAnd suppose commit I is the bad one. Let's start bisection with:\n\n# We ask bisection for 90% confidence in the identified commit being bad\ngit bisect start --confidence 0.9 %K %A\n\n# Bisection tells us to test %F. Let's assume test went well and we trust\n# our test results on 70%. So:\ngit bisect good --confidence 0.7\n\n# Bisection tells us to test %H. Again same result:\ngit bisect good --confidence 0.7\n\n# Bisection tells us to test %J. The test should fail for %J (remember %I is\n# the bad commit) but let's assume the test is falsely positive. So:\ngit bisect good --confidence 0.7\n\n# We are asked to test %H second time. Assume correct result so:\ngit bisect good --confidence 0.7\n\n# We are asked to test %J second time. Assume correct result so:\ngit bisect bad --confidence 0.7\n\n# We are asked to test %J again. Assume correct result so:\ngit bisect bad --confidence 0.7\n\n# And %J once more. Assume false positive so:\ngit bisect good --confidence 0.7\n\n# And %J once more. Assume correct result so:\ngit bisect bad --confidence 0.7\n\n# And %J again. Assume correct result so:\ngit bisect bad --confidence 0.7\n\n# And now we are asked to test %I. Assume correct result so:\ngit bisect bad --confidence 0.7\n\n# We are asked to test %I second time. Assume false positive so:\ngit bisect good --confidence 0.7\n\n# And %I once again. Assume correct result so:\ngit bisect bad --confidence 0.7\n\n# And %I once again. Assume correct result so:\ngit bisect bad --confidence 0.7\n\n# And %I once again. Assume correct result so:\ngit bisect bad --confidence 0.7\n\nAnd now git tells us %I is the bad commit with desired confidence. We can see\nthe bisection was able to identify the bad commit although there were three\nfalse positive tests (out of total 14 tests).\n\n------\n\nThis patch set implements stochastic bisection for git. The first part of the\nseries improves some tests so that they accept other valid decisions for\nbisection points. This is needed because to make it easier to share some logic\nbetween normal and stochastic bisection, I needed to slightly change some bits\nfor normal bisection and then since commit weights will be computed in a\nsomewhat different order, also chosen bisection points are sometimes different.\n\nThe second part of the series then implements stochastic bisection itself.\nNote that I didn't integrate any tests for stochastic bisection into 'make\ntest' run yet (so far I did only manual tests) and I still need to update\nmanpages etc. I plan to do that but I've decided to post the series now to get\nsome early feedback.\n\n\t\t\t\t\t\t\t\tHonza\n\nPS: Please leave me in CC for replies. I'm not subscribed to the git mailing\nlist.\n"},{"id":"441622","messageId":"20211118164940.8818-11-jack@suse.cz","threadId":"56938","inReplyTo":"20211118164940.8818-1-jack@suse.cz","subject":"[PATCH 10/27] bisect: Fixup bisect-porcelain/58","fromName":"Jan Kara","fromEmail":"jack@suse.cz","sentAt":"2021-11-18T16:49:23Z","receivedAt":"2021-11-18T16:49:55Z","isPatch":true,"sender":{"key":"jack@suse.cz","avatar":null},"body":"Test 58 from t6030-bisect-porcelain.sh assumes that bisection algorithm\nsuggests HASH6 as the last bisection step when HASH5 is an equivalent\nchoice. Fix the test to work in both cases.\n\nSigned-off-by: Jan Kara \n---\n t/t6030-bisect-porcelain.sh | 3 ++-\n 1 file changed, 2 insertions(+), 1 deletion(-)\n\ndiff --git a/t/t6030-bisect-porcelain.sh b/t/t6030-bisect-porcelain.sh\nindex 46d67929e1e5..3363dc765b9d 100755\n--- a/t/t6030-bisect-porcelain.sh\n+++ b/t/t6030-bisect-porcelain.sh\n@@ -811,7 +811,8 @@ test_expect_success '\"git bisect bad HEAD\" behaves as \"git bisect bad\"' '\n \tgit bisect start HEAD $HASH1 &&\n \tgit bisect good HEAD &&\n \tgit bisect bad HEAD &&\n-\ttest \"$HASH6\" = $(git rev-parse --verify HEAD) &&\n+\trev=$(git rev-parse --verify HEAD) &&\n+\ttest \"$HASH5\" = \"$rev\" -o \"$HASH6\" = \"$rev\" &&\n \tgit bisect reset\n '\n \n-- \n2.26.2\n\n"},{"id":"441624","messageId":"20211118164940.8818-9-jack@suse.cz","threadId":"56938","inReplyTo":"20211118164940.8818-1-jack@suse.cz","subject":"[PATCH 08/27] bisect: Fixup bisect-porcelain/50","fromName":"Jan Kara","fromEmail":"jack@suse.cz","sentAt":"2021-11-18T16:49:21Z","receivedAt":"2021-11-18T16:49:56Z","isPatch":true,"sender":{"key":"jack@suse.cz","avatar":null},"body":"Test 50 from t6030-bisect-porcelain.sh assumes that bisection algorithm\nsuggests BROKEN_HASH6 when BROKEN_HASH5 is an equivalent choice. Fix the\ntest to work in both cases.\n\nSigned-off-by: Jan Kara \n---\n t/t6030-bisect-porcelain.sh | 15 ++++++++++++++-\n 1 file changed, 14 insertions(+), 1 deletion(-)\n\ndiff --git a/t/t6030-bisect-porcelain.sh b/t/t6030-bisect-porcelain.sh\nindex 4ec7b5b5a72e..79f253f01b00 100755\n--- a/t/t6030-bisect-porcelain.sh\n+++ b/t/t6030-bisect-porcelain.sh\n@@ -689,10 +689,23 @@ check_same()\n \ttest_cmp_rev \"$1\" \"$2\"\n }\n \n+check_oneof()\n+{\n+\tbase=\"$1\"\n+\tshift\n+\techo \"Checking $base is among $@\" &&\n+\tfor rev in \"$@\"; do\n+\t\tif test_cmp_rev \"$base\" \"$rev\"; then\n+\t\t\treturn 0\n+\t\tfi\n+\tdone\n+\treturn 1\n+}\n+\n test_expect_success 'bisect: --no-checkout - start commit bad' '\n \tgit bisect reset &&\n \tgit bisect start BROKEN_HASH7 BROKEN_HASH4 --no-checkout &&\n-\tcheck_same BROKEN_HASH6 BISECT_HEAD &&\n+\tcheck_oneof BISECT_HEAD BROKEN_HASH5 BROKEN_HASH6 &&\n \tgit bisect reset\n '\n \n-- \n2.26.2\n\n"},{"id":"441623","messageId":"20211118164940.8818-6-jack@suse.cz","threadId":"56938","inReplyTo":"20211118164940.8818-1-jack@suse.cz","subject":"[PATCH 05/27] bisect: Fixup bisect-porcelain/34","fromName":"Jan Kara","fromEmail":"jack@suse.cz","sentAt":"2021-11-18T16:49:18Z","receivedAt":"2021-11-18T16:49:57Z","isPatch":true,"sender":{"key":"jack@suse.cz","avatar":null},"body":"Test 34 from t6030-bisect-porcelain.sh assumes that bisection algorithm\nsuggests HASH6 after merge base when HASH5 is an equivalent choice. Fix\nthe test to work in both cases.\n\nSigned-off-by: Jan Kara \n---\n t/t6030-bisect-porcelain.sh | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\ndiff --git a/t/t6030-bisect-porcelain.sh b/t/t6030-bisect-porcelain.sh\nindex d693c0002098..ed81a6403b63 100755\n--- a/t/t6030-bisect-porcelain.sh\n+++ b/t/t6030-bisect-porcelain.sh\n@@ -433,7 +433,7 @@ test_expect_success 'good merge base when good and bad are siblings' '\n \tgrep $HASH4 my_bisect_log.txt &&\n \tgit bisect good > my_bisect_log.txt &&\n \t! grep \"merge base must be tested\" my_bisect_log.txt &&\n-\tgrep $HASH6 my_bisect_log.txt &&\n+\tgrep -E \"$HASH5|$HASH6\" my_bisect_log.txt &&\n \tgit bisect reset\n '\n test_expect_success 'skipped merge base when good and bad are siblings' '\n-- \n2.26.2\n\n"},{"id":"441625","messageId":"20211118164940.8818-10-jack@suse.cz","threadId":"56938","inReplyTo":"20211118164940.8818-1-jack@suse.cz","subject":"[PATCH 09/27] bisect: Fixup bisect-porcelain/54","fromName":"Jan Kara","fromEmail":"jack@suse.cz","sentAt":"2021-11-18T16:49:22Z","receivedAt":"2021-11-18T16:49:58Z","isPatch":true,"sender":{"key":"jack@suse.cz","avatar":null},"body":"Test 54 from t6030-bisect-porcelain.sh assumes that bisection algorithm\nsuggests BROKEN_HASH8 as the second bisection point when BROKEN_HASH7 is\nan equivalent choice. Fix the test to work in both cases.\n\nSigned-off-by: Jan Kara \n---\n t/t6030-bisect-porcelain.sh | 6 +++++-\n 1 file changed, 5 insertions(+), 1 deletion(-)\n\ndiff --git a/t/t6030-bisect-porcelain.sh b/t/t6030-bisect-porcelain.sh\nindex 79f253f01b00..46d67929e1e5 100755\n--- a/t/t6030-bisect-porcelain.sh\n+++ b/t/t6030-bisect-porcelain.sh\n@@ -743,7 +743,11 @@ test_expect_success 'bisect: --no-checkout - target after breakage' '\n \tgit bisect start broken BROKEN_HASH4 --no-checkout &&\n \tcheck_same BROKEN_HASH6 BISECT_HEAD &&\n \tgit bisect good BISECT_HEAD &&\n-\tcheck_same BROKEN_HASH8 BISECT_HEAD &&\n+\tcheck_oneof BISECT_HEAD BROKEN_HASH7 BROKEN_HASH8 &&\n+\tif check_same BROKEN_HASH7 BISECT_HEAD; then\n+\t\tgit bisect good BISECT_HEAD &&\n+\t\tcheck_same BROKEN_HASH8 BISECT_HEAD\n+\tfi &&\n \ttest_must_fail git bisect good BISECT_HEAD &&\n \tcheck_same BROKEN_HASH9 bisect/bad &&\n \tgit bisect reset\n-- \n2.26.2\n\n"},{"id":"441626","messageId":"20211118164940.8818-7-jack@suse.cz","threadId":"56938","inReplyTo":"20211118164940.8818-1-jack@suse.cz","subject":"[PATCH 06/27] bisect: Fixup bisect-porcelain/40","fromName":"Jan Kara","fromEmail":"jack@suse.cz","sentAt":"2021-11-18T16:49:19Z","receivedAt":"2021-11-18T16:50:00Z","isPatch":true,"sender":{"key":"jack@suse.cz","avatar":null},"body":"Test 40 from t6030-bisect-porcelain.sh assumes that bisection algorithm\nsuggests HASH6 after merge base when HASH5 is an equivalent choice. Fix\nthe test to work in both cases.\n\nSigned-off-by: Jan Kara \n---\n t/t6030-bisect-porcelain.sh | 5 +++--\n 1 file changed, 3 insertions(+), 2 deletions(-)\n\ndiff --git a/t/t6030-bisect-porcelain.sh b/t/t6030-bisect-porcelain.sh\nindex ed81a6403b63..0f2a91996393 100755\n--- a/t/t6030-bisect-porcelain.sh\n+++ b/t/t6030-bisect-porcelain.sh\n@@ -524,8 +524,9 @@ test_expect_success 'optimized merge base checks' '\n \tgrep \"$HASH4\" my_bisect_log.txt &&\n \tgit bisect good > my_bisect_log2.txt &&\n \ttest -f \".git/BISECT_ANCESTORS_OK\" &&\n-\ttest \"$HASH6\" = $(git rev-parse --verify HEAD) &&\n-\tgit bisect bad &&\n+\trev_hash=$(git rev-parse --verify HEAD) &&\n+\ttest \"$HASH5\" = \"$rev_hash\" -o \"$HASH6\" = \"$rev_hash\" &&\n+\tgit bisect bad \"$HASH6\" &&\n \tgit bisect good \"$A_HASH\" > my_bisect_log4.txt &&\n \ttest_i18ngrep \"merge base must be tested\" my_bisect_log4.txt &&\n \ttest_path_is_missing \".git/BISECT_ANCESTORS_OK\"\n-- \n2.26.2\n\n"},{"id":"441627","messageId":"20211118164940.8818-16-jack@suse.cz","threadId":"56938","inReplyTo":"20211118164940.8818-1-jack@suse.cz","subject":"[PATCH 15/27] bisect: Rename clear_distance() to clear_counted_flag()","fromName":"Jan Kara","fromEmail":"jack@suse.cz","sentAt":"2021-11-18T16:49:28Z","receivedAt":"2021-11-18T16:50:02Z","isPatch":true,"sender":{"key":"jack@suse.cz","avatar":null},"body":"clear_distance() only clears COUNTED flag. Rename the function to match\nwhat it does. No code changes.\n\nSigned-off-by: Jan Kara \n---\n bisect.c | 4 ++--\n 1 file changed, 2 insertions(+), 2 deletions(-)\n\ndiff --git a/bisect.c b/bisect.c\nindex 7416a57db4e3..675e8d433760 100644\n--- a/bisect.c\n+++ b/bisect.c\n@@ -68,7 +68,7 @@ static int count_distance(struct commit_list *entry)\n \treturn nr;\n }\n \n-static void clear_distance(struct commit_list *list)\n+static void clear_counted_flag(struct commit_list *list)\n {\n \twhile (list) {\n \t\tstruct commit *commit = list->item;\n@@ -339,7 +339,7 @@ static struct commit_list *do_find_bisection(struct commit_list *list,\n \t\tif (bisect_flags & FIND_BISECTION_FIRST_PARENT_ONLY)\n \t\t\tBUG(\"shouldn't be calling count-distance in fp mode\");\n \t\tweight_set(p, count_distance(p));\n-\t\tclear_distance(list);\n+\t\tclear_counted_flag(list);\n \n \t\t/* Does it happen to be at half-way? */\n \t\tif (!(bisect_flags & FIND_BISECTION_ALL) &&\n-- \n2.26.2\n\n"},{"id":"441628","messageId":"20211118164940.8818-21-jack@suse.cz","threadId":"56938","inReplyTo":"20211118164940.8818-1-jack@suse.cz","subject":"[PATCH 20/27] bisect: Compute probability a particular commit is bad","fromName":"Jan Kara","fromEmail":"jack@suse.cz","sentAt":"2021-11-18T16:49:33Z","receivedAt":"2021-11-18T16:50:04Z","isPatch":true,"sender":{"key":"jack@suse.cz","avatar":null},"body":"Compute conditional probability a commit is bad given results of tests\nperformed so far, for each commit in commit list.\n\nSigned-off-by: Jan Kara \n---\n bisect.c | 124 +++++++++++++++++++++++++++++++++++++++++++++++++++++++\n 1 file changed, 124 insertions(+)\n\ndiff --git a/bisect.c b/bisect.c\nindex cf11926d6f4e..680b96654fd4 100644\n--- a/bisect.c\n+++ b/bisect.c\n@@ -576,6 +576,128 @@ static struct commit_list *reverse_list(struct commit_list *list)\n \treturn last;\n }\n \n+struct sw_rev_bmp_hash_entry {\n+\tstruct hashmap_entry entry;\n+\tstruct st_weight *commit_weight;\n+\tfpnum_t cluster_p_bad;\n+\tunsigned int count;\n+};\n+\n+static int sw_rev_bmp_cmp(const void *data, const struct hashmap_entry *ap,\n+\t\t\t const struct hashmap_entry *bp, const void *keydata)\n+{\n+\tint i;\n+\tconst struct sw_rev_bmp_hash_entry *a, *b;\n+\n+\ta = container_of(ap, const struct sw_rev_bmp_hash_entry, entry);\n+\tb = container_of(bp, const struct sw_rev_bmp_hash_entry, entry);\n+\n+\tfor (i = 0; i < sw_rev_bmp_longs; i++)\n+\t\tif (a->commit_weight->rev_bitmap[i] !=\n+\t\t b->commit_weight->rev_bitmap[i])\n+\t\t\treturn 1;\n+\treturn 0;\n+}\n+\n+/*\n+ * Compute for each commit a probability it is the bad one given tests\n+ * performed so far.\n+ */\n+static void compute_commit_weights(struct commit_list *list)\n+{\n+\tstruct commit_list *p;\n+\tstruct hashmap reach_map;\n+\tstruct sw_rev_bmp_hash_entry *found_entry, entry;\n+\tstruct hashmap_iter reach_iter, trev_iter;\n+\tfpnum_t cluster_prob_sum = 0;\n+\n+\t/*\n+\t * We call a \"cluster\" a set of commits which have identical set of\n+\t * tested revisions that can reach to it. We compute the size of each\n+\t * cluster here - we count only tree-changing nodes as only those can\n+\t * be the bad ones.\n+\t */\n+\thashmap_init(&reach_map, sw_rev_bmp_cmp, NULL, ptest_revs.nr + 1);\n+\tfor (p = list; p; p = p->next) {\n+\t\tstruct st_weight *pweight;\n+\t\tunsigned int hashval;\n+\n+\t\tif (p->item->object.flags & TREESAME)\n+\t\t\tcontinue;\n+\n+\t\tpweight = *commit_weight_at(&commit_weight, p->item);\n+\t\thashval = memhash(pweight->rev_bitmap,\n+\t\t\t\tsw_rev_bmp_longs * sizeof(unsigned long));\n+\t\thashmap_entry_init(&entry.entry, hashval);\n+\t\tentry.commit_weight = pweight;\n+\t\tfound_entry = hashmap_get_entry(&reach_map, &entry, entry, NULL);\n+\t\tif (!found_entry) {\n+\t\t\tfound_entry = xmalloc(\n+\t\t\t\t\tsizeof(struct sw_rev_bmp_hash_entry));\n+\t\t\thashmap_entry_init(&found_entry->entry, hashval);\n+\t\t\tfound_entry->commit_weight = pweight;\n+\t\t\tfound_entry->count = 0;\n+\t\t\thashmap_add(&reach_map, &found_entry->entry);\n+\t\t}\n+\t\tfound_entry->count++;\n+\t}\n+\n+\t/*\n+\t * Compute probability bad commit is in a particular cluster. The\n+\t * probability is:\n+\t * P(error in cluster C) =\n+\t * \\Pi_{i\\in 'tested rev not reaching C'} P(test at i good) *\n+\t * \\Pi_{i\\in 'tested rev reaching C'} P(test at i bad)\n+\t */\n+\thashmap_for_each_entry(&reach_map, &reach_iter, found_entry, entry) {\n+\t\tfpnum_t cluster_prob = FP_ONE;\n+\t\tstruct tested_rev *trev;\n+\n+\t\thashmap_for_each_entry(&tested_revs_map, &trev_iter, trev,\n+\t\t\t\t entry) {\n+\t\t\tif (sw_rev_bmp_test(found_entry->commit_weight,\n+\t\t\t\t\t trev->index)) {\n+\t\t\t\tcluster_prob = fp_mul(cluster_prob,\n+\t\t\t\t\t\tFP_ONE - trev->confidence);\n+\t\t\t} else {\n+\t\t\t\tcluster_prob = fp_mul(cluster_prob,\n+\t\t\t\t\t\ttrev->confidence);\n+\t\t\t}\n+\t\t}\n+\t\tfound_entry->cluster_p_bad = cluster_prob;\n+\t\tcluster_prob_sum += cluster_prob;\n+\t}\n+\t/*\n+\t * Normalize the probabilities to sum to 1 - we need this normalization\n+\t * because in fact we compute conditional probability of bad commit\n+\t * being in a particular cluster given test results we already\n+\t * obtained.\n+\t */\n+\thashmap_for_each_entry(&reach_map, &reach_iter, found_entry, entry) {\n+\t\tfound_entry->cluster_p_bad = fp_div(found_entry->cluster_p_bad,\n+\t\t\t\t\t\t cluster_prob_sum);\n+\t}\n+\n+\t/* Uniformly distribute the probability among all nodes of a cluster */\n+\tfor (p = list; p; p = p->next) {\n+\t\tstruct st_weight *pweight;\n+\n+\t\tif (p->item->object.flags & TREESAME)\n+\t\t\tcontinue;\n+\n+\t\tpweight = *commit_weight_at(&commit_weight, p->item);\n+\t\thashmap_entry_init(&entry.entry,\n+\t\t\tmemhash(pweight->rev_bitmap,\n+\t\t\t\tsw_rev_bmp_longs * sizeof(unsigned long)));\n+\t\tentry.commit_weight = pweight;\n+\t\tfound_entry = hashmap_get_entry(&reach_map, &entry, entry, NULL);\n+\t\tpweight->node_weight =\n+\t\t\tfound_entry->cluster_p_bad / found_entry->count;\n+\t}\n+\n+\thashmap_clear_and_free(&reach_map, struct sw_rev_bmp_hash_entry, entry);\n+}\n+\n void find_bisection(struct commit_list **commit_list, int *reaches,\n \t\t int *all, unsigned bisect_flags)\n {\n@@ -615,6 +737,8 @@ void find_bisection(struct commit_list **commit_list, int *reaches,\n \tif (result_confidence)\n \t\tcompute_tested_descendants(list);\n \tlist = reverse_list(list);\n+\tif (result_confidence)\n+\t\tcompute_commit_weights(list);\n \tshow_list(\"bisection 2 sorted\", 0, nr, list);\n \n \t/* Do the real work of finding bisection commit. */\n-- \n2.26.2\n\n"},{"id":"441629","messageId":"20211118164940.8818-24-jack@suse.cz","threadId":"56938","inReplyTo":"20211118164940.8818-1-jack@suse.cz","subject":"[PATCH 23/27] bisect: Find bisection point for stochastic weights","fromName":"Jan Kara","fromEmail":"jack@suse.cz","sentAt":"2021-11-18T16:49:36Z","receivedAt":"2021-11-18T16:50:05Z","isPatch":true,"sender":{"key":"jack@suse.cz","avatar":null},"body":"The algorithm for finding the next bisection point for stochastic\nbisection is the same as for normal bisection. Just instead of uniform\nnode weight 1 we use the weights derived from computed fault\nprobabilities. To allow reusing as much code as possible we change\nnormal bisection to use fixedpoint number type (uint64_t) for\ncomputations instead of int. It wastes 4 bytes per commit but is\nprobably worth the avoided duplication. We change the functions deciding\nabout bisection point to work on weights in [0,1] range and scale normal\nbisection weights to be in this range.\n\nSigned-off-by: Jan Kara \n---\n bisect.c | 138 ++++++++++++++++++++++++++++++++++-----------------\n fixedpoint.h | 10 ++++\n 2 files changed, 102 insertions(+), 46 deletions(-)\n\ndiff --git a/bisect.c b/bisect.c\nindex 8e47c3fb4b9e..12b027b86e75 100644\n--- a/bisect.c\n+++ b/bisect.c\n@@ -42,6 +42,12 @@ static const char *argv_checkout[] = {\"checkout\", \"-q\", NULL, \"--\", NULL};\n static const char *term_bad;\n static const char *term_good;\n \n+/*\n+ * Slab for keeping weight information associated with each commit. For normal\n+ * bisection we keep just weight of each commit (fpnum_t - fraction of\n+ * reachable commits), for stochastic bisection we keep struct st_weight which\n+ * contains more information.\n+ */\n define_commit_slab(commit_weight, void *);\n static struct commit_weight commit_weight;\n \n@@ -50,7 +56,9 @@ static struct commit_weight commit_weight;\n * weights.\n */\n struct st_weight {\n-\tfpnum_t weight;\t\t/* Total weight of all reachable commits */\n+\tfpnum_t weight;\t\t/* Total weight of all reachable commits. This\n+\t\t\t\t * has to be first in this struct for weight()\n+\t\t\t\t * and weight_set() to work correctly. */\n \tfpnum_t node_weight;\t/* Weight of this particular commit */\n \tunsigned long rev_bitmap[];\t/* Bitmap of tested commits reaching\n \t\t\t\t\t * this commit */\n@@ -71,14 +79,26 @@ static inline int has_weight(struct commit_list *elem)\n \t *commit_weight_at(&commit_weight, elem->item) != NULL;\n }\n \n-static inline int weight(struct commit_list *elem)\n+static inline fpnum_t weight(struct commit_list *elem)\n+{\n+\treturn *(fpnum_t *)*commit_weight_at(&commit_weight, elem->item);\n+}\n+\n+static inline void weight_set(struct commit_list *elem, fpnum_t weight)\n {\n-\treturn *(int *)*commit_weight_at(&commit_weight, elem->item);\n+\t*(fpnum_t *)*commit_weight_at(&commit_weight, elem->item) = weight;\n }\n \n-static inline void weight_set(struct commit_list *elem, int weight)\n+static inline fpnum_t node_weight(struct commit_list *elem)\n {\n-\t*(int *)*commit_weight_at(&commit_weight, elem->item) = weight;\n+\t/*\n+\t * For normal bisection weight of each node is 1. For stochastic\n+\t * bisection we use the weight computed based on test results.\n+\t */\n+\tif (result_confidence)\n+\t\treturn ((struct st_weight *)*commit_weight_at(&commit_weight,\n+\t\t\t\t\telem->item))->node_weight;\n+\treturn FP_ONE;\n }\n \n #define BITS_PER_LONG (sizeof(long) * 8)\n@@ -133,9 +153,9 @@ static int count_interesting_parents(struct commit *commit)\n * We care just barely enough to avoid recursing for\n * non-merge entries.\n */\n-static int count_distance(struct commit_list *entry)\n+static fpnum_t count_distance(struct commit_list *entry)\n {\n-\tint nr = 0;\n+\tfpnum_t weight = 0;\n \n \twhile (entry) {\n \t\tstruct commit *commit = entry->item;\n@@ -144,20 +164,20 @@ static int count_distance(struct commit_list *entry)\n \t\tif (commit->object.flags & (UNINTERESTING | COUNTED))\n \t\t\tbreak;\n \t\tif (!(commit->object.flags & TREESAME))\n-\t\t\tnr++;\n+\t\t\tweight += node_weight(entry);\n \t\tcommit->object.flags |= COUNTED;\n \t\tp = commit->parents;\n \t\tentry = p;\n \t\tif (p) {\n \t\t\tp = p->next;\n \t\t\twhile (p) {\n-\t\t\t\tnr += count_distance(p);\n+\t\t\t\tweight += count_distance(p);\n \t\t\t\tp = p->next;\n \t\t\t}\n \t\t}\n \t}\n \n-\treturn nr;\n+\treturn weight;\n }\n \n static void clear_counted_flag(struct commit_list *list)\n@@ -169,9 +189,18 @@ static void clear_counted_flag(struct commit_list *list)\n \t}\n }\n \n+/* Return scale of weights in commit_weight() array */\n+static int weight_scale(int nr)\n+{\n+\tif (result_confidence)\n+\t\treturn 1;\n+\treturn nr;\n+}\n+\n static inline int approx_halfway(struct commit_list *p, int nr)\n {\n-\tint diff;\n+\tfpnum_t diff;\n+\tint scale = weight_scale(nr);\n \n \t/*\n \t * Don't short-cut something we are not going to return!\n@@ -180,25 +209,30 @@ static inline int approx_halfway(struct commit_list *p, int nr)\n \t\treturn 0;\n \tif (DEBUG_BISECT)\n \t\treturn 0;\n-\t/*\n-\t * For small number of commits 2 and 3 are halfway of 5, and\n-\t * 3 is halfway of 6 but 2 and 4 are not.\n-\t */\n-\tdiff = 2 * weight(p) - nr;\n-\tswitch (diff) {\n-\tcase -1: case 0: case 1:\n-\t\treturn 1;\n-\tdefault:\n+\n+\tif (!result_confidence) {\n+\t\tscale = nr;\n \t\t/*\n-\t\t * For large number of commits we are not so strict, it's\n-\t\t * good enough if it's within ~0.1% of the halfway point,\n-\t\t * e.g. 5000 is exactly halfway of 10000, but we consider\n-\t\t * the values [4996, 5004] as halfway as well.\n+\t\t * For small number of commits 2 and 3 are halfway of 5, and 3\n+\t\t * is halfway of 6 but 2 and 4 are not. For large number of\n+\t\t * commits we are not so strict, it's good enough if it's\n+\t\t * within ~0.1% of the halfway point, e.g. 5000 is exactly\n+\t\t * halfway of 10000, but we consider the values [4996, 5004] as\n+\t\t * halfway as well.\n \t\t */\n-\t\tif (abs(diff) < nr / 1024)\n-\t\t\treturn 1;\n-\t\treturn 0;\n+\t\tdiff = frac_to_fp((nr + 1023) / 1024, nr);\n+\t} else {\n+\t\t/*\n+\t\t * For stochastic we accept any node whose weight is within\n+\t\t * 1/16 from the middle. In the worst case this may result in\n+\t\t * ~20% more tests which is not too bad.\n+\t\t */\n+\t\tdiff = frac_to_fp(1, 16);\n \t}\n+\tif (weight(p) > (FP_HALF - diff) * scale &&\n+\t weight(p) < (FP_HALF + diff) * scale)\n+\t\treturn 1;\n+\treturn 0;\n }\n \n static void show_list(const char *debug, int counted, int nr,\n@@ -227,7 +261,7 @@ static void show_list(const char *debug, int counted, int nr,\n \t\t\t(commit_flags & UNINTERESTING) ? 'U' : ' ',\n \t\t\t(commit_flags & COUNTED) ? 'C' : ' ');\n \t\tif (has_weight(p))\n-\t\t\tfprintf(stderr, \"%3d\", weight(p));\n+\t\t\tfprintf(stderr, \"%lf\", fp_to_double(weight(p)));\n \t\telse\n \t\t\tfprintf(stderr, \"---\");\n \t\tfprintf(stderr, \" %.*s\", 8, oid_to_hex(&commit->object.oid));\n@@ -245,19 +279,20 @@ static void show_list(const char *debug, int counted, int nr,\n static struct commit_list *best_bisection(struct commit_list *list, int nr)\n {\n \tstruct commit_list *p, *best;\n-\tint best_distance = -1;\n+\tfpnum_t best_distance = -1;\n+\tint scale = weight_scale(nr);\n \n \tbest = list;\n \tfor (p = list; p; p = p->next) {\n-\t\tint distance;\n+\t\tfpnum_t distance;\n \t\tunsigned commit_flags = p->item->object.flags;\n \n \t\tif (commit_flags & TREESAME)\n \t\t\tcontinue;\n \t\tdistance = weight(p);\n-\t\tif (nr - distance < distance)\n-\t\t\tdistance = nr - distance;\n-\t\tif (distance > best_distance) {\n+\t\tif (distance > FP_HALF * scale)\n+\t\t\tdistance = FP_ONE * scale - distance;\n+\t\tif (best_distance == -1 || distance > best_distance) {\n \t\t\tbest = p;\n \t\t\tbest_distance = distance;\n \t\t}\n@@ -268,7 +303,7 @@ static struct commit_list *best_bisection(struct commit_list *list, int nr)\n \n struct commit_dist {\n \tstruct commit *commit;\n-\tint distance;\n+\tfpnum_t distance;\n };\n \n static int compare_commit_dist(const void *a_, const void *b_)\n@@ -277,27 +312,32 @@ static int compare_commit_dist(const void *a_, const void *b_)\n \n \ta = (struct commit_dist *)a_;\n \tb = (struct commit_dist *)b_;\n-\tif (a->distance != b->distance)\n-\t\treturn b->distance - a->distance; /* desc sort */\n+\tif (a->distance != b->distance) {\n+\t\tif (a->distance > b->distance)\n+\t\t\treturn -1;\n+\t\treturn 1;\n+\t}\n \treturn oidcmp(&a->commit->object.oid, &b->commit->object.oid);\n }\n \n-static struct commit_list *best_bisection_sorted(struct commit_list *list, int nr)\n+static struct commit_list *best_bisection_sorted(struct commit_list *list,\n+\t\t\t\t\t\t int nr)\n {\n \tstruct commit_list *p;\n \tstruct commit_dist *array = xcalloc(nr, sizeof(*array));\n \tstruct strbuf buf = STRBUF_INIT;\n \tint cnt, i;\n+\tint scale = weight_scale(nr);\n \n \tfor (p = list, cnt = 0; p; p = p->next) {\n-\t\tint distance;\n+\t\tfpnum_t distance;\n \t\tunsigned commit_flags = p->item->object.flags;\n \n \t\tif (commit_flags & TREESAME)\n \t\t\tcontinue;\n \t\tdistance = weight(p);\n-\t\tif (nr - distance < distance)\n-\t\t\tdistance = nr - distance;\n+\t\tif (distance > FP_HALF * scale)\n+\t\t\tdistance = FP_ONE * scale - distance;\n \t\tarray[cnt].commit = p->item;\n \t\tarray[cnt].distance = distance;\n \t\tcnt++;\n@@ -307,7 +347,13 @@ static struct commit_list *best_bisection_sorted(struct commit_list *list, int n\n \t\tstruct object *obj = &(array[i].commit->object);\n \n \t\tstrbuf_reset(&buf);\n-\t\tstrbuf_addf(&buf, \"dist=%d\", array[i].distance);\n+\t\tif (!result_confidence) {\n+\t\t\tstrbuf_addf(&buf, \"dist=%u\",\n+\t\t\t\t fp_to_int(array[i].distance));\n+\t\t} else {\n+\t\t\tstrbuf_addf(&buf, \"dist=%lf\",\n+\t\t\t\t fp_to_double(array[i].distance));\n+\t\t}\n \t\tadd_name_decoration(DECORATION_NONE, buf.buf, obj);\n \n \t\tp->item = array[i].commit;\n@@ -323,7 +369,7 @@ static struct commit_list *best_bisection_sorted(struct commit_list *list, int n\n \treturn list;\n }\n \n-#define WEIGHT_UNSET -1\n+#define WEIGHT_UNSET ((fpnum_t)-1)\n \n /*\n * Zero or positive weight is the number of interesting commits it can\n@@ -381,7 +427,7 @@ static struct commit_list *do_find_bisection(struct commit_list *list,\n \t\tfor (p = list; p; p = p->next) {\n \t\t\tstruct commit_list *q;\n \t\t\tunsigned commit_flags = p->item->object.flags;\n-\t\t\tint parent_weight = 0;\n+\t\t\tfpnum_t parent_weight = 0;\n \n \t\t\tif (weight(p) != WEIGHT_UNSET)\n \t\t\t\tcontinue;\n@@ -408,7 +454,7 @@ static struct commit_list *do_find_bisection(struct commit_list *list,\n \t\t\t * otherwise inherit it from q directly.\n \t\t\t */\n \t\t\tif (!(commit_flags & TREESAME)) {\n-\t\t\t\tweight_set(p, parent_weight + 1);\n+\t\t\t\tweight_set(p, parent_weight + node_weight(p));\n \t\t\t\tcounted++;\n \t\t\t\tshow_list(\"bisection 2 count one\",\n \t\t\t\t\t counted, nr, list);\n@@ -433,7 +479,7 @@ static struct commit_list *do_find_bisection(struct commit_list *list,\n \n static void *setup_commit_weight_array(struct commit_list *list, int nodes)\n {\n-\tint entry_size = sizeof(int);\n+\tint entry_size = sizeof(fpnum_t);\n \tvoid *array;\n \tstruct commit_list *p;\n \tint n;\n@@ -725,7 +771,7 @@ void find_bisection(struct commit_list **commit_list, int *reaches,\n \t\t\tbest = list;\n \t\t\tbest->next = NULL;\n \t\t}\n-\t\t*reaches = weight(best);\n+\t\t*reaches = fp_to_int(weight(best) * (nr / weight_scale(nr)));\n \t}\n \tfree(weights);\n \t*commit_list = best;\ndiff --git a/fixedpoint.h b/fixedpoint.h\nindex 159bb6ef4358..6d03a5e010ee 100644\n--- a/fixedpoint.h\n+++ b/fixedpoint.h\n@@ -14,6 +14,16 @@ static inline const fpnum_t frac_to_fp(unsigned int n, unsigned int d)\n \treturn (((fpnum_t)n) << FIXEDPOINT_SHIFT) / d;\n }\n \n+static inline const fpnum_t int_to_fp(unsigned int n)\n+{\n+\treturn ((fpnum_t)n) << FIXEDPOINT_SHIFT;\n+}\n+\n+static inline unsigned int fp_to_int(fpnum_t n)\n+{\n+\treturn (n + (1ULL << (FIXEDPOINT_SHIFT - 1))) >> FIXEDPOINT_SHIFT;\n+}\n+\n static inline const fpnum_t double_to_fp(double n)\n {\n \treturn (n * (1ULL << FIXEDPOINT_SHIFT));\n-- \n2.26.2\n\n"},{"id":"441630","messageId":"20211118164940.8818-12-jack@suse.cz","threadId":"56938","inReplyTo":"20211118164940.8818-1-jack@suse.cz","subject":"[PATCH 11/27] bisect: Fix bisection debugging","fromName":"Jan Kara","fromEmail":"jack@suse.cz","sentAt":"2021-11-18T16:49:24Z","receivedAt":"2021-11-18T16:50:07Z","isPatch":true,"sender":{"key":"jack@suse.cz","avatar":null},"body":"show_list() dumps commit weights associated with each commit. Thus it\nneeds commit_weight slab already initialized. Move initialization of\ncommit_weight slab before the first show_list() call.\n\nSigned-off-by: Jan Kara \n---\n bisect.c | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\ndiff --git a/bisect.c b/bisect.c\nindex 888949fba6b5..ab264b8ca879 100644\n--- a/bisect.c\n+++ b/bisect.c\n@@ -395,8 +395,8 @@ void find_bisection(struct commit_list **commit_list, int *reaches,\n \tstruct commit_list *list, *p, *best, *next, *last;\n \tint *weights;\n \n-\tshow_list(\"bisection 2 entry\", 0, 0, *commit_list);\n \tinit_commit_weight(&commit_weight);\n+\tshow_list(\"bisection 2 entry\", 0, 0, *commit_list);\n \n \t/*\n \t * Count the number of total and tree-changing items on the\n-- \n2.26.2\n\n"},{"id":"441631","messageId":"20211118164940.8818-14-jack@suse.cz","threadId":"56938","inReplyTo":"20211118164940.8818-1-jack@suse.cz","subject":"[PATCH 13/27] bisect: Allow specifying desired result confidence","fromName":"Jan Kara","fromEmail":"jack@suse.cz","sentAt":"2021-11-18T16:49:26Z","receivedAt":"2021-11-18T16:50:08Z","isPatch":true,"sender":{"key":"jack@suse.cz","avatar":null},"body":"Allow specifying desired result confidence for stochastic bisection\nwhen starting bisection. Store it and load it when doing bisection\nsteps.\n\nSigned-off-by: Jan Kara \n---\n bisect.c | 15 ++++++++++++++-\n builtin/bisect--helper.c | 22 +++++++++++++++++++++-\n fixedpoint.h | 1 +\n 3 files changed, 36 insertions(+), 2 deletions(-)\n\ndiff --git a/bisect.c b/bisect.c\nindex 0773a872c82b..f87753d0c67c 100644\n--- a/bisect.c\n+++ b/bisect.c\n@@ -22,6 +22,8 @@ static struct oid_array good_revs;\n static struct oid_array ptest_revs;\n static struct oid_array skipped_revs;\n \n+static fpnum_t result_confidence;\n+\n static struct object_id *current_bad_oid;\n \n static const char *argv_checkout[] = {\"checkout\", \"-q\", NULL, \"--\", NULL};\n@@ -482,15 +484,25 @@ static GIT_PATH_FUNC(git_path_bisect_log, \"BISECT_LOG\")\n static GIT_PATH_FUNC(git_path_bisect_terms, \"BISECT_TERMS\")\n static GIT_PATH_FUNC(git_path_bisect_first_parent, \"BISECT_FIRST_PARENT\")\n static GIT_PATH_FUNC(git_path_bisect_confidences, \"BISECT_CONFIDENCES\")\n+static GIT_PATH_FUNC(git_path_bisect_result_confidence, \"BISECT_RESULT_CONFIDENCE\")\n static GIT_PATH_FUNC(git_path_head_name, \"head-name\")\n \n static void read_bisect_confidences(void)\n {\n \tstruct strbuf str = STRBUF_INIT;\n-\tconst char *filename = git_path_bisect_confidences();\n+\tconst char *filename = git_path_bisect_result_confidence();\n \tFILE *fp = fopen(filename, \"r\");\n \n \t/* Just a regular bisection? */\n+\tif (!fp)\n+\t\treturn;\n+\tif (fscanf(fp, \"%\"FPNUM_FMT, &result_confidence) != 1)\n+\t\tdie(_(\"Cannot parse result confidence in file '%s'\"), filename);\n+\tfclose(fp);\n+\n+\t/* No uncertain bisection steps yet? */\n+\tfilename = git_path_bisect_confidences();\n+\tfp = fopen(filename, \"r\");\n \tif (!fp)\n \t\treturn;\n \n@@ -1223,6 +1235,7 @@ int bisect_clean_state(void)\n \tunlink_or_warn(git_path_bisect_terms());\n \tunlink_or_warn(git_path_bisect_first_parent());\n \tunlink_or_warn(git_path_bisect_confidences());\n+\tunlink_or_warn(git_path_bisect_result_confidence());\n \t/* Cleanup head-name if it got left by an old version of git-bisect */\n \tunlink_or_warn(git_path_head_name());\n \t/*\ndiff --git a/builtin/bisect--helper.c b/builtin/bisect--helper.c\nindex f88feb8da949..5b46a8ca3fd9 100644\n--- a/builtin/bisect--helper.c\n+++ b/builtin/bisect--helper.c\n@@ -21,12 +21,14 @@ static GIT_PATH_FUNC(git_path_bisect_names, \"BISECT_NAMES\")\n static GIT_PATH_FUNC(git_path_bisect_first_parent, \"BISECT_FIRST_PARENT\")\n static GIT_PATH_FUNC(git_path_bisect_run, \"BISECT_RUN\")\n static GIT_PATH_FUNC(git_path_bisect_confidences, \"BISECT_CONFIDENCES\")\n+static GIT_PATH_FUNC(git_path_bisect_result_confidence, \"BISECT_RESULT_CONFIDENCE\")\n \n static const char * const git_bisect_helper_usage[] = {\n \tN_(\"git bisect--helper --bisect-reset []\"),\n \tN_(\"git bisect--helper --bisect-terms [--term-good | --term-old | --term-bad | --term-new]\"),\n \tN_(\"git bisect--helper --bisect-start [--term-{new,bad}= --term-{old,good}=]\"\n-\t\t\t\t\t \" [--no-checkout] [--first-parent] [ [...]] [--] [...]\"),\n+\t\t\t\t\t \" [--no-checkout] [--first-parent] [--confidence ]\"\n+\t\t\t\t\t \" [ [...]] [--] [...]\"),\n \tN_(\"git bisect--helper --bisect-next\"),\n \tN_(\"git bisect--helper --bisect-state (bad|new) [--confidence ] []\"),\n \tN_(\"git bisect--helper --bisect-state (good|old) [--confidence ] [...]\"),\n@@ -668,6 +670,7 @@ static enum bisect_error bisect_start(struct bisect_terms *terms, const char **a\n \tstruct object_id head_oid;\n \tstruct object_id oid;\n \tconst char *head;\n+\tfpnum_t confidence = FP_ONE;\n \n \tif (is_bare_repository())\n \t\tno_checkout = 1;\n@@ -690,6 +693,16 @@ static enum bisect_error bisect_start(struct bisect_terms *terms, const char **a\n \t\t\tno_checkout = 1;\n \t\t} else if (!strcmp(arg, \"--first-parent\")) {\n \t\t\tfirst_parent_only = 1;\n+\t\t} else if (!strcmp(arg, \"--confidence\")) {\n+\t\t\ti++;\n+\t\t\tif (argc <= i)\n+\t\t\t\treturn error(_(\"missing confidence argument\"));\n+\t\t\tif (parse_confidence(argv[i], &confidence))\n+\t\t\t\treturn -1;\n+\t\t\tif (confidence == FP_ONE)\n+\t\t\t\treturn error(_(\"Absolute confidence not possible with stochastic bisection\"));\n+\t\t\tif (confidence < FP_HALF)\n+\t\t\t\treturn error(_(\"Target confidence of at least 0.5 needed for stochastic bisection\"));\n \t\t} else if (!strcmp(arg, \"--term-good\") ||\n \t\t\t !strcmp(arg, \"--term-old\")) {\n \t\t\ti++;\n@@ -809,6 +822,10 @@ static enum bisect_error bisect_start(struct bisect_terms *terms, const char **a\n \tif (first_parent_only)\n \t\twrite_file(git_path_bisect_first_parent(), \"\\n\");\n \n+\tif (confidence != FP_ONE)\n+\t\twrite_file(git_path_bisect_result_confidence(),\n+\t\t\t \"%\" FPNUM_FMT \"\\n\", confidence);\n+\n \tif (no_checkout) {\n \t\tif (get_oid(start_head.buf, &oid) < 0) {\n \t\t\tres = error(_(\"invalid ref: '%s'\"), start_head.buf);\n@@ -917,6 +934,9 @@ static enum bisect_error bisect_state(struct bisect_terms *terms, const char **a\n \t\t\treturn error(_(\"missing confidence argument\"));\n \t\tif (parse_confidence(argv[1], &confidence))\n \t\t\treturn -1;\n+\t\tif (is_empty_or_missing_file(git_path_bisect_result_confidence()))\n+\t\t\treturn error(_(\"Stochastic bisection not started. Pass \"\n+\t\t\t\t\"desired target confidence to git bisect start.\"));\n \t\targv += 2;\n \t\targc -= 2;\n \t}\ndiff --git a/fixedpoint.h b/fixedpoint.h\nindex addef223be2b..3f6234c6530a 100644\n--- a/fixedpoint.h\n+++ b/fixedpoint.h\n@@ -25,5 +25,6 @@ static inline const double fp_to_double(fpnum_t n)\n }\n \n #define FP_ONE frac_to_fp(1, 1)\n+#define FP_HALF frac_to_fp(1, 2)\n \n #endif\n-- \n2.26.2\n\n"},{"id":"441632","messageId":"20211118164940.8818-23-jack@suse.cz","threadId":"56938","inReplyTo":"20211118164940.8818-1-jack@suse.cz","subject":"[PATCH 22/27] bisect: Move count_distance()","fromName":"Jan Kara","fromEmail":"jack@suse.cz","sentAt":"2021-11-18T16:49:35Z","receivedAt":"2021-11-18T16:50:09Z","isPatch":true,"sender":{"key":"jack@suse.cz","avatar":null},"body":"Move count_distance() function as stochastic bisection will need to\ncall weight() from it and the move avoids forward declaration. No code\nchanges.\n\nSigned-off-by: Jan Kara \n---\n bisect.c | 92 ++++++++++++++++++++++++++++----------------------------\n 1 file changed, 46 insertions(+), 46 deletions(-)\n\ndiff --git a/bisect.c b/bisect.c\nindex 4107161c086c..8e47c3fb4b9e 100644\n--- a/bisect.c\n+++ b/bisect.c\n@@ -42,52 +42,6 @@ static const char *argv_checkout[] = {\"checkout\", \"-q\", NULL, \"--\", NULL};\n static const char *term_bad;\n static const char *term_good;\n \n-/* Remember to update object flag allocation in object.h */\n-#define COUNTED\t\t(1u<<16)\n-\n-/*\n- * This is a truly stupid algorithm, but it's only\n- * used for bisection, and we just don't care enough.\n- *\n- * We care just barely enough to avoid recursing for\n- * non-merge entries.\n- */\n-static int count_distance(struct commit_list *entry)\n-{\n-\tint nr = 0;\n-\n-\twhile (entry) {\n-\t\tstruct commit *commit = entry->item;\n-\t\tstruct commit_list *p;\n-\n-\t\tif (commit->object.flags & (UNINTERESTING | COUNTED))\n-\t\t\tbreak;\n-\t\tif (!(commit->object.flags & TREESAME))\n-\t\t\tnr++;\n-\t\tcommit->object.flags |= COUNTED;\n-\t\tp = commit->parents;\n-\t\tentry = p;\n-\t\tif (p) {\n-\t\t\tp = p->next;\n-\t\t\twhile (p) {\n-\t\t\t\tnr += count_distance(p);\n-\t\t\t\tp = p->next;\n-\t\t\t}\n-\t\t}\n-\t}\n-\n-\treturn nr;\n-}\n-\n-static void clear_counted_flag(struct commit_list *list)\n-{\n-\twhile (list) {\n-\t\tstruct commit *commit = list->item;\n-\t\tcommit->object.flags &= ~COUNTED;\n-\t\tlist = list->next;\n-\t}\n-}\n-\n define_commit_slab(commit_weight, void *);\n static struct commit_weight commit_weight;\n \n@@ -169,6 +123,52 @@ static int count_interesting_parents(struct commit *commit)\n \treturn count;\n }\n \n+/* Remember to update object flag allocation in object.h */\n+#define COUNTED\t\t(1u<<16)\n+\n+/*\n+ * This is a truly stupid algorithm, but it's only\n+ * used for bisection, and we just don't care enough.\n+ *\n+ * We care just barely enough to avoid recursing for\n+ * non-merge entries.\n+ */\n+static int count_distance(struct commit_list *entry)\n+{\n+\tint nr = 0;\n+\n+\twhile (entry) {\n+\t\tstruct commit *commit = entry->item;\n+\t\tstruct commit_list *p;\n+\n+\t\tif (commit->object.flags & (UNINTERESTING | COUNTED))\n+\t\t\tbreak;\n+\t\tif (!(commit->object.flags & TREESAME))\n+\t\t\tnr++;\n+\t\tcommit->object.flags |= COUNTED;\n+\t\tp = commit->parents;\n+\t\tentry = p;\n+\t\tif (p) {\n+\t\t\tp = p->next;\n+\t\t\twhile (p) {\n+\t\t\t\tnr += count_distance(p);\n+\t\t\t\tp = p->next;\n+\t\t\t}\n+\t\t}\n+\t}\n+\n+\treturn nr;\n+}\n+\n+static void clear_counted_flag(struct commit_list *list)\n+{\n+\twhile (list) {\n+\t\tstruct commit *commit = list->item;\n+\t\tcommit->object.flags &= ~COUNTED;\n+\t\tlist = list->next;\n+\t}\n+}\n+\n static inline int approx_halfway(struct commit_list *p, int nr)\n {\n \tint diff;\n-- \n2.26.2\n\n"},{"id":"441633","messageId":"20211118164940.8818-20-jack@suse.cz","threadId":"56938","inReplyTo":"20211118164940.8818-1-jack@suse.cz","subject":"[PATCH 19/27] bisect: Compute reachability of tested revs","fromName":"Jan Kara","fromEmail":"jack@suse.cz","sentAt":"2021-11-18T16:49:32Z","receivedAt":"2021-11-18T16:50:10Z","isPatch":true,"sender":{"key":"jack@suse.cz","avatar":null},"body":"Compute for each rev a bitmap of revs that can reach it and that were\ntested during stochastic bisection run.\n\nSigned-off-by: Jan Kara \n---\n bisect.c | 199 ++++++++++++++++++++++++++++++++++++++++++++++++++-\n fixedpoint.h | 18 +++++\n 2 files changed, 215 insertions(+), 2 deletions(-)\n\ndiff --git a/bisect.c b/bisect.c\nindex 3a26255e8650..cf11926d6f4e 100644\n--- a/bisect.c\n+++ b/bisect.c\n@@ -17,6 +17,7 @@\n #include \"object-store.h\"\n #include \"dir.h\"\n #include \"fixedpoint.h\"\n+#include \"hashmap.h\"\n \n static struct oid_array good_revs;\n static struct oid_array ptest_revs;\n@@ -24,6 +25,16 @@ static struct oid_array skipped_revs;\n \n static fpnum_t result_confidence;\n \n+struct tested_rev {\n+\tstruct hashmap_entry entry;\n+\tstruct object_id *oid;\n+\tint index;\t\t/* Index in ptest_revs array */\n+\tfpnum_t confidence;\t/* Total confidence the rev is good computed\n+\t\t\t\t * from of all tests on this rev */\n+};\n+\n+static struct hashmap tested_revs_map;\n+\n static struct object_id *current_bad_oid;\n \n static const char *argv_checkout[] = {\"checkout\", \"-q\", NULL, \"--\", NULL};\n@@ -80,8 +91,26 @@ static void clear_counted_flag(struct commit_list *list)\n define_commit_slab(commit_weight, void *);\n static struct commit_weight commit_weight;\n \n+/*\n+ * Information associated with each commit when computing stochastic bisection\n+ * weights.\n+ */\n+struct st_weight {\n+\tfpnum_t weight;\t\t/* Total weight of all reachable commits */\n+\tfpnum_t node_weight;\t/* Weight of this particular commit */\n+\tunsigned long rev_bitmap[];\t/* Bitmap of tested commits reaching\n+\t\t\t\t\t * this commit */\n+};\n+int sw_rev_bmp_longs;\n+\n #define DEBUG_BISECT 0\n \n+#if DEBUG_BISECT > 0\n+#define debug_bisect(fmt...) fprintf(stderr, fmt)\n+#else\n+#define debug_bisect(fmt...) do { } while (0)\n+#endif\n+\n static inline int has_weight(struct commit_list *elem)\n {\n \treturn commit_weight.slab_size > 0 &&\n@@ -98,6 +127,37 @@ static inline void weight_set(struct commit_list *elem, int weight)\n \t*(int *)*commit_weight_at(&commit_weight, elem->item) = weight;\n }\n \n+#define BITS_PER_LONG (sizeof(long) * 8)\n+\n+/*\n+ * Add bits in 'from' reachability bitmap to 'to'. Returns 1 if any bit in 'to'\n+ * was set.\n+ */\n+static int sw_rev_bmp_or(struct st_weight *to, struct st_weight *from)\n+{\n+\tint i;\n+\tint set = 0;\n+\n+\tfor (i = 0; i < sw_rev_bmp_longs; i++) {\n+\t\tunsigned long prev = to->rev_bitmap[i];\n+\n+\t\tto->rev_bitmap[i] |= from->rev_bitmap[i];\n+\t\tset |= (to->rev_bitmap[i] != prev);\n+\t}\n+\treturn set;\n+}\n+\n+static void sw_rev_bmp_set(struct st_weight *to, int idx)\n+{\n+\tto->rev_bitmap[idx / BITS_PER_LONG] |= 1UL << (idx % BITS_PER_LONG);\n+}\n+\n+static unsigned long sw_rev_bmp_test(struct st_weight *to, int idx)\n+{\n+\treturn to->rev_bitmap[idx / BITS_PER_LONG] &\n+\t\t\t\t\t(1UL << (idx % BITS_PER_LONG));\n+}\n+\n static int count_interesting_parents(struct commit *commit, unsigned bisect_flags)\n {\n \tstruct commit_list *p;\n@@ -403,6 +463,14 @@ static void *setup_commit_weight_array(struct commit_list *list, int nodes)\n \tstruct commit_list *p;\n \tint n;\n \n+\t/* Stochastic bisection? */\n+\tif (result_confidence) {\n+\t\tint revs = ptest_revs.nr + 1;\n+\n+\t\tsw_rev_bmp_longs = (revs + BITS_PER_LONG - 1) / BITS_PER_LONG;\n+\t\tentry_size = sizeof(struct st_weight) +\n+\t\t\t\t\tsw_rev_bmp_longs * sizeof(long);\n+\t}\n \tarray = xcalloc(nodes, entry_size);\n \tfor (n = 0, p = list; p; p = p->next, n++) {\n \t\t*commit_weight_at(&commit_weight, p->item) =\n@@ -411,6 +479,91 @@ static void *setup_commit_weight_array(struct commit_list *list, int nodes)\n \treturn array;\n }\n \n+static struct tested_rev *lookup_tested_oid(struct object_id *oid)\n+{\n+\tstruct tested_rev key;\n+\n+\thashmap_entry_init(&key.entry, oidhash(oid));\n+\tkey.oid = oid;\n+\treturn hashmap_get_entry(&tested_revs_map, &key, entry, NULL);\n+}\n+\n+static int sw_rev_test_idx(struct commit *commit)\n+{\n+\tstruct tested_rev *tr;\n+\n+\ttr = lookup_tested_oid(&commit->object.oid);\n+\tif (!tr)\n+\t\treturn -1;\n+\treturn tr->index;\n+}\n+\n+static int propagate_to_ancestors(struct commit *commit)\n+{\n+\tstruct commit_list *q;\n+\tint out_of_order = 0, set;\n+\tstruct st_weight *cw;\n+\n+\tcw = *commit_weight_at(&commit_weight, commit);\n+\tfor (q = commit->parents; q; q = q->next) {\n+\t\tif (q->item->object.flags & UNINTERESTING)\n+\t\t\tcontinue;\n+\t\tset = sw_rev_bmp_or(*commit_weight_at(&commit_weight, q->item),\n+\t\t\t\t cw);\n+\t\tif (set && q->item->object.flags & COUNTED) {\n+\t\t\tdebug_bisect(\"descendants_bitmap: Recursion for %s\\n\",\n+\t\t\t\t oid_to_hex(&q->item->object.oid));\n+\t\t\t/*\n+\t\t\t * If the commit is already processed, we need to\n+\t\t\t * propagate bitmap update to all already processed\n+\t\t\t * ancestors. The 'list' should be close to inverse\n+\t\t\t * topological order so this should be rare.\n+\t\t\t */\n+\t\t\tout_of_order = 1;\n+\t\t}\n+\t}\n+\treturn out_of_order;\n+}\n+\n+/*\n+ * For each commit in the 'list' compute bitmap of tested revisions that can\n+ * reach it. Note for our purposes each commit can reach itself.\n+ */\n+static void compute_tested_descendants(struct commit_list *list)\n+{\n+\tstruct commit_list *p;\n+\tint retry = 0, tried = 1;\n+\n+\tfor (p = list; p; p = p->next) {\n+\t\tstruct commit *commit = p->item;\n+\t\tstruct st_weight *cw;\n+\t\tint idx;\n+\n+\t\tcw = *commit_weight_at(&commit_weight, commit);\n+\t\tidx = sw_rev_test_idx(commit);\n+\t\tif (idx >= 0)\n+\t\t\tsw_rev_bmp_set(cw, idx);\n+\t\tretry = propagate_to_ancestors(commit);\n+\t\tcommit->object.flags |= COUNTED;\n+\t}\n+\tclear_counted_flag(list);\n+\t/*\n+\t * We expect the 'list' to be close to reverse topological order. If\n+\t * it is not exactly in reverse topological order, we need to repeat\n+\t * descendant bit propagation until bitmaps are stable.\n+\t */\n+\twhile (retry) {\n+\t\ttried++;\n+\t\tretry = 0;\n+\t\tfor (p = list; p; p = p->next) {\n+\t\t\tretry = propagate_to_ancestors(p->item);\n+\t\t\tp->item->object.flags |= COUNTED;\n+\t\t}\n+\t\tclear_counted_flag(list);\n+\t}\n+\tdebug_bisect(\"%s: Took %d iterations to stabilize.\\n\", __func__, tried);\n+}\n+\n static struct commit_list *reverse_list(struct commit_list *list)\n {\n \tstruct commit_list *p, *next, *last = NULL;\n@@ -459,6 +612,8 @@ void find_bisection(struct commit_list **commit_list, int *reaches,\n \t\tgoto out_weights;\n \t}\n \tweights = setup_commit_weight_array(list, on_list);\n+\tif (result_confidence)\n+\t\tcompute_tested_descendants(list);\n \tlist = reverse_list(list);\n \tshow_list(\"bisection 2 sorted\", 0, nr, list);\n \n@@ -522,11 +677,39 @@ static GIT_PATH_FUNC(git_path_bisect_confidences, \"BISECT_CONFIDENCES\")\n static GIT_PATH_FUNC(git_path_bisect_result_confidence, \"BISECT_RESULT_CONFIDENCE\")\n static GIT_PATH_FUNC(git_path_head_name, \"head-name\")\n \n+static int tested_rev_cmp(const void *data, const struct hashmap_entry *ap,\n+\t\t\t const struct hashmap_entry *bp, const void *keydata)\n+{\n+\tconst struct tested_rev *a, *b;\n+\n+\ta = container_of(ap, const struct tested_rev, entry);\n+\tb = container_of(bp, const struct tested_rev, entry);\n+\n+\treturn oidcmp(a->oid, b->oid);\n+}\n+\n+static void setup_tested_revs_map(void)\n+{\n+\tint i;\n+\tstruct tested_rev *tr;\n+\n+\thashmap_init(&tested_revs_map, tested_rev_cmp, NULL, ptest_revs.nr + 1);\n+\tfor (i = 0; i < ptest_revs.nr; i++) {\n+\t\ttr = xmalloc(sizeof(struct tested_rev));\n+\t\thashmap_entry_init(&tr->entry, oidhash(ptest_revs.oid + i));\n+\t\ttr->oid = ptest_revs.oid + i;\n+\t\ttr->index = i;\n+\t\ttr->confidence = FP_HALF;\n+\t\thashmap_add(&tested_revs_map, &tr->entry);\n+\t}\n+}\n+\n static void read_bisect_confidences(void)\n {\n \tstruct strbuf str = STRBUF_INIT;\n \tconst char *filename = git_path_bisect_result_confidence();\n \tFILE *fp = fopen(filename, \"r\");\n+\tstruct tested_rev *trev;\n \n \t/* Just a regular bisection? */\n \tif (!fp)\n@@ -535,6 +718,8 @@ static void read_bisect_confidences(void)\n \t\tdie(_(\"Cannot parse result confidence in file '%s'\"), filename);\n \tfclose(fp);\n \n+\tsetup_tested_revs_map();\n+\n \t/* No uncertain bisection steps yet? */\n \tfilename = git_path_bisect_confidences();\n \tfp = fopen(filename, \"r\");\n@@ -542,7 +727,7 @@ static void read_bisect_confidences(void)\n \t\treturn;\n \n \twhile (strbuf_getline_lf(&str, fp) != EOF) {\n-\t\tfpnum_t prob;\n+\t\tfpnum_t prob, pos_prob, neg_prob;\n \t\tchar *spc;\n \t\tchar state;\n \t\tstruct object_id oid;\n@@ -562,7 +747,17 @@ static void read_bisect_confidences(void)\n \t\tif (get_oid(str.buf, &oid))\n \t\t\tdie(_(\"Cannot get oid of rev '%s' from file '%s'\"),\n \t\t\t str.buf, filename);\n-\t\t/* We'll use parsed data later */\n+\t\ttrev = lookup_tested_oid(&oid);\n+\t\tif (!trev)\n+\t\t\tdie(_(\"Rev '%s' not tracked as ptest rev.\"), str.buf);\n+\t\tif (state == 'b')\n+\t\t\tprob = FP_ONE - prob;\n+\t\tpos_prob = fp_mul(trev->confidence, prob);\n+\t\tneg_prob = fp_mul(FP_ONE - trev->confidence, FP_ONE - prob);\n+\t\ttrev->confidence = fp_div(pos_prob, pos_prob + neg_prob);\n+\t\tdebug_bisect(\"read confidence %s: %\"FPNUM_FMT\n+\t\t\t\" (total %\"FPNUM_FMT\")\\n\",\n+\t\t\tstr.buf, prob, trev->confidence);\n \t}\n \tstrbuf_release(&str);\n \tfclose(fp);\ndiff --git a/fixedpoint.h b/fixedpoint.h\nindex 3f6234c6530a..159bb6ef4358 100644\n--- a/fixedpoint.h\n+++ b/fixedpoint.h\n@@ -27,4 +27,22 @@ static inline const double fp_to_double(fpnum_t n)\n #define FP_ONE frac_to_fp(1, 1)\n #define FP_HALF frac_to_fp(1, 2)\n \n+/* Multiplication for numbers <= 1 */\n+static inline const fpnum_t fp_mul(fpnum_t n, fpnum_t m)\n+{\n+\tif (m == FP_ONE)\n+\t\treturn n;\n+\tif (n == FP_ONE)\n+\t\treturn m;\n+\tassert(m < FP_ONE && n < FP_ONE);\n+\treturn (m * n) >> FIXEDPOINT_SHIFT;\n+}\n+\n+/* Division for number <= 1 */\n+static inline const fpnum_t fp_div(fpnum_t n, fpnum_t d)\n+{\n+\tassert(n <= FP_ONE);\n+\treturn (n << (FIXEDPOINT_SHIFT - 1)) / (d >> 1);\n+}\n+\n #endif\n-- \n2.26.2\n\n"},{"id":"441634","messageId":"20211118164940.8818-8-jack@suse.cz","threadId":"56938","inReplyTo":"20211118164940.8818-1-jack@suse.cz","subject":"[PATCH 07/27] bisect: Remove duplicated bisect-porcelain/48","fromName":"Jan Kara","fromEmail":"jack@suse.cz","sentAt":"2021-11-18T16:49:20Z","receivedAt":"2021-11-18T16:50:11Z","isPatch":true,"sender":{"key":"jack@suse.cz","avatar":null},"body":"Test 48 from t6030-bisect-porcelain.sh claims it tests whether bisection\nfails if tree is broken on start commit. However that actually does not\nhappen because the bisection really only fails because the first trial\npoint we choose happens to be broken. Furthermore there is another\nequivalent trial point which is not broken so the test is not reliable.\nRemove it as test 49 tests the same behavior is a more reliable setting.\n\nSigned-off-by: Jan Kara \n---\n t/t6030-bisect-porcelain.sh | 6 ------\n 1 file changed, 6 deletions(-)\n\ndiff --git a/t/t6030-bisect-porcelain.sh b/t/t6030-bisect-porcelain.sh\nindex 0f2a91996393..4ec7b5b5a72e 100755\n--- a/t/t6030-bisect-porcelain.sh\n+++ b/t/t6030-bisect-porcelain.sh\n@@ -675,12 +675,6 @@ cat > expected.missing-tree.default <error.txt &&\n-\ttest_cmp expected.missing-tree.default error.txt\n-'\n-\n test_expect_success 'bisect fails if tree is broken on trial commit' '\n \tgit bisect reset &&\n \ttest_must_fail git bisect start BROKEN_HASH9 BROKEN_HASH4 2>error.txt &&\n-- \n2.26.2\n\n"},{"id":"441635","messageId":"20211118164940.8818-17-jack@suse.cz","threadId":"56938","inReplyTo":"20211118164940.8818-1-jack@suse.cz","subject":"[PATCH 16/27] bisect: Separate commit list reversal","fromName":"Jan Kara","fromEmail":"jack@suse.cz","sentAt":"2021-11-18T16:49:29Z","receivedAt":"2021-11-18T16:50:22Z","isPatch":true,"sender":{"key":"jack@suse.cz","avatar":null},"body":"Item list reversal is part of code counting number of list items\nchanging tree. Move it into the separate function and do the reversal\nafter counting. The stochastic bisection will need to do more operations\nafter the counting but before reversing the list.\n\nSigned-off-by: Jan Kara \n---\n bisect.c | 29 +++++++++++++++++++++--------\n 1 file changed, 21 insertions(+), 8 deletions(-)\n\ndiff --git a/bisect.c b/bisect.c\nindex 675e8d433760..8dc1eb7f9d82 100644\n--- a/bisect.c\n+++ b/bisect.c\n@@ -398,11 +398,24 @@ static struct commit_list *do_find_bisection(struct commit_list *list,\n \t\treturn best_bisection_sorted(list, nr);\n }\n \n+\n+static struct commit_list *reverse_list(struct commit_list *list)\n+{\n+\tstruct commit_list *p, *next, *last = NULL;\n+\n+\tfor (p = list; p; p = next) {\n+\t\tnext = p->next;\n+\t\tp->next = last;\n+\t\tlast = p;\n+\t}\n+\treturn last;\n+}\n+\n void find_bisection(struct commit_list **commit_list, int *reaches,\n \t\t int *all, unsigned bisect_flags)\n {\n \tint nr, on_list;\n-\tstruct commit_list *list, *p, *best, *next, *last;\n+\tstruct commit_list *list, *p, *best, *next, **pnext;\n \tint *weights;\n \n \tinit_commit_weight(&commit_weight);\n@@ -410,25 +423,25 @@ void find_bisection(struct commit_list **commit_list, int *reaches,\n \n \t/*\n \t * Count the number of total and tree-changing items on the\n-\t * list, while reversing the list.\n+\t * list and trim uninteresting items from the list.\n \t */\n-\tfor (nr = on_list = 0, last = NULL, p = *commit_list;\n-\t p;\n-\t p = next) {\n+\tlist = *commit_list;\n+\tpnext = &list;\n+\tfor (nr = on_list = 0, p = list; p; p = next) {\n \t\tunsigned commit_flags = p->item->object.flags;\n \n \t\tnext = p->next;\n \t\tif (commit_flags & UNINTERESTING) {\n+\t\t\t*pnext = next;\n \t\t\tfree(p);\n \t\t\tcontinue;\n \t\t}\n-\t\tp->next = last;\n-\t\tlast = p;\n+\t\tpnext = &p->next;\n \t\tif (!(commit_flags & TREESAME))\n \t\t\tnr++;\n \t\ton_list++;\n \t}\n-\tlist = last;\n+\tlist = reverse_list(list);\n \tshow_list(\"bisection 2 sorted\", 0, nr, list);\n \n \t*all = nr;\n-- \n2.26.2\n\n"},{"id":"441636","messageId":"20211118164940.8818-15-jack@suse.cz","threadId":"56938","inReplyTo":"20211118164940.8818-1-jack@suse.cz","subject":"[PATCH 14/27] bisect: Use void * for commit_weight","fromName":"Jan Kara","fromEmail":"jack@suse.cz","sentAt":"2021-11-18T16:49:27Z","receivedAt":"2021-11-18T16:50:23Z","isPatch":true,"sender":{"key":"jack@suse.cz","avatar":null},"body":"For stochastic bisection we will need to store more information per\ncommit. Make commit_weight slab store void * instead of int * so that we\ncan reuse it for stochastic bisection as well.\n\nSigned-off-by: Jan Kara \n---\n bisect.c | 14 ++++++++++----\n 1 file changed, 10 insertions(+), 4 deletions(-)\n\ndiff --git a/bisect.c b/bisect.c\nindex f87753d0c67c..7416a57db4e3 100644\n--- a/bisect.c\n+++ b/bisect.c\n@@ -77,19 +77,25 @@ static void clear_distance(struct commit_list *list)\n \t}\n }\n \n-define_commit_slab(commit_weight, int *);\n+define_commit_slab(commit_weight, void *);\n static struct commit_weight commit_weight;\n \n #define DEBUG_BISECT 0\n \n+static inline int has_weight(struct commit_list *elem)\n+{\n+\treturn commit_weight.slab_size > 0 &&\n+\t *commit_weight_at(&commit_weight, elem->item) != NULL;\n+}\n+\n static inline int weight(struct commit_list *elem)\n {\n-\treturn **commit_weight_at(&commit_weight, elem->item);\n+\treturn *(int *)*commit_weight_at(&commit_weight, elem->item);\n }\n \n static inline void weight_set(struct commit_list *elem, int weight)\n {\n-\t**commit_weight_at(&commit_weight, elem->item) = weight;\n+\t*(int *)*commit_weight_at(&commit_weight, elem->item) = weight;\n }\n \n static int count_interesting_parents(struct commit *commit, unsigned bisect_flags)\n@@ -163,7 +169,7 @@ static void show_list(const char *debug, int counted, int nr,\n \t\t\t(commit_flags & TREESAME) ? ' ' : 'T',\n \t\t\t(commit_flags & UNINTERESTING) ? 'U' : ' ',\n \t\t\t(commit_flags & COUNTED) ? 'C' : ' ');\n-\t\tif (*commit_weight_at(&commit_weight, p->item))\n+\t\tif (has_weight(p))\n \t\t\tfprintf(stderr, \"%3d\", weight(p));\n \t\telse\n \t\t\tfprintf(stderr, \"---\");\n-- \n2.26.2\n\n"},{"id":"441637","messageId":"20211118164940.8818-18-jack@suse.cz","threadId":"56938","inReplyTo":"20211118164940.8818-1-jack@suse.cz","subject":"[PATCH 17/27] bisect: Allow more complex commit weights","fromName":"Jan Kara","fromEmail":"jack@suse.cz","sentAt":"2021-11-18T16:49:30Z","receivedAt":"2021-11-18T16:50:23Z","isPatch":true,"sender":{"key":"jack@suse.cz","avatar":null},"body":"For stochastic bisection we will need to keep more information for each\ncommit than plain int. Factor out initialization of commit weight\nstorage into a separate function so that stochastic bisection can more\neasily alter it.\n\nSigned-off-by: Jan Kara \n---\n bisect.c | 28 ++++++++++++++++++++--------\n 1 file changed, 20 insertions(+), 8 deletions(-)\n\ndiff --git a/bisect.c b/bisect.c\nindex 8dc1eb7f9d82..dd2f6b68ae3d 100644\n--- a/bisect.c\n+++ b/bisect.c\n@@ -280,19 +280,17 @@ static struct commit_list *best_bisection_sorted(struct commit_list *list, int n\n * or positive distance.\n */\n static struct commit_list *do_find_bisection(struct commit_list *list,\n-\t\t\t\t\t int nr, int *weights,\n-\t\t\t\t\t unsigned bisect_flags)\n+\t\t\t\t\t int nr, unsigned bisect_flags)\n {\n-\tint n, counted;\n+\tint counted;\n \tstruct commit_list *p;\n \n \tcounted = 0;\n \n-\tfor (n = 0, p = list; p; p = p->next) {\n+\tfor (p = list; p; p = p->next) {\n \t\tstruct commit *commit = p->item;\n \t\tunsigned commit_flags = commit->object.flags;\n \n-\t\t*commit_weight_at(&commit_weight, p->item) = &weights[n++];\n \t\tswitch (count_interesting_parents(commit, bisect_flags)) {\n \t\tcase 0:\n \t\t\tif (!(commit_flags & TREESAME)) {\n@@ -398,6 +396,20 @@ static struct commit_list *do_find_bisection(struct commit_list *list,\n \t\treturn best_bisection_sorted(list, nr);\n }\n \n+static void *setup_commit_weight_array(struct commit_list *list, int nodes)\n+{\n+\tint entry_size = sizeof(int);\n+\tvoid *array;\n+\tstruct commit_list *p;\n+\tint n;\n+\n+\tarray = xcalloc(nodes, entry_size);\n+\tfor (n = 0, p = list; p; p = p->next, n++) {\n+\t\t*commit_weight_at(&commit_weight, p->item) =\n+\t\t\t\t\t\tarray + n * entry_size;\n+\t}\n+\treturn array;\n+}\n \n static struct commit_list *reverse_list(struct commit_list *list)\n {\n@@ -416,7 +428,7 @@ void find_bisection(struct commit_list **commit_list, int *reaches,\n {\n \tint nr, on_list;\n \tstruct commit_list *list, *p, *best, *next, **pnext;\n-\tint *weights;\n+\tvoid *weights;\n \n \tinit_commit_weight(&commit_weight);\n \tshow_list(\"bisection 2 entry\", 0, 0, *commit_list);\n@@ -441,14 +453,14 @@ void find_bisection(struct commit_list **commit_list, int *reaches,\n \t\t\tnr++;\n \t\ton_list++;\n \t}\n+\tweights = setup_commit_weight_array(list, on_list);\n \tlist = reverse_list(list);\n \tshow_list(\"bisection 2 sorted\", 0, nr, list);\n \n \t*all = nr;\n-\tCALLOC_ARRAY(weights, on_list);\n \n \t/* Do the real work of finding bisection commit. */\n-\tbest = do_find_bisection(list, nr, weights, bisect_flags);\n+\tbest = do_find_bisection(list, nr, bisect_flags);\n \tif (best) {\n \t\tif (!(bisect_flags & FIND_BISECTION_ALL)) {\n \t\t\tlist->item = best->item;\n-- \n2.26.2\n\n"},{"id":"441638","messageId":"20211118164940.8818-19-jack@suse.cz","threadId":"56938","inReplyTo":"20211118164940.8818-1-jack@suse.cz","subject":"[PATCH 18/27] bisect: Terminate early if there are no eligible commits","fromName":"Jan Kara","fromEmail":"jack@suse.cz","sentAt":"2021-11-18T16:49:31Z","receivedAt":"2021-11-18T16:50:23Z","isPatch":true,"sender":{"key":"jack@suse.cz","avatar":null},"body":"If there are no commits that can be valid bisection point, just\nterminate search for bisection point early. Firstly, it just wastes\ntime, secondly with more complex computations for stochastic bisection\nwe would have to deal with this special corner-case unnecessarily.\n\nSigned-off-by: Jan Kara \n---\n bisect.c | 8 ++++++--\n 1 file changed, 6 insertions(+), 2 deletions(-)\n\ndiff --git a/bisect.c b/bisect.c\nindex dd2f6b68ae3d..3a26255e8650 100644\n--- a/bisect.c\n+++ b/bisect.c\n@@ -453,12 +453,15 @@ void find_bisection(struct commit_list **commit_list, int *reaches,\n \t\t\tnr++;\n \t\ton_list++;\n \t}\n+\t*all = nr;\n+\tif (!nr) {\n+\t\t*reaches = 0;\n+\t\tgoto out_weights;\n+\t}\n \tweights = setup_commit_weight_array(list, on_list);\n \tlist = reverse_list(list);\n \tshow_list(\"bisection 2 sorted\", 0, nr, list);\n \n-\t*all = nr;\n-\n \t/* Do the real work of finding bisection commit. */\n \tbest = do_find_bisection(list, nr, bisect_flags);\n \tif (best) {\n@@ -472,6 +475,7 @@ void find_bisection(struct commit_list **commit_list, int *reaches,\n \t}\n \tfree(weights);\n \t*commit_list = best;\n+out_weights:\n \tclear_commit_weight(&commit_weight);\n }\n \n-- \n2.26.2\n\n"},{"id":"441639","messageId":"20211118164940.8818-22-jack@suse.cz","threadId":"56938","inReplyTo":"20211118164940.8818-1-jack@suse.cz","subject":"[PATCH 21/27] bisect: Reorganize commit weight computation","fromName":"Jan Kara","fromEmail":"jack@suse.cz","sentAt":"2021-11-18T16:49:34Z","receivedAt":"2021-11-18T16:50:23Z","isPatch":true,"sender":{"key":"jack@suse.cz","avatar":null},"body":"Reorganize commit weight computation a bit so that it is easier to\ngeneralize for stochastic bisection. There's no real need for two\nspecial values (-1 and -2). Also we can set weight of leaf nodes while\ncomputing weight of nodes with one parent. Overall the code becomes a\nbit simpler.\n\nSigned-off-by: Jan Kara \n---\n bisect.c | 93 +++++++++++++++++++++-----------------------------------\n 1 file changed, 34 insertions(+), 59 deletions(-)\n\ndiff --git a/bisect.c b/bisect.c\nindex 680b96654fd4..4107161c086c 100644\n--- a/bisect.c\n+++ b/bisect.c\n@@ -158,17 +158,14 @@ static unsigned long sw_rev_bmp_test(struct st_weight *to, int idx)\n \t\t\t\t\t(1UL << (idx % BITS_PER_LONG));\n }\n \n-static int count_interesting_parents(struct commit *commit, unsigned bisect_flags)\n+static int count_interesting_parents(struct commit *commit)\n {\n \tstruct commit_list *p;\n \tint count;\n \n-\tfor (count = 0, p = commit->parents; p; p = p->next) {\n+\tfor (count = 0, p = commit->parents; p; p = p->next)\n \t\tif (!(p->item->object.flags & UNINTERESTING))\n \t\t\tcount++;\n-\t\tif (bisect_flags & FIND_BISECTION_FIRST_PARENT_ONLY)\n-\t\t\tbreak;\n-\t}\n \treturn count;\n }\n \n@@ -326,18 +323,14 @@ static struct commit_list *best_bisection_sorted(struct commit_list *list, int n\n \treturn list;\n }\n \n+#define WEIGHT_UNSET -1\n+\n /*\n- * zero or positive weight is the number of interesting commits it can\n+ * Zero or positive weight is the number of interesting commits it can\n * reach, including itself. Especially, weight = 0 means it does not\n * reach any tree-changing commits (e.g. just above uninteresting one\n- * but traversal is with pathspec).\n- *\n- * weight = -1 means it has one parent and its distance is yet to\n- * be computed.\n- *\n- * weight = -2 means it has more than one parent and its distance is\n- * unknown. After running count_distance() first, they will get zero\n- * or positive distance.\n+ * but traversal is with pathspec). We initialize weights to a special value\n+ * WEIGHT_UNSET to identify commits for which we didn't compute weight yet.\n */\n static struct commit_list *do_find_bisection(struct commit_list *list,\n \t\t\t\t\t int nr, unsigned bisect_flags)\n@@ -346,32 +339,8 @@ static struct commit_list *do_find_bisection(struct commit_list *list,\n \tstruct commit_list *p;\n \n \tcounted = 0;\n-\n-\tfor (p = list; p; p = p->next) {\n-\t\tstruct commit *commit = p->item;\n-\t\tunsigned commit_flags = commit->object.flags;\n-\n-\t\tswitch (count_interesting_parents(commit, bisect_flags)) {\n-\t\tcase 0:\n-\t\t\tif (!(commit_flags & TREESAME)) {\n-\t\t\t\tweight_set(p, 1);\n-\t\t\t\tcounted++;\n-\t\t\t\tshow_list(\"bisection 2 count one\",\n-\t\t\t\t\t counted, nr, list);\n-\t\t\t}\n-\t\t\t/*\n-\t\t\t * otherwise, it is known not to reach any\n-\t\t\t * tree-changing commit and gets weight 0.\n-\t\t\t */\n-\t\t\tbreak;\n-\t\tcase 1:\n-\t\t\tweight_set(p, -1);\n-\t\t\tbreak;\n-\t\tdefault:\n-\t\t\tweight_set(p, -2);\n-\t\t\tbreak;\n-\t\t}\n-\t}\n+\tfor (p = list; p; p = p->next)\n+\t\tweight_set(p, WEIGHT_UNSET);\n \n \tshow_list(\"bisection 2 initialize\", counted, nr, list);\n \n@@ -389,21 +358,21 @@ static struct commit_list *do_find_bisection(struct commit_list *list,\n \t * So we will first count distance of merges the usual\n \t * way, and then fill the blanks using cheaper algorithm.\n \t */\n-\tfor (p = list; p; p = p->next) {\n-\t\tif (p->item->object.flags & UNINTERESTING)\n-\t\t\tcontinue;\n-\t\tif (weight(p) != -2)\n-\t\t\tcontinue;\n-\t\tif (bisect_flags & FIND_BISECTION_FIRST_PARENT_ONLY)\n-\t\t\tBUG(\"shouldn't be calling count-distance in fp mode\");\n-\t\tweight_set(p, count_distance(p));\n-\t\tclear_counted_flag(list);\n+\tif (!(bisect_flags & FIND_BISECTION_FIRST_PARENT_ONLY)) {\n+\t\tfor (p = list; p; p = p->next) {\n+\t\t\tif (p->item->object.flags & UNINTERESTING)\n+\t\t\t\tcontinue;\n+\t\t\tif (count_interesting_parents(p->item) <= 1)\n+\t\t\t\tcontinue;\n+\t\t\tweight_set(p, count_distance(p));\n+\t\t\tclear_counted_flag(list);\n \n-\t\t/* Does it happen to be at half-way? */\n-\t\tif (!(bisect_flags & FIND_BISECTION_ALL) &&\n-\t\t approx_halfway(p, nr))\n-\t\t\treturn p;\n-\t\tcounted++;\n+\t\t\t/* Does it happen to be at half-way? */\n+\t\t\tif (!(bisect_flags & FIND_BISECTION_ALL) &&\n+\t\t\t approx_halfway(p, nr))\n+\t\t\t\treturn p;\n+\t\t\tcounted++;\n+\t\t}\n \t}\n \n \tshow_list(\"bisection 2 count_distance\", counted, nr, list);\n@@ -412,8 +381,9 @@ static struct commit_list *do_find_bisection(struct commit_list *list,\n \t\tfor (p = list; p; p = p->next) {\n \t\t\tstruct commit_list *q;\n \t\t\tunsigned commit_flags = p->item->object.flags;\n+\t\t\tint parent_weight = 0;\n \n-\t\t\tif (0 <= weight(p))\n+\t\t\tif (weight(p) != WEIGHT_UNSET)\n \t\t\t\tcontinue;\n \n \t\t\tfor (q = p->item->parents;\n@@ -421,10 +391,15 @@ static struct commit_list *do_find_bisection(struct commit_list *list,\n \t\t\t q = bisect_flags & FIND_BISECTION_FIRST_PARENT_ONLY ? NULL : q->next) {\n \t\t\t\tif (q->item->object.flags & UNINTERESTING)\n \t\t\t\t\tcontinue;\n-\t\t\t\tif (0 <= weight(q))\n+\t\t\t\tparent_weight = weight(q);\n+\t\t\t\tif (parent_weight != WEIGHT_UNSET)\n \t\t\t\t\tbreak;\n \t\t\t}\n-\t\t\tif (!q)\n+\t\t\t/*\n+\t\t\t * Only parent with unset weight? We need to compute\n+\t\t\t * other weights first.\n+\t\t\t */\n+\t\t\tif (parent_weight == WEIGHT_UNSET)\n \t\t\t\tcontinue;\n \n \t\t\t/*\n@@ -433,13 +408,13 @@ static struct commit_list *do_find_bisection(struct commit_list *list,\n \t\t\t * otherwise inherit it from q directly.\n \t\t\t */\n \t\t\tif (!(commit_flags & TREESAME)) {\n-\t\t\t\tweight_set(p, weight(q)+1);\n+\t\t\t\tweight_set(p, parent_weight + 1);\n \t\t\t\tcounted++;\n \t\t\t\tshow_list(\"bisection 2 count one\",\n \t\t\t\t\t counted, nr, list);\n \t\t\t}\n \t\t\telse\n-\t\t\t\tweight_set(p, weight(q));\n+\t\t\t\tweight_set(p, parent_weight);\n \n \t\t\t/* Does it happen to be at half-way? */\n \t\t\tif (!(bisect_flags & FIND_BISECTION_ALL) &&\n-- \n2.26.2\n\n"},{"id":"441640","messageId":"20211118164940.8818-13-jack@suse.cz","threadId":"56938","inReplyTo":"20211118164940.8818-1-jack@suse.cz","subject":"[PATCH 12/27] bisect: Accept and store confidence with each decision","fromName":"Jan Kara","fromEmail":"jack@suse.cz","sentAt":"2021-11-18T16:49:25Z","receivedAt":"2021-11-18T16:50:23Z","isPatch":true,"sender":{"key":"jack@suse.cz","avatar":null},"body":"With each decision whether a commit is good or bad, accept an optional\nconfidence argument and store it in bisect log and special file with\nprobabilities a test is recording a 'bad' result. We will later use\nthese probabilities to alter decisions about the next bisection point.\n\nSigned-off-by: Jan Kara \n---\n bisect.c | 51 ++++++++++++++++\n builtin/bisect--helper.c | 129 ++++++++++++++++++++++++++++++++-------\n fixedpoint.h | 29 +++++++++\n 3 files changed, 186 insertions(+), 23 deletions(-)\n create mode 100644 fixedpoint.h\n\ndiff --git a/bisect.c b/bisect.c\nindex ab264b8ca879..0773a872c82b 100644\n--- a/bisect.c\n+++ b/bisect.c\n@@ -16,8 +16,10 @@\n #include \"commit-reach.h\"\n #include \"object-store.h\"\n #include \"dir.h\"\n+#include \"fixedpoint.h\"\n \n static struct oid_array good_revs;\n+static struct oid_array ptest_revs;\n static struct oid_array skipped_revs;\n \n static struct object_id *current_bad_oid;\n@@ -444,12 +446,17 @@ static int register_ref(const char *refname, const struct object_id *oid,\n \t\t\tint flags, void *cb_data)\n {\n \tstruct strbuf good_prefix = STRBUF_INIT;\n+\tstruct strbuf ptest_prefix = STRBUF_INIT;\n+\n \tstrbuf_addstr(&good_prefix, term_good);\n \tstrbuf_addstr(&good_prefix, \"-\");\n+\tstrbuf_addstr(&ptest_prefix, \"ptest-\");\n \n \tif (!strcmp(refname, term_bad)) {\n \t\tcurrent_bad_oid = xmalloc(sizeof(*current_bad_oid));\n \t\toidcpy(current_bad_oid, oid);\n+\t} else if (starts_with(refname, ptest_prefix.buf)) {\n+\t\toid_array_append(&ptest_revs, oid);\n \t} else if (starts_with(refname, good_prefix.buf)) {\n \t\toid_array_append(&good_revs, oid);\n \t} else if (starts_with(refname, \"skip-\")) {\n@@ -474,8 +481,46 @@ static GIT_PATH_FUNC(git_path_bisect_start, \"BISECT_START\")\n static GIT_PATH_FUNC(git_path_bisect_log, \"BISECT_LOG\")\n static GIT_PATH_FUNC(git_path_bisect_terms, \"BISECT_TERMS\")\n static GIT_PATH_FUNC(git_path_bisect_first_parent, \"BISECT_FIRST_PARENT\")\n+static GIT_PATH_FUNC(git_path_bisect_confidences, \"BISECT_CONFIDENCES\")\n static GIT_PATH_FUNC(git_path_head_name, \"head-name\")\n \n+static void read_bisect_confidences(void)\n+{\n+\tstruct strbuf str = STRBUF_INIT;\n+\tconst char *filename = git_path_bisect_confidences();\n+\tFILE *fp = fopen(filename, \"r\");\n+\n+\t/* Just a regular bisection? */\n+\tif (!fp)\n+\t\treturn;\n+\n+\twhile (strbuf_getline_lf(&str, fp) != EOF) {\n+\t\tfpnum_t prob;\n+\t\tchar *spc;\n+\t\tchar state;\n+\t\tstruct object_id oid;\n+\n+\t\tstrbuf_trim(&str);\n+\t\tspc = strchr(str.buf, ' ');\n+\t\tif (!spc)\n+\t\t\tdie(_(\"Badly formatted content in file '%s': %s\"),\n+\t\t\t filename, str.buf);\n+\t\t*spc = 0;\n+\t\tif (sscanf(spc + 1, \"%c %\" FPNUM_FMT, &state, &prob) != 2)\n+\t\t\tdie(_(\"Cannot parse confidence in file '%s': %s\"),\n+\t\t\t filename, spc+1);\n+\t\tif (state != 'g' && state != 'b')\n+\t\t\tdie(_(\"Unknown test state in file '%s': '%c'\"),\n+\t\t\t filename, state);\n+\t\tif (get_oid(str.buf, &oid))\n+\t\t\tdie(_(\"Cannot get oid of rev '%s' from file '%s'\"),\n+\t\t\t str.buf, filename);\n+\t\t/* We'll use parsed data later */\n+\t}\n+\tstrbuf_release(&str);\n+\tfclose(fp);\n+}\n+\n static void read_bisect_paths(struct strvec *array)\n {\n \tstruct strbuf str = STRBUF_INIT;\n@@ -661,6 +706,10 @@ static void bisect_rev_setup(struct repository *r, struct rev_info *revs,\n \n \t/* rev_argv.argv[0] will be ignored by setup_revisions */\n \tstrvec_push(&rev_argv, \"bisect_rev_setup\");\n+\t/*\n+\t * We use only revision certainly known to be good or bad for limiting\n+\t * a search.\n+\t */\n \tstrvec_pushf(&rev_argv, bad_format, oid_to_hex(current_bad_oid));\n \tfor (i = 0; i < good_revs.nr; i++)\n \t\tstrvec_pushf(&rev_argv, good_format,\n@@ -1023,6 +1072,7 @@ enum bisect_error bisect_next_all(struct repository *r, const char *prefix)\n \tread_bisect_terms(&term_bad, &term_good);\n \tif (read_bisect_refs())\n \t\tdie(_(\"reading bisect refs failed\"));\n+\tread_bisect_confidences();\n \n \tif (file_exists(git_path_bisect_first_parent()))\n \t\tbisect_flags |= FIND_BISECTION_FIRST_PARENT_ONLY;\n@@ -1172,6 +1222,7 @@ int bisect_clean_state(void)\n \tunlink_or_warn(git_path_bisect_run());\n \tunlink_or_warn(git_path_bisect_terms());\n \tunlink_or_warn(git_path_bisect_first_parent());\n+\tunlink_or_warn(git_path_bisect_confidences());\n \t/* Cleanup head-name if it got left by an old version of git-bisect */\n \tunlink_or_warn(git_path_head_name());\n \t/*\ndiff --git a/builtin/bisect--helper.c b/builtin/bisect--helper.c\nindex 28a2e6a5750b..f88feb8da949 100644\n--- a/builtin/bisect--helper.c\n+++ b/builtin/bisect--helper.c\n@@ -9,6 +9,7 @@\n #include \"prompt.h\"\n #include \"quote.h\"\n #include \"revision.h\"\n+#include \"fixedpoint.h\"\n \n static GIT_PATH_FUNC(git_path_bisect_terms, \"BISECT_TERMS\")\n static GIT_PATH_FUNC(git_path_bisect_expected_rev, \"BISECT_EXPECTED_REV\")\n@@ -19,6 +20,7 @@ static GIT_PATH_FUNC(git_path_head_name, \"head-name\")\n static GIT_PATH_FUNC(git_path_bisect_names, \"BISECT_NAMES\")\n static GIT_PATH_FUNC(git_path_bisect_first_parent, \"BISECT_FIRST_PARENT\")\n static GIT_PATH_FUNC(git_path_bisect_run, \"BISECT_RUN\")\n+static GIT_PATH_FUNC(git_path_bisect_confidences, \"BISECT_CONFIDENCES\")\n \n static const char * const git_bisect_helper_usage[] = {\n \tN_(\"git bisect--helper --bisect-reset []\"),\n@@ -26,8 +28,8 @@ static const char * const git_bisect_helper_usage[] = {\n \tN_(\"git bisect--helper --bisect-start [--term-{new,bad}= --term-{old,good}=]\"\n \t\t\t\t\t \" [--no-checkout] [--first-parent] [ [...]] [--] [...]\"),\n \tN_(\"git bisect--helper --bisect-next\"),\n-\tN_(\"git bisect--helper --bisect-state (bad|new) []\"),\n-\tN_(\"git bisect--helper --bisect-state (good|old) [...]\"),\n+\tN_(\"git bisect--helper --bisect-state (bad|new) [--confidence ] []\"),\n+\tN_(\"git bisect--helper --bisect-state (good|old) [--confidence ] [...]\"),\n \tN_(\"git bisect--helper --bisect-replay \"),\n \tN_(\"git bisect--helper --bisect-skip [(|)...]\"),\n \tN_(\"git bisect--helper --bisect-visualize\"),\n@@ -254,18 +256,24 @@ static void log_commit(FILE *fp, char *fmt, const char *state,\n \tfree(label);\n }\n \n-static int bisect_write(const char *state, const char *rev,\n+static int bisect_write(const char *state, const char *rev, fpnum_t confidence,\n \t\t\tconst struct bisect_terms *terms, int nolog)\n {\n+\tconst char *logstate = state;\n \tstruct strbuf tag = STRBUF_INIT;\n \tstruct object_id oid;\n \tstruct commit *commit;\n \tFILE *fp = NULL;\n \tint res = 0;\n \n+\t/* Uncertain result? */\n+\tif (one_of(state, terms->term_bad, terms->term_good, NULL) &&\n+\t confidence != FP_ONE)\n+\t\tstate = \"ptest\";\n+\n \tif (!strcmp(state, terms->term_bad)) {\n \t\tstrbuf_addf(&tag, \"refs/bisect/%s\", state);\n-\t} else if (one_of(state, terms->term_good, \"skip\", NULL)) {\n+\t} else if (one_of(state, terms->term_good, \"skip\", \"ptest\", NULL)) {\n \t\tstrbuf_addf(&tag, \"refs/bisect/%s-%s\", state, rev);\n \t} else {\n \t\tres = error(_(\"Bad bisect_write argument: %s\"), state);\n@@ -283,6 +291,24 @@ static int bisect_write(const char *state, const char *rev,\n \t\tgoto finish;\n \t}\n \n+\t/* Store confidence if it is non-trivial */\n+\tif (!strcmp(state, \"ptest\")) {\n+\t\tchar cstate;\n+\n+\t\tfp = fopen(git_path_bisect_confidences(), \"a\");\n+\t\tif (!fp) {\n+\t\t\tres = error_errno(_(\"couldn't open the file '%s'\"),\n+\t\t\t\tgit_path_bisect_confidences());\n+\t\t\tgoto finish;\n+\t\t}\n+\t\tif (!strcmp(logstate, terms->term_bad))\n+\t\t\tcstate = 'b';\n+\t\telse\n+\t\t\tcstate = 'g';\n+\t\tfprintf(fp, \"%s %c %\" FPNUM_FMT \"\\n\", rev, cstate, confidence);\n+\t\tfclose(fp);\n+\t}\n+\n \tfp = fopen(git_path_bisect_log(), \"a\");\n \tif (!fp) {\n \t\tres = error_errno(_(\"couldn't open the file '%s'\"), git_path_bisect_log());\n@@ -290,10 +316,16 @@ static int bisect_write(const char *state, const char *rev,\n \t}\n \n \tcommit = lookup_commit_reference(the_repository, &oid);\n-\tlog_commit(fp, \"%s\", state, commit);\n+\tlog_commit(fp, \"%s\", logstate, commit);\n \n-\tif (!nolog)\n-\t\tfprintf(fp, \"git bisect %s %s\\n\", state, rev);\n+\tif (!nolog) {\n+\t\tif (!strcmp(state, \"ptest\")) {\n+\t\t\tfprintf(fp, \"git bisect %s --confidence %lf %s\\n\",\n+\t\t\t\tlogstate, fp_to_double(confidence), rev);\n+\t\t} else {\n+\t\t\tfprintf(fp, \"git bisect %s %s\\n\", logstate, rev);\n+\t\t}\n+\t}\n \n finish:\n \tif (fp)\n@@ -612,6 +644,16 @@ static enum bisect_error bisect_auto_next(struct bisect_terms *terms, const char\n \treturn bisect_next(terms, prefix);\n }\n \n+static int parse_confidence(const char *str, fpnum_t *confidence)\n+{\n+\tdouble confd;\n+\n+\tif (sscanf(str, \"%lf\", &confd) != 1 || confd < 0 || confd > 1)\n+\t\treturn error(_(\"invalid confidence '%s'\"), str);\n+\t*confidence = double_to_fp(confd);\n+\treturn 0;\n+}\n+\n static enum bisect_error bisect_start(struct bisect_terms *terms, const char **argv, int argc)\n {\n \tint no_checkout = 0;\n@@ -784,8 +826,8 @@ static enum bisect_error bisect_start(struct bisect_terms *terms, const char **a\n \twrite_file(git_path_bisect_names(), \"%s\\n\", bisect_names.buf);\n \n \tfor (i = 0; i < states.nr; i++)\n-\t\tif (bisect_write(states.items[i].string,\n-\t\t\t\t revs.items[i].string, terms, 1)) {\n+\t\tif (bisect_write(states.items[i].string, revs.items[i].string,\n+\t\t FP_ONE, terms, 1)) {\n \t\t\tres = BISECT_FAILED;\n \t\t\tgoto finish;\n \t\t}\n@@ -854,6 +896,7 @@ static enum bisect_error bisect_state(struct bisect_terms *terms, const char **a\n \tstruct object_id oid, expected;\n \tstruct strbuf buf = STRBUF_INIT;\n \tstruct oid_array revs = OID_ARRAY_INIT;\n+\tfpnum_t confidence = FP_ONE;\n \n \tif (!argc)\n \t\treturn error(_(\"Please call `--bisect-state` with at least one argument\"));\n@@ -868,6 +911,15 @@ static enum bisect_error bisect_state(struct bisect_terms *terms, const char **a\n \n \targv++;\n \targc--;\n+\n+\tif (argc > 0 && !strcmp(argv[0], \"--confidence\")) {\n+\t\tif (argc < 2)\n+\t\t\treturn error(_(\"missing confidence argument\"));\n+\t\tif (parse_confidence(argv[1], &confidence))\n+\t\t\treturn -1;\n+\t\targv += 2;\n+\t\targc -= 2;\n+\t}\n \tif (argc > 1 && !strcmp(state, terms->term_bad))\n \t\treturn error(_(\"'git bisect %s' can take only one argument.\"), terms->term_bad);\n \n@@ -912,7 +964,8 @@ static enum bisect_error bisect_state(struct bisect_terms *terms, const char **a\n \tstrbuf_release(&buf);\n \n \tfor (i = 0; i < revs.nr; i++) {\n-\t\tif (bisect_write(state, oid_to_hex(&revs.oid[i]), terms, 0)) {\n+\t\tif (bisect_write(state, oid_to_hex(&revs.oid[i]), confidence,\n+\t\t\t\t terms, 0)) {\n \t\t\toid_array_clear(&revs);\n \t\t\treturn BISECT_FAILED;\n \t\t}\n@@ -946,39 +999,69 @@ static enum bisect_error bisect_log(void)\n \n static int process_replay_line(struct bisect_terms *terms, struct strbuf *line)\n {\n-\tconst char *p = line->buf + strspn(line->buf, \" \\t\");\n-\tchar *word_end, *rev;\n+\tchar *p = line->buf + strspn(line->buf, \" \\t\");\n+\tchar *word_end, *cmd;\n \n-\tif ((!skip_prefix(p, \"git bisect\", &p) &&\n-\t!skip_prefix(p, \"git-bisect\", &p)) || !isspace(*p))\n+\tif ((!skip_prefix(p, \"git bisect\", (const char **)&p) &&\n+\t!skip_prefix(p, \"git-bisect\", (const char **)&p)) || !isspace(*p))\n \t\treturn 0;\n \tp += strspn(p, \" \\t\");\n \n+\tcmd = p;\n \tword_end = (char *)p + strcspn(p, \" \\t\");\n-\trev = word_end + strspn(word_end, \" \\t\");\n+\tp = word_end + strspn(word_end, \" \\t\");\n \t*word_end = '\\0'; /* NUL-terminate the word */\n \n \tget_terms(terms);\n-\tif (check_and_set_terms(terms, p))\n+\tif (check_and_set_terms(terms, cmd))\n \t\treturn -1;\n \n-\tif (!strcmp(p, \"start\")) {\n+\tif (!strcmp(cmd, \"start\")) {\n \t\tstruct strvec argv = STRVEC_INIT;\n \t\tint res;\n-\t\tsq_dequote_to_strvec(rev, &argv);\n+\t\tsq_dequote_to_strvec(p, &argv);\n \t\tres = bisect_start(terms, argv.v, argv.nr);\n \t\tstrvec_clear(&argv);\n \t\treturn res;\n \t}\n \n-\tif (one_of(p, terms->term_good,\n-\t terms->term_bad, \"skip\", NULL))\n-\t\treturn bisect_write(p, rev, terms, 0);\n+\tif (one_of(cmd, terms->term_good,\n+\t terms->term_bad, \"skip\", NULL)) {\n+\t\tfpnum_t confidence = FP_ONE;\n+\t\tchar *arg;\n+\n+\t\targ = p;\n+\t\tword_end = (char *)p + strcspn(p, \" \\t\");\n+\t\tp = word_end + strspn(word_end, \" \\t\");\n+\t\t*word_end = '\\0';\n+\t\tif (!strcmp(arg, \"--confidence\")) {\n+\t\t\tif (!strcmp(cmd, \"skip\")) {\n+\t\t\t\terror(_(\"skipping does not take confidence\"));\n+\t\t\t\treturn -1;\n+\t\t\t}\n+\t\t\tif (!*p) {\n+\t\t\t\terror(_(\"missing bisect confidence argument\"));\n+\t\t\t\treturn -1;\n+\t\t\t}\n+\t\t\targ = p;\n+\t\t\tword_end = (char *)p + strcspn(p, \" \\t\");\n+\t\t\tp = word_end + strspn(word_end, \" \\t\");\n+\t\t\t*word_end = '\\0';\n+\t\t\tif (parse_confidence(arg, &confidence))\n+\t\t\t\treturn -1;\n+\t\t\targ = p;\n+\t\t}\n+\t\tif (!*arg) {\n+\t\t\terror(_(\"missing bisect revision\"));\n+\t\t\treturn -1;\n+\t\t}\n+\t\treturn bisect_write(cmd, arg, confidence, terms, 0);\n+\t}\n \n-\tif (!strcmp(p, \"terms\")) {\n+\tif (!strcmp(cmd, \"terms\")) {\n \t\tstruct strvec argv = STRVEC_INIT;\n \t\tint res;\n-\t\tsq_dequote_to_strvec(rev, &argv);\n+\t\tsq_dequote_to_strvec(p, &argv);\n \t\tres = bisect_terms(terms, argv.nr == 1 ? argv.v[0] : NULL);\n \t\tstrvec_clear(&argv);\n \t\treturn res;\ndiff --git a/fixedpoint.h b/fixedpoint.h\nnew file mode 100644\nindex 000000000000..addef223be2b\n--- /dev/null\n+++ b/fixedpoint.h\n@@ -0,0 +1,29 @@\n+#ifndef FIXEDPOINT_H\n+#define FIXEDPOINT_H\n+\n+#include \n+\n+#define FIXEDPOINT_SHIFT 32\n+\n+typedef uint64_t fpnum_t;\n+\n+#define FPNUM_FMT PRIu64\n+\n+static inline const fpnum_t frac_to_fp(unsigned int n, unsigned int d)\n+{\n+\treturn (((fpnum_t)n) << FIXEDPOINT_SHIFT) / d;\n+}\n+\n+static inline const fpnum_t double_to_fp(double n)\n+{\n+\treturn (n * (1ULL << FIXEDPOINT_SHIFT));\n+}\n+\n+static inline const double fp_to_double(fpnum_t n)\n+{\n+\treturn ((double)n) / (1ULL << FIXEDPOINT_SHIFT);\n+}\n+\n+#define FP_ONE frac_to_fp(1, 1)\n+\n+#endif\n-- \n2.26.2\n\n"},{"id":"441641","messageId":"20211118164940.8818-25-jack@suse.cz","threadId":"56938","inReplyTo":"20211118164940.8818-1-jack@suse.cz","subject":"[PATCH 24/27] bisect: Stop bisection when we are confident about bad commit","fromName":"Jan Kara","fromEmail":"jack@suse.cz","sentAt":"2021-11-18T16:49:37Z","receivedAt":"2021-11-18T16:50:23Z","isPatch":true,"sender":{"key":"jack@suse.cz","avatar":null},"body":"When we found a commit that has high enough probability of being bad,\nstop bisection and report it.\n\nSigned-off-by: Jan Kara \n---\n bisect.c | 18 +++++++++++++++---\n 1 file changed, 15 insertions(+), 3 deletions(-)\n\ndiff --git a/bisect.c b/bisect.c\nindex 12b027b86e75..7da74778d780 100644\n--- a/bisect.c\n+++ b/bisect.c\n@@ -624,7 +624,7 @@ static int sw_rev_bmp_cmp(const void *data, const struct hashmap_entry *ap,\n * Compute for each commit a probability it is the bad one given tests\n * performed so far.\n */\n-static void compute_commit_weights(struct commit_list *list)\n+static struct commit_list *compute_commit_weights(struct commit_list *list)\n {\n \tstruct commit_list *p;\n \tstruct hashmap reach_map;\n@@ -714,9 +714,14 @@ static void compute_commit_weights(struct commit_list *list)\n \t\tfound_entry = hashmap_get_entry(&reach_map, &entry, entry, NULL);\n \t\tpweight->node_weight =\n \t\t\tfound_entry->cluster_p_bad / found_entry->count;\n+\t\t/* Found node we are confident enough is bad? */\n+\t\tif (pweight->node_weight >= result_confidence)\n+\t\t\tbreak;\n \t}\n \n \thashmap_clear_and_free(&reach_map, struct sw_rev_bmp_hash_entry, entry);\n+\n+\treturn p;\n }\n \n void find_bisection(struct commit_list **commit_list, int *reaches,\n@@ -758,14 +763,21 @@ void find_bisection(struct commit_list **commit_list, int *reaches,\n \tif (result_confidence)\n \t\tcompute_tested_descendants(list);\n \tlist = reverse_list(list);\n-\tif (result_confidence)\n-\t\tcompute_commit_weights(list);\n+\tif (result_confidence) {\n+\t\tbest = compute_commit_weights(list);\n+\t\t/* Found commit we are confident is bad? Stop bisection... */\n+\t\tif (best) {\n+\t\t\toidcpy(current_bad_oid, &best->item->object.oid);\n+\t\t\tgoto found_best;\n+\t\t}\n+\t}\n \tshow_list(\"bisection 2 sorted\", 0, nr, list);\n \n \t/* Do the real work of finding bisection commit. */\n \tbest = do_find_bisection(list, nr, bisect_flags);\n \tif (best) {\n \t\tif (!(bisect_flags & FIND_BISECTION_ALL)) {\n+found_best:\n \t\t\tlist->item = best->item;\n \t\t\tfree_commit_list(list->next);\n \t\t\tbest = list;\n-- \n2.26.2\n\n"},{"id":"441642","messageId":"20211118164940.8818-27-jack@suse.cz","threadId":"56938","inReplyTo":"20211118164940.8818-1-jack@suse.cz","subject":"[PATCH 26/27] bisect: Debug stochastic bisection","fromName":"Jan Kara","fromEmail":"jack@suse.cz","sentAt":"2021-11-18T16:49:39Z","receivedAt":"2021-11-18T16:52:13Z","isPatch":true,"sender":{"key":"jack@suse.cz","avatar":null},"body":"Add debug prints for debugging stochastic bisection.\n\nSigned-off-by: Jan Kara \n---\n bisect.c | 56 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n 1 file changed, 56 insertions(+)\n\ndiff --git a/bisect.c b/bisect.c\nindex 6ed740106795..4d2ba5dbd77e 100644\n--- a/bisect.c\n+++ b/bisect.c\n@@ -620,6 +620,21 @@ static int sw_rev_bmp_cmp(const void *data, const struct hashmap_entry *ap,\n \treturn 0;\n }\n \n+static void show_cluster(struct sw_rev_bmp_hash_entry *entry)\n+{\n+\tint i;\n+\n+\tif (!DEBUG_BISECT)\n+\t\treturn;\n+\n+\tfprintf(stderr, \"cluster prob %\"FPNUM_FMT\" members %u reaching revs \",\n+\t\tentry->cluster_p_bad, entry->count);\n+\tfor (i = 0; i < ptest_revs.nr; i++)\n+\t\tif (sw_rev_bmp_test(entry->commit_weight, i))\n+\t\t\tfprintf(stderr, \"%.8s \", oid_to_hex(ptest_revs.oid + i));\n+\tfprintf(stderr, \"\\n\");\n+}\n+\n /*\n * Compute for each commit a probability it is the bad one given tests\n * performed so far.\n@@ -697,6 +712,7 @@ static struct commit_list *compute_commit_weights(struct commit_list *list)\n \thashmap_for_each_entry(&reach_map, &reach_iter, found_entry, entry) {\n \t\tfound_entry->cluster_p_bad = fp_div(found_entry->cluster_p_bad,\n \t\t\t\t\t\t cluster_prob_sum);\n+\t\tshow_cluster(found_entry);\n \t}\n \n \t/* Uniformly distribute the probability among all nodes of a cluster */\n@@ -1111,6 +1127,30 @@ static struct commit_list *managed_skipped(struct commit_list *list,\n \treturn skip_away(list, count);\n }\n \n+static void print_object(struct object *obj)\n+{\n+\tunsigned flags = obj->flags;\n+\n+\tfprintf(stderr, \"%c%c%c%c \",\n+\t\t(flags & TREESAME) ? ' ' : 'T',\n+\t\t(flags & UNINTERESTING) ? 'U' : ' ',\n+\t\t(flags & SEEN) ? 'S' : ' ',\n+\t\t(flags & COUNTED) ? 'C' : ' ');\n+\tfprintf(stderr, \"%.8s\\n\", oid_to_hex(&obj->oid));\n+}\n+\n+static void show_object_array(const char *str, struct object_array *array)\n+{\n+\tint i;\n+\n+\tif (!DEBUG_BISECT)\n+\t\treturn;\n+\n+\tfprintf(stderr, \"%s\\n\", str);\n+\tfor (i = 0; i < array->nr; i++)\n+\t\tprint_object(array->objects[i].item);\n+}\n+\n static void bisect_rev_setup(struct repository *r, struct rev_info *revs,\n \t\t\t const char *prefix,\n \t\t\t const char *bad_format, const char *good_format,\n@@ -1139,12 +1179,16 @@ static void bisect_rev_setup(struct repository *r, struct rev_info *revs,\n \n \tsetup_revisions(rev_argv.nr, rev_argv.v, revs, NULL);\n \t/* XXX leak rev_argv, as \"revs\" may still be pointing to it */\n+\tshow_list(\"setup_revisions commits\", 0, 0, revs->commits);\n+\tshow_object_array(\"setup_revisions pending\", &revs->pending);\n }\n \n static void bisect_common(struct rev_info *revs)\n {\n \tif (prepare_revision_walk(revs))\n \t\tdie(\"revision walk setup failed\");\n+\tshow_list(\"bisect_common commits\", 0, 0, revs->commits);\n+\tshow_object_array(\"bisect_common pending\", &revs->pending);\n \tif (revs->tree_objects)\n \t\tmark_edges_uninteresting(revs, NULL, 0);\n }\n@@ -1462,6 +1506,12 @@ void read_bisect_terms(const char **read_bad, const char **read_good)\n \tfclose(fp);\n }\n \n+static int debug_print_oid(const struct object_id *oid, void *data)\n+{\n+\tfprintf(stderr, \"%s\\n\", oid_to_hex(oid));\n+\treturn 0;\n+}\n+\n /*\n * We use the convention that return BISECT_INTERNAL_SUCCESS_1ST_BAD_FOUND (-10) means\n * the bisection process finished successfully.\n@@ -1493,6 +1543,12 @@ enum bisect_error bisect_next_all(struct repository *r, const char *prefix)\n \tif (read_bisect_refs())\n \t\tdie(_(\"reading bisect refs failed\"));\n \tread_bisect_confidences();\n+\tif (DEBUG_BISECT) {\n+\t\tdebug_bisect(\"good revs:\\n\");\n+\t\toid_array_for_each(&good_revs, debug_print_oid, NULL);\n+\t\tdebug_bisect(\"p-test revs:\\n\");\n+\t\toid_array_for_each(&ptest_revs, debug_print_oid, NULL);\n+\t}\n \n \tif (file_exists(git_path_bisect_first_parent()))\n \t\tbisect_flags |= FIND_BISECTION_FIRST_PARENT_ONLY;\n-- \n2.26.2\n\n"},{"id":"441643","messageId":"20211118164940.8818-26-jack@suse.cz","threadId":"56938","inReplyTo":"20211118164940.8818-1-jack@suse.cz","subject":"[PATCH 25/27] bisect: Report commit with the highest probability","fromName":"Jan Kara","fromEmail":"jack@suse.cz","sentAt":"2021-11-18T16:49:38Z","receivedAt":"2021-11-18T16:52:13Z","isPatch":true,"sender":{"key":"jack@suse.cz","avatar":null},"body":"For stochastic bisection it does not make sense to report number of\ncommits to investigate (since we always consider all). What we can do\nthough is to report the highest probability some commit has of being\nbad. That also indicates how far we are from the end of bisection as\nonce the probability reaches desired result confidence bisection stops.\n\nSigned-off-by: Jan Kara \n---\n bisect.c | 56 +++++++++++++++++++++++++++++++++-------------\n bisect.h | 4 +++-\n builtin/rev-list.c | 6 +++--\n 3 files changed, 48 insertions(+), 18 deletions(-)\n\ndiff --git a/bisect.c b/bisect.c\nindex 7da74778d780..6ed740106795 100644\n--- a/bisect.c\n+++ b/bisect.c\n@@ -724,7 +724,25 @@ static struct commit_list *compute_commit_weights(struct commit_list *list)\n \treturn p;\n }\n \n-void find_bisection(struct commit_list **commit_list, int *reaches,\n+static fpnum_t heaviest_commit(struct commit_list *list)\n+{\n+\tfpnum_t best_weight = 0;\n+\tstruct commit_list *p;\n+\n+\tfor (p = list; p; p = p->next) {\n+\t\tstruct st_weight *pweight;\n+\n+\t\tif (p->item->object.flags & TREESAME)\n+\t\t\tcontinue;\n+\n+\t\tpweight = *commit_weight_at(&commit_weight, p->item);\n+\t\tif (pweight->node_weight > best_weight)\n+\t\t\tbest_weight = pweight->node_weight;\n+\t}\n+\treturn best_weight;\n+}\n+\n+void find_bisection(struct commit_list **commit_list, fpnum_t *reaches,\n \t\t int *all, unsigned bisect_flags)\n {\n \tint nr, on_list;\n@@ -770,6 +788,7 @@ void find_bisection(struct commit_list **commit_list, int *reaches,\n \t\t\toidcpy(current_bad_oid, &best->item->object.oid);\n \t\t\tgoto found_best;\n \t\t}\n+\t\t*reaches = heaviest_commit(list);\n \t}\n \tshow_list(\"bisection 2 sorted\", 0, nr, list);\n \n@@ -783,7 +802,8 @@ void find_bisection(struct commit_list **commit_list, int *reaches,\n \t\t\tbest = list;\n \t\t\tbest->next = NULL;\n \t\t}\n-\t\t*reaches = fp_to_int(weight(best) * (nr / weight_scale(nr)));\n+\t\tif (!result_confidence)\n+\t\t\t*reaches = weight(best) / nr;\n \t}\n \tfree(weights);\n \t*commit_list = best;\n@@ -1457,7 +1477,8 @@ enum bisect_error bisect_next_all(struct repository *r, const char *prefix)\n {\n \tstruct rev_info revs;\n \tstruct commit_list *tried;\n-\tint reaches = 0, all = 0, nr, steps;\n+\tint all = 0, nr, steps;\n+\tfpnum_t reaches = 0;\n \tenum bisect_error res = BISECT_OK;\n \tstruct object_id *bisect_rev;\n \tchar *steps_msg;\n@@ -1536,19 +1557,24 @@ enum bisect_error bisect_next_all(struct repository *r, const char *prefix)\n \t\treturn BISECT_INTERNAL_SUCCESS_1ST_BAD_FOUND;\n \t}\n \n-\tnr = all - reaches - 1;\n-\tsteps = estimate_bisect_steps(all);\n+\tif (!result_confidence) {\n+\t\tnr = all - fp_to_int(reaches * all) - 1;\n+\t\tsteps = estimate_bisect_steps(all);\n \n-\tsteps_msg = xstrfmt(Q_(\"(roughly %d step)\", \"(roughly %d steps)\",\n-\t\t steps), steps);\n-\t/*\n-\t * TRANSLATORS: the last %s will be replaced with \"(roughly %d\n-\t * steps)\" translation.\n-\t */\n-\tprintf(Q_(\"Bisecting: %d revision left to test after this %s\\n\",\n-\t\t \"Bisecting: %d revisions left to test after this %s\\n\",\n-\t\t nr), nr, steps_msg);\n-\tfree(steps_msg);\n+\t\tsteps_msg = xstrfmt(Q_(\"(roughly %d step)\", \"(roughly %d steps)\",\n+\t\t\t steps), steps);\n+\t\t/*\n+\t\t * TRANSLATORS: the last %s will be replaced with \"(roughly %d\n+\t\t * steps)\" translation.\n+\t\t */\n+\t\tprintf(Q_(\"Bisecting: %d revision left to test after this %s\\n\",\n+\t\t\t \"Bisecting: %d revisions left to test after this %s\\n\",\n+\t\t\t nr), nr, steps_msg);\n+\t\tfree(steps_msg);\n+\t} else {\n+\t\tprintf(_(\"Bisecting: most probable commit has probability %lf\\n\"),\n+\t\t\tfp_to_double(reaches));\n+\t}\n \t/* Clean up objects used, as they will be reused. */\n \trepo_clear_commit_marks(r, ALL_REV_FLAGS);\n \ndiff --git a/bisect.h b/bisect.h\nindex ec24ac2d7ee9..d0a805b05041 100644\n--- a/bisect.h\n+++ b/bisect.h\n@@ -1,6 +1,8 @@\n #ifndef BISECT_H\n #define BISECT_H\n \n+#include \"fixedpoint.h\"\n+\n struct commit_list;\n struct repository;\n \n@@ -11,7 +13,7 @@ struct repository;\n * Otherwise, it will be either all non-SAMETREE commits or the single\n * best commit, as chosen by `find_all`.\n */\n-void find_bisection(struct commit_list **list, int *reaches, int *all,\n+void find_bisection(struct commit_list **list, fpnum_t *reaches, int *all,\n \t\t unsigned bisect_flags);\n \n struct commit_list *filter_skipped(struct commit_list *list,\ndiff --git a/builtin/rev-list.c b/builtin/rev-list.c\nindex 36cb909ebaa5..c98ac9e91688 100644\n--- a/builtin/rev-list.c\n+++ b/builtin/rev-list.c\n@@ -702,7 +702,8 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)\n \t\tmark_edges_uninteresting(&revs, show_edge, 0);\n \n \tif (bisect_list) {\n-\t\tint reaches, all;\n+\t\tint all;\n+\t\tfpnum_t reaches;\n \t\tunsigned bisect_flags = 0;\n \n \t\tif (bisect_find_all)\n@@ -714,7 +715,8 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)\n \t\tfind_bisection(&revs.commits, &reaches, &all, bisect_flags);\n \n \t\tif (bisect_show_vars)\n-\t\t\treturn show_bisect_vars(&info, reaches, all);\n+\t\t\treturn show_bisect_vars(&info, fp_to_int(reaches * all),\n+\t\t\t\t\t\tall);\n \t}\n \n \tif (filter_provided_objects) {\n-- \n2.26.2\n\n"},{"id":"441644","messageId":"20211118164940.8818-28-jack@suse.cz","threadId":"56938","inReplyTo":"20211118164940.8818-1-jack@suse.cz","subject":"[PATCH 27/27] bisect: Allow bisection debugging of approx_halfway()","fromName":"Jan Kara","fromEmail":"jack@suse.cz","sentAt":"2021-11-18T16:49:40Z","receivedAt":"2021-11-18T16:52:13Z","isPatch":true,"sender":{"key":"jack@suse.cz","avatar":null},"body":"Currently approx_halfway() is shortcircuited when bisection debugging is\nturned on. Allow possibility of printing all debug messages while\nkeeping approx_halfway() working by setting DEBUG_BISECT to 1. Disable\napprox_halfway() only when BISECT_DEBUG is larger than 1. Also add a\ndebug message to approx_halfway() to dump info about commit it is\nselecting.\n\nSigned-off-by: Jan Kara \n---\n bisect.c | 7 +++++--\n 1 file changed, 5 insertions(+), 2 deletions(-)\n\ndiff --git a/bisect.c b/bisect.c\nindex 4d2ba5dbd77e..60e8c32056ac 100644\n--- a/bisect.c\n+++ b/bisect.c\n@@ -207,7 +207,7 @@ static inline int approx_halfway(struct commit_list *p, int nr)\n \t */\n \tif (p->item->object.flags & TREESAME)\n \t\treturn 0;\n-\tif (DEBUG_BISECT)\n+\tif (DEBUG_BISECT > 1)\n \t\treturn 0;\n \n \tif (!result_confidence) {\n@@ -230,8 +230,11 @@ static inline int approx_halfway(struct commit_list *p, int nr)\n \t\tdiff = frac_to_fp(1, 16);\n \t}\n \tif (weight(p) > (FP_HALF - diff) * scale &&\n-\t weight(p) < (FP_HALF + diff) * scale)\n+\t weight(p) < (FP_HALF + diff) * scale) {\n+\t\tdebug_bisect(\"found approx half: %lf diff %lf\\n\",\n+\t\t\t fp_to_double(weight(p)), fp_to_double(diff));\n \t\treturn 1;\n+\t}\n \treturn 0;\n }\n \n-- \n2.26.2\n\n"},{"id":"441655","messageId":"CAPx1GvdKuBmxN0XM3PKJO+0V=P3OoyB4VDzmqshv7N+3vFF8gw@mail.gmail.com","threadId":"56938","inReplyTo":"20211118164940.8818-2-jack@suse.cz","subject":"Re: [PATCH 01/27] bisect: Fixup test rev-list-bisect/02","fromName":"Chris Torek","fromEmail":"chris.torek@gmail.com","sentAt":"2021-11-18T20:08:48Z","receivedAt":"2021-11-18T20:09:03Z","isPatch":true,"sender":{"key":"chris.torek@gmail.com","avatar":"https://avatars.githubusercontent.com/u/16826774?v=4"},"body":"On Thu, Nov 18, 2021 at 10:38 AM Jan Kara wrote:\n> diff --git a/t/t6002-rev-list-bisect.sh b/t/t6002-rev-list-bisect.sh\n> index b95a0212adff..48db52447fd3 100755\n> --- a/t/t6002-rev-list-bisect.sh\n> +++ b/t/t6002-rev-list-bisect.sh\n> @@ -247,8 +247,9 @@ test_expect_success 'set up fake --bisect refs' '\n> test_expect_success 'rev-list --bisect can default to good/bad refs' '\n> # the only thing between c3 and c1 is c2\n> git rev-parse c2 >expect &&\n> - git rev-list --bisect >actual &&\n> - test_cmp expect actual\n> + git rev-parse b2 >>expect &&\n> + actual=$(git rev-list --bisect) &&\n> + grep &>/dev/null $actual expect\n\n`&>` is a bashism; you need `>/dev/null 2>&1` here for general portability.\n\nChris\n\nref: https://unix.stackexchange.com/questions/581507/redirecting-stdout-and-stderr-together-vs-redirecting-stdout-and-then-stderr-to/\n"},{"id":"441656","messageId":"CAPx1Gvfe46JFeNT8nW6NcFFy7bnR+eWYKS0-5soPVTmPxxJccA@mail.gmail.com","threadId":"56938","inReplyTo":"20211118164940.8818-4-jack@suse.cz","subject":"Re: [PATCH 03/27] bisect: Fixup test bisect-porcelain/20","fromName":"Chris Torek","fromEmail":"chris.torek@gmail.com","sentAt":"2021-11-18T20:13:21Z","receivedAt":"2021-11-18T20:13:35Z","isPatch":true,"sender":{"key":"chris.torek@gmail.com","avatar":"https://avatars.githubusercontent.com/u/16826774?v=4"},"body":"On Thu, Nov 18, 2021 at 10:39 AM Jan Kara wrote:\n> diff --git a/t/t6030-bisect-porcelain.sh b/t/t6030-bisect-porcelain.sh\n> index f8cfdd3c36d2..13f7deea4d81 100755\n> --- a/t/t6030-bisect-porcelain.sh\n> +++ b/t/t6030-bisect-porcelain.sh\n> @@ -240,8 +240,13 @@ test_expect_success 'bisect skip: cannot tell between 3 commits' '\n> test_expect_success 'bisect skip: cannot tell between 2 commits' '\n> test_when_finished git bisect reset &&\n> git bisect start $HASH4 $HASH1 &&\n> - git bisect skip &&\n> - test_expect_code 2 git bisect good >my_bisect_log.txt &&\n> + if [ $(git rev-parse HEAD) == $HASH2 ]; then\n> + results=('good' 'skip')\n> + else\n> + results=('skip' 'good')\n> + fi &&\n> + git bisect ${results[0]} &&\n> + test_expect_code 2 git bisect ${results[1]} >my_bisect_log.txt &&\n\nThese are also not available in old POSIX shell - consider using two\nseparate variables to hold the two strings.\n\nChris\n"},{"id":"441664","messageId":"YZbOKgoYmeM/yLAs@nand.local","threadId":"56938","inReplyTo":"20211118164940.8818-3-jack@suse.cz","subject":"Re: [PATCH 02/27] bisect: Fixup bisect-porcelain/17","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2021-11-18T22:05:41Z","receivedAt":"2021-11-18T22:05:48Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Thu, Nov 18, 2021 at 05:49:15PM +0100, Jan Kara wrote:\n\n> Test 17 from t6030-bisect-porcelain.sh assumes that bisection algorithm\n> suggests first HASH3 where HASH2 and HASH3 are equivalent choices. Make\n> sure test correctly handles both choices, add test variant to properly\n> test commit skipping in the second case.\n\nOK, makes sense-ish: at least in the context of preparing for the\nbisection algorithm to change. The subject line leaves a bit to be\ndesired, though. Perhaps:\n\n t6030: handle equivalent bisection points gracefully\n\n> diff --git a/t/t6030-bisect-porcelain.sh b/t/t6030-bisect-porcelain.sh\n> index 1be85d064e76..f8cfdd3c36d2 100755\n> --- a/t/t6030-bisect-porcelain.sh\n> +++ b/t/t6030-bisect-porcelain.sh\n> @@ -197,11 +197,27 @@ test_expect_success 'bisect skip: successful result' '\n> \ttest_when_finished git bisect reset &&\n> \tgit bisect reset &&\n> \tgit bisect start $HASH4 $HASH1 &&\n> -\tgit bisect skip &&\n> +\tif [ $(git rev-parse HEAD) == $HASH3 ]; then\n\nThis is somewhat uncommon style for Git's test suite. It might be more\nappropriate to write instead:\n\n if test \"$HASH3\" = \"$(git rev-parse HEAD)\"\n then\n git bisect skip\n fi &&\n # ...\n\n> +# $HASH1 is good, $HASH4 is bad, we skip $HASH2\n> +# but $HASH3 is good,\n\nIt looks like this comment should have gone above the start of the test\nin the previous hunk.\n\nBut it looks like you accidentally duplicated this test in its entirety\n(with the addition of the misplaced comment) below instead.\n\nThanks,\nTaylor\n"},{"id":"441666","messageId":"YZbPY9is4+4q2rxF@nand.local","threadId":"56938","inReplyTo":"CAPx1Gvfe46JFeNT8nW6NcFFy7bnR+eWYKS0-5soPVTmPxxJccA@mail.gmail.com","subject":"Re: [PATCH 03/27] bisect: Fixup test bisect-porcelain/20","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2021-11-18T22:10:43Z","receivedAt":"2021-11-18T22:10:45Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Thu, Nov 18, 2021 at 12:13:21PM -0800, Chris Torek wrote:\n> On Thu, Nov 18, 2021 at 10:39 AM Jan Kara wrote:\n> > diff --git a/t/t6030-bisect-porcelain.sh b/t/t6030-bisect-porcelain.sh\n> > index f8cfdd3c36d2..13f7deea4d81 100755\n> > --- a/t/t6030-bisect-porcelain.sh\n> > +++ b/t/t6030-bisect-porcelain.sh\n> > @@ -240,8 +240,13 @@ test_expect_success 'bisect skip: cannot tell between 3 commits' '\n> > test_expect_success 'bisect skip: cannot tell between 2 commits' '\n> > test_when_finished git bisect reset &&\n> > git bisect start $HASH4 $HASH1 &&\n> > - git bisect skip &&\n> > - test_expect_code 2 git bisect good >my_bisect_log.txt &&\n> > + if [ $(git rev-parse HEAD) == $HASH2 ]; then\n> > + results=('good' 'skip')\n> > + else\n> > + results=('skip' 'good')\n> > + fi &&\n> > + git bisect ${results[0]} &&\n> > + test_expect_code 2 git bisect ${results[1]} >my_bisect_log.txt &&\n>\n> These are also not available in old POSIX shell - consider using two\n> separate variables to hold the two strings.\n\nOr just inlining the commands that you actually want to run inside of\nthe if statement above:\n\n if test \"$HASH2\" = \"$(git rev-parse HEAD)\n then\n git bisect good &&\n test_expect_code 2 git bisect skip >my_bisect_log.txt\n else\n git bisect skip &&\n test_expect_code 2 git bisect good >my_bisect_log.txt\n fi && #...\n\nHere (and in the previous patch) it might be helpful to add a short note\nin these conditionals, maybe along the lines of:\n\n # HASH2 and HASH3 are equivalent choices, but we only want to mark\n # HASH2 as \"good\". Handle either ordering:\n\nSame note on the brevity of the subject line applies here, too.\n\nThanks,\nTaylor\n"},{"id":"441671","messageId":"YZbYjFpA1bpeebx+@nand.local","threadId":"56938","inReplyTo":"20211118164940.8818-1-jack@suse.cz","subject":"Re: Stochastic bisection support","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2021-11-18T22:49:48Z","receivedAt":"2021-11-18T22:49:50Z","isPatch":false,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Thu, Nov 18, 2021 at 05:49:13PM +0100, Jan Kara wrote:\n\n> The first part of the series improves some tests so that they accept\n> other valid decisions for bisection points. This is needed because to\n> make it easier to share some logic between normal and stochastic\n> bisection, I needed to slightly change some bits for normal bisection\n> and then since commit weights will be computed in a somewhat different\n> order, also chosen bisection points are sometimes different.\n\nI have only looked through a couple of the first half of your patches,\nbut I'm not sure I understand why non-stochastic bisection needs to\nchange at all in order to support stochastic bisection.\n\nIn other words, if we're tweaking all of these tests to allow picking\nequivalent bisection points, why can't we simply leave them alone? It\nwould be nice if normal bisection didn't change as a result of adding a\nnew feature on top.\n\nThanks,\nTaylor\n"},{"id":"441754","messageId":"nycvar.QRO.7.76.6.2111191653390.63@tvgsbejvaqbjf.bet","threadId":"56938","inReplyTo":"CAPx1GvdKuBmxN0XM3PKJO+0V=P3OoyB4VDzmqshv7N+3vFF8gw@mail.gmail.com","subject":"Re: [PATCH 01/27] bisect: Fixup test rev-list-bisect/02","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2021-11-19T16:31:22Z","receivedAt":"2021-11-19T16:31:28Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Thu, 18 Nov 2021, Chris Torek wrote:\n\n> On Thu, Nov 18, 2021 at 10:38 AM Jan Kara wrote:\n> > diff --git a/t/t6002-rev-list-bisect.sh b/t/t6002-rev-list-bisect.sh\n> > index b95a0212adff..48db52447fd3 100755\n> > --- a/t/t6002-rev-list-bisect.sh\n> > +++ b/t/t6002-rev-list-bisect.sh\n> > @@ -247,8 +247,9 @@ test_expect_success 'set up fake --bisect refs' '\n> > test_expect_success 'rev-list --bisect can default to good/bad refs' '\n> > # the only thing between c3 and c1 is c2\n> > git rev-parse c2 >expect &&\n> > - git rev-list --bisect >actual &&\n> > - test_cmp expect actual\n> > + git rev-parse b2 >>expect &&\n> > + actual=$(git rev-list --bisect) &&\n> > + grep &>/dev/null $actual expect\n>\n> `&>` is a bashism; you need `>/dev/null 2>&1` here for general portability.\n\nMore importantly, why do you suppress the output in the first place? This\nwill make debugging breakages harder.\n\nLet's just not redirect the output?\n\nI do see a more structural problem here, though. Throughout the test\nsuite, it is our custom to generate files called `expect` with what we\nconsider the expected output, and then generate `actual` with the actual\noutput. We then compare the results and complain if they are not\nidentical.\n\nWith this patch, we break that paradigm. All of a sudden, `expect` is not\nat all the expected output anymore, but a haystack in which we want to\nfind one thing.\n\nAnd even after reading the commit message twice, I am unconvinced that b2\n(whatever that is) might be an equally good choice. I become even more\ndoubtful about that statement when I look at the code comment at the\nbeginning of the test case:\n\n\t# the only thing between c3 and c1 is c2\n\nSo either this code comment is wrong, or the patch. And if the code\ncomment is wrong, I would like to know when it became wrong, and how, and\nwhy it slipped through our review.\n\nCiao,\nDscho\n"},{"id":"441755","messageId":"nycvar.QRO.7.76.6.2111191731400.63@tvgsbejvaqbjf.bet","threadId":"56938","inReplyTo":"20211118164940.8818-1-jack@suse.cz","subject":"Re: Stochastic bisection support","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2021-11-19T16:39:35Z","receivedAt":"2021-11-19T16:39:42Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Jan,\n\nOn Thu, 18 Nov 2021, Jan Kara wrote:\n\n> In some cases regressions (or generally changes) we are trying to bisect have\n> probabilistic nature. This can for example happen for hard to trigger race\n> condition where it is difficult to distinguish working state from just not\n> hitting the race or it can happen for performance regressions where it is\n> sometimes difficult to distinguish random workload fluctuations from the\n> regression we are looking for. With standard bisection the only option we have\n> is to repeatedly test suggested bisection point until we are sure enough which\n> way to go. This leads to rather long bisection times and still a single wrong\n> decision whether a commit is good to bad renders the whole bisection useless.\n>\n> Stochastic bisection tries to address these problems. When deciding whether a\n> commit is good or bad, you can also specify your confidence in the decision.\n> For performance tests you can usually directly infer this confidence from the\n> distance of your current result from good/bad values, for hard to reproduce\n> races you are usually 100% confident for bad commits, for good commits you need\n> to somehow estimate your confidence based on past experience with reproducing\n> the issue. The stochastic bisection algorithm then uses these test results\n> and confidences to suggest next commit to try, tracking for each commit the\n> probability the commit is the bad one given current test results. Once some\n> commit reaches high enough probability (set when starting bisection) of being\n> the bad one, we stop bisecting and annouce this commit.\n\nAn interesting problem, for sure!\n\nIt is slightly related to a scenario that has been described to me\nrecently: in a gigantic project whose full test suite is too large to run\nwith every Pull Request, where tests are more likely to become flaky\nrather than simply break, a stochastic CI regime was introduced where a\nsemi-random subset of the test suite is run with every CI build. That team\nalso came up with the concept of attaching confidences as you describe.\n\nI only had time to look at the first patch closely so far. I hope to find\nmore time next week to review further.\n\nCiao,\nDscho\n"},{"id":"441841","messageId":"CAPx1GvfT36SvJ6Lwf1-2KUebVXkCkNvYTUw=FU+dHBy76VN5RQ@mail.gmail.com","threadId":"56938","inReplyTo":"nycvar.QRO.7.76.6.2111191731400.63@tvgsbejvaqbjf.bet","subject":"Re: Stochastic bisection support","fromName":"Chris Torek","fromEmail":"chris.torek@gmail.com","sentAt":"2021-11-20T07:54:12Z","receivedAt":"2021-11-20T07:54:42Z","isPatch":false,"sender":{"key":"chris.torek@gmail.com","avatar":"https://avatars.githubusercontent.com/u/16826774?v=4"},"body":"On Fri, Nov 19, 2021 at 8:51 AM Johannes Schindelin\n wrote:\n> An interesting problem, for sure!\n>\n> It is slightly related to a scenario that has been described to me\n> recently: in a gigantic project whose full test suite is too large to run\n> with every Pull Request, where tests are more likely to become flaky\n> rather than simply break, a stochastic CI regime was introduced where a\n> semi-random subset of the test suite is run with every CI build. That team\n> also came up with the concept of attaching confidences as you describe.\n>\n> I only had time to look at the first patch closely so far. I hope to find\n> more time next week to review further.\n\nI only scanned for obvious items myself, but the idea of a\nprobabilistic test is indeed interesting.\n\nI do wonder why you (Jan Kara, not Dscho :-) ) used fixed-point\narithmetic here though.\n\nChris\n"},{"id":"441930","messageId":"20211122115740.GA24453@quack2.suse.cz","threadId":"56938","inReplyTo":"CAPx1GvfT36SvJ6Lwf1-2KUebVXkCkNvYTUw=FU+dHBy76VN5RQ@mail.gmail.com","subject":"Re: Stochastic bisection support","fromName":"Jan Kara","fromEmail":"jack@suse.cz","sentAt":"2021-11-22T11:57:40Z","receivedAt":"2021-11-22T11:57:43Z","isPatch":false,"sender":{"key":"jack@suse.cz","avatar":null},"body":"On Fri 19-11-21 23:54:12, Chris Torek wrote:\n> On Fri, Nov 19, 2021 at 8:51 AM Johannes Schindelin\n> wrote:\n> > An interesting problem, for sure!\n> >\n> > It is slightly related to a scenario that has been described to me\n> > recently: in a gigantic project whose full test suite is too large to run\n> > with every Pull Request, where tests are more likely to become flaky\n> > rather than simply break, a stochastic CI regime was introduced where a\n> > semi-random subset of the test suite is run with every CI build. That team\n> > also came up with the concept of attaching confidences as you describe.\n> >\n> > I only had time to look at the first patch closely so far. I hope to find\n> > more time next week to review further.\n> \n> I only scanned for obvious items myself, but the idea of a\n> probabilistic test is indeed interesting.\n> \n> I do wonder why you (Jan Kara, not Dscho :-) ) used fixed-point\n> arithmetic here though.\n\nAh, very good question. I guess because I'm primarily Linux kernel\nprogrammer and we don't have floating point arithmetics in the kernel so\nI'm used to fixedpoint :). Secondarily because fixedpoint arithmetics\nprovides me more control over where I'm loosing precision but looking at\nthis now I agree the ugliness in the code is not probably worth the\nimagined win. I'll rewrite stuff using floating point. Thanks for the\nsuggestion.\n\n\t\t\t\t\t\t\t\tHonza\n-- \nJan Kara \nSUSE Labs, CR\n"},{"id":"441933","messageId":"20211122121307.GB24453@quack2.suse.cz","threadId":"56938","inReplyTo":"YZbYjFpA1bpeebx+@nand.local","subject":"Re: Stochastic bisection support","fromName":"Jan Kara","fromEmail":"jack@suse.cz","sentAt":"2021-11-22T12:13:07Z","receivedAt":"2021-11-22T12:13:13Z","isPatch":false,"sender":{"key":"jack@suse.cz","avatar":null},"body":"On Thu 18-11-21 17:49:48, Taylor Blau wrote:\n> On Thu, Nov 18, 2021 at 05:49:13PM +0100, Jan Kara wrote:\n> \n> > The first part of the series improves some tests so that they accept\n> > other valid decisions for bisection points. This is needed because to\n> > make it easier to share some logic between normal and stochastic\n> > bisection, I needed to slightly change some bits for normal bisection\n> > and then since commit weights will be computed in a somewhat different\n> > order, also chosen bisection points are sometimes different.\n> \n> I have only looked through a couple of the first half of your patches,\n> but I'm not sure I understand why non-stochastic bisection needs to\n> change at all in order to support stochastic bisection.\n> \n> In other words, if we're tweaking all of these tests to allow picking\n> equivalent bisection points, why can't we simply leave them alone? It\n> would be nice if normal bisection didn't change as a result of adding a\n> new feature on top.\n\nThe big part of why results for normal bisection change are the changes in\n\"bisect: Reorganize commit weight computation\" to function\ndo_find_bisection() where previously we didn't call approx_halfway() on the\ncommits at the end of chain (looks like unintended omission) while after my\nchanges we call approx_halfway() for all commits. And I have reorganized\ndo_find_bisection() because I reuse it for stochastic bisection as well and\nthe code is IMO easier to understand after reorganization so it is still\ncomprehensible after I add there complexity of stochastic bisection.\n\nI understand the churn in the tests is unwelcome but long-term it seems\nlike a low enough cost to pay for more maintainable code. But if git\nmaintainers think otherwise I can try keeping classic bisection code\ndecisions without changes. Just let me know what you prefer.\n\n\t\t\t\t\t\t\t\tHonza\n-- \nJan Kara \nSUSE Labs, CR\n"},{"id":"441935","messageId":"20211122122759.GC24453@quack2.suse.cz","threadId":"56938","inReplyTo":"YZbOKgoYmeM/yLAs@nand.local","subject":"Re: [PATCH 02/27] bisect: Fixup bisect-porcelain/17","fromName":"Jan Kara","fromEmail":"jack@suse.cz","sentAt":"2021-11-22T12:27:59Z","receivedAt":"2021-11-22T12:28:02Z","isPatch":true,"sender":{"key":"jack@suse.cz","avatar":null},"body":"On Thu 18-11-21 17:05:41, Taylor Blau wrote:\n> On Thu, Nov 18, 2021 at 05:49:15PM +0100, Jan Kara wrote:\n> \n> > Test 17 from t6030-bisect-porcelain.sh assumes that bisection algorithm\n> > suggests first HASH3 where HASH2 and HASH3 are equivalent choices. Make\n> > sure test correctly handles both choices, add test variant to properly\n> > test commit skipping in the second case.\n> \n> OK, makes sense-ish: at least in the context of preparing for the\n> bisection algorithm to change. The subject line leaves a bit to be\n> desired, though. Perhaps:\n> \n> t6030: handle equivalent bisection points gracefully\n\nSure, I can improve all subjects to test updates like this.\n\n> > diff --git a/t/t6030-bisect-porcelain.sh b/t/t6030-bisect-porcelain.sh\n> > index 1be85d064e76..f8cfdd3c36d2 100755\n> > --- a/t/t6030-bisect-porcelain.sh\n> > +++ b/t/t6030-bisect-porcelain.sh\n> > @@ -197,11 +197,27 @@ test_expect_success 'bisect skip: successful result' '\n> > \ttest_when_finished git bisect reset &&\n> > \tgit bisect reset &&\n> > \tgit bisect start $HASH4 $HASH1 &&\n> > -\tgit bisect skip &&\n> > +\tif [ $(git rev-parse HEAD) == $HASH3 ]; then\n> \n> This is somewhat uncommon style for Git's test suite. It might be more\n> appropriate to write instead:\n> \n> if test \"$HASH3\" = \"$(git rev-parse HEAD)\"\n> then\n> git bisect skip\n> fi &&\n> # ...\n\nSure. Will do.\n\n> > +# $HASH1 is good, $HASH4 is bad, we skip $HASH2\n> > +# but $HASH3 is good,\n> \n> It looks like this comment should have gone above the start of the test\n> in the previous hunk.\n> \n> But it looks like you accidentally duplicated this test in its entirety\n> (with the addition of the misplaced comment) below instead.\n\nNo, I think the comment and the test are correct. The first test tests\nsituation\n\nH1--H2--H3--H4\n^ ^ ^ ^\n| bad | bad\ngood skipped\n\nthe second test tests situation\n\nH1--H2--H3--H4\n^ ^ ^ ^\n| skipped bad\ngood good\n\nSo in both cases we can decide about the bad commit besides the skipped\ncommit. And if the bisection algorithm picks H2 out of H2/H3 (which are\nequivalent) then second test tests this situation fully, if the bisection\nalgorithm picks H3, then the first test tests this situation fully.\n\n\t\t\t\t\t\t\t\tHonza\n-- \nJan Kara \nSUSE Labs, CR\n"},{"id":"441938","messageId":"20211122124850.GD24453@quack2.suse.cz","threadId":"56938","inReplyTo":"nycvar.QRO.7.76.6.2111191653390.63@tvgsbejvaqbjf.bet","subject":"Re: [PATCH 01/27] bisect: Fixup test rev-list-bisect/02","fromName":"Jan Kara","fromEmail":"jack@suse.cz","sentAt":"2021-11-22T12:48:50Z","receivedAt":"2021-11-22T12:48:53Z","isPatch":true,"sender":{"key":"jack@suse.cz","avatar":null},"body":"On Fri 19-11-21 17:31:22, Johannes Schindelin wrote:\n> Hi,\n> \n> On Thu, 18 Nov 2021, Chris Torek wrote:\n> \n> > On Thu, Nov 18, 2021 at 10:38 AM Jan Kara wrote:\n> > > diff --git a/t/t6002-rev-list-bisect.sh b/t/t6002-rev-list-bisect.sh\n> > > index b95a0212adff..48db52447fd3 100755\n> > > --- a/t/t6002-rev-list-bisect.sh\n> > > +++ b/t/t6002-rev-list-bisect.sh\n> > > @@ -247,8 +247,9 @@ test_expect_success 'set up fake --bisect refs' '\n> > > test_expect_success 'rev-list --bisect can default to good/bad refs' '\n> > > # the only thing between c3 and c1 is c2\n> > > git rev-parse c2 >expect &&\n> > > - git rev-list --bisect >actual &&\n> > > - test_cmp expect actual\n> > > + git rev-parse b2 >>expect &&\n> > > + actual=$(git rev-list --bisect) &&\n> > > + grep &>/dev/null $actual expect\n> >\n> > `&>` is a bashism; you need `>/dev/null 2>&1` here for general portability.\n> \n> More importantly, why do you suppress the output in the first place? This\n> will make debugging breakages harder.\n> \n> Let's just not redirect the output?\n\nSure, I can leave error output alone. I'll do that.\n\n> I do see a more structural problem here, though. Throughout the test\n> suite, it is our custom to generate files called `expect` with what we\n> consider the expected output, and then generate `actual` with the actual\n> output. We then compare the results and complain if they are not\n> identical.\n\nA lot of bisection tests do not work like that. Just look through\nt/t6030-bisect-porcelain.sh for example. I agree that the usage of 'expect'\nand 'actual' may be misleading after my changes though so I will rename\nthem.\n\n> With this patch, we break that paradigm. All of a sudden, `expect` is not\n> at all the expected output anymore, but a haystack in which we want to\n> find one thing.\n> \n> And even after reading the commit message twice, I am unconvinced that b2\n> (whatever that is) might be an equally good choice. I become even more\n> doubtful about that statement when I look at the code comment at the\n> beginning of the test case:\n> \n> \t# the only thing between c3 and c1 is c2\n> \n> So either this code comment is wrong, or the patch. And if the code\n> comment is wrong, I would like to know when it became wrong, and how, and\n> why it slipped through our review.\n\nI agree the comment is confusing but it is more incomplete than outright\nwrong. I can fix that. The graph operated by this test looks like:\n\nb1--b2\n \\ \\\n \\c1--c2--c3\n\nb1 and c1 are marked as good, c3 is marked as bad. Now b2 & c2 are indeed\nequivalent bisection choices because after picking any of them we may need\none more bisection step to identify the bad commit.\n\nThe test including the comment was introduced by 03df567fbf6a\n(\"for_each_bisect_ref(): don't trim refnames\") but I cannot really comment\non why the comment passed review :). IMO because it seems obvious enough...\n\n\t\t\t\t\t\t\t\tHonza\n\n-- \nJan Kara \nSUSE Labs, CR\n"},{"id":"441939","messageId":"20211122124944.GE24453@quack2.suse.cz","threadId":"56938","inReplyTo":"YZbPY9is4+4q2rxF@nand.local","subject":"Re: [PATCH 03/27] bisect: Fixup test bisect-porcelain/20","fromName":"Jan Kara","fromEmail":"jack@suse.cz","sentAt":"2021-11-22T12:49:44Z","receivedAt":"2021-11-22T12:49:46Z","isPatch":true,"sender":{"key":"jack@suse.cz","avatar":null},"body":"On Thu 18-11-21 17:10:43, Taylor Blau wrote:\n> On Thu, Nov 18, 2021 at 12:13:21PM -0800, Chris Torek wrote:\n> > On Thu, Nov 18, 2021 at 10:39 AM Jan Kara wrote:\n> > > diff --git a/t/t6030-bisect-porcelain.sh b/t/t6030-bisect-porcelain.sh\n> > > index f8cfdd3c36d2..13f7deea4d81 100755\n> > > --- a/t/t6030-bisect-porcelain.sh\n> > > +++ b/t/t6030-bisect-porcelain.sh\n> > > @@ -240,8 +240,13 @@ test_expect_success 'bisect skip: cannot tell between 3 commits' '\n> > > test_expect_success 'bisect skip: cannot tell between 2 commits' '\n> > > test_when_finished git bisect reset &&\n> > > git bisect start $HASH4 $HASH1 &&\n> > > - git bisect skip &&\n> > > - test_expect_code 2 git bisect good >my_bisect_log.txt &&\n> > > + if [ $(git rev-parse HEAD) == $HASH2 ]; then\n> > > + results=('good' 'skip')\n> > > + else\n> > > + results=('skip' 'good')\n> > > + fi &&\n> > > + git bisect ${results[0]} &&\n> > > + test_expect_code 2 git bisect ${results[1]} >my_bisect_log.txt &&\n> >\n> > These are also not available in old POSIX shell - consider using two\n> > separate variables to hold the two strings.\n> \n> Or just inlining the commands that you actually want to run inside of\n> the if statement above:\n> \n> if test \"$HASH2\" = \"$(git rev-parse HEAD)\n> then\n> git bisect good &&\n> test_expect_code 2 git bisect skip >my_bisect_log.txt\n> else\n> git bisect skip &&\n> test_expect_code 2 git bisect good >my_bisect_log.txt\n> fi && #...\n> \n> Here (and in the previous patch) it might be helpful to add a short note\n> in these conditionals, maybe along the lines of:\n> \n> # HASH2 and HASH3 are equivalent choices, but we only want to mark\n> # HASH2 as \"good\". Handle either ordering:\n> \n> Same note on the brevity of the subject line applies here, too.\n\nSure, I'll fix these. Thanks for review.\n\n\t\t\t\t\t\t\t\tHonza\n\n-- \nJan Kara \nSUSE Labs, CR\n"},{"id":"441940","messageId":"CAP8UFD0fhKxmuXT40oVj-m6nfkgH+=0isf+vo6bcXW4YbkTEkg@mail.gmail.com","threadId":"56938","inReplyTo":"20211118164940.8818-1-jack@suse.cz","subject":"Re: Stochastic bisection support","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2021-11-22T12:55:33Z","receivedAt":"2021-11-22T12:55:49Z","isPatch":false,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"Hi,\n\nOn Thu, Nov 18, 2021 at 9:33 PM Jan Kara wrote:\n>\n> Hello,\n>\n> In some cases regressions (or generally changes) we are trying to bisect have\n> probabilistic nature. This can for example happen for hard to trigger race\n> condition where it is difficult to distinguish working state from just not\n> hitting the race or it can happen for performance regressions where it is\n> sometimes difficult to distinguish random workload fluctuations from the\n> regression we are looking for. With standard bisection the only option we have\n> is to repeatedly test suggested bisection point until we are sure enough which\n> way to go. This leads to rather long bisection times and still a single wrong\n> decision whether a commit is good to bad renders the whole bisection useless.\n>\n> Stochastic bisection tries to address these problems. When deciding whether a\n> commit is good or bad, you can also specify your confidence in the decision.\n> For performance tests you can usually directly infer this confidence from the\n> distance of your current result from good/bad values, for hard to reproduce\n> races you are usually 100% confident for bad commits, for good commits you need\n> to somehow estimate your confidence based on past experience with reproducing\n> the issue. The stochastic bisection algorithm then uses these test results\n> and confidences to suggest next commit to try, tracking for each commit the\n> probability the commit is the bad one given current test results. Once some\n> commit reaches high enough probability (set when starting bisection) of being\n> the bad one, we stop bisecting and annouce this commit.\n\nThe following project is based on Bayesian Search Theory and might be\ninteresting if you haven't looked at it:\n\nhttps://github.com/Ealdwulf/BBChop\n\nBest,\nChristian.\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n> Example:\n>\n> Consider an example of a stochastic bisection of the following commits:\n>\n> A--B--C--D-----F-----H--------K\n> \\ \\ \\-E-/ / /\n> \\ \\--------G-/ /\n> \\------------------I--J-/\n>\n> And suppose commit I is the bad one. Let's start bisection with:\n>\n> # We ask bisection for 90% confidence in the identified commit being bad\n> git bisect start --confidence 0.9 %K %A\n>\n> # Bisection tells us to test %F. Let's assume test went well and we trust\n> # our test results on 70%. So:\n> git bisect good --confidence 0.7\n>\n> # Bisection tells us to test %H. Again same result:\n> git bisect good --confidence 0.7\n>\n> # Bisection tells us to test %J. The test should fail for %J (remember %I is\n> # the bad commit) but let's assume the test is falsely positive. So:\n> git bisect good --confidence 0.7\n>\n> # We are asked to test %H second time. Assume correct result so:\n> git bisect good --confidence 0.7\n>\n> # We are asked to test %J second time. Assume correct result so:\n> git bisect bad --confidence 0.7\n>\n> # We are asked to test %J again. Assume correct result so:\n> git bisect bad --confidence 0.7\n>\n> # And %J once more. Assume false positive so:\n> git bisect good --confidence 0.7\n>\n> # And %J once more. Assume correct result so:\n> git bisect bad --confidence 0.7\n>\n> # And %J again. Assume correct result so:\n> git bisect bad --confidence 0.7\n>\n> # And now we are asked to test %I. Assume correct result so:\n> git bisect bad --confidence 0.7\n>\n> # We are asked to test %I second time. Assume false positive so:\n> git bisect good --confidence 0.7\n>\n> # And %I once again. Assume correct result so:\n> git bisect bad --confidence 0.7\n>\n> # And %I once again. Assume correct result so:\n> git bisect bad --confidence 0.7\n>\n> # And %I once again. Assume correct result so:\n> git bisect bad --confidence 0.7\n>\n> And now git tells us %I is the bad commit with desired confidence. We can see\n> the bisection was able to identify the bad commit although there were three\n> false positive tests (out of total 14 tests).\n>\n> ------\n>\n> This patch set implements stochastic bisection for git. The first part of the\n> series improves some tests so that they accept other valid decisions for\n> bisection points. This is needed because to make it easier to share some logic\n> between normal and stochastic bisection, I needed to slightly change some bits\n> for normal bisection and then since commit weights will be computed in a\n> somewhat different order, also chosen bisection points are sometimes different.\n>\n> The second part of the series then implements stochastic bisection itself.\n> Note that I didn't integrate any tests for stochastic bisection into 'make\n> test' run yet (so far I did only manual tests) and I still need to update\n> manpages etc. I plan to do that but I've decided to post the series now to get\n> some early feedback.\n>\n> Honza\n>\n> PS: Please leave me in CC for replies. I'm not subscribed to the git mailing\n> list.\n"},{"id":"441945","messageId":"20211122133123.GF24453@quack2.suse.cz","threadId":"56938","inReplyTo":"CAP8UFD0fhKxmuXT40oVj-m6nfkgH+=0isf+vo6bcXW4YbkTEkg@mail.gmail.com","subject":"Re: Stochastic bisection support","fromName":"Jan Kara","fromEmail":"jack@suse.cz","sentAt":"2021-11-22T13:31:23Z","receivedAt":"2021-11-22T13:31:27Z","isPatch":false,"sender":{"key":"jack@suse.cz","avatar":null},"body":"Hi!\n\nOn Mon 22-11-21 13:55:33, Christian Couder wrote:\n> On Thu, Nov 18, 2021 at 9:33 PM Jan Kara wrote:\n> >\n> > Hello,\n> >\n> > In some cases regressions (or generally changes) we are trying to bisect have\n> > probabilistic nature. This can for example happen for hard to trigger race\n> > condition where it is difficult to distinguish working state from just not\n> > hitting the race or it can happen for performance regressions where it is\n> > sometimes difficult to distinguish random workload fluctuations from the\n> > regression we are looking for. With standard bisection the only option we have\n> > is to repeatedly test suggested bisection point until we are sure enough which\n> > way to go. This leads to rather long bisection times and still a single wrong\n> > decision whether a commit is good to bad renders the whole bisection useless.\n> >\n> > Stochastic bisection tries to address these problems. When deciding whether a\n> > commit is good or bad, you can also specify your confidence in the decision.\n> > For performance tests you can usually directly infer this confidence from the\n> > distance of your current result from good/bad values, for hard to reproduce\n> > races you are usually 100% confident for bad commits, for good commits you need\n> > to somehow estimate your confidence based on past experience with reproducing\n> > the issue. The stochastic bisection algorithm then uses these test results\n> > and confidences to suggest next commit to try, tracking for each commit the\n> > probability the commit is the bad one given current test results. Once some\n> > commit reaches high enough probability (set when starting bisection) of being\n> > the bad one, we stop bisecting and annouce this commit.\n> \n> The following project is based on Bayesian Search Theory and might be\n> interesting if you haven't looked at it:\n> \n> https://github.com/Ealdwulf/BBChop\n\nThanks for the link. I already know about that project and I had a look\ninto it when doing some initial research. But the biggest limitation of\nthat project is that it works only for linear history. I need to generally\nbisect Linux kernel repository which has enough merges that the limitation\nof linear history makes the use of the above tool impractical.\n\nFurthermore direct integration of stochastic bisection into git makes this\neasier to integrate into our performance testing framework.\n\n\t\t\t\t\t\t\t\tHonza\n-- \nJan Kara \nSUSE Labs, CR\n"}]}