This is an archive of the discontinued Mercurial Phabricator instance.

merge: cache unknown dir checks (issue5716)
ClosedPublic

Authored by mbthomas on Oct 24 2017, 11:02 AM.

Download Raw Diff

Details

Reviewers

durin42
krbullock

Group Reviewers

hg-reviewers

Commits

rHGb85962350bb3: merge: cache unknown dir checks (issue5716)

Summary

As mentioned in D1222, the recent pathconflicts change regresses update
performance in large repositories when many files are being updated.

To mitigate this, we introduce two caches of directories that have
already found to be either:

unknown directories, but which are not aliased by files and so don't need to be checked if they are files again; and
missing directores, which cannot cause path conflicts, and cannot contain a file that causes a path conflict.

When checking the paths of a file, testing against this caches means we can
skip tests that involve touching the filesystem.

Diff Detail

Repository

rHG Mercurial

Lint

Lint Skipped

Unit

Unit Tests Skipped

Event Timeline

mbthomas created this revision.Oct 24 2017, 11:02 AM

Herald added a reviewer: hg-reviewers. · View Herald TranscriptOct 24 2017, 11:02 AM

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

If this mitigates or fixes issue5716, please mention it in the summary line.

Code LGTM, but I haven't done any performance testing on this.

mbthomas added a child revision: D1226: merge: check created file dirs for path conflicts only once (issue5716).Oct 24 2017, 1:58 PM

mbthomas retitled this revision from merge: cache unknown dir checks to merge: cache unknown dir checks (issue5716).Oct 24 2017, 1:59 PM

There is still some cost to doing the check, so it's not a complete reversal of issue5716, but it helps a lot.

Could you make this a class with unknowndircache and missingdircache being private fields?

How much do you think writing some of this code in native code (e.g. Rust) would help?

mbthomas updated this revision to Diff 3083.Oct 25 2017, 5:28 AM

Updated as requested.

The whole of _checkunknownfiles is probably a reasonable candidate for native code if we want to speed up update. It's the second most expensive part, after actually updating the files. The function is also pretty isolated - it accesses the dirstate (which may also be native code), and in some cases it checks the file contents on disk against the destination revision, but that's pretty rare. It might even be possible to do some of it in parallel.

Is it okay to punt on this until after 4.4?

Yes, fine to punt to after 4.4. With D1223 the checks are disabled, so we're back to the old behaviour for path conflicts, but the perf is ok.

needs rebased, otherwise looks fine

This revision now requires changes to proceed.Nov 13 2017, 5:53 PM

mbthomas updated this revision to Diff 3473.Nov 14 2017, 11:37 AM

krbullock accepted this revision.Dec 1 2017, 12:57 PM

Closed by commit rHGb85962350bb3: merge: cache unknown dir checks (issue5716) (authored by mbthomas). · Explain WhyDec 1 2017, 12:58 PM

This revision was automatically updated to reflect the committed changes.

Revision Contents
Changeset List

			Path	Packages
M			mercurial/merge.py (54 lines)

Diff	ID	Description	Created	Lint	Unit
Base		Base
Diff 1	3078		Oct 24 2017, 11:02 AM	★	★
Diff 2	3083		Oct 25 2017, 5:28 AM	★	★
Diff 3	3473		Nov 14 2017, 11:37 AM	★	★
Diff 4	4056	rHGb85962350bb31bc33c917866bea67918c24ff2b3	Nov 24 2017, 3:53 PM	★	★

	Status	Author	Revision
	Closed	mbthomas	D1226 merge: check created file dirs for path conflicts only once (issue5716)
	Closed	mbthomas	D1224 merge: cache unknown dir checks (issue5716)

Diff 3083

