Mercurial > hg
view hgext/convert/bzr.py @ 42354:dbd0fcca6dfc
discovery: slowly increase sampling size
Some pathological discovery runs can requires many roundtrip. When this happens
things can get very slow.
To make the algorithm more resilience again such pathological case. We slowly
increase the sample size with each roundtrip (+5%). This will have a negligible
impact on "normal" discovery with few roundtrips, but a large positive impact of
case with many roundtrips. Asking more question per roundtrip helps to reduce
the undecided set faster. Instead of reducing the undecided set a linear speed
(in the worst case), we reduce it as a guaranteed (small) exponential rate. The
data below show this slow ramp up in sample size:
round trip | 1 | 5 | 10 | 20 | 50 | 100 | 130 |
sample size | 200 | 254 | 321 | 517 | 2 199 | 25 123 | 108 549 |
covered nodes | 200 | 1 357 | 2 821 | 7 031 | 42 658 | 524 530 | 2 276 755 |
To be a bit more concrete, lets take a very pathological case as an example. We
are doing discovery from a copy of Mozilla-try to a more recent version of
mozilla-unified. Mozilla-unified heads are unknown to the mozilla-try repo and
there are over 1 million "missing" changesets. (the discovery is "local" to
avoid network interference)
Without this change, the discovery:
- last 1858 seconds (31 minutes),
- does 1700 round trip,
- asking about 340 000 nodes.
With this change, the discovery:
- last 218 seconds (3 minutes, 38 seconds a -88% improvement),
- does 94 round trip (-94%),
- asking about 344 211 nodes (+1%).
Of course, this is an extreme case (and 3 minutes is still slow). However this
give a good example of how this sample size increase act as a safety net
catching any bad situations.
We could image a steeper increase than 5%. For example 10% would give the
following number:
round trip | 1 | 5 | 10 | 20 | 50 | 75 | 100 |
sample size | 200 | 321 | 514 | 1 326 | 23 060 | 249 812 | 2 706 594 |
covered nodes | 200 | 1 541 | 3 690 | 12 671 | 251 871 | 2 746 254 | 29 770 966 |
In parallel, it is useful to understand these pathological cases and improve
them. However the current change provides a general purpose safety net to smooth
the impact of pathological cases.
To avoid issue with older http server, the increase in sample size only occurs
if the protocol has not limit on command argument size.
author | Pierre-Yves David <pierre-yves.david@octobus.net> |
---|---|
date | Tue, 21 May 2019 13:08:22 +0200 |
parents | 85da230c316a |
children | 2372284d9457 |
line wrap: on
line source
# bzr.py - bzr support for the convert extension # # Copyright 2008, 2009 Marek Kubica <marek@xivilization.net> and others # # This software may be used and distributed according to the terms of the # GNU General Public License version 2 or any later version. # This module is for handling 'bzr', that was formerly known as Bazaar-NG; # it cannot access 'bar' repositories, but they were never used very much from __future__ import absolute_import import os from mercurial.i18n import _ from mercurial import ( demandimport, error ) from . import common # these do not work with demandimport, blacklist demandimport.IGNORES.update([ 'bzrlib.transactions', 'bzrlib.urlutils', 'ElementPath', ]) try: # bazaar imports import bzrlib.bzrdir import bzrlib.errors import bzrlib.revision import bzrlib.revisionspec bzrdir = bzrlib.bzrdir errors = bzrlib.errors revision = bzrlib.revision revisionspec = bzrlib.revisionspec revisionspec.RevisionSpec except ImportError: pass supportedkinds = ('file', 'symlink') class bzr_source(common.converter_source): """Reads Bazaar repositories by using the Bazaar Python libraries""" def __init__(self, ui, repotype, path, revs=None): super(bzr_source, self).__init__(ui, repotype, path, revs=revs) if not os.path.exists(os.path.join(path, '.bzr')): raise common.NoRepo(_('%s does not look like a Bazaar repository') % path) try: # access bzrlib stuff bzrdir except NameError: raise common.NoRepo(_('Bazaar modules could not be loaded')) path = os.path.abspath(path) self._checkrepotype(path) try: self.sourcerepo = bzrdir.BzrDir.open(path).open_repository() except errors.NoRepositoryPresent: raise common.NoRepo(_('%s does not look like a Bazaar repository') % path) self._parentids = {} self._saverev = ui.configbool('convert', 'bzr.saverev') def _checkrepotype(self, path): # Lightweight checkouts detection is informational but probably # fragile at API level. It should not terminate the conversion. try: dir = bzrdir.BzrDir.open_containing(path)[0] try: tree = dir.open_workingtree(recommend_upgrade=False) branch = tree.branch except (errors.NoWorkingTree, errors.NotLocalUrl): tree = None branch = dir.open_branch() if (tree is not None and tree.bzrdir.root_transport.base != branch.bzrdir.root_transport.base): self.ui.warn(_('warning: lightweight checkouts may cause ' 'conversion failures, try with a regular ' 'branch instead.\n')) except Exception: self.ui.note(_('bzr source type could not be determined\n')) def before(self): """Before the conversion begins, acquire a read lock for all the operations that might need it. Fortunately read locks don't block other reads or writes to the repository, so this shouldn't have any impact on the usage of the source repository. The alternative would be locking on every operation that needs locks (there are currently two: getting the file and getting the parent map) and releasing immediately after, but this approach can take even 40% longer.""" self.sourcerepo.lock_read() def after(self): self.sourcerepo.unlock() def _bzrbranches(self): return self.sourcerepo.find_branches(using=True) def getheads(self): if not self.revs: # Set using=True to avoid nested repositories (see issue3254) heads = sorted([b.last_revision() for b in self._bzrbranches()]) else: revid = None for branch in self._bzrbranches(): try: r = revisionspec.RevisionSpec.from_string(self.revs[0]) info = r.in_history(branch) except errors.BzrError: pass revid = info.rev_id if revid is None: raise error.Abort(_('%s is not a valid revision') % self.revs[0]) heads = [revid] # Empty repositories return 'null:', which cannot be retrieved heads = [h for h in heads if h != 'null:'] return heads def getfile(self, name, rev): revtree = self.sourcerepo.revision_tree(rev) fileid = revtree.path2id(name.decode(self.encoding or 'utf-8')) kind = None if fileid is not None: kind = revtree.kind(fileid) if kind not in supportedkinds: # the file is not available anymore - was deleted return None, None mode = self._modecache[(name, rev)] if kind == 'symlink': target = revtree.get_symlink_target(fileid) if target is None: raise error.Abort(_('%s.%s symlink has no target') % (name, rev)) return target, mode else: sio = revtree.get_file(fileid) return sio.read(), mode def getchanges(self, version, full): if full: raise error.Abort(_("convert from cvs does not support --full")) self._modecache = {} self._revtree = self.sourcerepo.revision_tree(version) # get the parentids from the cache parentids = self._parentids.pop(version) # only diff against first parent id prevtree = self.sourcerepo.revision_tree(parentids[0]) files, changes = self._gettreechanges(self._revtree, prevtree) return files, changes, set() def getcommit(self, version): rev = self.sourcerepo.get_revision(version) # populate parent id cache if not rev.parent_ids: parents = [] self._parentids[version] = (revision.NULL_REVISION,) else: parents = self._filterghosts(rev.parent_ids) self._parentids[version] = parents branch = self.recode(rev.properties.get('branch-nick', u'default')) if branch == 'trunk': branch = 'default' return common.commit(parents=parents, date='%d %d' % (rev.timestamp, -rev.timezone), author=self.recode(rev.committer), desc=self.recode(rev.message), branch=branch, rev=version, saverev=self._saverev) def gettags(self): bytetags = {} for branch in self._bzrbranches(): if not branch.supports_tags(): return {} tagdict = branch.tags.get_tag_dict() for name, rev in tagdict.iteritems(): bytetags[self.recode(name)] = rev return bytetags def getchangedfiles(self, rev, i): self._modecache = {} curtree = self.sourcerepo.revision_tree(rev) if i is not None: parentid = self._parentids[rev][i] else: # no parent id, get the empty revision parentid = revision.NULL_REVISION prevtree = self.sourcerepo.revision_tree(parentid) changes = [e[0] for e in self._gettreechanges(curtree, prevtree)[0]] return changes def _gettreechanges(self, current, origin): revid = current._revision_id changes = [] renames = {} seen = set() # Fall back to the deprecated attribute for legacy installations. try: inventory = origin.root_inventory except AttributeError: inventory = origin.inventory # Process the entries by reverse lexicographic name order to # handle nested renames correctly, most specific first. curchanges = sorted(current.iter_changes(origin), key=lambda c: c[1][0] or c[1][1], reverse=True) for (fileid, paths, changed_content, versioned, parent, name, kind, executable) in curchanges: if paths[0] == u'' or paths[1] == u'': # ignore changes to tree root continue # bazaar tracks directories, mercurial does not, so # we have to rename the directory contents if kind[1] == 'directory': if kind[0] not in (None, 'directory'): # Replacing 'something' with a directory, record it # so it can be removed. changes.append((self.recode(paths[0]), revid)) if kind[0] == 'directory' and None not in paths: renaming = paths[0] != paths[1] # neither an add nor an delete - a move # rename all directory contents manually subdir = inventory.path2id(paths[0]) # get all child-entries of the directory for name, entry in inventory.iter_entries(subdir): # hg does not track directory renames if entry.kind == 'directory': continue frompath = self.recode(paths[0] + '/' + name) if frompath in seen: # Already handled by a more specific change entry # This is important when you have: # a => b # a/c => a/c # Here a/c must not be renamed into b/c continue seen.add(frompath) if not renaming: continue topath = self.recode(paths[1] + '/' + name) # register the files as changed changes.append((frompath, revid)) changes.append((topath, revid)) # add to mode cache mode = ((entry.executable and 'x') or (entry.kind == 'symlink' and 's') or '') self._modecache[(topath, revid)] = mode # register the change as move renames[topath] = frompath # no further changes, go to the next change continue # we got unicode paths, need to convert them path, topath = paths if path is not None: path = self.recode(path) if topath is not None: topath = self.recode(topath) seen.add(path or topath) if topath is None: # file deleted changes.append((path, revid)) continue # renamed if path and path != topath: renames[topath] = path changes.append((path, revid)) # populate the mode cache kind, executable = [e[1] for e in (kind, executable)] mode = ((executable and 'x') or (kind == 'symlink' and 'l') or '') self._modecache[(topath, revid)] = mode changes.append((topath, revid)) return changes, renames def _filterghosts(self, ids): """Filters out ghost revisions which hg does not support, see <http://bazaar-vcs.org/GhostRevision> """ parentmap = self.sourcerepo.get_parent_map(ids) parents = tuple([parent for parent in ids if parent in parentmap]) return parents