annotate: pre-calculate the "needed" dictionary (issue5360) The "needed" dict is used as a reference counter to free items in the giant "hist" dict. However, currently it is not very accurate and can lead to dropping "hist" items unnecessarily, for example, with the following DAG, -3- / \ 0--1--2--4-- The current algorithm will visit and calculate rev 1 twice, undesired. And it tries to be smart by clearing rev 1's parents: "pcache[1] = []" at the time hist[1] being accessed (note: hist[1] needs to be used twice, by rev 2 and rev 3). It can result in incorrect results if p1 of rev 4 deletes chunks belonging to rev 0. However, simply removing "needed" is not okay, because it will consume 10x memory: # without any change % HGRCPATH= lrun ./hg annotate mercurial/commands.py -r d130a38 3>&2 [1] MEMORY 49074176 CPUTIME 9.213 REALTIME 9.270 # with "needed" removed MEMORY 637673472 CPUTIME 8.164 REALTIME 8.249 This patch moves "needed" (and "pcache") calculation to a separate DFS to address the issue. It improves perf and fixes issue5360 by correctly reusing hist, while maintaining low memory usage. Some additional attempt has been made to further reduce memory usage, like changing "pcache[f] = []" to "del pcache[f]". Therefore the result can be both faster and lower memory usage: # with this patch applied MEMORY 47575040 CPUTIME 7.870 REALTIME 7.926 [1]: lrun is a lightweight sandbox built on Linux cgroup and namespace. It's used to measure CPU and memory usage here. Source code is available at github.com/quark-zju/lrun.

     1

  $ hg init base

     2

     3

  $ cd base

     4

  $ echo 'alpha' > alpha

     5

  $ hg ci -A -m 'add alpha'

     6

  adding alpha

     7

  $ cd ..

     8

     9

  $ hg clone base work

    10

  updating to branch default

    11

  1 files updated, 0 files merged, 0 files removed, 0 files unresolved

    12

    13

  $ cd work

    14

  $ echo 'beta' > beta

    15

  $ hg ci -A -m 'add beta'

    16

  adding beta

    17

  $ cd ..

    18

    19

  $ cd base

    20

  $ echo 'gamma' > gamma

    21

  $ hg ci -A -m 'add gamma'

    22

  adding gamma

    23

  $ cd ..

    24

    25

  $ cd work

    26

  $ hg pull -q

    27

  $ hg merge

    28

  1 files updated, 0 files merged, 0 files removed, 0 files unresolved

    29

  (branch merge, don't forget to commit)

    30

    31

Update --clean to revision 1 to simulate a failed merge:

    32

    33

  $ rm alpha beta gamma

    34

  $ hg update --clean 1

    35

  2 files updated, 0 files merged, 0 files removed, 0 files unresolved

    36

    37

  $ cd ..