v2.55 regression: cache_tree_fully_valid() makes branch-changing checkout ~40s on a large full index (even for same-commit switches)

[tyrielv]

Summary

Since v2.55, a branch-changing git checkout on a large full index has become dramatically slower. Almost the entire cost is in cache_tree_fully_valid(). The slowdown is independent of how many paths change: switching between two branches that point at the same commit (zero working-tree updates, nr_unpack_entries=0) takes ~40s. The same operation on v2.54 completes in <1s.

Environment

• Microsoft Git v2.55.0.vfs.0.3 (also reproduces on v2.55.0.vfs.0.6), Windows x64
• Large repository — index has ~2.4M entries (~180 MB full index)
• Reproduced in two independent setups (see below)

Steps to reproduce

1. In a repo with a very large index, create two branches at the same commit:

   git branch branchA
   git branch branchB
   

2. Alternate checking them out:

   git checkout branchA
   git checkout branchB
   

   Each switch moves HEAD to a different ref but changes no files (identical trees).

Expected

Sub-second — nothing is written to the working tree.

Actual

~40–44s per switch on v2.55. The same steps on v2.54 finish in <1s (verified by direct A/B on the same repository).

Evidence — GIT_TRACE2_PERF, exactly one checkout (wall-clock ~44s)

Confirmed a single git process (one cmd_name = checkout, no child git processes):

Region	t_rel (s)
cache_tree … fully_valid (call 1, inside unpack_trees)	~20
cache_tree … fully_valid (call 2, during index write)	~19
unpack_trees … check_updates	~0.0001
unpack_trees/nr_unpack_entries	0

cache-tree.c:262  region_enter  cache_tree  ....label:fully_valid
cache-tree.c:264  region_leave  19.919597   cache_tree  ....label:fully_valid   (inside unpack_trees)
unpack-trees.c:2147 data  unpack_trees/nr_unpack_entries:0
cache-tree.c:262  region_enter  cache_tree  label:fully_valid
cache-tree.c:264  region_leave  18.359747   cache_tree  label:fully_valid       (during index write)

In our repro cache_tree_fully_valid() is invoked twice per checkout (~20s + ~19s ≈ ~40s of the ~44s total); check_updates — the phase parallel checkout speeds up — is ~0.

Two independent reproductions

1. GVFS/VFS-for-Git enlistment (virtual filesystem, ~183 MB index): ~39–44s per switch.

2. Plain scalar clone of the same repo (no virtual filesystem, ~179 MB index): ~44s per switch, same trace shape (2× fully_valid, nr_unpack_entries=0).

   Important: a default scalar clone uses a sparse index, and with the sparse index the checkout is fast — the regression does not appear. It only reproduces after disabling the sparse index and expanding to a full index:

   git config index.sparse false
   git read-tree HEAD     # materialize the full ~2.4M-entry index
   

   This localizes the cost to full-index cache-tree validation, and shows it is not specific to GVFS.

What we ruled out

• Parallel checkout / core.fscache: checkout.workers=0 (parallel) vs =1 (sequential) are identical (~38–44s each). check_updates is ~0, so parallelizing working-tree writes changes nothing.
• Amount of change: nr_unpack_entries=0 — the cost is a fixed per-checkout tax, not proportional to changed paths, and is worst for same-commit switches.
• GVFS virtual filesystem: also reproduces on a plain scalar clone (full index).
• Not present in v2.54: verified by direct A/B on the same repository (<1s).
• Sparse index avoids it: only the full index is affected.

Notes

• Also present in v2.55.0.vfs.0.6.

[tyrielv]

Root cause (measured, with an instrumented build)

I instrumented cache_tree_fully_valid() and the odb read path. One same-commit
branch switch (index ~2.4M entries, one alternate = a shared object cache):

fully_valid/nodes:        381,006
fully_valid/odb_misses:   0            <- every object found on the first read
fully_valid/loose_lstats: 380,944      <- ~1 wasted lstat() per node
fully_valid region:       16.2s + 15.9s = ~32s

There are no cache misses, no fetches, and no reprepares. The entire cost is
one wasted filesystem lstat() per tree node -- ~381K lstat() calls on
loose-object paths that do not exist.

Why the lstat happens

Three things combine, and all three are required:

1. The recursion is enabled. cache_tree_fully_valid() walks every node of
   the cache tree, calling odb_has_object() per node.

2. ODB_HAS_OBJECT_RECHECK_PACKED clears OBJECT_INFO_QUICK. With QUICK
   off, the loose-object check takes the real-lstat() branch in
   read_object_info_from_path() (odb/source-loose.c) instead of the cached
   quick_has_loose() fast path.

