D4120: shortest: use nodetree for finding shortest node within revset

martinvonz (Martin von Zweigbergk) phabricator at mercurial-scm.org
Sun Aug 5 07:59:08 UTC 2018


martinvonz created this revision.
Herald added a subscriber: mercurial-devel.
Herald added a reviewer: hg-reviewers.

REVISION 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()").

REPOSITORY
  rHG Mercurial

REVISION DETAIL
  https://phab.mercurial-scm.org/D4120

AFFECTED FILES
  mercurial/cext/revlog.c
  mercurial/scmutil.py

CHANGE DETAILS

diff --git a/mercurial/scmutil.py b/mercurial/scmutil.py
--- a/mercurial/scmutil.py
+++ b/mercurial/scmutil.py
@@ -34,6 +34,7 @@
     obsutil,
     pathutil,
     phases,
+    policy,
     pycompat,
     revsetlang,
     similar,
@@ -52,6 +53,8 @@
 else:
     from . import scmposix as scmplatform
 
+parsers = policy.importmod(r'parsers')
+
 termsize = scmplatform.termsize
 
 class status(tuple):
@@ -514,6 +517,24 @@
                 cache['disambiguationrevset'] = revs
         if cl.rev(node) in revs:
             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 = nodetree.shortest(node)
+                prefix = hexnode[:length]
+                return disambiguate(prefix)
             for length in range(minlength, len(hexnode) + 1):
                 matches = []
                 prefix = hexnode[:length]
diff --git a/mercurial/cext/revlog.c b/mercurial/cext/revlog.c
--- a/mercurial/cext/revlog.c
+++ b/mercurial/cext/revlog.c
@@ -1087,6 +1087,23 @@
 	return -1;
 }
 
+static PyObject *nt_insert_py(nodetree *self, PyObject *args)
+{
+	Py_ssize_t rev;
+	const char *node;
+	if (!PyArg_ParseTuple(args, "i", &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)
 {
 	/* rev==-2 happens to get encoded as 0, which is interpreted as not set */
@@ -1173,13 +1190,42 @@
 	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)
 {
 	free(self->nodes);
 	self->nodes = NULL;
 	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 = {
 	PyVarObject_HEAD_INIT(NULL, 0) /* header */
 	"parsers.nodetree",        /* tp_name */
@@ -1208,7 +1254,7 @@
 	0,                         /* tp_weaklistoffset */
 	0,                         /* tp_iter */
 	0,                         /* tp_iternext */
-	0,                         /* tp_methods */
+	nt_methods,                /* tp_methods */
 	0,                         /* tp_members */
 	0,                         /* tp_getset */
 	0,                         /* tp_base */



To: martinvonz, #hg-reviewers
Cc: mercurial-devel


More information about the Mercurial-devel mailing list