This is an archive of the discontinued Mercurial Phabricator instance.

Differential D987

copies: add a config to limit the number of candidates to check in heuristics
ClosedPublic

Authored by pulkit on Oct 7 2017, 9:00 PM.

Details

Reviewers
yuja
Group Reviewers
hg-reviewers
Commits
rHGf05a6e015ecc: copies: add a config to limit the number of candidates to check in heuristics
Summary

The heuristics algorithm find possible candidates for move/copy and then check
whether they are actually a copy or move. In some cases, there can be lot of
candidates possible which can actually slow down the algorithm.

This patch introduces a config option
experimental.copytrace.movecandidateslimit using which one can limit the
candidates to check. The limit defaults to 100.

Thanks to Yuya for suggesting to skip copytracing for that file with a
warning.

Diff Detail

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

Event Timeline

pulkit created this revision.Oct 7 2017, 9:00 PM
yuja requested changes to this revision.Oct 9 2017, 9:26 AM
yuja added a subscriber: yuja.
  • ui.configint() ?
  • I don't think taking the first 5 candidates would do something sensible. Is it reasonable?
  • tests?
This revision now requires changes to proceed.Oct 9 2017, 9:26 AM
pulkit edited the summary of this revision. (Show Details)Oct 9 2017, 5:09 PM
pulkit updated this revision to Diff 2539.
yuja requested changes to this revision.Oct 11 2017, 10:55 AM

Oops, the default value (5 vs 100) wasn't my point. I doubt if taking the first n
candidates would be a good "heuristic."

If I understand correctly, it may miss the copy information only if the file is
out of the n-candidates list. I think it would be hard for users to understand
why the copy wasn't detected. That's my concern.

(marked as "request changes" to flag discussion is ongoing. no new version is requested.)

This revision now requires changes to proceed.Oct 11 2017, 10:55 AM
pulkit added a comment.Oct 11 2017, 2:34 PM
In D987#16792, @yuja wrote:

Oops, the default value (5 vs 100) wasn't my point. I doubt if taking the first n
candidates would be a good "heuristic."

Oh, sorry. I changed it to 100 as I think that will be a good maximum and a good default rather than 5.

If I understand correctly, it may miss the copy information only if the file is
out of the n-candidates list. I think it would be hard for users to understand
why the copy wasn't detected. That's my concern.

I have added a debug message saying more candidates than the limit which can give user a hint in this case. Shall I make that a ui.status() thing?

(marked as "request changes" to flag discussion is ongoing. no new version is requested.)

yuja added a comment.Oct 12 2017, 10:14 AM

I have added a debug message saying more candidates than the limit which can give user a hint in this case. Shall I make that a ui.status() thing?

Perhaps.

And I think the status/warning message should be displayed in a stable manner,
which is:

  • do not try to find copy from the first n candidates, and show the message saying copy tracing is disabled due to too many candidates,
  • or show the message only when copy cannot be detected.
pulkit added a comment.Oct 12 2017, 2:58 PM
In D987#17141, @yuja wrote:

I have added a debug message saying more candidates than the limit which can give user a hint in this case. Shall I make that a ui.status() thing?

Perhaps.
And I think the status/warning message should be displayed in a stable manner,
which is:

  • do not try to find copy from the first n candidates, and show the message saying copy tracing is disabled due to too many candidates,

Should we just disable copy trace or fallback to the full copytracing algorithm? I like falling back to full copytracing rather than disabling straight away.

  • or show the message only when copy cannot be detected.

Did you mean, "show a message only when copy cannot be detected and we have more candidates than the limit"?

yuja added a comment.Oct 13 2017, 10:00 AM
In D987#17308, @pulkit wrote:
In D987#17141, @yuja wrote:
  • do not try to find copy from the first n candidates, and show the message saying copy tracing is disabled due to too many candidates,

Should we just disable copy trace or fallback to the full copytracing algorithm? I like falling back to full copytracing rather than disabling straight away.

