{"thread":{"id":"19668","subject":"[PATCH v2 1/3] bisect: add parameters to \"filter_skipped\"","startedAt":"2009-06-05T04:10:40Z","lastAt":"2009-06-06T05:19:32Z","messageCount":9,"participants":["Christian Couder","Junio C Hamano"],"isPatch":true,"patchVersion":2,"patchTotal":3},"messages":[{"id":"115468","messageId":"20090605040238.8885.92790.chriscool@tuxfamily.org","threadId":"19668","inReplyTo":null,"subject":"[PATCH v2 0/3] automatically skip away from broken commits","fromName":"Christian Couder","fromEmail":"chriscool@tuxfamily.org","sentAt":"2009-06-05T04:10:40Z","receivedAt":"2009-06-05T04:10:40Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"This patch series makes \"git bisect skip\" skip away from an area where\nthe commits cannot be tested.\n\nThis is done automatically. The user has nothing todo. We alternatively\ntry to test commits 20%, 40% and 60% away from the optimal commit that\nhas been skipped.\n\n  bisect: add parameters to \"filter_skipped\"\n  bisect: when skipping, choose a commit away from a skipped commit\n  t6030: test skipping away from an already skipped commit\n\n bisect.c                    |   77 ++++++++++++++++++++++++++++++++++++++++--\n bisect.h                    |    4 ++-\n builtin-rev-list.c          |    4 ++-\n t/t6030-bisect-porcelain.sh |   12 +++++++\n 4 files changed, 91 insertions(+), 6 deletions(-)\n"},{"id":"115467","messageId":"20090605041044.8885.91204.chriscool@tuxfamily.org","threadId":"19668","inReplyTo":"20090605040238.8885.92790.chriscool@tuxfamily.org","subject":"[PATCH v2 1/3] bisect: add parameters to \"filter_skipped\"","fromName":"Christian Couder","fromEmail":"chriscool@tuxfamily.org","sentAt":"2009-06-05T04:10:41Z","receivedAt":"2009-06-05T04:10:41Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"because we will need to get more information from this function in\nsome later patches.\n\nThe new \"int *count\" parameter gives the number of commits left after\nthe skipped commit have been filtered out.\n\nThe new \"int *skipped_first\" parameter tells us if the first commit\nin the list has been skipped. Note that using this parameter also\nchanges the behavior of the function if the first commit is indeed\nskipped. Because we assume that in this case we will want all the\nfiltered commits, not just the first one, even if \"show_all\" is not\nset.\n\nSigned-off-by: Christian Couder <chriscool@tuxfamily.org>\n---\n bisect.c           |   26 ++++++++++++++++++++++----\n bisect.h           |    4 +++-\n builtin-rev-list.c |    4 +++-\n 3 files changed, 28 insertions(+), 6 deletions(-)\n\ndiff --git a/bisect.c b/bisect.c\nindex 2c14f4d..02497f7 100644\n--- a/bisect.c\n+++ b/bisect.c\n@@ -523,12 +523,19 @@ static char *join_sha1_array_hex(struct sha1_array *array, char delim)\n \n struct commit_list *filter_skipped(struct commit_list *list,\n \t\t\t\t   struct commit_list **tried,\n-\t\t\t\t   int show_all)\n+\t\t\t\t   int show_all,\n+\t\t\t\t   int *count,\n+\t\t\t\t   int *skipped_first)\n {\n \tstruct commit_list *filtered = NULL, **f = &filtered;\n \n \t*tried = NULL;\n \n+\tif (skipped_first)\n+\t\t*skipped_first = 0;\n+\tif (count)\n+\t\t*count = 0;\n+\n \tif (!skipped_revs.sha1_nr)\n \t\treturn list;\n \n@@ -537,19 +544,30 @@ struct commit_list *filter_skipped(struct commit_list *list,\n \t\tlist->next = NULL;\n \t\tif (0 <= lookup_sha1_array(&skipped_revs,\n \t\t\t\t\t   list->item->object.sha1)) {\n+\t\t\tif (skipped_first && !*skipped_first)\n+\t\t\t\t*skipped_first = 1;\n \t\t\t/* Move current to tried list */\n \t\t\t*tried = list;\n \t\t\ttried = &list->next;\n \t\t} else {\n-\t\t\tif (!show_all)\n-\t\t\t\treturn list;\n+\t\t\tif (!show_all) {\n+\t\t\t\tif (!skipped_first || !*skipped_first)\n+\t\t\t\t\treturn list;\n+\t\t\t} else if (skipped_first && !*skipped_first) {\n+\t\t\t\t*skipped_first = -1;\n+\t\t\t}\n \t\t\t/* Move current to filtered list */\n \t\t\t*f = list;\n \t\t\tf = &list->next;\n+\t\t\tif (count)\n+\t\t\t\t(*count)++;\n \t\t}\n \t\tlist = next;\n \t}\n \n+\tif (skipped_first && *skipped_first == -1)\n+\t\t*skipped_first = 0;\n+\n \treturn filtered;\n }\n \n@@ -865,7 +883,7 @@ int bisect_next_all(const char *prefix)\n \n \trevs.commits = find_bisection(revs.commits, &reaches, &all,\n \t\t\t\t       !!skipped_revs.sha1_nr);\n-\trevs.commits = filter_skipped(revs.commits, &tried, 0);\n+\trevs.commits = filter_skipped(revs.commits, &tried, 0, NULL, NULL);\n \n \tif (!revs.commits) {\n \t\t/*\ndiff --git a/bisect.h b/bisect.h\nindex fb744fd..82f8fc1 100644\n--- a/bisect.h\n+++ b/bisect.h\n@@ -7,7 +7,9 @@ extern struct commit_list *find_bisection(struct commit_list *list,\n \n extern struct commit_list *filter_skipped(struct commit_list *list,\n \t\t\t\t\t  struct commit_list **tried,\n-\t\t\t\t\t  int show_all);\n+\t\t\t\t\t  int show_all,\n+\t\t\t\t\t  int *count,\n+\t\t\t\t\t  int *skipped_first);\n \n extern void print_commit_list(struct commit_list *list,\n \t\t\t      const char *format_cur,\ndiff --git a/builtin-rev-list.c b/builtin-rev-list.c\nindex 73bff84..69753dc 100644\n--- a/builtin-rev-list.c\n+++ b/builtin-rev-list.c\n@@ -262,7 +262,9 @@ int show_bisect_vars(struct rev_list_info *info, int reaches, int all)\n \tif (!revs->commits && !(flags & BISECT_SHOW_TRIED))\n \t\treturn 1;\n \n-\trevs->commits = filter_skipped(revs->commits, &tried, flags & BISECT_SHOW_ALL);\n+\trevs->commits = filter_skipped(revs->commits, &tried,\n+\t\t\t\t       flags & BISECT_SHOW_ALL,\n+\t\t\t\t       NULL, NULL);\n \n \t/*\n \t * revs->commits can reach \"reaches\" commits among\n-- \n1.6.3.GIT\n"},{"id":"115469","messageId":"20090605041044.8885.92104.chriscool@tuxfamily.org","threadId":"19668","inReplyTo":"20090605040238.8885.92790.chriscool@tuxfamily.org","subject":"[PATCH v2 2/3] bisect: when skipping, choose a commit away from a skipped commit","fromName":"Christian Couder","fromEmail":"chriscool@tuxfamily.org","sentAt":"2009-06-05T04:10:42Z","receivedAt":"2009-06-05T04:10:42Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"To do that a new function \"apply_skip_ratio\" is added and another\nfunction \"managed_skipped\" is created to wrap both \"filter_skipped\"\nand the previous one.\n\nIn \"managed_skipped\" we detect when we should choose a commit away\nfrom a skipped one and then we automatically choose a skip ratio\nto pass to \"apply_skip_ratio\".\n\nThe ratio is choosen so that it alternates between 1/5, 2/5 and\n3/5.\n\nIn \"apply_skip_ratio\", we ignore a given ratio of all the commits\nthat could be tested.\n\nSigned-off-by: Christian Couder <chriscool@tuxfamily.org>\n---\n bisect.c |   53 ++++++++++++++++++++++++++++++++++++++++++++++++++++-\n 1 files changed, 52 insertions(+), 1 deletions(-)\n\ndiff --git a/bisect.c b/bisect.c\nindex 02497f7..3ad9887 100644\n--- a/bisect.c\n+++ b/bisect.c\n@@ -571,6 +571,57 @@ struct commit_list *filter_skipped(struct commit_list *list,\n \treturn filtered;\n }\n \n+static struct commit_list *apply_skip_ratio(struct commit_list *list,\n+\t\t\t\t\t    int count,\n+\t\t\t\t\t    int skip_num, int skip_denom)\n+{\n+\tint index, i;\n+\tstruct commit_list *cur, *previous;\n+\n+\tcur = list;\n+\tprevious = NULL;\n+\tindex = count * skip_num / skip_denom;\n+\n+\tfor (i = 0; cur; cur = cur->next, i++) {\n+\t\tif (i == index) {\n+\t\t\tif (hashcmp(cur->item->object.sha1, current_bad_sha1))\n+\t\t\t\treturn cur;\n+\t\t\tif (previous)\n+\t\t\t\treturn previous;\n+\t\t\treturn list;\n+\t\t}\n+\t\tprevious = cur;\n+\t}\n+\n+\treturn list;\n+}\n+\n+static struct commit_list *managed_skipped(struct commit_list *list,\n+\t\t\t\t\t   struct commit_list **tried)\n+{\n+\tint count, skipped_first;\n+\tint skip_num, skip_denom;\n+\n+\t*tried = NULL;\n+\n+\tif (!skipped_revs.sha1_nr)\n+\t\treturn list;\n+\n+\tif (!skip_num)\n+\t\treturn filter_skipped(list, tried, 0, NULL, NULL);\n+\n+\tlist = filter_skipped(list, tried, 0, &count, &skipped_first);\n+\n+\tif (!skipped_first)\n+\t\treturn list;\n+\n+\t/* Use alternatively 1/5, 2/5 and 3/5 as skip ratio. */\n+\tskip_num = count % 3 + 1;\n+\tskip_denom = 5;\n+\n+\treturn apply_skip_ratio(list, count, skip_num, skip_denom);\n+}\n+\n static void bisect_rev_setup(struct rev_info *revs, const char *prefix,\n \t\t\t     const char *bad_format, const char *good_format,\n \t\t\t     int read_paths)\n@@ -883,7 +934,7 @@ int bisect_next_all(const char *prefix)\n \n \trevs.commits = find_bisection(revs.commits, &reaches, &all,\n \t\t\t\t       !!skipped_revs.sha1_nr);\n-\trevs.commits = filter_skipped(revs.commits, &tried, 0, NULL, NULL);\n+\trevs.commits = managed_skipped(revs.commits, &tried);\n \n \tif (!revs.commits) {\n \t\t/*\n-- \n1.6.3.GIT\n"},{"id":"115470","messageId":"20090605041044.8885.1948.chriscool@tuxfamily.org","threadId":"19668","inReplyTo":"20090605040238.8885.92790.chriscool@tuxfamily.org","subject":"[PATCH v2 3/3] t6030: test skipping away from an already skipped commit","fromName":"Christian Couder","fromEmail":"chriscool@tuxfamily.org","sentAt":"2009-06-05T04:10:43Z","receivedAt":"2009-06-05T04:10:43Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"\nSigned-off-by: Christian Couder <chriscool@tuxfamily.org>\n---\n t/t6030-bisect-porcelain.sh |   12 ++++++++++++\n 1 files changed, 12 insertions(+), 0 deletions(-)\n\ndiff --git a/t/t6030-bisect-porcelain.sh b/t/t6030-bisect-porcelain.sh\nindex 5254b23..4556cdd 100755\n--- a/t/t6030-bisect-porcelain.sh\n+++ b/t/t6030-bisect-porcelain.sh\n@@ -555,6 +555,18 @@ test_expect_success 'restricting bisection on one dir and a file' '\n \tgrep \"$PARA_HASH4 is first bad commit\" my_bisect_log.txt\n '\n \n+test_expect_success 'skipping away from skipped commit' '\n+\tgit bisect start $PARA_HASH7 $HASH1 &&\n+\tpara4=$(git rev-parse --verify HEAD) &&\n+\ttest \"$para4\" = \"$PARA_HASH4\" &&\n+        git bisect skip &&\n+\thash7=$(git rev-parse --verify HEAD) &&\n+\ttest \"$hash7\" = \"$HASH7\" &&\n+        git bisect skip &&\n+\thash3=$(git rev-parse --verify HEAD) &&\n+\ttest \"$hash3\" = \"$HASH3\"\n+'\n+\n #\n #\n test_done\n-- \n1.6.3.GIT\n"},{"id":"115488","messageId":"7vtz2vp45e.fsf@alter.siamese.dyndns.org","threadId":"19668","inReplyTo":"20090605041044.8885.91204.chriscool@tuxfamily.org","subject":"Re: [PATCH v2 1/3] bisect: add parameters to \"filter_skipped\"","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-06-05T06:48:29Z","receivedAt":"2009-06-05T06:48:29Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Christian Couder <chriscool@tuxfamily.org> writes:\n\n> because we will need to get more information from this function in\n> some later patches.\n>\n> The new \"int *count\" parameter gives the number of commits left after\n> the skipped commit have been filtered out.\n>\n> The new \"int *skipped_first\" parameter tells us if the first commit\n> in the list has been skipped. Note that using this parameter also\n> changes the behavior of the function if the first commit is indeed\n> skipped. Because we assume that in this case we will want all the\n> filtered commits, not just the first one, even if \"show_all\" is not\n> set.\n\nThe way you use (*skipped_first == -1) as a marker to mean \"we've already\nchecked more than one commit_list so even when we see a one to be skipped,\nit won't be the first one\" is unreadable, especially without explanation.\nWorse yet, the above paragraph explains what the parameter does, but why\nis it so special to skip the one that happens to be the first on the input\nlist, especially when one does not know how the list is sorted to begin\nwith.\n\nI understand that the list is sorted by the \"goodness\" value, i.e. the one\nthat cuts the graph into closer-to-equal halves comes earlier in the list,\nbut still it is unclear why having to skip the best one is so special\ncompared to having to skip say the second best one, especially when you\nimagine a case where the first two on the list are of equal \"goodness\"\nvalue.\n"},{"id":"115487","messageId":"7vmy8np44z.fsf@alter.siamese.dyndns.org","threadId":"19668","inReplyTo":"20090605041044.8885.92104.chriscool@tuxfamily.org","subject":"Re: [PATCH v2 2/3] bisect: when skipping, choose a commit away from a skipped commit","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-06-05T06:48:44Z","receivedAt":"2009-06-05T06:48:44Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Christian Couder <chriscool@tuxfamily.org> writes:\n\n> +static struct commit_list *apply_skip_ratio(struct commit_list *list,\n> +\t\t\t\t\t    int count,\n> +\t\t\t\t\t    int skip_num, int skip_denom)\n> +{\n> +\tint index, i;\n> +\tstruct commit_list *cur, *previous;\n> +\n> +\tcur = list;\n> +\tprevious = NULL;\n> +\tindex = count * skip_num / skip_denom;\n> +\n> +\tfor (i = 0; cur; cur = cur->next, i++) {\n> +\t\tif (i == index) {\n> +\t\t\tif (hashcmp(cur->item->object.sha1, current_bad_sha1))\n> +\t\t\t\treturn cur;\n> +\t\t\tif (previous)\n> +\t\t\t\treturn previous;\n\nWhen you return \"previous\", don't you need to make sure it is not the\ncurrently bad one?  That is,...\n\n> +\t\t\treturn list;\n> +\t\t}\n> +\t\tprevious = cur;\n\n... shouldn't this be\n\n                if (hashcmp(cur->item->object.sha1, curret_bad_sha1))\n                        previous = cur;\n\n> +\t}\n\nI do not understand the math/logic you are using here.  The incoming list\nis sorted by the \"goodness\" value, and untestable ones have already been\nremoved.  By picking ones that are far from the tip, you are deliberately\naccepting far suboptimal bisection, but I do not see how you are\nguaranteeing that making such a trade-off is driving you away from the\nuntestable ones.  It almost feels to me that it is no better than randomly\npicking one from the list, so why can this be an improvement over \"pick\nthe one that is testable that appears first in the list that is sorted by\nthe goodness value\"?\n\nImagine you have a graph like this (G is good, B is bad, and both branches\nhave similar number of commits):\n\n\tG-------------y--z--a--b--c--B\n                              /\n        G--------------f--e--d\n\nIn the above graph, a and d would give the best bisection, because they\ncan reach about half the number of nodes in the entire graph, and the goal\nof the basic \"find_bisection()\" is to find a commit that cuts the graph\ninto closest-to-the-equal halves.  For this reason, 'a' and 'd' would be\nnear the beginning of the output from find_bisection(find_all) you run\nwhen there are untestable commits in your managed_skipped().\n\nSuppose 'd' was already marked untestable, but 'a' is not.  And 'd' has\nslightly better \"goodness\" value than 'a'.\n\n\tSide note.  I do not think the situation should change drastically\n\tif 'a' has a better \"goodness\" value than 'd' has, but your\n\t\"skipped_first\" logic that I already said I do not understand in\n\tmy earlier comment treats them quite differently, so this example\n\texplicitly talks about the case where 'd' is better than 'a'.\n\nYou do not check 'a' but check somewhere much older, either on the top\nbranch or on the bottom branch.  Why?\n\n'b', because it is direct descendant of 'd', is likely to have inherited\nthe unrelated breakage from 'd' that made it untestable.  'c', being its\ndescendant, can also be contaminated with the unrelated breakage, but\nthere is a chance that such an unrelated breakage was fixed there.\nSimilarly, 'e' is likely to share the same unrelated breakage as 'd' has,\nbecause it is a direct ancestor.  'f' shares the possibility but has a\nbetter chance of being testable than 'e' is.\n\nBut 'a' does not have any relationship with 'd' and it is unlikely such an\nunrelated breakage exists there.\n\nI _think_ the solution to the \"bisection with untestable\" problem should\nbe handled as an optimization problem of two goodness values that cannot\nbe directly compared and traded-off:\n\n - The point chosen should be close to the mid-point.  The closer \"weight\"\n   value given in do_find_bisection() is to half the number of nodes, the\n   better;\n\n - The point chosen should be far from any known untestable commits.  We\n   do not currently have function to count distance from untestable\n   commits, nor make a call to such a function after filtering untestable\n   commits, but I think we should.\n\nWe already have an efficient and good implementation to compute the former\ncriteria (find_bisection).\n\nThe \"badness\" value that comes from the latter criteria essentially should\nbe how close, from ancestry point of view, each commit is related to the\nones that are known to be untestable.  In the picture, 'b' and 'e' are\nclose relatives (they have thick blood relationship with 'd') and worse\nthan 'c' and 'f' but 'a' shouldn't be punished for being married to 'd'\nthat has a bad blood at all.\n\nNow coming back to the \"skipped_first\" topic.  Let's use the same graph,\nbut now let's assume neither 'a' nor 'd' is known to be untestable, and\nalso 'a' gives slightly better \"goodness\" value than 'd' does.  Further\nsuppose that 'z' was already known to be untestable this time.\n\nEven though 'a' may have a better goodness value, hence it is not skipped,\nshouldn't we be favoring 'd' over 'a' because 'a' is far likely to be\nuntestable (due to closer blood tie with 'z') than 'd' is, and 'a' and 'd'\nwould give roughly the same \"goodness\" value?\n\nThis is why I said I do not understand your skipped_first logic.\n\n> +static struct commit_list *managed_skipped(struct commit_list *list,\n> +\t\t\t\t\t   struct commit_list **tried)\n> +{\n> +\tint count, skipped_first;\n> +\tint skip_num, skip_denom;\n> +\n> +\t*tried = NULL;\n> +\n> +\tif (!skipped_revs.sha1_nr)\n> +\t\treturn list;\n> +\n> +\tif (!skip_num)\n> +\t\treturn filter_skipped(list, tried, 0, NULL, NULL);\n\nskip_num is uninitialized and then checked here.  Is it supposed to be\n\"static int\" with implied 0 initialization?\n\n> +\tlist = filter_skipped(list, tried, 0, &count, &skipped_first);\n> +\n> +\tif (!skipped_first)\n> +\t\treturn list;\n> +\n> +\t/* Use alternatively 1/5, 2/5 and 3/5 as skip ratio. */\n> +\tskip_num = count % 3 + 1;\n> +\tskip_denom = 5;\n> +\n> +\treturn apply_skip_ratio(list, count, skip_num, skip_denom);\n> +}\n"},{"id":"115600","messageId":"200906060638.15267.chriscool@tuxfamily.org","threadId":"19668","inReplyTo":"7vtz2vp45e.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH v2 1/3] bisect: add parameters to \"filter_skipped\"","fromName":"Christian Couder","fromEmail":"chriscool@tuxfamily.org","sentAt":"2009-06-06T04:38:14Z","receivedAt":"2009-06-06T04:38:14Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"Le Friday 05 June 2009, Junio C Hamano a écrit :\n> Christian Couder <chriscool@tuxfamily.org> writes:\n> > because we will need to get more information from this function in\n> > some later patches.\n> >\n> > The new \"int *count\" parameter gives the number of commits left after\n> > the skipped commit have been filtered out.\n> >\n> > The new \"int *skipped_first\" parameter tells us if the first commit\n> > in the list has been skipped. Note that using this parameter also\n> > changes the behavior of the function if the first commit is indeed\n> > skipped. Because we assume that in this case we will want all the\n> > filtered commits, not just the first one, even if \"show_all\" is not\n> > set.\n>\n> The way you use (*skipped_first == -1) as a marker to mean \"we've already\n> checked more than one commit_list so even when we see a one to be\n> skipped, it won't be the first one\" is unreadable, especially without\n> explanation. Worse yet, the above paragraph explains what the parameter\n> does, but why is it so special to skip the one that happens to be the\n> first on the input list, especially when one does not know how the list\n> is sorted to begin with.\n\nI added the following comment before the function:\n\n/*\n * In this function, passing a not NULL skipped_first is very special.\n * It means that we want to know if the first commit in the list is\n * skipped because we will want to test a commit away from it if it is\n * indeed skipped.\n * So if the first commit is skipped, we cannot take the shortcut to\n * just \"return list\" when we find the first non skipped commit, we\n * have to return a fully filtered list.\n *\n * We use (*skipped_first == -1) to mean \"it has been found that the\n * first commit is not skipped\". In this case *skipped_first is set back\n * to 0 just before the function returns.\n */\n\nI hope this is enough to clarify what this function does.\n\n> I understand that the list is sorted by the \"goodness\" value, i.e. the\n> one that cuts the graph into closer-to-equal halves comes earlier in the\n> list, but still it is unclear why having to skip the best one is so\n> special compared to having to skip say the second best one, especially\n> when you imagine a case where the first two on the list are of equal\n> \"goodness\" value.\n\nThe reason why only having to skip the best one is special is just because \nit is simpler to only check if the best one is skipped or not.\n\nI agree that it could be an improvement to consider if other commits with \nthe same goodness value are also skipped, but I think it would make the \ncode more complex.\n\nThanks,\nChristian.\n"},{"id":"115599","messageId":"200906060638.25566.chriscool@tuxfamily.org","threadId":"19668","inReplyTo":"7vmy8np44z.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH v2 2/3] bisect: when skipping, choose a commit away from a skipped commit","fromName":"Christian Couder","fromEmail":"chriscool@tuxfamily.org","sentAt":"2009-06-06T04:38:25Z","receivedAt":"2009-06-06T04:38:25Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"Le Friday 05 June 2009, Junio C Hamano a écrit :\n> Christian Couder <chriscool@tuxfamily.org> writes:\n> > +static struct commit_list *apply_skip_ratio(struct commit_list *list,\n> > +\t\t\t\t\t    int count,\n> > +\t\t\t\t\t    int skip_num, int skip_denom)\n> > +{\n> > +\tint index, i;\n> > +\tstruct commit_list *cur, *previous;\n> > +\n> > +\tcur = list;\n> > +\tprevious = NULL;\n> > +\tindex = count * skip_num / skip_denom;\n> > +\n> > +\tfor (i = 0; cur; cur = cur->next, i++) {\n> > +\t\tif (i == index) {\n> > +\t\t\tif (hashcmp(cur->item->object.sha1, current_bad_sha1))\n> > +\t\t\t\treturn cur;\n> > +\t\t\tif (previous)\n> > +\t\t\t\treturn previous;\n>\n> When you return \"previous\", don't you need to make sure it is not the\n> currently bad one?  That is,...\n>\n> > +\t\t\treturn list;\n> > +\t\t}\n> > +\t\tprevious = cur;\n>\n> ... shouldn't this be\n>\n>                 if (hashcmp(cur->item->object.sha1, curret_bad_sha1))\n>                         previous = cur;\n>\n> > +\t}\n\nI think the current bad will always have the worst goodness value so it will \nalways be the last item in the list, so it cannot be \"previous\".\n\nYou can try it out with \"git rev-list --bisect-all HEAD ^HEAD~10\" for \nexample, the bad item (HEAD in this example) will always appear \nwith \"(dist=0)\" at the end.\n\nWe rely on that in \"bisect_next_all\" to decide if we found the first bad \ncommit. We do:\n\n\tbisect_rev = revs.commits->item->object.sha1;\n\t...\n\n\tif (!hashcmp(bisect_rev, current_bad_sha1)) {\n\t\texit_if_skipped_commits(tried, current_bad_sha1);\n\t\tprintf(\"%s is first bad commit\\n\", bisect_rev_hex);\n\t\tshow_diff_tree(prefix, revs.commits->item);\n\t\t/* This means the bisection process succeeded. */\n\t\texit(10);\n\t}\n\n> I do not understand the math/logic you are using here.  The incoming list\n> is sorted by the \"goodness\" value, and untestable ones have already been\n> removed.\n\nYes.\n\n> By picking ones that are far from the tip, you are deliberately \n> accepting far suboptimal bisection, but I do not see how you are\n> guaranteeing that making such a trade-off is driving you away from the\n> untestable ones. \n\nI think picking one commit far from the tip, doens't mean accepting far \nsuboptimal bisection. HPA wrote in a recent thread (RFE: \"git bisect \nreverse\"):\n\n\"You don't drop to 1/2 bit of information until x = 0.11 or 0.89\"\n\nand I think the worst possible value with my code means x = 0.2 or x = 0.8 \n(with the 3/5 ratio).\n\nIt's true that when using a ratio to skip away from an untestable one we \ndon't check that we don't come near another untestable one. \n\n> It almost feels to me that it is no better than \n> randomly picking one from the list, so why can this be an improvement\n> over \"pick the one that is testable that appears first in the list that\n> is sorted by the goodness value\"?\n\nWe rely on the assumption that the probability that there are many \nuntestable ones in many different places quite far away from an untestable \none and from each other is very low.\n\nFor example using the following script:\n\n-------------\n#!/bin/sh\n\nnew_commit() {\n    num=\"$1\"\n    echo \"line for commit $num\" >> hello\n    git commit -m \"commit $num\" hello\n}\n\ntouch hello\ngit add hello\n\nfor val in $(seq 100)\ndo\n  new_commit $val\ndone\n-------------\n\nand then bisecting between the first and last commits gives something like:\n\n$ git bisect start HEAD HEAD~99\nBisecting: 49 revisions left to test after this (roughly 6 steps)\n[e65f680ee31729d2db66dbed7eb24ea8c0e8b6c3] commit 50\n$ git bisect skip\nBisecting: 48 revisions left to test after this (roughly 6 steps)\n[6cc0df3b9762928c90a5ce7ad4d27bf3340983c3] commit 51\n$ git bisect skip\nBisecting: 48 revisions left to test after this (roughly 6 steps)\n[45387fab3997ca8c449ac419cb401207aa63da4d] commit 71\n$ git bisect skip\nBisecting: 48 revisions left to test after this (roughly 6 steps)\n[dd20066ed8a287e8105b833911de7509ca5ec339] commit 40\n$ git bisect skip\nBisecting: 48 revisions left to test after this (roughly 6 steps)\n[8f0c63e6eede9650bb577dba6f3092703409509e] commit 20\n$ git bisect skip\nBisecting: 48 revisions left to test after this (roughly 6 steps)\n[4809a426fd411f2db43291bc5d206b199ca9e648] commit 30\n$ git bisect skip\nBisecting: 48 revisions left to test after this (roughly 6 steps)\n[095cc6a1c6f071f3807ca123ab5bcfc133f36f96] commit 61\n$ git bisect skip\nBisecting: 48 revisions left to test after this (roughly 6 steps)\n[94a00c0de61ed8ddef261bebfbbb00bc6e0a3a1f] commit 82\n$ git bisect skip\nBisecting: 48 revisions left to test after this (roughly 6 steps)\n[5d1a2332b7d5d409faebb7056e11028f5b7642f4] commit 29\n$ git bisect skip\nBisecting: 48 revisions left to test after this (roughly 6 steps)\n[ad46dfdfb0a871b13144395efe26607cb63c7f5b] commit 39\n\nSo after testing commits 50 and 51 that are near the middle, you test many \ncommits far away from both commits 50 and 51 and from each other, and yet \nnot too close to 0 or 100.\n\n> Imagine you have a graph like this (G is good, B is bad, and both\n> branches have similar number of commits):\n>\n> \tG-------------y--z--a--b--c--B\n>                               /\n>         G--------------f--e--d\n>\n> In the above graph, a and d would give the best bisection, because they\n> can reach about half the number of nodes in the entire graph, and the\n> goal of the basic \"find_bisection()\" is to find a commit that cuts the\n> graph into closest-to-the-equal halves.  For this reason, 'a' and 'd'\n> would be near the beginning of the output from find_bisection(find_all)\n> you run when there are untestable commits in your managed_skipped().\n>\n> Suppose 'd' was already marked untestable, but 'a' is not.  And 'd' has\n> slightly better \"goodness\" value than 'a'.\n>\n> \tSide note.  I do not think the situation should change drastically\n> \tif 'a' has a better \"goodness\" value than 'd' has, but your\n> \t\"skipped_first\" logic that I already said I do not understand in\n> \tmy earlier comment treats them quite differently, so this example\n> \texplicitly talks about the case where 'd' is better than 'a'.\n>\n> You do not check 'a' but check somewhere much older, either on the top\n> branch or on the bottom branch.  Why?\n\nThe reason is that it would make the code more complex to check that we are \nin this case, and that this case may not happen very often (it relies on \nboth being near a merge and having branches of the same size), and that we \ndon't loose much (see above my reference to what HPA wrote) by testing a \ncommit quite far away.\n\n> 'b', because it is direct descendant of 'd', is likely to have inherited\n> the unrelated breakage from 'd' that made it untestable.  'c', being its\n> descendant, can also be contaminated with the unrelated breakage, but\n> there is a chance that such an unrelated breakage was fixed there.\n> Similarly, 'e' is likely to share the same unrelated breakage as 'd' has,\n> because it is a direct ancestor.  'f' shares the possibility but has a\n> better chance of being testable than 'e' is.\n>\n> But 'a' does not have any relationship with 'd' and it is unlikely such\n> an unrelated breakage exists there.\n>\n> I _think_ the solution to the \"bisection with untestable\" problem should\n> be handled as an optimization problem of two goodness values that cannot\n> be directly compared and traded-off:\n>\n>  - The point chosen should be close to the mid-point.  The closer\n> \"weight\" value given in do_find_bisection() is to half the number of\n> nodes, the better;\n\nI am not so sure this is so important.\n\n>  - The point chosen should be far from any known untestable commits.  We\n>    do not currently have function to count distance from untestable\n>    commits, nor make a call to such a function after filtering untestable\n>    commits, but I think we should.\n\nI think this should be the case with my patch series.\n\n> We already have an efficient and good implementation to compute the\n> former criteria (find_bisection).\n>\n> The \"badness\" value that comes from the latter criteria essentially\n> should be how close, from ancestry point of view, each commit is related\n> to the ones that are known to be untestable.  In the picture, 'b' and 'e'\n> are close relatives (they have thick blood relationship with 'd') and\n> worse than 'c' and 'f' but 'a' shouldn't be punished for being married to\n> 'd' that has a bad blood at all.\n>\n> Now coming back to the \"skipped_first\" topic.  Let's use the same graph,\n> but now let's assume neither 'a' nor 'd' is known to be untestable, and\n> also 'a' gives slightly better \"goodness\" value than 'd' does.  Further\n> suppose that 'z' was already known to be untestable this time.\n>\n> Even though 'a' may have a better goodness value, hence it is not\n> skipped, shouldn't we be favoring 'd' over 'a' because 'a' is far likely\n> to be untestable (due to closer blood tie with 'z') than 'd' is, and 'a'\n> and 'd' would give roughly the same \"goodness\" value?\n>\n> This is why I said I do not understand your skipped_first logic.\n\nI agree that we could probably analyse the graph much better than what my \npatch series does, but I think that it would be quite complex.\n\n> > +static struct commit_list *managed_skipped(struct commit_list *list,\n> > +\t\t\t\t\t   struct commit_list **tried)\n> > +{\n> > +\tint count, skipped_first;\n> > +\tint skip_num, skip_denom;\n> > +\n> > +\t*tried = NULL;\n> > +\n> > +\tif (!skipped_revs.sha1_nr)\n> > +\t\treturn list;\n> > +\n> > +\tif (!skip_num)\n> > +\t\treturn filter_skipped(list, tried, 0, NULL, NULL);\n>\n> skip_num is uninitialized and then checked here.  Is it supposed to be\n> \"static int\" with implied 0 initialization?\n\nOoops, I forgot to remove these 2 lines. They were usefull in my previous \nseries but they should be removed in this one.\n\n> > +\tlist = filter_skipped(list, tried, 0, &count, &skipped_first);\n> > +\n> > +\tif (!skipped_first)\n> > +\t\treturn list;\n> > +\n> > +\t/* Use alternatively 1/5, 2/5 and 3/5 as skip ratio. */\n> > +\tskip_num = count % 3 + 1;\n> > +\tskip_denom = 5;\n> > +\n> > +\treturn apply_skip_ratio(list, count, skip_num, skip_denom);\n> > +}\n\nI will repost the series with the above fix and some added comments.\n\nThanks,\nChristian.\n"},{"id":"115605","messageId":"7vzlcmdjmj.fsf@alter.siamese.dyndns.org","threadId":"19668","inReplyTo":"200906060638.25566.chriscool@tuxfamily.org","subject":"Re: [PATCH v2 2/3] bisect: when skipping, choose a commit away from a skipped commit","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-06-06T05:19:32Z","receivedAt":"2009-06-06T05:19:32Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Christian Couder <chriscool@tuxfamily.org> writes:\n\n> For example using the following script:\n>\n> -------------\n> #!/bin/sh\n>\n> new_commit() {\n>     num=\"$1\"\n>     echo \"line for commit $num\" >> hello\n>     git commit -m \"commit $num\" hello\n> }\n>\n> touch hello\n> git add hello\n>\n> for val in $(seq 100)\n> do\n>   new_commit $val\n> done\n\nBut isn't this a totally uninteresting case of 100 _single_ strand of\npearls?  For a linear history, you do not even need the bisect machinery;\nyou can even bisect by hand.\n\n>> Imagine you have a graph like this (G is good, B is bad, and both\n>> branches have similar number of commits):\n>>\n>> \tG-------------y--z--a--b--c--B\n>>                               /\n>>         G--------------f--e--d\n>>\n>> In the above graph, a and d would give the best bisection, because they\n>> can reach about half the number of nodes in the entire graph, and the\n>> goal of the basic \"find_bisection()\" is to find a commit that cuts the\n>> graph into closest-to-the-equal halves.  For this reason, 'a' and 'd'\n>> would be near the beginning of the output from find_bisection(find_all)\n>> you run when there are untestable commits in your managed_skipped().\n>>\n>> Suppose 'd' was already marked untestable, but 'a' is not.  And 'd' has\n>> slightly better \"goodness\" value than 'a'.\n>>\n>> \tSide note.  I do not think the situation should change drastically\n>> \tif 'a' has a better \"goodness\" value than 'd' has, but your\n>> \t\"skipped_first\" logic that I already said I do not understand in\n>> \tmy earlier comment treats them quite differently, so this example\n>> \texplicitly talks about the case where 'd' is better than 'a'.\n>>\n>> You do not check 'a' but check somewhere much older, either on the top\n>> branch or on the bottom branch.  Why?\n>\n> The reason is that it would make the code more complex to check that we are \n> in this case, and that this case may not happen very often (it relies on \n> both being near a merge and having branches of the same size), and that we \n> don't loose much (see above my reference to what HPA wrote) by testing a \n> commit quite far away.\n\nI think what you are missing is that you are not even guaranteeing \"quite\nfar away\" in the _topological_ space, especially in the presense of merges.\n\nIf you focus on a totally linear history, yes, picking somewhere away, in\nthe \"goodness\" scale space, from the optimal point (and there is a single\noptimal point) that is untestable happens to take you away from that\nparticular untestable one in the topology space as well.  But that only\nholds true when you have no merges.\n\nMy example graph was not an extreme special case at all.  It is just an\nillustration of a typical real-life history.  Sure, I told you to assume\nthat both sides have about equal number of commits, but if the top branch\nwere longer, then instead of 'a', perhaps 'y' or its parent may be the\nnext best commit.  It is still very close in the \"goodness\" space to the\nuntestable commit 'd', but it is very far away from it in the topological\nspace, but your algorithm discards it because it is close in the\n\"goodness\" scale space.  And the distance in the topological space from\nuntestable ones is what we seek here.\n\n>>  - The point chosen should be far from any known untestable commits.  We\n>>    do not currently have function to count distance from untestable\n>>    commits, nor make a call to such a function after filtering untestable\n>>    commits, but I think we should.\n>\n> I think this should be the case with my patch series.\n\nWhy?  You are picking \"away, in the goodness scale, from the _best_ one\".\nI've already explained why it does not follow that the commit chosen that\nway is _topologically_ away from _untestable_ ones.\n\n> I agree that we could probably analyse the graph much better than what my \n> patch series does, but I think that it would be quite complex.\n\nIf you do not want complexity, let's not even do this \"away in the\ngoodness space from the best one\".  Your three patches already add\ncomplexity to the algorithm, and I do not think what they do is worth it.\nIt solves a wrong problem, that does not have anything to do with \"stay\naway from untestable ones in the topological space\".\n"}]}