[PATCH v2 00/21] git bisect improvements

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@vger.kernel.org/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