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

     2

== Local

     3

Ready.

     4

Un and Deux

     5

Eins und Zwei

     6

One and Two

     7

Nope

     8

Eins und Zwei

     9

Hello, John Smith

    10

Ready.

    11

Uno und Due

    12

    13

== Remote

    14

Ready.

    15

REQ: foo?one=Vo&two=Efvy

    16

  -> Vo!boe!Efvy

    17

Un and Deux

    18

REQ: bar?b=Fjot&a=[xfj

    19

  -> Fjot!voe![xfj

    20

Eins und Zwei

    21

REQ: batch?cmds=foo:one=Pof,two=Uxp;bar:b=Fjot,a=[xfj

    22

  -> Pof!boe!Uxp;Fjot!voe![xfj

    23

REQ: greet?name=Kpio!Tnjui

    24

  -> Ifmmp-!Kpio!Tnjui

    25

REQ: batch?cmds=bar:b=Vop,a=Evf

    26

  -> Vop!voe!Evf

    27

One and Two

    28

Nope

    29

Eins und Zwei

    30

Hello, John Smith

    31

Ready.

    32

Uno und Due