diff -r cb466830826a -r 28445179df90 mercurial/obsolete.py
--- a/mercurial/obsolete.py	Sat Nov 16 12:34:05 2013 -0500
+++ b/mercurial/obsolete.py	Sat Nov 16 20:34:58 2013 -0500
@@ -267,7 +267,8 @@
         Return the number of new marker."""
         if not _enabled:
             raise util.Abort('obsolete feature is not enabled on this repo')
-        new = [m for m in markers if m not in self._all]
+        known = set(self._all)
+        new = [m for m in markers if m not in known]
         if new:
             f = self.sopener('obsstore', 'ab')
             try: