Patchwork [1,of,2] revset: make children O(number of children)

login
register
mail settings
Submitter Durham Goode
Date Sept. 23, 2014, 6:31 a.m.
Message ID <e7e0c696c29e1735aad7.1411453868@dev2000.prn2.facebook.com>
Download mbox | patch
Permalink /patch/5916/
State Accepted
Headers show

Comments

Durham Goode - Sept. 23, 2014, 6:31 a.m.
# HG changeset patch
# User Durham Goode <durham@fb.com>
# Date 1411450626 25200
#      Mon Sep 22 22:37:06 2014 -0700
# Node ID e7e0c696c29e1735aad7a77f82bfc987354a98c1
# Parent  e6e7ef68c879b55c1b2c0ebe00d8cbdbc929dbed
revset: make children O(number of children)

Previously children() would iterate over every item in the subset (often time
the entire repo) and check if they were in the childset. This was super slow.

Now we iterate over items in the childset and check them against the subset,
which makes the function O(number of children) instead of O(size of repo).

This takes a rebase in a large repo from 17 seconds to 14 seconds.

revset #29: (children(ancestor(tip~5, tip)) and ::(tip~5))::
0) wall 0.171047 comb 0.170000 user 0.170000 sys 0.000000 (best of 51)
1) wall 0.155102 comb 0.150000 user 0.150000 sys 0.000000 (best of 55)

Patch

diff --git a/contrib/revsetbenchmarks.txt b/contrib/revsetbenchmarks.txt
--- a/contrib/revsetbenchmarks.txt
+++ b/contrib/revsetbenchmarks.txt
@@ -27,3 +27,4 @@ 
 (_intlist('20000\x0020001')) and merge()
 parents(20000)
 (20000::) - (20000)
+(children(ancestor(tip~5, tip)) and ::(tip~5))::
diff --git a/mercurial/revset.py b/mercurial/revset.py
--- a/mercurial/revset.py
+++ b/mercurial/revset.py
@@ -575,7 +575,7 @@ 
     """
     s = getset(repo, baseset(repo), x).set()
     cs = _children(repo, subset, s)
-    return subset & cs
+    return cs & subset
 
 def closed(repo, subset, x):
     """``closed()``