Perf: restore O(N+M) item filtering in Lookup.GetItems

[JanProvaznik]

Summary

PR #12320 (merged Sep 2025) reimplemented Lookup.Scope tables to use ItemDictionarySlim + plain List<T> instead of ItemDictionary, for nice allocation/CPU wins on most workloads. As part of that change, the result-construction path inside Lookup.GetItems was rewritten — and an algorithmic regression slipped in:

• Before Perf: Reimplement Lookup.Scope tables without ItemDictionary #12320: result was an ItemDictionary. Removes were applied via ItemDictionary.RemoveItems(allRemoves) which uses an internal Dictionary<T, LinkedListNode<T>> for O(1) hash-keyed deletes. Total per-call cost: O(N + A + M).
• After Perf: Reimplement Lookup.Scope tables without ItemDictionary #12320: result is a List<ProjectItemInstance>. For every item in groupFound and every add, the code calls a static ShouldRemoveItem(item, allRemoves) that linearly scans every list inside allRemoves. Total per-call cost: O((N + A) × M).

Where N = items in the matched group, A = total adds across scopes, M = total removes across scopes.

For projects with thousands of items in one collection that go through many small batched-remove operations (a common pattern in C++ build extensions that partition source files via repeated <ItemGroup><Item Remove="…"/></ItemGroup> intrinsics inside batched targets), this turns multi-minute builds into multi-hour builds. There are external reports of exactly this regression after upgrading to a VS 2026 / vs18.3+ version of MSBuild.

The customer-facing report correctly bisected the regression to PR #12320 by direct line-pointing at the ItemDictionary → List<T> switch.

Architecture change

flowchart LR
  subgraph Before["pre-#12320 (correct, slower allocation profile)"]
    direction TB
    A1[GetItems] --> A2["result = new ItemDictionary"]
    A2 --> A3["ImportItemsOfType(groupFound)"]
    A3 --> A4["ImportItemsOfType(allAdds)"]
    A4 --> A5["RemoveItems(allRemoves)<br/>O(M) hashed removes via _nodes"]
    A5 --> A6[return result]
  end

  subgraph Bug["after #12320 (regressed)"]
    direction TB
    B1[GetItems] --> B2["result = new List"]
    B2 --> B3["foreach item in groupFound:<br/>ShouldRemoveItem(item, allRemoves)<br/><b>O(M) linear scan per item</b>"]
    B3 --> B4["foreach add in allAdds:<br/>ShouldRemoveItem(item, allRemoves)<br/><b>O(M) linear scan per item</b>"]
    B4 --> B5[return result]
    style B3 fill:#fdd
    style B4 fill:#fdd
  end

  subgraph Fix["this PR"]
    direction TB
    C1[GetItems] --> C2["result = new List"]
    C2 --> C3{"totalRemoves &gt; 8?"}
    C3 -- "no (small)" --> C4["foreach item: ShouldRemoveItem<br/>O(M) linear, M is tiny"]
    C3 -- "yes (large)" --> C5["removeSet = HashSet&lt;ProjectItemInstance&gt;<br/>(default = reference equality,<br/>matches ShouldRemoveItem &amp;<br/>pre-#12320 _nodes)"]
    C5 --> C6["foreach item: removeSet.Contains<br/><b>O(1) per item</b>"]
    C4 --> C7[return result]
    C6 --> C7
    style C5 fill:#dfd
    style C6 fill:#dfd
  end

Loading

Fix

In Lookup.GetItems (src/Build/BackEnd/Components/RequestBuilder/Lookup.cs):

1. Compute total allRemoves count (cheap — sum the list-of-lists sizes).
2. If above a small threshold (> 8), build a HashSet<ProjectItemInstance> populated with all removes. Use removeSet.Contains(item) instead of ShouldRemoveItem when filtering groupFound and allAdds.
3. Below the threshold, fall through to the original linear scan — for tiny remove sets the HashSet allocation/hashing cost outweighs the win.

Why reference-equality semantics are preserved

• ProjectItemInstance does not override Equals/GetHashCode, so HashSet<ProjectItemInstance> with the default comparer keys by reference.
• The actual matching condition in the existing ShouldRemoveItem is itemAsTaskItem == removeAsTaskItem (reference equality on an interface with no == overload). The preceding EvaluatedIncludeEscaped length + ordinal checks are early-out false filters; they cannot promote a value-equal-but-reference-different pair to a match.
• The pre-Perf: Reimplement Lookup.Scope tables without ItemDictionary #12320 ItemDictionary keyed its _nodes by Dictionary<T, LinkedListNode<T>> — also default reference equality on ProjectItemInstance. So this fix restores the historical behavior, not changes it. There is a regression test (GetItems_RemoveUsesReferenceEquality_NotValueEquality) asserting this contract.

Evidence

A new BenchmarkDotNet benchmark MSBuild.Benchmarks.LookupGetItemsBenchmark models the QtMsBuild-style workload: a base scope with N items of one type, plus M small batches of removes, calling GetItems after each batch. Two scenarios:

• SingleScope — removes accumulate in one scope's PrimaryRemoveTable (worst case for the regression).
• MergedSubScopes — each batch enters a child scope, removes, calls GetItems, then leaves; subsequent calls see remove lists from multiple scope levels (representative of how batched intrinsic-task removes accumulate during a real build).

Measured on .NET 10, Windows 11 (Hyper-V), --job short, parameters BaseItemCount=2000, RemoveBatchCount=100, RemoveBatchSize=10:

