Summary

RelPath's Ord compared components(), splitting both paths at every
separator. It now compares bytes, ranking / below every other byte,
and skips equal 16-byte chunks first. Components never contain /, so
the order is the same.

The worktree snapshot keys entries_by_path by RelPath, so the
background scanner compares paths for every insert and lookup. It does
that while holding BackgroundScanner::state, which workers hold for
about 90% of an initial scan, so the comparison sets how fast the scan
finishes.

One comparison, outside Zed in a release build:

Pair Before After
Equal paths 75.9 ns 3.7 ns
Siblings at depth 6 71.8 ns 2.1 ns
Different top-level directories 13.8 ns 1.3 ns
Parent and child 66.2 ns 3.5 ns
a/b and a.b 35.2 ns 1.3 ns
200-byte name, last byte differs 23.3 ns 5.9 ns
16 one-byte components 198.3 ns 4.0 ns
Random pairs from the Linux snapshot 38.2 ns 7.2 ns
Neighbours in the sorted Linux snapshot 78.4 ns 12.4 ns

Initial scan with Worktree::local and RealFs in a headless app, one
scan per process, warm file cache, Ryzen 7 9800X3D (16 threads), median
of alternating runs (9 per variant, 5 for Firefox):

Tree Entries Wall before Wall after CPU before CPU after
Linux snapshot as empty files, tmpfs 72,680 333.6 ms 212.2 ms
1,210 ms 1,184 ms
Linux checkout 120,916 615.4 ms 360.7 ms 2,126 ms 2,034 ms
Firefox checkout 532,906 4.38 s 2.29 s 11.62 s 10.18 s
Zed checkout 5,351 45.8 ms 36.8 ms 147.8 ms 144.0 ms

The snapshot is not a Git repository, so the scan defers directories
deeper than file_scan_depth. Both versions found the same entries in
every run.

Testing

  • test_rel_path_cmp_matches_component_order is new. It checks the
    order against components() for pairs that differ at or around a
    separator, prefixes, non-ASCII names, and paths with NUL bytes, such as
    the keys that tree_sort_path builds. It also checks each pair with
    15-, 16-, and 32-byte directory prefixes prepended, so the 16-byte chunk
    loop runs.
  • Outside Zed, the new comparison agreed with components() on 8
    million random pairs, including paths with NUL bytes, and returned
    Equal only for equal paths. Both comparisons sort the 103,708 paths of
    the Linux snapshot in the same order, as plain paths and as
    tree_sort_path keys.
  • cargo test -p path, cargo test -p util, cargo test -p worktree,
    cargo test -p project_panel, and cargo test -p git_ui pass.
  • cargo test -p project --features test-support --test integration
    passes.
  • ./script/clippy -p path passes.

Self-review

  • I've reviewed my diff for quality, security, reliability, and
    performance.
  • UI changes follow the
    checklist.
  • Tests cover the new or changed behavior.

Release Notes:

  • Improved the time to scan large projects when they are opened