This is an archive of the discontinued Mercurial Phabricator instance.

Differential D4120

shortest: use nodetree for finding shortest node within revset
ClosedPublic

Authored by martinvonz on Aug 5 2018, 3:58 AM.

Details

Reviewers
None
Group Reviewers
hg-reviewers
Commits
rHG7a759ad2d06d: shortest: use nodetree for finding shortest node within revset
Summary

This speeds up hg log -T '{shortest(node,1)}\n' in my repo from 12s
to 4.5s. That's very close to the 4.1s it takes without the
disambiguation revset configured. My repo has 69.5k revisions, of
which 550 were in the configured revset ("not public()").

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

martinvonz created this revision.Aug 5 2018, 3:58 AM
martinvonz updated this revision to Diff 9926.Aug 5 2018, 4:03 AM
martinvonz updated this revision to Diff 9985.Aug 6 2018, 9:24 AM
martinvonz updated this revision to Diff 10044.Aug 7 2018, 2:27 AM
martinvonz updated this revision to Diff 10084.Aug 8 2018, 8:09 PM
martinvonz updated this revision to Diff 10095.Aug 9 2018, 3:27 AM
martinvonz updated this revision to Diff 10458.Aug 20 2018, 3:35 AM
martinvonz added a comment.Aug 20 2018, 3:36 AM

I have rebased this series and run all tests in pure and native mode, so this should be ready to queue as far as I can tell.

yuja added a subscriber: yuja.Aug 20 2018, 6:51 PM

test-revisions.t fails probably because null. I've queued up to the previous
patch.

static int nt_init_py(nodetree *self, PyObject *args)
{

  • PyObject *index;

+ indexObject *index;

Dropped this change as it's unrelated to this patch, and the index variable
is casted to indexObject* anyway.

	unsigned capacity;
  • if (!PyArg_ParseTuple(args, "O!I", &index, &capacity))

+ if (!PyArg_ParseTuple(args, "O!I", &indexType, &index, &capacity))

		return -1;

Moved this to D4118.

	return nt_init(self, (indexObject*)index, capacity);
martinvonz added a comment.Aug 20 2018, 7:01 PM
In D4120#66662, @yuja wrote:

test-revisions.t fails probably because null.

Hmm, it passes for me. How does it fail for you?

I've queued up to the previous
patch.

static int nt_init_py(nodetree *self, PyObject *args)
{

  • PyObject *index;

+ indexObject *index;

Dropped this change as it's unrelated to this patch, and the index variable
is casted to indexObject* anyway.

	unsigned capacity;
  • if (!PyArg_ParseTuple(args, "O!I", &index, &capacity))

+ if (!PyArg_ParseTuple(args, "O!I", &indexType, &index, &capacity))

		return -1;

Moved this to D4118.

	return nt_init(self, (indexObject*)index, capacity);

Thanks!

martinvonz updated this revision to Diff 10485.Aug 20 2018, 7:02 PM
yuja added a comment.Aug 21 2018, 7:42 AM
Hmm, it passes for me. How does it fail for you?

Okay, it's a real bug. Filling Py_ssize_t as int.

static PyObject *nt_insert_py(nodetree *self, PyObject *args)
{
	Py_ssize_t rev;
	const char *node;
	if (!PyArg_ParseTuple(args, "i", &rev))
Traceback (most recent call last):
  File "hg", line 41, in <module>
    dispatch.run()
  File "mercurial/dispatch.py", line 90, in run
    status = dispatch(req)
  File "mercurial/dispatch.py", line 213, in dispatch
    ret = _runcatch(req) or 0
  File "mercurial/dispatch.py", line 354, in _runcatch
    return _callcatch(ui, _runcatchfunc)
  File "mercurial/dispatch.py", line 362, in _callcatch
    return scmutil.callcatch(ui, func)
  File "mercurial/scmutil.py", line 164, in callcatch
    return func()
  File "mercurial/dispatch.py", line 344, in _runcatchfunc
    return _dispatch(req)
  File "mercurial/dispatch.py", line 982, in _dispatch
    cmdpats, cmdoptions)
  File "mercurial/dispatch.py", line 728, in runcommand
    ret = _runcommand(ui, options, cmd, d)
  File "mercurial/dispatch.py", line 990, in _runcommand
    return cmdfunc()
  File "mercurial/dispatch.py", line 979, in <lambda>
    d = lambda: util.checksignature(func)(ui, *args, **strcmdopt)
  File "mercurial/util.py", line 1531, in check
    return func(*args, **kwargs)
  File "mercurial/dispatch.py", line 592, in __call__
    return util.checksignature(self.fn)(ui, *args, **opts)
  File "mercurial/util.py", line 1531, in check
    return func(*args, **kwargs)
  File "mercurial/commands.py", line 3643, in log
    displayfn(ui, repo, revs, displayer, getrenamed)
  File "mercurial/logcmdutil.py", line 897, in displayrevs
    displayer.show(ctx, copies=copies)
  File "mercurial/logcmdutil.py", line 186, in show
    self._show(ctx, copies, props)
  File "mercurial/logcmdutil.py", line 460, in _show
    self.ui.write(self.t.render(key, props))
  File "mercurial/templater.py", line 926, in render
    return b''.join(self.generate(t, mapping))
  File "mercurial/util.py", line 1442, in increasingchunks
    for chunk in source:
  File "mercurial/templateutil.py", line 659, in flatten
    for i in thing:
  File "mercurial/templateutil.py", line 853, in runtemplate
    yield evalrawexp(context, mapping, arg)
  File "mercurial/templateutil.py", line 707, in evalrawexp
    return func(context, mapping, data)
  File "mercurial/templatefuncs.py", line 634, in shortest
    return scmutil.shortesthexnodeidprefix(repo, node, minlength, cache)
  File "mercurial/scmutil.py", line 531, in shortesthexnodeidprefix
    nodetree.insert(r)
ValueError: revlog index out of range
yuja added a comment.Aug 21 2018, 7:45 AM

And can you bump cext version again as new code depends on nodetree.insert()?

martinvonz added a comment.Aug 21 2018, 11:32 AM
In D4120#66682, @yuja wrote:
Hmm, it passes for me. How does it fail for you?

Okay, it's a real bug. Filling Py_ssize_t as int.

Fixed that and bumped the version. Thanks for helping me find that.

Closed by commit rHG7a759ad2d06d: shortest: use nodetree for finding shortest node within revset (authored by martinvonz). · Explain WhyAug 21 2018, 6:49 PM
This revision was automatically updated to reflect the committed changes.

Revision Contents
Changeset List

PathPackages
Mmercurial/cext/parsers.c (2 lines)
Mmercurial/cext/revlog.c (48 lines)
Mmercurial/policy.py (2 lines)
Mmercurial/scmutil.py (21 lines)

Diff 10502

mercurial/cext/parsers.c

{"fm1readmarkers", fm1readmarkers, METH_VARARGS, {"fm1readmarkers", fm1readmarkers, METH_VARARGS,
"parse v1 obsolete markers\n"}, "parse v1 obsolete markers\n"},
{NULL, NULL}}; {NULL, NULL}};
void dirs_module_init(PyObject *mod); void dirs_module_init(PyObject *mod);
void manifest_module_init(PyObject *mod); void manifest_module_init(PyObject *mod);
void revlog_module_init(PyObject *mod); void revlog_module_init(PyObject *mod);
static const int version = 8; static const int version = 9;
static void module_init(PyObject *mod) static void module_init(PyObject *mod)
{ {
PyModule_AddIntConstant(mod, "version", version); PyModule_AddIntConstant(mod, "version", version);
/* This module constant has two purposes. First, it lets us unit test /* This module constant has two purposes. First, it lets us unit test
* the ImportError raised without hard-coding any error text. This * the ImportError raised without hard-coding any error text. This
* means we can change the text in the future without breaking tests, * means we can change the text in the future without breaking tests,

mercurial/cext/revlog.c

level += 1; level += 1;
off = v; off = v;
} }
} }
return -1; return -1;
} }
static PyObject *nt_insert_py(nodetree *self, PyObject *args)
{
Py_ssize_t rev;
const char *node;
if (!PyArg_ParseTuple(args, "n", &rev))
return NULL;
const Py_ssize_t length = index_length(self->index);
if (rev < 0 || rev >= length) {
PyErr_SetString(PyExc_ValueError, "revlog index out of range");
return NULL;
}
node = index_node_existing(self->index, rev);
if (nt_insert(self, node, rev) == -1)
return NULL;
Py_RETURN_NONE;
}
static int nt_delete_node(nodetree *self, const char *node) static int nt_delete_node(nodetree *self, const char *node)
{ {
/* rev==-2 happens to get encoded as 0, which is interpreted as not set */ /* rev==-2 happens to get encoded as 0, which is interpreted as not set */
return nt_insert(self, node, -2); return nt_insert(self, node, -2);
} }
static int nt_init(nodetree *self, indexObject *index, unsigned capacity) static int nt_init(nodetree *self, indexObject *index, unsigned capacity)
{ {
* The node was still not unique after 40 hex digits, so this won't * The node was still not unique after 40 hex digits, so this won't
* happen. Also, if we get here, then there's a programming error in * happen. Also, if we get here, then there's a programming error in
* this file that made us insert a node longer than 40 hex digits. * this file that made us insert a node longer than 40 hex digits.
*/ */
PyErr_SetString(PyExc_Exception, "broken node tree"); PyErr_SetString(PyExc_Exception, "broken node tree");
return -3; return -3;
} }
static PyObject *nt_shortest_py(nodetree *self, PyObject *args)
{
PyObject *val;
char *node;
int length;
if (!PyArg_ParseTuple(args, "O", &val))
return NULL;
if (node_check(val, &node) == -1)
return NULL;
length = nt_shortest(self, node);
if (length == -3)
return NULL;
if (length == -2) {
raise_revlog_error();
return NULL;
}
return PyInt_FromLong(length);
}
static void nt_dealloc(nodetree *self) static void nt_dealloc(nodetree *self)
{ {
Py_XDECREF(self->index); Py_XDECREF(self->index);
free(self->nodes); free(self->nodes);
self->nodes = NULL; self->nodes = NULL;
PyObject_Del(self); PyObject_Del(self);
} }
static PyMethodDef nt_methods[] = {
{"insert", (PyCFunction)nt_insert_py, METH_VARARGS,
"insert an index entry"},
{"shortest", (PyCFunction)nt_shortest_py, METH_VARARGS,
"find length of shortest hex nodeid of a binary ID"},
{NULL} /* Sentinel */
};
static PyTypeObject nodetreeType = { static PyTypeObject nodetreeType = {
PyVarObject_HEAD_INIT(NULL, 0) /* header */ PyVarObject_HEAD_INIT(NULL, 0) /* header */
"parsers.nodetree", /* tp_name */ "parsers.nodetree", /* tp_name */
sizeof(nodetree) , /* tp_basicsize */ sizeof(nodetree) , /* tp_basicsize */
0, /* tp_itemsize */ 0, /* tp_itemsize */
(destructor)nt_dealloc, /* tp_dealloc */ (destructor)nt_dealloc, /* tp_dealloc */
0, /* tp_print */ 0, /* tp_print */
0, /* tp_getattr */ 0, /* tp_getattr */
Py_TPFLAGS_DEFAULT, /* tp_flags */ Py_TPFLAGS_DEFAULT, /* tp_flags */
"nodetree", /* tp_doc */ "nodetree", /* tp_doc */
0, /* tp_traverse */ 0, /* tp_traverse */
0, /* tp_clear */ 0, /* tp_clear */
0, /* tp_richcompare */ 0, /* tp_richcompare */
0, /* tp_weaklistoffset */ 0, /* tp_weaklistoffset */
0, /* tp_iter */ 0, /* tp_iter */
0, /* tp_iternext */ 0, /* tp_iternext */
0, /* tp_methods */ nt_methods, /* tp_methods */
0, /* tp_members */ 0, /* tp_members */
0, /* tp_getset */ 0, /* tp_getset */
0, /* tp_base */ 0, /* tp_base */
0, /* tp_dict */ 0, /* tp_dict */
0, /* tp_descr_get */ 0, /* tp_descr_get */
0, /* tp_descr_set */ 0, /* tp_descr_set */
0, /* tp_dictoffset */ 0, /* tp_dictoffset */
(initproc)nt_init_py, /* tp_init */ (initproc)nt_init_py, /* tp_init */

mercurial/policy.py

return fakelocals[modname] return fakelocals[modname]
# keep in sync with "version" in C modules # keep in sync with "version" in C modules
_cextversions = { _cextversions = {
(r'cext', r'base85'): 1, (r'cext', r'base85'): 1,
(r'cext', r'bdiff'): 3, (r'cext', r'bdiff'): 3,
(r'cext', r'mpatch'): 1, (r'cext', r'mpatch'): 1,
(r'cext', r'osutil'): 4, (r'cext', r'osutil'): 4,
(r'cext', r'parsers'): 8, (r'cext', r'parsers'): 9,
} }
# map import request to other package or module # map import request to other package or module
_modredirects = { _modredirects = {
(r'cext', r'charencode'): (r'cext', r'parsers'), (r'cext', r'charencode'): (r'cext', r'parsers'),
(r'cffi', r'base85'): (r'pure', r'base85'), (r'cffi', r'base85'): (r'pure', r'base85'),
(r'cffi', r'charencode'): (r'pure', r'charencode'), (r'cffi', r'charencode'): (r'pure', r'charencode'),
(r'cffi', r'parsers'): (r'pure', r'parsers'), (r'cffi', r'parsers'): (r'pure', r'parsers'),

mercurial/scmutil.py

from . import ( from . import (
encoding, encoding,
error, error,
match as matchmod, match as matchmod,
obsolete, obsolete,
obsutil, obsutil,
pathutil, pathutil,
phases, phases,
policy,
pycompat, pycompat,
revsetlang, revsetlang,
similar, similar,
url, url,
util, util,
vfs, vfs,
) )
from .utils import ( from .utils import (
procutil, procutil,
stringutil, stringutil,
) )
if pycompat.iswindows: if pycompat.iswindows:
from . import scmwindows as scmplatform from . import scmwindows as scmplatform
else: else:
from . import scmposix as scmplatform from . import scmposix as scmplatform
parsers = policy.importmod(r'parsers')
termsize = scmplatform.termsize termsize = scmplatform.termsize
class status(tuple): class status(tuple):
'''Named tuple with a list of files per status. The 'deleted', 'unknown' '''Named tuple with a list of files per status. The 'deleted', 'unknown'
and 'ignored' properties are only relevant to the working copy. and 'ignored' properties are only relevant to the working copy.
''' '''
__slots__ = () __slots__ = ()
if cache is not None: if cache is not None:
revs = cache.get('disambiguationrevset') revs = cache.get('disambiguationrevset')
if revs is None: if revs is None:
revs = repo.anyrevs([revset], user=True) revs = repo.anyrevs([revset], user=True)
if cache is not None: if cache is not None:
cache['disambiguationrevset'] = revs cache['disambiguationrevset'] = revs
if cl.rev(node) in revs: if cl.rev(node) in revs:
hexnode = hex(node) hexnode = hex(node)
nodetree = None
if cache is not None:
nodetree = cache.get('disambiguationnodetree')
if not nodetree:
try:
nodetree = parsers.nodetree(cl.index, len(revs))
except AttributeError:
# no native nodetree
pass
else:
for r in revs:
nodetree.insert(r)
if cache is not None:
cache['disambiguationnodetree'] = nodetree
if nodetree is not None:
length = max(nodetree.shortest(node), minlength)
prefix = hexnode[:length]
return disambiguate(prefix)
for length in range(minlength, len(hexnode) + 1): for length in range(minlength, len(hexnode) + 1):
matches = [] matches = []
prefix = hexnode[:length] prefix = hexnode[:length]
for rev in revs: for rev in revs:
otherhexnode = repo[rev].hex() otherhexnode = repo[rev].hex()
if prefix == otherhexnode[:length]: if prefix == otherhexnode[:length]:
matches.append(otherhexnode) matches.append(otherhexnode)
if len(matches) == 1: if len(matches) == 1: