Solver: add `been_intersected_with` / `been_reduced_by` dedup caches

[doubleailes]

Background

Audit against rez/src/rez/SOLVER.md flagged that rer's PackageVariantSlice is missing two per-slice caches that rez uses to skip redundant work:

• been_intersected_with — records ranges a slice has already been intersected with; `intersect()` short-circuits if the incoming range is already covered.
• been_reduced_by — records package requests a slice has already been reduced by; `reduce_by()` short-circuits on repeats.

In rez these are part of the "optimised mode" path on `_PackageVariantSlice` (`rez/src/rez/solver.py:566+`).

Impact

• Correctness: none. rer redoes work that rez would skip, but the result is identical. This is consistent with rer matching rez 1:1 on the 188-case benchmark.
• Performance: rer is already faster than rez on the benchmark (~44s vs ~206s), so there's no urgency, but the headroom is real — the redundant intersect/reduce work shows up in the hot loop.

What to do

1. Add two fields to `PackageVariantSlice` (`crates/rer-resolver/src/rez_solver/variant.rs:476-493`):
   • `been_intersected_with: FxHashSet` (or equivalent)
   • `been_reduced_by: FxHashSet` (or equivalent)
2. In `intersect()` (`variant.rs:588-606`): if the incoming range is in `been_intersected_with`, return `Unchanged`.
3. In `reduce_by()` (`variant.rs:609-674`): if the incoming request is in `been_reduced_by`, return `Unchanged`.
4. Decide on cache cloning behaviour: rez keeps the cache when entries are unchanged, drops it on `copy_with_entries`. Match that.
5. Re-run the rez benchmark and report timing delta.

References

• rer slice: `crates/rer-resolver/src/rez_solver/variant.rs:476-493`
• rez slice: `rez/src/rez/solver.py:566+`
• SOLVER.md mentions these as part of the "immutability optimization" pattern (~line 158)

[doubleailes]

Implemented and benchmarked. The optimisation does not translate from Python to Rust — every variant attempted is at best neutral and at worst a 2–3× regression. Closing as wontfix.

What I did

1. Added been_intersected_with: RefCell<FxHashSet<VersionRange>> and been_reduced_by: RefCell<FxHashSet<Requirement>> to PackageVariantSlice, with early-return cache hits in intersect/reduce_by and cache propagation in copy_with_entries (mirroring rez's _copy at solver.py:861-869).
2. Instrumented call/hit counters and ran the 188-case benchmark.
3. Tried a "cheap key" variant: memoised the Hash output on VersionRange via OnceCell<u64>, so per-call lookup drops from segment-walk to cell read.
4. Tried each cache independently to isolate the cost.

Measurements (rez benchmark, 188 cases, release mode, same machine)

Variant	Total	Mean	Δ vs baseline
Baseline (main)	43.0 s	230 ms	—
derive(Hash) + intersect cache only	44.1 s	235 ms	+2.6 %
derive(Hash) + both caches	86.3 s	459 ms	+101 %
Memoised hash + both caches	132.1 s	703 ms	+207 %
Memoised hash + intersect cache only	46.1 s	245 ms	+7.2 %

188/188 correctness preserved in every variant.

Hit-rate instrumentation tells the story

Op	Calls	Hits	Hit rate
intersect	288,729	206,211	71.4 %
reduce_by	26,980,353	78,368	0.29 %

• reduce_by is called ~27 million times. The cache lookup fires on every one of those, but lands only 0.3% of the time. We pay the per-call hash cost on 26.9M misses to save work on 78k hits.
• intersect hits land 71% of the time, but the work being skipped (a tight entries.iter().filter on Rc-shared entries with range.contains per entry) is so cheap that the savings approximately equal the lookup cost. Even with a 71% hit rate the cache is within noise of baseline.
• Memoising the hash makes the lookup theoretically O(1) but adds an OnceCell<u64> field to every VersionRange clone (and ranges are cloned a lot in intersect/union/from_versions/etc.). That per-clone overhead exceeds the cache savings.

Root cause

rez's optimisation pays off because Python's per-call overhead (function dispatch, list iteration, attribute lookup) makes redoing intersect/reduce work expensive relative to a hash-set lookup. In rer the relationship is inverted: the entries-filter loop is a tight Rust pointer/range op, and hashing a VersionRange walks all its segments. The cache check costs more than the work it would skip. There is no variant where the cost ratio swings back the other way for this workload.

Recommendation

Closing this issue. Audit doc PR #62 / commit summary should be updated to remove this as a "potential perf win" — the data shows it's not.