This is an archive of the discontinued Mercurial Phabricator instance.

Differential D6259

[POC] revset: on-disk cache for children queries
Needs RevisionPublic

Authored by joerg.sonnenberger on Apr 16 2019, 6:43 PM.

Details

Reviewers
marmoute
baymax
Group Reviewers
hg-reviewers
Summary

This is a proof of concept for further discussion.

Diff Detail

Repository
rHG Mercurial
Branch
default
Lint
No Linters Available
Unit
No Unit Test Coverage

Event Timeline

joerg.sonnenberger retitled this revision from revset: on-disk cache for children queries to [POC] revset: on-disk cache for children queries.Apr 16 2019, 6:49 PM
indygreg added a subscriber: indygreg.Apr 17 2019, 6:54 AM

Do you have performance numbers to share? Substantial wins would definitely pique my interest :)

joerg.sonnenberger added a comment.Apr 17 2019, 8:54 AM

For the NetBSD repository, a trivial test with the new cache:

time hg log -r '1000~-400' -T {node} > /dev/null
real	0m1.898s
time hg log -r '1000~-400' -T {node} > /dev/null
real	0m0.170s
time hg log -r '1000~-1' -T {node} > /dev/null
real	0m0.166s
time hg log -r '440000~-1' -T {node} > /dev/null
real	0m0.170s

First one includes the time to initially warmup the cache.

Without the cache:

time hg log -r '1000~0' -T {node} > /dev/null
real	0m0.196s
time hg log -r '1000~-1' -T {node} > /dev/null
real	0m0.825s
time hg log -r '1000~-2' -T {node} > /dev/null
real	0m1.288s
time hg log -r '1000~-400' -T {node} > /dev/null
real	3m23.201s
time hg log -r '440000~-1' -T {node} > /dev/null
real	0m0.182s

In other words, building the cache is amortised by one or two queries for children early up in the tree. The cache still provides a good benefit nearer to tip.

martinvonz added a subscriber: martinvonz.Apr 17 2019, 9:29 AM

Perhaps we'd want this to not be specifically for revsets? We could also write to it when we write to the changelog to keep it up to date.

marmoute added a subscriber: marmoute.Jan 23 2020, 12:19 PM

If we have one, we'll want it to be generic (so also for changelog). Do we have performance number of the time it takes to build it ?

marmoute requested changes to this revision.Apr 22 2020, 12:05 PM

This is POC, so moving out of review.

This revision now requires changes to proceed.Apr 22 2020, 12:05 PM
joerg.sonnenberger retitled this revision from [POC] revset: on-disk cache for children queries to revset: on-disk cache for children queries.Jul 12 2020, 9:52 PM
joerg.sonnenberger updated this revision to Diff 21871.
joerg.sonnenberger retitled this revision from revset: on-disk cache for children queries to [POC] revset: on-disk cache for children queries.Jul 12 2020, 10:07 PM
pulkit added a subscriber: pulkit.Jul 20 2020, 8:58 AM

@joerg.sonnenberger Is this still a POC? I see that you updated the code.

joerg.sonnenberger added a comment.Jul 20 2020, 9:46 AM

Yes, it's still a POC. I wanted to make sure that it works in the modern world, but I am still considering the idea in the context of larger changes for transactional caches.

marmoute added a comment.Sep 11 2020, 4:24 AM

