Optimize flushChanges via WeakMap<Atom, ArraySet<EffectScheduler>>

[justjake]

This strategy comes from https://github.com/starbeamjs/starbeam

Currently when we write to an Atom, we recursively search the children to notify EffectScheduler subscribers. The problem with this kind of graph traversal in Javascript is that it's not very cache friendly. We can skip some work using the lastTraversedEpoch which effectively memoizes the traversal for already-notified subscribers. The work skipping helps in the best case, but doesn't reduce time spent in the worst case.

My proposed optimization is that we maintain a const ATOM_SUBSCRIBERS = new WeakMap<Atom, ArraySet<EffectScheduler>> which stores a direct mapping from mounted atoms to effects. If we can correctly maintain this set, the notification algorithm becomes strictly O(subscribers) instead of O(graph):

function flushChanges(atoms: Iterable<_Atom<any>>) {
  const reactors = new Set<EffectScheduler<unknown>>()
  for (const atom of atoms) {
    ATOM_SUBSCRIBERS.get(atom)?.forEach(effect => reactors.add(effect))
  }
  reactors.forEach(effect => r.maybeScheduleEffect())
} 

I haven't spent much time on the maintenance algorithm for ATOM_SUBSCRIBERS, but we should be able to do it in stopCapturingParents or similar by doing an upwards crawl of the parent. I don't recall how Starbeam implements it.

Maybe the maintenance time plus the storage space of any required memoize overwhelm the savings, but I think it could be a profitable optimization strategy.

[ds300]

It's a nice idea! I had the same idea but I ran into issues trying to implement it back in the early days of signia.

The problem is:

During a transaction the dependency graph may change, and it becomes possible for a change to an atom to need to flow to a reactor that it wasn't connected to before the start of the transaction. Which meant that any time the parents of any computed changed during a transaction we had to traverse it's entire parent hierarchy to find root atoms, and then make sure it's list of connected reactors was up to date, while detaching the reactors of any atoms no longer in the parent hierarchy.

I tried to optimize that by caching the parent atoms at each computed node, but that was slow and buggy and complicated, so I didn't pursue it further.

I'd be interested to find out whether starbeam is both pull-based and has transactions, and if so whether their stuff resolves the issue I ran into somehow.