Dependency graph and timing (take two)

Help
1

In my first attempt to ask this question I demonstrated my lack of understanding of Mutables, but didn’t really get at the underlying issue I was trying to understand. So here goes another try…

tldr: Why doesn’t the visualization get called when the simulation takes longer than the interval between updates?

I have a control variable con that gets updated via the view input event mechanism at an interval controlled by the user using a slider. The control variable is then consumed by a simulation sim that takes a long time to update (in real cases due to lots of compute, but here with a delay of 50 ms). (The simulation is maintained in a Mutable that I hope I am now using correctly!) The simulation is then consumed by a visualization viz that displays the current state of the simulation.

If the interval between control updates is longer than the time it takes for the simulation to actually update, then everything works fine. But if the interval between control updates is shorter than the time for the simulation to update, the visualization no longer gets called.

I understand that the next update to con is occurring before viz gets called in the current update, but I thought that the computation would get pushed through the whole dependency graph before the next update would be “allowed” to begin.

You can try this for yourself in this notebook. First, Start the updates. You will see the visualization updating with each update of the simulation. Now try lowering the interval between updates with the slider. When the interval drops below 50 ms, the updates to the visualization become intermittent and then cease entirely. You can Stop the updates, and Reset the simulation so you can experiment around with it.

https://observablehq.com/d/82cee29f690254db

2

The problem is that by the time the sim value resolves, it’s already been invalidated (made stale) because the upstream variable con has changed. That means anything downstream of sim, namely the cell that defines viz, isn’t computed by the runtime: by the time its inputs resolve, they are already stale. It’s this line here:

One way to fix this would be to remove one layer of indirection. Rather than having con → sim → viz, you could visualize the state of the simulation in the same cell that you derive it. For example, if you change your viz cell to be a pure function of the simulation state:

function viz(sim) {
  return html`<b>Simulation = ${sim}</b>`;
}

You can then redefine your sim cell like so:

if (con.reset) reset();
await Promises.delay(50);
const sim = increment() * 100;
display(viz(sim));

But note that you’ll still have the problem that any cell referencing sim will be starved because by the time the value of sim resolves it will already be stale. This only “fixes” the problem by moving the display into the cell that defines sim and before the runtime aborts the computation.

A more general way to fix this problem would be to replace your counter mutable with a sim mutable that represents the latest state of the simulation without regard to whether that state is stale. For example:

let _counter = 0;
const sim = Mutable(0);
const step = () => (sim.value = ++_counter * 100);
const reset = () => (sim.value = _counter = 0);

Here sim is a mutable storing the simulation state; step is the function you call to compute the next iteration of the simulation state, returning the updated state; and reset is the function you call to reset the simulation back to its initial state. The _counter local variable represents the “private” internal state of the simulation. You could make that a mutable, too, if you wanted to reference it in other cells, but here I just left it a plain variable and used an underscore to indicate that other cells shouldn’t peek at it.

Then, can you can drive your simulation with a cell that is purely side effects, calling the reset and/or step mutation functions as appropriate, and reacting to con:

if (con.reset) reset();
await Promises.delay(50);
step();

And then you can visualize the sim state, say in an HTML cell:

<b>Simulation = ${sim}</b>
3

Very interesting. The “stick it all in one cell” solution definitely makes sense to me, since it avoids the possibility of something going stale “between” cells. I’m going to have to sit with the “pure side effects” solution and try to understand why that works.

As far as order of execution among cells, when I said:

I thought that the computation would get pushed through the whole dependency graph before the next update would be “allowed” to begin

I was dead wrong!

I did not realize that the order of execution of cells, even with a straightforward sequence of dependencies, is non-deterministic. Specifically, with a sequence of cells: A → B → C, they might execute in the order:
A, B, C, A, B, C, …
but it could also be:
A, A, B, C, …
or:
A, B, A, B, C, …
etc…

It will depend on how long it takes each cell to execute compared to how often the “ticks” come in to initiate the sequence again starting with A. And that will depend on the speed of the CPU, what else is running on the machine, etc…

Of course, as long as the amount of work being done by each cell is sufficiently minimal, this won’t come up in practice, but I seem to have hit the limit with one or two of my simulations when paired with a very quick step rate.

4

Your updated understanding sounds correct to me. There is no guarantee that downstream cells run after every update — only “eventually” (though as you showed downstream computation can be starved indefinitely).

I suspect we could improve the Runtime to avoid starvation somehow, such that the slower cells still run just less frequently. Another trap the Runtime needs to avoid is running many copies of a slow downstream cell in parallel; ideally only one version of each cell is computed at a time. Contributions welcome if you want to study the Runtime. It’s tricky, though!