##// END OF EJS Templates
discovery: slowly increase sampling size...
discovery: slowly increase sampling size Some pathological discovery runs can requires many roundtrip. When this happens things can get very slow. To make the algorithm more resilience again such pathological case. We slowly increase the sample size with each roundtrip (+5%). This will have a negligible impact on "normal" discovery with few roundtrips, but a large positive impact of case with many roundtrips. Asking more question per roundtrip helps to reduce the undecided set faster. Instead of reducing the undecided set a linear speed (in the worst case), we reduce it as a guaranteed (small) exponential rate. The data below show this slow ramp up in sample size: round trip | 1 | 5 | 10 | 20 | 50 | 100 | 130 | sample size | 200 | 254 | 321 | 517 | 2 199 | 25 123 | 108 549 | covered nodes | 200 | 1 357 | 2 821 | 7 031 | 42 658 | 524 530 | 2 276 755 | To be a bit more concrete, lets take a very pathological case as an example. We are doing discovery from a copy of Mozilla-try to a more recent version of mozilla-unified. Mozilla-unified heads are unknown to the mozilla-try repo and there are over 1 million "missing" changesets. (the discovery is "local" to avoid network interference) Without this change, the discovery: - last 1858 seconds (31 minutes), - does 1700 round trip, - asking about 340 000 nodes. With this change, the discovery: - last 218 seconds (3 minutes, 38 seconds a -88% improvement), - does 94 round trip (-94%), - asking about 344 211 nodes (+1%). Of course, this is an extreme case (and 3 minutes is still slow). However this give a good example of how this sample size increase act as a safety net catching any bad situations. We could image a steeper increase than 5%. For example 10% would give the following number: round trip | 1 | 5 | 10 | 20 | 50 | 75 | 100 | sample size | 200 | 321 | 514 | 1 326 | 23 060 | 249 812 | 2 706 594 | covered nodes | 200 | 1 541 | 3 690 | 12 671 | 251 871 | 2 746 254 | 29 770 966 | In parallel, it is useful to understand these pathological cases and improve them. However the current change provides a general purpose safety net to smooth the impact of pathological cases. To avoid issue with older http server, the increase in sample size only occurs if the protocol has not limit on command argument size.

File last commit:

