##// END OF EJS Templates
xdiff: add a preprocessing step that trims files...
xdiff: add a preprocessing step that trims files xdiff has a `xdl_trim_ends` step that removes common lines, unmatchable lines. That is in theory good, but happens too late - after splitting, hashing, and adjusting the hash values so they are unique. Those splitting, hashing and adjusting hash values steps could have noticeable overhead. Diffing two large files with minor (one-line-ish) changes are not uncommon. In that case, the raw performance of those preparation steps seriously matter. Even allocating an O(N) array and storing line offsets to it is expensive. Therefore my previous attempts [1] [2] cannot be good enough since they do not remove the O(N) array assignment. This patch adds a preprocessing step - `xdl_trim_files` that runs before other preprocessing steps. It counts common prefix and suffix and lines in them (needed for displaying line number), without doing anything else. Testing with a crafted large (169MB) file, with minor change: ``` open('a','w').write(''.join('%s\n' % (i % 100000) for i in xrange(30000000) if i != 6000000)) open('b','w').write(''.join('%s\n' % (i % 100000) for i in xrange(30000000) if i != 6003000)) ``` Running xdiff by a simple binary [3], this patch improves the xdiff perf by more than 10x for the above case: ``` # xdiff before this patch 2.41s user 1.13s system 98% cpu 3.592 total # xdiff after this patch 0.14s user 0.16s system 98% cpu 0.309 total # gnu diffutils 0.12s user 0.15s system 98% cpu 0.272 total # (best of 20 runs) ``` It's still slightly slower than GNU diffutils. But it's pretty close now. Testing with real repo data: For the whole repo, this patch makes xdiff 25% faster: ``` # hg perfbdiff --count 100 --alldata -c d334afc585e2 --blocks [--xdiff] # xdiff, after ! wall 0.058861 comb 0.050000 user 0.050000 sys 0.000000 (best of 100) # xdiff, before ! wall 0.077816 comb 0.080000 user 0.080000 sys 0.000000 (best of 91) # bdiff ! wall 0.117473 comb 0.120000 user 0.120000 sys 0.000000 (best of 67) ``` For files that are long (ex. commands.py), the speedup is more than 3x, very significant: ``` # hg perfbdiff --count 3000 --blocks commands.py.i 1 [--xdiff] # xdiff, after ! wall 0.690583 comb 0.690000 user 0.690000 sys 0.000000 (best of 12) # xdiff, before ! wall 2.240361 comb 2.210000 user 2.210000 sys 0.000000 (best of 4) # bdiff ! wall 2.469852 comb 2.440000 user 2.440000 sys 0.000000 (best of 4) ``` [1]: https://phab.mercurial-scm.org/D2631 [2]: https://phab.mercurial-scm.org/D2634 [3]: ``` // Code to run xdiff from command line. No proper error handling. #include <stdlib.h> #include <unistd.h> #include <sys/types.h> #include <sys/stat.h> #include <fcntl.h> #include "mercurial/thirdparty/xdiff/xdiff.h" #define ensure(x) if (!(x)) exit(255); mmfile_t readfile(const char *path) { struct stat st; int fd = open(path, O_RDONLY); fstat(fd, &st); mmfile_t file = { malloc(st.st_size), st.st_size }; ensure(read(fd, file.ptr, st.st_size) == st.st_size); close(fd); return file; } int main(int argc, char const *argv[]) { mmfile_t a = readfile(argv[1]), b = readfile(argv[2]); xpparam_t xpp = {0}; xdemitconf_t xecfg = {0}; xdemitcb_t ecb = {0}; xdl_diff(&a, &b, &xpp, &xecfg, &ecb); return 0; } ``` Differential Revision: https://phab.mercurial-scm.org/D2686

File last commit:

r34216:21fc747e default
r36838:f33a87cf default
Show More
unionrepo.py
259 lines | 9.0 KiB | text/x-python | PythonLexer
Mads Kiilerich
unionrepo: read-only operations on a union of two localrepos...
r18944 # unionrepo.py - repository class for viewing union of repository changesets
#
# Derived from bundlerepo.py
# Copyright 2006, 2007 Benoit Boissinot <bboissin@gmail.com>
# Copyright 2013 Unity Technologies, Mads Kiilerich <madski@unity3d.com>
#
# This software may be used and distributed according to the terms of the
# GNU General Public License version 2 or any later version.
"""Repository class for "in-memory pull" of one local repository to another,
allowing operations like diff and log with revsets.
"""
Gregory Szorc
unionrepo: use absolute_import
r25988 from __future__ import absolute_import
from .i18n import _
from .node import nullid
from . import (
changelog,
cmdutil,
Pierre-Yves David
error: get Abort from 'error' instead of 'util'...
r26587 error,
Gregory Szorc
unionrepo: use absolute_import
r25988 filelog,
localrepo,
manifest,
mdiff,
pathutil,
Pulkit Goyal
py3: use pycompat.getcwd() instead of os.getcwd()...
r30519 pycompat,
Gregory Szorc
unionrepo: use absolute_import
r25988 revlog,
util,
Pierre-Yves David
vfs: use 'vfs' module directly in 'mercurial.unionrepo'...
r31242 vfs as vfsmod,
Gregory Szorc
unionrepo: use absolute_import
r25988 )
Mads Kiilerich
unionrepo: read-only operations on a union of two localrepos...
r18944
class unionrevlog(revlog.revlog):
def __init__(self, opener, indexfile, revlog2, linkmapper):
# How it works:
# To retrieve a revision, we just need to know the node id so we can
# look it up in revlog2.
#
# To differentiate a rev in the second revlog from a rev in the revlog,
# we check revision against repotiprev.
Pierre-Yves David
vfs: use 'vfs' module directly in 'mercurial.unionrepo'...
r31242 opener = vfsmod.readonlyvfs(opener)
Mads Kiilerich
unionrepo: read-only operations on a union of two localrepos...
r18944 revlog.revlog.__init__(self, opener, indexfile)
self.revlog2 = revlog2
n = len(self)
self.repotiprev = n - 1
self.bundlerevs = set() # used by 'bundle()' revset expression
for rev2 in self.revlog2:
rev = self.revlog2.index[rev2]
# rev numbers - in revlog2, very different from self.rev
Pierre-Yves David
unionrepo: take delta base in account with building unified revlog...
r26230 _start, _csize, _rsize, base, linkrev, p1rev, p2rev, node = rev
Mike Edgar
changegroup: add flags field to cg3 delta header...
r27433 flags = _start & 0xFFFF
Mads Kiilerich
unionrepo: read-only operations on a union of two localrepos...
r18944
if linkmapper is None: # link is to same revlog
assert linkrev == rev2 # we never link back
link = n
else: # rev must be mapped from repo2 cl to unified cl by linkmapper
link = linkmapper(linkrev)
Pierre-Yves David
unionrepo: take delta base in account with building unified revlog...
r26230 if linkmapper is not None: # link is to same revlog
base = linkmapper(base)
Mads Kiilerich
unionrepo: read-only operations on a union of two localrepos...
r18944 if node in self.nodemap:
# this happens for the common revlog revisions
self.bundlerevs.add(self.nodemap[node])
continue
p1node = self.revlog2.node(p1rev)
p2node = self.revlog2.node(p2rev)
Mike Edgar
changegroup: add flags field to cg3 delta header...
r27433 e = (flags, None, None, base,
Mads Kiilerich
unionrepo: read-only operations on a union of two localrepos...
r18944 link, self.rev(p1node), self.rev(p2node), node)
self.index.insert(-1, e)
self.nodemap[node] = n
self.bundlerevs.add(n)
n += 1
def _chunk(self, rev):
if rev <= self.repotiprev:
return revlog.revlog._chunk(self, rev)
return self.revlog2._chunk(self.node(rev))
def revdiff(self, rev1, rev2):
"""return or calculate a delta between two revisions"""
if rev1 > self.repotiprev and rev2 > self.repotiprev:
return self.revlog2.revdiff(
self.revlog2.rev(self.node(rev1)),
self.revlog2.rev(self.node(rev2)))
elif rev1 <= self.repotiprev and rev2 <= self.repotiprev:
Wojciech Lopata
unionrevlog: extract 'baserevision' and 'baserevdiff' methods...
r19630 return self.baserevdiff(rev1, rev2)
Mads Kiilerich
unionrepo: read-only operations on a union of two localrepos...
r18944
Jun Wu
unionrepo: avoid unnecessary node -> rev conversion
r31724 return mdiff.textdiff(self.revision(rev1), self.revision(rev2))
Mads Kiilerich
unionrepo: read-only operations on a union of two localrepos...
r18944
Remi Chaintron
revlog: add 'raw' argument to revision and _addrevision...
r30743 def revision(self, nodeorrev, raw=False):
Mads Kiilerich
unionrepo: read-only operations on a union of two localrepos...
r18944 """return an uncompressed revision of a given node or revision
number.
"""
if isinstance(nodeorrev, int):
rev = nodeorrev
node = self.node(rev)
else:
node = nodeorrev
rev = self.rev(node)
if node == nullid:
return ""
if rev > self.repotiprev:
text = self.revlog2.revision(node)
self._cache = (node, rev, text)
else:
Wojciech Lopata
unionrevlog: extract 'baserevision' and 'baserevdiff' methods...
r19630 text = self.baserevision(rev)
Mads Kiilerich
unionrepo: read-only operations on a union of two localrepos...
r18944 # already cached
return text
Wojciech Lopata
unionrevlog: extract 'baserevision' and 'baserevdiff' methods...
r19630 def baserevision(self, nodeorrev):
# Revlog subclasses may override 'revision' method to modify format of
# content retrieved from revlog. To use unionrevlog with such class one
# needs to override 'baserevision' and make more specific call here.
return revlog.revlog.revision(self, nodeorrev)
def baserevdiff(self, rev1, rev2):
# Exists for the same purpose as baserevision.
return revlog.revlog.revdiff(self, rev1, rev2)
Mads Kiilerich
unionrepo: read-only operations on a union of two localrepos...
r18944 def addrevision(self, text, transaction, link, p1=None, p2=None, d=None):
raise NotImplementedError
Yuya Nishihara
revlog: update signature of dummy addgroup() in bundlerepo and unionrepo...
r34216 def addgroup(self, deltas, transaction, addrevisioncb=None):
Mads Kiilerich
unionrepo: read-only operations on a union of two localrepos...
r18944 raise NotImplementedError
def strip(self, rev, minlink):
raise NotImplementedError
def checksize(self):
raise NotImplementedError
class unionchangelog(unionrevlog, changelog.changelog):
def __init__(self, opener, opener2):
changelog.changelog.__init__(self, opener)
linkmapper = None
changelog2 = changelog.changelog(opener2)
unionrevlog.__init__(self, opener, self.indexfile, changelog2,
linkmapper)
Wojciech Lopata
unionrevlog: extract 'baserevision' and 'baserevdiff' methods...
r19630 def baserevision(self, nodeorrev):
# Although changelog doesn't override 'revision' method, some extensions
# may replace this class with another that does. Same story with
# manifest and filelog classes.
return changelog.changelog.revision(self, nodeorrev)
def baserevdiff(self, rev1, rev2):
return changelog.changelog.revdiff(self, rev1, rev2)
Durham Goode
manifest: add unionmanifestlog support...
r30374 class unionmanifest(unionrevlog, manifest.manifestrevlog):
Mads Kiilerich
unionrepo: read-only operations on a union of two localrepos...
r18944 def __init__(self, opener, opener2, linkmapper):
Durham Goode
manifest: add unionmanifestlog support...
r30374 manifest.manifestrevlog.__init__(self, opener)
manifest2 = manifest.manifestrevlog(opener2)
Mads Kiilerich
unionrepo: read-only operations on a union of two localrepos...
r18944 unionrevlog.__init__(self, opener, self.indexfile, manifest2,
linkmapper)
Wojciech Lopata
unionrevlog: extract 'baserevision' and 'baserevdiff' methods...
r19630 def baserevision(self, nodeorrev):
Durham Goode
manifest: add unionmanifestlog support...
r30374 return manifest.manifestrevlog.revision(self, nodeorrev)
Wojciech Lopata
unionrevlog: extract 'baserevision' and 'baserevdiff' methods...
r19630
def baserevdiff(self, rev1, rev2):
Durham Goode
manifest: add unionmanifestlog support...
r30374 return manifest.manifestrevlog.revdiff(self, rev1, rev2)
Wojciech Lopata
unionrevlog: extract 'baserevision' and 'baserevdiff' methods...
r19630
Mads Kiilerich
unionrepo: read-only operations on a union of two localrepos...
r18944 class unionfilelog(unionrevlog, filelog.filelog):
def __init__(self, opener, path, opener2, linkmapper, repo):
filelog.filelog.__init__(self, opener, path)
filelog2 = filelog.filelog(opener2, path)
unionrevlog.__init__(self, opener, self.indexfile, filelog2,
linkmapper)
self._repo = repo
Wojciech Lopata
unionrevlog: extract 'baserevision' and 'baserevdiff' methods...
r19630 def baserevision(self, nodeorrev):
return filelog.filelog.revision(self, nodeorrev)
def baserevdiff(self, rev1, rev2):
return filelog.filelog.revdiff(self, rev1, rev2)
Mike Edgar
revlog: add "iscensored()" to revlog public API...
r24118 def iscensored(self, rev):
"""Check if a revision is censored."""
if rev <= self.repotiprev:
return filelog.filelog.iscensored(self, rev)
Sean Farley
unionrepo: fix wrong rev being checked in iscensored (issue5024)
r27723 node = self.node(rev)
return self.revlog2.iscensored(self.revlog2.rev(node))
Mike Edgar
revlog: add "iscensored()" to revlog public API...
r24118
Mads Kiilerich
unionrepo: read-only operations on a union of two localrepos...
r18944 class unionpeer(localrepo.localpeer):
def canpush(self):
return False
class unionrepository(localrepo.localrepository):
def __init__(self, ui, path, path2):
localrepo.localrepository.__init__(self, ui, path)
Mads Kiilerich
config: set a 'source' in most cases where config don't come from file but code...
r20790 self.ui.setconfig('phases', 'publish', False, 'unionrepo')
Mads Kiilerich
unionrepo: read-only operations on a union of two localrepos...
r18944
self._url = 'union:%s+%s' % (util.expandpath(path),
util.expandpath(path2))
self.repo2 = localrepo.localrepository(ui, path2)
@localrepo.unfilteredpropertycache
def changelog(self):
Angel Ezquerra
localrepo: remove all external users of localrepo.sopener...
r23878 return unionchangelog(self.svfs, self.repo2.svfs)
Mads Kiilerich
unionrepo: read-only operations on a union of two localrepos...
r18944
def _clrev(self, rev2):
"""map from repo2 changelog rev to temporary rev in self.changelog"""
node = self.repo2.changelog.node(rev2)
return self.changelog.rev(node)
Durham Goode
manifest: move manifest creation to a helper function...
r30218 def _constructmanifest(self):
Angel Ezquerra
localrepo: remove all external users of localrepo.sopener...
r23878 return unionmanifest(self.svfs, self.repo2.svfs,
Pierre-Yves David
unionrepo: properly handle hidden linkrev in revlog (issue5070)...
r28222 self.unfiltered()._clrev)
Mads Kiilerich
unionrepo: read-only operations on a union of two localrepos...
r18944
def url(self):
return self._url
def file(self, f):
Angel Ezquerra
localrepo: remove all external users of localrepo.sopener...
r23878 return unionfilelog(self.svfs, f, self.repo2.svfs,
Pierre-Yves David
unionrepo: properly handle hidden linkrev in revlog (issue5070)...
r28222 self.unfiltered()._clrev, self)
Mads Kiilerich
unionrepo: read-only operations on a union of two localrepos...
r18944
def close(self):
self.repo2.close()
def cancopy(self):
return False
def peer(self):
return unionpeer(self)
def getcwd(self):
Pulkit Goyal
py3: use pycompat.getcwd() instead of os.getcwd()...
r30519 return pycompat.getcwd() # always outside the repo
Mads Kiilerich
unionrepo: read-only operations on a union of two localrepos...
r18944
def instance(ui, path, create):
if create:
Pierre-Yves David
error: get Abort from 'error' instead of 'util'...
r26587 raise error.Abort(_('cannot create new union repository'))
configitems: register the 'bundle.mainreporoot' config
r33179 parentpath = ui.config("bundle", "mainreporoot")
Mads Kiilerich
unionrepo: read-only operations on a union of two localrepos...
r18944 if not parentpath:
# try to find the correct path to the working directory repo
Pulkit Goyal
py3: use pycompat.getcwd() instead of os.getcwd()...
r30519 parentpath = cmdutil.findrepo(pycompat.getcwd())
Mads Kiilerich
unionrepo: read-only operations on a union of two localrepos...
r18944 if parentpath is None:
parentpath = ''
if parentpath:
# Try to make the full path relative so we get a nice, short URL.
# In particular, we don't want temp dir names in test outputs.
Pulkit Goyal
py3: use pycompat.getcwd() instead of os.getcwd()...
r30519 cwd = pycompat.getcwd()
Mads Kiilerich
unionrepo: read-only operations on a union of two localrepos...
r18944 if parentpath == cwd:
parentpath = ''
else:
FUJIWARA Katsunori
unionrepo: use pathutil.normasprefix to ensure os.sep at the end of cwd...
r24835 cwd = pathutil.normasprefix(cwd)
Mads Kiilerich
unionrepo: read-only operations on a union of two localrepos...
r18944 if parentpath.startswith(cwd):
parentpath = parentpath[len(cwd):]
if path.startswith('union:'):
s = path.split(":", 1)[1].split("+", 1)
if len(s) == 1:
repopath, repopath2 = parentpath, s[0]
else:
repopath, repopath2 = s
else:
repopath, repopath2 = parentpath, path
return unionrepository(ui, repopath, repopath2)