Creating N mounted stores or unmounting N stores on the same host is O(N^2) #7
Comments
lawnsea
added a commit
to lawnsea/redux-mount-store
that referenced
this issue
Jul 20, 2016
As described in RetailMeNotSandbox#7, repeatedly performing immutable updates can be very slow. One part of the problem is that object-path-immutable doesn't provide a facility for performing multiple operations on an object and then returning a single new object with all affected paths cloned. For example: ``` let o = { foo: { bar: {} } }; o = objectPathImmutable.set(o, 'foo.bar.applesauce', 'chutney'); o = objectPathImmutable.set(o, 'foo.bar.jam', 'marmelade'); ``` Both `foo` and `bar` are cloned twice in the above code. What we would like instead is to perform an immutable transaction. This patch implements an API that supports the same operations as object-path-immutable, but performed as a transaction. This is partial progress toward fixing RetailMeNotSandbox#7.
lawnsea
added a commit
that referenced
this issue
Jul 26, 2016
As described in #7, repeatedly performing immutable updates can be very slow. One part of the problem is that object-path-immutable doesn't provide a facility for performing multiple operations on an object and then returning a single new object with all affected paths cloned. For example: ``` let o = { foo: { bar: {} } }; o = objectPathImmutable.set(o, 'foo.bar.applesauce', 'chutney'); o = objectPathImmutable.set(o, 'foo.bar.jam', 'marmelade'); ``` Both `foo` and `bar` are cloned twice in the above code. What we would like instead is to perform an immutable transaction. This patch implements an API that supports the same operations as object-path-immutable, but performed as a transaction. This is partial progress toward fixing #7. [close #9]
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
The problem
When a mounted store is actually created, we dispatch a
MOUNTaction. When we reduce this action, we write the mounted store's initial state to its mount path in the host's own state. This requires that we also clone all ancestor objects in the state. For example, adding a new mount atfoo.bar.applesaucerequires that we clonefoo.barandfoo.Doing so turns out to be O(N) where N is the number of properties on the object. Thus creating N mounted stores on the same host is O(1+2+...+N) = O(N^2).
Unmounting N stores on the same host exhibits similar complexity for the same reason. This is a bummer.
Possible solutions
Other immutable libraries
When we update state, we use
object-path-immutable#set, which performs the cloning described above. I first benchmarked equivalent methods from seamless-immutable and Immutable.js. Both were slower, which is unsurprising, sinceobject-path-immutable#setis dead simple.Immutable.js would be faster, but only if we require reducers to operate on its immutable types, rather than a plain object. I feel that would limit the usefulness of this library.
Be lazy
So, we need to do less work. We can't avoid writing the mounted store's state into the host's own state, but we can batch the writes up and only clone once per batch. This will necessitate changes the semantics of mounting and unmounting wrt actions. What we will do is batch up the work to mount or unmount and either perform it on a later turn of the event loop, or when needed due to a call to
getStateordispatchnecessitates.The plan
mount,mount+ create, andunmountmountandunmountto do everything lazilyThe text was updated successfully, but these errors were encountered: