Hi, a long time ago[1] I sent the first version of this patchset to the list. Since then I wrote different variants of the algorithm, fixed some bugs, made the tests work ;), and finally performed some performance tests to pick the best version of the different variants. For the performance tests I used the Git repositories of the Linux kernel and of Git itself and performed whole-history bisections with a bisect script that decided "good" or "bad" based on the hash of a commit. And another bisect script that did the opposite. I omit the details. The best variant uses a DFS for the traversal without any further "smart" tricks: These tricks led to more "administrative expense" than gain of performance. I'm sorry that it took so long to prepare the 2nd patchset (mainly vacation and other work in between). So I hope it's sufficiently good for inclusion. :) Cheers 1. https://www.mail-archive.com/git@xxxxxxxxxxxxxxx/msg86353.html Stephan Beyer (21): bisect: write about `bisect next` in documentation bisect: allow 'bisect run' if no good commit is known t/test-lib-functions.sh: generalize test_cmp_rev t: use test_cmp_rev() where appropriate t6030: generalize test to not rely on current implementation bisect: add test for the bisect algorithm bisect: plug the biggest memory leak bisect: make bisect compile if DEBUG_BISECT is set bisect: make algorithm behavior independent of DEBUG_BISECT bisect: get rid of recursion in count_distance() bisect: use struct node_data array instead of int array bisect: replace clear_distance() by unique markers bisect: use commit instead of commit list as arguments when appropriate bisect: extract get_distance() function from code duplication bisect: introduce distance_direction() bisect: make total number of commits global bisect: rename count_distance() to compute_weight() bisect: prepare for different algorithms based on find_all bisect: use a bottom-up traversal to find relevant weights bisect: compute best bisection in compute_relevant_weights() bisect: get back halfway shortcut Documentation/git-bisect.txt | 24 ++ bisect.c | 481 ++++++++++++++++++++---------- git-bisect.sh | 32 +- t/t2012-checkout-last.sh | 8 +- t/t3308-notes-merge.sh | 8 +- t/t3310-notes-merge-manual-resolve.sh | 8 +- t/t3311-notes-merge-fanout.sh | 6 +- t/t3404-rebase-interactive.sh | 38 +-- t/t3407-rebase-abort.sh | 8 +- t/t3410-rebase-preserve-dropped-merges.sh | 4 +- t/t3411-rebase-preserve-around-merges.sh | 10 +- t/t3414-rebase-preserve-onto.sh | 12 +- t/t3501-revert-cherry-pick.sh | 4 +- t/t3506-cherry-pick-ff.sh | 6 +- t/t3903-stash.sh | 6 +- t/t4150-am.sh | 18 +- t/t5404-tracking-branches.sh | 2 +- t/t5505-remote.sh | 4 +- t/t5520-pull.sh | 36 +-- t/t6022-merge-rename.sh | 2 +- t/t6030-bisect-porcelain.sh | 228 +++++++------- t/t6036-recursive-corner-cases.sh | 58 ++-- t/t6042-merge-rename-corner-cases.sh | 50 ++-- t/t7003-filter-branch.sh | 8 +- t/t7004-tag.sh | 2 +- t/t7110-reset-merge.sh | 24 +- t/t7201-co.sh | 12 +- t/t7601-merge-pull-config.sh | 17 +- t/t7603-merge-reduce-heads.sh | 30 +- t/t7605-merge-resolve.sh | 5 +- t/t8010-bisect-algorithm.sh | 155 ++++++++++ t/t9162-git-svn-dcommit-interactive.sh | 8 +- t/t9300-fast-import.sh | 12 +- t/test-lib-functions.sh | 14 +- 34 files changed, 832 insertions(+), 508 deletions(-) create mode 100755 t/t8010-bisect-algorithm.sh -- 2.8.1.137.g522756c -- To unsubscribe from this list: send the line "unsubscribe git" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html