mercurial/merge.py

	def _checkunknownfile(repo, wctx, mctx, f, f2=None):			def _checkunknownfile(repo, wctx, mctx, f, f2=None):
	if f2 is None:			if f2 is None:
	f2 = f			f2 = f
	return (repo.wvfs.audit.check(f)			return (repo.wvfs.audit.check(f)
	and repo.wvfs.isfileorlink(f)			and repo.wvfs.isfileorlink(f)
	and repo.dirstate.normalize(f) not in repo.dirstate			and repo.dirstate.normalize(f) not in repo.dirstate
	and mctx[f2].cmp(wctx[f]))			and mctx[f2].cmp(wctx[f]))

	def _checkunknowndirs(repo, f):			class _unknowndirschecker(object):
	"""			"""
	Look for any unknown files or directories that may have a path conflict			Look for any unknown files or directories that may have a path conflict
	with a file. If any path prefix of the file exists as a file or link,			with a file. If any path prefix of the file exists as a file or link,
	then it conflicts. If the file itself is a directory that contains any			then it conflicts. If the file itself is a directory that contains any
	file that is not tracked, then it conflicts.			file that is not tracked, then it conflicts.

	Returns the shortest path at which a conflict occurs, or None if there is			Returns the shortest path at which a conflict occurs, or None if there is
	no conflict.			no conflict.
	"""			"""
				def __init__(self):
				# A set of paths known to be good. This prevents repeated checking of
				# dirs. It will be updated with any new dirs that are checked and found
				# to be safe.
				self._unknowndircache = set()

				# A set of paths that are known to be absent. This prevents repeated
				# checking of subdirectories that are known not to exist. It will be
				# updated with any new dirs that are checked and found to be absent.
				self._missingdircache = set()

				def __call__(self, repo, f):
	# Check for path prefixes that exist as unknown files.			# Check for path prefixes that exist as unknown files.
	for p in reversed(list(util.finddirs(f))):			for p in reversed(list(util.finddirs(f))):
	if (repo.wvfs.audit.check(p)			if p in self._missingdircache:
	and repo.wvfs.isfileorlink(p)			return
				if p in self._unknowndircache:
				continue
				if repo.wvfs.audit.check(p):
				if (repo.wvfs.isfileorlink(p)
	and repo.dirstate.normalize(p) not in repo.dirstate):			and repo.dirstate.normalize(p) not in repo.dirstate):
	return p			return p
				if not repo.wvfs.lexists(p):
				self._missingdircache.add(p)
				return
				self._unknowndircache.add(p)

	# Check if the file conflicts with a directory containing unknown files.			# Check if the file conflicts with a directory containing unknown files.
	if repo.wvfs.audit.check(f) and repo.wvfs.isdir(f):			if repo.wvfs.audit.check(f) and repo.wvfs.isdir(f):
	# Does the directory contain any files that are not in the dirstate?			# Does the directory contain any files that are not in the dirstate?
	for p, dirs, files in repo.wvfs.walk(f):			for p, dirs, files in repo.wvfs.walk(f):
	for fn in files:			for fn in files:
	relf = repo.dirstate.normalize(repo.wvfs.reljoin(p, fn))			relf = repo.dirstate.normalize(repo.wvfs.reljoin(p, fn))
	if relf not in repo.dirstate:			if relf not in repo.dirstate:
	return f			return f
	return None			return None

	def _checkunknownfiles(repo, wctx, mctx, force, actions, mergeforce):			def _checkunknownfiles(repo, wctx, mctx, force, actions, mergeforce):
	"""			"""
	Considers any actions that care about the presence of conflicting unknown			Considers any actions that care about the presence of conflicting unknown
	files. For some actions, the result is to abort; for others, it is to			files. For some actions, the result is to abort; for others, it is to
	choose a different action.			choose a different action.
	"""			"""
	fileconflicts = set()			fileconflicts = set()
	pathconflicts = set()			pathconflicts = set()
	warnconflicts = set()			warnconflicts = set()
	abortconflicts = set()			abortconflicts = set()
	unknownconfig = _getcheckunknownconfig(repo, 'merge', 'checkunknown')			unknownconfig = _getcheckunknownconfig(repo, 'merge', 'checkunknown')
	ignoredconfig = _getcheckunknownconfig(repo, 'merge', 'checkignored')			ignoredconfig = _getcheckunknownconfig(repo, 'merge', 'checkignored')
	if not force:			if not force:
	def collectconflicts(conflicts, config):			def collectconflicts(conflicts, config):
	if config == 'abort':			if config == 'abort':
	abortconflicts.update(conflicts)			abortconflicts.update(conflicts)
	elif config == 'warn':			elif config == 'warn':
	warnconflicts.update(conflicts)			warnconflicts.update(conflicts)

				checkunknowndirs = _unknowndirschecker()
	for f, (m, args, msg) in actions.iteritems():			for f, (m, args, msg) in actions.iteritems():
	if m in ('c', 'dc'):			if m in ('c', 'dc'):
	if _checkunknownfile(repo, wctx, mctx, f):			if _checkunknownfile(repo, wctx, mctx, f):
	fileconflicts.add(f)			fileconflicts.add(f)
	elif f not in wctx:			elif f not in wctx:
	path = _checkunknowndirs(repo, f)			path = checkunknowndirs(repo, f)
	if path is not None:			if path is not None:
	pathconflicts.add(path)			pathconflicts.add(path)
	elif m == 'dg':			elif m == 'dg':
	if _checkunknownfile(repo, wctx, mctx, f, args[0]):			if _checkunknownfile(repo, wctx, mctx, f, args[0]):
	fileconflicts.add(f)			fileconflicts.add(f)

	allconflicts = fileconflicts \| pathconflicts			allconflicts = fileconflicts \| pathconflicts
	ignoredconflicts = set([c for c in allconflicts			ignoredconflicts = set([c for c in allconflicts