diff --git a/rust/treedirstate/src/python.rs b/rust/treedirstate/src/python.rs
--- a/rust/treedirstate/src/python.rs
+++ b/rust/treedirstate/src/python.rs
@@ -318,4 +318,33 @@
         Ok(self.dirstate(py).borrow().root_id().map(|id| id.0))
     }
 
+    def computenonnormals(&self, nonnormal: PyObject, otherparent: PyObject) -> PyResult<PyObject> {
+        let mut dirstate = self.dirstate(py).borrow_mut();
+        let mut tracked_visitor = |filepath: &Vec<KeyRef>, state: &mut FileState| {
+            if state.state != b'n' || state.mtime == -1 {
+                let filename = PyBytes::new(py, &filepath.concat()).into_object();
+                nonnormal.call(py, (filename,), None).map_err(|e| callback_error(py, e))?;
+            }
+            if state.state == b'n' && state.mtime == -2 {
+                let filename = PyBytes::new(py, &filepath.concat()).into_object();
+                otherparent.call(py, (filename,), None).map_err(|e| callback_error(py, e))?;
+            }
+            Ok(())
+        };
+        dirstate
+            .visit_tracked(&mut tracked_visitor)
+            .map_err(|e| PyErr::new::<exc::IOError, _>(py, e.description()))?;
+
+        let mut removed_visitor = |filepath: &Vec<KeyRef>, _state: &mut FileState| {
+            let filename = PyBytes::new(py, &filepath.concat()).into_object();
+            nonnormal.call(py, (filename,), None).map_err(|e| callback_error(py, e))?;
+            Ok(())
+        };
+        dirstate
+            .visit_removed(&mut removed_visitor)
+            .map_err(|e| PyErr::new::<exc::IOError, _>(py, e.description()))?;
+
+        Ok(py.None())
+    }
+
 });
diff --git a/treedirstate/__init__.py b/treedirstate/__init__.py
--- a/treedirstate/__init__.py
+++ b/treedirstate/__init__.py
@@ -28,6 +28,9 @@
 treedirstateversion = 1
 useinnewrepos = True
 
+# Sentinel length value for when a nonnormalset or otherparentset is absent.
+setabsent = 0xffffffff
+
 class _reader(object):
     def __init__(self, data, offset):
         self.data = data
@@ -207,19 +210,22 @@
 
     def addfile(self, f, oldstate, state, mode, size, mtime):
         self._rmap.addfile(f, oldstate, state, mode, size, mtime)
-        if state != 'n' or mtime == -1:
-            self._nonnormalset.add(f)
-        else:
-            self._nonnormalset.discard(f)
-        if size == -2:
-            self._otherparentset.add(f)
-        else:
-            self._otherparentset.discard(f)
+        if self._nonnormalset is not None:
+            if state != 'n' or mtime == -1:
+                self._nonnormalset.add(f)
+            else:
+                self._nonnormalset.discard(f)
+        if self._otherparentset is not None:
+            if size == -2:
+                self._otherparentset.add(f)
+            else:
+                self._otherparentset.discard(f)
 
     def removefile(self, f, oldstate, size):
         self._rmap.removefile(f, oldstate, size)
-        self._nonnormalset.add(f)
-        if size == -2:
+        if self._nonnormalset is not None:
+            self._nonnormalset.add(f)
+        if size == -2 and self._otherparentset is not None:
             self._otherparentset.add(f)
 
     def dropfile(self, f, oldstate):
@@ -227,8 +233,10 @@
         Drops a file from the dirstate.  Returns True if it was previously
         recorded.
         """
-        self._nonnormalset.discard(f)
-        self._otherparentset.discard(f)
+        if self._nonnormalset is not None:
+            self._nonnormalset.discard(f)
+        if self._otherparentset is not None:
+            self._otherparentset.discard(f)
         return self._rmap.dropfile(f)
 
     def clearambiguoustimes(self, files, now):
@@ -256,12 +264,22 @@
         self._parents = (p1, p2)
         self._dirtyparents = True
 
+    def _computenonnormals(self):
+        self._nonnormalset = set()
+        self._otherparentset = set()
+        self._rmap.computenonnormals(self._nonnormalset.add,
+                                     self._otherparentset.add)
+
     @property
     def nonnormalset(self):
+        if self._nonnormalset is None:
+            self._computenonnormals()
         return self._nonnormalset
 
     @property
     def otherparentset(self):
+        if self._otherparentset is None:
+            self._computenonnormals()
         return self._otherparentset
 
     def getfilefoldmap(self):
@@ -326,6 +344,8 @@
 
         def readset():
             slen = r.readuint()
+            if slen == setabsent:
+                return None
             s = set()
             for _i in range(slen):
                 s.add(r.readstr())
@@ -344,11 +364,16 @@
 
     def write(self, st, now):
         """Write the dirstate to the filehandle st."""
+        if self._nonnormalset is not None:
+            nonnormadd = self._nonnormalset.add
+        else:
+            def nonnormadd(f):
+                pass
         if self._treeid is None:
             self._treeid = '000'
-            self._rmap.write('dirstate.tree.000', now, self._nonnormalset.add)
+            self._rmap.write('dirstate.tree.000', now, nonnormadd)
         else:
-            self._rmap.writedelta(now, self._nonnormalset.add)
+            self._rmap.writedelta(now, nonnormadd)
         st.write(self._genrootdata())
         st.close()
         self._dirtyparents = False
@@ -380,12 +405,20 @@
         for k, v in self.copymap.iteritems():
             w.writestr(k)
             w.writestr(v)
-        w.writeuint(len(self._nonnormalset))
-        for v in self._nonnormalset:
-            w.writestr(v)
-        w.writeuint(len(self._otherparentset))
-        for v in self._otherparentset:
-            w.writestr(v)
+
+        setthreshold = max(1000, self._rmap.filecount() / 3)
+
+        def writeset(s):
+            if s is None or len(s) > setthreshold:
+                # The set is absent or too large.  Mark it as absent.
+                w.writeuint(setabsent)
+            else:
+                w.writeuint(len(s))
+                for v in s:
+                    w.writestr(v)
+
+        writeset(self._nonnormalset)
+        writeset(self._otherparentset)
 
         return w.buffer.getvalue()