Lazy state calculation

[Dionysusnu]

Currently, things like Computed will update as soon as any of its dependencies updates, and return the cached value on :get(). This is unnecessary, if there are no current dependents, or if the current dependents in turn do not have any dependents. This may become a significant performance drawback once Timers from #12 are added, as these will have to update on every Heartbeat. Instead, Computed could, for example, set self._didChange in :update(), and then calculate itself in :get() if this property is found to be true. It then sets the property to false and caches the value for future :get()s.

[Dionysusnu]

An example of when a State can become temporarily unused:

local leftAligned = Computed(function()
    -- complex, expensive math
end)
local rightAligned = Computed(function()
    -- different expensive math
end)

New "TextButton" {
    Position = Computed(function()
        return if alignmentKind:get() == "Left" then leftAligned:get() else rightAligned:get()
    end)
}

Currently, this will always be doing double work.

[dphfox]

This is something I've been thinking about a lot recently.

What this actually boils down to is answering the question 'will this change have a side effect anywhere in the reactive graph' which is actually something we can't answer for sure right now. There is no restriction on what can be made part of the reactive graph by design for extensibility, which means that we would have to introduce some kind of mechanism for state objects to identify themselves as being free from side effects.

As an example, Computed objects do not have side effects (unless you write impure code, in which case all bets are off). Changing foo will cause no side effect:

local foo = Value(5)

local bar = Computed(function()
    return foo:get() * 2
end)

foo:set(25) -- no effect

Other graph objects, for example Observer, do have side effects:

local foo = Value(5)

local bar = Computed(function()
    return foo:get() * 2
end)

Observer(bar):onChange(function()
    -- do something with bar
end)

foo:set(25) -- this may have a side effect

The big problem this inevitably points towards is garbage collection - how will a timer garbage collect it's own RenderStepped connection that keeps it alive? This is something I allude to in the timers issue - indeed, having a timer bound to render step makes it very difficult to properly evaluate when it's actually safe to collect. Lazy evaluation would go a long way towards solving this but would also require a fair amount more processing to be done on the reactive graph.

[dphfox]

The other issue that lazy state computation raises is exiting early if a value is unchanged; with lazy state evaluation, we have no way of knowing whether a value has changed until we evaluate it. This may inadvertently result in excessive updates being dispatched.

[Dionysusnu]

The other issue that lazy state computation raises is exiting early if a value is unchanged; with lazy state evaluation, we have no way of knowing whether a value has changed until we evaluate it. This may inadvertently result in excessive updates being dispatched.

I'm not sure what the drawback is here? Currently, that value would already have been evaluated earlier. So it's still 1 calculation, just only when actually needed?

[dphfox]

The issue I'm specifically thinking of is this; if a value indirectly uses another value which has changed, then that value must be marked as 'needs recalculation'. This can't take into account whether the dependencies have actually changed - they've only possibly changed. This means that potentially a lot of :get() calls could end up doing a lot more work than usual just to try and re-evaluate themselves (or alternatively, do a lot more work than usual to verify with their ancestors that re-evaluation needs to occur).

This is something we need to be particularly aware of given that a lot of uses of state objects appear in tight loops or performance critical code (specifically wrt animations) so doing lots of possibly expensive work in :get() could be dangerous. Remember - right now, the cost of a change to the reactive graph is entirely borne by the thread doing the setting, not the thread doing the getting. This is good in the context of animations because it minimises work done in places like RenderStepped. Not all resumption points are made equal.

We should probably test this out.

[Dionysusnu]

if a value indirectly uses another value which has changed, then that value must be marked as 'needs recalculation'. This can't take into account whether the dependencies have actually changed - they've only possibly changed.

That "another value" would know if its new value is actually different. And then either it calculates the main value directly, or it sets the main value for recalculation the next time. Which might be at a worse time if it's in RenderStepped, but the calculation happens either way.

[dphfox]

