[PATCH] revert-roots: narrow the subset using smartset operation

[Pierre-Yves David]

# HG changeset patch
# User Pierre-Yves David <pierre-yves.david at fb.com>
# Date 1413015460 25200
#      Sat Oct 11 01:17:40 2014 -0700
# Node ID 99aa98d462b455b00b3af9c8a1f44e3f6268b73d
# Parent  e9edd53770fb77a9787a3e6592a3bf0a29c1bd80
revert-roots: narrow the subset using smartset operation

We were manually creating a base with explicit subset testing. We should let
smartset magic happen and optimise that logic if needed.

benchmark show some massive speedup when "parents set" is huge and "subset" is
small.

revset: 42:68 and roots(42:tip)
0) wall 0.011322 comb 0.010000 user 0.010000 sys 0.000000 (best of 161)
1) wall 0.002282 comb 0.010000 user 0.010000 sys 0.000000 (best of 1082)

Minor speedup in simple case (were fullreposet helps)

revset: roots(0::tip)
0) wall 0.095688 comb 0.100000 user 0.100000 sys 0.000000 (best of 85)
1) wall 0.084448 comb 0.080000 user 0.080000 sys 0.000000 (best of 95)

revset: roots((0:tip)::)
0) wall 0.146752 comb 0.140000 user 0.140000 sys 0.000000 (best of 58)
1) wall 0.143538 comb 0.140000 user 0.140000 sys 0.000000 (best of 59)

And small overhead then the "parents set" is fairly complicated (transforming it
into a revset once and for all appears to be faster).

revset: roots((tip~100::) - (tip~100::tip))
0) wall 0.004652 comb 0.010000 user 0.010000 sys 0.000000 (best of 544)
1) wall 0.004878 comb 0.010000 user 0.010000 sys 0.000000 (best of 479)

revset: roots((0::) - (0::tip))
0) wall 0.146587 comb 0.150000 user 0.150000 sys 0.000000 (best of 53)
1) wall 0.157192 comb 0.160000 user 0.160000 sys 0.000000 (best of 53)

revset: first(roots((0::) - (0::tip)))
0) wall 0.152924 comb 0.150000 user 0.150000 sys 0.000000 (best of 57)
1) wall 0.153192 comb 0.160000 user 0.160000 sys 0.000000 (best of 55)

diff --git a/contrib/revsetbenchmarks.txt b/contrib/revsetbenchmarks.txt
--- a/contrib/revsetbenchmarks.txt
+++ b/contrib/revsetbenchmarks.txt
@@ -15,10 +15,11 @@ min(0:tip)
 0::
 min(0::)
 # those two `roots(...)` inputs are close to what phase movement use.
 roots((tip~100::) - (tip~100::tip))
 roots((0::) - (0::tip))
+42:68 and roots(42:tip)
 ::p1(p1(tip))::
 public()
 :10000 and public()
 draft()
 :10000 and draft()
diff --git a/mercurial/revset.py b/mercurial/revset.py
--- a/mercurial/revset.py
+++ b/mercurial/revset.py
@@ -1679,11 +1679,11 @@ def reverse(repo, subset, x):
 def roots(repo, subset, x):
     """``roots(set)``
     Changesets in set with no parent changeset in set.
     """
     s = getset(repo, fullreposet(repo), x)
-    subset = baseset([r for r in s if r in subset])
+    subset = subset & s# baseset([r for r in s if r in subset])
     cs = _children(repo, subset, s)
     return subset - cs
 
 def secret(repo, subset, x):
     """``secret()``