3. Object lookup is per-source, packed-then-loose. odb_read_object_info_extended()
   iterates odb->sources and, within each source,
   odb_source_files_read_object_info() checks that source's packfiles then its
   loose store (odb/source-files.c). The tree objects live in the alternate
   (the shared object cache), not the primary object dir. So for each object the
   search is: primary packfiles (miss) -> primary loose lstat() (miss) ->
   alternate packfiles (hit). That wasted primary-loose lstat() runs once per
   object.

Why 2.55 is the first affected version

The behavior is the product of two independent upstream changes that first
coexist in 2.55:

• Per-source lookup order (global-pack-list-first -> per-source
  packed-then-loose) came from the odb "sources" refactor
  (cb506a8a69 "odb: introduce "files" source" and the surrounding series by
  Patrick Steinhardt), which landed in upstream v2.54.0.
• The recursion was restored by 521731213c
  "cache-tree: fix inverted object existence check in cache_tree_fully_valid",
  which landed in upstream v2.55.0. Between v2.50 and v2.54 an inverted
  check (introduced by 062b914c84, 2025-04-29) made
  cache_tree_fully_valid() bail at the root without recursing, so the
  per-object cost never showed.

Timeline of the combination:

Version	Recursion	odb lookup order	Result
2.49	yes	global packs first	fast (~2s)
2.50-2.53	no (bail)	global packs first	fast
2.54	no (bail)	per-source packed/loose	fast (masked)
2.55	yes	per-source packed/loose	slow (~32s)

So 2.49 recurses too, but its global-pack-first search finds the alternate's
packed object before any loose lstat, so it stays ~2s. 2.55 is the first (and
only) version that has both the recursion and the per-source order.

Not the usual suspects

• Not "many packfiles." fully_valid time is flat (~14-15s) from 15 to 99
  packs -- the cost does not scale with pack count. It is the per-node lstat,
  not pack search.
• Not object fetching / cache-server state. odb_misses = 0; nothing is
  fetched during the walk.
• Not GVFS-specific. It also reproduces on a plain scalar clone (once the
  sparse index is expanded to a full index), because that enlistment also has
  an alternate (the scalar shared cache) where the objects live.

Fix directions

• Drop ODB_HAS_OBJECT_RECHECK_PACKED in cache_tree_fully_valid() (use
  odb_has_object(..., 0)): restores the quick_has_loose() fast path and
  avoids the wasted lstat. The cache-tree OIDs are already-known local trees,
  so the quick existence check is sufficient.
• Or restore an all-packs-before-loose search order across sources, so an
  object present in any source's packfiles is found before any loose lstat.
• Or short-circuit the walk the way update_one() already does at the root.

[tyrielv]

Fix approach (and alternatives considered)

Chosen fix: reorder the ODB read loop to consult every source's
packfiles before any source's loose object store, gated on the
repository having alternates. It preserves the exact meaning of
cache_tree_fully_valid(), fixes every RECHECK_PACKED caller rather
than one, and restores pre-refactor performance (cache_tree_fully_valid()
~32s -> ~2s; ~380k wasted stat()s -> 0). It keeps the per-source
encapsulation from the upstream refactor and only changes the search
order when more than one source exists, so single-source repositories
are unaffected.

Two narrower options were considered and rejected:

• Drop ODB_HAS_OBJECT_RECHECK_PACKED in cache_tree_fully_valid()
  (use the OBJECT_INFO_QUICK path). Measured ~4.9s vs the ordering
  fix's ~2.4s. It removes the stat() but still pays a
  quick_has_loose() probe per object on the primary source, and it
  only patches this one caller instead of the shared root cause in the
  ODB read loop.

• Short-circuit cache_tree_fully_valid() to a root-only check
  (mirroring update_one()). Fastest in isolation, but it weakens the
  function's contract from "every tree object is present" to "the root
  tree is present," relying on the prune-closure invariant (git prune
  removes whole reachability closures, so a present root implies present
  children). That assumption only holds for the prune/gc threat model,
  not for partial clones or corruption, and it diverges for the
  sparse-index.c caller, which frees and fully recomputes on an
  invalid result and would therefore act on the deeper check. Since all
  callers run cache_tree_fully_valid() unconditionally before any
  fallback, this option also buys nothing the ordering fix doesn't,
  while changing observable behavior. Rejected in favor of keeping the
  contract intact and making the underlying lookup cheap.

A PR implementing the ordering fix (with a t5615 regression test that
uses %(deltabase) to prove an object is read from an alternate's pack
rather than a local loose copy) is on the way.