This is an archive of the discontinued Mercurial Phabricator instance.

Differential D1472

clindex: integrate Rust nodemap
ClosedPublic

Authored by quark on Nov 20 2017, 7:11 PM.
Tags
None
Subscribers
durham

Details

Reviewers
durham
Group Reviewers
Restricted Project
Commits
rFBHGX2c843b93364b: clindex: integrate Rust nodemap
Summary

Change clindex so it can use the rust nodemap for node lookups and partial
match. By default, the code runs in a "verify" mode that compares the rust
nodemap against the original nodemap. Once we gain more confident, we can
drop the support of the original nodemap (so it does not build a radix
tree).

After this, there is no need to enable perftweaks.cachenoderevs or
fastpartialmatch.

Performance wise, the nodemap seems to be a bit faster than revlog.c trie.
The former takes 91% (+/-5%) of the time needed for the latter. That was
tested by running the following script 20 times on fbsource:

from mercurial.cext import parsers
from hgext3rd.rust import indexes
import contextlib, os
m = {}
@contextlib.contextmanager
def measure(name):
    utime, stime, cutime, cstime, elapsed = os.times()
    try:
        yield
    finally:
        utime2, stime2, cutime, cstime, elapsed2 = os.times()
        print('%14s: User %.3f  Sys %.3f  Real %.3f'
              % (name, utime2 - utime, stime2 - stime, elapsed2 - elapsed))
        m[name] = elapsed2 - elapsed
cl = open('00changelog.i').read()
with measure('nodemap'):
    nm = indexes.nodemap(cl, indexes.nodemap.emptyindexbuffer())
    nm.partialmatch('da0443cd533f4073e8d0e324d55')
with measure('revlog index'):
    idx = parsers.index(cl, False)
    idx.partialmatch('da0443cd533f4073e8d0e324d55')
print('nodemap: %.2f revlog' % (m['nodemap'] / m['revlog index']))
Test Plan

Checks clindex with rust nodemap can be a drop-in replacement

Change revlog.py temporarily to disable its inline feature so clindex will be used:

-_maxinline = 131072
+_maxinline = 0

Then run tests with the extension enabled:

./run-tests.py -l --extra-config-opt=extensions.clindex= --extra-config-opt=clindex.lagthreshold=1 --extra-config-opt=clindex.logpath=/tmp/l  -j `nproc`

Check the test output change makes sense (ex. extension list change, .hg
content change, help text change) and /tmp/l does not have contents like
"inconsistent" or "corrupted".

Check memory safety

Rebuild Python to be valgrind friendly (--without-pymalloc --with-valgrind),

Disable re2 by changing import re2 in util.py to import not_exist since it
will trigger a lot of "read uninitialized memory" reports.

Use valgrind to run a few hg commands:

valgrind python2 hg commit -m 1 --config extensions.clindex= --config clindex.lagthreshold=1

Especially, do a rebase with obsstore disabled to exercise the "strip" code
path and make sure valgrind does not report anything except for memory leak
(normal for Python).

Diff Detail

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

Event Timeline

quark created this revision.Nov 20 2017, 7:11 PM
Herald added a reviewer: Restricted Project. · View Herald TranscriptNov 20 2017, 7:11 PM
quark added a comment.EditedNov 21 2017, 1:32 AM

I will split the diff.

EDIT: does not look that easy to split.

quark planned changes to this revision.Nov 21 2017, 12:14 PM
quark added inline comments.
hgext3rd/clindex.pyx
424

This method got missing when rebasing.

quark updated this revision to Diff 3742.Nov 21 2017, 3:25 PM
quark edited the test plan for this revision. (Show Details)Nov 22 2017, 8:45 PM
quark updated this revision to Diff 3791.
quark edited the test plan for this revision. (Show Details)Nov 22 2017, 8:52 PM
quark edited the summary of this revision. (Show Details)Nov 22 2017, 9:31 PM
durham requested changes to this revision.Dec 6 2017, 7:48 PM
durham added a subscriber: durham.

