Skip to content

recalc: cache seed_spill_sensitive's full derived seed set (Design B, deferred from #991) #993

Description

@hhimanshu

Context

Issue #991's investigation identified two O(formula-cell-count) fixed costs in
Workbook::recalc_incremental_measured. The first (snapshot_formula_values)
was fixed in full. The second (seed_spill_sensitive) breaks into two parts:

This issue tracks (b): a full "Design B" that caches the entire derived seed
set
seed_spill_sensitive produces (not just the AuthoredCellIndex it
consults), invalidated on a schedule wide enough to cover every way that
derived set can go stale — which is a materially larger set of triggers than
the graph cache's or the spill-anchor cache's own invalidation schedules,
since it depends on the combination of the dependency graph, the current
spill-rectangle map, and the authored-cell set all at once.

Why this was deferred rather than built alongside #991

Quoting the design investigation directly, since these caveats are exactly
why this needs its own dedicated review cycle rather than being rushed into
#991:

I am less confident in Design B than in Design A... a strictly bigger
correctness surface than #983 or #984... a missed invalidation is a wrong
answer, not a slow one... I'd want the property/differential suites run at
a raised seed budget before believing it.

The #991 PR implemented only the narrower, safer fallback — caching just the
AuthoredCellIndex build — explicitly because it is "a much narrower and
more obviously-correct condition... maybe half the win for a fraction of the
risk," in the same design investigation's own words.

Measured context

On incremental_recalc/row_totals_volatile_seed (clone-cost subtracted), the
#991 fallback alone showed a negligible wall-clock improvement on that
specific fixture: the dominant remaining cost there is exactly this
O(formula cells × precedents) sweep (b), not the AuthoredCellIndex build
(a) the #991 fallback targets. A fix here would need to address that sweep
directly — this issue is the place to design and justify one.

Ask

Investigate whether seed_spill_sensitive's full result set can be safely
cached and reused across incremental recalc calls, with an invalidation
schedule proven correct against:

Before implementing, run the property/differential suites (recalc_differential_tests.rs,
recalc_incremental_property_tests.rs) at a raised seed budget
(TRUECALC_DIFF_SEEDS=10000 or higher) against the proposed invalidation
schedule specifically, since a missed invalidation here is a silently wrong
answer, not merely a missed optimization.

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

Labels

No labels
No labels

Type

No type

Projects

No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions