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.

  $ hg init a
  $ cd a
  $ echo a > a
  $ hg ci -Am0
  adding a
  $ echo b > b
  $ hg ci -Am1
  adding b
  $ hg tag -r0 default
  warning: tag default conflicts with existing branch name
  $ hg log
  changeset:   2:30a83d1e4a1e
  tag:         tip
  user:        test
  date:        Thu Jan 01 00:00:00 1970 +0000
  summary:     Added tag default for changeset f7b1eb17ad24
  
  changeset:   1:925d80f479bb
  user:        test
  date:        Thu Jan 01 00:00:00 1970 +0000
  summary:     1
  
  changeset:   0:f7b1eb17ad24
  tag:         default
  user:        test
  date:        Thu Jan 01 00:00:00 1970 +0000
  summary:     0
  
  $ hg update 'tag(default)'
  0 files updated, 0 files merged, 2 files removed, 0 files unresolved
  $ hg parents
  changeset:   0:f7b1eb17ad24
  tag:         default
  user:        test
  date:        Thu Jan 01 00:00:00 1970 +0000
  summary:     0
  
  $ hg update 'branch(default)'
  2 files updated, 0 files merged, 0 files removed, 0 files unresolved
  $ hg parents
  changeset:   2:30a83d1e4a1e
  tag:         tip
  user:        test
  date:        Thu Jan 01 00:00:00 1970 +0000
  summary:     Added tag default for changeset f7b1eb17ad24
  

  $ cd ..