This is an archive of the discontinued Mercurial Phabricator instance.

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

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

Download Raw Diff

Details

Reviewers

marmoute
baymax

Group Reviewers

hg-reviewers

Summary

This is a proof of concept for further discussion.

Diff Detail

Repository

rHG Mercurial

Lint

Lint Skipped

Unit

Unit Tests Skipped

Event Timeline

joerg.sonnenberger created this revision.Apr 16 2019, 6:43 PM

Herald added a reviewer: hg-reviewers. · View Herald TranscriptApr 16 2019, 6:43 PM

Herald added a subscriber: mercurial-devel. · View Herald Transcript

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

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

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.

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.

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 ?

This is POC, so moving out of review.

This revision now requires changes to proceed.Apr 22 2020, 12:05 PM

Herald added a subscriber: mercurial-patches. · View Herald TranscriptApr 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

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

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.

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.

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

			Path	Packages
M			mercurial/localrepo.py (120 lines)
M			mercurial/revset.py (17 lines)

Commit	Parents	Author	Summary	Date
		Joerg Sonnenberger		Apr 14 2019, 8:17 PM

Diff 14789

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 hashlib			import hashlib
	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 = {}			self._branchcaches = {}
	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('experimental', 'bundle2-advertise'):			if self.ui.configbool('experimental', 'bundle2-advertise'):
	caps = set(caps)			caps = set(caps)
	capsblob = bundle2.encodecaps(bundle2.getrepocaps(self,			capsblob = bundle2.encodecaps(bundle2.getrepocaps(self,
	role='client'))			role='client'))
	caps.add('bundle2=' + urlreq.quote(capsblob))			caps.add('bundle2=' + urlreq.quote(capsblob))
	return caps			return caps
	trypending=txnutil.mayhavepending(self.root))			trypending=txnutil.mayhavepending(self.root))

	@storecache('00manifest.i')			@storecache('00manifest.i')
	def manifestlog(self):			def manifestlog(self):
	rootstore = manifest.manifestrevlog(self.svfs)			rootstore = manifest.manifestrevlog(self.svfs)
	return manifest.manifestlog(self.svfs, self, rootstore,			return manifest.manifestlog(self.svfs, self, rootstore,
	self._storenarrowmatch)			self._storenarrowmatch)

				@unfilteredpropertycache
				def _childrencache(self):
				self.__childrencache = childrencache(self)
				return self.__childrencache

	@repofilecache('dirstate')			@repofilecache('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 = self.revbranchcache()			rbc = self.revbranchcache()
	for r in self.changelog:			for r in self.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['.'].parents():			for ctx in self['.'].parents():
	ctx.manifest() # accessing the manifest is enough			ctx.manifest() # accessing the manifest is enough
				self._childrencache.clear()
				self._childrencache.write()

	def invalidatecaches(self):			def invalidatecaches(self):

	if r'_tagscache' in vars(self):			if r'_tagscache' in vars(self):
	# can't use delattr on proxy			# can't use delattr on proxy
	del self.__dict__[r'_tagscache']			del self.__dict__[r'_tagscache']

	self.unfiltered()._branchcaches.clear()			self.unfiltered()._branchcaches.clear()
	self.invalidatevolatilesets()			self.invalidatevolatilesets()
	self._sparsesignaturecache.clear()			self._sparsesignaturecache.clear()
				self._childrencache.clear()
				self._childrencache.write()

	def invalidatevolatilesets(self):			def invalidatevolatilesets(self):
	self.filteredrevcache.clear()			self.filteredrevcache.clear()
	obsolete.clearobscaches(self)			obsolete.clearobscaches(self)

	def invalidatedirstate(self):			def invalidatedirstate(self):
	'''Invalidates the dirstate, causing the next call to dirstate			'''Invalidates the dirstate, causing the next call to dirstate
	to check if it was modified since the last time it was read,			to check if it was modified since the last time it was read,
	'after unshare')			'after unshare')

	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, r'__class__', poisonedrepository)			object.__setattr__(repo, r'__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 = 'childrencache'
				def __init__(self, repo, readonly=False):
				assert repo.filtername is None
				self._data = None
				self._new_data = {}
				self._read = False
				self._repo = repo
				self._readonly = readonly

				def children(self, rev):
				if not self._read:
				self.read()
				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('Truncated children cache')
				for i in 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
				for r in xrange(start, len(self._repo)):
				rev = idx[r]
				if rev[5] != nullrev:
				self._new_data.setdefault(rev[5], set()).add(r)
				if rev[6] != nullrev and rev[5] != rev[6]:
				self._new_data.setdefault(rev[6], set()).add(r)
				if rev[5] == nullrev and rev[6] == nullrev:
				self._new_data.setdefault(nullrev, set()).add(r)

				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('children cache missing or too short, ignored')
				self._lastknown = 0
				self._update_changes(0)
				return
				tip, lastrev = struct.unpack_from('>20sl', data, 0)
				if lastrev == 0:
				self._repo.ui.debug('children cache empty, ignored')
				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('children cache does not match current repository state, ignored')
				return
				data = data[24:]
				if lastrev * 8 > len(data):
				self._lastknown = 0
				self._update_changes(0)
				self._repo.ui.debug('children cache was truncated, ignored')
				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 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(
	_("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
	in set.			in set.
	if m(f):			if m(f):
	return True			return True

	return subset.filter(matches, condrepr=('<status[%r] %r>', field, pat))			return subset.filter(matches, condrepr=('<status[%r] %r>', field, pat))

	def _children(repo, subset, parentset):			def _children(repo, subset, parentset):
	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
	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)			return baseset(cs)

	@predicate('children(set)', safe=True)			@predicate('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)

Diff	ID	Description	Created	Lint	Unit
Base		Base
Diff 1	14789		Apr 16 2019, 6:43 PM	★	★
Diff 2	21871		Jul 12 2020, 9:52 PM	★	★