This is an archive of the discontinued Mercurial Phabricator instance.

Differential D3499

revlog: use node tree (native code) for shortest() calculation
ClosedPublic

Authored by martinvonz on May 8 2018, 2:07 PM.

Download Raw Diff

Details

Reviewers

indygreg

Group Reviewers

hg-reviewers

Commits

rHG0304f22497fa: revlog: use node tree (native code) for shortest() calculation

Summary

I want to rewrite revlog.shortest() to disambiguate only among hex
nodeids and then disambiguate the result with revnums at a higher
level (in scmutil). However, that would slow down `hg log -T
'{shortest(node,1)}\n'` from 5.0s to 6.8s, which I wasn't sure would
be acceptable. So this patch makes revlog.shortest() use the node tree
for finding the length of the shortest prefix that's unambiguous among
nodeids. Once that has been found, it makes it longer until it is also
not ambiguous with a revnum.

This speeds up hg log -T '{shortest(node,1)}\n' from 5.0s to 4.0s.

Diff Detail

Repository

rHG Mercurial

Lint

Lint Skipped

Unit

Unit Tests Skipped

Event Timeline

martinvonz created this revision.May 8 2018, 2:07 PM

Herald added a reviewer: indygreg. · View Herald TranscriptMay 8 2018, 2:07 PM

Herald added a reviewer: hg-reviewers. · View Herald Transcript

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

martinvonz added a child revision: D3500: shortest: make pure code also disambigute against revnums at end.May 8 2018, 2:07 PM

Looks generally good, but can you fix your editor to not do Google indent?

I'm not sure if we should bump the module version in this case, but I would
do that just for sanity.

+static int nt_shortest(indexObject *self, const char *node)
+{
+ if (nt_init(self) == -1)
+ return -3;
+ if (nt_populate(self) == -1)
+ return -3;
+
+ int level, off;

Declaration has to be moved to top.

+ for (level = off = 0; level < 40; level++) {
+ int k = nt_level(node, level);
+ nodetree *n = &self->nt[off];
+ int v = n->children[k];
+ if (v < 0) {
+ v = -(v + 1);
+ const char *n = index_node(self, v);

Here, too.

In D3499#55772, @yuja wrote:

Looks generally good, but can you fix your editor to not do Google indent?

Wow, we still use tabs?! Okay, will change.

I'm not sure if we should bump the module version in this case, but I would
do that just for sanity.

Done, I think, but please check that I did it right.

+static int nt_shortest(indexObject *self, const char *node)
+{
+ if (nt_init(self) == -1)
+ return -3;
+ if (nt_populate(self) == -1)
+ return -3;
+
+ int level, off;

Declaration has to be moved to top.

Done.

+ for (level = off = 0; level < 40; level++) {
+ int k = nt_level(node, level);
+ nodetree *n = &self->nt[off];
+ int v = n->children[k];
+ if (v < 0) {
+ v = -(v + 1);
+ const char *n = index_node(self, v);

Here, too.

Done.

martinvonz updated this revision to Diff 8624.May 10 2018, 12:01 PM

+static int nt_shortest(indexObject *self, const char *node)
+{
+ int level, off;
+
+ if (nt_init(self) == -1)
+ return -3;
+ if (nt_populate(self) == -1)
+ return -3;
+
+ for (level = off = 0; level < 40; level++) {
+ int k, v;
+ nodetree *n = &self->nt[off];
+ k = nt_level(node, level);
+ v = n->children[k];
+ if (v < 0) {
+ v = -(v + 1);
+ const char *n = index_node(self, v);

Perhaps we should check if n == NULL. index_node_existing() might be more
appropriate.

Can you send a followup?

In D3499#55925, @yuja wrote:

+static int nt_shortest(indexObject *self, const char *node)
+{
+ int level, off;
+
+ if (nt_init(self) == -1)
+ return -3;
+ if (nt_populate(self) == -1)
+ return -3;
+
+ for (level = off = 0; level < 40; level++) {
+ int k, v;
+ nodetree *n = &self->nt[off];
+ k = nt_level(node, level);
+ v = n->children[k];
+ if (v < 0) {
+ v = -(v + 1);
+ const char *n = index_node(self, v);

Perhaps we should check if n == NULL. index_node_existing() might be more
appropriate.

Oops, funny how I missed that after just having added index_node_existing. Thanks for noticing.

Can you send a followup?

Will do. Feel free to fold in.

martinvonz mentioned this in D3530: revlog: handle error from node lookup.May 11 2018, 10:33 AM

Closed by commit rHG0304f22497fa: revlog: use node tree (native code) for shortest() calculation (authored by martinvonz). · Explain WhyMay 11 2018, 3:32 PM

This revision was automatically updated to reflect the committed changes.

martinvonz mentioned this in rHG312d7d14d44e: revlog: handle error from node lookup.May 11 2018, 10:54 PM

Revision Contents
Changeset List

			Path	Packages
M			mercurial/cext/parsers.c (2 lines)
M			mercurial/cext/revlog.c (73 lines)
M			mercurial/policy.py (2 lines)
M			mercurial/revlog.py (26 lines)

Diff	ID	Description	Created	Lint	Unit
Base		Base
Diff 1	8552		May 8 2018, 2:07 PM	★	★
Diff 2	8624		May 10 2018, 12:01 PM	★	★
Diff 3	8639	rHG0304f22497fafcfeedf80fb0698d888ee41a2135	May 3 2018, 2:17 AM	★	★

Commit	Parents	Author	Summary	Date
		Martin von Zweigbergk		May 3 2018, 2:17 AM

Status	Author	Revision
Closed	martinvonz	D3502 shortest: move revnum-disambiguation out of revlog
Closed	martinvonz	D3501 shortest: remove unnecessary check for revnum in isvalid()
Closed	martinvonz	D3500 shortest: make pure code also disambigute against revnums at end
Closed	martinvonz	D3499 revlog: use node tree (native code) for shortest() calculation
Closed	martinvonz	D3498 revlog: use literal -1 instead of variable that always has that value
Closed	martinvonz	D3497 revlog: extract function for fully populating the radix tree

Diff 8624

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 = 4;			static const int version = 5;

	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

	if (nt_init(self) == -1)			if (nt_init(self) == -1)
	return -3;			return -3;
	if (nt_populate(self) == -1)			if (nt_populate(self) == -1)
	return -3;			return -3;

	return nt_find(self, node, nodelen, 1);			return nt_find(self, node, nodelen, 1);
	}			}

				/*
				* Find the length of the shortest unique prefix of node.
				*
				* Return values:
				*
				* -3: error (exception set)
				* -2: not found (no exception set)
				* rest: length of shortest prefix
				*/
				static int nt_shortest(indexObject self, const char node)
				{
				int level, off;

				if (nt_init(self) == -1)
				return -3;
				if (nt_populate(self) == -1)
				return -3;

				for (level = off = 0; level < 40; level++) {
				int k, v;
				nodetree *n = &self->nt[off];
				k = nt_level(node, level);
				v = n->children[k];
				if (v < 0) {
				v = -(v + 1);
				const char *n = index_node(self, v);
				if (memcmp(node, n, 20) != 0)
				/*
				* Found a unique prefix, but it wasn't for the
				* requested node (i.e the requested node does
				* not exist).
				*/
				return -2;
				return level + 1;
				}
				if (v == 0)
				return -2;
				off = v;
				}
				/*
				* 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
				* this file that made us insert a node longer than 40 hex digits.
				*/
				PyErr_SetString(PyExc_Exception, "broken node tree");
				return -3;
				}

	static PyObject index_partialmatch(indexObject self, PyObject *args)			static PyObject index_partialmatch(indexObject self, PyObject *args)
	{			{
	const char *fullnode;			const char *fullnode;
	int nodelen;			int nodelen;
	char *node;			char *node;
	int rev, i;			int rev, i;

	if (!PyArg_ParseTuple(args, PY23("s#", "y#"), &node, &nodelen))			if (!PyArg_ParseTuple(args, PY23("s#", "y#"), &node, &nodelen))

	fullnode = index_node_existing(self, rev);			fullnode = index_node_existing(self, rev);
	if (fullnode == NULL) {			if (fullnode == NULL) {
	return NULL;			return NULL;
	}			}
	return PyBytes_FromStringAndSize(fullnode, 20);			return PyBytes_FromStringAndSize(fullnode, 20);
	}			}

				static PyObject index_shortest(indexObject self, PyObject *args)
				{
				Py_ssize_t nodelen;
				PyObject *val;
				char *node;
				int length;

				if (!PyArg_ParseTuple(args, "O", &val))
				return NULL;
				if (node_check(val, &node, &nodelen) == -1)
				return NULL;

				self->ntlookups++;
				length = nt_shortest(self, node);
				if (length == -3)
				return NULL;
				if (length == -2) {
				raise_revlog_error();
				return NULL;
				}
				return PyInt_FromLong(length);
				}

	static PyObject index_m_get(indexObject self, PyObject *args)			static PyObject index_m_get(indexObject self, PyObject *args)
	{			{
	Py_ssize_t nodelen;			Py_ssize_t nodelen;
	PyObject *val;			PyObject *val;
	char *node;			char *node;
	int rev;			int rev;

	if (!PyArg_ParseTuple(args, "O", &val))			if (!PyArg_ParseTuple(args, "O", &val))
	{"headrevsfiltered", (PyCFunction)index_headrevs, METH_VARARGS,			{"headrevsfiltered", (PyCFunction)index_headrevs, METH_VARARGS,
	"get filtered head revisions"}, /* Can always do filtering */			"get filtered head revisions"}, /* Can always do filtering */
	{"deltachain", (PyCFunction)index_deltachain, METH_VARARGS,			{"deltachain", (PyCFunction)index_deltachain, METH_VARARGS,
	"determine revisions with deltas to reconstruct fulltext"},			"determine revisions with deltas to reconstruct fulltext"},
	{"insert", (PyCFunction)index_insert, METH_VARARGS,			{"insert", (PyCFunction)index_insert, METH_VARARGS,
	"insert an index entry"},			"insert an index entry"},
	{"partialmatch", (PyCFunction)index_partialmatch, METH_VARARGS,			{"partialmatch", (PyCFunction)index_partialmatch, METH_VARARGS,
	"match a potentially ambiguous node ID"},			"match a potentially ambiguous node ID"},
				{"shortest", (PyCFunction)index_shortest, METH_VARARGS,
				"find length of shortest hex nodeid of a binary ID"},
	{"stats", (PyCFunction)index_stats, METH_NOARGS,			{"stats", (PyCFunction)index_stats, METH_NOARGS,
	"stats for the index"},			"stats for the index"},
	{NULL} /* Sentinel */			{NULL} /* Sentinel */
	};			};

	static PyGetSetDef index_getset[] = {			static PyGetSetDef index_getset[] = {
	{"nodemap", (getter)index_nodemap, NULL, "nodemap", NULL},			{"nodemap", (getter)index_nodemap, NULL, "nodemap", NULL},
	{NULL} /* Sentinel */			{NULL} /* Sentinel */

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'): 4,			(r'cext', r'parsers'): 5,
	}			}

	# 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/revlog.py

	return False			return False
	except error.WdirUnsupported:			except error.WdirUnsupported:
	# single 'ff...' match			# single 'ff...' match
	return True			return True
	if node is None:			if node is None:
	raise LookupError(node, self.indexfile, _('no node'))			raise LookupError(node, self.indexfile, _('no node'))
	return not isrev(prefix)			return not isrev(prefix)

				def maybewdir(prefix):
				return all(c == 'f' for c in prefix)

	hexnode = hex(node)			hexnode = hex(node)

				def disambiguate(hexnode, minlength):
				for length in range(minlength, 41):
				prefix = hexnode[:length]
				if not isrev(prefix) and not maybewdir(prefix):
				return prefix

				if not getattr(self, 'filteredrevs', None):
				try:
				length = max(self.index.shortest(node), minlength)
				return disambiguate(hexnode, length)
				except RevlogError:
				if node == wdirid:
				for length in range(minlength, 41):
				prefix = hexnode[:length]
				if isvalid(prefix):
				return prefix
				else:
				raise LookupError(node, self.indexfile, _('no node'))
				except AttributeError:
				# Fall through to pure code
				pass

	shortest = hexnode			shortest = hexnode
	startlength = max(6, minlength)			startlength = max(6, minlength)
	length = startlength			length = startlength
	while True:			while True:
	prefix = hexnode[:length]			prefix = hexnode[:length]
	if isvalid(prefix):			if isvalid(prefix):
	shortest = prefix			shortest = prefix
	if length == minlength or length > startlength:			if length == minlength or length > startlength: