{"thread":{"id":"41528","subject":"[PATCH 00/16] git bisect improvements","startedAt":"2016-02-26T02:04:26Z","lastAt":"2016-03-22T11:35:14Z","messageCount":34,"participants":["Stephan Beyer","Junio C Hamano","Christian Couder","Jacob Keller","Matthieu Moy","Pranit Bauva"],"isPatch":true,"patchVersion":1,"patchTotal":16},"messages":[{"id":"279460","messageId":"1456452282-10325-1-git-send-email-s-beyer@gmx.net","threadId":"41528","inReplyTo":null,"subject":"[PATCH 00/16] git bisect improvements","fromName":"Stephan Beyer","fromEmail":"s-beyer@gmx.net","sentAt":"2016-02-26T02:04:26Z","receivedAt":"2016-02-26T02:04:26Z","isPatch":true,"sender":{"key":"s-beyer@gmx.net","avatar":"https://avatars.githubusercontent.com/u/143889?v=4"},"body":"Hi,\n\nthis set of patches provides improvements for git bisect.\n\nQuick summary of changes\n - relevant for users:\n - `git bisect next` is documented and motivated\n - git bisect implementation becomes much faster\n (or: is now working) for big repositories**\n - relevant for developers:\n - a test for the git bisect algorithm is added\n - fix: bisect.c compiles also if DEBUG_BISECT is set\n\nThe ** marked change is the most interesting one.\nTo be more accurate: the use case is when you want to bisect in a\nrepository with a huge amount of merge commits (and having these\nmerge commits relevant for the actual bisect process).\nFor example, a bisect in the whole git master branch took\n~50 seconds, now it takes ~4 seconds.\n\n\nNote that the patches have finer granularity (especially the performance\nimprovements are splitted into several preparing commits).\nFor some patches, there is some more patch-related story as\n\"cover letter material\" in these patches.\n\nBtw: I also wondered about the internationalizaton: no string in bisect.c\nis marked for translation. Intentionally?\n\nCheers\n\nStephan Beyer (16):\n bisect: write about `bisect next` in documentation\n bisect: add test for the bisect algorithm\n bisect: make bisect compile if DEBUG_BISECT is set\n bisect: make algorithm behavior independent of DEBUG_BISECT\n bisect: get rid of recursion in count_distance()\n bisect: use struct node_data array instead of int array\n bisect: replace clear_distance() by unique markers\n bisect: use commit instead of commit list as arguments when\n appropriate\n bisect: extract get_distance() function from code duplication\n bisect: introduce distance_direction()\n bisect: make total number of commits global\n bisect: rename count_distance() to compute_weight()\n bisect: prepare for different algorithms based on find_all\n bisect: use a modified breadth-first search to find relevant weights\n bisect: compute best bisection in compute_relevant_weights()\n bisect: get back halfway shortcut\n\n Documentation/git-bisect.txt | 25 +++\n bisect.c | 473 ++++++++++++++++++++++++++++---------------\n git-bisect.sh | 15 +-\n t/t8010-bisect-algorithm.sh | 162 +++++++++++++++\n 4 files changed, 502 insertions(+), 173 deletions(-)\n create mode 100755 t/t8010-bisect-algorithm.sh\n\n-- \n2.7.1.354.gd492730.dirty\n"},{"id":"279471","messageId":"1456452282-10325-2-git-send-email-s-beyer@gmx.net","threadId":"41528","inReplyTo":"1456452282-10325-1-git-send-email-s-beyer@gmx.net","subject":"[PATCH 01/16] bisect: write about `bisect next` in documentation","fromName":"Stephan Beyer","fromEmail":"s-beyer@gmx.net","sentAt":"2016-02-26T02:04:27Z","receivedAt":"2016-02-26T02:04:27Z","isPatch":true,"sender":{"key":"s-beyer@gmx.net","avatar":"https://avatars.githubusercontent.com/u/143889?v=4"},"body":"Mention `bisect next` in the documentation of bisect.\n`bisect next` is only useful in rare cases and the result\ncan also be accomplished using other utilities (like reflog).\nHowever, it is available as a bisect command and should hence be\ndocumented.\n\nAlso mention the use case when no good commit is known.\nSome user message in git-bisect.sh is changed to reflect that\nuse case. It is also simplified: there is no need to mention\nrunning `bisect start` explicitly, because it can be done\nindirectly using `bisect bad`.\n\nSigned-off-by: Stephan Beyer \n---\n\nThis patch considers the source code comment that says to be\n\"not sure we want 'next' at the UI level anymore\", and replies with\n\"Yes, we want it!\". Therefore, the \"git bisect next\" functionality\nis explicitly motivated and documented.\n\nThe motivation of \"having no good commit\" is not made up. I am\nworking on a big project that is several years old and nearly\nno test exists. So I add a test and things go wrong. However,\nI know from using (an older version of) the project that a similar\ncase did work. So...I want to find the bad commit...\nHowever, to make git bisect work, I always first had to find a good\ncommit, so I ended up doing the whole bisection process manually\n(because I did not know that \"git bisect next\" existed).\n\nI think that this change will help people who are also in these\nsituations.\n\n Documentation/git-bisect.txt | 25 +++++++++++++++++++++++++\n git-bisect.sh | 15 ++++-----------\n 2 files changed, 29 insertions(+), 11 deletions(-)\n\ndiff --git a/Documentation/git-bisect.txt b/Documentation/git-bisect.txt\nindex 7e79aae..8045e6d 100644\n--- a/Documentation/git-bisect.txt\n+++ b/Documentation/git-bisect.txt\n@@ -27,6 +27,7 @@ on the subcommand:\n git bisect replay \n git bisect log\n git bisect run ...\n+ git bisect next\n git bisect help\n \n This command uses a binary search algorithm to find which commit in\n@@ -66,6 +67,15 @@ checks it out, and outputs something similar to the following:\n Bisecting: 675 revisions left to test after this (roughly 10 steps)\n ------------------------------------------------\n \n+Note that in cases you do not know a good commit,\n+you can also start with:\n+\n+------------------------------------------------\n+$ git bisect start\n+$ git bisect bad # current version is bad\n+$ git bisect next # check out another commit\n+------------------------------------------------\n+\n You should now compile the checked-out version and test it. If that\n version works correctly, type\n \n@@ -353,6 +363,21 @@ rewind the tree to the pristine state. Finally the script should exit\n with the status of the real test to let the `git bisect run` command loop\n determine the eventual outcome of the bisect session.\n \n+Bisect next\n+~~~~~~~~~~~\n+\n+Sometimes it can be necessary to check out other branches during a bisect\n+session. If you want to check out the next commit of the bisection again,\n+simply issue the command:\n+\n+------------\n+$ git bisect next\n+------------\n+\n+Another typical use case of this command is when you have marked a commit\n+as bad but you do not know a good commit. Instead of crawling through the\n+history yourself, let this command check out a commit for you.\n+\n OPTIONS\n -------\n --no-checkout::\ndiff --git a/git-bisect.sh b/git-bisect.sh\nindex 5d1cb00..5c93a27 100755\n--- a/git-bisect.sh\n+++ b/git-bisect.sh\n@@ -334,16 +334,10 @@ bisect_next_check() {\n \t*)\n \t\tbad_syn=$(bisect_voc bad)\n \t\tgood_syn=$(bisect_voc good)\n-\t\tif test -s \"$GIT_DIR/BISECT_START\"\n-\t\tthen\n-\n-\t\t\teval_gettextln \"You need to give me at least one \\$bad_syn and one \\$good_syn revision.\n-(You can use \\\"git bisect \\$bad_syn\\\" and \\\"git bisect \\$good_syn\\\" for that.)\" >&2\n-\t\telse\n-\t\t\teval_gettextln \"You need to start by \\\"git bisect start\\\".\n-You then need to give me at least one \\$good_syn and one \\$bad_syn revision.\n-(You can use \\\"git bisect \\$bad_syn\\\" and \\\"git bisect \\$good_syn\\\" for that.)\" >&2\n-\t\tfi\n+\t\teval_gettextln \"You need to give me at least one \\$bad_syn revision.\n+Use \\\"git bisect \\$bad_syn\\\" for that. One \\$good_syn revision is also helpful\n+for bisecting (use \\\"git bisect \\$good_syn\\\"). If you do not know one \\$good_syn\n+revision, you can use \\\"git bisect next\\\" to find one.\" >&2\n \t\texit 1 ;;\n \tesac\n }\n@@ -677,7 +671,6 @@ case \"$#\" in\n \tskip)\n \t\tbisect_skip \"$@\" ;;\n \tnext)\n-\t\t# Not sure we want \"next\" at the UI level anymore.\n \t\tbisect_next \"$@\" ;;\n \tvisualize|view)\n \t\tbisect_visualize \"$@\" ;;\n-- \n2.7.1.354.gd492730.dirty\n"},{"id":"279472","messageId":"1456452282-10325-3-git-send-email-s-beyer@gmx.net","threadId":"41528","inReplyTo":"1456452282-10325-1-git-send-email-s-beyer@gmx.net","subject":"[PATCH 02/16] bisect: add test for the bisect algorithm","fromName":"Stephan Beyer","fromEmail":"s-beyer@gmx.net","sentAt":"2016-02-26T02:04:28Z","receivedAt":"2016-02-26T02:04:28Z","isPatch":true,"sender":{"key":"s-beyer@gmx.net","avatar":"https://avatars.githubusercontent.com/u/143889?v=4"},"body":"Signed-off-by: Stephan Beyer \n---\n\nTo be honest: the test could be better, it could be more \"targeted\",\ni.e. the example commit history could be smaller and just consider\nall the cases and corner cases and whatever.\nHowever, I made it first to understand the algorithm and verify the\ndescription of it in the documentation. Then I was too lazy to\nimprove it. I am sorry that this is no better advertising text. ;)\n\nMoreover, the test does not test one important thing that is\nalways cared about in the bisect code: TREESAME commits.\nPerhaps I got the concept wrong. I tried to obtain TREESAME commits\nusing 'git commit --allow-empty -m \"same tree\"'. However, those\ncommits were never considered being TREESAME. So I gave up (I did\nnot care much.)\nAnyone has an idea how to obtain them?\nOr is this a bug that should be fixed?\n\n(Also UNINTERESTING commits are never found by the DEBUG_BISECT\noutput, but I think this is because they are just filtered out.)\n\n t/t8010-bisect-algorithm.sh | 162 ++++++++++++++++++++++++++++++++++++++++++++\n 1 file changed, 162 insertions(+)\n create mode 100755 t/t8010-bisect-algorithm.sh\n\ndiff --git a/t/t8010-bisect-algorithm.sh b/t/t8010-bisect-algorithm.sh\nnew file mode 100755\nindex 0000000..bda59da\n--- /dev/null\n+++ b/t/t8010-bisect-algorithm.sh\n@@ -0,0 +1,162 @@\n+#!/bin/sh\n+#\n+# Copyright (c) 2016 Stephan Beyer\n+#\n+test_description='Tests git bisect algorithm'\n+\n+exec output &&\n+\tgrep \"$(git rev-parse BCDmerge) is the first bad commit\" output\n+'\n+\n+# G 5a6bcdf D3 | w min | w min |\n+# | B 02f2eed A9 | 14 0 | 7 0 |\n+# | *---. 6174c5c BCDmerge | 13 1 | 6 1 |\n+# | |\\ \\ \\ | | |\n+# | |_|_|/ | | |\n+# |/| | | | | |\n+# G | | | a6d6dab D2 | good | good |\n+# * | | | 86414e4 D1 | good | good |\n+# | | | * c672402 C3 | 7 7 *| good |\n+# | | | * 0555272 C2 | 6 6 | good |\n+# | | | * 28c2b2a C1 | 5 5 | good |\n+# | | * | 4b5a7d9 B3 | 5 5 | 3 3 *|\n+# | * | | a419ab7 Bmerge | 8 6 | 4 3 *|\n+# | |\\ \\ \\ | | |\n+# | | |/ / | | |\n+# | | * | 4fa1e39 B2 | 4 4 | 2 2 |\n+# | | * | 92a014d B1 | 3 3 | 1 1 |\n+# | * | | 79158c7 A8 | 5 5 | 1 1 |\n+# | | |/ | | |\n+# | |/| | | |\n+# | * | 237eb73 A7 | 4 4 | good |\n+# | * | 3b2f811 A6 | 3 3 | good |\n+# | |/ | | |\n+# | * 0f2b6d2 A5 | 2 2 | good |\n+# | * 1fcdaf0 A4 | 1 1 | good |\n+# |/ | | |\n+# * 096648b A3 | good | good |\n+# * 1cf01b8 A2 | good | good |\n+# * 6623165 A1 | good | good |\n+\n+test_expect_success 'bisect algorithm works with good commit on unrelated branch' '\n+\tgit bisect reset &&\n+\tgit bisect start A9 D3 &&\n+\ttest \"$(git rev-parse HEAD)\" = \"$(git merge-base A9 D3)\" &&\n+\ttest \"$(git rev-parse HEAD)\" = \"$(git rev-parse D2)\" &&\n+\tgit bisect good &&\n+\ttest \"$(git rev-parse HEAD)\" = \"$(git rev-parse C3)\" &&\n+\tgit bisect good &&\n+\ttest \"$(git rev-parse HEAD)\" = \"$(git rev-parse B3)\" \\\n+\t -o \"$(git rev-parse HEAD)\" = \"$(git rev-parse Bmerge)\"\n+'\n+\n+test_done\n-- \n2.7.1.354.gd492730.dirty\n"},{"id":"279461","messageId":"1456452282-10325-4-git-send-email-s-beyer@gmx.net","threadId":"41528","inReplyTo":"1456452282-10325-1-git-send-email-s-beyer@gmx.net","subject":"[PATCH 03/16] bisect: make bisect compile if DEBUG_BISECT is set","fromName":"Stephan Beyer","fromEmail":"s-beyer@gmx.net","sentAt":"2016-02-26T02:04:29Z","receivedAt":"2016-02-26T02:04:29Z","isPatch":true,"sender":{"key":"s-beyer@gmx.net","avatar":"https://avatars.githubusercontent.com/u/143889?v=4"},"body":"Setting the macro DEBUG_BISECT to 1 enables debugging information\nfor the bisect algorithm. The code did not compile due to struct\nchanges.\n\nSigned-off-by: Stephan Beyer \n---\n bisect.c | 6 +++---\n 1 file changed, 3 insertions(+), 3 deletions(-)\n\ndiff --git a/bisect.c b/bisect.c\nindex 06ec54e..905e63a 100644\n--- a/bisect.c\n+++ b/bisect.c\n@@ -131,7 +131,7 @@ static void show_list(const char *debug, int counted, int nr,\n \t\tunsigned flags = commit->object.flags;\n \t\tenum object_type type;\n \t\tunsigned long size;\n-\t\tchar *buf = read_sha1_file(commit->object.sha1, &type, &size);\n+\t\tchar *buf = read_sha1_file(commit->object.oid.hash, &type, &size);\n \t\tconst char *subject_start;\n \t\tint subject_len;\n \n@@ -143,10 +143,10 @@ static void show_list(const char *debug, int counted, int nr,\n \t\t\tfprintf(stderr, \"%3d\", weight(p));\n \t\telse\n \t\t\tfprintf(stderr, \"---\");\n-\t\tfprintf(stderr, \" %.*s\", 8, sha1_to_hex(commit->object.sha1));\n+\t\tfprintf(stderr, \" %.*s\", 8, sha1_to_hex(commit->object.oid.hash));\n \t\tfor (pp = commit->parents; pp; pp = pp->next)\n \t\t\tfprintf(stderr, \" %.*s\", 8,\n-\t\t\t\tsha1_to_hex(pp->item->object.sha1));\n+\t\t\t\tsha1_to_hex(pp->item->object.oid.hash));\n \n \t\tsubject_len = find_commit_subject(buf, &subject_start);\n \t\tif (subject_len)\n-- \n2.7.1.354.gd492730.dirty\n"},{"id":"279476","messageId":"1456452282-10325-5-git-send-email-s-beyer@gmx.net","threadId":"41528","inReplyTo":"1456452282-10325-1-git-send-email-s-beyer@gmx.net","subject":"[PATCH 04/16] bisect: make algorithm behavior independent of DEBUG_BISECT","fromName":"Stephan Beyer","fromEmail":"s-beyer@gmx.net","sentAt":"2016-02-26T02:04:30Z","receivedAt":"2016-02-26T02:04:30Z","isPatch":true,"sender":{"key":"s-beyer@gmx.net","avatar":"https://avatars.githubusercontent.com/u/143889?v=4"},"body":"If DEBUG_BISECT is set to 1, bisect does not only show debug\ninformation but also changes the algorithm behavior: halfway()\nis always false.\n\nThis commit makes the algorithm independent of DEBUG_BISECT.\n\nSigned-off-by: Stephan Beyer \n---\n bisect.c | 2 --\n 1 file changed, 2 deletions(-)\n\ndiff --git a/bisect.c b/bisect.c\nindex 905e63a..412e2c0 100644\n--- a/bisect.c\n+++ b/bisect.c\n@@ -101,8 +101,6 @@ static inline int 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-\t\treturn 0;\n \t/*\n \t * 2 and 3 are halfway of 5.\n \t * 3 is halfway of 6 but 2 and 4 are not.\n-- \n2.7.1.354.gd492730.dirty\n"},{"id":"279474","messageId":"1456452282-10325-6-git-send-email-s-beyer@gmx.net","threadId":"41528","inReplyTo":"1456452282-10325-1-git-send-email-s-beyer@gmx.net","subject":"[PATCH 05/16] bisect: get rid of recursion in count_distance()","fromName":"Stephan Beyer","fromEmail":"s-beyer@gmx.net","sentAt":"2016-02-26T02:04:31Z","receivedAt":"2016-02-26T02:04:31Z","isPatch":true,"sender":{"key":"s-beyer@gmx.net","avatar":"https://avatars.githubusercontent.com/u/143889?v=4"},"body":"Large repositories with a huge amount of merge commits in the\nbisection process could lead to stack overflows in git bisect.\nIn order to prevent this, this commit uses an *iterative* version\nfor counting the number of ancestors of a commit.\n\nSigned-off-by: Stephan Beyer \n---\n\nIn the cover letter I promised that bisect will be faster.\nIt's not rocket science to know that replacing a simple recursion\nby an iterative version involving a list (with alloc'ing and stuff)\nmakes the code slower.\n\nFor my git master branch test, this changed the running time\nfrom ~50 to ~60 seconds. However, for a smaller stack size,\nthis changes the running time from to ~60 seconds.\nThat's a win ;-)\n\n bisect.c | 55 ++++++++++++++++++++++---------------------------------\n 1 file changed, 22 insertions(+), 33 deletions(-)\n\ndiff --git a/bisect.c b/bisect.c\nindex 412e2c0..03e7660 100644\n--- a/bisect.c\n+++ b/bisect.c\n@@ -26,33 +26,23 @@ static const char *term_good;\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+\tstruct commit_list *todo = NULL;\n+\tcommit_list_append(entry->item, &todo);\n \n-\twhile (entry) {\n-\t\tstruct commit *commit = entry->item;\n-\t\tstruct commit_list *p;\n+\twhile (todo) {\n+\t\tstruct commit *commit = pop_commit(&todo);\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\tif (!(commit->object.flags & (UNINTERESTING | COUNTED))) {\n+\t\t\tstruct commit_list *p;\n+\t\t\tif (!(commit->object.flags & TREESAME))\n+\t\t\t\tnr++;\n+\t\t\tcommit->object.flags |= COUNTED;\n+\n+\t\t\tfor (p = commit->parents; p; p = p->next) {\n+\t\t\t\tcommit_list_insert(p->item, &todo);\n \t\t\t}\n \t\t}\n \t}\n@@ -287,7 +277,7 @@ static struct commit_list *do_find_bisection(struct commit_list *list,\n \t * can reach. So we do not have to run the expensive\n \t * count_distance() for single strand of pearls.\n \t *\n-\t * However, if you have more than one parents, you cannot\n+\t * However, if you have more than one parent, you cannot\n \t * just add their distance and one for yourself, since\n \t * they usually reach the same ancestor and you would\n \t * end up counting them twice that way.\n@@ -296,17 +286,16 @@ static struct commit_list *do_find_bisection(struct commit_list *list,\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\tweight_set(p, count_distance(p));\n-\t\tclear_distance(list);\n+\t\tif (!(p->item->object.flags & UNINTERESTING)\n+\t\t && (weight(p) == -2)) {\n+\t\t\tweight_set(p, count_distance(p));\n+\t\t\tclear_distance(list);\n \n-\t\t/* Does it happen to be at exactly half-way? */\n-\t\tif (!find_all && halfway(p, nr))\n-\t\t\treturn p;\n-\t\tcounted++;\n+\t\t\t/* Does it happen to be at exactly half-way? */\n+\t\t\tif (!find_all && 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-- \n2.7.1.354.gd492730.dirty\n"},{"id":"279470","messageId":"1456452282-10325-7-git-send-email-s-beyer@gmx.net","threadId":"41528","inReplyTo":"1456452282-10325-1-git-send-email-s-beyer@gmx.net","subject":"[PATCH 06/16] bisect: use struct node_data array instead of int array","fromName":"Stephan Beyer","fromEmail":"s-beyer@gmx.net","sentAt":"2016-02-26T02:04:32Z","receivedAt":"2016-02-26T02:04:32Z","isPatch":true,"sender":{"key":"s-beyer@gmx.net","avatar":"https://avatars.githubusercontent.com/u/143889?v=4"},"body":"This is a preparation for subsequent changes.\nDuring a bisection process, we want to augment commits with\nfurther information to improve speed.\n\nSigned-off-by: Stephan Beyer \n---\n bisect.c | 61 ++++++++++++++++++++++++++++++-------------------------------\n 1 file changed, 30 insertions(+), 31 deletions(-)\n\ndiff --git a/bisect.c b/bisect.c\nindex 03e7660..bcb58ed 100644\n--- a/bisect.c\n+++ b/bisect.c\n@@ -23,9 +23,21 @@ static const char *argv_show_branch[] = {\"show-branch\", NULL, NULL};\n static const char *term_bad;\n static const char *term_good;\n \n+struct node_data {\n+\tint weight;\n+};\n+\n /* Remember to update object flag allocation in object.h */\n #define COUNTED\t\t(1u<<16)\n \n+#define DEBUG_BISECT 0\n+\n+static inline struct node_data *node_data(struct commit *elem)\n+{\n+\tassert(elem->util);\n+\treturn (struct node_data *)elem->util;\n+}\n+\n static int count_distance(struct commit_list *entry)\n {\n \tint nr = 0;\n@@ -59,18 +71,6 @@ static void clear_distance(struct commit_list *list)\n \t}\n }\n \n-#define DEBUG_BISECT 0\n-\n-static inline int weight(struct commit_list *elem)\n-{\n-\treturn *((int*)(elem->item->util));\n-}\n-\n-static inline void weight_set(struct commit_list *elem, int weight)\n-{\n-\t*((int*)(elem->item->util)) = weight;\n-}\n-\n static int count_interesting_parents(struct commit *commit)\n {\n \tstruct commit_list *p;\n@@ -95,7 +95,7 @@ static inline int halfway(struct commit_list *p, int nr)\n \t * 2 and 3 are halfway of 5.\n \t * 3 is halfway of 6 but 2 and 4 are not.\n \t */\n-\tswitch (2 * weight(p) - nr) {\n+\tswitch (2 * node_data(p->item)->weight - nr) {\n \tcase -1: case 0: case 1:\n \t\treturn 1;\n \tdefault:\n@@ -128,7 +128,7 @@ static void show_list(const char *debug, int counted, int nr,\n \t\t\t(flags & UNINTERESTING) ? 'U' : ' ',\n \t\t\t(flags & COUNTED) ? 'C' : ' ');\n \t\tif (commit->util)\n-\t\t\tfprintf(stderr, \"%3d\", weight(p));\n+\t\t\tfprintf(stderr, \"%3d\", node_data(commit)->weight);\n \t\telse\n \t\t\tfprintf(stderr, \"---\");\n \t\tfprintf(stderr, \" %.*s\", 8, sha1_to_hex(commit->object.oid.hash));\n@@ -156,7 +156,7 @@ static struct commit_list *best_bisection(struct commit_list *list, int nr)\n \n \t\tif (flags & TREESAME)\n \t\t\tcontinue;\n-\t\tdistance = weight(p);\n+\t\tdistance = node_data(p->item)->weight;\n \t\tif (nr - distance < distance)\n \t\t\tdistance = nr - distance;\n \t\tif (distance > best_distance) {\n@@ -196,7 +196,7 @@ static struct commit_list *best_bisection_sorted(struct commit_list *list, int n\n \n \t\tif (flags & TREESAME)\n \t\t\tcontinue;\n-\t\tdistance = weight(p);\n+\t\tdistance = node_data(p->item)->weight;\n \t\tif (nr - distance < distance)\n \t\t\tdistance = nr - distance;\n \t\tarray[cnt].commit = p->item;\n@@ -234,7 +234,7 @@ 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 int nr, struct node_data *weights,\n \t\t\t\t\t int find_all)\n {\n \tint n, counted;\n@@ -246,11 +246,11 @@ static struct commit_list *do_find_bisection(struct commit_list *list,\n \t\tstruct commit *commit = p->item;\n \t\tunsigned flags = commit->object.flags;\n \n-\t\tp->item->util = &weights[n++];\n+\t\tcommit->util = &weights[n++];\n \t\tswitch (count_interesting_parents(commit)) {\n \t\tcase 0:\n \t\t\tif (!(flags & TREESAME)) {\n-\t\t\t\tweight_set(p, 1);\n+\t\t\t\tnode_data(commit)->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@@ -261,10 +261,10 @@ static struct commit_list *do_find_bisection(struct commit_list *list,\n \t\t\t */\n \t\t\tbreak;\n \t\tcase 1:\n-\t\t\tweight_set(p, -1);\n+\t\t\tnode_data(commit)->weight = -1;\n \t\t\tbreak;\n \t\tdefault:\n-\t\t\tweight_set(p, -2);\n+\t\t\tnode_data(commit)->weight = -2;\n \t\t\tbreak;\n \t\t}\n \t}\n@@ -287,8 +287,8 @@ static struct commit_list *do_find_bisection(struct commit_list *list,\n \t */\n \tfor (p = list; p; p = p->next) {\n \t\tif (!(p->item->object.flags & UNINTERESTING)\n-\t\t && (weight(p) == -2)) {\n-\t\t\tweight_set(p, count_distance(p));\n+\t\t && (node_data(p->item)->weight == -2)) {\n+\t\t\tnode_data(p->item)->weight = count_distance(p);\n \t\t\tclear_distance(list);\n \n \t\t\t/* Does it happen to be at exactly half-way? */\n@@ -305,12 +305,12 @@ static struct commit_list *do_find_bisection(struct commit_list *list,\n \t\t\tstruct commit_list *q;\n \t\t\tunsigned flags = p->item->object.flags;\n \n-\t\t\tif (0 <= weight(p))\n+\t\t\tif (0 <= node_data(p->item)->weight)\n \t\t\t\tcontinue;\n \t\t\tfor (q = p->item->parents; q; q = 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\tif (0 <= node_data(q->item)->weight)\n \t\t\t\t\tbreak;\n \t\t\t}\n \t\t\tif (!q)\n@@ -321,14 +321,13 @@ static struct commit_list *do_find_bisection(struct commit_list *list,\n \t\t\t * add one for p itself if p is to be counted,\n \t\t\t * otherwise inherit it from q directly.\n \t\t\t */\n+\t\t\tnode_data(p->item)->weight = node_data(q->item)->weight;\n \t\t\tif (!(flags & TREESAME)) {\n-\t\t\t\tweight_set(p, weight(q)+1);\n+\t\t\t\tnode_data(p->item)->weight++;\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 \n \t\t\t/* Does it happen to be at exactly half-way? */\n \t\t\tif (!find_all && halfway(p, nr))\n@@ -350,7 +349,7 @@ struct commit_list *find_bisection(struct commit_list *list,\n {\n \tint nr, on_list;\n \tstruct commit_list *p, *best, *next, *last;\n-\tint *weights;\n+\tstruct node_data *weights;\n \n \tshow_list(\"bisection 2 entry\", 0, 0, list);\n \n@@ -376,14 +375,14 @@ struct commit_list *find_bisection(struct commit_list *list,\n \tshow_list(\"bisection 2 sorted\", 0, nr, list);\n \n \t*all = nr;\n-\tweights = xcalloc(on_list, sizeof(*weights));\n+\tweights = (struct node_data *)xcalloc(on_list, sizeof(*weights));\n \n \t/* Do the real work of finding bisection commit. */\n \tbest = do_find_bisection(list, nr, weights, find_all);\n \tif (best) {\n \t\tif (!find_all)\n \t\t\tbest->next = NULL;\n-\t\t*reaches = weight(best);\n+\t\t*reaches = node_data(best->item)->weight;\n \t}\n \tfree(weights);\n \treturn best;\n-- \n2.7.1.354.gd492730.dirty\n"},{"id":"279466","messageId":"1456452282-10325-8-git-send-email-s-beyer@gmx.net","threadId":"41528","inReplyTo":"1456452282-10325-1-git-send-email-s-beyer@gmx.net","subject":"[PATCH 07/16] bisect: replace clear_distance() by unique markers","fromName":"Stephan Beyer","fromEmail":"s-beyer@gmx.net","sentAt":"2016-02-26T02:04:33Z","receivedAt":"2016-02-26T02:04:33Z","isPatch":true,"sender":{"key":"s-beyer@gmx.net","avatar":"https://avatars.githubusercontent.com/u/143889?v=4"},"body":"clear_distance() was a O(#commits)-time function to clear the COUNTED\nflag from commits counted in count_distance().\nThe functions count_distance() and clear_distance() were called for\neach merge commit.\n\nThis commit gets rid of the clear_distance() function by making\ncount_distance() use unique marker ids that do not need to be\ncleared afterwards. This speeds up the bisecting process on\nlarge repositories with a huge amount of merges.\n\nSigned-off-by: Stephan Beyer \n---\n\nYaaay, this is our first gain of performance!\nMy test: ~30 seconds\n\n bisect.c | 29 +++++++++++------------------\n 1 file changed, 11 insertions(+), 18 deletions(-)\n\ndiff --git a/bisect.c b/bisect.c\nindex bcb58ed..6df13b0 100644\n--- a/bisect.c\n+++ b/bisect.c\n@@ -23,13 +23,13 @@ static const char *argv_show_branch[] = {\"show-branch\", NULL, NULL};\n static const char *term_bad;\n static const char *term_good;\n \n+static unsigned marker;\n+\n struct node_data {\n \tint weight;\n+\tunsigned marked;\n };\n \n-/* Remember to update object flag allocation in object.h */\n-#define COUNTED\t\t(1u<<16)\n-\n #define DEBUG_BISECT 0\n \n static inline struct node_data *node_data(struct commit *elem)\n@@ -43,15 +43,17 @@ static int count_distance(struct commit_list *entry)\n \tint nr = 0;\n \tstruct commit_list *todo = NULL;\n \tcommit_list_append(entry->item, &todo);\n+\tmarker++;\n \n \twhile (todo) {\n \t\tstruct commit *commit = pop_commit(&todo);\n \n-\t\tif (!(commit->object.flags & (UNINTERESTING | COUNTED))) {\n+\t\tif (!(commit->object.flags & UNINTERESTING)\n+\t\t && node_data(commit)->marked != marker) {\n \t\t\tstruct commit_list *p;\n \t\t\tif (!(commit->object.flags & TREESAME))\n \t\t\t\tnr++;\n-\t\t\tcommit->object.flags |= COUNTED;\n+\t\t\tnode_data(commit)->marked = marker;\n \n \t\t\tfor (p = commit->parents; p; p = p->next) {\n \t\t\t\tcommit_list_insert(p->item, &todo);\n@@ -62,15 +64,6 @@ static int count_distance(struct commit_list *entry)\n \treturn nr;\n }\n \n-static void clear_distance(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 int count_interesting_parents(struct commit *commit)\n {\n \tstruct commit_list *p;\n@@ -123,10 +116,9 @@ static void show_list(const char *debug, int counted, int nr,\n \t\tconst char *subject_start;\n \t\tint subject_len;\n \n-\t\tfprintf(stderr, \"%c%c%c \",\n+\t\tfprintf(stderr, \"%c%c \",\n \t\t\t(flags & TREESAME) ? ' ' : 'T',\n-\t\t\t(flags & UNINTERESTING) ? 'U' : ' ',\n-\t\t\t(flags & COUNTED) ? 'C' : ' ');\n+\t\t\t(flags & UNINTERESTING) ? 'U' : ' ');\n \t\tif (commit->util)\n \t\t\tfprintf(stderr, \"%3d\", node_data(commit)->weight);\n \t\telse\n@@ -289,7 +281,6 @@ static struct commit_list *do_find_bisection(struct commit_list *list,\n \t\tif (!(p->item->object.flags & UNINTERESTING)\n \t\t && (node_data(p->item)->weight == -2)) {\n \t\t\tnode_data(p->item)->weight = count_distance(p);\n-\t\t\tclear_distance(list);\n \n \t\t\t/* Does it happen to be at exactly half-way? */\n \t\t\tif (!find_all && halfway(p, nr))\n@@ -351,6 +342,8 @@ struct commit_list *find_bisection(struct commit_list *list,\n \tstruct commit_list *p, *best, *next, *last;\n \tstruct node_data *weights;\n \n+\tmarker = 0;\n+\n \tshow_list(\"bisection 2 entry\", 0, 0, list);\n \n \t/*\n-- \n2.7.1.354.gd492730.dirty\n"},{"id":"279464","messageId":"1456452282-10325-9-git-send-email-s-beyer@gmx.net","threadId":"41528","inReplyTo":"1456452282-10325-1-git-send-email-s-beyer@gmx.net","subject":"[PATCH 08/16] bisect: use commit instead of commit list as arguments when appropriate","fromName":"Stephan Beyer","fromEmail":"s-beyer@gmx.net","sentAt":"2016-02-26T02:04:34Z","receivedAt":"2016-02-26T02:04:34Z","isPatch":true,"sender":{"key":"s-beyer@gmx.net","avatar":"https://avatars.githubusercontent.com/u/143889?v=4"},"body":"It makes no sense that the argument for count_distance() and\nhalfway() is a commit list when only its first commit is relevant.\n\nSigned-off-by: Stephan Beyer \n---\n\nThis is just some kind of minor code cleanup.\nThe typical \"while at it\", you know it, I guess.\n\n bisect.c | 16 ++++++++--------\n 1 file changed, 8 insertions(+), 8 deletions(-)\n\ndiff --git a/bisect.c b/bisect.c\nindex 6df13b0..76f2445 100644\n--- a/bisect.c\n+++ b/bisect.c\n@@ -38,11 +38,11 @@ static inline struct node_data *node_data(struct commit *elem)\n \treturn (struct node_data *)elem->util;\n }\n \n-static int count_distance(struct commit_list *entry)\n+static int count_distance(struct commit *entry)\n {\n \tint nr = 0;\n \tstruct commit_list *todo = NULL;\n-\tcommit_list_append(entry->item, &todo);\n+\tcommit_list_append(entry, &todo);\n \tmarker++;\n \n \twhile (todo) {\n@@ -77,18 +77,18 @@ static int count_interesting_parents(struct commit *commit)\n \treturn count;\n }\n \n-static inline int halfway(struct commit_list *p, int nr)\n+static inline int halfway(struct commit *commit, int nr)\n {\n \t/*\n \t * Don't short-cut something we are not going to return!\n \t */\n-\tif (p->item->object.flags & TREESAME)\n+\tif (commit->object.flags & TREESAME)\n \t\treturn 0;\n \t/*\n \t * 2 and 3 are halfway of 5.\n \t * 3 is halfway of 6 but 2 and 4 are not.\n \t */\n-\tswitch (2 * node_data(p->item)->weight - nr) {\n+\tswitch (2 * node_data(commit)->weight - nr) {\n \tcase -1: case 0: case 1:\n \t\treturn 1;\n \tdefault:\n@@ -280,10 +280,10 @@ static struct commit_list *do_find_bisection(struct commit_list *list,\n \tfor (p = list; p; p = p->next) {\n \t\tif (!(p->item->object.flags & UNINTERESTING)\n \t\t && (node_data(p->item)->weight == -2)) {\n-\t\t\tnode_data(p->item)->weight = count_distance(p);\n+\t\t\tnode_data(p->item)->weight = count_distance(p->item);\n \n \t\t\t/* Does it happen to be at exactly half-way? */\n-\t\t\tif (!find_all && halfway(p, nr))\n+\t\t\tif (!find_all && halfway(p->item, nr))\n \t\t\t\treturn p;\n \t\t\tcounted++;\n \t\t}\n@@ -321,7 +321,7 @@ static struct commit_list *do_find_bisection(struct commit_list *list,\n \t\t\t}\n \n \t\t\t/* Does it happen to be at exactly half-way? */\n-\t\t\tif (!find_all && halfway(p, nr))\n+\t\t\tif (!find_all && halfway(p->item, nr))\n \t\t\t\treturn p;\n \t\t}\n \t}\n-- \n2.7.1.354.gd492730.dirty\n"},{"id":"279463","messageId":"1456452282-10325-10-git-send-email-s-beyer@gmx.net","threadId":"41528","inReplyTo":"1456452282-10325-1-git-send-email-s-beyer@gmx.net","subject":"[PATCH 09/16] bisect: extract get_distance() function from code duplication","fromName":"Stephan Beyer","fromEmail":"s-beyer@gmx.net","sentAt":"2016-02-26T02:04:35Z","receivedAt":"2016-02-26T02:04:35Z","isPatch":true,"sender":{"key":"s-beyer@gmx.net","avatar":"https://avatars.githubusercontent.com/u/143889?v=4"},"body":"Signed-off-by: Stephan Beyer \n---\n\nWe will also use that function more often later.\n\n bisect.c | 16 ++++++++++------\n 1 file changed, 10 insertions(+), 6 deletions(-)\n\ndiff --git a/bisect.c b/bisect.c\nindex 76f2445..afdd1c4 100644\n--- a/bisect.c\n+++ b/bisect.c\n@@ -38,6 +38,14 @@ static inline struct node_data *node_data(struct commit *elem)\n \treturn (struct node_data *)elem->util;\n }\n \n+static inline int get_distance(struct commit *commit, int total)\n+{\n+\tint distance = node_data(commit)->weight;\n+\tif (total - distance < distance)\n+\t\tdistance = total - distance;\n+\treturn distance;\n+}\n+\n static int count_distance(struct commit *entry)\n {\n \tint nr = 0;\n@@ -148,9 +156,7 @@ static struct commit_list *best_bisection(struct commit_list *list, int nr)\n \n \t\tif (flags & TREESAME)\n \t\t\tcontinue;\n-\t\tdistance = node_data(p->item)->weight;\n-\t\tif (nr - distance < distance)\n-\t\t\tdistance = nr - distance;\n+\t\tdistance = get_distance(p->item, nr);\n \t\tif (distance > best_distance) {\n \t\t\tbest = p;\n \t\t\tbest_distance = distance;\n@@ -188,9 +194,7 @@ static struct commit_list *best_bisection_sorted(struct commit_list *list, int n\n \n \t\tif (flags & TREESAME)\n \t\t\tcontinue;\n-\t\tdistance = node_data(p->item)->weight;\n-\t\tif (nr - distance < distance)\n-\t\t\tdistance = nr - distance;\n+\t\tdistance = get_distance(p->item, nr);\n \t\tarray[cnt].commit = p->item;\n \t\tarray[cnt].distance = distance;\n \t\tcnt++;\n-- \n2.7.1.354.gd492730.dirty\n"},{"id":"279468","messageId":"1456452282-10325-11-git-send-email-s-beyer@gmx.net","threadId":"41528","inReplyTo":"1456452282-10325-1-git-send-email-s-beyer@gmx.net","subject":"[PATCH 10/16] bisect: introduce distance_direction()","fromName":"Stephan Beyer","fromEmail":"s-beyer@gmx.net","sentAt":"2016-02-26T02:04:36Z","receivedAt":"2016-02-26T02:04:36Z","isPatch":true,"sender":{"key":"s-beyer@gmx.net","avatar":"https://avatars.githubusercontent.com/u/143889?v=4"},"body":"We introduce the concept of rising and falling distances\n(in addition to a halfway distance).\nThis will be useful in subsequent commits.\n\nSigned-off-by: Stephan Beyer \n---\n bisect.c | 33 +++++++++++++++++++++++----------\n 1 file changed, 23 insertions(+), 10 deletions(-)\n\ndiff --git a/bisect.c b/bisect.c\nindex afdd1c4..a09a410 100644\n--- a/bisect.c\n+++ b/bisect.c\n@@ -46,6 +46,28 @@ static inline int get_distance(struct commit *commit, int total)\n \treturn distance;\n }\n \n+/*\n+ * Return -1 if the distance is falling.\n+ * (A falling distance means that the distance of the\n+ * given commit is larger than the distance of its\n+ * child commits.)\n+ * Return 0 if the distance is halfway.\n+ * Return 1 if the distance is rising.\n+ */\n+static inline int distance_direction(struct commit *commit, int total)\n+{\n+\tint doubled_diff = 2 * node_data(commit)->weight - total;\n+\tif (doubled_diff < -1)\n+\t\treturn 1;\n+\tif (doubled_diff > 1)\n+\t\treturn -1;\n+\t/*\n+\t * 2 and 3 are halfway of 5.\n+\t * 3 is halfway of 6 but 2 and 4 are not.\n+\t */\n+\treturn 0;\n+}\n+\n static int count_distance(struct commit *entry)\n {\n \tint nr = 0;\n@@ -92,16 +114,7 @@ static inline int halfway(struct commit *commit, int nr)\n \t */\n \tif (commit->object.flags & TREESAME)\n \t\treturn 0;\n-\t/*\n-\t * 2 and 3 are halfway of 5.\n-\t * 3 is halfway of 6 but 2 and 4 are not.\n-\t */\n-\tswitch (2 * node_data(commit)->weight - nr) {\n-\tcase -1: case 0: case 1:\n-\t\treturn 1;\n-\tdefault:\n-\t\treturn 0;\n-\t}\n+\treturn !distance_direction(commit, nr);\n }\n \n #if !DEBUG_BISECT\n-- \n2.7.1.354.gd492730.dirty\n"},{"id":"279475","messageId":"1456452282-10325-12-git-send-email-s-beyer@gmx.net","threadId":"41528","inReplyTo":"1456452282-10325-1-git-send-email-s-beyer@gmx.net","subject":"[PATCH 11/16] bisect: make total number of commits global","fromName":"Stephan Beyer","fromEmail":"s-beyer@gmx.net","sentAt":"2016-02-26T02:04:37Z","receivedAt":"2016-02-26T02:04:37Z","isPatch":true,"sender":{"key":"s-beyer@gmx.net","avatar":"https://avatars.githubusercontent.com/u/143889?v=4"},"body":"The total number of commits in a bisect process is a property of\nthe bisect process. Making this property global helps to make the code\nclearer.\n\nSigned-off-by: Stephan Beyer \n---\n bisect.c | 74 ++++++++++++++++++++++++++++++++++------------------------------\n 1 file changed, 39 insertions(+), 35 deletions(-)\n\ndiff --git a/bisect.c b/bisect.c\nindex a09a410..3a3a728 100644\n--- a/bisect.c\n+++ b/bisect.c\n@@ -23,6 +23,8 @@ static const char *argv_show_branch[] = {\"show-branch\", NULL, NULL};\n static const char *term_bad;\n static const char *term_good;\n \n+static int total;\n+\n static unsigned marker;\n \n struct node_data {\n@@ -38,7 +40,7 @@ static inline struct node_data *node_data(struct commit *elem)\n \treturn (struct node_data *)elem->util;\n }\n \n-static inline int get_distance(struct commit *commit, int total)\n+static inline int get_distance(struct commit *commit)\n {\n \tint distance = node_data(commit)->weight;\n \tif (total - distance < distance)\n@@ -54,7 +56,7 @@ static inline int get_distance(struct commit *commit, int total)\n * Return 0 if the distance is halfway.\n * Return 1 if the distance is rising.\n */\n-static inline int distance_direction(struct commit *commit, int total)\n+static inline int distance_direction(struct commit *commit)\n {\n \tint doubled_diff = 2 * node_data(commit)->weight - total;\n \tif (doubled_diff < -1)\n@@ -107,25 +109,25 @@ static int count_interesting_parents(struct commit *commit)\n \treturn count;\n }\n \n-static inline int halfway(struct commit *commit, int nr)\n+static inline int halfway(struct commit *commit)\n {\n \t/*\n \t * Don't short-cut something we are not going to return!\n \t */\n \tif (commit->object.flags & TREESAME)\n \t\treturn 0;\n-\treturn !distance_direction(commit, nr);\n+\treturn !distance_direction(commit);\n }\n \n #if !DEBUG_BISECT\n-#define show_list(a,b,c,d) do { ; } while (0)\n+#define show_list(a,b,c) do { ; } while (0)\n #else\n-static void show_list(const char *debug, int counted, int nr,\n+static void show_list(const char *debug, int counted,\n \t\t struct commit_list *list)\n {\n \tstruct commit_list *p;\n \n-\tfprintf(stderr, \"%s (%d/%d)\\n\", debug, counted, nr);\n+\tfprintf(stderr, \"%s (%d/%d)\\n\", debug, counted, total);\n \n \tfor (p = list; p; p = p->next) {\n \t\tstruct commit_list *pp;\n@@ -157,7 +159,7 @@ static void show_list(const char *debug, int counted, int nr,\n }\n #endif /* DEBUG_BISECT */\n \n-static struct commit_list *best_bisection(struct commit_list *list, int nr)\n+static struct commit_list *best_bisection(struct commit_list *list)\n {\n \tstruct commit_list *p, *best;\n \tint best_distance = -1;\n@@ -169,7 +171,7 @@ static struct commit_list *best_bisection(struct commit_list *list, int nr)\n \n \t\tif (flags & TREESAME)\n \t\t\tcontinue;\n-\t\tdistance = get_distance(p->item, nr);\n+\t\tdistance = get_distance(p->item);\n \t\tif (distance > best_distance) {\n \t\t\tbest = p;\n \t\t\tbest_distance = distance;\n@@ -195,10 +197,10 @@ static int compare_commit_dist(const void *a_, const void *b_)\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 {\n \tstruct commit_list *p;\n-\tstruct commit_dist *array = xcalloc(nr, sizeof(*array));\n+\tstruct commit_dist *array = xcalloc(total, sizeof(*array));\n \tint cnt, i;\n \n \tfor (p = list, cnt = 0; p; p = p->next) {\n@@ -207,7 +209,7 @@ static struct commit_list *best_bisection_sorted(struct commit_list *list, int n\n \n \t\tif (flags & TREESAME)\n \t\t\tcontinue;\n-\t\tdistance = get_distance(p->item, nr);\n+\t\tdistance = get_distance(p->item);\n \t\tarray[cnt].commit = p->item;\n \t\tarray[cnt].distance = distance;\n \t\tcnt++;\n@@ -243,7 +245,7 @@ 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, struct node_data *weights,\n+\t\t\t\t\t struct node_data *weights,\n \t\t\t\t\t int find_all)\n {\n \tint n, counted;\n@@ -262,7 +264,7 @@ static struct commit_list *do_find_bisection(struct commit_list *list,\n \t\t\t\tnode_data(commit)->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\t\t counted, list);\n \t\t\t}\n \t\t\t/*\n \t\t\t * otherwise, it is known not to reach any\n@@ -278,7 +280,7 @@ static struct commit_list *do_find_bisection(struct commit_list *list,\n \t\t}\n \t}\n \n-\tshow_list(\"bisection 2 initialize\", counted, nr, list);\n+\tshow_list(\"bisection 2 initialize\", counted, list);\n \n \t/*\n \t * If you have only one parent in the resulting set\n@@ -300,15 +302,15 @@ static struct commit_list *do_find_bisection(struct commit_list *list,\n \t\t\tnode_data(p->item)->weight = count_distance(p->item);\n \n \t\t\t/* Does it happen to be at exactly half-way? */\n-\t\t\tif (!find_all && halfway(p->item, nr))\n+\t\t\tif (!find_all && halfway(p->item))\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+\tshow_list(\"bisection 2 count_distance\", counted, list);\n \n-\twhile (counted < nr) {\n+\twhile (counted < total) {\n \t\tfor (p = list; p; p = p->next) {\n \t\t\tstruct commit_list *q;\n \t\t\tunsigned flags = p->item->object.flags;\n@@ -334,40 +336,41 @@ static struct commit_list *do_find_bisection(struct commit_list *list,\n \t\t\t\tnode_data(p->item)->weight++;\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\t\t counted, list);\n \t\t\t}\n \n \t\t\t/* Does it happen to be at exactly half-way? */\n-\t\t\tif (!find_all && halfway(p->item, nr))\n+\t\t\tif (!find_all && halfway(p->item))\n \t\t\t\treturn p;\n \t\t}\n \t}\n \n-\tshow_list(\"bisection 2 counted all\", counted, nr, list);\n+\tshow_list(\"bisection 2 counted all\", counted, list);\n \n \tif (!find_all)\n-\t\treturn best_bisection(list, nr);\n+\t\treturn best_bisection(list);\n \telse\n-\t\treturn best_bisection_sorted(list, nr);\n+\t\treturn best_bisection_sorted(list);\n }\n \n struct commit_list *find_bisection(struct commit_list *list,\n \t\t\t\t\t int *reaches, int *all,\n \t\t\t\t\t int find_all)\n {\n-\tint nr, on_list;\n+\tint on_list;\n \tstruct commit_list *p, *best, *next, *last;\n \tstruct node_data *weights;\n \n+\ttotal = 0;\n \tmarker = 0;\n \n-\tshow_list(\"bisection 2 entry\", 0, 0, list);\n+\tshow_list(\"bisection 2 entry\", 0, list);\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 */\n-\tfor (nr = on_list = 0, last = NULL, p = list;\n+\tfor (on_list = 0, last = NULL, p = list;\n \t p;\n \t p = next) {\n \t\tunsigned flags = p->item->object.flags;\n@@ -378,23 +381,24 @@ struct commit_list *find_bisection(struct commit_list *list,\n \t\tp->next = last;\n \t\tlast = p;\n \t\tif (!(flags & TREESAME))\n-\t\t\tnr++;\n+\t\t\ttotal++;\n \t\ton_list++;\n \t}\n \tlist = last;\n-\tshow_list(\"bisection 2 sorted\", 0, nr, list);\n+\tshow_list(\"bisection 2 sorted\", 0, list);\n \n-\t*all = nr;\n+\t*all = total;\n \tweights = (struct node_data *)xcalloc(on_list, sizeof(*weights));\n \n \t/* Do the real work of finding bisection commit. */\n-\tbest = do_find_bisection(list, nr, weights, find_all);\n+\tbest = do_find_bisection(list, weights, find_all);\n \tif (best) {\n \t\tif (!find_all)\n \t\t\tbest->next = NULL;\n \t\t*reaches = node_data(best->item)->weight;\n \t}\n \tfree(weights);\n+\n \treturn best;\n }\n \n@@ -931,7 +935,7 @@ int bisect_next_all(const char *prefix, int no_checkout)\n {\n \tstruct rev_info revs;\n \tstruct commit_list *tried;\n-\tint reaches = 0, all = 0, nr, steps;\n+\tint reaches = 0, nr, steps;\n \tconst unsigned char *bisect_rev;\n \n \tread_bisect_terms(&term_bad, &term_good);\n@@ -945,7 +949,7 @@ int bisect_next_all(const char *prefix, int no_checkout)\n \n \tbisect_common(&revs);\n \n-\trevs.commits = find_bisection(revs.commits, &reaches, &all,\n+\trevs.commits = find_bisection(revs.commits, &reaches, &total,\n \t\t\t\t !!skipped_revs.nr);\n \trevs.commits = managed_skipped(revs.commits, &tried);\n \n@@ -963,7 +967,7 @@ int bisect_next_all(const char *prefix, int no_checkout)\n \t\texit(1);\n \t}\n \n-\tif (!all) {\n+\tif (!total) {\n \t\tfprintf(stderr, \"No testable commit found.\\n\"\n \t\t\t\"Maybe you started with bad path parameters?\\n\");\n \t\texit(4);\n@@ -980,8 +984,8 @@ int bisect_next_all(const char *prefix, int no_checkout)\n \t\texit(10);\n \t}\n \n-\tnr = all - reaches - 1;\n-\tsteps = estimate_bisect_steps(all);\n+\tnr = total - reaches - 1;\n+\tsteps = estimate_bisect_steps(total);\n \tprintf(\"Bisecting: %d revision%s left to test after this \"\n \t \"(roughly %d step%s)\\n\", nr, (nr == 1 ? \"\" : \"s\"),\n \t steps, (steps == 1 ? \"\" : \"s\"));\n-- \n2.7.1.354.gd492730.dirty\n"},{"id":"279473","messageId":"1456452282-10325-13-git-send-email-s-beyer@gmx.net","threadId":"41528","inReplyTo":"1456452282-10325-1-git-send-email-s-beyer@gmx.net","subject":"[PATCH 12/16] bisect: rename count_distance() to compute_weight()","fromName":"Stephan Beyer","fromEmail":"s-beyer@gmx.net","sentAt":"2016-02-26T02:04:38Z","receivedAt":"2016-02-26T02:04:38Z","isPatch":true,"sender":{"key":"s-beyer@gmx.net","avatar":"https://avatars.githubusercontent.com/u/143889?v=4"},"body":"Let us use the term \"weight\" for the number of ancestors\nof each commit, and \"distance\" for the number\nmin{weight, #commits - weight}. (Bisect finds the commit\nwith maximum distance.)\n\nIn these terms, \"count_distance()\" is the wrong name of\nthe function. So it is renamed to \"compute_weight()\",\nand it also directly sets the computed weight.\n\nSigned-off-by: Stephan Beyer \n---\n bisect.c | 11 ++++++-----\n 1 file changed, 6 insertions(+), 5 deletions(-)\n\ndiff --git a/bisect.c b/bisect.c\nindex 3a3a728..a9387a7 100644\n--- a/bisect.c\n+++ b/bisect.c\n@@ -70,7 +70,7 @@ static inline int distance_direction(struct commit *commit)\n \treturn 0;\n }\n \n-static int count_distance(struct commit *entry)\n+static int compute_weight(struct commit *entry)\n {\n \tint nr = 0;\n \tstruct commit_list *todo = NULL;\n@@ -93,6 +93,7 @@ static int count_distance(struct commit *entry)\n \t\t}\n \t}\n \n+\tnode_data(entry)->weight = nr;\n \treturn nr;\n }\n \n@@ -241,7 +242,7 @@ static struct commit_list *best_bisection_sorted(struct commit_list *list)\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+ * unknown. After running compute_weight() first, they will get zero\n * or positive distance.\n */\n static struct commit_list *do_find_bisection(struct commit_list *list,\n@@ -286,7 +287,7 @@ static struct commit_list *do_find_bisection(struct commit_list *list,\n \t * If you have only one parent in the resulting set\n \t * then you can reach one commit more than that parent\n \t * can reach. So we do not have to run the expensive\n-\t * count_distance() for single strand of pearls.\n+\t * compute_weight() for single strand of pearls.\n \t *\n \t * However, if you have more than one parent, you cannot\n \t * just add their distance and one for yourself, since\n@@ -299,7 +300,7 @@ static struct commit_list *do_find_bisection(struct commit_list *list,\n \tfor (p = list; p; p = p->next) {\n \t\tif (!(p->item->object.flags & UNINTERESTING)\n \t\t && (node_data(p->item)->weight == -2)) {\n-\t\t\tnode_data(p->item)->weight = count_distance(p->item);\n+\t\t\tcompute_weight(p->item);\n \n \t\t\t/* Does it happen to be at exactly half-way? */\n \t\t\tif (!find_all && halfway(p->item))\n@@ -308,7 +309,7 @@ static struct commit_list *do_find_bisection(struct commit_list *list,\n \t\t}\n \t}\n \n-\tshow_list(\"bisection 2 count_distance\", counted, list);\n+\tshow_list(\"bisection 2 compute_weight\", counted, list);\n \n \twhile (counted < total) {\n \t\tfor (p = list; p; p = p->next) {\n-- \n2.7.1.354.gd492730.dirty\n"},{"id":"279465","messageId":"1456452282-10325-14-git-send-email-s-beyer@gmx.net","threadId":"41528","inReplyTo":"1456452282-10325-1-git-send-email-s-beyer@gmx.net","subject":"[PATCH 13/16] bisect: prepare for different algorithms based on find_all","fromName":"Stephan Beyer","fromEmail":"s-beyer@gmx.net","sentAt":"2016-02-26T02:04:39Z","receivedAt":"2016-02-26T02:04:39Z","isPatch":true,"sender":{"key":"s-beyer@gmx.net","avatar":"https://avatars.githubusercontent.com/u/143889?v=4"},"body":"This is a preparation commit with copy-and-paste involved.\nThe function do_find_bisection() is changed and copied to\ntwo almost similar functions compute_all_weights() and\ncompute_relevant_weights().\n\nThe function compute_relevant_weights() stops when a\n\"halfway\" commit is found.\n\nTo keep the code clean, the halfway commit is not returned\nand has to be found by best_bisection() afterwards.\nThis results in a singular additional O(#commits)-time\noverhead but this will be outweighed by the following\nchanges to compute_relevant_weights().\n\nIt is necessary to keep compute_all_weights() for the\n\"git rev-list --bisect-all\" command. All other bisect-related\ncommands will use compute_relevant_weights().\n\nSigned-off-by: Stephan Beyer \n---\n bisect.c | 116 ++++++++++++++++++++++++++++++++++++++++++++++++++++-----------\n 1 file changed, 97 insertions(+), 19 deletions(-)\n\ndiff --git a/bisect.c b/bisect.c\nindex a9387a7..1d1f61c 100644\n--- a/bisect.c\n+++ b/bisect.c\n@@ -179,6 +179,7 @@ static struct commit_list *best_bisection(struct commit_list *list)\n \t\t}\n \t}\n \n+\tbest->next = NULL;\n \treturn best;\n }\n \n@@ -245,9 +246,8 @@ static struct commit_list *best_bisection_sorted(struct commit_list *list)\n * unknown. After running compute_weight() first, they will get zero\n * or positive distance.\n */\n-static struct commit_list *do_find_bisection(struct commit_list *list,\n-\t\t\t\t\t struct node_data *weights,\n-\t\t\t\t\t int find_all)\n+static void compute_all_weights(struct commit_list *list,\n+\t\t\t\tstruct node_data *weights)\n {\n \tint n, counted;\n \tstruct commit_list *p;\n@@ -301,10 +301,88 @@ static struct commit_list *do_find_bisection(struct commit_list *list,\n \t\tif (!(p->item->object.flags & UNINTERESTING)\n \t\t && (node_data(p->item)->weight == -2)) {\n \t\t\tcompute_weight(p->item);\n+\t\t\tcounted++;\n+\t\t}\n+\t}\n+\n+\tshow_list(\"bisection 2 compute_weight\", counted, list);\n+\n+\twhile (counted < total) {\n+\t\tfor (p = list; p; p = p->next) {\n+\t\t\tstruct commit_list *q;\n+\t\t\tunsigned flags = p->item->object.flags;\n+\n+\t\t\tif (0 <= node_data(p->item)->weight)\n+\t\t\t\tcontinue;\n+\t\t\tfor (q = p->item->parents; q; q = q->next) {\n+\t\t\t\tif (q->item->object.flags & UNINTERESTING)\n+\t\t\t\t\tcontinue;\n+\t\t\t\tif (0 <= node_data(q->item)->weight)\n+\t\t\t\t\tbreak;\n+\t\t\t}\n+\t\t\tif (!q)\n+\t\t\t\tcontinue;\n+\n+\t\t\t/*\n+\t\t\t * weight for p is unknown but q is known.\n+\t\t\t * add one for p itself if p is to be counted,\n+\t\t\t * otherwise inherit it from q directly.\n+\t\t\t */\n+\t\t\tnode_data(p->item)->weight = node_data(q->item)->weight;\n+\t\t\tif (!(flags & TREESAME)) {\n+\t\t\t\tnode_data(p->item)->weight++;\n+\t\t\t\tcounted++;\n+\t\t\t\tshow_list(\"bisection 2 count one\",\n+\t\t\t\t\t counted, list);\n+\t\t\t}\n+\t\t}\n+\t}\n+\tshow_list(\"bisection 2 counted all\", counted, list);\n+}\n+\n+/* At the moment this is basically the same as compute_all_weights()\n+ * but with a halfway shortcut */\n+static void compute_relevant_weights(struct commit_list *list,\n+\t\t\t\t struct node_data *weights)\n+{\n+\tint n, counted;\n+\tstruct commit_list *p;\n+\n+\tcounted = 0;\n+\n+\tfor (n = 0, p = list; p; p = p->next) {\n+\t\tstruct commit *commit = p->item;\n+\t\tunsigned flags = commit->object.flags;\n+\n+\t\tcommit->util = &weights[n++];\n+\t\tswitch (count_interesting_parents(commit)) {\n+\t\tcase 0:\n+\t\t\tif (!(flags & TREESAME)) {\n+\t\t\t\tnode_data(commit)->weight = 1;\n+\t\t\t\tcounted++;\n+\t\t\t\tshow_list(\"bisection 2 count one\",\n+\t\t\t\t\t counted, list);\n+\t\t\t}\n+\t\t\tbreak;\n+\t\tcase 1:\n+\t\t\tnode_data(commit)->weight = -1;\n+\t\t\tbreak;\n+\t\tdefault:\n+\t\t\tnode_data(commit)->weight = -2;\n+\t\t\tbreak;\n+\t\t}\n+\t}\n+\n+\tshow_list(\"bisection 2 initialize\", counted, list);\n+\n+\tfor (p = list; p; p = p->next) {\n+\t\tif (!(p->item->object.flags & UNINTERESTING)\n+\t\t && (node_data(p->item)->weight == -2)) {\n+\t\t\tcompute_weight(p->item);\n \n \t\t\t/* Does it happen to be at exactly half-way? */\n-\t\t\tif (!find_all && halfway(p->item))\n-\t\t\t\treturn p;\n+\t\t\tif (halfway(p->item))\n+\t\t\t\treturn;\n \t\t\tcounted++;\n \t\t}\n \t}\n@@ -341,17 +419,11 @@ static struct commit_list *do_find_bisection(struct commit_list *list,\n \t\t\t}\n \n \t\t\t/* Does it happen to be at exactly half-way? */\n-\t\t\tif (!find_all && halfway(p->item))\n-\t\t\t\treturn p;\n+\t\t\tif (halfway(p->item))\n+\t\t\t\treturn;\n \t\t}\n \t}\n-\n \tshow_list(\"bisection 2 counted all\", counted, list);\n-\n-\tif (!find_all)\n-\t\treturn best_bisection(list);\n-\telse\n-\t\treturn best_bisection_sorted(list);\n }\n \n struct commit_list *find_bisection(struct commit_list *list,\n@@ -365,6 +437,9 @@ struct commit_list *find_bisection(struct commit_list *list,\n \ttotal = 0;\n \tmarker = 0;\n \n+\tif (!list)\n+\t\treturn NULL;\n+\n \tshow_list(\"bisection 2 entry\", 0, list);\n \n \t/*\n@@ -391,13 +466,16 @@ struct commit_list *find_bisection(struct commit_list *list,\n \t*all = total;\n \tweights = (struct node_data *)xcalloc(on_list, sizeof(*weights));\n \n-\t/* Do the real work of finding bisection commit. */\n-\tbest = do_find_bisection(list, weights, find_all);\n-\tif (best) {\n-\t\tif (!find_all)\n-\t\t\tbest->next = NULL;\n-\t\t*reaches = node_data(best->item)->weight;\n+\tif (find_all) {\n+\t\tcompute_all_weights(list, weights);\n+\t\tbest = best_bisection_sorted(list);\n+\t} else {\n+\t\tcompute_relevant_weights(list, weights);\n+\t\tbest = best_bisection(list);\n \t}\n+\tassert(best);\n+\t*reaches = node_data(best->item)->weight;\n+\n \tfree(weights);\n \n \treturn best;\n-- \n2.7.1.354.gd492730.dirty\n"},{"id":"279467","messageId":"1456452282-10325-15-git-send-email-s-beyer@gmx.net","threadId":"41528","inReplyTo":"1456452282-10325-1-git-send-email-s-beyer@gmx.net","subject":"[PATCH 14/16] bisect: use a modified breadth-first search to find relevant weights","fromName":"Stephan Beyer","fromEmail":"s-beyer@gmx.net","sentAt":"2016-02-26T02:04:40Z","receivedAt":"2016-02-26T02:04:40Z","isPatch":true,"sender":{"key":"s-beyer@gmx.net","avatar":"https://avatars.githubusercontent.com/u/143889?v=4"},"body":"The idea is to reverse the DAG and perform a modified breadth-first search\non it, starting on all sources of the reversed DAG.\nBefore each visit of a commit, its weight is induced.\nThis only works for non-merge commits, so the BFS stops prematurely on\nmerge commits (that are collected in a list).\nMerge commits from that collection are considered for further visits\nas soon as all their parents have been visited.\nTheir weights are computed using compute_weight().\nEach BFS walk ends when the computed weight is falling or halfway.\n\nSigned-off-by: Stephan Beyer \n---\n\nIn other words: walk the history up, compute the weight of each\ncommit and stop when you know a better commit cannot follow.\n\nThis way, the expensive \"compute_weight()\" function is not called\non merge commits that will not help to find the maximum distance.\n\nI have to mention that I also had a more complex idea, involving\na binary search on specifically ordered merge commits, and then\ninducing the weights of the commits between those merge commits.\nHowever, this is pretty nontrivial, error-prone by definition,\nand the compute_weight() calls during the binary search can be more\nexpensive than during the \"bottom-up\" BFS walk.\nSo this is clearly the better idea. (And also follows the KISS rule.)\n\nFor the ads: ~3-4 seconds\n\n bisect.c | 246 ++++++++++++++++++++++++++++++++++++++++-----------------------\n 1 file changed, 158 insertions(+), 88 deletions(-)\n\ndiff --git a/bisect.c b/bisect.c\nindex 1d1f61c..827a82a 100644\n--- a/bisect.c\n+++ b/bisect.c\n@@ -30,6 +30,9 @@ static unsigned marker;\n struct node_data {\n \tint weight;\n \tunsigned marked;\n+\tunsigned parents;\n+\tunsigned visited : 1;\n+\tstruct commit_list *children;\n };\n \n #define DEBUG_BISECT 0\n@@ -110,16 +113,6 @@ static int count_interesting_parents(struct commit *commit)\n \treturn count;\n }\n \n-static inline int halfway(struct commit *commit)\n-{\n-\t/*\n-\t * Don't short-cut something we are not going to return!\n-\t */\n-\tif (commit->object.flags & TREESAME)\n-\t\treturn 0;\n-\treturn !distance_direction(commit);\n-}\n-\n #if !DEBUG_BISECT\n #define show_list(a,b,c) do { ; } while (0)\n #else\n@@ -340,90 +333,167 @@ static void compute_all_weights(struct commit_list *list,\n \tshow_list(\"bisection 2 counted all\", counted, list);\n }\n \n-/* At the moment this is basically the same as compute_all_weights()\n- * but with a halfway shortcut */\n+static struct commit_list *build_reversed_dag(struct commit_list *list,\n+\t\t\t\t\t struct node_data *nodes)\n+{\n+\tstruct commit_list *sources = NULL;\n+\tstruct commit_list *p;\n+\tint n = 0;\n+\tfor (p = list; p; p = p->next)\n+\t\tp->item->util = &nodes[n++];\n+\tfor (p = list; p; p = p->next) {\n+\t\tstruct commit_list *parent;\n+\t\tstruct commit *commit = p->item;\n+\t\tfor (parent = commit->parents; parent; parent = parent->next) {\n+\t\t\tif (!(parent->item->object.flags & UNINTERESTING)) {\n+\t\t\t\tstruct commit_list **next = &node_data(parent->item)->children;\n+\t\t\t\tcommit_list_insert(commit, next);\n+\t\t\t\tnode_data(commit)->parents++;\n+\t\t\t}\n+\t\t}\n+\t}\n+\n+\t/* find all sources */\n+\tfor (p = list; p; p = p->next) {\n+\t\tif (node_data(p->item)->parents == 0)\n+\t\t\tcommit_list_insert(p->item, &sources);\n+\t}\n+\n+\treturn sources;\n+}\n+\n+static void commit_list_insert_unique(struct commit *item,\n+\t\t\t\t struct commit_list **list)\n+{\n+\tif (!*list || item < (*list)->item) /* empty list or item will be first */\n+\t\tcommit_list_insert(item, list);\n+\telse if (item != (*list)->item) { /* item will not be first or not inserted */\n+\t\tstruct commit_list *p = *list;\n+\t\tfor (; p->next && p->next->item < item; p = p->next);\n+\t\tif (!p->next || item != p->next->item) /* not already inserted */\n+\t\t\tcommit_list_insert(item, &p->next);\n+\t}\n+}\n+\n+/* do a BFS on the reversed DAG (starting from commits in queue), stop at merge commits */\n+static void bfs_up_to_merges(struct commit_list *queue,\n+\t\t\t struct commit_list **merges)\n+{\n+\tassert(queue);\n+\tstruct commit_list **last;\n+\tfor (last = &queue->next; *last; last = &(*last)->next);\n+\n+\twhile (queue) {\n+\t\tstruct commit *top = queue->item;\n+\t\tstruct commit_list *p;\n+\n+\t\tif (distance_direction(top) > 0) {\n+\t\t\tnode_data(top)->visited = 1;\n+\n+\t\t\t/* queue children */\n+\t\t\tfor (p = node_data(top)->children; p; p = p->next) {\n+\t\t\t\tif (node_data(p->item)->parents > 1) /* child is a merge */\n+\t\t\t\t\tcommit_list_insert_unique(p->item, merges);\n+\t\t\t\telse {\n+\t\t\t\t\tnode_data(p->item)->weight = node_data(top)->weight;\n+\t\t\t\t\tif (!(p->item->object.flags & TREESAME))\n+\t\t\t\t\t\tnode_data(p->item)->weight++;\n+\t\t\t\t\tlast = commit_list_append(p->item, last);\n+\t\t\t\t}\n+\t\t\t}\n+\t\t}\n+\n+\t\tpop_commit(&queue);\n+\t}\n+}\n+\n+static int all_parents_are_visited(struct commit *merge)\n+{\n+\tstruct commit_list *p;\n+\tfor (p = merge->parents; p; p = p->next) {\n+\t\tif (p->item->util && !node_data(p->item)->visited)\n+\t\t\treturn 0;\n+\t}\n+\treturn 1;\n+}\n+\n+static struct commit *extract_merge_to_queue(struct commit_list **merges)\n+{\n+\tassert(merges);\n+\n+\tstruct commit_list *p, *q;\n+\tstruct commit *found;\n+\n+\t/* find a merge that is ready, i.e. all parents have been computed */\n+\tfor (q = NULL, p = *merges; p && !all_parents_are_visited(p->item);\n+\t q = p, p = p->next);\n+\tif (!p)\n+\t\treturn NULL;\n+\n+\t/* remove that commit from the list and return it */\n+\tif (q) {\n+\t\tassert(q->next == p);\n+\t\tq->next = p->next;\n+\t} else /* found first element of list */\n+\t\t*merges = p->next;\n+\tfound = p->item;\n+\tfree(p);\n+\n+\treturn found;\n+}\n+\n+static int find_new_queue_from_merges(struct commit_list **queue,\n+\t\t\t\t struct commit_list **merges)\n+{\n+\tif (*merges) {\n+\t\tstruct commit *merge = extract_merge_to_queue(merges);\n+\t\t*queue = NULL;\n+\t\tif (merge) {\n+\t\t\tcommit_list_insert(merge, queue);\n+\t\t\treturn 1;\n+\t\t}\n+\t}\n+\treturn 0;\n+}\n+\n+static void compute_merge_weights(struct commit_list *merges)\n+{\n+\tstruct commit_list *p;\n+\tfor (p = merges; p; p = p->next)\n+\t\tcompute_weight(p->item);\n+}\n+\n+static void modified_bfs(struct commit_list *queue)\n+{\n+\tstruct commit_list *merges = NULL;\n+\tbfs_up_to_merges(queue, &merges);\n+\twhile (find_new_queue_from_merges(&queue, &merges)) {\n+\t\tcompute_merge_weights(queue);\n+\t\tbfs_up_to_merges(queue, &merges);\n+\t}\n+}\n+\n+/* The idea is to reverse the DAG and perform a modified breadth-first search\n+ * on it, starting on all sources of the reversed DAG.\n+ * Before each visit of a commit, its weight is induced.\n+ * This only works for non-merge commits, so the BFS stops prematurely on\n+ * merge commits (that are collected in a list).\n+ * Merge commits from that collection are considered for further visits\n+ * as soon as all parents have been visited.\n+ * Their weights are computed using compute_weight().\n+ * Each BFS branch ends when the computed weight is falling or halfway.\n+ */\n static void compute_relevant_weights(struct commit_list *list,\n \t\t\t\t struct node_data *weights)\n {\n-\tint n, counted;\n \tstruct commit_list *p;\n+\tstruct commit_list *sources = build_reversed_dag(list, weights);\n \n-\tcounted = 0;\n+\tfor (p = sources; p; p = p->next)\n+\t\tnode_data(p->item)->weight = 1;\n+\tmodified_bfs(sources);\n \n-\tfor (n = 0, p = list; p; p = p->next) {\n-\t\tstruct commit *commit = p->item;\n-\t\tunsigned flags = commit->object.flags;\n-\n-\t\tcommit->util = &weights[n++];\n-\t\tswitch (count_interesting_parents(commit)) {\n-\t\tcase 0:\n-\t\t\tif (!(flags & TREESAME)) {\n-\t\t\t\tnode_data(commit)->weight = 1;\n-\t\t\t\tcounted++;\n-\t\t\t\tshow_list(\"bisection 2 count one\",\n-\t\t\t\t\t counted, list);\n-\t\t\t}\n-\t\t\tbreak;\n-\t\tcase 1:\n-\t\t\tnode_data(commit)->weight = -1;\n-\t\t\tbreak;\n-\t\tdefault:\n-\t\t\tnode_data(commit)->weight = -2;\n-\t\t\tbreak;\n-\t\t}\n-\t}\n-\n-\tshow_list(\"bisection 2 initialize\", counted, list);\n-\n-\tfor (p = list; p; p = p->next) {\n-\t\tif (!(p->item->object.flags & UNINTERESTING)\n-\t\t && (node_data(p->item)->weight == -2)) {\n-\t\t\tcompute_weight(p->item);\n-\n-\t\t\t/* Does it happen to be at exactly half-way? */\n-\t\t\tif (halfway(p->item))\n-\t\t\t\treturn;\n-\t\t\tcounted++;\n-\t\t}\n-\t}\n-\n-\tshow_list(\"bisection 2 compute_weight\", counted, list);\n-\n-\twhile (counted < total) {\n-\t\tfor (p = list; p; p = p->next) {\n-\t\t\tstruct commit_list *q;\n-\t\t\tunsigned flags = p->item->object.flags;\n-\n-\t\t\tif (0 <= node_data(p->item)->weight)\n-\t\t\t\tcontinue;\n-\t\t\tfor (q = p->item->parents; q; q = q->next) {\n-\t\t\t\tif (q->item->object.flags & UNINTERESTING)\n-\t\t\t\t\tcontinue;\n-\t\t\t\tif (0 <= node_data(q->item)->weight)\n-\t\t\t\t\tbreak;\n-\t\t\t}\n-\t\t\tif (!q)\n-\t\t\t\tcontinue;\n-\n-\t\t\t/*\n-\t\t\t * weight for p is unknown but q is known.\n-\t\t\t * add one for p itself if p is to be counted,\n-\t\t\t * otherwise inherit it from q directly.\n-\t\t\t */\n-\t\t\tnode_data(p->item)->weight = node_data(q->item)->weight;\n-\t\t\tif (!(flags & TREESAME)) {\n-\t\t\t\tnode_data(p->item)->weight++;\n-\t\t\t\tcounted++;\n-\t\t\t\tshow_list(\"bisection 2 count one\",\n-\t\t\t\t\t counted, list);\n-\t\t\t}\n-\n-\t\t\t/* Does it happen to be at exactly half-way? */\n-\t\t\tif (halfway(p->item))\n-\t\t\t\treturn;\n-\t\t}\n-\t}\n-\tshow_list(\"bisection 2 counted all\", counted, list);\n+\tshow_list(\"bisection 3 result\", total, list);\n }\n \n struct commit_list *find_bisection(struct commit_list *list,\n-- \n2.7.1.354.gd492730.dirty\n"},{"id":"279469","messageId":"1456452282-10325-16-git-send-email-s-beyer@gmx.net","threadId":"41528","inReplyTo":"1456452282-10325-1-git-send-email-s-beyer@gmx.net","subject":"[PATCH 15/16] bisect: compute best bisection in compute_relevant_weights()","fromName":"Stephan Beyer","fromEmail":"s-beyer@gmx.net","sentAt":"2016-02-26T02:04:41Z","receivedAt":"2016-02-26T02:04:41Z","isPatch":true,"sender":{"key":"s-beyer@gmx.net","avatar":"https://avatars.githubusercontent.com/u/143889?v=4"},"body":"This commit gets rid of the O(#commits) extra overhead of\nthe best_bisection() function.\n\nSigned-off-by: Stephan Beyer \n---\n bisect.c | 43 ++++++++++++++++++-------------------------\n 1 file changed, 18 insertions(+), 25 deletions(-)\n\ndiff --git a/bisect.c b/bisect.c\nindex 827a82a..185a3cf 100644\n--- a/bisect.c\n+++ b/bisect.c\n@@ -27,6 +27,8 @@ static int total;\n \n static unsigned marker;\n \n+static struct commit_list best_bisection;\n+\n struct node_data {\n \tint weight;\n \tunsigned marked;\n@@ -73,6 +75,14 @@ static inline int distance_direction(struct commit *commit)\n \treturn 0;\n }\n \n+static inline void update_best_bisection(struct commit *commit)\n+{\n+\tif (distance_direction(commit) >= 0\n+\t && node_data(commit)->weight > node_data(best_bisection.item)->weight) {\n+\t\tbest_bisection.item = commit;\n+\t}\n+}\n+\n static int compute_weight(struct commit *entry)\n {\n \tint nr = 0;\n@@ -153,29 +163,6 @@ static void show_list(const char *debug, int counted,\n }\n #endif /* DEBUG_BISECT */\n \n-static struct commit_list *best_bisection(struct commit_list *list)\n-{\n-\tstruct commit_list *p, *best;\n-\tint best_distance = -1;\n-\n-\tbest = list;\n-\tfor (p = list; p; p = p->next) {\n-\t\tint distance;\n-\t\tunsigned flags = p->item->object.flags;\n-\n-\t\tif (flags & TREESAME)\n-\t\t\tcontinue;\n-\t\tdistance = get_distance(p->item);\n-\t\tif (distance > best_distance) {\n-\t\t\tbest = p;\n-\t\t\tbest_distance = distance;\n-\t\t}\n-\t}\n-\n-\tbest->next = NULL;\n-\treturn best;\n-}\n-\n struct commit_dist {\n \tstruct commit *commit;\n \tint distance;\n@@ -403,6 +390,7 @@ static void bfs_up_to_merges(struct commit_list *queue,\n \t\t\t}\n \t\t}\n \n+\t\tupdate_best_bisection(top);\n \t\tpop_commit(&queue);\n \t}\n }\n@@ -459,8 +447,10 @@ static int find_new_queue_from_merges(struct commit_list **queue,\n static void compute_merge_weights(struct commit_list *merges)\n {\n \tstruct commit_list *p;\n-\tfor (p = merges; p; p = p->next)\n+\tfor (p = merges; p; p = p->next) {\n \t\tcompute_weight(p->item);\n+\t\tupdate_best_bisection(p->item);\n+\t}\n }\n \n static void modified_bfs(struct commit_list *queue)\n@@ -489,6 +479,9 @@ static void compute_relevant_weights(struct commit_list *list,\n \tstruct commit_list *p;\n \tstruct commit_list *sources = build_reversed_dag(list, weights);\n \n+\tbest_bisection.item = sources->item;\n+\tbest_bisection.next = NULL;\n+\n \tfor (p = sources; p; p = p->next)\n \t\tnode_data(p->item)->weight = 1;\n \tmodified_bfs(sources);\n@@ -541,7 +534,7 @@ struct commit_list *find_bisection(struct commit_list *list,\n \t\tbest = best_bisection_sorted(list);\n \t} else {\n \t\tcompute_relevant_weights(list, weights);\n-\t\tbest = best_bisection(list);\n+\t\tbest = &best_bisection;\n \t}\n \tassert(best);\n \t*reaches = node_data(best->item)->weight;\n-- \n2.7.1.354.gd492730.dirty\n"},{"id":"279462","messageId":"1456452282-10325-17-git-send-email-s-beyer@gmx.net","threadId":"41528","inReplyTo":"1456452282-10325-1-git-send-email-s-beyer@gmx.net","subject":"[PATCH 16/16] bisect: get back halfway shortcut","fromName":"Stephan Beyer","fromEmail":"s-beyer@gmx.net","sentAt":"2016-02-26T02:04:42Z","receivedAt":"2016-02-26T02:04:42Z","isPatch":true,"sender":{"key":"s-beyer@gmx.net","avatar":"https://avatars.githubusercontent.com/u/143889?v=4"},"body":"The documentation says that when the maximum possible distance\nis found, the algorithm stops immediately. That feature is\nreestablished by this commit.\n\nSigned-off-by: Stephan Beyer \n---\n\nIn my tests, I have not seen any gain of performance by\ndoing this... but it's fast now anyway, who cares ;-)\n\n bisect.c | 17 ++++++++++++-----\n 1 file changed, 12 insertions(+), 5 deletions(-)\n\ndiff --git a/bisect.c b/bisect.c\nindex 185a3cf..0153d9a 100644\n--- a/bisect.c\n+++ b/bisect.c\n@@ -363,8 +363,8 @@ static void commit_list_insert_unique(struct commit *item,\n }\n \n /* do a BFS on the reversed DAG (starting from commits in queue), stop at merge commits */\n-static void bfs_up_to_merges(struct commit_list *queue,\n-\t\t\t struct commit_list **merges)\n+static int bfs_up_to_merges(struct commit_list *queue,\n+\t\t\t struct commit_list **merges)\n {\n \tassert(queue);\n \tstruct commit_list **last;\n@@ -391,8 +391,13 @@ static void bfs_up_to_merges(struct commit_list *queue,\n \t\t}\n \n \t\tupdate_best_bisection(top);\n+\t\tif (distance_direction(top) == 0) { // halfway\n+\t\t\tassert(!(top->object.flags & TREESAME));\n+\t\t\treturn 1;\n+\t\t}\n \t\tpop_commit(&queue);\n \t}\n+\treturn 0;\n }\n \n static int all_parents_are_visited(struct commit *merge)\n@@ -456,10 +461,12 @@ static void compute_merge_weights(struct commit_list *merges)\n static void modified_bfs(struct commit_list *queue)\n {\n \tstruct commit_list *merges = NULL;\n-\tbfs_up_to_merges(queue, &merges);\n-\twhile (find_new_queue_from_merges(&queue, &merges)) {\n+\tint halfway_found = bfs_up_to_merges(queue, &merges);\n+\n+\twhile (!halfway_found\n+\t && find_new_queue_from_merges(&queue, &merges)) {\n \t\tcompute_merge_weights(queue);\n-\t\tbfs_up_to_merges(queue, &merges);\n+\t\thalfway_found &= bfs_up_to_merges(queue, &merges);\n \t}\n }\n \n-- \n2.7.1.354.gd492730.dirty\n"},{"id":"279482","messageId":"xmqqr3g0kvzx.fsf@gitster.mtv.corp.google.com","threadId":"41528","inReplyTo":"1456452282-10325-15-git-send-email-s-beyer@gmx.net","subject":"Re: [PATCH 14/16] bisect: use a modified breadth-first search to find relevant weights","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-02-26T03:09:54Z","receivedAt":"2016-02-26T03:09:54Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Stephan Beyer writes:\n\n> The idea is to reverse the DAG and perform a modified breadth-first search\n> on it, starting on all sources of the reversed DAG.\n> Before each visit of a commit, its weight is induced.\n> This only works for non-merge commits, so the BFS stops prematurely on\n> merge commits (that are collected in a list).\n> Merge commits from that collection are considered for further visits\n> as soon as all their parents have been visited.\n> Their weights are computed using compute_weight().\n> Each BFS walk ends when the computed weight is falling or halfway.\n>\n> Signed-off-by: Stephan Beyer \n> ---\n>\n> In other words: walk the history up, compute the weight of each\n> commit and stop when you know a better commit cannot follow.\n>\n> This way, the expensive \"compute_weight()\" function is not called\n> on merge commits that will not help to find the maximum distance.\n\nInteresting. So you walk from the bottom commits, incrementing the\nweight while walking on a part of the graph that is single strand of\npearls, or doing the \"count the reachable ones the hard way\" when\nyou hit a merge [*1*], but either way, once you know the commit you\nare looking at is above the mid-way, i.e. reaches more than half of\nthe graph, then stop walking because its children will never be\nbetter than that commit?\n\nThis is doubly clever idea [*2*]. It cuts the search space in half\nfor one thing, and more importantly, because \"count the reachable\nones the hard way\" counting has to traverse the graph from a merge\nto the bottom boundary, the computation for a merge commit in the\nmore recent half of the history is more expensive than the\ncomputation for a merge comit in the older half of the history, and\nwhat you are avoiding is to waste the cycles on that more expensive\nhalf.\n\nI like it.\n\nI haven't studied the code carefully, but your mention of BFS makes\nme wonder if you can \"narrow\" down the search space even more. In\nan earlier step of the series, you introduced a work queue to\nreplace the recursion. The recursion forces the algorithm to work\nalong the topology of the history, but you have more latitude in\nselecting the commit to dig further with a work queue.\n\nI wonder if you can sort the elements on the work queue based on\ntheir distance (i.e. by using a priority queue). You know the total\nupfront, so you may find a commit whose weight is exactly half of it\nbefore traversing all the bottom half of the history and it may turn\nout to be even more efficient. After all, you are only looking for\njust one such commit, not trying to find all the commits with the\nbest weight.\n\n\n[Footnote]\n\n*1* A merge between a commit that reaches N commits and another that\nreaches M commits may have weight smaller than the sum of N and M,\nand that is why I left the original \"truly stupid algorithm\" Linus\nwrote as-is when I did the obvious optimization for the linear parts\nof the history.\n\n*2* Whenever I revisited the bisection in my head, I thought about\nways to improve that \"truly stupid\" counting, but never thought\nabout an approach to simply reduce the number of times the \"truly\nstupid\" counting has to be done.\n"},{"id":"279483","messageId":"xmqqmvqokvy8.fsf@gitster.mtv.corp.google.com","threadId":"41528","inReplyTo":"1456452282-10325-9-git-send-email-s-beyer@gmx.net","subject":"Re: [PATCH 08/16] bisect: use commit instead of commit list as arguments when appropriate","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-02-26T03:10:55Z","receivedAt":"2016-02-26T03:10:55Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Stephan Beyer writes:\n\n> It makes no sense that the argument for count_distance() and\n> halfway() is a commit list when only its first commit is relevant.\n>\n> Signed-off-by: Stephan Beyer \n> ---\n>\n> This is just some kind of minor code cleanup.\n> The typical \"while at it\", you know it, I guess.\n\nIf you are doing while-at-it, please rename the variable to commit\nor something. \"entry\" refers to one element in the list, but the\nentity the updated code works on is no longer that.\n\n>\n> bisect.c | 16 ++++++++--------\n> 1 file changed, 8 insertions(+), 8 deletions(-)\n>\n> diff --git a/bisect.c b/bisect.c\n> index 6df13b0..76f2445 100644\n> --- a/bisect.c\n> +++ b/bisect.c\n> @@ -38,11 +38,11 @@ static inline struct node_data *node_data(struct commit *elem)\n> \treturn (struct node_data *)elem->util;\n> }\n> \n> -static int count_distance(struct commit_list *entry)\n> +static int count_distance(struct commit *entry)\n> {\n> \tint nr = 0;\n> \tstruct commit_list *todo = NULL;\n> -\tcommit_list_append(entry->item, &todo);\n> +\tcommit_list_append(entry, &todo);\n> \tmarker++;\n> \n> \twhile (todo) {\n> @@ -77,18 +77,18 @@ static int count_interesting_parents(struct commit *commit)\n> \treturn count;\n> }\n> \n> -static inline int halfway(struct commit_list *p, int nr)\n> +static inline int halfway(struct commit *commit, int nr)\n> {\n> \t/*\n> \t * Don't short-cut something we are not going to return!\n> \t */\n> -\tif (p->item->object.flags & TREESAME)\n> +\tif (commit->object.flags & TREESAME)\n> \t\treturn 0;\n> \t/*\n> \t * 2 and 3 are halfway of 5.\n> \t * 3 is halfway of 6 but 2 and 4 are not.\n> \t */\n> -\tswitch (2 * node_data(p->item)->weight - nr) {\n> +\tswitch (2 * node_data(commit)->weight - nr) {\n> \tcase -1: case 0: case 1:\n> \t\treturn 1;\n> \tdefault:\n> @@ -280,10 +280,10 @@ static struct commit_list *do_find_bisection(struct commit_list *list,\n> \tfor (p = list; p; p = p->next) {\n> \t\tif (!(p->item->object.flags & UNINTERESTING)\n> \t\t && (node_data(p->item)->weight == -2)) {\n> -\t\t\tnode_data(p->item)->weight = count_distance(p);\n> +\t\t\tnode_data(p->item)->weight = count_distance(p->item);\n> \n> \t\t\t/* Does it happen to be at exactly half-way? */\n> -\t\t\tif (!find_all && halfway(p, nr))\n> +\t\t\tif (!find_all && halfway(p->item, nr))\n> \t\t\t\treturn p;\n> \t\t\tcounted++;\n> \t\t}\n> @@ -321,7 +321,7 @@ static struct commit_list *do_find_bisection(struct commit_list *list,\n> \t\t\t}\n> \n> \t\t\t/* Does it happen to be at exactly half-way? */\n> -\t\t\tif (!find_all && halfway(p, nr))\n> +\t\t\tif (!find_all && halfway(p->item, nr))\n> \t\t\t\treturn p;\n> \t\t}\n> \t}\n"},{"id":"279486","messageId":"CAP8UFD2szf46skWmgZi3kSkh3D0aeMPw4TagUQa7KZ-z6pHdAA@mail.gmail.com","threadId":"41528","inReplyTo":"1456452282-10325-3-git-send-email-s-beyer@gmx.net","subject":"Re: [PATCH 02/16] bisect: add test for the bisect algorithm","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2016-02-26T06:53:42Z","receivedAt":"2016-02-26T06:53:42Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"On Fri, Feb 26, 2016 at 3:04 AM, Stephan Beyer wrote:\n> Signed-off-by: Stephan Beyer \n> ---\n>\n> To be honest: the test could be better, it could be more \"targeted\",\n> i.e. the example commit history could be smaller and just consider\n> all the cases and corner cases and whatever.\n> However, I made it first to understand the algorithm and verify the\n> description of it in the documentation. Then I was too lazy to\n> improve it. I am sorry that this is no better advertising text. ;)\n>\n> Moreover, the test does not test one important thing that is\n> always cared about in the bisect code: TREESAME commits.\n> Perhaps I got the concept wrong. I tried to obtain TREESAME commits\n> using 'git commit --allow-empty -m \"same tree\"'. However, those\n> commits were never considered being TREESAME. So I gave up (I did\n> not care much.)\n\nI didn't care enough to test TREESAME either.\n\n> Anyone has an idea how to obtain them?\n> Or is this a bug that should be fixed?\n>\n> (Also UNINTERESTING commits are never found by the DEBUG_BISECT\n> output, but I think this is because they are just filtered out.)\n\nYeah, I think so.\n\n> t/t8010-bisect-algorithm.sh | 162 ++++++++++++++++++++++++++++++++++++++++++++\n> 1 file changed, 162 insertions(+)\n> create mode 100755 t/t8010-bisect-algorithm.sh\n>\n> diff --git a/t/t8010-bisect-algorithm.sh b/t/t8010-bisect-algorithm.sh\n> new file mode 100755\n> index 0000000..bda59da\n> --- /dev/null\n> +++ b/t/t8010-bisect-algorithm.sh\n> @@ -0,0 +1,162 @@\n> +#!/bin/sh\n> +#\n> +# Copyright (c) 2016 Stephan Beyer\n> +#\n> +test_description='Tests git bisect algorithm'\n> +\n> +exec +\n> +. ./test-lib.sh\n> +\n> +test_expect_success 'set up a history for the test' '\n> + test_commit A1 A 1 &&\n> + test_commit A2 A 2 &&\n> + test_commit A3 A 3 &&\n> + test_commit A4 A 4 &&\n> + test_commit A5 A 5 &&\n> + test_commit A6 A 6 &&\n> + git checkout -b b A5 &&\n> + test_commit B1 B 1 &&\n> + git checkout master &&\n> + test_commit A7 A 7 &&\n> + git checkout b &&\n> + test_commit B2 B 2 &&\n> + git checkout master &&\n> + test_commit A8 A 8 &&\n> + test_merge Bmerge b &&\n> + git checkout b &&\n> + test_commit B3 B 3 &&\n> + git checkout -b c A7 &&\n> + test_commit C1 C 1 &&\n> + git checkout -b d A3 &&\n> + test_commit D1 D 1 &&\n> + git checkout c &&\n> + test_commit C2 C 2 &&\n> + git checkout d &&\n> + test_commit D2 D 2 &&\n> + git checkout c &&\n> + test_commit C3 C 3 &&\n> + git checkout master &&\n> + git merge -m BCDmerge b c d &&\n> + git tag BCDmerge &&\n> + test_commit A9 A 9 &&\n> + git checkout d &&\n> + test_commit D3 &&\n> + git checkout master\n> +'\n> +\n> +test_expect_success 'bisect algorithm works in linear history with an odd number of commits' '\n> + git bisect start A7 &&\n> + git bisect next &&\n> + test \"$(git rev-parse HEAD)\" = \"$(git rev-parse A3)\" \\\n> + -o \"$(git rev-parse HEAD)\" = \"$(git rev-parse A4)\"\n\nI thought that we should not use \"-o\" and \"-a\" but instead \"|| test\"\nand \"&& test\".\n\n> +'\n> +\n> +test_expect_success 'bisect algorithm works in linear history with an even number of commits' '\n> + git bisect reset &&\n> + git bisect start A8 &&\n> + git bisect next &&\n> + test \"$(git rev-parse HEAD)\" = \"$(git rev-parse A4)\"\n> +'\n> +\n> +test_expect_success 'bisect algorithm works with a merge' '\n> + git bisect reset &&\n> + git bisect start Bmerge &&\n> + git bisect next &&\n> + test \"$(git rev-parse HEAD)\" = \"$(git rev-parse A5)\" &&\n> + git bisect good &&\n> + test \"$(git rev-parse HEAD)\" = \"$(git rev-parse A8)\" &&\n> + git bisect good &&\n> + test \"$(git rev-parse HEAD)\" = \"$(git rev-parse B2)\" \\\n> + -o \"$(git rev-parse HEAD)\" = \"$(git rev-parse B1)\"\n\nHere and in other places too...\n"},{"id":"279494","messageId":"CA+P7+xqRFvzvD3dX+WM9vuJ1mmSdMeoQQTat+4be0gfsLXfSJw@mail.gmail.com","threadId":"41528","inReplyTo":"1456452282-10325-2-git-send-email-s-beyer@gmx.net","subject":"Re: [PATCH 01/16] bisect: write about `bisect next` in documentation","fromName":"Jacob Keller","fromEmail":"jacob.keller@gmail.com","sentAt":"2016-02-26T08:02:06Z","receivedAt":"2016-02-26T08:02:06Z","isPatch":true,"sender":{"key":"jacob.keller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/874719?v=4"},"body":"On Thu, Feb 25, 2016 at 6:04 PM, Stephan Beyer wrote:\n> This patch considers the source code comment that says to be\n> \"not sure we want 'next' at the UI level anymore\", and replies with\n> \"Yes, we want it!\". Therefore, the \"git bisect next\" functionality\n> is explicitly motivated and documented.\n>\n\nI did not know about this, but I definitely would have found it useful\nin the past.\n\nThanks,\nJake\n"},{"id":"279548","messageId":"xmqqoab3jokp.fsf@gitster.mtv.corp.google.com","threadId":"41528","inReplyTo":"1456452282-10325-2-git-send-email-s-beyer@gmx.net","subject":"Re: [PATCH 01/16] bisect: write about `bisect next` in documentation","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-02-26T18:47:50Z","receivedAt":"2016-02-26T18:47:50Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Stephan Beyer writes:\n\n> +Bisect next\n> +~~~~~~~~~~~\n> +\n> +Sometimes it can be necessary to check out other branches during a bisect\n> +session. If you want to check out the next commit of the bisection again,\n> +simply issue the command:\n> +\n> +------------\n> +$ git bisect next\n> +------------\n\nHmph, I am not quite sure what you mean by checking out other\nbranches during a bisect session.\n\nDuring bisection, you are on a detached HEAD with refs/bisect/*\nholding the current state, and \"next\" indeed is a way to recompute\nthe commit to be tested based on that state.\n\nBut I wonder if it is safe and sane to encourage \"checking out other\nbranches during a bisect session.\" as you cannot tell what other\ncrazy things they will do while on \"other branches\". I do not think\nwe even try to (and I do not think we should) handle a case where\nthe user tries to merge another branch, sees conflicts and says\n\"bisect next\" without cleaning up, for example.\n\n> +Another typical use case of this command is when you have marked a commit\n> +as bad but you do not know a good commit. Instead of crawling through the\n> +history yourself, let this command check out a commit for you.\n\nI would say this is the only sensible use of \"next\", but as you\ncannot see ;-) in the comment from the pre-context of the patch\nbelow, \"have bad but not good. we could bisect althoguh this is less\noptimum.\", I am not sure if it is a good idea to say \"is also helpful\"\nas if we are encouraging such a usage.\n\n> OPTIONS\n> -------\n> --no-checkout::\n> diff --git a/git-bisect.sh b/git-bisect.sh\n> index 5d1cb00..5c93a27 100755\n> --- a/git-bisect.sh\n> +++ b/git-bisect.sh\n> @@ -334,16 +334,10 @@ bisect_next_check() {\n> \t*)\n> \t\tbad_syn=$(bisect_voc bad)\n> \t\tgood_syn=$(bisect_voc good)\n> -\t\tif test -s \"$GIT_DIR/BISECT_START\"\n> -\t\tthen\n> -\n> -\t\t\teval_gettextln \"You need to give me at least one \\$bad_syn and one \\$good_syn revision.\n> -(You can use \\\"git bisect \\$bad_syn\\\" and \\\"git bisect \\$good_syn\\\" for that.)\" >&2\n> -\t\telse\n> -\t\t\teval_gettextln \"You need to start by \\\"git bisect start\\\".\n> -You then need to give me at least one \\$good_syn and one \\$bad_syn revision.\n> -(You can use \\\"git bisect \\$bad_syn\\\" and \\\"git bisect \\$good_syn\\\" for that.)\" >&2\n> -\t\tfi\n> +\t\teval_gettextln \"You need to give me at least one \\$bad_syn revision.\n> +Use \\\"git bisect \\$bad_syn\\\" for that. One \\$good_syn revision is also helpful\n> +for bisecting (use \\\"git bisect \\$good_syn\\\"). If you do not know one \\$good_syn\n> +revision, you can use \\\"git bisect next\\\" to find one.\" >&2\n> \t\texit 1 ;;\n> \tesac\n> }\n> @@ -677,7 +671,6 @@ case \"$#\" in\n> \tskip)\n> \t\tbisect_skip \"$@\" ;;\n> \tnext)\n> -\t\t# Not sure we want \"next\" at the UI level anymore.\n> \t\tbisect_next \"$@\" ;;\n> \tvisualize|view)\n> \t\tbisect_visualize \"$@\" ;;\n"},{"id":"279567","messageId":"56D0BBB4.9020305@gmx.net","threadId":"41528","inReplyTo":"xmqqr3g0kvzx.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH 14/16] bisect: use a modified breadth-first search to find relevant weights","fromName":"Stephan Beyer","fromEmail":"s-beyer@gmx.net","sentAt":"2016-02-26T20:55:16Z","receivedAt":"2016-02-26T20:55:16Z","isPatch":true,"sender":{"key":"s-beyer@gmx.net","avatar":"https://avatars.githubusercontent.com/u/143889?v=4"},"body":"Hi,\n\nOn 02/26/2016 04:09 AM, Junio C Hamano wrote:\n> Interesting. So you walk from the bottom commits, incrementing the\n> weight while walking on a part of the graph that is single strand of\n> pearls, or doing the \"count the reachable ones the hard way\" when\n> you hit a merge [*1*], but either way, once you know the commit you\n> are looking at is above the mid-way, i.e. reaches more than half of\n> the graph, then stop walking because its children will never be\n> better than that commit?\n\nExactly. Maybe that's an even better description for the commit message l-)\n\n> I haven't studied the code carefully, but your mention of BFS makes\n> me wonder if you can \"narrow\" down the search space even more.\n\nI had an idea that aimed at accomplishing this by finding the\nhighest-distance merge commit using binary search. (The BFS collected\nall merge commits, in that order, then you could do binary search.)\nSo you have O(log(#mergecommits)) \"do it the hard way\" weight computations.\nHowever, in the worst case (or even in every case, I did not thoroughly\nthink about the cases that can occur), it could happen that it also had\nto do these \"do it the hard way\" computations for all merge commits with\nsmaller weight... That's why I dropped this idea in favor of the more\nsimple approach that I sent to the list.\n\n> In an earlier step of the series, you introduced a work queue to\n> replace the recursion. The recursion forces the algorithm to work\n> along the topology of the history, but you have more latitude in\n> selecting the commit to dig further with a work queue.\n> \n> I wonder if you can sort the elements on the work queue based on\n> their distance (i.e. by using a priority queue). You know the total\n> upfront, so you may find a commit whose weight is exactly half of it\n> before traversing all the bottom half of the history and it may turn\n> out to be even more efficient. After all, you are only looking for\n> just one such commit, not trying to find all the commits with the\n> best weight.\n\nFor the compute_weight() function (the \"doing it the hard way\"\nfunction), this would not make sense since all parent commits (of a\nmerge commit we call compute_weight() on) will have smaller distance.\n\nHowever, your idea can help:\nI just noticed that it's not important that I use a *B*FS because of the\nacyclity. So I could also use a DFS that is \"more greedy\" going towards\nhigh numbers.\nNote that the traversal is always on trees because the merge commits are\ncut out. So whenever a branching (a commit with more than one child)\noccurs, the DFS should follow the branch of maximum length to its leaf.\n(These maximum lengths can be saved during build_reversed_dag().)\nThen, if there is a halfway commit, we stop. If not, we can just go on\nwith the remaining DFS...\nI think I only rethought and rephrased your idea. :) Sounds good to me.\nI'm going to add commits for that.\n\n> [Footnote]\n> \n> *1* A merge between a commit that reaches N commits and another that\n> reaches M commits may have weight smaller than the sum of N and M,\n> and that is why I left the original \"truly stupid algorithm\" Linus\n> wrote as-is when I did the obvious optimization for the linear parts\n> of the history.\n\nYes. In fact, the \"truly stupid algorithm\" is not truly stupid. I'm not\nquite sure, but I think it's still the best algorithm known so far for\nthat problem. (But maybe the problem is just not very interesting in\nscience.)\n\n> *2* Whenever I revisited the bisection in my head, I thought about\n> ways to improve that \"truly stupid\" counting, but never thought\n> about an approach to simply reduce the number of times the \"truly\n> stupid\" counting has to be done.\n\nWell, I also improved that \"truly stupid\" counting a little in a former\ncommit (patch 7). But it's just the implementation that I improved\n(time/memory trade-off), not the algorithm. :)\n\nCheers,\n Stephan\n"},{"id":"279569","messageId":"56D0C5E0.2020703@gmx.net","threadId":"41528","inReplyTo":"CAP8UFD2szf46skWmgZi3kSkh3D0aeMPw4TagUQa7KZ-z6pHdAA@mail.gmail.com","subject":"Re: [PATCH 02/16] bisect: add test for the bisect algorithm","fromName":"Stephan Beyer","fromEmail":"s-beyer@gmx.net","sentAt":"2016-02-26T21:38:40Z","receivedAt":"2016-02-26T21:38:40Z","isPatch":true,"sender":{"key":"s-beyer@gmx.net","avatar":"https://avatars.githubusercontent.com/u/143889?v=4"},"body":"Hi Christian,\n\nOn 02/26/2016 07:53 AM, Christian Couder wrote:\n>> +test_expect_success 'bisect algorithm works in linear history with an odd number of commits' '\n>> + git bisect start A7 &&\n>> + git bisect next &&\n>> + test \"$(git rev-parse HEAD)\" = \"$(git rev-parse A3)\" \\\n>> + -o \"$(git rev-parse HEAD)\" = \"$(git rev-parse A4)\"\n> \n> I thought that we should not use \"-o\" and \"-a\" but instead \"|| test\"\n> and \"&& test\".\n\nWhy is this? I understand the && instead of -a thing (test atomicity),\nhowever, for || this results in an ugly\n\n+ git bisect next &&\n+ ( test \"$(git rev-parse HEAD)\" = \"$(git rev-parse A3)\" ||\n+ test \"$(git rev-parse HEAD)\" = \"$(git rev-parse A4)\" )\n\nRight? (Otherwise a failure of e.g. \"git bisect start A7\" would run\nthe command after || (which may still be fine in some cases but is wrong\nin most of the other cases).\n\nHowever, what do you think about this?\n\ndiff --git a/t/t8010-bisect-algorithm.sh b/t/t8010-bisect-algorithm.sh\nindex bda59da..ae50e7c 100755\n--- a/t/t8010-bisect-algorithm.sh\n+++ b/t/t8010-bisect-algorithm.sh\n@@ -8,6 +8,16 @@ exec wrote:\n> Hi Christian,\n>\n> On 02/26/2016 07:53 AM, Christian Couder wrote:\n>>> +test_expect_success 'bisect algorithm works in linear history with an odd number of commits' '\n>>> + git bisect start A7 &&\n>>> + git bisect next &&\n>>> + test \"$(git rev-parse HEAD)\" = \"$(git rev-parse A3)\" \\\n>>> + -o \"$(git rev-parse HEAD)\" = \"$(git rev-parse A4)\"\n>>\n>> I thought that we should not use \"-o\" and \"-a\" but instead \"|| test\"\n>> and \"&& test\".\n>\n> Why is this?\n\nI think it is because it might not be very portable, but I am not sure\nI remember well the previous discussions about this.\n\n> I understand the && instead of -a thing (test atomicity),\n> however, for || this results in an ugly\n>\n> + git bisect next &&\n> + ( test \"$(git rev-parse HEAD)\" = \"$(git rev-parse A3)\" ||\n> + test \"$(git rev-parse HEAD)\" = \"$(git rev-parse A4)\" )\n>\n> Right? (Otherwise a failure of e.g. \"git bisect start A7\" would run\n> the command after || (which may still be fine in some cases but is wrong\n> in most of the other cases).\n\nYeah.\n\nBy the way maybe t6030-bisect-porcelain.sh is paranoid, but it does\nsome of those checks like:\n\n HASH4=$(git rev-parse --verify HEAD)\n\nand later:\n\n rev_hash4=$(git rev-parse --verify HEAD) &&\n test \"$rev_hash4\" = \"$HASH4\" &&\n\nSo it uses \"--verify\" and also often puts the \"git rev-parse\" on a\nseparate line...\n\n> However, what do you think about this?\n>\n> diff --git a/t/t8010-bisect-algorithm.sh b/t/t8010-bisect-algorithm.sh\n> index bda59da..ae50e7c 100755\n> --- a/t/t8010-bisect-algorithm.sh\n> +++ b/t/t8010-bisect-algorithm.sh\n> @@ -8,6 +8,16 @@ exec \n> . ./test-lib.sh\n>\n> +test_compare_rev () {\n> + arg=\"$(git rev-parse \"$1\")\"\n\n...hence I would suggest:\n\n arg=\"$(git rev-parse --verify \"$1\")\" || return\n\n> + shift\n> + for rev\n> + do\n> + test \"$arg\" = \"$(git rev-parse \"$rev\")\" && return 0\n\n...and:\n\n hash=\"$(git rev-parse --verify \"$rev\")\" || return\n test \"$arg\" = \"$hash\" && return 0\n\n> + done\n> + return 1\n> +}\n\nOtherwise I like test_compare_rev().\n\nThanks,\nChristian.\n"},{"id":"279638","messageId":"vpqd1riqq7o.fsf@anie.imag.fr","threadId":"41528","inReplyTo":"CAP8UFD27f3zmrLrvyCuMfs6ijt7MtLB8rX0Ykvfar3kidpm6LQ@mail.gmail.com","subject":"Re: [PATCH 02/16] bisect: add test for the bisect algorithm","fromName":"Matthieu Moy","fromEmail":"matthieu.moy@grenoble-inp.fr","sentAt":"2016-02-27T12:42:51Z","receivedAt":"2016-02-27T12:42:51Z","isPatch":true,"sender":{"key":"matthieu.moy@grenoble-inp.fr","avatar":"https://gravatar.com/avatar/72c8a2705971a25dfaff23cece15130d405685845d911aedd5667ace277f3fc5?d=mp&s=160"},"body":"Christian Couder writes:\n\n> Hi Stephan,\n>\n> On Fri, Feb 26, 2016 at 10:38 PM, Stephan Beyer wrote:\n>> Hi Christian,\n>>\n>> On 02/26/2016 07:53 AM, Christian Couder wrote:\n>>>> +test_expect_success 'bisect algorithm works in linear history with an odd number of commits' '\n>>>> + git bisect start A7 &&\n>>>> + git bisect next &&\n>>>> + test \"$(git rev-parse HEAD)\" = \"$(git rev-parse A3)\" \\\n>>>> + -o \"$(git rev-parse HEAD)\" = \"$(git rev-parse A4)\"\n>>>\n>>> I thought that we should not use \"-o\" and \"-a\" but instead \"|| test\"\n>>> and \"&& test\".\n>>\n>> Why is this?\n>\n> I think it is because it might not be very portable, but I am not sure\n> I remember well the previous discussions about this.\n\nSee Documentation/CodingGuidelines:\n\n - We do not write our \"test\" command with \"-a\" and \"-o\" and use \"&&\"\n or \"||\" to concatenate multiple \"test\" commands instead, because\n the use of \"-a/-o\" is often error-prone. E.g.\n\n test -n \"$x\" -a \"$a\" = \"$b\"\n\n is buggy and breaks when $x is \"=\", but\n\n test -n \"$x\" && test \"$a\" = \"$b\"\n\n does not have such a problem.\n\nRegarding portability, test -a/-o is not strictly POSIX (it's in the XSI\nextension), but AFAIK implemented by all reasonable shells.\n\n-- \nMatthieu Moy\nhttp://www-verimag.imag.fr/~moy/\n"},{"id":"279642","messageId":"56D1A873.1090709@gmx.net","threadId":"41528","inReplyTo":"xmqqoab3jokp.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH 01/16] bisect: write about `bisect next` in documentation","fromName":"Stephan Beyer","fromEmail":"s-beyer@gmx.net","sentAt":"2016-02-27T13:45:23Z","receivedAt":"2016-02-27T13:45:23Z","isPatch":true,"sender":{"key":"s-beyer@gmx.net","avatar":"https://avatars.githubusercontent.com/u/143889?v=4"},"body":"Hi,\n\nOn 02/26/2016 07:47 PM, Junio C Hamano wrote:\n> But I wonder if it is safe and sane to encourage \"checking out other\n> branches during a bisect session.\" as you cannot tell what other\n> crazy things they will do while on \"other branches\". I do not think\n> we even try to (and I do not think we should) handle a case where\n> the user tries to merge another branch, sees conflicts and says\n> \"bisect next\" without cleaning up, for example.\n\nI rephrase it as follows to not encourage checking out another branch\n(or commit ;]) but to mention that it works to get back if someone\naccidentally did it.\n\n--8<--8<--8<--\n\nBisect next\n~~~~~~~~~~~\n\nIn case you have marked a commit as bad but you do not know a good\ncommit, you do not have to crawl through the commit history yourself to\nfind a good commit. Simply issue the command:\n\n------------\n$ git bisect next\n------------\n\nThis command is also handy when you accidentally checked out another\ncommit during a bisection. It computes the commit for the bisection\nand checks it out again.\n\n-->8-->8-->8--\n\nIs that better?\n\nThanks,\nStephan\n"},{"id":"279656","messageId":"xmqqk2lqghdw.fsf@gitster.mtv.corp.google.com","threadId":"41528","inReplyTo":"56D1A873.1090709@gmx.net","subject":"Re: [PATCH 01/16] bisect: write about `bisect next` in documentation","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-02-27T18:03:39Z","receivedAt":"2016-02-27T18:03:39Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Stephan Beyer writes:\n\n> I rephrase it as follows to not encourage checking out another branch\n> (or commit ;]) but to mention that it works to get back if someone\n> accidentally did it.\n>\n> --8<--8<--8<--\n>\n> Bisect next\n> ~~~~~~~~~~~\n>\n> In case you have marked a commit as bad but you do not know a good\n> commit, you do not have to crawl through the commit history yourself to\n> find a good commit. Simply issue the command:\n>\n> ------------\n> $ git bisect next\n> ------------\n>\n> This command is also handy when you accidentally checked out another\n> commit during a bisection. It computes the commit for the bisection\n> and checks it out again.\n>\n> -->8-->8-->8--\n>\n> Is that better?\n\nThanks, I think it is definitely better than the original patch.\n\nI cannot say it is better than not having that extra paragraph,\nthough. An immediate recovery after an accidental checkout can be\ndone with \"git checkout -\", and the only case \"bisect next\" is safe\nand better is somebody accidentally checked multiple random commits\nout without doing anything else (in which case you'd need to ask\nreflog where the HEAD was in order to use \"checkout\" to go back).\n\nBut if they are doing more than just a single \"checkout\" immediately\nfollowed by \"oops that wasn't what I intended--now I want to go\nback\", they need more than \"bisect next\" or \"checkout $somewhere\"\nanyway, so...\n"},{"id":"279669","messageId":"56D1FB53.2020404@gmx.net","threadId":"41528","inReplyTo":"xmqqk2lqghdw.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH 01/16] bisect: write about `bisect next` in documentation","fromName":"Stephan Beyer","fromEmail":"s-beyer@gmx.net","sentAt":"2016-02-27T19:38:59Z","receivedAt":"2016-02-27T19:38:59Z","isPatch":true,"sender":{"key":"s-beyer@gmx.net","avatar":"https://avatars.githubusercontent.com/u/143889?v=4"},"body":"Hi,\n\nOn 02/27/2016 07:03 PM, Junio C Hamano wrote:\n> Stephan Beyer writes:\n> \n>> This command is also handy when you accidentally checked out another\n>> commit during a bisection. It computes the commit for the bisection\n>> and checks it out again.\n>>\n>> -->8-->8-->8--\n>>\n>> Is that better?\n> \n> Thanks, I think it is definitely better than the original patch.\n> \n> I cannot say it is better than not having that extra paragraph,\n> though.\n\nOkay, I will remove that extra paragraph.\n\nHowever, it probably should be documented what \"git bisect next\" does\nafter you've specified bad and good commits.\n\nFor that, I'd like to have an extra informational paragraph.\nWhat about: \"In general, the command computes the next commit for the\nbisection and checks it out.\"\nThis would be neutral, in the meaning that no use case is involved.\n\nAnother more \"strict\" choice could be to change the behavior such that\n\"git bisect next\" dies when invoked after a good (and a bad) commit is\nspecified. In that case, there is no need to document the behavior ;-)\nHowever, in that case the name of \"git bisect next\" would be wrong...\n\nCheers,\nStephan\n"},{"id":"279722","messageId":"xmqqbn70g048.fsf@gitster.mtv.corp.google.com","threadId":"41528","inReplyTo":"56D1FB53.2020404@gmx.net","subject":"Re: [PATCH 01/16] bisect: write about `bisect next` in documentation","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-02-28T18:28:55Z","receivedAt":"2016-02-28T18:28:55Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Stephan Beyer writes:\n\n> However, it probably should be documented what \"git bisect next\" does\n> after you've specified bad and good commits.\n>\n> For that, I'd like to have an extra informational paragraph.\n> What about: \"In general, the command computes the next commit for the\n> bisection and checks it out.\"\n> This would be neutral, in the meaning that no use case is involved.\n\nGood thinking. Thanks for being careful; I often pretend to take an\nextreme position to invite a well-thought-out rebuttal, and I really\nlike it when people respond with a good counter-proposal.\n"},{"id":"281302","messageId":"CAFZEwPPon1q_iW_xNfmVxiQhyaQh_pZpk2jzoyzi3RjJd998pg@mail.gmail.com","threadId":"41528","inReplyTo":"1456452282-10325-1-git-send-email-s-beyer@gmx.net","subject":"Re: [PATCH 00/16] git bisect improvements","fromName":"Pranit Bauva","fromEmail":"pranit.bauva@gmail.com","sentAt":"2016-03-20T18:50:38Z","receivedAt":"2016-03-20T18:50:38Z","isPatch":true,"sender":{"key":"pranit.bauva@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2959938?v=4"},"body":"I have been recently following this series of patches and it seems a\nbit stale. These patches haven't been followed up with improvement\npatches. If it is okay with you then can I work more upon these\npatches in my GSoC project. These really seem interesting and Git\ncould really benefit from this.\n\nRegards,\nPranit Bauva\n\nOn Fri, Feb 26, 2016 at 7:34 AM, Stephan Beyer wrote:\n> Hi,\n>\n> this set of patches provides improvements for git bisect.\n>\n> Quick summary of changes\n> - relevant for users:\n> - `git bisect next` is documented and motivated\n> - git bisect implementation becomes much faster\n> (or: is now working) for big repositories**\n> - relevant for developers:\n> - a test for the git bisect algorithm is added\n> - fix: bisect.c compiles also if DEBUG_BISECT is set\n>\n> The ** marked change is the most interesting one.\n> To be more accurate: the use case is when you want to bisect in a\n> repository with a huge amount of merge commits (and having these\n> merge commits relevant for the actual bisect process).\n> For example, a bisect in the whole git master branch took\n> ~50 seconds, now it takes ~4 seconds.\n>\n>\n> Note that the patches have finer granularity (especially the performance\n> improvements are splitted into several preparing commits).\n> For some patches, there is some more patch-related story as\n> \"cover letter material\" in these patches.\n>\n> Btw: I also wondered about the internationalizaton: no string in bisect.c\n> is marked for translation. Intentionally?\n>\n> Cheers\n>\n> Stephan Beyer (16):\n> bisect: write about `bisect next` in documentation\n> bisect: add test for the bisect algorithm\n> bisect: make bisect compile if DEBUG_BISECT is set\n> bisect: make algorithm behavior independent of DEBUG_BISECT\n> bisect: get rid of recursion in count_distance()\n> bisect: use struct node_data array instead of int array\n> bisect: replace clear_distance() by unique markers\n> bisect: use commit instead of commit list as arguments when\n> appropriate\n> bisect: extract get_distance() function from code duplication\n> bisect: introduce distance_direction()\n> bisect: make total number of commits global\n> bisect: rename count_distance() to compute_weight()\n> bisect: prepare for different algorithms based on find_all\n> bisect: use a modified breadth-first search to find relevant weights\n> bisect: compute best bisection in compute_relevant_weights()\n> bisect: get back halfway shortcut\n>\n> Documentation/git-bisect.txt | 25 +++\n> bisect.c | 473 ++++++++++++++++++++++++++++---------------\n> git-bisect.sh | 15 +-\n> t/t8010-bisect-algorithm.sh | 162 +++++++++++++++\n> 4 files changed, 502 insertions(+), 173 deletions(-)\n> create mode 100755 t/t8010-bisect-algorithm.sh\n>\n> --\n> 2.7.1.354.gd492730.dirty\n>\n> --\n> To unsubscribe from this list: send the line \"unsubscribe git\" in\n> the body of a message to majordomo@vger.kernel.org\n> More majordomo info at http://vger.kernel.org/majordomo-info.html\n"},{"id":"281395","messageId":"56F07434.8090005@gmx.net","threadId":"41528","inReplyTo":"CAFZEwPPon1q_iW_xNfmVxiQhyaQh_pZpk2jzoyzi3RjJd998pg@mail.gmail.com","subject":"Re: [PATCH 00/16] git bisect improvements","fromName":"Stephan Beyer","fromEmail":"s-beyer@gmx.net","sentAt":"2016-03-21T22:22:44Z","receivedAt":"2016-03-21T22:22:44Z","isPatch":true,"sender":{"key":"s-beyer@gmx.net","avatar":"https://avatars.githubusercontent.com/u/143889?v=4"},"body":"Hi Pranit,\n\nOn 03/20/2016 07:50 PM, Pranit Bauva wrote:\n> I have been recently following this series of patches and it seems a\n> bit stale. These patches haven't been followed up with improvement\n> patches.\n\nI'm on vacation at the moment.\n\nPatchset v1 contains some bugs. So I just updated the branch on\ngithub[1] for you which is the state-of-the-art for patchset v2. Note\nthat it also contains an odd bug (which seems to exist before my patches\nbut turns to light after my patches) but I haven't found time to\ninvestigate it further before my vacation started. (That's also why I\ndidn't post any updates on that topic to the list.)\n\n1. https://github.com/sbeyer/git/commits/bisect\n\nAlso sorry, I am not following the list so I didn't know there was a\nGSoC project for bisect.\n\n> If it is okay with you then can I work more upon these\n> patches in my GSoC project.\n\nI'm totally fine with that, of course. :)\n\nThanks,\nStephan\n"},{"id":"281414","messageId":"CAP8UFD1wneDoLcQp0R-8Y17V0Tzo6d_hxY=k8v5dKOgP10ecRA@mail.gmail.com","threadId":"41528","inReplyTo":"56F07434.8090005@gmx.net","subject":"Re: [PATCH 00/16] git bisect improvements","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2016-03-22T07:35:33Z","receivedAt":"2016-03-22T07:35:33Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"On Mon, Mar 21, 2016 at 11:22 PM, Stephan Beyer wrote:\n>\n> Also sorry, I am not following the list so I didn't know there was a\n> GSoC project for bisect.\n>\n>> If it is okay with you then can I work more upon these\n>> patches in my GSoC project.\n>\n> I'm totally fine with that, of course. :)\n\nYou are the Stephan Beyer who did a GSoC project on the sequencer\naround 2009, right?\n\nIt's nice to see you back on the list :-)\n"},{"id":"281427","messageId":"CAFZEwPOiUWDZKprWW4q3diUUvauc2epJHVD64qjCi_3S8KBWMQ@mail.gmail.com","threadId":"41528","inReplyTo":"56F07434.8090005@gmx.net","subject":"Re: [PATCH 00/16] git bisect improvements","fromName":"Pranit Bauva","fromEmail":"pranit.bauva@gmail.com","sentAt":"2016-03-22T11:35:14Z","receivedAt":"2016-03-22T11:35:14Z","isPatch":true,"sender":{"key":"pranit.bauva@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2959938?v=4"},"body":"On Tue, Mar 22, 2016 at 3:52 AM, Stephan Beyer wrote:\n>> If it is okay with you then can I work more upon these\n>> patches in my GSoC project.\n>\n> I'm totally fine with that, of course. :)\n\nThanks! :)\nI will try and fix the left over bug if time persists.\n\nRegards,\nPranit Bauva\n"}]}