changeset 22450:95af98616aa7

revset: make parents() O(number of parents) Strip executes a revset like this: max(parents(_intlist('1234\x001235')) - _intlist('1234\x001235')) Previously the parents() revset would do 'subset & parents' which iterates over each item in the subset and checks if it's in parents. subset is usually the entire repo (a spanset) so this takes a while. Reversing the parameters to be 'parents & subset' means the operation becomes O(number of parents) instead of O(size of repo). It also means the result gets evaluated immediately (since parents isn't a lazy set), but I think this is a win in most scenarios. This shaves 0.3 seconds off strip (amend/histedit/rebase/etc) for large repositories. revset #0: parents(20000) 0) obsolete feature not enabled but 54243 markers found! ! wall 0.006256 comb 0.010000 user 0.010000 sys 0.000000 (best of 289) 1) obsolete feature not enabled but 54243 markers found! ! wall 0.000391 comb 0.000000 user 0.000000 sys 0.000000 (best of 4323)
author Durham Goode <durham@fb.com>
date Fri, 12 Sep 2014 15:00:51 -0700
parents da05fe01170b
children 186fd06283b4
files contrib/revsetbenchmarks.txt mercurial/revset.py tests/test-revset.t
diffstat 3 files changed, 3 insertions(+), 2 deletions(-) [+]
line wrap: on
line diff
--- a/contrib/revsetbenchmarks.txt	Fri Sep 12 16:21:13 2014 -0700
+++ b/contrib/revsetbenchmarks.txt	Fri Sep 12 15:00:51 2014 -0700
@@ -23,4 +23,5 @@
 max(::(tip~20) - obsolete())
 roots((0:tip)::)
 (not public() - obsolete())
+parents(20000)
 (20000::) - (20000)
--- a/mercurial/revset.py	Fri Sep 12 16:21:13 2014 -0700
+++ b/mercurial/revset.py	Fri Sep 12 15:00:51 2014 -0700
@@ -1236,7 +1236,7 @@
     cl = repo.changelog
     for r in getset(repo, spanset(repo), x):
         ps.update(cl.parentrevs(r))
-    return subset & ps
+    return baseset(ps) & subset
 
 def parentspec(repo, subset, x, n):
     """``set^0``
--- a/tests/test-revset.t	Fri Sep 12 16:21:13 2014 -0700
+++ b/tests/test-revset.t	Fri Sep 12 15:00:51 2014 -0700
@@ -567,10 +567,10 @@
 test intersecting something with an addset
 
   $ log 'parents(outgoing() or removes(a))'
+  8
   1
   4
   5
-  8
 
 check that conversion to only works
   $ try --optimize '::3 - ::1'