Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Have watchers track like computeds? #195

Open
dead-claudia opened this issue Apr 25, 2024 · 6 comments
Open

Have watchers track like computeds? #195

dead-claudia opened this issue Apr 25, 2024 · 6 comments

Comments

@dead-claudia
Copy link
Contributor

It'd simplify watcher management a lot, and it'd make it work like a mirror image of untrack. It also would simplify implementations somewhat and mitigate some perf hazards around Signal.subtle.{,un}watch.

The idea is this:

  • watcher.track(body): Tracks any newly accessed signals in body(), and after body() returns/throws, removes any signals not accessed. Returns the result of body()'s evaluation. The idea is it mirrors untrack(body).
  • watcher.reset(): Equivalent to watcher.track(() => {}), useful for clearing all signals in the watcher.

To add to a watcher, simply .get() inside a tracked callback. And to remove, simply omit.

This would also remove the need for intermediate Computeds for such auto-tracking.


This stands somewhat in opposition to some of what I've suggested in #178, in that the watcher would have to retain a list of signals it depends on. However, it'd simplify the internal execution model a bit:

  • Watchers track dependent States.
  • Computeds track dependent Computeds and States.
  • On all signals' get, add the signal to the current Watcher if not already present.
  • On Computed#get, it recurses through its dependencies to wire everything up.
    • On State dependency, add the State to the current Watcher if not already present. If dirty, treat the parent Computed as dirty.
    • On Computed dependency, add the Computed to the current Watcher if not already present, and recurse into its children. If after that, the dependency Computed is treated as dirty already, treat the parent Computed as dirty.
    • If all of a parent Computed's dependencies treat it as dirty, toss the children (removing descendant States from the current Watcher and vice versa if necessary) and execute the Computed's body. If the result is equal, treat the parent Computed as not dirty. Speculative descent can speed this up considerably, at cost to some memory churn (it may be worth putting this into the spec as well):
      1. Clone the current Watcher's dependent State set and let this be the saved set.
      2. Descend into existing dependencies. If none of them treat this Computed to be dirty, return.
      3. Reference-swap the current Watcher's dependent State set with the saved set. Now, the speculative set is the one saved and the old set is the one being added to.
      4. Execute this Computed's body. Treat this Computed's parent as dirty if and only if the result equals the previous result.
      5. For each State in the saved (speculative) set not in the (possibly updated) current Watcher's dependent State set, remove the current Watcher from that State's watcher set.
  • Before executing the tracked call, save the watcher's State set and set it to an empty set.
  • After executing the tracked call, diff the watcher's current signal set against the saved one, adding watchers to new signals' observing watcher sets and removing watchers from old signals' observing watcher sets.
    1. Push new ones to an intermediate list and remove retained ones from the saved set. This leaves the saved set with only old entries.
    2. Add the watcher to the new signals. It's okay to allow recursive .track(...) as the current set isn't accessed here.
    3. Remove the watcher from the old signals. It's okay to allow recursive .track(...) as the current set isn't accessed here.

    Why wait? It avoids premature unwatch -> rewatch cycles when a signal is removed from one Computed but added to another in the same pass. Likewise, the add-before-remove order ensures external reference counters don't hit zero and result in recreation of anything.

  • Persistent state needed:
    • A global "current watcher" field
    • A global "current computed" field
    • A per-watcher "watched states" set (iteration order observable)
    • A per-computed "watched signals" set (iteration order not observable)
    • A per-state "linked watchers" set (iteration order not observable)
@dead-claudia dead-claudia changed the title Track watchers like computeds? Have watchers track like computeds? Apr 25, 2024
@dead-claudia
Copy link
Contributor Author

I just realized this also carries a unique benefit: nothing has to accept an API class except for the operand of the class itself. It's entirely implicit. This allows for polyfills to use private fields for everything.

@shaylew
Copy link
Collaborator

shaylew commented Apr 26, 2024

This API is somewhat less expressive than the current Watcher interface, if track(fn) always resets -- it keeps you from being able to incrementally add things to a Watcher without repeating its previous (potentially long) list of dependencies. But if it doesn't reset it's definitely a nicer API, and worth floating.

One could also imagine a (non-resetting) track(fnOrSignal) that goes either way, and does:

  1. If typeof fnOrSignal is function, run it in the watcher's tracking context
  2. if fnOrSignal has a get property that's a function, run fnOrSignal.get() in the watcher's tracking context.

It's slightly more complicated, but supports both styles and prevents you from having to make closures to wrap signals just to watch them.

This does end up leaving out "unwatch a specific signal", so we'd want to double check the use cases there.

Being able to batch calls to watch and unwatch is very useful, and I think we do want to figure out a good mechanism for that. One option would be to defer them until you're outside of the outermost Computed's .get, which seems reasonable as a baseline and (maybe less reasonably) lets you use a dummy computed with an untrack inside to force batching. Watcher track as a way to get batching seems just as reasonable.

