diff --git a/mercurial/dirstate.py b/mercurial/dirstate.py
--- a/mercurial/dirstate.py
+++ b/mercurial/dirstate.py
@@ -338,6 +338,19 @@ class dirstate(object):
         if not st:
             return
 
+        if util.safehasattr(parsers, 'dict_new_presized'):
+            # Make an estimate of the number of files in the dirstate based on
+            # its size. From a linear regression on a set of real-world repos,
+            # all over 10,000 files, the size of a dirstate entry is 85
+            # bytes. The cost of resizing is significantly higher than the cost
+            # of filling in a larger presized dict, so subtract 20% from the
+            # size.
+            #
+            # This heuristic is imperfect in many ways, so in a future dirstate
+            # format update it makes sense to just record the number of entries
+            # on write.
+            self._map = parsers.dict_new_presized(len(st) / 71)
+
         # Python's garbage collector triggers a GC each time a certain number
         # of container objects (the number being defined by
         # gc.get_threshold()) are allocated. parse_dirstate creates a tuple