Small comments

hgext3rd/clindex.pyx
84

And we're relying on the mmap config to make this fast right?

89

I think this was covered in one of your other diffs, but what happens if the nodemap index is out of date? It builds an inmemory index of the new stuff at the end of the origindex file?

185

If config.nodemap is False, rustnodemap is undefined here right? Is that a problem?

334

Hmm, so this means any command that accesses to repositories changelogs in one process will write logs to the wrong place? And they'll probably read the wrong config as well?

Since the clindex class has access to a vfs, which I assume is the svfs, could we have these global objects at least be in a dictionary indexed by svfs root path? So multiple repositories don't collide?

393

Should we set _logpath equal to False here or something? So we don't repeatedly try to open the bad logpath?

This revision now requires changes to proceed.Dec 6 2017, 7:48 PM
quark added inline comments.Dec 7 2017, 3:38 PM
hgext3rd/clindex.pyx
84

The mmap config removes cost reading .i happening at revlog.__init__, not here. Constructing origindextype is fast regardless of the mmap option.

89

It builds the "side index" as a separate index. It's not mutating the main index since there is no way to copy-on-write plus appending the main index buffer. It's possible to implement such copy-on-write in user-space. But that might introduce too much overhead.

185

It's a problem introduced by multiple amends. Will change.

334

clindex uses cachevfs.

I think config and cachevfs will be right since when _wrapchangelog re-assign them, the re-assignment won't affect existing clindex objects.

Log paths could be wrong if repo changed, yes. But blackbox and commandserver.logpath have similar issues. Maybe we should just use a single global path like /var/log/mercurial/.... I noticed infinitepush is already using that.

quark updated this revision to Diff 4372.Dec 11 2017, 7:20 PM
quark added inline comments.Dec 11 2017, 7:22 PM
hgext3rd/clindex.pyx
393

Should be fine? blackbox does not have that logic and there were no complaints yet.

durham accepted this revision.Dec 14 2017, 7:38 PM
This revision is now accepted and ready to land.Dec 14 2017, 7:38 PM
quark updated this revision to Diff 4454.Dec 14 2017, 9:21 PM
quark edited the summary of this revision. (Show Details)Dec 14 2017, 10:15 PM
Closed by commit rFBHGX2c843b93364b: clindex: integrate Rust nodemap (authored by quark). · Explain WhyDec 15 2017, 2:35 PM
This revision was automatically updated to reflect the committed changes.

Revision Contents
Changeset List

PathPackages
Mhgext3rd/clindex.pyx (396 lines)

Diff 4513

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::
[clindex]
# Use Rust nodemap
nodemap = True
# Verify operations against other implementations.
# Turn this off for performance.
verify = True
# Incrementally build Rust nodemap once it misses 20k revisions
lagthreshold = 20000
# Path to write logs (default: $repo/.hg/cache/clindex.log)
logpath = /tmp/a.log
""" """
from __future__ import absolute_import from __future__ import absolute_import
import datetime
import errno
import os
from mercurial import ( from mercurial import (
changelog, changelog,
chgserver,
error, error,
extensions, extensions,
localrepo,
policy, policy,
registrar,
revlog, revlog,
util,
vfs as vfsmod,
) )
origindex = policy.importmod('parsers').index from mercurial.node import (
hex,
nullhex,
nullid,
)
from .rust import indexes
configtable = {}
configitem = registrar.configitem(configtable)
configitem('clindex', 'nodemap', default=True)
configitem('clindex', 'verify', default=True)
# Inserting 20k nodes takes about 2ms. See https://phab.mercurial-scm.org/D1291
# for the table of node count and performance.
configitem('clindex', 'lagthreshold', default=20000)
# Path to write logs.
configitem('clindex', 'logpath', default=None)
origindextype = policy.importmod('parsers').index
# cdef is important for performance because it avoids dict lookups: # cdef is important for performance because it avoids dict lookups:
# - `self._origindex` becomes `some_c_struct_pointer->_origindex` # - `self._origindex` becomes `some_c_struct_pointer->_origindex`
# - `__getitem__`, `__len__` will be using `PyMappingMethods` APIs # - `__getitem__`, `__len__` will be using `PyMappingMethods` APIs
cdef class clindex(object): cdef class clindex(object):
cdef readonly _changelog
cdef readonly localconfig _config
cdef readonly nodemap _nodemap
cdef _origindex cdef _origindex
cdef _vfs
def __init__(self, data, inlined): def __init__(self, data, inlined, vfs, config):
assert not inlined assert not inlined
self._origindex = origindex(data, inlined) assert vfs
self._origindex = origindextype(data, inlined)
durhamUnsubmitted
Not Done

And we're relying on the mmap config to make this fast right?

durham: And we're relying on the mmap config to make this fast right?
quarkAuthorUnsubmitted
Not Done

The mmap config removes cost reading .i happening at revlog.__init__, not here. Constructing origindextype is fast regardless of the mmap option.

quark: The mmap config removes cost reading `.i` happening at `revlog.__init__`, not here.
self._changelog = data
# Copy the config so it can be changed just for this clindex object.
# For example, disabling Rust nodemap temporarily if strip happens.
self._config = config.copy()
self._nodemap = nodemap(self._origindex, data, vfs, config)
durhamUnsubmitted
Not Done

I think this was covered in one of your other diffs, but what happens if the nodemap index is out of date? It builds an inmemory index of the new stuff at the end of the origindex file?

durham: I think this was covered in one of your other diffs, but what happens if the nodemap index is…
quarkAuthorUnsubmitted
Not Done

It builds the "side index" as a separate index. It's not mutating the main index since there is no way to copy-on-write plus appending the main index buffer. It's possible to implement such copy-on-write in user-space. But that might introduce too much overhead.

quark: It builds the "side index" as a separate index. It's not mutating the main index since there is…
self._vfs = vfs
def ancestors(self, *revs): def ancestors(self, *revs):
return self._origindex.ancestors(*revs) return self._origindex.ancestors(*revs)
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):
def headrevsfiltered(self, filtered): def headrevsfiltered(self, filtered):
return self._origindex.headrevsfiltered(filtered) return self._origindex.headrevsfiltered(filtered)
def deltachain(self, rev, stoprev, generaldelta): def deltachain(self, rev, stoprev, generaldelta):
return self._origindex.deltachain(rev, stoprev, generaldelta) return self._origindex.deltachain(rev, stoprev, generaldelta)
def insert(self, int rev, entry): def insert(self, int rev, entry):
return self._origindex.insert(rev, entry) if rev < 0:
rev = len(self._origindex) + rev
self._origindex.insert(rev, entry)
self._nodemap[entry[-1]] = rev
def partialmatch(self, hexnode): def partialmatch(self, hexnode):
return self._origindex.partialmatch(hexnode) return self._nodemap.partialmatch(hexnode)
def __len__(self): def __len__(self):
return len(self._origindex) return len(self._origindex)
def __delslice__(self, Py_ssize_t i, Py_ssize_t j):
# This one is tricky: it's called by strip. The Rust nodemap cannot
# really handle it easily so let's just disable it for now.
# repo.destroyed() will reconstruct a clindex object, which will
# re-enable and re-build the cache.
del self._origindex[i:j]
self._config.nodemap = False
@property @property
def nodemap(self): def nodemap(self):
return nodemap(self._origindex) return self._nodemap
def destroying(self):
_log(self._vfs, 'clindex: destroying')
self._nodemap.destroying()
def updatecaches(self):
self._nodemap.updatecache()
cdef class nodemap(object): cdef class nodemap(object):
"""mutable nodemap
Backed by an immutable nodemap implemented by Rust and a simple override
dict. The Rust nodemap only follows changelog index data while the nodemap
has to support __setitem__ to be compatible with the current Mercurial
APIs.
"""
cdef localconfig _config
cdef _origindex cdef _origindex
cdef readonly _overrides # {node: rev | None}
cdef readonly _rustnodemap
cdef _vfs
cdef readonly bint _updated
emptyindex = indexes.nodemap.emptyindexbuffer()
def __init__(self, origindex): def __init__(self, origindex, changelog, vfs, config):
self._config = config
self._origindex = origindex self._origindex = origindex
self._overrides = {}
self._vfs = vfs
try:
index = util.buffer(util.mmapread(vfs('nodemap')))
if len(index) < len(self.emptyindex):
index = self.emptyindex
except IOError as ex:
if ex.errno != errno.ENOENT:
raise
_log(self._vfs, 'nodemap: is empty')
index = self.emptyindex
if config.nodemap:
try:
rustnodemap = indexes.nodemap(changelog, index)
except Exception as ex:
_log(self._vfs, 'nodemap: corrupted: %r' % ex)
rustnodemap = indexes.nodemap(changelog, self.emptyindex)
self._rustnodemap = rustnodemap
durhamUnsubmitted
Not Done

