This is an archive of the discontinued Mercurial Phabricator instance.

Differential D1521

clindex: use childmap to calculate phases
AbandonedPublic

Authored by quark on Nov 27 2017, 1:30 PM.
Tags
None
Subscribers
None

Details

Reviewers
None
Group Reviewers
Restricted Project
Summary

Calculating phases is O(len(changelog)) since it scans revisions starting
with min(draft()) (unfiltered). Use the childmap so it is actually
O(len(not public())).

This saves 100+ms for a fbsource repo created in late 2015.

Besides, the old phases code build a O(len(changelog)) Python list for
rev -> phase queries. This patch does not build such list and saves
O(len(changelog)) memory.

Test Plan

With verify mode on, run core hg tests and make sure there is no
inconsistent cases with the original phases implementation.

Diff Detail

Repository
rFBHGX Facebook Mercurial Extensions
Lint
Lint Skipped
Unit
Unit Tests Skipped

Event Timeline

quark created this revision.Nov 27 2017, 1:30 PM
Herald added a reviewer: Restricted Project. · View Herald TranscriptNov 27 2017, 1:30 PM
quark updated this revision to Diff 4458.Dec 14 2017, 9:21 PM
quark abandoned this revision.Dec 7 2019, 2:13 AM

Took another approach.

Revision Contents
Changeset List

PathPackages
Mhgext3rd/clindex.pyx (38 lines)

Diff 4458

hgext3rd/clindex.pyx

# Copyright 2017 Facebook, Inc. # Copyright 2017 Facebook, Inc.
# #
# This software may be used and distributed according to the terms of the # This software may be used and distributed according to the terms of the
# GNU General Public License version 2 or any later version. # GNU General Public License version 2 or any later version.
"""alternative changelog index """alternative changelog index
This extension replaces certain parts of changelog index algorithms to make it This extension replaces certain parts of changelog index algorithms to make it
more efficient when changelog is large. more efficient when changelog is large.
Config:: Config::
[clindex] [clindex]
# Use Rust childmap. # Use Rust childmap.
# It's currently used to speed up phases calculation.
childmap = True childmap = True
# Use Rust nodemap # Use Rust nodemap
nodemap = True nodemap = True
# Verify operations against other implementations. # Verify operations against other implementations.
# Turn this off for performance. # Turn this off for performance.
verify = True verify = True
def commonancestorsheads(self, *revs): def commonancestorsheads(self, *revs):
return self._origindex.commonancestorsheads(*revs) return self._origindex.commonancestorsheads(*revs)
def __getitem__(self, int rev): def __getitem__(self, int rev):
return self._origindex[rev] return self._origindex[rev]
def computephasesmapsets(self, roots): def computephasesmapsets(self, roots):
if not self._config.childmap:
return self._origindex.computephasesmapsets(roots) return self._origindex.computephasesmapsets(roots)
# using childmap
drafts = self._descendants(roots[0])
secrets = self._descendants(roots[1])
drafts -= secrets
sets = [None, drafts, secrets]
if self._config.verify:
origlen, origsets = self._origindex.computephasesmapsets(roots)
for phase in (1, 2):
origset = origsets[phase]
thisset = sets[phase]
added = thisset - origset
removed = origset - thisset
if added or removed:
_logandraise(
self._vfs,
'phases: inconsistent result(%s):\n added %r'
'\n removed %r' % (phase, added, removed))
return len(self), sets
cpdef _descendants(self, rootrevs):
assert self._config.childmap
queue = rootrevs[:]
revs = set()
while queue:
rev = queue.pop()
if rev in revs:
continue
revs.add(rev)
queue.extend(self._children(rev))
return revs
cpdef _children(self, int rev):
assert self._config.childmap
return self._childmap[rev]
def reachableroots2(self, int minroot, heads, roots, includepath): def reachableroots2(self, int minroot, heads, roots, includepath):
return self._origindex.reachableroots2(minroot, heads, roots, return self._origindex.reachableroots2(minroot, heads, roots,
includepath) includepath)
def headrevs(self): def headrevs(self):
return self._origindex.headrevs() return self._origindex.headrevs()