I don't think I understand what you imagine lazy state evaluation would look like. Do you mean it should be lazy when there are no dependents, or are all objects lazy all of the time?

[Dionysusnu]

I don't think I understand what you imagine lazy state evaluation would look like. Do you mean it should be lazy when there are no dependents, or are all objects lazy all of the time?

I'm not entirely sure. If possible, probably the latter? Either way, I don't see how it can result in more calculations than currently. In any case it will retain the same logic of knowing whether a new value actually requires recalculating dependents.

[dphfox]

I've been playing with this for a bit, and while I think it's broadly positive, I still am not confident about always lazy evaluating stuff. For maximum flexibility I think it'd be good to have an Eager state object that immediately evaluates the state object it's given upon an update, giving room for (mostly) transparent performance tweaking for any state object without requiring any further API changes.

[Dionysusnu]

The implementing PR, #251, has actually taken an (at least to me) unforeseen in-between approach, which is to calculate eagerly if there are any dependent states. I think it's worth re-listing the possible approaches, just so they can all be considered. 1) Always eager, no exceptions. Current approach. Can be quite expensive for unused values. 2) Always eager, unless explicitly using the Lazy wrapper. Takes extra work from the user to optimise cases where necessary, and has similar issues to option 4) 3) Lazy only if there are no direct dependents, unless explicitly using the Eager wrapper. Approach taken by #251. 4) Lazy only if there are no total tree users, unless explicitly using Eager. 5) Always lazy, unless explicitly using Eager. 6) Always lazy, no exceptions.

2 (if using Lazy), 5 (if not avoided by the user with an explicit Eager) and 6 all have the issue of calculating at possibly inefficient times. 3 has the issue of still doing excessive calculations if the dependent state is never used.

I think 4 is the least drawbacked solution, but it does provide a bigger implementation challenge than just doing 3.

[Almost89]

Trying to add 4's approach having a LITTLE bit of brain fog. Here's what I've got so far:

local function shouldCalculate(dependentState)
    for subDependentState in dependentState.dependentSet do
        if isState(subDependentState) then
            -- idk what to do here?
        end
    end
    return false
end

[Dionysusnu]

In theory, the only check necessary is whether any of those subDependentStates are an Observer. However that does leave open the case where users have custom code using :get(false). Maybe Fusion should, at least as an experiment at the start, emit a warning if :get is called when the value is not cached yet?

[Almost89]

However that does leave open the case where users have custom code using :get(false). Maybe Fusion should, at least as an experiment at the start, emit a warning if :get is called when the value is not cached yet?

Pretty sure :get() doesn't exist anymore.

[Dionysusnu]

Has it already been removed? I thought it was still in the design stage. Either way, same principle applies with the new rough equivalent. Edit: Yes I see PR 216 was merged. My bad. So the same applies to the peek method. If we implement option 4, it becomes a possibly-expensive call, which may not be intended by the consumer. So maybe there should be a warning about that when the expensive case is triggered?

[Almost89]

So when you peek() the computed and it has _didChange set to true it warns in output with a message like:

Computed has not yet cached its value meaning this could be an expensive call.

[dphfox]

Wrote about this on Technical Fluff: https://fluff.blog/2024/04/14/evolving-fusions-execution-model.html

I plan to get started on this imminently. I have things blocked on this right now, so I'll offer to take over from here.

[dphfox]

By the way, to chime in on the discussion here; I plan to adopt the same approach as Reactively here. I think that adopting a hybrid push-pull system as they've done should lead to good baseline performance.

As far as whether to evaluate eagerly or lazily, the way that tokamak (and I suspect Reactively, but unsure) is to allow graph objects to label themselves as "eager". When eager state objects are encountered during the push "invalidation" process, they're collected into a list. Once all invalidation is complete, these eager state objects are then "revalidated". From there, the state objects can pull from the rest of the graph to revalidate whichever objects they need dynamically.