If config.nodemap is False, rustnodemap is undefined here right? Is that a problem?

durham: If config.nodemap is False, rustnodemap is undefined here right? Is that a problem?
quarkAuthorUnsubmitted
Not Done

It's a problem introduced by multiple amends. Will change.

quark: It's a problem introduced by multiple amends. Will change.
self._updated = False
def updatecache(self):
# updatecache may get called for *many* times. That is, an "outdated"
# changelog object being used across multiple transactions. This test
# avoids unnecessary re-updates.
if self._updated:
return
# nodemap was disabled (ex. by destroying()). The changelog is now
# outdated. Do not rely on it building index.
if not self._config.nodemap:
return
# Writing nodemap has a cost. Do not update it if not lagging too much.
lag = self._rustnodemap.lag()
if lag == 0 or lag < self._config.lagthreshold:
return
_log(self._vfs, 'nodemap: updating (lag=%s)' % lag)
with self._vfs('nodemap', 'w', atomictemp=True) as f:
f.write(self._rustnodemap.build())
self._updated = True
def __getitem__(self, node): def __getitem__(self, node):
if not self._config.nodemap:
return self._origindex[node] return self._origindex[node]
if node == nullid:
# special case for hg: '\0' * 20 => -1
return -1
if node in self._overrides:
rev = self._overrides[node]
elif self._config.verify:
try:
revorig = self._origindex[node]
except error.RevlogError:
revorig = None # convert "not found" to None
rev = _logifraise(self._vfs,
lambda: self._rustnodemap[node],
lambda: {'nodemap.getitem': hex(node),
'revorig': revorig})
if rev != revorig:
_logandraise(self._vfs,
'nodemap: inconsistent getitem(%s): %r vs %r'
% (hex(node), rev, revorig))
else:
rev = self._rustnodemap[node]
if rev is None:
raise error.RevlogError
else:
return rev
def __setitem__(self, node, rev): def __setitem__(self, node, rev):
self._overrides[node] = rev
self._origindex[node] = rev self._origindex[node] = rev
def __delitem__(self, node):
self._overrides[node] = None
def __contains__(self, node): def __contains__(self, node):
if not self._config.nodemap:
return node in self._origindex return node in self._origindex
if self._overrides.get(node) or node == nullid:
return True
if self._config.verify:
resorig = node in self._origindex
res = _logifraise(self._vfs,
lambda: node in self._rustnodemap,
lambda: {'nodemap.contains': hex(node),
'resorig': resorig})
if res != resorig:
_logandraise(self._vfs,
'nodemap: inconsistent contains(%s): %r vs %r'
% (hex(node), res, resorig))
else:
res = node in self._rustnodemap
return res
def get(self, node, default=None): def get(self, node, default=None):
return self._origindex.get(node, default) if self.__contains__(node):
return self.__getitem__(node)
else:
return default
def partialmatch(self, hexprefix):
if not self._config.nodemap:
return self._origindex.partialmatch(hexprefix)
if self._config.verify:
resorig = self._origindex.partialmatch(hexprefix)
res = _logifraise(
self._vfs,
lambda: self._rustpartialmatch(hexprefix),
lambda: {'partialmatch': hexprefix, 'resorig': resorig})
if res != resorig:
_logandraise(
self._vfs,
'nodemap: inconsistent partialmatch(%s): %r vs %r'
% (hexprefix, res, resorig))
else:
res = self._rustpartialmatch(hexprefix)
return res
cdef _rustpartialmatch(self, hexprefix):
candidates = set()
# Special case: nullid
if nullhex.startswith(hexprefix):
candidates.add(nullid)
try:
node = self._rustnodemap.partialmatch(hexprefix)
if node is not None:
candidates.add(node)
except RuntimeError as ex:
# Convert 'ambiguous prefix' to RevlogError. This is because the
# rust code cannot access RevlogError cleanly. So we do the
# conversion here.
if 'ambiguous prefix' in ex:
raise error.RevlogError
raise
# Search nodes in overrides. This is needed because overrides could
# live outside the changelog snapshot and are unknown to the rust
# index. Ideally we can keep changelog always up-to-date with the
# index. But that requires more changes (ex. removing index.insert API
# and index takes care of data writes).
candidates.update(k for k in self._overrides.iterkeys()
if hex(k).startswith(hexprefix))
if len(candidates) == 1:
return list(candidates)[0]
elif len(candidates) > 1:
raise error.RevlogError
else:
return None
@property
def lag(self):
if self._config.nodemap:
return self._rustnodemap.lag()
else:
return 0
def destroying(self):
self._vfs.tryunlink('nodemap')
self._config.nodemap = False
# These are unfortunate. But we need vfs access inside index.__init__. Doing
# that properly requires API changes in revlog.__init__ and
# revlogio.parseindex that might make things uglier, or break the (potential)
durhamUnsubmitted
Not Done

