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)

mercurial/bookmarks.py

@@ -60,6 +60,7 b' class bmstore(object):'
     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 b' class bmstore(object):'
                         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 b' class bmstore(object):'
         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 b' class bmstore(object):'
 
     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]

tests/test-bookmarks.t

@@ -68,6 +68,9 b' list bookmarks'
      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 b' list bookmarks'
      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 b' list bookmarks'
      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