(I'm going to make a note that we should follow up on the watch/unwatch batching. We had some discussions about it early on, on a draft that had Effect rather than Watcher, and seemed to come to a consensus that "outside the outermost Computed or Effect" was lazy enough to batch and prompt enough about cleaning things up, but it's not the only coherent choice.)


As for the implementation notes... I'm fairly skeptical of anything that involves trying to make direct state->watcher or watcher->state edges, because there are graph structures where this blows up the total number of edges (and the work to create and later traverse them) quadratically. What's the problem you're trying to solve here, or what is it that's unsatisfactory about just treating Watchers in the graph the same way as we would a Computed that nothing else depends on?

@dead-claudia
Copy link
Contributor Author

dead-claudia commented Apr 29, 2024

@shaylew Apologies for the length.

This API is somewhat less expressive than the current Watcher interface, if track(fn) always resets -- it keeps you from being able to incrementally add things to a Watcher without repeating its previous (potentially long) list of dependencies. But if it doesn't reset it's definitely a nicer API, and worth floating.

This is a good point around not auto-resetting, and I'm okay with separating the two.

Admittedly, my API suggestion here was a bit bold and audacious.

One could also imagine a (non-resetting) track(fnOrSignal) that goes either way, and does:

  1. If typeof fnOrSignal is function, run it in the watcher's tracking context
  2. if fnOrSignal has a get property that's a function, run fnOrSignal.get() in the watcher's tracking context.

It's slightly more complicated, but supports both styles and prevents you from having to make closures to wrap signals just to watch them.

This does end up leaving out "unwatch a specific signal", so we'd want to double check the use cases there.

I could see that, though a separate .watch method would make more sense than combining the two methods.

Being able to batch calls to watch and unwatch is very useful, and I think we do want to figure out a good mechanism for that. One option would be to defer them until you're outside of the outermost Computed's .get, which seems reasonable as a baseline and (maybe less reasonably) lets you use a dummy computed with an untrack inside to force batching. Watcher track as a way to get batching seems just as reasonable.

It sounds reasonable on the surface, but it can cause abstractions to inexplicably break. Consider this situation, where one watcher watches a signal, but that same signal is also accessed by a parent computed watched by a different watcher:

  • In a framework, you watch a computed and invoke its .get().
  • You also limit a framework function to only be called during the scope of that .get(). Calling it during watch/unwatch is documented to be fine.
  • A component library your user uses happens to rely on that framework function being callable during watch/unwatch. It also does animations, and so while that's playing, it needs to update signals a lot.
  • The end developer, using two different frameworks, is calling the function to mount the component inside the signal handler of another library.

Now, you have two problems:

  1. The component library starts inexplicably throwing. The end developer tracks it down pretty easily to the library and files a bug report against it. That library's framework documents the throwing function as safe in that given instant, so the library developer files a bug against the framework. The framework developer can't reproduce the issue since they don't know about the integration issue, and so they close it. End developer has no idea it's actually the other framework causing it, and is now raging about the whole situation on Twitter/X.
  2. During animations, the library component sets an inner signal's value. This causes the parent framework to recompute the tree. The tree is the same as before, since nothing functionally changed, but it takes long enough to cause occasional but frequent stutters on mobile. The end developer tracks this down, profiles their app, and is utterly baffled that their framework's even rendering at that time. They don't know about Signal.subtle.untrack or the fact the inner component's using signals, so they spend a few days straight, only to give up on figuring out what's causing the stutters.

You need a clean boundary between watcher and parent computed, and the current proposed .watch(...) API doesn't afford that.

(I'm going to make a note that we should follow up on the watch/unwatch batching. We had some discussions about it early on, on a draft that had Effect rather than Watcher, and seemed to come to a consensus that "outside the outermost Computed or Effect" was lazy enough to batch and prompt enough about cleaning things up, but it's not the only coherent choice.)

Yeah, that batching is one of my main concerns, and it's part of what motivated me to suggest this as a means to delimit watchers, separate from computed.get().

As for the implementation notes... I'm fairly skeptical of anything that involves trying to make direct state->watcher or watcher->state edges, because there are graph structures where this blows up the total number of edges (and the work to create and later traverse them) quadratically.

You can't really do watcher reactions without at least indirect state -> watcher references. Even the polyfill has them indirectly.

Having each State hold a Set<Watcher> does allow you to entirely avoid traversing any graphs, though. With that, all you'd be doing is iterating that set each state.set(value).

The state (or really, signal) -> watcher links are just for the batching mechanism. Other strategies are possible for it.

What's the problem you're trying to solve here, or what is it that's unsatisfactory about just treating Watchers in the graph the same way as we would a Computed that nothing else depends on?

Could you elaborate? Not sure what you're talking about.

@dead-claudia dead-claudia mentioned this issue Apr 30, 2024
@shaylew
Copy link
Collaborator

