Repository: jelmer/dulwich

Issue:
porcelain.status takes much longer than git status for many untracked directories
`porcelain.status` takes much longer than `git status` for many untracked directories.

Reproduction:

```bash 
# prep the directories
for i in {1..40}; do
  for j in {1..1000}; do
    mkdir -p tmp/$i/$j
    touch tmp/$i/$j/t
  done
done
```

```bash
# validate the number of directories/files is relatively large
> find tmp | wc -l
   80041
```

```bash
> time git status --porcelain
?? tmp/
git st --porcelain  0.01s user 0.01s system 83% cpu 0.019 total
```

```python
from dulwich import porcelain
from dulwich.repo import Repo
import time
t0 = time.time(); _ = porcelain.status(Repo(".")); print(f"Took {time.time() - t0} seconds")
Took 14.289646625518799 seconds
```

Discussion:
@jelmer: porcelain.status() hasn't been optimized for performance yet - it currently makes a few passes over the working directory, and could probably be simplified to just a single pass.

Solution patch:
diff --git a/dulwich/porcelain.py b/dulwich/porcelain.py
index 7dcdb7ca..210071be 100644
--- a/dulwich/porcelain.py
+++ b/dulwich/porcelain.py
@@ -1641,7 +1641,7 @@ def pull(
             _import_remote_refs(r.refs, remote_name, fetch_result.refs)
 
 
-def status(repo=".", ignored=False, untracked_files="all"):
+def status(repo=".", ignored=False, untracked_files="normal"):
     """Returns staged, unstaged, and untracked changes relative to the HEAD.
 
     Args:
@@ -1649,11 +1649,12 @@ def status(repo=".", ignored=False, untracked_files="all"):
       ignored: Whether to include ignored files in untracked
       untracked_files: How to handle untracked files, defaults to "all":
           "no": do not return untracked files
+          "normal": return untracked directories, not their contents
           "all": include all files in untracked directories
-        Using untracked_files="no" can be faster than "all" when the worktreee
+        Using untracked_files="no" can be faster than "all" when the worktree
           contains many untracked files/directories.
-
-    Note: untracked_files="normal" (git's default) is not implemented.
+        Using untracked_files="normal" provides a good balance, only showing
+          directories that are entirely untracked without listing all their contents.
 
     Returns: GitStatus tuple,
         staged -  dict with lists of staged paths (diff index/HEAD)
@@ -1731,17 +1732,14 @@ def get_untracked_paths(
       untracked_files: How to handle untracked files:
         - "no": return an empty list
         - "all": return all files in untracked directories
-        - "normal": Not implemented
+        - "normal": return untracked directories without listing their contents
 
     Note: ignored directories will never be walked for performance reasons.
       If exclude_ignored is False, only the path to an ignored directory will
       be yielded, no files inside the directory will be returned
     """
-    if untracked_files == "normal":
-        raise NotImplementedError("normal is not yet supported")
-
-    if untracked_files not in ("no", "all"):
-        raise ValueError("untracked_files must be one of (no, all)")
+    if untracked_files not in ("no", "all", "normal"):
+        raise ValueError("untracked_files must be one of (no, all, normal)")
 
     if untracked_files == "no":
         return
@@ -1750,29 +1748,84 @@ def get_untracked_paths(
         ignore_manager = IgnoreFilterManager.from_repo(r)
 
     ignored_dirs = []
+    # List to store untracked directories found during traversal
+    untracked_dir_list = []
 
     def prune_dirnames(dirpath, dirnames):
         for i in range(len(dirnames) - 1, -1, -1):
             path = os.path.join(dirpath, dirnames[i])
             ip = os.path.join(os.path.relpath(path, basepath), "")
+
+            # Check if directory is ignored
             if ignore_manager.is_ignored(ip):
                 if not exclude_ignored:
                     ignored_dirs.append(
                         os.path.join(os.path.relpath(path, frompath), "")
                     )
                 del dirnames[i]
+                continue
+
+            # For "normal" mode, check if the directory is entirely untracked
+            if untracked_files == "normal":
+                # Convert directory path to tree path for index lookup
+                dir_tree_path = path_to_tree_path(basepath, path)
+
+                # Check if any file in this directory is tracked
+                dir_prefix = dir_tree_path + b"/" if dir_tree_path else b""
+                has_tracked_files = any(name.startswith(dir_prefix) for name in index)
+
+                if not has_tracked_files:
+                    # This directory is entirely untracked
+                    # Check if it should be excluded due to ignore rules
+                    is_ignored = ignore_manager.is_ignored(
+                        os.path.relpath(path, basepath)
+                    )
+                    if not exclude_ignored or not is_ignored:
+                        rel_path = os.path.join(os.path.relpath(path, frompath), "")
+                        untracked_dir_list.append(rel_path)
+                    del dirnames[i]
+
         return dirnames
 
-    for ap, is_dir in _walk_working_dir_paths(
-        frompath, basepath, prune_dirnames=prune_dirnames
-    ):
-        if not is_dir:
-            ip = path_to_tree_path(basepath, ap)
-            if ip not in index:
-                if not exclude_ignored or not ignore_manager.is_ignored(
-                    os.path.relpath(ap, basepath)
-                ):
-                    yield os.path.relpath(ap, frompath)
+    # For "all" mode, use the original behavior
+    if untracked_files == "all":
+        for ap, is_dir in _walk_working_dir_paths(
+            frompath, basepath, prune_dirnames=prune_dirnames
+        ):
+            if not is_dir:
+                ip = path_to_tree_path(basepath, ap)
+                if ip not in index:
+                    if not exclude_ignored or not ignore_manager.is_ignored(
+                        os.path.relpath(ap, basepath)
+                    ):
+                        yield os.path.relpath(ap, frompath)
+    else:  # "normal" mode
+        # Walk directories, handling both files and directories
+        for ap, is_dir in _walk_working_dir_paths(
+            frompath, basepath, prune_dirnames=prune_dirnames
+        ):
+            # This part won't be reached for pruned directories
+            if is_dir:
+                # Check if this directory is entirely untracked
+                dir_tree_path = path_to_tree_path(basepath, ap)
+                dir_prefix = dir_tree_path + b"/" if dir_tree_path else b""
+                has_tracked_files = any(name.startswith(dir_prefix) for name in index)
+                if not has_tracked_files:
+                    if not exclude_ignored or not ignore_manager.is_ignored(
+                        os.path.relpath(ap, basepath)
+                    ):
+                        yield os.path.join(os.path.relpath(ap, frompath), "")
+            else:
+                # Check individual files in directories that contain tracked files
+                ip = path_to_tree_path(basepath, ap)
+                if ip not in index:
+                    if not exclude_ignored or not ignore_manager.is_ignored(
+                        os.path.relpath(ap, basepath)
+                    ):
+                        yield os.path.relpath(ap, frompath)
+
+        # Yield any untracked directories found during pruning
+        yield from untracked_dir_list
 
     yield from ignored_dirs
 


Test patch:
diff --git a/tests/test_porcelain.py b/tests/test_porcelain.py
index 16862574..db461576 100644
--- a/tests/test_porcelain.py
+++ b/tests/test_porcelain.py
@@ -3723,6 +3723,69 @@ class StatusTests(PorcelainTestCase):
         _, _, untracked = porcelain.status(self.repo.path, untracked_files="all")
         self.assertEqual(untracked, ["untracked_dir/untracked_file"])
 
+    def test_status_untracked_path_normal(self) -> None:
+        # Create an untracked directory with multiple files
+        untracked_dir = os.path.join(self.repo_path, "untracked_dir")
+        os.mkdir(untracked_dir)
+        untracked_file1 = os.path.join(untracked_dir, "file1")
+        untracked_file2 = os.path.join(untracked_dir, "file2")
+        with open(untracked_file1, "w") as fh:
+            fh.write("untracked1")
+        with open(untracked_file2, "w") as fh:
+            fh.write("untracked2")
+
+        # Create a nested untracked directory
+        nested_dir = os.path.join(untracked_dir, "nested")
+        os.mkdir(nested_dir)
+        nested_file = os.path.join(nested_dir, "file3")
+        with open(nested_file, "w") as fh:
+            fh.write("untracked3")
+
+        # Test "normal" mode - should only show the directory, not individual files
+        _, _, untracked = porcelain.status(self.repo.path, untracked_files="normal")
+        self.assertEqual(untracked, ["untracked_dir/"])
+
+        # Test "all" mode - should show all files
+        _, _, untracked_all = porcelain.status(self.repo.path, untracked_files="all")
+        self.assertEqual(
+            sorted(untracked_all),
+            [
+                "untracked_dir/file1",
+                "untracked_dir/file2",
+                "untracked_dir/nested/file3",
+            ],
+        )
+
+    def test_status_mixed_tracked_untracked(self) -> None:
+        # Create a directory with both tracked and untracked files
+        mixed_dir = os.path.join(self.repo_path, "mixed_dir")
+        os.mkdir(mixed_dir)
+
+        # Add a tracked file
+        tracked_file = os.path.join(mixed_dir, "tracked.txt")
+        with open(tracked_file, "w") as fh:
+            fh.write("tracked content")
+        porcelain.add(self.repo.path, paths=[tracked_file])
+        porcelain.commit(
+            repo=self.repo.path,
+            message=b"add tracked file",
+            author=b"author <email>",
+            committer=b"committer <email>",
+        )
+
+        # Add untracked files to the same directory
+        untracked_file = os.path.join(mixed_dir, "untracked.txt")
+        with open(untracked_file, "w") as fh:
+            fh.write("untracked content")
+
+        # In "normal" mode, should show individual untracked files in mixed dirs
+        _, _, untracked = porcelain.status(self.repo.path, untracked_files="normal")
+        self.assertEqual(untracked, ["mixed_dir/untracked.txt"])
+
+        # In "all" mode, should be the same for mixed directories
+        _, _, untracked_all = porcelain.status(self.repo.path, untracked_files="all")
+        self.assertEqual(untracked_all, ["mixed_dir/untracked.txt"])
+
     def test_status_crlf_mismatch(self) -> None:
         # First make a commit as if the file has been added on a Linux system
         # or with core.autocrlf=True
@@ -4028,8 +4091,19 @@ class StatusTests(PorcelainTestCase):
             )
 
     def test_get_untracked_paths_normal(self) -> None:
-        with self.assertRaises(NotImplementedError):
-            _, _, _ = porcelain.status(repo=self.repo.path, untracked_files="normal")
+        # Create an untracked directory with files
+        untracked_dir = os.path.join(self.repo.path, "untracked_dir")
+        os.mkdir(untracked_dir)
+        with open(os.path.join(untracked_dir, "file1.txt"), "w") as f:
+            f.write("untracked content")
+        with open(os.path.join(untracked_dir, "file2.txt"), "w") as f:
+            f.write("more untracked content")
+
+        # Test that "normal" mode works and returns only the directory
+        _, _, untracked = porcelain.status(
+            repo=self.repo.path, untracked_files="normal"
+        )
+        self.assertEqual(untracked, ["untracked_dir/"])
 
     def test_get_untracked_paths_top_level_issue_1247(self) -> None:
         """Test for issue #1247: ensure top-level untracked files are detected."""