Method	Before (broken)	After (fix)	Speedup	Allocations before → after
SingleScope	456.9 ms	5.2 ms	~87×	1.58 MB → 2.65 MB
MergedSubScopes	273.6 ms	3.3 ms	~83×	2.41 MB → 3.48 MB

Allocations rise modestly (per-call HashSet allocation), but the CPU win dominates by orders of magnitude. The speedup grows multiplicatively with N × M — at N=5000, M=200 the broken code took ~5 s per op while the fix completes in ~27 ms (~180×), confirming the regression was quadratic.

To reproduce:

cd src/MSBuild.Benchmarks
dotnet run -c Release -f net10.0 -- --filter "*LookupGetItemsBenchmark*" --job short

Tests

All assertions use Shouldly per tests.instructions.md.

• GetItemsAfterManyBatchedRemoves_ReturnsCorrectItems — 200 base items, 50 batches of 4 removes; asserts exact remaining membership (exercises HashSet path on groupFound).
• GetItems_LinearAndHashSetPathsAgree([8], [9]) — boundary Theory proving both code paths produce identical results across the threshold.
• GetItems_RemoveUsesReferenceEquality_NotValueEquality — 30 distinct ProjectItemInstance references all sharing the same EvaluatedInclude; removing 10 leaves exactly the other 20. Pins the reference-identity contract.
• GetItemsAfterMergedSubScopeRemoves_ReturnsCorrectItems — multi-scope variant: 20 child scopes each contributing 3 removes via merge; verifies correctness when allRemoves contains multiple lists.
• GetItems_RemovesNotInGroup_AreNoOps — 30 base items + 20 phantom removes that don't match anything; asserts all 30 originals survive.
• GetItems_RemoveSubsetOfAdds_ReturnsRemainingAdds — empty base, 20 AddNewItem calls, 15 reference-equal removes; asserts the HashSet branch on allAdds keeps exactly the 5 unremoved adds.
• All 28 pre-existing Lookup_Tests, plus 154 IntrinsicTask_Tests and BatchingEngine_Tests, continue to pass. New count: 35 in Lookup_Tests.

Scope notes

• Out of scope (filed as follow-up consideration): Lookup.MergeScopeIntoNotLastScope no longer dedups removes when merging up — it just ImportItems the list ("for perf, deferring until used" per its comment). That can inflate M over time. The fix in this PR makes GetItems tolerate inflated M cheaply (HashSet dedups for free during construction), so this is now an allocation/footprint concern, not an asymptotic-CPU concern. Worth a separate follow-up if there's evidence it matters in practice.
• No InternalsVisibleTo expansion to test code: just to the existing MSBuild.Benchmarks project (uses the same Microsoft strong-name public key as Microsoft.NET.StringTools.Benchmark already does for StringTools).
• No public API change, no targets change, no behavioral change visible to project files.

Backport candidates

Servicing branches that contain PR #12320 and would benefit:

• vs18.3, vs18.4, vs18.5, vs18.6, vs18.7

Suggested after this lands in main.

---

Fixes performance regression introduced by #12320.

[JanProvaznik]

Round 1 of multi-agent review addressed in commit 13e0265:

From the expert reviewer (expert-reviewer):

• ✅ MUST: Convert new tests to Shouldly per tests.instructions.md. Done — Assert.Equal/Contains/DoesNotContain → ShouldBe/ShouldContain/ShouldNotContain, plus using Shouldly;.
• ✅ SHOULD: Add no-op-removes test. New GetItems_RemovesNotInGroup_AreNoOps builds 30 base items, then removes 20 phantom ProjectItemInstance references that were never added to the table; asserts all 30 originals survive. Exercises HashSet path with zero-effect removes.
• ✅ SHOULD: Add adds-path test. Existing tests only exercised the HashSet branch over groupFound. New GetItems_RemoveSubsetOfAdds_ReturnsRemainingAdds uses an empty base table, adds 20 items via AddNewItem, then removes 15 of them and asserts exactly the 5 unremoved adds remain — pinning the HashSet branch over allAdds.
• 🟡 SHOULD: Follow-up issue for MergeScopeIntoNotLastScope dedup, with a backlink in this PR. I'll file that separately and edit the PR body to link it once it has a number; deliberately keeping it out of this PR to keep the servicing-backport surface minimal and focused.
• 🟢 NIT items (wasted alloc when no source to filter; threshold sweep in benchmark; dedupe filter loop into a local function): deliberately skipped to keep the diff surgical for backport. Easy to revisit in a follow-up if servicing risk is acceptable.

Test count is now 35/35 in Lookup_Tests (28 pre-existing + 7 new test methods).

From the diff-only reviewer (code-review):

• 🚫 False positive on the central correctness claim. The reviewer asserted that HashSet<ProjectItemInstance> would use value equality because of Equals/GetHashCode overrides at lines 1703 and 1718 of ProjectItemInstance.cs. Those overrides are inside the nested internal sealed class TaskItem (line 781), which is a separate class — ProjectItemInstance holds a TaskItem by composition (private TaskItem _taskItem;, line 60). ProjectItemInstance itself overrides only ToString (line 445), so EqualityComparer<ProjectItemInstance>.Default resolves to reference equality, exactly as the fix requires.

  Empirical confirmation: GetItems_RemoveUsesReferenceEquality_NotValueEquality constructs 30 distinct ProjectItemInstance objects all with the same EvaluatedInclude and removes only the first 10 by reference. With value equality those 30 would collapse to one and removing one would remove all; the test passes (asserts exactly 20 remain), confirming reference equality is in effect.

  No code change needed for that finding.

Will hold the draft until the follow-up issue exists and is linked.