More extensible effect notification

[justjake]

Currently when we end a transaction:

1. we synchronously fan out and find all the reactor EffectScheduler instances that are out-of-date with the changed Atoms. We "notify" each EffectScheduler that it may need to change by calling reactor.maybeScheduleEffect()
2. Inside EffectScheduler, maybeScheduleEffect causes us to synchronously re-compute its dependency parent Computeds.
3. Finally, if any parent computed actually changed after recompute, then the EffectScheduler will schedule the effect for execution. The default "schedule" for effects to also run synchronously, but a user may provide a schedule function to defer it for later.

At Notion, we've noticed that recomputing Computed can take a substantial amount of event loop runtime, even if the result computation doesn't change. Because of this, we also schedule and throttle re-computation (step 2) using a queue and requestAnimationFrame. Would there be any correctness problem in deferring almost everything in maybeScheduleEffect() to an arbitrary later time, like we allow for maybeExecute()? I don't think that would cause any correctness issues.

The most naive change to allow consumers to defer step 2 would be to add scheduleRecompute?: (fn: () => void) => void option to EffectScheduler, and enqueue maybeScheduleEffect calls with that callback.. But I think there's a more interesting way to think about effects and scheduling, especially in light of the effort in #53.

The great thing about a logical clock derivation system is that reading a value is guaranteed to be consistent, no matter how much local or wall-clock time passes between the change of a state and when you perform a read. That means the change notification mechanism of Signia has no bearing on the correctness of Signia's computations.

Because of that property, I think it would be low-risk to move the notification behavior from a single traverse implementation in transaction.ts to a polymorphic method on Child called .notify(). The default implementation of that method on Computed and EffectScheduler would implement the same behavior of traverse as of today:

class _Computed {
	notify() {
    			if (this.lastTraversedEpoch === globalEpoch) {
				return
			}

			this.lastTraversedEpoch = globalEpoch
			this.children.visit(child => child.notify())
	}
}

class EffectScheduler {
	notify() {
			if (this.lastTraversedEpoch === globalEpoch) {
				return
			}

			this.lastTraversedEpoch = globalEpoch
			this.maybeScheduleEffect()
	}
}

By making notify polymorphic, we can implement subclasses of both Computed and EffectScheduler that can arbitrarily accelerate or defer both the scheduling and algorithm for notifying their subgraph. To enable communication between participants, we could add an argument to notify like notify(ChangeSet) or something that especially complex participants could use as a WeakMap key / token or something.

The "push" Computed can be implemebed as a subclass that redefines notify to immediately do node.__unsafe__getWithoutCapture() etc.

[ds300]

Thanks for the great suggestion!

I see the value and I think it would work well for EffectScheduler.

Computed is a bit trickier

• Making traverse polymorphic could impact perf since it is used in such hot loops. But it could also be fine 🤷‍♀️
• It would bake in the current graph traversal approach and might make it difficult to add perf improvements or new features over time, e.g. I don't think push nodes would work implemented this way, they required a few extra core changes, and even then they weren't working 100% correctly according to the fuzz tests.

I'd be happy to merge a PR enabling this for EffectScheduler via an extra callback arg! That feels like a minimal and sensible change that provides a lot of extra leverage.

[justjake]

Agree about baking in the tree traversal 👍🏻, it's certainly a stretch to consider that polymorphism; going that route would need a lot more design.