The approach used by the nodemap is probably a good way forward for transactional case. Some kind of happen only index, that get recompacked on a regular basis. Combined with an append only data file (for example, children can be stored as linked list (data file size) with a pointer to the first entry in an index file.

baymax requested changes to this revision.Dec 22 2020, 3:22 AM

There seems to have been no activities on this Diff for the past 3 Months.

By policy, we are automatically moving it out of the need-review state.

Please, move it back to need-review without hesitation if this diff should still be discussed.

:baymax:need-review-idle:

This revision now requires changes to proceed.Dec 22 2020, 3:22 AM

Revision Contents
Changeset List

Diff 21871

mercurial/localrepo.py

# localrepo.py - read/write repository class for mercurial # localrepo.py - read/write repository class for mercurial
# #
# Copyright 2005-2007 Matt Mackall <mpm@selenic.com> # Copyright 2005-2007 Matt Mackall <mpm@selenic.com>
# #
# 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.
from __future__ import absolute_import from __future__ import absolute_import
import errno import errno
import os import os
import random import random
import struct
import sys import sys
import time import time
import weakref import weakref
from .i18n import _ from .i18n import _
from .node import ( from .node import (
bin, bin,
hex, hex,
self.svfs.vfs.audit = self._getsvfsward(self.svfs.vfs.audit) self.svfs.vfs.audit = self._getsvfsward(self.svfs.vfs.audit)
else: # standard vfs else: # standard vfs
self.svfs.audit = self._getsvfsward(self.svfs.audit) self.svfs.audit = self._getsvfsward(self.svfs.audit)
self._dirstatevalidatewarned = False self._dirstatevalidatewarned = False
self._branchcaches = branchmap.BranchMapCache() self._branchcaches = branchmap.BranchMapCache()
self._revbranchcache = None self._revbranchcache = None
self.__childrencache = None
self._filterpats = {} self._filterpats = {}
self._datafilters = {} self._datafilters = {}
self._transref = self._lockref = self._wlockref = None self._transref = self._lockref = self._wlockref = None
# A cache for various files under .hg/ that tracks file changes, # A cache for various files under .hg/ that tracks file changes,
# (used by the filecache decorator) # (used by the filecache decorator)
# #
# Maps a property name to its util.filecacheentry # Maps a property name to its util.filecacheentry
return checksvfs return checksvfs
def close(self): def close(self):
self._writecaches() self._writecaches()
def _writecaches(self): def _writecaches(self):
if self._revbranchcache: if self._revbranchcache:
self._revbranchcache.write() self._revbranchcache.write()
if self.__childrencache:
self.__childrencache.write()
def _restrictcapabilities(self, caps): def _restrictcapabilities(self, caps):
if self.ui.configbool(b'experimental', b'bundle2-advertise'): if self.ui.configbool(b'experimental', b'bundle2-advertise'):
caps = set(caps) caps = set(caps)
capsblob = bundle2.encodecaps( capsblob = bundle2.encodecaps(
bundle2.getrepocaps(self, role=b'client') bundle2.getrepocaps(self, role=b'client')
) )
caps.add(b'bundle2=' + urlreq.quote(capsblob)) caps.add(b'bundle2=' + urlreq.quote(capsblob))
# load dirstate before changelog to avoid race see issue6303 # load dirstate before changelog to avoid race see issue6303
self.dirstate.prefetch_parents() self.dirstate.prefetch_parents()
return self.store.changelog(txnutil.mayhavepending(self.root)) return self.store.changelog(txnutil.mayhavepending(self.root))
@storecache(b'00manifest.i') @storecache(b'00manifest.i')
def manifestlog(self): def manifestlog(self):
return self.store.manifestlog(self, self._storenarrowmatch) return self.store.manifestlog(self, self._storenarrowmatch)
rootstore = manifest.manifestrevlog(self.svfs)
return manifest.manifestlog(
self.svfs, self, rootstore, self._storenarrowmatch
)
@unfilteredpropertycache
def _childrencache(self):
self.__childrencache = childrencache(self)
return self.__childrencache
@repofilecache(b'dirstate') @repofilecache(b'dirstate')
def dirstate(self): def dirstate(self):
return self._makedirstate() return self._makedirstate()
def _makedirstate(self): def _makedirstate(self):
"""Extension point for wrapping the dirstate per-repo.""" """Extension point for wrapping the dirstate per-repo."""
sparsematchfn = lambda: sparse.matcher(self) sparsematchfn = lambda: sparse.matcher(self)
rbc = unfi.revbranchcache() rbc = unfi.revbranchcache()
for r in unfi.changelog: for r in unfi.changelog:
rbc.branchinfo(r) rbc.branchinfo(r)
rbc.write() rbc.write()
# ensure the working copy parents are in the manifestfulltextcache # ensure the working copy parents are in the manifestfulltextcache
for ctx in self[b'.'].parents(): for ctx in self[b'.'].parents():
ctx.manifest() # accessing the manifest is enough ctx.manifest() # accessing the manifest is enough
self._childrencache.clear()
self._childrencache.write()
# accessing fnode cache warms the cache # accessing fnode cache warms the cache
tagsmod.fnoderevs(self.ui, unfi, unfi.changelog.revs()) tagsmod.fnoderevs(self.ui, unfi, unfi.changelog.revs())
# accessing tags warm the cache # accessing tags warm the cache
self.tags() self.tags()
self.filtered(b'served').tags() self.filtered(b'served').tags()
# The `full` arg is documented as updating even the lazily-loaded # The `full` arg is documented as updating even the lazily-loaded
# caches immediately, so we're forcing a write to cause these caches # caches immediately, so we're forcing a write to cause these caches
# to be warmed up even if they haven't explicitly been requested # to be warmed up even if they haven't explicitly been requested
# yet (if they've never been used by hg, they won't ever have been # yet (if they've never been used by hg, they won't ever have been
# written, even if they're a subset of another kind of cache that # written, even if they're a subset of another kind of cache that
# *has* been used). # *has* been used).
for filt in repoview.filtertable.keys(): for filt in repoview.filtertable.keys():
filtered = self.filtered(filt) filtered = self.filtered(filt)
filtered.branchmap().write(filtered) filtered.branchmap().write(filtered)
else:
if self.__childrencache:
self.__childrencache.write()
def invalidatecaches(self): def invalidatecaches(self):
if '_tagscache' in vars(self): if '_tagscache' in vars(self):
# can't use delattr on proxy # can't use delattr on proxy
del self.__dict__['_tagscache'] del self.__dict__['_tagscache']
self._branchcaches.clear() self._branchcaches.clear()
self.invalidatevolatilesets() self.invalidatevolatilesets()
self._sparsesignaturecache.clear() self._sparsesignaturecache.clear()
self._childrencache.clear()
def invalidatevolatilesets(self): def invalidatevolatilesets(self):
self.filteredrevcache.clear() self.filteredrevcache.clear()
obsolete.clearobscaches(self) obsolete.clearobscaches(self)
self._quick_access_changeid_invalidate() self._quick_access_changeid_invalidate()
def invalidatedirstate(self): def invalidatedirstate(self):
'''Invalidates the dirstate, causing the next call to dirstate '''Invalidates the dirstate, causing the next call to dirstate
) )
def close(self): def close(self):
pass pass
# We may have a repoview, which intercepts __setattr__. So be sure # We may have a repoview, which intercepts __setattr__. So be sure
# we operate at the lowest level possible. # we operate at the lowest level possible.
object.__setattr__(repo, '__class__', poisonedrepository) object.__setattr__(repo, '__class__', poisonedrepository)
class childrencache(object):
"""Persistent cache, mapping from revision number to revision numbers of
the direct children. This is a low level cache, independent of filtering.
"""
_filename = b'childrencache'
def __init__(self, repo, readonly=False):
assert repo.filtername is None
self._data = None
self._new_data = {}
self._read = False
self._repo = repo.unfiltered()
self._readonly = readonly
def children(self, rev):
if not self._read:
self.read()
if rev >= self._lastrecorded:
self._update_changes(self._lastrecorded)
children = self._new_data.get(rev, set())
rev += 1
if rev >= self._lastknown:
return children
children = children.copy()
child_len, child_off = struct.unpack_from('>ll', self._data, 8 * rev)
if child_len == 1:
children.add(child_off)
elif child_len > 1:
start = 8 * self._lastknown + child_off * 4
if len(self._data) < start + child_len * 4:
raise error.Abort(b'Truncated children cache')
for i in pycompat.xrange(child_len):
(child,) = struct.unpack_from('>l', self._data, start)
children.add(child)
start += 4
return children
def clear(self):
self._read = True
self._data = None
self._new_data = {}
self._lastknown = 0
self._update_changes(0)
def _update_changes(self, start):
idx = self._repo.changelog.index
lastrev = len(self._repo)
for r in pycompat.xrange(start, lastrev):
rev = idx[r]
p1, p2 = rev[5:7]
if p1 != nullrev or p2 == nullrev:
self._new_data.setdefault(p1, set()).add(r)
if p2 != nullrev:
self._new_data.setdefault(p2, set()).add(r)
self._lastrecorded = lastrev
def read(self):
if self._read:
return
self._read = True
try:
data = self._repo.cachevfs.read(self._filename)
except (OSError, IOError):
data = ""
if len(data) < 24:
self._repo.ui.debug(
b'children cache missing or too short, ignored\n'
)
self._lastknown = 0
self._update_changes(0)
return
tip, lastrev = struct.unpack_from('>20sl', data, 0)
if lastrev == 0:
self._repo.ui.debug(b'children cache empty, ignored\n')
self._lastknown = 0
self._update_changes(0)
return
if (
lastrev > len(self._repo) + 1
or self._repo.changelog.node(lastrev - 2) != tip
):
self._lastknown = 0
self._update_changes(0)
self._repo.ui.debug(
b'children cache does not match current repository state, ignored\n'
)
return
data = data[24:]
if lastrev * 8 > len(data):
self._lastknown = 0
self._update_changes(0)
self._repo.ui.debug(b'children cache was truncated, ignored\n')
return
self._data = data
self._lastknown = lastrev
self._update_changes(lastrev)
def write(self):
if not self._new_data or self._readonly:
return
lastrev = len(self._repo) + 1
data = [struct.pack('>20sl', self._repo.changelog.tip(), lastrev)]
data2 = []
for r in pycompat.xrange(lastrev):
children = self.children(r - 1)
data.append(struct.pack('>l', len(children)))
if len(children) == 0:
data.append(struct.pack('>l', 0))
elif len(children) == 1:
children = list(children)
data.append(struct.pack('>l', children[0]))
else:
data.append(struct.pack('>l', len(data2)))
for c in children:
data2.append(struct.pack('>l', c))
output = b''.join(data) + b''.join(data2)
self._repo.cachevfs.write(self._filename, output, atomictemp=True)

mercurial/revset.py

def _childrenspec(repo, subset, x, n, order): def _childrenspec(repo, subset, x, n, order):
"""Changesets that are the Nth child of a changeset """Changesets that are the Nth child of a changeset
in set. in set.
""" """
cs = set() cs = set()
for r in getset(repo, fullreposet(repo), x): for r in getset(repo, fullreposet(repo), x):
for i in range(n): for i in range(n):
c = repo[r].children() c = repo._childrencache.children(r)
if len(c) == 0: if len(c) == 0:
break break
if len(c) > 1: if len(c) > 1:
raise error.RepoLookupError( raise error.RepoLookupError(
_(b"revision in set has more than one child") _("revision in set has more than one child")
) )
r = c[0].rev() r = list(c)[0]
else: else:
cs.add(r) cs.add(r)
return subset & cs return subset & cs
def ancestorspec(repo, subset, x, n, order): def ancestorspec(repo, subset, x, n, order):
"""``set~n`` """``set~n``
Changesets that are the Nth ancestor (first parents only) of a changeset Changesets that are the Nth ancestor (first parents only) of a changeset
else: else:
if any(m(f) for f in files): if any(m(f) for f in files):
return True return True
return subset.filter(matches, condrepr=(b'<status[%r] %r>', field, pat)) return subset.filter(matches, condrepr=(b'<status[%r] %r>', field, pat))
def _children(repo, subset, parentset): def _children(repo, subset, parentset):
def visiblerev(rev):
try:
repo.changelog.node(rev)
return True
except IndexError:
return False
if not parentset: if not parentset:
return baseset() return baseset()
cs = set() cs = set.union(*[set(repo._childrencache.children(c)) for c in parentset])
pr = repo.changelog.parentrevs return baseset({rev for rev in cs if visiblerev(rev)})
minrev = parentset.min()
nullrev = node.nullrev
for r in subset:
if r <= minrev:
continue
p1, p2 = pr(r)
if p1 in parentset:
cs.add(r)
if p2 != nullrev and p2 in parentset:
cs.add(r)
return baseset(cs)
@predicate(b'children(set)', safe=True) @predicate(b'children(set)', safe=True)
def children(repo, subset, x): def children(repo, subset, x):
"""Child changesets of changesets in set. """Child changesets of changesets in set.
""" """
s = getset(repo, fullreposet(repo), x) s = getset(repo, fullreposet(repo), x)
cs = _children(repo, subset, s) cs = _children(repo, subset, s)

tests/test-clone-uncompressed.t

#if stream-bundle2 #if stream-bundle2
$ hg clone --stream -U http://localhost:$HGPORT clone1 $ hg clone --stream -U http://localhost:$HGPORT clone1
streaming all changes streaming all changes
1030 files to transfer, 96.5 KB of data 1030 files to transfer, 96.5 KB of data
transferred 96.5 KB in * seconds (* */sec) (glob) transferred 96.5 KB in * seconds (* */sec) (glob)
$ ls -1 clone1/.hg/cache $ ls -1 clone1/.hg/cache
branch2-served branch2-served
childrencache
rbc-names-v1 rbc-names-v1
rbc-revs-v1 rbc-revs-v1
#endif #endif
getbundle requests with stream=1 are uncompressed getbundle requests with stream=1 are uncompressed
$ get-with-headers.py $LOCALIP:$HGPORT '?cmd=getbundle' content-type --bodyfile body --hgproto '0.1 0.2 comp=zlib,none' --requestheader "x-hgarg-1=bundlecaps=HG20%2Cbundle2%3DHG20%250Abookmarks%250Achangegroup%253D01%252C02%250Adigests%253Dmd5%252Csha1%252Csha512%250Aerror%253Dabort%252Cunsupportedcontent%252Cpushraced%252Cpushkey%250Ahgtagsfnodes%250Alistkeys%250Aphases%253Dheads%250Apushkey%250Aremote-changegroup%253Dhttp%252Chttps&cg=0&common=0000000000000000000000000000000000000000&heads=c17445101a72edac06facd130d14808dfbd5c7c2&stream=1" $ get-with-headers.py $LOCALIP:$HGPORT '?cmd=getbundle' content-type --bodyfile body --hgproto '0.1 0.2 comp=zlib,none' --requestheader "x-hgarg-1=bundlecaps=HG20%2Cbundle2%3DHG20%250Abookmarks%250Achangegroup%253D01%252C02%250Adigests%253Dmd5%252Csha1%252Csha512%250Aerror%253Dabort%252Cunsupportedcontent%252Cpushraced%252Cpushkey%250Ahgtagsfnodes%250Alistkeys%250Aphases%253Dheads%250Apushkey%250Aremote-changegroup%253Dhttp%252Chttps&cg=0&common=0000000000000000000000000000000000000000&heads=c17445101a72edac06facd130d14808dfbd5c7c2&stream=1"
200 Script output follows 200 Script output follows

tests/test-clone.t

#endif #endif
Trigger branchcache creation: Trigger branchcache creation:
$ hg branches $ hg branches
default 10:a7949464abda default 10:a7949464abda
$ ls .hg/cache $ ls .hg/cache
branch2-served branch2-served
childrencache
rbc-names-v1 rbc-names-v1
rbc-revs-v1 rbc-revs-v1
Default operation: Default operation:
$ hg clone . ../b $ hg clone . ../b
updating to branch default updating to branch default
2 files updated, 0 files merged, 0 files removed, 0 files unresolved 2 files updated, 0 files merged, 0 files removed, 0 files unresolved

tests/test-debugcommands.t

$ hg debugupdatecaches --debug $ hg debugupdatecaches --debug
updating the branch cache updating the branch cache
$ ls -r .hg/cache/* $ ls -r .hg/cache/*
.hg/cache/tags2-served .hg/cache/tags2-served
.hg/cache/tags2 .hg/cache/tags2
.hg/cache/rbc-revs-v1 .hg/cache/rbc-revs-v1
.hg/cache/rbc-names-v1 .hg/cache/rbc-names-v1
.hg/cache/hgtagsfnodes1 .hg/cache/hgtagsfnodes1
.hg/cache/childrencache
.hg/cache/branch2-visible-hidden .hg/cache/branch2-visible-hidden
.hg/cache/branch2-visible .hg/cache/branch2-visible
.hg/cache/branch2-served.hidden .hg/cache/branch2-served.hidden
.hg/cache/branch2-served .hg/cache/branch2-served
.hg/cache/branch2-immutable .hg/cache/branch2-immutable
.hg/cache/branch2-base .hg/cache/branch2-base
Test debugcolor Test debugcolor

tests/test-hardlinks.t

r4 has hardlinks in the working dir (not just inside .hg): r4 has hardlinks in the working dir (not just inside .hg):
$ nlinksdir r4 $ nlinksdir r4
2 r4/.hg/00changelog.i 2 r4/.hg/00changelog.i
2 r4/.hg/branch 2 r4/.hg/branch
2 r4/.hg/cache/branch2-base 2 r4/.hg/cache/branch2-base
2 r4/.hg/cache/branch2-served 2 r4/.hg/cache/branch2-served
2 r4/.hg/cache/childrencache
2 r4/.hg/cache/rbc-names-v1 2 r4/.hg/cache/rbc-names-v1
2 r4/.hg/cache/rbc-revs-v1 2 r4/.hg/cache/rbc-revs-v1
2 r4/.hg/dirstate 2 r4/.hg/dirstate
2 r4/.hg/fsmonitor.state (fsmonitor !) 2 r4/.hg/fsmonitor.state (fsmonitor !)
2 r4/.hg/hgrc 2 r4/.hg/hgrc
2 r4/.hg/last-message.txt 2 r4/.hg/last-message.txt
2 r4/.hg/requires 2 r4/.hg/requires
2 r4/.hg/store/00changelog.i 2 r4/.hg/store/00changelog.i
2 files updated, 0 files merged, 0 files removed, 0 files unresolved (execbit !) 2 files updated, 0 files merged, 0 files removed, 0 files unresolved (execbit !)
1 files updated, 0 files merged, 0 files removed, 0 files unresolved (no-execbit !) 1 files updated, 0 files merged, 0 files removed, 0 files unresolved (no-execbit !)
$ nlinksdir r4 $ nlinksdir r4
2 r4/.hg/00changelog.i 2 r4/.hg/00changelog.i
1 r4/.hg/branch 1 r4/.hg/branch
2 r4/.hg/cache/branch2-base 2 r4/.hg/cache/branch2-base
2 r4/.hg/cache/branch2-served 2 r4/.hg/cache/branch2-served
2 r4/.hg/cache/childrencache
2 r4/.hg/cache/rbc-names-v1 2 r4/.hg/cache/rbc-names-v1
2 r4/.hg/cache/rbc-revs-v1 2 r4/.hg/cache/rbc-revs-v1
1 r4/.hg/dirstate 1 r4/.hg/dirstate
1 r4/.hg/fsmonitor.state (fsmonitor !) 1 r4/.hg/fsmonitor.state (fsmonitor !)
2 r4/.hg/hgrc 2 r4/.hg/hgrc
2 r4/.hg/last-message.txt 2 r4/.hg/last-message.txt
2 r4/.hg/requires 2 r4/.hg/requires
2 r4/.hg/store/00changelog.i 2 r4/.hg/store/00changelog.i

tests/test-remote-hidden.t

-------------------- --------------------
$ ls -1 repo-with-hidden/.hg/cache $ ls -1 repo-with-hidden/.hg/cache
branch2 branch2
branch2-base branch2-base
branch2-served branch2-served
branch2-served.hidden branch2-served.hidden
branch2-visible branch2-visible
childrencache
rbc-names-v1 rbc-names-v1
rbc-revs-v1 rbc-revs-v1
tags2 tags2
tags2-visible tags2-visible
Check that the `served.hidden` repoview Check that the `served.hidden` repoview
--------------------------------------- ---------------------------------------

tests/test-server-view.t

$ ls -1 test/.hg/cache/ $ ls -1 test/.hg/cache/
branch2-base%89c45d2fa07e branch2-base%89c45d2fa07e
branch2-immutable%89c45d2fa07e branch2-immutable%89c45d2fa07e
branch2-served branch2-served
branch2-served%89c45d2fa07e branch2-served%89c45d2fa07e
branch2-served.hidden%89c45d2fa07e branch2-served.hidden%89c45d2fa07e
branch2-visible%89c45d2fa07e branch2-visible%89c45d2fa07e
branch2-visible-hidden%89c45d2fa07e branch2-visible-hidden%89c45d2fa07e
childrencache
hgtagsfnodes1 hgtagsfnodes1
rbc-names-v1 rbc-names-v1
rbc-revs-v1 rbc-revs-v1
tags2 tags2
tags2-served%89c45d2fa07e tags2-served%89c45d2fa07e
cleanup cleanup
$ cat errors.log $ cat errors.log
$ killdaemons.py $ killdaemons.py