Download Raw Diff

Details

Reviewers

None

Group 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

Herald added a reviewer: hg-reviewers. · View Herald TranscriptAug 5 2018, 3:58 AM

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

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 10274.Aug 10 2018, 12:05 AM

martinvonz updated this revision to Diff 10275.Aug 10 2018, 12:26 AM

martinvonz updated this revision to Diff 10458.Aug 20 2018, 3:35 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.

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);

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

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

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

martinvonz updated this revision to Diff 10491.Aug 21 2018, 11:31 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.

Diff	ID	Description	Created	Lint	Unit
Base		Base
Diff 1	9923		Aug 5 2018, 3:58 AM	★	★
Diff 2	9926		Aug 5 2018, 4:03 AM	★	★
Diff 3	9985		Aug 6 2018, 9:24 AM	★	★
Diff 4	10044		Aug 7 2018, 2:27 AM	★	★
Diff 5	10084		Aug 8 2018, 8:09 PM	★	★
Diff 6	10095		Aug 9 2018, 3:27 AM	★	★
Diff 7	10274		Aug 10 2018, 12:05 AM	★	★
Diff 8	10275		Aug 10 2018, 12:26 AM	★	★
Diff 9	10458		Aug 20 2018, 3:35 AM	★	★
Diff 10	10485		Aug 20 2018, 7:02 PM	★	★
Diff 11	10491		Aug 21 2018, 11:31 AM	★	★
Diff 12	10502	rHG7a759ad2d06dcf6548a8cc19fcd773eaa943f7ac	Aug 5 2018, 3:42 AM	★	★

Status	Author	Revision
Closed	martinvonz	D4120 shortest: use nodetree for finding shortest node within revset
Closed	martinvonz	D4119 index: move raise_revlog_error() further up
Closed	martinvonz	D4118 index: make node tree a Python object
Closed	martinvonz	D4166 index: make capacity argument to nt_init be measured in revisions
Closed	martinvonz	D4165 index: avoid duplicating capacity-growth expression
Closed	martinvonz	D4164 index: move check for too large capacity into nt_init()
Closed	martinvonz	D4163 shortest: don't include nullid in disambigution revset
Closed	martinvonz	D4162 index: don't include nullid in the internal "length" field

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:

			Path	Packages
M			mercurial/cext/parsers.c (2 lines)
M			mercurial/cext/revlog.c (48 lines)
M			mercurial/policy.py (2 lines)
M			mercurial/scmutil.py (21 lines)

This is an archive of the discontinued Mercurial Phabricator instance.

shortest: use nodetree for finding shortest node within revset
ClosedPublic

Details

Diff Detail

Event Timeline

Revision Contents
Changeset List

Diff 10502

mercurial/cext/parsers.c

mercurial/cext/revlog.c

mercurial/policy.py

mercurial/scmutil.py

This is an archive of the discontinued Mercurial Phabricator instance.

shortest: use nodetree for finding shortest node within revsetClosedPublic

Details

Diff Detail

Event Timeline

Revision ContentsChangeset List

Diff 10502

mercurial/cext/parsers.c

mercurial/cext/revlog.c

mercurial/policy.py

mercurial/scmutil.py

shortest: use nodetree for finding shortest node within revset
ClosedPublic

Revision Contents
Changeset List