#2596·knockout

Massive performance problem with dependencies.

Author: gschadowCreated Jul 6, 2022Updated Dec 1, 2023

I have made a demo spreadsheet application with knockout to find out (a) how easy it is and (b) how well ko handles huge arrays of data with lots of dependencies. The result is that it's horribly slow for something that is certainly a stress-test, but Google sheets handles that with grace in 10,000 cells and more, while ko croaks in a table of only 400 cells. I first started this on stackoverflow here: https://stackoverflow.com/questions/72873850/any-way-to-make-knockout-faster-or-is-data-binding-fundamentally-flawed but then discussion ensued here which fired up my determination to prove absence of user error on my part, ultimately I created a subcribable, observable, and computed implementation with straight-forward dependency detection and propagation with objective measurements showing that knockout's is thousands-fold slower, behaves in O(e^n) time, while mine, does O(n^2). You can fast-forward to the head on comparison here below https://github.com/knockout/knockout/issues/2596#issuecomment-1177770646 which also simmered down the code to just what matters.


By profiling I determined that the most time is spent here:

evaluateImmediate_CallReadWithDependencyDetection: function (notifyChange) {
    window.cccnt = (window.cccnt||0)+1;

so I added this counter cccnt, and I could in a 20 x 20 table after filling it with the formula, go to J10 and add " + 1" to the formula there, something that changes the result value ( " * 1" does not).

Now here is the counts.

  1. on first initialization: 5,453
  2. after filling with the formulas: 10,387 - 5,453 = 4,934 difference
  3. when updating the formula in J10: 1,422,465 - 10,387 = 1,412,078

That's 1.4 million times evaluating for just 400 formulas (actually, in the J10 update it only affects 100 cells! This is definitely not right. When I put similar counters into my write and read functions, I get 420 writes after the whole test, which is good, but before the formula update in J10 I have read run 837 and after the update I have 706,268.

So this is clearly wrong and optimizable somehow. Since we have the dependencies once we should run the updates cascading them down one way J10 updates, the 2 immediately dependent cells are K10 and J11, so they update. Then their dependents, and so on which means only 100 cells should update. But somehow it runs amok here.

I am not sure how to start attacking this problem, but I have some optimism that it could be done. That it is actually a bug of some sort.