( )⚙ D3453 revlog: use radix tree also for matching keys shorter than 4 hex digits

This is an archive of the discontinued Mercurial Phabricator instance.

Differential D3453

revlog: use radix tree also for matching keys shorter than 4 hex digits
ClosedPublic

Authored by martinvonz on May 6 2018, 12:53 AM.

Details

Reviewers
None
Group Reviewers
hg-reviewers
Commits
rHG92ed344a9e64: revlog: use radix tree also for matching keys shorter than 4 hex digits
Summary

I don't know what the reason for the 4-digit limit was, and I can't
think of any real disadvantages of using the radix tree also when the
requested minimum length is short. This speeds up `hg log -T
'{shortest(node,1)}\n'` from 2m16s to 4.5s by making that not fall
back to pure code.

Diff Detail

Repository
rHG Mercurial
Lint
Lint Skipped
Unit
Unit Tests Skipped

Event Timeline

martinvonz created this revision.May 6 2018, 12:53 AM
Closed by commit rHG92ed344a9e64: revlog: use radix tree also for matching keys shorter than 4 hex digits (authored by martinvonz). · Explain WhyMay 7 2018, 8:54 AM
This revision was automatically updated to reflect the committed changes.
yuja added a subscriber: yuja.May 7 2018, 9:09 AM

"I don't know what the reason for the 4-digit limit was,"

I guessed it would avoid building a full radix tree where a given hash
was likely to be ambiguous, but maybe I'm wrong since it seems clear that
linear scan in Python wouldn't be faster than building radix tree in C.

Revision Contents
Changeset List

PathPackages
Mmercurial/cext/revlog.c (2 lines)

Diff 8470

mercurial/cext/revlog.c

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))
return NULL; return NULL;
if (nodelen < 4) { if (nodelen < 1) {
PyErr_SetString(PyExc_ValueError, "key too short"); PyErr_SetString(PyExc_ValueError, "key too short");
return NULL; return NULL;
} }
if (nodelen > 40) { if (nodelen > 40) {
PyErr_SetString(PyExc_ValueError, "key too long"); PyErr_SetString(PyExc_ValueError, "key too long");
return NULL; return NULL;
} }