This is an archive of the discontinued Mercurial Phabricator instance.

Differential D5413

manifest: convert a recursive function to iterative one using stacks
ClosedPublic

Authored by pulkit on Dec 12 2018, 8:28 AM.

Details

Reviewers
None
Group Reviewers
hg-reviewers
Commits
rHG2c3f69855ce8: manifest: convert a recursive function to iterative one using stacks
Summary

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.

Diff Detail

Repository
rHG Mercurial
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.

Event Timeline

pulkit created this revision.Dec 12 2018, 8:28 AM
pulkit edited the summary of this revision. (Show Details)Dec 12 2018, 8:34 AM
durin42 added a subscriber: durin42.Jan 9 2019, 3:05 PM
durin42 added inline comments.
mercurial/manifest.py
1139

room for a follow-up: I'm not sure this needs to be a nested function anymore (it could be a separate method on self)

Closed by commit rHG2c3f69855ce8: manifest: convert a recursive function to iterative one using stacks (authored by pulkit). · Explain WhyJan 9 2019, 3:10 PM
This revision was automatically updated to reflect the committed changes.

Revision Contents
Changeset List

PathPackages
Mmercurial/manifest.py (16 lines)

Diff 13106

mercurial/manifest.py

string. string.
''' '''
if match and not match.always(): if match and not match.always():
m1 = self.matches(match) m1 = self.matches(match)
m2 = m2.matches(match) m2 = m2.matches(match)
return m1.diff(m2, clean=clean) return m1.diff(m2, clean=clean)
result = {} result = {}
emptytree = treemanifest() emptytree = treemanifest()
def _diff(t1, t2):
def _iterativediff(t1, t2, stack):
durin42Unsubmitted
Not Done

room for a follow-up: I'm not sure this needs to be a nested function anymore (it could be a separate method on self)

durin42: room for a follow-up: I'm not sure this needs to be a nested function anymore (it could be a…
"""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: if t1._node == t2._node and not t1._dirty and not t2._dirty:
return return
t1._load() t1._load()
t2._load() t2._load()
self._loaddifflazy(t1, t2) self._loaddifflazy(t1, t2)
for d, m1 in t1._dirs.iteritems(): for d, m1 in t1._dirs.iteritems():
m2 = t2._dirs.get(d, emptytree) m2 = t2._dirs.get(d, emptytree)
_diff(m1, m2) stack.append((m1, m2))
for d, m2 in t2._dirs.iteritems(): for d, m2 in t2._dirs.iteritems():
if d not in t1._dirs: if d not in t1._dirs:
_diff(emptytree, m2) stack.append((emptytree, m2))
for fn, n1 in t1._files.iteritems(): for fn, n1 in t1._files.iteritems():
fl1 = t1._flags.get(fn, '') fl1 = t1._flags.get(fn, '')
n2 = t2._files.get(fn, None) n2 = t2._files.get(fn, None)
fl2 = t2._flags.get(fn, '') fl2 = t2._flags.get(fn, '')
if n1 != n2 or fl1 != fl2: if n1 != n2 or fl1 != fl2:
result[t1._subpath(fn)] = ((n1, fl1), (n2, fl2)) result[t1._subpath(fn)] = ((n1, fl1), (n2, fl2))
elif clean: elif clean:
result[t1._subpath(fn)] = None result[t1._subpath(fn)] = None
for fn, n2 in t2._files.iteritems(): for fn, n2 in t2._files.iteritems():
if fn not in t1._files: if fn not in t1._files:
fl2 = t2._flags.get(fn, '') fl2 = t2._flags.get(fn, '')
result[t2._subpath(fn)] = ((None, ''), (n2, fl2)) 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 return result
def unmodifiedsince(self, m2): def unmodifiedsince(self, m2):
return not self._dirty and not m2._dirty and self._node == m2._node return not self._dirty and not m2._dirty and self._node == m2._node
def parse(self, text, readsubtree): def parse(self, text, readsubtree):
selflazy = self._lazydirs selflazy = self._lazydirs
subpath = self._subpath subpath = self._subpath