Omnistac / zedux

:zap: A Molecular State Engine for React
https://Omnistac.github.io/zedux/
MIT License
376 stars 7 forks source link

feat!: make instances valid graph nodes and jobs #114

Closed bowheart closed 2 months ago

bowheart commented 2 months ago

Description

Our benchmarks revealed several performance bottlenecks in Zedux. None of these are problematic - Zedux is already 2-3x faster than Jotai, which itself one of the fastest state managers. However, we determined that Zedux is capable of gunning for some insane numbers akin to the fastest signals libs (like S.js, Solid signals, and Reactively). But it required a big rework.

The Rework

Zedux v1 stores atom instances in the ecosystem (ecosystem._instances), selectors in the Selectors class (ecosystem.selectors._items), and the graph nodes for each atom instance or selector cache in the Graph class (ecosystem._graph.nodes).

This led to lots of unnecessary reads - every time an atom instance updates, it has to find its graph node. Every time the graph propagates changes to nodes, it has to find the node's instances. We did this originally to support instance force-destruction - if an instance was destroyed, its graph node would remain until its dependents recreated the atom instance. But it didn't take long to determine this approach is unnecessary.

I refactored all the node/instance storage locations to use JS Maps, which are significantly faster at reads/writes/iterating when immutability isn't involved (which it isn't here). But doubling up the node storage locations still slows things down quite a bit.

Migrate ecosystem._instances, ecosystem.selectors._items, and ecosystem._graph.nodes to a single ecosystem.nodes map. This speeds up Zedux by almost 2x.

Additionally, the system for tracking graph updates during evaluation and applying them was unnecessarily slow, using a duplicated stack and creating lots of extra JS maps and objects for GC. Replace all of this with reusing the existing evaluation "stack" and a single pendingFlags mutation on every graph edge to gain an extra 10-20% speed boost.

Additionally x2, the most expensive piece of every atom instance and selector cache is the creation of a closure that can be passed to the scheduler to schedule jobs for that instance. Rather than creating a new function for every node, make the nodes themselves valid scheduler jobs. This way, we can reuse prototype methods for the scheduler's callbacks. This earns another 10-20% speed boost.

Some further perf tweaks included giving selector instances access to the ecosystem, giving both source and observer nodes access to the graph edge, and prioritizing checks for nodes in functions that accept either nodes or templates (so nodes can be passed directly for a speed boost).

Summary:

// Before:
interface Job {...}
interface EcosystemGraphNode {...}
class AtomInstanceBase {...}
class AtomInstance extends AtomInstanceBase {...}
class SelectorCache {...}

// After:
interface Job {...}
class GraphNode implements Job {...}
class AtomInstance extends GraphNode {...}
class SelectorInstance extends GraphNode {...}

Numbers:

# Before rework:

framework        , test                                                         , time     , gcTime
Zedux            , avoidablePropagation                                         , 1046.21  , 20.05
Zedux            , broadPropagation                                             , 4449.14  , 64.89
Zedux            , deepPropagation                                              , 905.68   , 19.85
Zedux            , diamond                                                      , 1808.94  , 30.58
Zedux            , mux                                                          , 1474.97  , 28.26
Zedux            , repeatedObservers                                            , 217.54   , 3.14
Zedux            , triangle                                                     , 579.48   , 11.92
Zedux            , unstable                                                     , 450.50   , 24.84

# After rework:

framework        , test                                                         , time     , gcTime
Zedux            , avoidablePropagation                                         , 437.31   , 9.53
Zedux            , broadPropagation                                             , 1681.34  , 23.87
Zedux            , deepPropagation                                              , 401.31   , 7.37
Zedux            , diamond                                                      , 723.12   , 13.80
Zedux            , mux                                                          , 551.35   , 7.95
Zedux            , repeatedObservers                                            , 80.96    , 0.68
Zedux            , triangle                                                     , 231.53   , 4.36
Zedux            , unstable                                                     , 278.54   , 11.25

I also removed Zedux's source maps - Vite wasn't generating them correctly anyway and the non-minified output of the dev builds is very readable. Plus the source maps tripled the size of the npm package and prevented chrome's line-level profiling from kicking in. This also means we don't have to ship the src code of each package to npm, further reducing the downloaded package size.

Phase 2

The keen observer will notice that the broadPropagation benchmark, while almost 3x faster than v1, is still significantly slower than the rest. This is because Zedux uses an O(n log n) insertion sort algorithm to schedule jobs for every node update. While this is almost on par with top-tier solutions for deep updates and all other metrics, it's significantly slower for broad updates (e.g. a single atom that's used directly by many other atoms).

Broad graphs are by far the most common in real-world scenarios, so this is something we need to address. In fact, it's the main purpose of this PR, even though this PR doesn't address it directly yet.

This rework is a necessary phase 1 step that simplifies the graph. This will help with switching us to a system that can skip the scheduler for most graph updates. Phase 2 will implement the actual skipping of the scheduler. I'm currently planning on phase 2 being part of Zedux v2, but seeing the crazy gains we've already achieved, I might want to push it back to v3. I'm open to any thoughts.

Breaking Changes

This rework required a few breaking changes. Beyond the required ones, we have lots of changes planned for Zedux v2. I took this opportunity to get a headstart on quite a few of those, so this PR has a few more changes than necessary. I'll try to list every change here so we can copy them to the migration guide.

This PR also starts migrating us to using single-letter properties in Zedux's classes/objects for internal fields. These single letters are well documented and a shortened version of a real property name, so they're easy to work with once you know them. The idea is that end users shouldn't need to use these internal fields, so they're obfuscated by using single-letters just like React 19 now obfuscates its internals. This along with the main refactor reduces the minified bundle size of the React package by 5kb already. And we're not done yet. I won't document these single-letter properties here, but the plan is to document them in the official docs before v2.

When referring to these single-letter properties, we type e.g. ecosystem.nodes, keeping it user-friendly while still showing that the property's actual name is simply n.

We're also reducing the number of classes used, preferring plain functions wherever possible since they minify so much better and properly hide internal details.

For any _-prefixed public properties, some have new equivalents and some were removed or are no longer exposed. I'm not documenting these here since it's unlikely anyone was using them (and you should be aware they're prone to break if you do). One goal of Zedux v2 is to remove these unstable-but-exposed methods, hiding stuff that's really internal and properly exposing stuff that should be exposed - via stable single-letter properties for things most users shouldn't care about.

Deleted Selectors class

This class was where selector caches were stored and served as a bridge between them and the ecosystem. You could access it via ecosystem.selectors. That property is gone.

The parts of this class that dealt with an individual cached selector have been moved to the new SelectorInstance class. The parts that dealt with the all selectors have been moved to the Ecosystem class.

Just as atom instances are instances of an atom template, selector instances are now considered instances of a selector "template". The template is the selector function or selector config object. Unlike atoms, the function/object "template" reference matters - all its instances are cached under an id that the template is WeakMapped to.

SelectorCache reworked as SelectorInstance

You could get instances of SelectorCache via ecosystem.selectors.getCache. The concept of a selector "cache" is gone, replaced with selector "instances". Selector caches always functioned very similarly to atom instances and will even more so in v2. The new naming makes that apparent.

Deleted EvaluationStack class

This class kept track of what was evaluating and exposed the universal reactive atomGetters object that gets passed to all ions and atom selectors. You could access it via ecosystem._evaluationStack. That property is gone.

Another optimization introduced in this PR is to replace the evaluation "stack" inline by mutating a single object. This is significantly faster than pushing/popping an array. See benchmark here.

We also want to be able to access the reactive atomGetters much easier than the current ecosystem._evaluationStack.atomGetters since it's how Zedux mimics signals libraries - any reactive context calling a reactive atomGetter automatically gets its graph dependencies updated.

Most of this class has been migrated to internal utils in our evaluationContext.ts util. The exception is:

Deleted Graph class

Ah it served us well. This kept track of all graph nodes and ran all graph update operations, including propagating state/promise changed or force destruction notifications to a node's dependents. It could be accessed via ecosystem._graph. That property is gone.

Most of this class's functionality has been moved to the new GraphNode class which both AtomInstance and the new SelectorInstance class inherit. This was the primary focus of this refactor - to make nodes take care of their own operations.

Nothing to document here, since ecosystem._graph was underscore-prefixed, so it was likely unused. Comment if you have an exception and I'll fill in any migration details.

Replaced AtomInstanceBase class with GraphNode

AtomInstanceBase was kind of a pointless placeholder class that AtomInstance inherited from. Its purpose was supposed to be defining everything that a valid atom instance requires for Zedux to be able to work with it. You would then be able to create your own classes that extend AtomInstanceBase that add functionality (or remove bloat) from the standard AtomInstance class. These base-extending classes would work with all of Zedux's APIs, TypeScript included.

After this refactor, the new GraphNode class is the natural successor to AtomInstanceBase. It's much more useful by itself and accomplishes everything AtomInstanceBase was designed to do.

The only functionality this class had was the addDependent method which has been moved to GraphNode#on.

Note that we're still not documenting how to extend Zedux's classes as part of v2, but maybe soon after.

AtomInstance Changes

Removed All prevReasons Properties

prevReasons had no internal use and was really just for user benefit, to see why an atom or selector evaluated last time it did. However, we found we never used it and it actually causes a "memory leak" of sorts:

The prevReasons would hold onto the previous state of the node. If the node had giant state (we had one with 27MB of data), it could really add up. It isn't a real memory leak since that memory is cleaned up the next time the node evaluates (or if it's destroyed), but it's still some very unnecessary cruft.

