manifest: convert a recursive function to iterative one using stacks
I am debugging a memory issue from yesterday where `hg update` goes upto taking
22GB of memory on our internal treemanifest repository. This is an interesting
function and I saw memory consumption increasing while this function was
running.
It's sometimes hard to understand a recursive function and also the profile
won't show you actual operations which took time, rather it will show you the
function again and again in profile.
I am yet to notice any memory consumption decrease with this patch, but I
believe this will help like in making this a generator.
Differential Revision: https://phab.mercurial-scm.org/D5413
--- a/mercurial/manifest.py Sun Dec 23 02:01:35 2018 +0530
+++ b/mercurial/manifest.py Wed Dec 12 16:26:58 2018 +0300
@@ -1135,7 +1135,10 @@
return m1.diff(m2, clean=clean)
result = {}
emptytree = treemanifest()
- def _diff(t1, t2):
+
+ def _iterativediff(t1, t2, stack):
+ """compares two tree manifests and append new tree-manifests which
+ needs to be compared to stack"""
if t1._node == t2._node and not t1._dirty and not t2._dirty:
return
t1._load()
@@ -1144,11 +1147,11 @@
for d, m1 in t1._dirs.iteritems():
m2 = t2._dirs.get(d, emptytree)
- _diff(m1, m2)
+ stack.append((m1, m2))
for d, m2 in t2._dirs.iteritems():
if d not in t1._dirs:
- _diff(emptytree, m2)
+ stack.append((emptytree, m2))
for fn, n1 in t1._files.iteritems():
fl1 = t1._flags.get(fn, '')
@@ -1164,7 +1167,12 @@
fl2 = t2._flags.get(fn, '')
result[t2._subpath(fn)] = ((None, ''), (n2, fl2))
- _diff(self, m2)
+ stackls = []
+ _iterativediff(self, m2, stackls)
+ while stackls:
+ t1, t2 = stackls.pop()
+ # stackls is populated in the function call
+ _iterativediff(t1, t2, stackls)
return result
def unmodifiedsince(self, m2):