Is the full tracing faster than the heuristics in that case? If not, falling back
wouldn't be an option.

  • or show the message only when copy cannot be detected.

Did you mean, "show a message only when copy cannot be detected and we have more candidates than the limit"?

Yes, but I prefer the former option, "don't search copy source because there
are too many candidates", which seems easier to follow.

stash added a subscriber: stash.Oct 16 2017, 11:27 AM

@pulkit sorry for being late with the comments.
I agree with @yuja - falling back is not an option, because it's probably going to be slow.
As for these two options

  • do not try to find copy from the first n candidates, and show the message saying copy tracing is disabled due to too many candidates,
  • or show the message only when copy cannot be detected.

Do I understand correctly that

copy tracing is disabled

means that it's disabled only for this particular file and not for all files?

If yes, then I think that either option is fine.

yuja added a comment.Oct 16 2017, 11:38 AM
In D987#18592, @stash wrote:

copy tracing is disabled

means that it's disabled only for this particular file and not for all files?

Yes, this particular file which has an excessive number of candidates.

pulkit edited the summary of this revision. (Show Details)Oct 17 2017, 5:30 PM
pulkit updated this revision to Diff 2947.
yuja accepted this revision.Oct 18 2017, 8:35 AM
This revision is now accepted and ready to land.Oct 18 2017, 8:35 AM
Closed by commit rHGf05a6e015ecc: copies: add a config to limit the number of candidates to check in heuristics (authored by pulkit). · Explain WhyOct 18 2017, 8:47 AM
This revision was automatically updated to reflect the committed changes.

Revision Contents
Changeset List

Diff 2975

mercurial/configitems.py