So we removed prevReasons from selectors and atom instances. It's still possible to track previous evaluation reasons yourself using an ecosystem plugin on the stateChanged mod if you do need this functionality.

Plugin Action Changes

Not documenting these here as Zedux v2 is reworking plugins entirely, but this PR modifies several plugin action payload types to use GraphNodes, which is more useful than the previous AnyAtomInstance | SelectorCache unions.

getInternals Changes

Nobody should be touching Zedux's internals (returned from the exported getInternals function). Its entire structure changed and will probably change again before v2. Comment if you need any details.

Deprecations

Zedux v2 will deprecate several things. This PR only deprecates one:

TypeScript

New Features

This refactor also naturally added some new features, mostly as part of GraphNodes being standardized.

Ecosystem Features

The New Atom Getters

In Zedux v1, atom getters have this shape:

{ ecosystem, get, getInstance, select }

While we won't remove any of that in v2, we will deprecate both getInstance and select. The plan is that Zedux v3 will have this atom getters shape:

{ ecosystem, get, getNode }

The plan is to also deprecate injectAtomSelector and useAtomSelector in favor of injectAtomValue/useAtomValue (or the get atom getter of course).

This PR only introduces the new getNode atom getter to the Ecosystem class. It is not formalized yet and nothing is deprecated yet, I'll do that in a follow-up PR. We had to add it now since the Selectors class was removed and we needed some way to get a selector instance.

The GraphNode class

Both AtomInstance and the new SelectorInstance class extend this class. GraphNode implements the Job interface, meaning all graph nodes are valid scheduler jobs.

All graph nodes have the following non-obfuscated properties:

The new SelectorInstance class adds nothing user-facing on top of the base GraphNode class. That's really the purpose of a selector - to be the most lightweight node possible.

TypeScript

This PR introduces some wildly useful TypeScript improvements.

On that last note, we are considering deprecating all Atom*Type type helpers in v2 in favor of *Of (e.g. AtomStateType -> StateOf). Besides being more succinct, this is a pattern that I think is catching on in the TS community, so we want to stick to standards.

Summary

This PR is bigger than it needs to be, but really only by a little and it gets us well on our way to Zedux v2. I'll PR this against master, but don't merge it until the next/v1.3.x branch is merged into master, master is ready to be moved into v2 prep phase, and the v1.x support branch is cut.

This PR leaves some loose ends. I'll sum them all up in the Zedux v2 roadmap.