Prototypes CellsP33 · Spreadsheet engine

Recalculation

A sheet of a hundred thousand cells is built in a Web Worker: ten thousand rows of inputs, running totals that chain down the whole sheet, lookups, conditions and sums over ranges. Changing an input recalculates only the cells that read it, directly or through others, in an order where each cell comes after the cells it reads. The same change is then recalculated the slow way, every formula on the sheet, to compare.

Building. The sheet is being built in the worker.

Change one input

ChangeReachable cellsRecalculatedTimeEverything againFaster bySame values

How Cells is built
  1. Cells is a spreadsheet with its own formula engine, written for this prototype in plain JavaScript with no dependencies. The grid is drawn on a canvas, only the cells in view, so a sheet of a million rows scrolls as fast as a small one.
  2. A formula is read by a tokenizer and a parser with Excel’s precedence: the range, intersection and union operators first, then the minus sign of a number (so -2^2 is 4), percent, powers, multiplication, addition, joining text and comparison. A reference keeps the cells it points at and which of its parts are absolute (written with a $), so a copied formula moves only its relative parts, and a parse error names the place it went wrong.
  3. Values work as LibreOffice works them for an XLSX file: TRUE and FALSE are the numbers 1 and 0 with a logical format, a text in arithmetic is read by the number scanner of en-US, and two numbers that agree to about 15 digits are equal, so 0.1 plus 0.2 minus 0.3 is 0. Dates are days counted from 30 December 1899.
  4. Every formula cell registers the cells and ranges it reads in a dependency graph. Ranges are stored in an index of blocks of 64 rows by 16 columns, so a change inside a big range finds its formulas without looking at every formula. A change marks every cell it reaches, sorts them so each comes after the cells it reads, and works out only those. OFFSET, INDIRECT and RAND are volatile and run on every change. A circular reference is found by its strongly connected cells, and each of them shows #CIRC!.
  5. A formula that gives an array spills it into the cells below and to the right, as a dynamic array does, and shows #SPILL! when a cell is in the way. Inserting or deleting rows and columns rewrites every formula in the workbook, and a reference to a deleted cell becomes #REF!. Cut and paste moves the cells and keeps every reference to them pointing at them.
  6. XLSX files are read and written with Cells’ own zip and XML code: shared strings, number formats, several sheets, defined names, and formulas with their cached values. A formula that gives an array is written as an array formula over the range it spills into.
  7. The judge: a corpus of workbooks in 14 families and a fuzzer that writes formulas from a seed. Each workbook is written as XLSX by Cells, with no cached values and one wrong value on purpose, LibreOffice works it out in a profile of its own and saves it, and Cells reads LibreOffice’s values back. Every cell must agree to 15 significant digits, the precision LibreOffice writes.
  8. To agree to the last digit, Cells does the arithmetic the way LibreOffice’s build does: sums by Kahan and Neumaier in LibreOffice’s order, its rounding with 15 significant digits, a correctly rounded power, and the fused multiply-adds its compiler makes in RATE, the variance and the time value of money.