Recalculation algorithm

Overview

The current recalculation algorithm consists of marking cells and their dependents dirty based on volatility and changed cells, and then iteratively enqueueing dirty cells onto a queue in an order respecting their static dependencies, calculating each cell’s value in order off the front of the queue, correcting the queue order as dynamic dependencies are discovered by cell evaluation, and detecting and handling circular dependencies.

This algorithm guarantees that:

• a cell does not get recalculated unless its formula is (a) volatile, (b) depends in some way on a volatile cell, or (c) depends in some way on a cell whose value changed since the last recalculation — and in case (c), only if a change actually propagates all the way to it: if every dependency path to the cell contains some cell whose value came out unchanged, the cell’s formula is not re-evaluated
• all cell values potentially impacted by (a) cell value changes since the last recalculation, and (b) volatile cell values, will get recalculated, taking the up-to-date values of their dependencies correctly into account
• in the main pass, no cell value is updated more than once (but formulas containing dynamic dependencies may be partially evaluated more than once); cells involved in circular dependencies or what-if data tables can be evaluated repeatedly in the follow-up phases described below
• the order in which cell values are updated is a topological ordering of all cells by all cell-to-cell dependencies, static and dynamic

Definitions

Static dependency: a cell A depends statically on cell B if A has a formula which references B directly, by defined name or A1 address

Dynamic dependency: a cell A depends dynamically on cell B if A has a formula which does not reference B directly (or does so only in the first parameter of an OFFSET function call) but which contains a call to a reference-valued function (OFFSET, INDIRECT or ANCHORARRAY) which at evaluation time resolves to the address of cell B or a range containing it.

Indirect dependency: a cell A depends indirectly on cell B if there exists a path of (direct, i.e. cell-to-cell) dependencies from A to B.

Indirect static dependency: an indirect dependency in which every dependency in the path is static.

Circular dependency or Dependency cycle: a cell A depends circularly on itself if there exists a path of dependencies from it that leads back to it.

Static circular dependency: a circular dependency in which every dependency along the path is static

Dynamic circular dependency: a circular dependency in which one or more dependencies along the path are dynamic

Changed cell: a cell whose value or formula has changed since the last recalculation — by a direct edit, or as part of a larger operation such as a cell move, a row/column insert or delete rewriting formulas, or the application of a value snapshot.

Algorithm design and implementation

In each cell we track the cell recalculation state, which is one of UPTODATE, DIRTY, ENQUEUEING, ENQUEUED_MAYBE, ENQUEUED_CALC and NEWLY_UPTODATE. On initialization, and after each recalculation, all cells are in state UPTODATE.

Recalculation proceeds in two phases: the mark phase and the evaluation phase.

Mark phase

Set state to DIRTY on each cell that either

1. has a direct or indirect static dependency on a changed cell
2. or is volatile, or depends directly or indirectly on a volatile cell

Notes:

• the “direct or indirect” here means the DIRTY state is propagated along static dependency relationships to every cell that has an indirect static dependency on a volatile cell or a changed cell. This is done by recursing on the “incoming” graph edges of each cell, to the direct dependents of that cell. (Dependencies on ranges are stored in the dependency graph as range nodes, kept in per-sheet R-trees so that the range nodes overlapping a given cell can be looked up efficiently.)
• dynamic dependency relationships are not fully known until evaluation time, but they are approximated ahead of it:
  • when a formula’s dependencies are analyzed, each OFFSET/INDIRECT/ANCHORARRAY call is, where feasible, evaluated against the current state of the model, and the resulting reference is recorded in the dependency graph as a dynamic edge
  • each time such a cell’s formula is evaluated in a recalculation, the dynamic dependencies actually used are re-recorded, replacing the previously recorded ones
  • the DIRTY state is propagated along these recorded dynamic edges, just like static ones. The recorded edges reflect the previous evaluation, so they may prove wrong when the cell is next evaluated; the evaluation-time discovery described below remains the backstop that corrects the evaluation order in that case.
  • only when dependency analysis cannot determine any bound on the set of possible dependencies of a formula is the cell marked volatile, so that it is always enqueued and evaluated, and its dynamic dependencies get discovered in the evaluation phase, see below.