r37483:39e5e346 default
r42546:dbd0fcca default
Show More
fancyopts.py
378 lines | 11.2 KiB | text/x-python | PythonLexer
# fancyopts.py - better command line parsing
#
# Copyright 2005-2009 Matt Mackall <mpm@selenic.com> and others
#
# This software may be used and distributed according to the terms of the
# GNU General Public License version 2 or any later version.
from __future__ import absolute_import
import abc
import functools
from .i18n import _
from . import (
error,
pycompat,
)
# Set of flags to not apply boolean negation logic on
nevernegate = {
# avoid --no-noninteractive
'noninteractive',
# These two flags are special because they cause hg to do one
# thing and then exit, and so aren't suitable for use in things
# like aliases anyway.
'help',
'version',
}
def _earlyoptarg(arg, shortlist, namelist):
"""Check if the given arg is a valid unabbreviated option
Returns (flag_str, has_embedded_value?, embedded_value, takes_value?)
>>> def opt(arg):
... return _earlyoptarg(arg, b'R:q', [b'cwd=', b'debugger'])
long form:
>>> opt(b'--cwd')
('--cwd', False, '', True)
>>> opt(b'--cwd=')
('--cwd', True, '', True)
>>> opt(b'--cwd=foo')
('--cwd', True, 'foo', True)
>>> opt(b'--debugger')
('--debugger', False, '', False)
>>> opt(b'--debugger=') # invalid but parsable
('--debugger', True, '', False)
short form:
>>> opt(b'-R')
('-R', False, '', True)
>>> opt(b'-Rfoo')
('-R', True, 'foo', True)
>>> opt(b'-q')
('-q', False, '', False)
>>> opt(b'-qfoo') # invalid but parsable
('-q', True, 'foo', False)
unknown or invalid:
>>> opt(b'--unknown')
('', False, '', False)
>>> opt(b'-u')
('', False, '', False)
>>> opt(b'-ufoo')
('', False, '', False)
>>> opt(b'--')
('', False, '', False)
>>> opt(b'-')
('', False, '', False)
>>> opt(b'-:')
('', False, '', False)
>>> opt(b'-:foo')
('', False, '', False)
"""
if arg.startswith('--'):
flag, eq, val = arg.partition('=')
if flag[2:] in namelist:
return flag, bool(eq), val, False
if flag[2:] + '=' in namelist:
return flag, bool(eq), val, True
elif arg.startswith('-') and arg != '-' and not arg.startswith('-:'):
flag, val = arg[:2], arg[2:]
i = shortlist.find(flag[1:])
if i >= 0:
return flag, bool(val), val, shortlist.startswith(':', i + 1)
return '', False, '', False
def earlygetopt(args, shortlist, namelist, gnu=False, keepsep=False):
"""Parse options like getopt, but ignores unknown options and abbreviated
forms
If gnu=False, this stops processing options as soon as a non/unknown-option
argument is encountered. Otherwise, option and non-option arguments may be
intermixed, and unknown-option arguments are taken as non-option.
If keepsep=True, '--' won't be removed from the list of arguments left.
This is useful for stripping early options from a full command arguments.
>>> def get(args, gnu=False, keepsep=False):
... return earlygetopt(args, b'R:q', [b'cwd=', b'debugger'],
... gnu=gnu, keepsep=keepsep)
default parsing rules for early options:
>>> get([b'x', b'--cwd', b'foo', b'-Rbar', b'-q', b'y'], gnu=True)
([('--cwd', 'foo'), ('-R', 'bar'), ('-q', '')], ['x', 'y'])
>>> get([b'x', b'--cwd=foo', b'y', b'-R', b'bar', b'--debugger'], gnu=True)
([('--cwd', 'foo'), ('-R', 'bar'), ('--debugger', '')], ['x', 'y'])
>>> get([b'--unknown', b'--cwd=foo', b'--', '--debugger'], gnu=True)
([('--cwd', 'foo')], ['--unknown', '--debugger'])
restricted parsing rules (early options must come first):
>>> get([b'--cwd', b'foo', b'-Rbar', b'x', b'-q', b'y'], gnu=False)
([('--cwd', 'foo'), ('-R', 'bar')], ['x', '-q', 'y'])
>>> get([b'--cwd=foo', b'x', b'y', b'-R', b'bar', b'--debugger'], gnu=False)
([('--cwd', 'foo')], ['x', 'y', '-R', 'bar', '--debugger'])
>>> get([b'--unknown', b'--cwd=foo', b'--', '--debugger'], gnu=False)
([], ['--unknown', '--cwd=foo', '--', '--debugger'])
stripping early options (without loosing '--'):
>>> get([b'x', b'-Rbar', b'--', '--debugger'], gnu=True, keepsep=True)[1]
['x', '--', '--debugger']
last argument:
>>> get([b'--cwd'])
([], ['--cwd'])
>>> get([b'--cwd=foo'])
([('--cwd', 'foo')], [])
>>> get([b'-R'])
([], ['-R'])
>>> get([b'-Rbar'])
([('-R', 'bar')], [])
>>> get([b'-q'])
([('-q', '')], [])
>>> get([b'-q', b'--'])
([('-q', '')], [])
'--' may be a value:
>>> get([b'-R', b'--', b'x'])
([('-R', '--')], ['x'])
>>> get([b'--cwd', b'--', b'x'])
([('--cwd', '--')], ['x'])
value passed to bool options:
>>> get([b'--debugger=foo', b'x'])
([], ['--debugger=foo', 'x'])
>>> get([b'-qfoo', b'x'])
([], ['-qfoo', 'x'])
short option isn't separated with '=':
>>> get([b'-R=bar'])
([('-R', '=bar')], [])
':' may be in shortlist, but shouldn't be taken as an option letter:
>>> get([b'-:', b'y'])
([], ['-:', 'y'])
'-' is a valid non-option argument:
>>> get([b'-', b'y'])
([], ['-', 'y'])
"""
parsedopts = []
parsedargs = []
pos = 0
while pos < len(args):
arg = args[pos]
if arg == '--':
pos += not keepsep
break
flag, hasval, val, takeval = _earlyoptarg(arg, shortlist, namelist)
if not hasval and takeval and pos + 1 >= len(args):
# missing last argument
break
if not flag or hasval and not takeval:
# non-option argument or -b/--bool=INVALID_VALUE
if gnu:
parsedargs.append(arg)
pos += 1
else:
break
elif hasval == takeval:
# -b/--bool or -s/--str=VALUE
parsedopts.append((flag, val))
pos += 1
else:
# -s/--str VALUE
parsedopts.append((flag, args[pos + 1]))
pos += 2
parsedargs.extend(args[pos:])
return parsedopts, parsedargs
class customopt(object):
"""Manage defaults and mutations for any type of opt."""
__metaclass__ = abc.ABCMeta
def __init__(self, defaultvalue):
self._defaultvalue = defaultvalue
def _isboolopt(self):
return False
def getdefaultvalue(self):
"""Returns the default value for this opt.
Subclasses should override this to return a new value if the value type
is mutable."""
return self._defaultvalue
@abc.abstractmethod
def newstate(self, oldstate, newparam, abort):
"""Adds newparam to oldstate and returns the new state.
On failure, abort can be called with a string error message."""
class _simpleopt(customopt):
def _isboolopt(self):
return isinstance(self._defaultvalue, (bool, type(None)))
def newstate(self, oldstate, newparam, abort):
return newparam
class _callableopt(customopt):
def __init__(self, callablefn):
self.callablefn = callablefn
super(_callableopt, self).__init__(None)
def newstate(self, oldstate, newparam, abort):
return self.callablefn(newparam)
class _listopt(customopt):
def getdefaultvalue(self):
return self._defaultvalue[:]
def newstate(self, oldstate, newparam, abort):
oldstate.append(newparam)
return oldstate
class _intopt(customopt):
def newstate(self, oldstate, newparam, abort):
try:
return int(newparam)
except ValueError:
abort(_('expected int'))
def _defaultopt(default):
"""Returns a default opt implementation, given a default value."""
if isinstance(default, customopt):
return default
elif callable(default):
return _callableopt(default)
elif isinstance(default, list):
return _listopt(default[:])
elif type(default) is type(1):
return _intopt(default)
else:
return _simpleopt(default)
def fancyopts(args, options, state, gnu=False, early=False, optaliases=None):
"""
read args, parse options, and store options in state
each option is a tuple of:
short option or ''
long option
default value
description
option value label(optional)
option types include:
boolean or none - option sets variable in state to true
string - parameter string is stored in state
list - parameter string is added to a list
integer - parameter strings is stored as int
function - call function with parameter
customopt - subclass of 'customopt'
optaliases is a mapping from a canonical option name to a list of
additional long options. This exists for preserving backward compatibility
of early options. If we want to use it extensively, please consider moving
the functionality to the options table (e.g separate long options by '|'.)
non-option args are returned
"""
if optaliases is None:
optaliases = {}
namelist = []
shortlist = ''
argmap = {}
defmap = {}
negations = {}
alllong = set(o[1] for o in options)
for option in options:
if len(option) == 5:
short, name, default, comment, dummy = option
else:
short, name, default, comment = option
# convert opts to getopt format
onames = [name]
onames.extend(optaliases.get(name, []))
name = name.replace('-', '_')
argmap['-' + short] = name
for n in onames:
argmap['--' + n] = name
defmap[name] = _defaultopt(default)
# copy defaults to state
state[name] = defmap[name].getdefaultvalue()
# does it take a parameter?
if not defmap[name]._isboolopt():
if short:
short += ':'
onames = [n + '=' for n in onames]
elif name not in nevernegate:
for n in onames:
if n.startswith('no-'):
insert = n[3:]
else:
insert = 'no-' + n
# backout (as a practical example) has both --commit and
# --no-commit options, so we don't want to allow the
# negations of those flags.
if insert not in alllong:
assert ('--' + n) not in negations
negations['--' + insert] = '--' + n
namelist.append(insert)
if short:
shortlist += short
if name:
namelist.extend(onames)
# parse arguments
if early:
parse = functools.partial(earlygetopt, gnu=gnu)
elif gnu:
parse = pycompat.gnugetoptb
else:
parse = pycompat.getoptb
opts, args = parse(args, shortlist, namelist)
# transfer result to state
for opt, val in opts:
boolval = True
negation = negations.get(opt, False)
if negation:
opt = negation
boolval = False
name = argmap[opt]
obj = defmap[name]
if obj._isboolopt():
state[name] = boolval
else:
def abort(s):
raise error.Abort(_('invalid value %r for option %s, %s')
% (pycompat.maybebytestr(val), opt, s))
state[name] = defmap[name].newstate(state[name], val, abort)
# return unparsed args
return args