diff --git a/mercurial/context.py b/mercurial/context.py
--- a/mercurial/context.py
+++ b/mercurial/context.py
@@ -121,10 +121,11 @@ class basectx(object):
 
         modified, added, clean = [], [], []
         deleted, unknown, ignored = s[3], s[4], s[5]
+        deletedset = set(deleted)
         withflags = mf1.withflags() | mf2.withflags()
         for fn, mf2node in mf2.iteritems():
             if fn in mf1:
-                if (fn not in deleted and
+                if (fn not in deletedset and
                     ((fn in withflags and mf1.flags(fn) != mf2.flags(fn)) or
                      (mf1[fn] != mf2node and
                       (mf2node or self[fn].cmp(other[fn]))))):
@@ -132,7 +133,7 @@ class basectx(object):
                 elif listclean:
                     clean.append(fn)
                 del mf1[fn]
-            elif fn not in deleted:
+            elif fn not in deletedset:
                 added.append(fn)
         removed = mf1.keys()
         if removed: