changeset 51976:41b8892a2054

branchmap-v3: filter topo heads using node for performance reason

The branchmap currently contains heads as nodeid. If we build a set of revnum
with the topological heads, we need to turn the nodeid in the branchmap to revnum to
be able to check if they are topo-heads. That nodeid → revnum lookup is
"expensive" and adds up to something noticeable if you do it hundreds of thousand
of time.

Instead we turn all the topo-heads revnums into nodes and build a set. So we can
directly test membership of the nodeids stored in the branchmap. That is much
faster.

Ideally we would have revnum in the branchmap and could directly test revnum
against a revnum set and that would be even faster. However that's an adventure
for another time.

Without this change, the branchmap format "v3" was significantly slower than the
"v2" format. With this changes, some of that gap is recovered

With rust + persistent nodemap, this overhead was smaller because the extra
lookup did not had to to build the nodemap from scratch.

In addition the mozilla-unified repository is able to use the "pure_top" mode of
branchmap v3, so it was not really affected by this.

Future changeset will work of the remaining of the performance gap.


### benchmark.name                                 = hg.command.unbundle
  # bin-env-vars.hg.py-re2-module                  = default
  # benchmark.variants.issue6528                   = disabled
  # benchmark.variants.resource-usage              = default
  # benchmark.variants.reuse-external-delta-parent = yes
  # benchmark.variants.revs                        = any-1-extra-rev
  # benchmark.variants.source                      = unbundle
  # benchmark.variants.validate                    = default
  # benchmark.variants.verbosity                   = quiet

 ## data-env-vars.name     = netbeans-2018-08-01-zstd-sparse-revlog
  # bin-env-vars.hg.flavor = default
branch-v2:        0.233711  ~~~~~
branch-v3 before: 0.380994  (+63.02%, +0.15)
branch-v3 after:  0.368769  (+57.79%, +0.14)
  # bin-env-vars.hg.flavor = rust
branch-v2:        0.235230  ~~~~~
branch-v3 before: 0.385060  (+63.70%, +0.15)
branch-v3 after:  0.372460  (+58.34%, +0.14)
 ## data-env-vars.name     = netbeans-2018-08-01-ds2-pnm
  # bin-env-vars.hg.flavor = rust
branch-v2:        0.255586  ~~~~~
branch-v3 before: 0.317524  (+24.23%, +0.06)
branch-v3 after:  0.318907  (+24.78%, +0.06)

 ## data-env-vars.name     = mozilla-central-2024-03-22-zstd-sparse-revlog
  # bin-env-vars.hg.flavor = default
branch-v2:        0.339010  ~~~~~
branch-v3 before: 0.410007  (+20.94%, +0.07)
branch-v3 after:  0.349752   (+3.17%, +0.01)
  # bin-env-vars.hg.flavor = rust
branch-v2:        0.346525  ~~~~~
branch-v3 before: 0.410428  (+18.44%, +0.06)
branch-v3 after:  0.354300   (+2.24%, +0.01)
 ## data-env-vars.name     = mozilla-central-2024-03-22-ds2-pnm
  # bin-env-vars.hg.flavor = rust
branch-v2:        0.380202  ~~~~~
branch-v3 before: 0.393871   (+3.60%, +0.01)
branch-v3 after:  0.396293   (+4.23%, +0.02)

 ## data-env-vars.name     = mozilla-unified-2024-03-22-zstd-sparse-revlog
  # bin-env-vars.hg.flavor = default
branch-v2:        0.412165  ~~~~~
branch-v3 before: 0.438105   (+6.29%, +0.03)
branch-v3 after:  0.424769   (+3.06%, +0.01)
  # bin-env-vars.hg.flavor = rust
branch-v2:        0.412397  ~~~~~
branch-v3 before: 0.438405   (+6.31%, +0.03)
branch-v3 after:  0.421796   (+2.28%, +0.01)
 ## data-env-vars.name     = mozilla-unified-2024-03-22-ds2-pnm
  # bin-env-vars.hg.flavor = rust
branch-v2:        0.429501  ~~~~~
branch-v3 before: 0.452692   (+5.40%, +0.02)
branch-v3 after:  0.443849   (+3.34%, +0.01)

 ## data-env-vars.name     = mozilla-try-2024-03-26-zstd-sparse-revlog
  # bin-env-vars.hg.flavor = default
branch-v2:        3.403171  ~~~~~
branch-v3 before: 6.562345  (+92.83%, +3.16)
branch-v3 after:  6.234055  (+83.18%, +2.83)
  # bin-env-vars.hg.flavor = rust
branch-v2:        3.454876  ~~~~~
branch-v3 before: 6.160248  (+78.31%, +2.71)
branch-v3 after:  6.307813  (+82.58%, +2.85)
 ## data-env-vars.name     = mozilla-try-2024-03-26-ds2-pnm
  # bin-env-vars.hg.flavor = rust
branch-v2:        3.465435  ~~~~~
branch-v3 before: 5.381648  (+55.30%, +1.92)
branch-v3 after:  5.176076  (+49.36%, +1.71)

--- a/mercurial/branchmap.py	Fri Sep 27 15:19:10 2024 +0200
+++ b/mercurial/branchmap.py	Tue Sep 03 02:13:03 2024 +0200
@@ -910,11 +910,13 @@
         """write list of heads to a file
 
         Return the number of heads written."""
+        to_node = repo.changelog.node
         nodecount = 0
         topo_heads = None
         if self._pure_topo_branch is None:
-            topo_heads = set(self._get_topo_heads(repo))
-        to_rev = repo.changelog.index.rev
+            # we match using node because it is faster to built the set of node
+            # than to resolve node → rev later.
+            topo_heads = set(to_node(r) for r in self._get_topo_heads(repo))
         for label, nodes in sorted(self._entries.items()):
             if label == self._pure_topo_branch:
                 # not need to write anything the header took care of that
@@ -922,8 +924,7 @@
             label = encoding.fromlocal(label)
             for node in nodes:
                 if topo_heads is not None:
-                    rev = to_rev(node)
-                    if rev in topo_heads:
+                    if node in topo_heads:
                         continue
                 if node in self._closednodes:
                     state = b'c'