From ebc9529f0358bdb10192fa27bc75f5d4e452ce90 Mon Sep 17 00:00:00 2001 From: Christian Couder Date: Sat, 13 Jun 2009 07:21:06 +0200 Subject: bisect: use a PRNG with a bias when skipping away from untestable commits Using a PRNG (pseudo random number generator) with a bias should be better than alternating between 3 fixed ratios. In repositories with many untestable commits it should prevent alternating between areas where many commits are untestable. The bias should favor commits that can give more information, so that the bisection process should not loose much efficiency. HPA suggested to use a PRNG and found that the best bias is to raise a ratio between 0 and 1 given by the PRNG to the power 1.5. An integer square root function is implemented to avoid including and linking with -lm. A PRNG function is implemented to get the same number sequence on different machines as suggested by "man 3 rand". Signed-off-by: Christian Couder Signed-off-by: Junio C Hamano --- bisect.c | 50 +++++++++++++++++++++++++++++++++++---------- t/t6030-bisect-porcelain.sh | 4 ++-- 2 files changed, 41 insertions(+), 13 deletions(-) diff --git a/bisect.c b/bisect.c index 6fdff0572..095b55eba 100644 --- a/bisect.c +++ b/bisect.c @@ -585,16 +585,49 @@ struct commit_list *filter_skipped(struct commit_list *list, return filtered; } -static struct commit_list *apply_skip_ratio(struct commit_list *list, - int count, - int skip_num, int skip_denom) +#define PRN_MODULO 32768 + +/* + * This is a pseudo random number generator based on "man 3 rand". + * It is not used properly because the seed is the argument and it + * is increased by one between each call, but that should not matter + * for this application. + */ +int get_prn(int count) { + count = count * 1103515245 + 12345; + return ((unsigned)(count/65536) % PRN_MODULO); +} + +/* + * Custom integer square root from + * http://en.wikipedia.org/wiki/Integer_square_root + */ +static int sqrti(int val) +{ + float d, x = val; + + if (val == 0) + return 0; + + do { + float y = (x + (float)val / x) / 2; + d = (y > x) ? y - x : x - y; + x = y; + } while (d >= 0.5); + + return (int)x; +} + +static struct commit_list *skip_away(struct commit_list *list, int count) { - int index, i; struct commit_list *cur, *previous; + int prn, index, i; + + prn = get_prn(count); + index = (count * prn / PRN_MODULO) * sqrti(prn) / sqrti(PRN_MODULO); cur = list; previous = NULL; - index = count * skip_num / skip_denom; for (i = 0; cur; cur = cur->next, i++) { if (i == index) { @@ -614,7 +647,6 @@ static struct commit_list *managed_skipped(struct commit_list *list, struct commit_list **tried) { int count, skipped_first; - int skip_num, skip_denom; *tried = NULL; @@ -626,11 +658,7 @@ static struct commit_list *managed_skipped(struct commit_list *list, if (!skipped_first) return list; - /* Use alternatively 1/5, 2/5 and 3/5 as skip ratio. */ - skip_num = count % 3 + 1; - skip_denom = 5; - - return apply_skip_ratio(list, count, skip_num, skip_denom); + return skip_away(list, count); } static void bisect_rev_setup(struct rev_info *revs, const char *prefix, diff --git a/t/t6030-bisect-porcelain.sh b/t/t6030-bisect-porcelain.sh index 4556cdd8d..1315bab59 100755 --- a/t/t6030-bisect-porcelain.sh +++ b/t/t6030-bisect-porcelain.sh @@ -563,8 +563,8 @@ test_expect_success 'skipping away from skipped commit' ' hash7=$(git rev-parse --verify HEAD) && test "$hash7" = "$HASH7" && git bisect skip && - hash3=$(git rev-parse --verify HEAD) && - test "$hash3" = "$HASH3" + para3=$(git rev-parse --verify HEAD) && + test "$para3" = "$PARA_HASH3" ' # -- cgit v1.2.1 From 32d86ca53195590f8d7df9f5f58683c9a924d5af Mon Sep 17 00:00:00 2001 From: Christian Couder Date: Sat, 13 Jun 2009 13:11:02 +0200 Subject: Documentation: remove warning saying that "git bisect skip" may slow bisection This warning was probably useless anyway, but it is even more so now that filtering of skipped commits is done in C and that there is a mechanism to skip away from broken commits. Signed-off-by: Christian Couder Signed-off-by: Junio C Hamano --- Documentation/git-bisect.txt | 5 ++--- 1 file changed, 2 insertions(+), 3 deletions(-) diff --git a/Documentation/git-bisect.txt b/Documentation/git-bisect.txt index ffc02c737..63e7a42cb 100644 --- a/Documentation/git-bisect.txt +++ b/Documentation/git-bisect.txt @@ -164,9 +164,8 @@ to do it for you by issuing the command: $ git bisect skip # Current version cannot be tested ------------ -But computing the commit to test may be slower afterwards and git may -eventually not be able to tell the first bad commit among a bad commit -and one or more skipped commits. +But git may eventually be unable to tell the first bad commit among +a bad commit and one or more skipped commits. You can even skip a range of commits, instead of just one commit, using the "''..''" notation. For example: -- cgit v1.2.1