How to Recalculate a Spreadsheet

>The few people with the problem “my Excel spreadsheet is too slow” have already written enough Excel formulas that migration to any other platform is impossible. Fortunately, I have no understanding of business, and so we’re going to look at further improvements anyway.

That's how you know you're reading a really solid tech piece and not some blogspam!

The “Build Systems a la Carte” paper famously compares Excel with build systems such as Make and Bazel. Recalculating a spreadsheet efficiently is the same problem as compiling source code.

https://www.microsoft.com/en-us/research/uploads/prod/2018/0...

Topological sorting has many applications. I built this a couple years ago https://github.com/atlassubbed/atlas-relax.

It's a DAG-computing framework in JS that allows you to listen to updates in a compute graph. It's a set of legos that I used to build both a MobX clone (https://github.com/atlassubbed/atlas-munchlax) and a React clone (https://github.com/atlassubbed/atlas-mini-dom). React and MobX are actually the same thing mathematically: reactive DAGs, so they can both be built using the exact same abstraction.

If you're in TypeScript/JavaScript world, check out HyperFormula [1]. There's a summarized design document in the documentation that explains the AST, dependency graph, formula evaluation and lazy CRUD operations [2].

Disclaimer, I'm one of the founders.

[1] https://github.com/handsontable/hyperformula [2] https://handsontable.github.io/hyperformula/guide/key-concep...

The dependency graph is why you should always prefer INDEX over OFFSET, unless you really can't avoid it:

https://docs.microsoft.com/en-us/office/client-developer/exc...

Every instance of OFFSET in your sheet is recalculated after each cell change. I learnt that the hard way.

I found this: https://www.geeksforgeeks.org/topological-sorting/ very helpful when I was trying to figure out how to solve a toy spreadsheet I was working on. Includes a couple alternative implementations in a variety of languages.

“The issued patents are published by the patent office so you can find the whole long list of them and see exactly what they say. Of course, you couldn't actually read that whole list as there are too many of them. In the US, there are hundreds of thousands of software patents.

There is no way you can keep track of what they are all about. You would have to try to search for relevant ones. Some people say that should be easy in these modern days of computers. You could search for key words and so-on. That one works to a certain extent. You will find some patents in the area. You won't necessarily find them all however. For instance, there was a software patent which may have expired by now on natural order recalculation in spread sheets. This means basically that when you make certain cells depend upon other cells, it always recalculates everything after the things it depends on, so that after one re-calculation, everything is up to date. The first spread sheets did their recalculation top-down, so if you made a cell depend on a cell lower down, and you had a few such steps, you had to recalculate several times to get the new values to propagate upwards. You were supposed to have things depend upon cells above them. Then someone realized why don't I do the recalculation so that everything gets recalculated after the things it depends upon? This algorithm is known as topological sorting. The first reference to it I could find was in 1963. The patent covered several dozen different ways you could implement topological sorting but you wouldn't have found this patent by searching for spreadsheet. You couldn't have found it by searching for natural order or topological sort. It didn't have any of those terms in it. In fact, it was described as a method of compiling formulas into object code. When I first saw it, I thought it was the wrong patent.”

— Richard Stallman, 2002 (https://www.gnu.org/philosophy/software-patents)

While it's cool to see the CS theory used to optimize spreadsheet calculations, it also shows some important points. You can ship the first version with a poor algorithm that works. Performance improvement matters to users, but after doing what they need correctly. If you don't lead all the way to a solid solution you will be replaced by someone who does.

Topological sorting - that's a very nice idea.

In the past I've implemented dirty marking and, while fun to figure out the appropriate logic, topological sorting seems much neater.

The reactive programming model (or whatever you call it, honestly don’t know) is at the core of so many great tools and products - eg Terraform/Pulumi, Kubernetes, React, Mobx, Observable...

At the same time, we’ve struggled to find decent reference material or libraries for building a reactive framework for X (for our use case, X = data science workflows). Most of these libraries seem to implement all the primitives from scratch.

I’d be interested to here other people’s thoughts on this!

Reactive programming is a very solid paradigm. It is hard to get it right though. Especially when calculations are asynchronous. Excel is ubiquitous but is universally painful to use for anything beyond quick prototyping.

This was the major motivation for us to create

https://ellx.io

- a platform for visual reactive programming, working in your browser.

ObservableHQ was obviously an inspiration, but we concentrated on making it more production oriented: you can literally build a fully-fledged web application without leaving your browser, around solid reactive abstractions.

Some examples built with Ellx:

[1] https://ellx.io/matyunya/tensorflowjs-simple-demo

[2] https://ellx.io/matyunya/simple-voyager-clone

[3] https://ellx.io/dmaevsky/monte-carlo

React Hooks reminds me a lot of spreadsheets. Change a dependency and everything needs to be recalculated that depends on it and so on.

It's interesting to note that the improved algorithm also has a downside. With the VisiCalc algorithm, it is possible to model iterative fixpoint computations, so you could have a process that "converges" to a value, even having cycles in the computation graph. This is not true for the topological-sort based variants.

The VisiCalc story blew my mind here. It calculated everything from left to right over and over?

Around 2000 we had to make a spreadsheet in Java as an assignment in an introductory programming class. That it would be calculated in "demand-order" was such an obvious requirement it wasn't even mentioned in the assignment. This says something about what modern tools and languages does (Not that Java and Swing feels all that modern any more). Because they surely understood the problem way better than introductory programming students 20 years later.

Interesting read, thanks for sharing! I have played around with formulas for my Excel-like data table product [DataGridXL](https://datagridxl.com) for quite a while but I decided not to include the feature since it was a little more difficult to implement than I had imagined, exactly because of these update chain rules. Perhaps one day, in a v2.

Most other Javascript spreadsheet products are slow even without formulas, with a very slow DOM structure.

Does anyone know how LibreOffice Calc does this?

It is much slower than Microsoft Excel and WPS Office for complex loads [1, 2]

[1] https://github.com/amzn/computer-vision-basics-in-microsoft-...

[2] https://news.ycombinator.com/item?id=22357374

Observable works like this (for arbitrary JavaScript):

https://observablehq.com/@observablehq/how-observable-runs

Here’s the runtime source:

https://github.com/observablehq/runtime

The journalist quoted, Tracey Robnett Licklider, is the child of JCR Licklider whose vision for DARPA gave us all the toys we enjoy today. If you haven't read Mitchell Waldrop's "The Dream Machine" then you should remedy that. It's a great read and a hell of a story, and suddenly all the names of computing history will fit into a picture.

Interesting. I've never seen salsa available by weight, only by volume. I'd like the spicy salsa please, yes the 50 gram - pesado y picante.

To be honest you lost me at the end with the burrito code, I was left wondering why we have burrito code in our spreadsheet calcs.

I've always thought that these "dependency"-driven recalculations was akin to functional programming paradigms. Or am I misunderstanding functional?

This was a fantastic deep dive, and it made me think about things I had not thought about in a very long time, as well as some things that were entirely new to me.

Bravo.

This was quite fun, this type of problem solving deserves more attention in the business world.

so basically a DAG

Or you could just use alteryx