• a cell whose value was set by an edit is never itself marked DIRTY, and if it had a formula, the value edit cleared the formula; thus the cell is not volatile even if that formula had a volatile function call. Thus, dependency relationships will never cause the edited value to be overwritten by recalculation, as the cell will never be enqueued for evaluation (see below). A cell whose formula was edited is a different matter: it is itself enqueued for evaluation in the evaluation phase.

Evaluation phase

Maintain a queue, which is initially populated by invoking the enqueueCellPrecededByDirtyDependencies operation (see below) on:

(a) each cell whose formula was edited since the last recalculation.

(b) each direct dependent of a cell whose value was changed by an edit.

(c) each volatile cell.

Cells are enqueued in one of two states:

• ENQUEUED_CALC: the cell is known to require recomputation, because some direct dependency of it has changed (or it is itself a recalculation root).
• ENQUEUED_MAYBE: the cell was enqueued only to ensure correct evaluation order, as a dirty dependency of some other cell being enqueued, but no direct dependency of it has been observed to change.

Process the queue in order. For each cell taken off the front of the queue:

• if it is in state ENQUEUED_MAYBE, mark it up-to-date without evaluating it. This is safe in the ordinary case because all its dirty dependencies were enqueued ahead of it, so if any of them had changed value, this cell would have been promoted to ENQUEUED_CALC by the propagation described next. Growing spill ranges are an exception: they can force a cell back from newly up-to-date to dirty so the expanded spill area is reconciled.
• if it is in state ENQUEUED_CALC, evaluate its formula, set its value to the result, and mark it UPTODATE. Then, if its value changed, propagate: promote any already-enqueued direct static dependents from ENQUEUED_MAYBE to ENQUEUED_CALC, and invoke the enqueueCellPrecededByDirtyDependencies operation (see below) on any DIRTY cells that statically depend directly on it.

This constitutes a topological sort of the static dependency graph: a breadth-first traversal of static dependent relationships, at each layer propagating recalculation to all direct static dependents of any cells already updated. And the ENQUEUED_MAYBE handling prunes the work: a cell’s formula is only re-evaluated if a change actually propagates to the cell along some dependency path.

The enqueueCellPrecededByDirtyDependencies operation on a cell C consists of:

1. putting C in state ENQUEUEING,
2. invoking enqueueCellPrecededByDirtyDependencies recursively on each of C’s DIRTY direct dependencies
3. if C is still in state ENQUEUEING, put it in state ENQUEUED_CALC (if some direct dependency of C is already known to have updated in this recalculation, or C is the cell the operation was started on) or ENQUEUED_MAYBE (otherwise), and append it to the back of the queue.

