[PATCH 3 of 3] dirstate: minimize number of separate lstat calls

[Petr Kodl]

# HG changeset patch
# User Petr Kodl <petrkodl at gmail.com>
# Date 1220646245 14400
# Node ID 5cc4fb7d9dabb55f9a56a9813df0aaeeddbd8224
# Parent  d06d4ec75479dc1a065312751f0f3c86e4bac6c4
dirstate: minimize number of separate lstat calls

diff -r d06d4ec75479 -r 5cc4fb7d9dab mercurial/dirstate.py
--- a/mercurial/dirstate.py	Fri Sep 05 16:24:05 2008 -0400
+++ b/mercurial/dirstate.py	Fri Sep 05 16:24:05 2008 -0400
@@ -509,6 +509,27 @@
                         if (nf in dmap or not ignore(nf)) and matchfn(nf):
                             results[nf] = None
 
+        # if there are no directories to visit 
+        # try to consolidate number of lstat calls anyway 
+        # this reduces # of lstat calls from O(#files) to O(#directories) 
+        # assuming the lstat over files in dir is faster than lstat 
+        # over randomly spread files which seems to be the case at least for 
+        # Win32 and Linux 
+        # option 2 would be to never skip step 2 but this could be expensive in 
+        # extremely sparse trees (many files / small # tracked)
+        recurse = 1
+        if not work: 
+            visit_dirs = {} 
+            for x in [f for f in dmap if f not in results and match(f)]: 
+                visit_dirs[os.path.dirname(x)]=None
+            if '' in visit_dirs: 
+                visit_dirs.pop('')
+                visit_dirs['.']=None
+            visit_dirs = visit_dirs.keys()
+            visit_dirs.sort() 
+            work += visit_dirs 
+            recurse=0
+
         # step 2: visit subdirectories
         while work:
             nd = work.pop()
@@ -529,7 +550,7 @@
                 nf = normalize(nd and (nd + "/" + f) or f, True)
                 if nf not in results:
                     if kind == dirkind:
-                        if not ignore(nf):
+                        if not ignore(nf) and recurse:
                             wadd(nf)
                         if nf in dmap and matchfn(nf):
                             results[nf] = None