bisect: avoid copying ancestor list for non-merge commits During a bisection, hg needs to compute a list of all ancestors for every candidate commit. This is accomplished via a bottom-up traversal of the set of candidates, during which each revision's ancestor list is populated using the ancestor list of its parent(s). Previously, this involved copying the entire list, which could be very long in if the bisection range was large. To help improve this, we can observe that each candidate commit is visited exactly once, at which point its ancestor list is copied into its children's lists and then dropped. In the case of non-merge commits, a commit's ancestor list consists exactly of its parent's list plus itself. This means that we can trivially reuse the parent's existing list for one of its non-merge children, which avoids copying entirely if that commit is the parent's only child. This makes bisections over linear ranges of commits much faster. During some informal testing in the large publicly-available `mozilla-central` repository, this noticeably sped up bisections over large ranges of history: Setup: $ cd mozilla-central $ hg bisect --reset $ hg bisect --good 0 $ hg log -r tip -T '{rev}\n' 628417 Test: $ time hg bisect --bad tip --noupdate Before: real 3m35.927s user 3m35.553s sys 0m0.319s After: real 1m41.142s user 1m40.810s sys 0m0.285s

     1

     2

  $ cat >> $HGRCPATH <<EOF

     3

  > [extensions]

     4

  > convert=

     5

  > EOF

     6

     7

Prepare orig repo

     8

     9

  $ hg init orig

    10

  $ cd orig

    11

  $ echo foo > foo

    12

  $ HGUSER='user name' hg ci -qAm 'foo'

    13

  $ cd ..

    14

    15

Explicit --authors

    16

    17

  $ cat > authormap.txt <<EOF

    18

  > user name = Long User Name

    19

  > 

    20

  > # comment

    21

  > this line is ignored

    22

  > EOF

    23

  $ hg convert --authors authormap.txt orig new

    24

  initializing destination new repository

    25

  ignoring bad line in author map file authormap.txt: this line is ignored

    26

  scanning source...

    27

  sorting...

    28

  converting...

    29

  0 foo

    30

  writing author map file $TESTTMP/new/.hg/authormap

    31

  $ cat new/.hg/authormap

    32

  user name=Long User Name

    33

  $ hg -Rnew log

    34

  changeset:   0:d89716e88087

    35

  tag:         tip

    36

  user:        Long User Name

    37

  date:        Thu Jan 01 00:00:00 1970 +0000

    38

  summary:     foo

    39

    40

  $ rm -rf new

    41

    42

Implicit .hg/authormap

    43

    44

  $ hg init new

    45

  $ mv authormap.txt new/.hg/authormap

    46

  $ hg convert orig new

    47

  ignoring bad line in author map file $TESTTMP/new/.hg/authormap: this line is ignored

    48

  scanning source...

    49

  sorting...

    50

  converting...

    51

  0 foo

    52

  $ hg -Rnew log

    53

  changeset:   0:d89716e88087

    54

  tag:         tip

    55

  user:        Long User Name

    56

  date:        Thu Jan 01 00:00:00 1970 +0000

    57

  summary:     foo

    58