Incremental Dependency-Graph Recalculation for 184 Excel Formulas in a Browser Web Worker

Spreadsheets struggle to maintain smooth performance when implemented directly in JavaScript. Editing a single cell in a massive spreadsheet triggers reevaluation of every formula on the main thread, causing frame drops and frozen keyboard navigation. To address this issue, Arte Sheets— a browser-based spreadsheet supporting 184 Excel-compatible functions, dynamic arrays, Pivot Tables, and various file import/export formats— moved formula evaluation and file conversion into separate Web Workers.

However, simply moving work off the main thread is not enough; the worker must still recompute all 10,000 formulas on every keystroke, leading to long queues of outdated worker messages.

The authors designed a hybrid incremental precedent-closure and dynamic-spill fallback engine to tackle this challenge within a mere 60 lines of worker coordination code. Problem 1: Textbook spreadsheet tutorials assume cell dependencies form a static Directed Acyclic Graph (DAG). However, real-world .xlsx workbooks break these static DAG assumptions in three ways: volatile and dynamic-reference functions, dynamic array spills, and structural mutations.

These complexities make it challenging to handle OFFSET and FILTER spills inside an incremental single-cell walker, as they can introduce stale-cache bugs. Conversely, falling back to full recalculation for every workbook makes simple financial sheets feel sluggish.

Problem 2: To efficiently split safe incremental edits from spill/volatile passes, the calculation worker classifies every formula cell during upsert using a fast regex check for volatile and dynamic-spill functions. These functions are tracked in an unsafe set alongside sheet spillOwners. When an edit message arrives from the UI coordinator, the worker decides in O(1) whether to execute a full topological pass or a targeted incremental closure.

The nextLayout variable contains information about the current workbook state, and needsFullPass checks if a full recalculation is required based on various conditions like workbook reset, workbook ID changes, layout differences, and unsafe set size.

Problem 3: For the common case where workbooks contain functions like SUM, XLOOKUP, INDEX/MATCH, SUMIFS, IFERROR, PMT, and standard arithmetic, needsFullPass remains false. Instead of evaluating dependents immediately as they are discovered (which risks reading half-updated intermediate cells in diamond dependencies), the authors first close the transitive dirty set across recorded range precedents before evaluation.

This ensures that chains of dependent cells see fresh values. The code iterates through a list of range points, checking each dependent formula's range against recorded precedents. If a hit is found, the calculation process continues with updated values.