The state ENQUEUEING is only ever used during this operation on a particular cell — so if the recursion encounters a cell that is already in state ENQUEUEING, then a static circular reference has been detected. If iterative calculation is enabled, the cells of the cycle are handed off to the iterative calculation phase. Otherwise it is treated the way Excel does: leave the cell’s existing value if it has one, else set it to 0 (for a sheet cell; a defined name gets a #NAME? error instead), and either way mark the cell UPTODATE. (See more about circular dependency handling in a subsection below.)

The evaluation order resulting from the above is a breadth-first traversal of the static dependency graph. Only the static dependencies determine the order in which cells are placed onto the queue, (a) initially, and (b) at the end of processing each cell off the front of the queue.

That leaves dynamic dependencies, which are handled as follows.

A dynamic dependency is discovered upon evaluating a formula containing a “dynamic-reference” function: one that produces a cell/range reference based on its parameters. Those parameters themselves can be the results of formula evaluation, so the resulting dependency (edge in the dependency graph) cannot be known for certain until evaluation time. These functions are OFFSET, INDIRECT and ANCHORARRAY.

These functions output a Reference object with the dynamic property set to true. When such a reference is about to be passed as an argument to another function, the cells it references are checked and if any of them is not UPTODATE, then the cell evaluation is aborted by throwing EvaluationOrderException. Control thus passes back up the stack to the evaluation queue loop, with information about the discovered dynamic dependency.

This dynamic-dependency check is not performed for arguments in reference-only positions, where the receiving function inspects the reference itself rather than the values of the cells it refers to, or itself checks up-to-dateness of just the cells it actually reads:

• the first argument of OFFSET, ROW, COLUMN, ROWS, COLUMNS and FILTER. (For OFFSET, it’s not that reference that will eventually form a dynamic dependency for this cell, but the output of the OFFSET call — unless that in turn is also passed in a reference-only position.)
• the second argument of HLOOKUP, VLOOKUP and CELL
• the third argument of LOOKUP and XLOOKUP
• any argument of INTERSECT

Additionally, the arguments of the lazy-argument functions IF, IFS, IFERROR, IFNA, CHOOSE and SWITCH are only evaluated as needed, so e.g. the THEN argument of an IF call whose condition argument evaluated as false is never evaluated at all, and thus never has this check applied to it.

An EvaluationOrderException is handled in the evaluation queue loop by injecting the discovered dependency and all its DIRTY static dependencies at the front of the queue, as follows:

1. store the existing queue contents to the side, and empty out the queue
2. enqueue each cell of the dynamic dependency range using the enqueueCellPrecededByDirtyDependencies operation
3. append the aborted cell onto the end of the queue (so its evaluation will be retried after its discovered dynamic dependency has been evaluated)
4. append onto the end of the queue all cells that were previously in the queue and did not get re-enqueued ahead of the current cell by the above.

Finally, this dynamic-dependency handling keeps a record, cellReorderings, of the queue reorderings already performed during this recalculation. A dynamic circular dependency has been discovered when reordering would just repeat itself without any progress: when a cell D would be reordered in front of a cell C which D was already reordered in front of, with no formula-cell updates having occurred in between, or when the opposite reordering was already performed. (It wasn’t discovered earlier, in the initial recursive enqueueing of DIRTY cells, because at least one of the dependencies in the chain was dynamic.) It is handled like static circular dependencies: hand the cells off to the iterative calculation phase if iterative calculation is enabled, else keep the cell value if there is one (else assign zero, or a #NAME? error for a defined name), mark the cell UPTODATE and carry on.

When the queue is empty, the main pass is complete. Two settling phases then run before the recalculation is done:

• the data-table phase: the anchor cells of what-if data tables are held back from the main pass and evaluated here, by running per-scenario sub-recalculations with input values temporarily substituted
• the iterative calculation phase, if iterative calculation is enabled (see the circular-dependency section below).

These two phases alternate until a bounded fixpoint, because data-table results can feed dependency cycles and vice versa.

The end result is that the order in which cell values have been evaluated in the main pass is a topological ordering of the full dependency graph including dynamic dependencies (filtered to the set of cells impacted by volatile and changed cells), made gradually correct by the above reordering in response to discovery of dynamic dependencies.

Notes on circular dependency handling

The “circular dependency handling”, for a given cell on which a circular dependency is detected, is:

1. set the cell value to 0 if it does not already have a value (or to a #NAME? error, if it is a defined name rather than a sheet cell)
2. set the cell state to UPTODATE
3. add a note of a circular dependency at this cell, at NOTICE level, to the workbook details (visible to authors).

Excel and Google Sheets support, and the Office Open XML spec describes, an alternative mode of dealing with circular dependencies, called “Iterative Calculation”. We support that too: each workbook’s iterative-calculation settings are read from the workbook file (or can be passed in workbook options), and the model applies a merge of the settings of all its workbooks — iterate if any workbook says to, with the largest maxIterations and the smallest maxChange (exposed as Model.iterativeCalculationSettings()). When iterative calculation is enabled, cells discovered to be part of a dependency cycle are not given the above default handling. Instead they — along with all cells depending directly or indirectly on them — are handed off to the iterative calculation phase, which runs after the main pass: it repeatedly evaluates those cells in a fixed order until an iteration’s largest cell-value change is below maxChange, or maxIterations iterations have been performed.

Any circular dependency, static or dynamic, is shared among all the cells in the circular path of dependency relationships: no one cell is more “the circular dependency cell” than the others.

But the circular dependency is encountered at exactly one cell in that circular path, and (in the default, non-iterative mode) only that cell gets the “circular dependency handling” applied to it. Which cell that is depends pretty much arbitrarily on the path along which updates propagate into the circular dependency path, and thus can depend, even for identical workbooks, on:

1. which cells have been edited (and in which order, if more than one was edited since the last recalculation, such as when applying initial state on load, or UI state on workbook refresh)
2. the order in which volatile cells get evaluated.

This arbitrariness may lead to different results between GRID, Excel and Google Sheets. Such inconsistency is hard to eliminate (or impossible, if Excel and Google Sheets themselves differ on this; we haven’t checked whether they do), and it is probably acceptable for almost all use cases, under the assumption that users rarely rely on this happening at a specific cell in the cycle.

Finally, Excel also exposes the full path of circular dependencies, presenting it visually with arrows pointing between the cells, if the path is within one worksheet. We collect the cells of each detected cycle where we can (for some dynamically discovered cycles, only part of the path is known) and include them in the circular-dependency notice in the workbook details, but nothing presents them the way Excel’s arrows do. Google Sheets does not appear to support this either.

Possible future optimizations

These are design sketches for optimizations that are not implemented; they describe potential future work, not current behaviour.

Propagate updates only along paths that lead to cells that get used

Collect the output cells, i.e. the set of cells that belong to either

• the target range of an output element in the GRID document
• or, in edit mode, the active sheet, or even just the scrolled-into-view subrange of the active sheet, in the workbook area

Determine a set of cells whose value will not have any effect on any of these cells (i.e. whose set of direct and indirect dependents has no overlap with the output cells) for the user. And then simply don’t enqueue any of those cells.

(A building block for this now exists: the caller-directed deferral mechanism — Model.cellsToDefer — makes recalculation skip the given cells and track them as stale instead, to be computed by a later recalculation that includes them. The output-cell analysis to decide which cells to defer is what remains unimplemented.)

This will particularly help for large workbooks that haven’t been pruned down to what the GRID model needs — a common case where people “try GRID out” with a workbook they already have. The workbook will still be slow to load and parse formulas and construct the static dependency graph, but recalculation can be significantly quicker if much of the model does not need to be calculated at all.

In edit mode we will need to recalculate again when the user switches the workbook area to another sheet (or scrolls in it).

We might even be able to optimize the recalculation that occurs when the set of output cells changes (at least when the edit mode workbook area is scrolled or flipped to a different sheet — maybe it doesn’t make sense when adding or retargeting output elements) by:

• starting the recalculation at just those cells that we previously didn’t enqueue because they wouldn’t be needed
• not re-evaluating volatile cells

… i.e. this could amount to just lazily evaluating cells whose value we didn’t need before (but which will evaluate exactly as they would have if we had evaluated them before, because none of them are volatile).

So this “lazy-evaluation” recalculation may be, most of the time, a pretty lightweight operation.

Two possible complications:

• workbook errors may be encountered during the lazy evaluation, which may surprise the user when scrolling the workbook area. This is likely acceptable, but means that this lazy-evaluation optimization cannot be completely hidden from the user.
• this lazy-evaluation approach may not interact well with the change-propagation pruning (described in the algorithm section above) by which a cell is only re-evaluated when a dependency’s value actually changed. At least care would need to be taken to make sure these work well together.