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.

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
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.May 8 2018, 2:07 PM
yuja added a subscriber: yuja.May 10 2018, 9:08 AM

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.

martinvonz added a comment.May 10 2018, 12:01 PM
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
yuja added a comment.May 11 2018, 10:20 AM

+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?

martinvonz added a comment.May 11 2018, 10:33 AM
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.

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.

Revision Contents
Changeset List

PathPackages
Mmercurial/cext/parsers.c (2 lines)
Mmercurial/cext/revlog.c (74 lines)
Mmercurial/policy.py (2 lines)
Mmercurial/revlog.py (26 lines)

Diff 8639

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) {
const char *n;
v = -(v + 1);
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: