[PATCH v2 00/21] git bisect improvements

[Stephan Beyer <s-beyer@gmx.net>]

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

-- 
2.8.1.137.g522756c