bookmarks: cache reverse mapping (issue5868)
I chose a simpler implementation. If the initial cost of building reverse
mapping is significant, we'll have to move it under @propertycache.
The nodemap could be a dict of sets, but I think keeping a sorted list is
better since each node is likely to have zero/one bookmark.
Micro-benchmark with 1001 bookmarks and 1001 revisions:
$ for n in `seq 0 1000`; do touch $n; hg book book$n; hg ci -qAm$n; done
$ hg bookmarks --time > /dev/null
(orig) time: real 0.040 secs (user 0.050+0.000 sys 0.000+0.000)
(new) time: real 0.040 secs (user 0.040+0.000 sys 0.010+0.000)
$ hg log -T '{bookmarks}\n' --time > /dev/null
(orig) time: real 0.160 secs (user 0.160+0.000 sys 0.000+0.000)
(new) time: real 0.090 secs (user 0.100+0.000 sys 0.000+0.000)
--- a/mercurial/bookmarks.py Sat May 05 11:44:43 2018 +0900
+++ b/mercurial/bookmarks.py Sat May 05 11:42:42 2018 +0900
@@ -60,6 +60,7 @@
def __init__(self, repo):
self._repo = repo
self._refmap = refmap = {} # refspec: node
+ self._nodemap = nodemap = {} # node: sorted([refspec, ...])
self._clean = True
self._aclean = True
nm = repo.changelog.nodemap
@@ -76,6 +77,14 @@
if node in nm:
refspec = encoding.tolocal(refspec)
refmap[refspec] = node
+ nrefs = nodemap.get(node)
+ if nrefs is None:
+ nodemap[node] = [refspec]
+ else:
+ nrefs.append(refspec)
+ if nrefs[-2] > refspec:
+ # bookmarks weren't sorted before 4.5
+ nrefs.sort()
except (TypeError, ValueError):
# TypeError:
# - bin(...)
@@ -118,6 +127,7 @@
return self._refmap.keys()
# TODO: maybe rename to allnodes()? but nodes would have to be deduplicated
+ # could be self._nodemap.keys()
def values(self):
return self._refmap.values()
@@ -132,19 +142,29 @@
def _set(self, mark, node):
self._clean = False
+ if mark in self._refmap:
+ self._del(mark)
self._refmap[mark] = node
+ nrefs = self._nodemap.get(node)
+ if nrefs is None:
+ self._nodemap[node] = [mark]
+ else:
+ nrefs.append(mark)
+ nrefs.sort()
def _del(self, mark):
self._clean = False
- del self._refmap[mark]
+ node = self._refmap.pop(mark)
+ nrefs = self._nodemap[node]
+ if len(nrefs) == 1:
+ assert nrefs[0] == mark
+ del self._nodemap[node]
+ else:
+ nrefs.remove(mark)
def names(self, node):
"""Return a sorted list of bookmarks pointing to the specified node"""
- marks = []
- for m, n in self._refmap.iteritems():
- if n == node:
- marks.append(m)
- return sorted(marks)
+ return self._nodemap.get(node, [])
def changectx(self, mark):
node = self._refmap[mark]
--- a/tests/test-bookmarks.t Sat May 05 11:44:43 2018 +0900
+++ b/tests/test-bookmarks.t Sat May 05 11:42:42 2018 +0900
@@ -68,6 +68,9 @@
X 0:f7b1eb17ad24
* X2 0:f7b1eb17ad24
Y -1:000000000000
+ $ hg log -T '{bookmarks % "{rev} {bookmark}\n"}'
+ 0 X
+ 0 X2
$ echo b > b
$ hg add b
@@ -299,6 +302,11 @@
Y 2:db815d6d32e6
Z 0:f7b1eb17ad24
* x y 2:db815d6d32e6
+ $ hg log -T '{bookmarks % "{rev} {bookmark}\n"}'
+ 2 Y
+ 2 x y
+ 1 X2
+ 0 Z
look up stripped bookmark name
@@ -445,6 +453,11 @@
Y 2:db815d6d32e6
* Z 2:db815d6d32e6
x y 2:db815d6d32e6
+ $ hg log -T '{bookmarks % "{rev} {bookmark}\n"}'
+ 2 Y
+ 2 Z
+ 2 x y
+ 1 X2
revision but no bookmark name