Mercurial > hg
comparison mercurial/context.py @ 29861:2f6d5c60f6fc stable
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.
author | Jun Wu <quark@fb.com> |
---|---|
date | Fri, 02 Sep 2016 15:20:59 +0100 |
parents | 576ff900fcc7 |
children | 2c302c654451 |
comparison
equal
deleted
inserted
replaced
29853:d3b2da20a9c5 | 29861:2f6d5c60f6fc |
---|---|
988 | 988 |
989 # This algorithm would prefer to be recursive, but Python is a | 989 # This algorithm would prefer to be recursive, but Python is a |
990 # bit recursion-hostile. Instead we do an iterative | 990 # bit recursion-hostile. Instead we do an iterative |
991 # depth-first search. | 991 # depth-first search. |
992 | 992 |
993 # 1st DFS pre-calculates pcache and needed | |
993 visit = [base] | 994 visit = [base] |
994 hist = {} | |
995 pcache = {} | 995 pcache = {} |
996 needed = {base: 1} | 996 needed = {base: 1} |
997 while visit: | 997 while visit: |
998 f = visit.pop() | |
999 if f in pcache: | |
1000 continue | |
1001 pl = parents(f) | |
1002 pcache[f] = pl | |
1003 for p in pl: | |
1004 needed[p] = needed.get(p, 0) + 1 | |
1005 if p not in pcache: | |
1006 visit.append(p) | |
1007 | |
1008 # 2nd DFS does the actual annotate | |
1009 visit[:] = [base] | |
1010 hist = {} | |
1011 while visit: | |
998 f = visit[-1] | 1012 f = visit[-1] |
999 pcached = f in pcache | 1013 if f in hist: |
1000 if not pcached: | 1014 visit.pop() |
1001 pcache[f] = parents(f) | 1015 continue |
1002 | 1016 |
1003 ready = True | 1017 ready = True |
1004 pl = pcache[f] | 1018 pl = pcache[f] |
1005 for p in pl: | 1019 for p in pl: |
1006 if p not in hist: | 1020 if p not in hist: |
1007 ready = False | 1021 ready = False |
1008 visit.append(p) | 1022 visit.append(p) |
1009 if not pcached: | |
1010 needed[p] = needed.get(p, 0) + 1 | |
1011 if ready: | 1023 if ready: |
1012 visit.pop() | 1024 visit.pop() |
1013 reusable = f in hist | 1025 curr = decorate(f.data(), f) |
1014 if reusable: | |
1015 curr = hist[f] | |
1016 else: | |
1017 curr = decorate(f.data(), f) | |
1018 for p in pl: | 1026 for p in pl: |
1019 if not reusable: | 1027 curr = pair(hist[p], curr) |
1020 curr = pair(hist[p], curr) | |
1021 if needed[p] == 1: | 1028 if needed[p] == 1: |
1022 del hist[p] | 1029 del hist[p] |
1023 del needed[p] | 1030 del needed[p] |
1024 else: | 1031 else: |
1025 needed[p] -= 1 | 1032 needed[p] -= 1 |
1026 | 1033 |
1027 hist[f] = curr | 1034 hist[f] = curr |
1028 pcache[f] = [] | 1035 del pcache[f] |
1029 | 1036 |
1030 return zip(hist[base][0], hist[base][1].splitlines(True)) | 1037 return zip(hist[base][0], hist[base][1].splitlines(True)) |
1031 | 1038 |
1032 def ancestors(self, followfirst=False): | 1039 def ancestors(self, followfirst=False): |
1033 visit = {} | 1040 visit = {} |