fs: stop stat()ing every entry in recursive readdir

Project: nodejs/node | Language: JavaScript | Concepts: algorithmic-optimization, error-handling, api-design, testing-strategy | Difficulty: mid
Link: https://github.com/nodejs/node/pull/65487

The problem

The recursive variants of fs.readdir(), fs.readdirSync(), and fsPromises.readdir() were inefficient: they performed a stat() system call on every directory entry to determine if it was a directory to recurse into. This resulted in thousands of unnecessary stat() calls, especially costly on large directory trees, making these methods much slower than hand-written directory walks.

Why it's non-trivial

A naive fix might skip the stat() calls, but this would break the correct handling of symbolic links and entries with unknown types, which sometimes need a stat() to determine if they are directories. The solution must preserve behavior (including symlink-following) and output order, while avoiding unnecessary system calls.

The approach

1. Add constants for entry types and update benchmarks to support recursive:

+  UV_DIRENT_DIR,
+  UV_DIRENT_LINK,
+  UV_DIRENT_UNKNOWN,

These constants represent directory, symlink, and unknown types, used to avoid redundant stat() calls.

Benchmarks are updated to allow testing with the new recursive option:

-    fs.readdir(fullPath, { withFileTypes }, () => {
+    fs.readdir(fullPath, { withFileTypes, recursive }, () => {

This change is mirrored for readdirSync as well.

2. Centralize recursive directory traversal logic: A new function, collectRecursiveReaddirResult, is introduced:

function collectRecursiveReaddirResult(dir, prefix, { 0: names, 1: types }, context) {
  const { length } = names;
  for (let i = 0; i < length; i++) {
    const name = names[i];
    const relative = prefix === '' ? name : `${prefix}${pathModule.sep}${name}`;
    let isDirectory;
    if (context.withFileTypes) {
      const dirent = getDirent(dir, name, types[i]);
      ArrayPrototypePush(context.results, dirent);
      // Follow symbolic links to directories, see https://github.com/nodejs/node/issues/52663
      isDirectory = dirent.isDirectory() ||
        (dirent.isSymbolicLink() && binding.internalModuleStat(pathModule.join(dir, name)) === 1);
    } else {
      ArrayPrototypePush(context.results, relative);
      const type = types[i];
      isDirectory = type === UV_DIRENT_DIR ||
        ((type === UV_DIRENT_LINK || type === UV_DIRENT_UNKNOWN) &&
         binding.internalModuleStat(pathModule.join(dir, name)) === 1);
    }
    if (isDirectory) {
      ArrayPrototypePush(context.dirs, pathModule.join(dir, name));
      ArrayPrototypePush(context.prefixes, relative);
    }
  }
}

What this does:

• Uses the type information returned by the binding to avoid a stat() unless the entry is a symlink or unknown type.
• Only calls stat() when necessary to determine if a symlink/unknown is a directory.
• Builds up the list of results and directories to visit, using string concatenation for relative names instead of repeated path.join/path.relative calls.

3. Refactor recursive readdir implementations to use the new logic: For the callback-based API:

-    binding.readdir(
-      path,
-      context.encoding,
-      context.withFileTypes,
-      req,
-    );
+    binding.readdir(path, options.encoding, true, req);

Now always requests types from the binding, so the new logic can be used.

For the sync API:

-  for (let i = 0; i < context.pathsQueue.length; i++) {
-    read(context.pathsQueue[i]);
+  for (let i = 0; i < context.dirs.length; i++) {
+    const dir = context.dirs[i];
+    const result = binding.readdir(dir, options.encoding, true);
+    if (result !== undefined) {
+      collectRecursiveReaddirResult(dir, context.prefixes[i], result, context);
+    }
   }

What this does:

• Removes the old per-entry stat() logic.
• Uses the new function to efficiently collect results and directories for recursion.

4. Update promise-based API similarly:

const readdirWithTypes = (path) => PromisePrototypeThen(
  binding.readdir(path, options.encoding, true, kUsePromises),
  undefined,
  handleErrorFromBinding,
);
// ...
while (queue.length > 0) {
  const { 0: path, 1: prefix, 2: { 0: names, 1: types } } = ArrayPrototypePop(queue);
  for (let i = 0; i < names.length; i++) {
    // ... (see above for logic)
  }
}

What this does:

• Always requests types from the binding.
• Follows the same efficient logic as the sync/callback APIs.

5. Fix test for error handling with Buffer paths:

-readdir(Buffer.from(testDirPath), { recursive: true }, common.mustCall());
+readdir(Buffer.from(testDirPath), { recursive: true }, common.mustSucceed());

What this does:

• Ensures errors are delivered through the callback, not thrown, improving error handling consistency.

From the review thread

[review] anonrig: why did we remove this?

[review] anonrig: can we have jsdoc here please

Takeaways

• Leverage lower-level APIs to avoid redundant system calls: If you already have type information from a directory listing, don't issue extra stat() calls unless strictly necessary (e.g., for symlinks or unknown types).
• Centralize traversal logic for maintainability and correctness: By consolidating recursion and result collection into a single function, you reduce duplication and make it easier to keep behavior consistent across sync, async, and promise APIs.
• Preserve API semantics when optimizing: Even when optimizing for performance, ensure that output order, error handling, and edge-case behaviors (like symlink following) remain unchanged to avoid breaking user code.