Hmm, so this means any command that accesses to repositories changelogs in one process will write logs to the wrong place? And they'll probably read the wrong config as well?

Since the clindex class has access to a vfs, which I assume is the svfs, could we have these global objects at least be in a dictionary indexed by svfs root path? So multiple repositories don't collide?

durham: Hmm, so this means any command that accesses to repositories changelogs in one process will…
quarkAuthorUnsubmitted
Not Done

clindex uses cachevfs.

I think config and cachevfs will be right since when _wrapchangelog re-assign them, the re-assignment won't affect existing clindex objects.

Log paths could be wrong if repo changed, yes. But blackbox and commandserver.logpath have similar issues. Maybe we should just use a single global path like /var/log/mercurial/.... I noticed infinitepush is already using that.

quark: clindex uses cachevfs. I think config and cachevfs will be right since when `_wrapchangelog`…
# intention of keeping revlog low-level, de-coupled from high-level objects
# including vfs and ui. So let's use a temporary global state to pass the
# vfs object and config options down to parseindex.
_cachevfs = None
_config = None
# Lightweight config state that is dedicated for this extensions and is
# decoupled from heavy-weight ui object.
cdef class localconfig:
cdef public bint nodemap
cdef public bint verify
cdef public int lagthreshold
def copy(self):
rhs = localconfig()
rhs.nodemap = self.nodemap
rhs.verify = self.verify
rhs.lagthreshold = self.lagthreshold
return rhs
@classmethod
def fromui(cls, ui):
self = cls()
self.nodemap = ui.configbool('clindex', 'nodemap')
self.verify = ui.configbool('clindex', 'verify')
self.lagthreshold = ui.configint('clindex', 'lagthreshold')
return self
def _parseindex(orig, self, data, inline): def _parseindex(orig, self, data, inline):
if inline: if inline:
# clindex does not support inline # clindex does not support inline. fallback to original index
return orig(self, data, inline) return orig(self, data, inline)
index = clindex(data, inline) index = clindex(data, inline, _cachevfs, _config)
return index, index.nodemap, None return index, index.nodemap, None
def _changeloginit(orig, self, *args, **kwargs): # Simple utilities to log debug messages
with extensions.wrappedfunction(revlog.revlogio, 'parseindex', _parseindex): def _logandraise(vfs, message):
orig(self, *args, **kwargs) _log(vfs, message)
raise RuntimeError(message)
def _logifraise(vfs, func, infofunc):
try:
return func()
except RuntimeError as ex:
_log(vfs, 'exception: %r %r' % (ex, infofunc()))
raise
_logpath = None
def _log(vfs, message):
try:
if _logpath:
f = open(_logpath, 'ab')
else:
f = vfs('clindex.log', 'ab')
with f:
timestamp = datetime.datetime.now().strftime('%Y-%m-%d %H:%M:%S.%f')
pid = os.getpid()
f.write('%s [%d] %s\n' % (timestamp, pid, message))
durhamUnsubmitted
Not Done

