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

#performance #architecture #javascript #webdev

Spreadsheet UIs fail a simple latency test when built naively in JavaScript: the moment a user edits cell B4 in a 25,000-cell .xlsx model, evaluating every formula on the main thread drops frames and freezes keyboard navigation.

When building Arte Sheets—a local-first browser spreadsheet supporting 184 Excel-compatible functions, dynamic arrays, Pivot Tables, and .xlsx / .ods / .csv / .tsv import/export without requiring an account—we moved formula evaluation and file conversion into dedicated Web Workers.

Moving work off the main thread is only half the fix. If the worker still recalculates all 10,000 formulas on every keystroke, rapid edits queue up behind stale worker messages. Here is how we designed a hybrid incremental precedent-closure + dynamic-spill fallback engine in under 60 lines of worker coordination code.

Problem 1: Why Pure Topological DAGs Break on Real Spreadsheets

In textbook spreadsheet tutorials, cell dependencies form a static Directed Acyclic Graph (DAG):

C2 = A2 * B2 depends statically on A2 and B2.
Edit A2, walk outgoing edges from A2, recalculate C2, done.

Real-world .xlsx workbooks immediately break static DAG assumptions in three ways:

Volatile & Dynamic-Reference Functions: INDIRECT(), OFFSET(), NOW(), TODAY(), RAND(), and RANDBETWEEN() either change their target coordinates at runtime or mutate without any cell edit.
Dynamic Array Spills: Modern Excel functions like FILTER(), UNIQUE(), SORT(), SORTBY(), SEQUENCE(), and TRANSPOSE() write output into neighboring empty cells (spill regions) whose dimensions depend on runtime data values.
Structural Mutations: Renaming a sheet, changing merged regions, or updating named ranges invalidates range resolution globally.

If you try to handle OFFSET and FILTER spills inside an incremental single-cell walker, subtle stale-cache bugs creep in. Conversely, if you fall back to full recalculation for every workbook, simple financial sheets feel sluggish.

Problem 2: Splitting Safe Incremental Edits from Spill/Volatile Passes

Inside our calculation worker, we classify every formula cell on upsert using a fast regex check for volatile and dynamic-spill functions, tracking them in an unsafe set alongside sheet spillOwners:

const DYNAMIC_OR_VOLATILE =
  /\b(INDIRECT|OFFSET|NOW|TODAY|RAND|RANDBETWEEN|SEQUENCE|FILTER|UNIQUE|SORT|SORTBY|TRANSPOSE|RANDARRAY)\s*\(/i;

// During cell upsert in the worker:
const isFormula = typeof cell.raw === 'string' && cell.raw.startsWith('=');
const identity = `${sheet.id}!${key}`;

if (isFormula && DYNAMIC_OR_VOLATILE.test(cell.raw)) {
  unsafe.add(identity);
} else {
  unsafe.delete(identity);
}

When an edit message arrives from the UI coordinator, the worker decides in O(1) whether it must run a full topological pass or can execute a targeted incremental closure:

const nextLayout = JSON.stringify([
  data.sheets.map(s => [s.id, s.name, s.mergedRegions]),
  data.namedRanges,
  data.locale,
  data.currency,
]);

const needsFullPass =
  !store ||
  data.reset ||
  store.workbookId !== data.workbookId ||
  layout !== nextLayout ||
  unsafe.size > 0 ||
  store.sheets.some(s => s.spillOwners.size > 0);

Problem 3: Closing the Precedent Graph Before Evaluation

For the common case—workbooks filled with SUM, XLOOKUP, INDEX/MATCH, SUMIFS, IFERROR, PMT, and standard arithmetic—needsFullPass is false.

Instead of evaluating dependents immediately as we discover them (which risks reading half-updated intermediate cells in diamond dependencies like A1 -> B1, C1 -> D1), we first close the transitive dirty set across recorded range precedents [r1..r2, c1..c2], and then evaluate dirty formulas cleanly:

// Close the dependency graph before evaluation so chains see fresh values.
for (let i = 0; i < points.length; i++) {
  const [sheetName, key] = points[i];
  const [r, c] = key.split(',').map(Number);

  for (const [dependent, ranges] of store.precedents) {
    if (dirty.has(dependent)) continue;

    const hitsRange = ranges.some(
      x => x.sheetName === sheetName &&
           r >= x.r1 && r <= x.r2 &&
           c >= x.c1 && c <= x.c2
    );

    if (hitsRange) {
      dirty.add(dependent);
      const sep = dependent.lastIndexOf('!');
      points.push([dependent.slice(0, sep), dependent.slice(sep + 1)]);
    }
  }
}

And if a newly edited formula introduces a dynamic spill mid-evaluation, store._needsPass flips to true, seamlessly escalating to store.recalculateAllSync() before posting the delta payload back to the main thread.

Minimal Worker Payloads: Ship Only Formula Outputs, Not Whole Grids

Posting an entire WorkbookStore back across postMessage via structured cloning can easily serialize megabytes of formatting metadata on every edit. Instead, the worker returns a compact patch containing only:

id: monotonic request ID so the UI coordinator ignores superseded calculations
evaluated: exact count of cells recomputed (great for live telemetry & regression tests)
values: [cellKey, computedValue] tuples strictly for formula cells
spill & spillOwners: active dynamic array regions

Browser Spreadsheet Trade-Offs: Cloud SaaS vs. Local-First Worker Engine

Designing around Web Workers, IndexedDB, and an offline Service Worker changes the operational profile compared to cloud-only spreadsheets:

Capability	Cloud-First Browser Sheets	Desktop Suite Install	Arte Sheets (`sheets.arte-soft.com`)
Time to First Edit	Requires account login & cloud doc creation	Multi-GB desktop install + license	Instant in browser, zero sign-up required
Formula Execution	Remote server + client hybrid	Native local threads	Dedicated Web Worker (184 Excel functions + spills)
File I/O (`.xlsx`, `.ods`, `.csv`)	Uploads file to vendor cloud first	Local disk	Local worker parsing + `IndexedDB` persistence
Offline Availability	Requires browser extension / sync setup	Full offline	Built-in Service Worker offline caching
Optional Cloud Sync	Mandatory vendor storage	Vendor cloud drive	Optional EU (Germany) cloud sync on Pro

Key Takeaways for Heavy Browser Apps

Separate file parsing and formula calculation into independent workers. Importing a multi-sheet .xlsx archive shouldn't block UI scrolling or incremental cell edits.
Be honest about dynamic dependencies. Fast-path static range precedents (SUMIFS, XLOOKUP), and explicitly gate volatile/spill functions (INDIRECT, OFFSET, FILTER) into full-pass verification rather than risking silent stale values.
Return compact value diffs over postMessage. Keep cell style trees and DOM layout state on the main thread; let the worker own pure values and precedent ranges.

You can test the live worker engine directly in your browser (no sign-up) at sheets.arte-soft.com, or browse detailed formula and workflow comparisons against Excel, Google Sheets, LibreOffice Calc, and Numbers at sheets.arte-soft.com/compare/.

DEV Community