diff --git a/contrib/revsetbenchmarks.txt b/contrib/revsetbenchmarks.txt
--- a/contrib/revsetbenchmarks.txt
+++ b/contrib/revsetbenchmarks.txt
@@ -21,3 +21,4 @@ public()
 draft()
 :10000 and draft()
 max(::(tip~20) - obsolete())
+roots((0:tip)::)
diff --git a/mercurial/revset.py b/mercurial/revset.py
--- a/mercurial/revset.py
+++ b/mercurial/revset.py
@@ -2232,6 +2232,13 @@ class baseset(list):
         """Returns a new object with the substraction of the two collections.
 
         This is part of the mandatory API for smartset."""
+        # If we are operating on 2 baseset, do the computation now since all
+        # data is available. The alternative is to involve a lazyset, which
+        # may be slow.
+        if isinstance(other, baseset):
+            other = other.set()
+            return baseset([x for x in self if x not in other])
+
         return self.filter(lambda x: x not in other)
 
     def __and__(self, other):