shaylew commented May 13, 2024

On the algorithm:

You can't really do watcher reactions without at least indirect state -> watcher references. Even the polyfill has them indirectly.

Having each State hold a Set does allow you to entirely avoid traversing any graphs, though. With that, all you'd be doing is iterating that set each state.set(value).

It doesn't avoid the traversal, so much as it makes you do it eagerly at watch time, rather than lazily at set-time. This isn't obviously a bad trade, but I think it ends up being non-obviously a bad trade. In full (or mostly) generality you have some sort of graph like this:

mermaid-diagram-2024-05-13-014143

Notable to this situation is that, in the proposal's model:

  • You already need to traverse forwards from states if you set them, to dirty any computeds that depend on them.
  • Only the first such set has to do more than a constant amount of work, because after that everything is already dirty (up until you do a get and clean some of them).
  • Only the first watcher to be attached needs to traverse backwards to fire watched callbacks for the computeds/states, because after that everything is already live (until/unless all the watchers end up unwatching Cn at the same time).
  • watcher.watch(signal) takes a constant amount of memory, irrespective of how many transitive dependencies the signal has.

You can basically think about these bounds on a per-edge basis: each tracked read or .watch(x) creates one edge, dirtying traverses each forward edge at most once until the nodes are cleaned, and watching/unwatching nodes traverses each backwards edge at most once until the nodes change to unwatched/watched again.

As far as I can tell, trying to maintain a Set on each State doesn't play nice with those bounds. You pay for n^2 links, every consecutive set to one of the Si has to visit all n watchers (even though they'll already be dirty and won't be notified again after the first set), and every watch or unwatch on the watchers will have to visit n states and add/remove n links (even if those states don't need to fire any callbacks if their overall liveness hasn't changed).

@dead-claudia
Copy link
Contributor Author

dead-claudia commented May 14, 2024

@shaylew Okay, I took a step back, to focus more on the problem at hand. What about either of these possible solutions, using a .evaluateAndMarkReady() combined with scoping (#187)? Hooks would be called by watching and unwatching, and indirectly via computed .get() would get scheduled, and that method would execute and flush them.

Here's what I'm thinking at a high level (skipping around the value setting/propagating for brevity):

  • All nodes would need a "watching parent set" (initially empty), "watcher set" (initially empty), and "hook state" (initially "none") fields.
  • Computeds would need a children field.
  • Watchers would need a "hook request set", preferably iterated in insertion order.
  • A global "current parent" field would exist.
  • On all signal.get()s, the current parent is added to the watching parent set if it either has watchers or has a non-empty watching parent set. This is always O(1).
  • On computed.get(), for computeds that either have watchers or have a non-empty watching parent set when invoking the computed's callback:
    1. Save the computed's current children set. Let this be the saved set.
    2. Set its current children set to a new set. Let this be the new set.
    3. Execute the callback with this computed as the current parent.
    4. After the callback executes, for each child in the saved set not in the new set, remove this computed from that child's watched parent set.
      This is always O(child count) and not cache-friendly.
  • On state.set(value), the watching parent tree is traversed starting from the state node itself, with every found watcher invoked. This is O(watchers + node depth) and somewhat expensive, but using async context and a wrapper constructor, you can eliminate the node depth constraint.
  • On watcher.watch(signal), you'd add directly to the node's watcher set. If the node's watcher set was previously empty, you'd do a child tree traversal to add nodes to their children's watched computed sets, descending only when the child's watched computed set was previously empty. This is O(tree node count) and expensive.
  • On watcher.unwatch(signal), you'd remove directly from the node's watcher set. If the node's watcher set is newly empty, you'd do a child tree traversal to remove nodes from their children's watched computed sets, descending only when the child's watched computed set is made newly empty. This is O(tree node count) and expensive.
  • On watcher.evaluateAndMarkReady(), the watcher is unlocked for subsequent calls and then the nodes in the watcher's hook request set is iterated, removing them as they're visited. For nodes whose hook states are "add", their tracked callback is called and they're changed to "tracked". For nodes whose hook stare is "remove", same is done, but their untracked callback is called.
  • When a node is added to a parent for the first time, its "hook state" is set to "add" if it was previously "none", or "tracked" if previously "remove". When the node's removed, its hook state is set to "remove" if previously "tracked", "none" if previously "add". When it changes to "add" or "remove", it's added to each of its watchers' hook request sets, and when it transitions from either of those to "none" or "tracked", it's removed from that.

@dead-claudia
Copy link
Contributor Author

Okay, I came up with a simpler alternative that punts the whole question to userland, while still preventing double-notification: #222

For several promises, you can either aggregate them via Promise.all or use a dynamic batching mechanism (something I've wanted to see added to the language for years). The truly hard part isn't the immediate watching and signal collection management anyways, but the dependency tracking and knowing when to (and not to) watch.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants