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

This is an archive of the discontinued Mercurial Phabricator instance.

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

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
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 6 2018, 12:53 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.