[Bug]: fsevent: watch() rebuilds the whole stream per path, so adding N paths is O(N^2)

[devjgm]

Prerequisites

• I searched existing issues to avoid duplicates

Component

notify (core library)

Operating System

macOS

Notify Version

notify = "8.2.0" (also reproduces on main)

Notify Backend

FSEvents (macOS)

Bug Report

What happened?

On the FSEvents backend, watch() tears down and recreates the entire stream for every path added, so watching N paths costs O(N^2). FsEventWatcher::watch_inner:

fn watch_inner(&mut self, path: &Path, recursive_mode: RecursiveMode) -> Result<()> {
    self.stop();
    let result = self.append_path(path, recursive_mode);
    self.run()?;
    result
}

run() calls FSEventStreamCreate over the whole accumulated path array and spawns a fresh CFRunLoop thread, so adding N paths does N(N+1)/2 path registrations, N stream create/destroy cycles and N thread spawn/joins.

I expected watching N paths to cost about O(N), as it does on the inotify backend, whose watch_inner sends one AddWatch per path with no rebuild.

This matters for anything that watches a directory per crate, like rust-analyzer does, so on a 405-member Rust workspace (like mine) the watch setup takes seconds instead of milliseconds, and it pays that cost again whenever it rebuilds its watch set.

Steps to reproduce

Run the example below, which creates N empty directories and watches them one at a time. Time per watch() call grows linearly, so total time grows quadratically:

N=100   118.9ms
N=200   283.6ms   (2.4x)
N=400   871.9ms   (3.1x)
N=800      3.4s   (3.9x)

Against 405 real crate directories from a my project's real Rust workspace (longer paths, real contents) it is worse:

watch #0    took  992.8µs  cumulative  992.9µs
watch #100  took    4.4ms  cumulative  239.8ms
watch #200  took    7.7ms  cumulative  850.9ms
watch #300  took   11.3ms  cumulative     1.8s
watch #400  took   13.1ms  cumulative     3.0s

405 watch() calls in 3.1s

To generate that path list from any cargo workspace:

cargo metadata --format-version 1 --no-deps \
  | jq -r '.packages[].manifest_path' | xargs -n1 dirname | sort -u > paths.txt

A single watch() call once the array is full takes on the order of 15-25ms, and that call is already a all 405 paths. So adding the paths in one batch should cost about that much in total, rather than 3.1s.

Environment details

macOS 15 (Darwin 25.6.0), aarch64, APFS, local SSD. Same behaviour from the standalone binary below and

Error messages or logs

No errors. sample on the watching thread shows the time going into stream creation, with the rest parkpawned runloop thread to hand its runloop back:

NotifyActor::run
 └ notify::fsevent::FsEventWatcher::run
    ├ (parked) mpmc Channel::recv          <- waiting on the per-run thread handshake
    └ FSEventStreamCreate
       └ fsevent_realpath
          └ __getattrlist

Minimal code example

use notify::{RecursiveMode, Result, Watcher};
use std::path::PathBuf;
use std::time::Instant;

fn main() -> Result<()> {
    // A number makes that many empty dirs; anything else is a file of directory paths.
    let arg = std::env::args().nth(1).unwrap_or_else(|| "400".into());
    let scratch = std::env::temp_dir().join("notify-quadratic-repro-dirs");
    let dirs: Vec<PathBuf> = match arg.parse::<usize>() {
        Ok(n) => (0..n)
            .map(|i| {
                let d = scratch.join(format!("crate{i}"));
                std::fs::create_dir_all(&d).unwrap();
                d
            })
            .collect(),
        Err(_) => std::fs::read_to_string(&arg)
            .unwrap()
            .lines()
            .map(str::trim)
            .filter(|l| !l.is_empty())
            .map(PathBuf::from)
            .collect(),
    };

    let mut watcher = notify::recommended_watcher(|_| {})?;
    let start = Instant::now();
    for (i, dir) in dirs.iter().enumerate() {
        let one = Instant::now();
        watcher.watch(dir, RecursiveMode::Recursive)?;
        if i % 100 == 0 || i + 1 == dirs.len() {
            println!("watch #{i:<4} took {:>8.1?}  cumulative {:>8.1?}", one.elapsed(), start.elapsed());
        }
    }
    println!("\n{} watch() calls in {:.1?}", dirs.len(), start.elapsed());
    std::fs::remove_dir_all(&scratch).ok();
    Ok(())
}

Suggested fix

A bulk entry point that appends everything and rebuilds once, roughly:

fn watch_all(&mut self, paths: impl IntoIterator<Item = (PathBuf, RecursiveMode)>) -> Result<()>

Callers that add paths one at a time are unaffected.

Independently, watch_inner could skip stop()/run() when the new path is already covered by a recursive ancestor watch. stream_paths() already computes exactly that test; it just uses it when building the array rather than to decide whether a rebuild is needed at all.

[reckter]

We are running into this issue using deno --watch on a somewhat big repository. At our scale it takes about ~60s on my M5 Max to get a whole startup, without the --watch, it's about 5s. I can't really contribute anything further to this other then a field-report though.

If you need any information please ask, I am not sure if this should also be raised with the deno repository or not; please tell me if you want it there instead :)