Should we set _logpath equal to False here or something? So we don't repeatedly try to open the bad logpath?

durham: Should we set _logpath equal to False here or something? So we don't repeatedly try to open…
quarkAuthorUnsubmitted
Not Done

Should be fine? blackbox does not have that logic and there were no complaints yet.

quark: Should be fine? blackbox does not have that logic and there were no complaints yet.
except IOError:
# The log is not important. IOError like "Permission denied" should not
# be fatal.
pass
def _wrapchangelog(orig, repo):
# need to pass vfs to _parseindex so it can read the cache directory
global _cachevfs
_cachevfs = repo.cachevfs
# pass a subset of config interesting to this extension
global _config
_config = localconfig.fromui(repo.ui)
try:
with extensions.wrappedfunction(revlog.revlogio,
'parseindex', _parseindex):
return orig(repo)
finally:
# do not leak them outside parseindex
_config = None
_cachevfs = None
def reposetup(ui, repo):
if not repo.local():
return
unfilteredmethod = localrepo.unfilteredmethod
class clindexrepo(repo.__class__):
@unfilteredmethod
quarkAuthorUnsubmitted
Not Done

This method got missing when rebasing.

quark: This method got missing when rebasing.
def updatecaches(self, tr=None):
try:
self.changelog.index.updatecaches()
except AttributeError as ex: # pure, or clindex is not used
return
super(clindexrepo, self).updatecaches(tr)
@unfilteredmethod
def destroying(self):
# Tell clindex to prepare for the strip. clindex will unlink
# nodemap and other caches.
try:
self.changelog.index.destroying()
except AttributeError as ex:
return
super(clindexrepo, self).destroying()
@unfilteredmethod
def destroyed(self):
# Force a reload of changelog. The current "self.changelog" object
# has an outdated snapshot of changelog.i. We need to read the new
# version before updatecaches().
if 'changelog' in self.__dict__:
del self.__dict__['changelog']
if 'changelog' in self._filecache:
del self._filecache['changelog']
# This calls "updatecachess" and will pick up the new changelog.i.
super(clindexrepo, self).destroyed()
repo.__class__ = clindexrepo
def uisetup(ui): def uisetup(ui):
extensions.wrapfunction(changelog.changelog, '__init__', _changeloginit) # uisetup has side effects depending on configs. Mark [clindex] config
# section sensitive so chg works correctly.
chgserver._configsections.append('clindex')
# global logpath config
global _logpath
_logpath = ui.config('clindex', 'logpath')
# filecache method has to be wrapped using wrapfilecache
extensions.wrapfilecache(localrepo.localrepository, 'changelog',
_wrapchangelog)