annotate: pre-calculate the "needed" dictionary (issue5360) stable
authorJun Wu <quark@fb.com>
Fri, 02 Sep 2016 15:20:59 +0100
branchstable
changeset 29861 2f6d5c60f6fc
parent 29853 d3b2da20a9c5
child 29862 e7766022a61a
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.
mercurial/context.py
tests/test-annotate.t
--- a/mercurial/context.py	Thu Sep 01 14:01:43 2016 -0500
+++ b/mercurial/context.py	Fri Sep 02 15:20:59 2016 +0100
@@ -990,15 +990,29 @@
         # bit recursion-hostile. Instead we do an iterative
         # depth-first search.
 
+        # 1st DFS pre-calculates pcache and needed
         visit = [base]
-        hist = {}
         pcache = {}
         needed = {base: 1}
         while visit:
+            f = visit.pop()
+            if f in pcache:
+                continue
+            pl = parents(f)
+            pcache[f] = pl
+            for p in pl:
+                needed[p] = needed.get(p, 0) + 1
+                if p not in pcache:
+                    visit.append(p)
+
+        # 2nd DFS does the actual annotate
+        visit[:] = [base]
+        hist = {}
+        while visit:
             f = visit[-1]
-            pcached = f in pcache
-            if not pcached:
-                pcache[f] = parents(f)
+            if f in hist:
+                visit.pop()
+                continue
 
             ready = True
             pl = pcache[f]
@@ -1006,18 +1020,11 @@
                 if p not in hist:
                     ready = False
                     visit.append(p)
-                if not pcached:
-                    needed[p] = needed.get(p, 0) + 1
             if ready:
                 visit.pop()
-                reusable = f in hist
-                if reusable:
-                    curr = hist[f]
-                else:
-                    curr = decorate(f.data(), f)
+                curr = decorate(f.data(), f)
                 for p in pl:
-                    if not reusable:
-                        curr = pair(hist[p], curr)
+                    curr = pair(hist[p], curr)
                     if needed[p] == 1:
                         del hist[p]
                         del needed[p]
@@ -1025,7 +1032,7 @@
                         needed[p] -= 1
 
                 hist[f] = curr
-                pcache[f] = []
+                del pcache[f]
 
         return zip(hist[base][0], hist[base][1].splitlines(True))
 
--- a/tests/test-annotate.t	Thu Sep 01 14:01:43 2016 -0500
+++ b/tests/test-annotate.t	Fri Sep 02 15:20:59 2016 +0100
@@ -606,3 +606,35 @@
   3: B
 
   $ cd ..
+
+Issue5360: Deleted chunk in p1 of a merge changeset
+
+  $ hg init repo-5360
+  $ cd repo-5360
+  $ echo 1 > a
+  $ hg commit -A a -m 1
+  $ echo 2 >> a
+  $ hg commit -m 2
+  $ echo a > a
+  $ hg commit -m a
+  $ hg update '.^' -q
+  $ echo 3 >> a
+  $ hg commit -m 3 -q
+  $ hg merge 2 -q
+  $ cat > a << EOF
+  > b
+  > 1
+  > 2
+  > 3
+  > a
+  > EOF
+  $ hg resolve --mark -q
+  $ hg commit -m m
+  $ hg annotate a
+  4: b
+  0: 1
+  1: 2
+  3: 3
+  2: a
+
+  $ cd ..