The simplicity of this implementation seems to lend itself to favourable performance characteristics as it does a good job of reducing user code as much as possible, which - as per Reactively benchmarks - is the primary source of CPU load during real tasks. (anecdotally, this holds true for Fusion because Roblox APIs are very expensive relative to Luau code, and Fusion code almost always deals with Roblox APIs at some point during the update process.)

The simplicity should also make for cleaner and more maintainable code on our end, and should reduce the number of corner cases we have to consider wrt eager evaluation in correct topological order. One of our most teething problems historically have been "hidden dependencies" where two states depend on each other in such a way that the reactive graph doesn't properly model the connection, thus causing our topological sort to fail and introducing glitches. Creating dependencies on pull solves this nicely, so building the update mechanisms for eager objects like this means we solve that problem completely.

I propose that any more complex solution can likely be addressed by further remedies down the line, should they crop up as performance issues in real-world scenarios.

[dphfox]

Okay, so I'm realising that Reactively's algorithm has one problem that Fusion will have to solve uniquely. Reactively doesn't solve well for tracking whether updates to objects are "meaningful" - for example, if an object updates from 2 to 2, then there's no reason to update everything else, because 2 = 2.

I think I'll blend in a bit of my research from working on tokamak. In tokamak, there's a global time variable. This time variable monotonically increases over time. Every time an object meaningfully changes, it stores the time when that meaningful change occurred. When updating an object, the time of that object's last meaningful change is compared with the time of the dependency. If the dependency has an older time than the object's time, then that means the dependency hasn't meaningfully changed since this object last meaningfully changed. Thus, we can skip updates that don't meaningfully change anything if the object being updated still has a newer time than all of its dependencies.

In tokamak, the time is literally os.clock(). We could do that for Fusion, but it'd be interesting to pursue more deterministic solutions like some sort of integer counter.

[dphfox]

The upshot of this is that it should also be possible to reduce the number of graph colours down to simple binary invalid/valid using this approach, because tokamak doesn't employ any other colours.

[dphfox]

Here's my thinking on what to replace os.clock() with.

The main two properties of time we care about are that:

• at the start of a revalidation, time is larger than it has ever been before
• when dependencies update dependents, dependencies have an older time than dependents

Both of these mean the next time can always be derived from the reactive graph alone. The second property is trivial and local, but the first property is highly non-local and requires scanning the entire graph. This is not good.

If a way can be discovered of quickly getting the maximum time of a reactive graph, then the next time can be easily calculated without global state.

[dphfox]

Here's an idea. Consider an 'island' of graph objects connected to each other. We can store a table of information about this island, including useful properties such as the maximum time on this island. Each graph object can point at this island table to both identify which island it belongs to, and to quickly look up this information. From there, it's trivial to keep the maximum time up to date.

Now, consider two large islands of graph objects. These islands come from entirely separate universes, and have previously shared no knowledge about the other. (For example, they're islands created by two different Fusion modules).

Suddenly, a graph object from one island decides to connect to a graph object in the other island. They now form one mega-island, and so every graph object must now point to the mega-island-table.

If the island is small (size is trivial to track), then it's no big deal; we can spend a bit of cost to just merge the two islands together in the simple way. However, for large islands, this is a problem because we want the entire island to share the same island table, but we don't want to update all of those nodes in one of the islands.

So, instead of merging the island tables, we just link them to each other, so that they're aware of the other. When calculating values such as 'max time', the islands can quickly look across at each other to ensure that it is, indeed, the maximum. This algorithm is O(N) with respect to the number of large islands, but since the number of large islands is ordinarily limited, it's probably going to be fast.

[dphfox]

We could also just use os.clock(), which is probably faster than all this graph theory. So I think I'll do that, because I have few better ideas.

[dphfox]

I've committed the first iterations of my invalidation/revalidation algorithms to push-pull-execution #323

[dphfox]

Documented the new algorithm on Technical Fluff: https://fluff.blog/2024/04/16/monotonic-painting.html