Patchwork [4,of,4] bookmarks: cache reverse mapping (issue5868)

login
register
mail settings
Submitter Yuya Nishihara
Date May 6, 2018, 2:53 a.m.
Message ID <9ae8a72dec358d33c967.1525575227@mimosa>
Download mbox | patch
Permalink /patch/31275/
State Accepted
Headers show

Comments

Yuya Nishihara - May 6, 2018, 2:53 a.m.
# HG changeset patch
# User Yuya Nishihara <yuya@tcha.org>
# Date 1525488162 -32400
#      Sat May 05 11:42:42 2018 +0900
# Node ID 9ae8a72dec358d33c96725e1f94c631e869deb80
# Parent  f8b12218af5c8d09da0965d631ad6a19fc9df3de
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)
Augie Fackler - May 6, 2018, 4:47 p.m.
> On May 5, 2018, at 10:53 PM, Yuya Nishihara <yuya@tcha.org> wrote:
> 
> # HG changeset patch
> # User Yuya Nishihara <yuya@tcha.org>
> # Date 1525488162 -32400
> #      Sat May 05 11:42:42 2018 +0900
> # Node ID 9ae8a72dec358d33c96725e1f94c631e869deb80
> # Parent  f8b12218af5c8d09da0965d631ad6a19fc9df3de
> bookmarks: cache reverse mapping (issue5868)

queued, thanks

Patch

diff --git a/mercurial/bookmarks.py b/mercurial/bookmarks.py
--- a/mercurial/bookmarks.py
+++ b/mercurial/bookmarks.py
@@ -60,6 +60,7 @@  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 @@  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 @@  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 @@  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]
diff --git a/tests/test-bookmarks.t b/tests/test-bookmarks.t
--- a/tests/test-bookmarks.t
+++ b/tests/test-bookmarks.t
@@ -68,6 +68,9 @@  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 @@  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 @@  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