default=False, default=False,
) )
coreconfigitem('experimental', 'clientcompressionengines', coreconfigitem('experimental', 'clientcompressionengines',
default=list, default=list,
) )
coreconfigitem('experimental', 'copytrace', coreconfigitem('experimental', 'copytrace',
default='on', default='on',
) )
coreconfigitem('experimental', 'copytrace.movecandidateslimit',
default=100,
)
coreconfigitem('experimental', 'copytrace.sourcecommitlimit', coreconfigitem('experimental', 'copytrace.sourcecommitlimit',
default=100, default=100,
) )
coreconfigitem('experimental', 'crecordtest', coreconfigitem('experimental', 'crecordtest',
default=None, default=None,
) )
coreconfigitem('experimental', 'editortmpinhg', coreconfigitem('experimental', 'editortmpinhg',
default=False, default=False,

mercurial/copies.py

# copies.py - copy detection for Mercurial # copies.py - copy detection for Mercurial
# #
# Copyright 2008 Matt Mackall <mpm@selenic.com> # Copyright 2008 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 collections import collections
import heapq import heapq
import os import os
from .i18n import _
from . import ( from . import (
match as matchmod, match as matchmod,
node, node,
pathutil, pathutil,
scmutil, scmutil,
util, util,
) )
Source branch is commits from base up to c2 not including base. Source branch is commits from base up to c2 not including base.
If merge is involved it fallbacks to _fullcopytracing(). If merge is involved it fallbacks to _fullcopytracing().
Can be used by setting the following config: Can be used by setting the following config:
[experimental] [experimental]
copytrace = heuristics copytrace = heuristics
In some cases the copy/move candidates found by heuristics can be very large
in number and that will make the algorithm slow. The number of possible
candidates to check can be limited by using the config
`experimental.copytrace.movecandidateslimit` which defaults to 100.
""" """
if c1.rev() is None: if c1.rev() is None:
c1 = c1.p1() c1 = c1.p1()
if c2.rev() is None: if c2.rev() is None:
c2 = c2.p1() c2 = c2.p1()
copies = {} copies = {}
basename = os.path.basename(f) basename = os.path.basename(f)
dirname = os.path.dirname(f) dirname = os.path.dirname(f)
samebasename = basenametofilename[basename] samebasename = basenametofilename[basename]
samedirname = dirnametofilename[dirname] samedirname = dirnametofilename[dirname]
movecandidates = samebasename + samedirname movecandidates = samebasename + samedirname
# f is guaranteed to be present in c2, that's why # f is guaranteed to be present in c2, that's why
# c2.filectx(f) won't fail # c2.filectx(f) won't fail
f2 = c2.filectx(f) f2 = c2.filectx(f)
# we can have a lot of candidates which can slow down the heuristics
# config value to limit the number of candidates moves to check
maxcandidates = repo.ui.configint('experimental',
'copytrace.movecandidateslimit')
if len(movecandidates) > maxcandidates:
repo.ui.status(_("skipping copytracing for '%s', more "
"candidates than the limit: %d\n")
% (f, len(movecandidates)))
continue
for candidate in movecandidates: for candidate in movecandidates:
f1 = c1.filectx(candidate) f1 = c1.filectx(candidate)
if _related(f1, f2, anc.rev()): if _related(f1, f2, anc.rev()):
# if there are a few related copies then we'll merge # if there are a few related copies then we'll merge
# changes into all of them. This matches the behaviour # changes into all of them. This matches the behaviour
# of upstream copytracing # of upstream copytracing
copies[candidate] = f copies[candidate] = f

tests/test-copytrace-heuristics.t

$ hg rebase -s . -d 2 $ hg rebase -s . -d 2
rebasing 3:6b2f4cece40f "mod dir/a" (tip) rebasing 3:6b2f4cece40f "mod dir/a" (tip)
merging dir/b and dir/a to dir/b merging dir/b and dir/a to dir/b
saved backup bundle to $TESTTMP/repo/.hg/strip-backup/6b2f4cece40f-503efe60-rebase.hg (glob) saved backup bundle to $TESTTMP/repo/.hg/strip-backup/6b2f4cece40f-503efe60-rebase.hg (glob)
$ cd .. $ cd ..
$ rm -rf repo $ rm -rf repo
Test the copytrace.movecandidateslimit with many move candidates
----------------------------------------------------------------
$ hg init repo
$ initclient repo
$ cd repo
$ echo a > a
$ hg add a
$ hg ci -m initial
$ hg mv a foo
$ echo a > b
$ echo a > c
$ echo a > d
$ echo a > e
$ echo a > f
$ echo a > g
$ hg add b
$ hg add c
$ hg add d
$ hg add e
$ hg add f
$ hg add g
$ hg ci -m 'mv a foo, add many files'
$ hg up -q ".^"
$ echo b > a
$ hg ci -m 'mod a'
created new head
$ hg log -G -T 'changeset: {node}\n desc: {desc}\n'
@ changeset: ef716627c70bf4ca0bdb623cfb0d6fe5b9acc51e
| desc: mod a
| o changeset: 8329d5c6bf479ec5ca59b9864f3f45d07213f5a4
|/ desc: mv a foo, add many files
o changeset: 1451231c87572a7d3f92fc210b4b35711c949a98
desc: initial
With small limit
$ hg rebase -s 2 -d 1 --config experimental.copytrace.movecandidateslimit=0
rebasing 2:ef716627c70b "mod a" (tip)
skipping copytracing for 'a', more candidates than the limit: 7
other [source] changed a which local [dest] deleted
use (c)hanged version, leave (d)eleted, or leave (u)nresolved? u
unresolved conflicts (see hg resolve, then hg rebase --continue)
[1]
$ hg rebase --abort
rebase aborted
With default limit which is 100
$ hg rebase -s 2 -d 1
rebasing 2:ef716627c70b "mod a" (tip)
merging foo and a to foo
saved backup bundle to $TESTTMP/repo/.hg/strip-backup/ef716627c70b-24681561-rebase.hg (glob)
$ cd ..
$ rm -rf repo
Move file in one branch and delete it in another Move file in one branch and delete it in another
----------------------------------------------- -----------------------------------------------
$ hg init repo $ hg init repo
$ initclient repo $ initclient repo
$ cd repo $ cd repo
$ echo a > a $ echo a > a
$ hg add a $ hg add a