Use good data structures in Redux state, to avoid quadratic work #3949

gnprice · 2020-03-03T23:41:41Z

Priority checklist (with updates from our progress):

Completed the general infrastructure (particularly with [REVIEWABLE] A second approach to storing non-serializable data in Redux #4047), so that what remains is converting individual data structures.
(Store state.narrows as an Immutable.Map (continued) #4201) state.narrows
(filed as Use Immutable for state.flags. #4252) state.flags has several maps each of which can have one element per message, and which get updated every time you scroll through some messages and when you get new messages. The number of messages can easily be a few thousand, if you've browsed around a few narrows since launching the app. These should each be Immutable.Map.
(done as Store state.messages as an Immutable.Map. #4390) state.messages is a map with one element per message. This should be an Immutable.Map.
state.presence is a map with one element per currently-online user, and can get pretty frequent updates. This should be an Immutable.Map.
The values in state.narrows are arrays of message IDs, with perhaps thousands of elements if you've scrolled through a lot of history in some narrow. These should each be an Immutable.List.
(filed as part of Make "unread" model efficient at marking a message as read #4438) state.unread is a bit complicated, but in particular contains arrays of message IDs that will in total have up to 50k messages among them, if the user has that many unreads. (Including in muted streams, I believe -- so that may be fairly common for users of busy orgs.)
- Each of those arrays should be an Immutable.List.
- There are probably further improvements to make here that will complement that one.
state.users is less often updated, but can get very big -- total users can easily be a few thousand, in a large public org like chat.zulip.org. Currently this is an array. Instead it should be an Immutable.Map, or possibly a plain built-in Map. The reason here is mainly Avoid linear scans through all users, streams, etc. #3339.
(Get and maintain a handy optimized data structure of recent PM conversations #4392) state.pmConversations

As discussed in #3339, there are a lot of places where we maintain large amounts of data -- like all the users in the realm -- in data structures like Array which make it inefficient to find the data we want at a given time, like a particular user.

Some other data structures are maintained as objects used as maps: notably, the collection of all the messages we have from the server. These are efficient for lookup... but both these objects-as-maps, and the Arrays, are extremely inefficient to build up for large amounts of data in the Redux style we use. Specifically, building a new array like [...state, newItem] or a new object like { ...state, [newKey]: newItem } has to copy the entire existing array or object, taking linear time -- which means building up an array or object with N items this way takes quadratic time O(N^2). Demo at #3339 (comment) .

So, we should fix that.

There are a couple of potential stages here:

As a modest but useful improvement, we can use Map instead of object-as-map. This is still quadratic time to build, but over 2x faster (Avoid linear scans through all users, streams, etc. #3339 (comment)), a solid constant-factor improvement. It's also cleaner in the code and for type-checking.
For a more complete solution, we'd want to be maintaining our data structures in an efficient way. Efficiently maintaining data structures without mutating them is a bit subtle, but there are well-understood techniques for doing so (called "persistent data structures"). One implementation of those in JS is Immutable.js.

The main technical obstacle I believe we'll need to resolve is how to serialize and deserialize these data structures for redux-persist. This shouldn't fundamentally be complicated once we work out how; but it'll require some studying of the docs of redux-persist and friends and of Immutable.js, then possibly of implementations where docs are inadequate, in order to see how to wire up appropriate serialization and deserialization functions. Relatedly, we'll want to think through and test the migration path for data serialized by a previous version of the app.

I've forked off #3950 for using Map in place of object-as-map (the first stage above), which will also be an opportunity to figure out this aspect.

A quick extra note, in addition to what's there:

remotedev-serialize will serialize Immutable.js data structures, as well as built-in Map and Set. Key bits of the implementation:
https://github.com/zalmoxisus/remotedev-serialize/blob/master/immutable/serialize.js
https://github.com/zalmoxisus/remotedev-serialize/blob/master/helpers/index.js

Specifically about Immutable.js: one thing I remember taking from when I was reading about this area last year is that people get annoyed with converting their objects to and from Immutable's types.

My thinking on that -- untested, so maybe this is hard for some reason -- is that that could be addressed by

using Immutable for the big collections, like the user-id -> user map; but
using plain old JS objects (just as we do today) for the struct-like objects inside those collections, like the individual users.

Within this repo there's some ancient history with Immutable, from 2016: it was used at first and then was ripped out, in a series ending at 2eb654f. It looks like the strategy there was to use it even for the struct-like objects inside the collections; as expected, this meant its API showed up all over the code, and the people working on the app at the time decided they found that too annoying to keep doing.

Previous related chat discussion here:
https://chat.zulip.org/#narrow/stream/243-mobile-team/topic/pure.20functions/near/793927

The text was updated successfully, but these errors were encountered:

Storing the parsed ZulipVersion instance in Redux makes it easier to work with, so we don't have to think about constructing a new instance as part of every server feature check. The one tricky bit is that our Redux state is serialized with JSON.stringify by redux-persist so that it can be stored in ZulipAsyncStorage, but the ZulipVersion instance itself is not serializable. Thankfully, it can be fully represented by its raw version string, which is serializable. So, on entry into ZulipAsyncStorage, convert the ZulipVersion instance into the raw version string with .raw(), and on exit, call the ZulipVersion constructor on that raw version string. We use redux-persist's `createTransform`. We locate a value to apply this transformation to with an "outside-in" approach, in particular, by the value's extrinsic property of where it is in the Redux store. That is, we know that it's at the `zulipVersion` key on all Account objects in state.accounts. Instead, we might have used an "inside-out" approach to locate a value by its *intrinsic* property of being a ZulipVersion instance. (We don't insist on using a single approach for all future transforms, but it's useful to compare the two because it's possible that some kinds of transformations fit one way better than the other. See zulip#3950, "Use Map rather than object-as-Map in our Redux state", and zulip#3949, "Use good data structures in Redux state, to avoid quadratic work", for more things we'll need to transform.) The "outside-in" approach requires that we write and maintain code to establish the location of the values to transform. But the complexity of that code will be no more than the complexity of the reducer(s) in charge of the same part(s) of the state, so the burden isn't worrisome. Establishing the location is a two-step process: 1) In src/boot/store, tell the redux-persist transform, created with createTransform, what key you want to handle. (In this case, 'accounts'.) 2) In the reducer file corresponding to that key, write "save" and "load" functions that know where to find the value. (They also do the actual transformation.) It's helpful in step 2 to consolidate code into the reducer files, which already have code that's aware of the structure of the part of state being treated. (Further consolidation like this is zulip#3934.) If we had instead gone with the "inside-out" approach (i.e., locating the value by its being `instanceof ZulipVersion`), which doesn't depend on knowing the value's location in the Redux state, we might have used a handy feature of `remotedev-serialize` called "custom serialization functions" (see https://github.com/zalmoxisus/remotedev-serialize#passing-custom-serialization-functions). As noted in zulip#3949, at some point we'll probably use remotedev-serialize for the particular purpose of transforming Immutable.js data structures, so it may be convenient to piggy-back on that for this custom functionality. Greg explains that strategy at zulip#3952 (comment): """ * at save time, values that are `instanceof ZulipVersion` get turned into objects like `{__serializedType__: 'ZulipVersion', data: '2.0.0-rc1'}`, before being JSON-serialized * at load time, after JSON deserialization, values that are objects with a `__serializedType__` property get transformed in a way identified by that property's value: in particular if `__serializedType__: 'ZulipVersion'`, then `data` is fed to `new ZulipVersion` """ This would eliminate the need for custom code that tracks the location of the values to be transformed. Reasons we don't use this strategy here are that we don't expect the location of the ZulipVersion value to change, and that the remotedev-serialize strategy always requires writing a migration; old data has never been persisted with that __serializedType__ property. Fixes: zulip#3951

rk-for-zulip · 2020-03-10T17:13:20Z

In particular, for data which we want to keep sorted (for example, our NarrowsState, which is sorted by message ID), we may want to consider functional-red-black-tree.

Storing the parsed ZulipVersion instance in Redux makes it easier to work with, so we don't have to think about constructing a new instance as part of every server feature check. The one tricky bit is that our Redux state is serialized with JSON.stringify by redux-persist so that it can be stored in ZulipAsyncStorage, but the ZulipVersion instance itself is not serializable. Thankfully, it can be fully represented by its raw version string, which is serializable. So, on entry into ZulipAsyncStorage, convert the ZulipVersion instance into the raw version string with .raw(), and on exit, call the ZulipVersion constructor on that raw version string. We use redux-persist's `createTransform`. We locate a value to apply this transformation to with an "outside-in" approach, in particular, by the value's extrinsic property of where it is in the Redux store. That is, we know that it's at the `zulipVersion` key on all Account objects in state.accounts. Instead, we might have used an "inside-out" approach to locate a value by its *intrinsic* property of being a ZulipVersion instance. (We don't insist on using a single approach for all future transforms, but it's useful to compare the two because it's possible that some kinds of transformations fit one way better than the other. See zulip#3950, "Use Map rather than object-as-Map in our Redux state", and zulip#3949, "Use good data structures in Redux state, to avoid quadratic work", for more things we'll need to transform.) The "outside-in" approach requires that we write and maintain code to establish the location of the values to transform. But the complexity of that code will be no more than the complexity of the reducer(s) in charge of the same part(s) of the state, so the burden isn't worrisome. Establishing the location is a two-step process: 1) In src/boot/store, tell the redux-persist transform, created with createTransform, what key you want to handle. (In this case, 'accounts'.) 2) In the reducer file corresponding to that key, write "save" and "load" functions that know where to find the value. (They also do the actual transformation.) It's helpful in step 2 to consolidate code into the reducer files, which already have code that's aware of the structure of the part of state being treated. (Further consolidation like this is zulip#3934.) If we had instead gone with the "inside-out" approach (i.e., locating the value by its being `instanceof ZulipVersion`), which doesn't depend on knowing the value's location in the Redux state, we might have used a handy feature of `remotedev-serialize` called "custom serialization functions" (see https://github.com/zalmoxisus/remotedev-serialize#passing-custom-serialization-functions). As noted in zulip#3949, at some point we'll probably use remotedev-serialize for the particular purpose of transforming Immutable.js data structures, so it may be convenient to piggy-back on that for this custom functionality. Greg explains that strategy at zulip#3952 (comment): """ * at save time, values that are `instanceof ZulipVersion` get turned into objects like `{__serializedType__: 'ZulipVersion', data: '2.0.0-rc1'}`, before being JSON-serialized * at load time, after JSON deserialization, values that are objects with a `__serializedType__` property get transformed in a way identified by that property's value: in particular if `__serializedType__: 'ZulipVersion'`, then `data` is fed to `new ZulipVersion` """ This would eliminate the need for custom code that tracks the location of the values to be transformed. Reasons we don't use this strategy here are that we don't expect the location of the ZulipVersion value to change, and that the remotedev-serialize strategy always requires writing a migration; old data has never been persisted with that __serializedType__ property. Fixes: zulip#3951

In an upcoming commit, we will use these to implement "replacer" and "reviver" transforms so that we can store non-serializable objects, in this case, a ZulipVersion, in Redux, and have it be saved to disk in a serialized format. They will also be useful for storing, e.g., an Immutable.Map in Redux, later on, in zulip#3949 and zulip#3950.

Storing the parsed ZulipVersion instance in Redux makes it easier to work with, so we don't have to think about constructing a new instance as part of every server feature check. The one tricky bit is that our Redux state is serialized, with JSON.stringify, by redux-persist so that it can be stored in ZulipAsyncStorage, but the ZulipVersion instance itself is not serializable. Thankfully, it can be fully represented by its raw version string, which is serializable. So, on entry into ZulipAsyncStorage, convert the ZulipVersion instance into the raw version string with .raw() ("replace" it), and on exit, call the ZulipVersion constructor on that raw version string ("revive" it). We considered two main strategies for locating the bit of state to be transformed (in this case, the `zulipVersion` field, which stores a ZulipVersion value, in elements of the `state.accounts` array): 1) The "outside-in" strategy, of identifying the value by the extrinsic property of where it is; i.e., that it's at the field named 'zulipVersion' on elements of the `state.accounts` array, or 2) The "inside-out" strategy, of identifying the value by its intrinsic property of being `instanceof ZulipVersion`. We chose the latter. When we work on zulip#3950, converting our object-as-map fields to use Map or Immutable.Map, we'll be making similar, sweeping changes to many different parts of the state, so it's most natural for the bulk of our logic to be independent of the location in state, and focus instead on the type of non-serializable object being stored. This approach conveniently clears the path to use ImmutableJS for additional reasons discussed later in this message. An exploration of the "outside-in" approach is left as the un-merged PR zulip#3952. The main advantage of that approach is that we wouldn't need to write migrations, but it had the significant drawback of requiring a lot of code (for locating the bit of state to be transformed) that was 1) boilerplate, and 2) difficult to get fully type-checked, which is a bad combination. These concerns were not sufficiently alleviated by the complexity of that boilerplate being bounded by the complexity of the reducer(s) in charge of the corresponding part(s) of the state. There's nothing stopping us from mixing the two approaches, in future, but it would be nice to stick to one as far as possible, for simplicity. For the "inside-out" implementation, we use `remotedev-serialize` (added in a recent commit), with custom replacer and reviver functions. As Greg explains at zulip#3952 (comment): """ * at save time, values that are `instanceof ZulipVersion` get turned into objects like `{__serializedType__: 'ZulipVersion', data: '2.0.0-rc1'}`, before being JSON-serialized * at load time, after JSON deserialization, values that are objects with a `__serializedType__` property get transformed in a way identified by that property's value: in particular if `__serializedType__: 'ZulipVersion'`, then `data` is fed to `new ZulipVersion` """ Since nothing has ever been stored in this `__serializedType__` format, we have to write a migration. It turns out to be very straightforward, and we expect it will be in the future. But we MUST remember to do so every time we use this approach in future. As mentioned above, this approach further clears the way for ImmutableJS. I've neglected to mention that the primary purpose of `remotedev-serialize` is to replace and revive ImmutableJS objects! (Note that we added `immutable` as a dependency in a recent commit.) So zulip#3949 and zulip#3950 will be much easier after this. The custom replacer/reviver functions we use here are a nice bit of flexibility provided on the side. Fixes: zulip#3951

Do not use `remotedev-serialize` directly. In the next commit, we fix a security hole by wrapping this dependency and recommending the use of the wrapper. In an upcoming commit, we will set up a system of "replacer" and "reviver" transforms so that we can store non-serializable objects, such as ZulipVersion instances, in Redux, and have a serializable format be persisted to disk. This same system will be used for non-serializable objects besides ZulipVersion instances; see zulip#3949 and zulip#3950, which will be much easier after this series. For the Flow types for these modules: Thankfully, `immutable`, being much more popular, has Flow types out of the box. Some assembly is required for a libdef for `remotedev-serialize`, but it's important to get one working [1]. 1. Check to see if someone has already submitted a libdef to FlowTyped, with `flow-typed install remotedev-serialize`. There isn't; we get the output, '!! No [email protected] libdefs found in flow-typed for the explicitly requested libdefs. !! Consider using `flow-typed create-stub remotedev-serialize` to generate an empty libdef that you can fill in.'. 2. As that output suggests, run `flow-typed create-stub remotedev-serialize` . This creates `flow-typed/npm/remotedev-serialize_vx.x.x.js` and fills it with a template based on the directory structure in `node_modules/remotedev-serialize`. Move this to `flow-typed/remotedev-serialize_vx.x.x.js` (no `npm`) because we want to maintain it locally; we don't want local adjustments we make to get clobbered by an eventual libdef in the FlowTyped repo. Delete the metadata lines at the top; they work as a tag on libdef contents that come from the FlowTyped repo, which this one doesn't [2]. 3. Here, we could enter everything in manually, but it turns out that DefinitelyTyped has a TypeScript libdef for `remotedev-serialize` [3], which we can use as a starting point. So, copy that into a temporary local text file as, e.g., libdef.d.ts. 4. Flowgen [4] [5] [6] is a tool for translating from TypeScript to Flow. It isn't perfect, and it's transparent about that, which is good to see. We just need this single file translated, and it's small, so that increases our chances of success. Run `flowgen libdef.d.ts`. 5. That output isn't exactly in the form that we want, though. We want to put this information in `flow-typed/remotedev-serialize_vx.x.x.js` from step 2, in this block: ``` declare module 'remotedev-serialize' { declare module.exports: any; } ``` Copy it into that block, in any case, deleting the `declare module.exports: any;` line (we favor ES modules over CommonJS modules) and observe the errors. 6. The minimal set of changes to get it working is A) replace 'export' with 'declare export' [7] B) replace `typeof Immutable` with `any` and remove the Immutable import. You can't import types from other libdefs in a libdef [8]. 7. Step 2 created a lot of extra stubs in case we wanted to make a libdef for every single file in `node_modules/remotedev-serialize`. We never import directly from these other files, so it's fine to just put all the type information in a single libdef, as we did in the copy-and-paste in step 5. Delete those extra, unnecessary stubs. [1]: https://flow.org/en/docs/libdefs/#toc-general-best-practices [2]: https://chat.zulip.org/#narrow/stream/243-mobile-team/topic/Android.20build.3A.20unimodules/near/859855 [3]: https://github.com/DefinitelyTyped/DefinitelyTyped/blob/55ebcedca/types/remotedev-serialize/index.d.ts. [4]: https://github.com/joarwilk/flowgen [5]: zulip#3458 (comment) [6]: https://chat.zulip.org/#narrow/stream/243-mobile-team/topic/Android.20build.3A.20unimodules/near/845802 [7]: https://flow.org/en/docs/libdefs/creation/ [8]: https://github.com/flow-typed/flow-typed/blob/master/CONTRIBUTING.md#dont-import-types-from-other-libdefs

Storing the parsed ZulipVersion instance in Redux makes it easier to work with, so we don't have to think about constructing a new instance as part of every server feature check. The one tricky bit is that our Redux state is serialized by redux-persist so that it can be stored in ZulipAsyncStorage, but the ZulipVersion instance itself is not serializable. Thankfully, it can be fully represented by its raw version string, which is serializable. So, on entry into ZulipAsyncStorage, we just have to convert the ZulipVersion instance into the raw version string, with .raw() ("replace" it), and on exit, make a new ZulipVersion instance, by calling the constructor with that raw version string ("revive" it). We considered two main strategies for locating the bit of state to be transformed (in this case, the `zulipVersion` field, which stores a ZulipVersion value, in elements of the `state.accounts` array): 1) The "outside-in" strategy, of identifying the value by the extrinsic property of where it is; i.e., that it's at the field named 'zulipVersion' on elements of the `state.accounts` array, or 2) The "inside-out" strategy, of identifying the value by its intrinsic property of being `instanceof ZulipVersion`. We chose the latter. When we work on zulip#3950, converting our object-as-map fields to use Map or Immutable.Map, we'll be making similar, sweeping changes to many different parts of the state, so it's most natural for the bulk of our logic to be independent of the location in state, and focus instead on the type of non-serializable object being stored. This approach conveniently clears the path to use ImmutableJS for additional reasons discussed later in this message. An exploration of the "outside-in" approach is left as the un-merged PR zulip#3952. The main advantage of that approach is that we wouldn't need to write migrations, but it had the significant drawback of requiring a lot of code (for locating the bit of state to be transformed) that was 1) boilerplate, and 2) difficult to get fully type-checked, which is a bad combination. These concerns were not sufficiently alleviated by the complexity of that boilerplate being bounded by the complexity of the reducer(s) in charge of the corresponding part(s) of the state: it's better just to not have to write boilerplate every time. There's nothing stopping us from mixing the two approaches, in future, but it would be nice to stick to one as far as possible, for simplicity. For the "inside-out" implementation, we use `remotedev-serialize` (added in a recent commit) [1], with custom replacer and reviver functions, defined in the previous commit. As Greg explains at zulip#3952 (comment): """ * at save time, values that are `instanceof ZulipVersion` get turned into objects like `{__serializedType__: 'ZulipVersion', data: '2.0.0-rc1'}`, before being JSON-serialized * at load time, after JSON deserialization, values that are objects with a `__serializedType__` property get transformed in a way identified by that property's value: in particular if `__serializedType__: 'ZulipVersion'`, then `data` is fed to `new ZulipVersion` """ Since we've never dealt with the Zulip version in this "live" (i.e., non-serializable) form, we have to write a migration. This was straightforward, but we MUST remember to write this kind of migration in the future. For making a value "live", where it wasn't before, the migration needs to: 1) As input, take the previous way of storing the data. Don't confuse this with the *current* way of storing the "dead" form. Just like any other migration, the previous shape is the input. 2) As output, give the "live" form of the data. Once it's in Redux, the replacer will take care of persisting it in the correct form. As mentioned above, this approach further clears the way for ImmutableJS; zulip#3949 and zulip#3950 will be much easier after this. I've neglected to mention that the primary purpose of `remotedev-serialize` is to replace and revive ImmutableJS objects! Its "default" replacers and revivers do this. The custom replacer/reviver functions we use here are a nice bit of flexibility provided on the side. (We added `immutable` as a dependency in a recent commit, since `remotedev-serialize` depends on it.) Fixes: zulip#3951 [1]: Actually, we use a wrapper around it, developed in a recent commit, to avoid a security hole. As long as we follow the pattern introduced in the two previous commits, using SerializeEscaped.immutable and its exported constant SERIALIZED_TYPE_FIELD_NAME, instead of Serialize.immutable (where Serialize is the default export of `remotedev-serialize`), we're fine.

In an upcoming commit, we will set up a system of "replacer" and "reviver" transforms so that we can store non-serializable objects, such as ZulipVersion instances, in Redux, and have a serializable format be persisted to disk. This same system will be used for non-serializable objects besides ZulipVersion instances; see zulip#3949 and zulip#3950, which will be much easier after this series. We use our own fork of `remotedev-serialize`, at 5f9f759a4, which Greg authored atop `zalmoxisus/remotedev-serialize.git` at 0.1.8, because it fixes an important bug. Also, the project seems unmaintained, and the maintainer hasn't been active anywhere on GitHub. The bug is that data fails to round-trip when it contains a "__serializedType__" key, which is used by the reviver to identify and reverse a particular replace transform. Such data, if present, could trigger hidden functionality. Also, explain the process of getting the `remotedev-serialize` libdef set up, in docs/howto/libdef.md. This patch won't be visible if you're reading this commit in the output of `git log --stat -p -- flow-typed/remotedev-serialize_vx.x.x.js` Try `git log --stat -p` followed by the commit ID.

Storing the parsed ZulipVersion instance in Redux makes it easier to work with, so we don't have to think about constructing a new instance as part of every server feature check. The one tricky bit is that our Redux state is serialized by redux-persist so that it can be stored in ZulipAsyncStorage, but the ZulipVersion instance itself is not serializable. Thankfully, it can be fully represented by its raw version string, which is serializable. So, on entry into ZulipAsyncStorage, we just have to convert the ZulipVersion instance into the raw version string, with .raw() ("replace" it), and on exit, make a new ZulipVersion instance, by calling the constructor with that raw version string ("revive" it). We considered two main strategies for locating the bit of state to be transformed (in this case, the `zulipVersion` field, which stores a ZulipVersion value, in elements of the `state.accounts` array): 1) The "outside-in" strategy, of identifying the value by the extrinsic property of where it is; i.e., that it's at the field named 'zulipVersion' on elements of the `state.accounts` array, or 2) The "inside-out" strategy, of identifying the value by its intrinsic property of being `instanceof ZulipVersion`. We chose the latter. When we work on zulip#3950, converting our object-as-map fields to use Map or Immutable.Map, we'll be making similar, sweeping changes to many different parts of the state, so it's most natural for the bulk of our logic to be independent of the location in state, and focus instead on the type of non-serializable object being stored. This approach conveniently clears the path to use ImmutableJS for additional reasons discussed later. An exploration of the "outside-in" approach is left as the un-merged PR zulip#3952. The main advantage of that approach is that we wouldn't need to write migrations, but it had the significant drawback of requiring a lot of code (for locating the bit of state to be transformed) that was 1) boilerplate, and 2) difficult to get fully type-checked, which is a bad combination. These concerns were not sufficiently alleviated by the complexity of that boilerplate being bounded by the complexity of the reducer(s) in charge of the corresponding part(s) of the state: it's better just to not have to write the boilerplate. There's nothing stopping us from mixing the two approaches, in future, but it would be nice to stick to one as far as possible, for simplicity. For the "inside-out" implementation, we use `remotedev-serialize` (added in a recent commit) [1], with custom replacer and reviver functions, defined in the previous commit. As Greg explains at zulip#3952 (comment): """ * at save time, values that are `instanceof ZulipVersion` get turned into objects like `{__serializedType__: 'ZulipVersion', data: '2.0.0-rc1'}`, before being JSON-serialized * at load time, after JSON deserialization, values that are objects with a `__serializedType__` property get transformed in a way identified by that property's value: in particular if `__serializedType__: 'ZulipVersion'`, then `data` is fed to `new ZulipVersion` """ Since we've never dealt with the Zulip version in this "live" (i.e., non-serializable) form, we have to write a migration. This was straightforward, but we MUST remember to write this kind of migration in the future. For making a value "live", where it wasn't before, the migration needs to: 1) As input, take the previous shape of the data. Don't confuse this with the *current* way of storing the "dead" shape. Just like any other migration, the previous shape is the input. 2) As output, give the "live" form of the data. Once it's in Redux, the replacer will take care of persisting it in the correct "dead" form. As mentioned above, this approach further clears the way for ImmutableJS; zulip#3949 and zulip#3950 will be much easier after this. I've neglected to mention that the primary purpose of `remotedev-serialize` is to replace and revive ImmutableJS objects! Its "default" replacers and revivers do this. The custom replacer/reviver functions we use here are a nice feature provided on the side. (We added `immutable` as a dependency in a recent commit, since `remotedev-serialize` depends on it.) Fixes: zulip#3951 [1]: We actually use our own fork, `zulip/remotedev-serialize@5f9f759a4`, which fixes a bug where "__serializedType__" keys in data fail to round-trip properly.

In an upcoming commit, we will set up a system of "replacer" and "reviver" transforms so that we can store non-serializable objects, such as ZulipVersion instances, in Redux, and have a serializable format be persisted to disk. This same system will be used for non-serializable objects besides ZulipVersion instances; see zulip#3949 and zulip#3950, which will be much easier after this series. We use our own fork of `remotedev-serialize`, at 5f9f759a4, which Greg authored atop `zalmoxisus/remotedev-serialize.git` at 0.1.8, because it fixes an important bug. Also, the project seems unmaintained, and the maintainer hasn't been active anywhere on GitHub. The bug is that data fails to round-trip when it contains a "__serializedType__" key, which is used by the reviver to identify and reverse a particular replace transform. Such data, if present, could trigger hidden functionality. Also, explain the process of getting the `remotedev-serialize` libdef set up, in docs/howto/libdef.md. This patch won't be visible if you're reading this commit in the output of `git log --stat -p -- flow-typed/remotedev-serialize_vx.x.x.js` Try `git log --stat -p` followed by the commit ID.

Storing the parsed ZulipVersion instance in Redux makes it easier to work with, so we don't have to think about constructing a new instance as part of every server feature check. The one tricky bit is that our Redux state is serialized by redux-persist so that it can be stored in ZulipAsyncStorage, but the ZulipVersion instance itself is not serializable. Thankfully, it can be fully represented by its raw version string, which is serializable. So, on entry into ZulipAsyncStorage, we just have to convert the ZulipVersion instance into the raw version string, with .raw() ("replace" it), and on exit, make a new ZulipVersion instance, by calling the constructor with that raw version string ("revive" it). We considered two main strategies for locating the bit of state to be transformed (in this case, the `zulipVersion` field, which stores a ZulipVersion value, in elements of the `state.accounts` array): 1) The "outside-in" strategy, of identifying the value by the extrinsic property of where it is; i.e., that it's at the field named 'zulipVersion' on elements of the `state.accounts` array, or 2) The "inside-out" strategy, of identifying the value by its intrinsic property of being `instanceof ZulipVersion`. We chose the latter. When we work on zulip#3950, converting our object-as-map fields to use Map or Immutable.Map, we'll be making similar, sweeping changes to many different parts of the state, so it's most natural for the bulk of our logic to be independent of the location in state, and focus instead on the type of non-serializable object being stored. This approach conveniently clears the path to use ImmutableJS for additional reasons discussed later. An exploration of the "outside-in" approach is left as the un-merged PR zulip#3952. The main advantage of that approach is that we wouldn't need to write migrations, but it had the significant drawback of requiring a lot of code (for locating the bit of state to be transformed) that was 1) boilerplate, and 2) difficult to get fully type-checked, which is a bad combination. These concerns were not sufficiently alleviated by the complexity of that boilerplate being bounded by the complexity of the reducer(s) in charge of the corresponding part(s) of the state: it's better just to not have to write the boilerplate. There's nothing stopping us from mixing the two approaches, in future, but it would be nice to stick to one as far as possible, for simplicity. For the "inside-out" implementation, we use `remotedev-serialize` (added in a recent commit) [1], with custom replacer and reviver functions, defined in the previous commit. As Greg explains at zulip#3952 (comment): """ * at save time, values that are `instanceof ZulipVersion` get turned into objects like `{__serializedType__: 'ZulipVersion', data: '2.0.0-rc1'}`, before being JSON-serialized * at load time, after JSON deserialization, values that are objects with a `__serializedType__` property get transformed in a way identified by that property's value: in particular if `__serializedType__: 'ZulipVersion'`, then `data` is fed to `new ZulipVersion` """ Since we've never dealt with the Zulip version in this "live" (i.e., non-serializable) form, we have to write a migration. This was straightforward, but we MUST remember to write this kind of migration in the future. For making a value "live", where it wasn't before, the migration needs to: 1) As input, take the previous shape of the data. Don't confuse this with the *current* way of storing the "dead" shape. Just like any other migration, the previous shape is the input. 2) As output, give the "live" form of the data. Once it's in Redux, the replacer will take care of persisting it in the correct "dead" form. As mentioned above, this approach further clears the way for ImmutableJS; zulip#3949 and zulip#3950 will be much easier after this. I've neglected to mention that the primary purpose of `remotedev-serialize` is to replace and revive ImmutableJS objects! Its "default" replacers and revivers do this. The custom replacer/reviver functions we use here are a nice feature provided on the side. (We added `immutable` as a dependency in a recent commit, since `remotedev-serialize` depends on it.) Fixes: zulip#3951 [1]: We actually use our own fork, `zulip/remotedev-serialize@5f9f759a4`, which fixes a bug where "__serializedType__" keys in data fail to round-trip properly.

In an upcoming commit, we will set up a system of "replacer" and "reviver" transforms so that we can store non-serializable objects, such as ZulipVersion instances, in Redux, and have a serializable format be persisted to disk. This same system will be used for non-serializable objects besides ZulipVersion instances; see zulip#3949 and zulip#3950, which will be much easier after this series. We use our own fork of `remotedev-serialize`, at 5f9f759a4, which Greg authored atop `zalmoxisus/remotedev-serialize.git` at 0.1.8, because it fixes an important bug. Also, the project seems unmaintained, and the maintainer hasn't been active anywhere on GitHub. The bug is that data fails to round-trip when it contains a "__serializedType__" key, which is used by the reviver to identify and reverse a particular replace transform. Such data, if present, could trigger hidden functionality. Also, explain the process of getting the `remotedev-serialize` libdef set up, in docs/howto/libdefs.md.

Storing the parsed ZulipVersion instance in Redux makes it easier to work with, so we don't have to think about constructing a new instance as part of every server feature check. The one tricky bit is that our Redux state is serialized by redux-persist so that it can be stored in ZulipAsyncStorage, but the ZulipVersion instance itself is not serializable. Thankfully, it can be fully represented by its raw version string, which is serializable. So, on entry into ZulipAsyncStorage, we just have to convert the ZulipVersion instance into the raw version string, with .raw() ("replace" it), and on exit, make a new ZulipVersion instance, by calling the constructor with that raw version string ("revive" it). We considered two main strategies for locating the bit of state to be transformed (in this case, the `zulipVersion` field, which stores a ZulipVersion value, in elements of the `state.accounts` array): 1) The "outside-in" strategy, of identifying the value by the extrinsic property of where it is; i.e., that it's at the field named 'zulipVersion' on elements of the `state.accounts` array, or 2) The "inside-out" strategy, of identifying the value by its intrinsic property of being `instanceof ZulipVersion`. We chose the latter. When we work on zulip#3950, converting our object-as-map fields to use Map or Immutable.Map, we'll be making similar, sweeping changes to many different parts of the state, so it's most natural for the bulk of our logic to be independent of the location in state, and focus instead on the type of non-serializable object being stored. This approach conveniently clears the path to use ImmutableJS for additional reasons discussed later. An exploration of the "outside-in" approach is left as the un-merged PR zulip#3952. The main advantage of that approach is that we wouldn't need to write migrations, but it had the significant drawback of requiring a lot of code (for locating the bit of state to be transformed) that was 1) boilerplate, and 2) difficult to get fully type-checked, which is a bad combination. These concerns were not sufficiently alleviated by the complexity of that boilerplate being bounded by the complexity of the reducer(s) in charge of the corresponding part(s) of the state: it's better just to not have to write the boilerplate. There's nothing stopping us from mixing the two approaches, in future, but it would be nice to stick to one as far as possible, for simplicity. For the "inside-out" implementation, we use `remotedev-serialize` (added in a recent commit) [1], with custom replacer and reviver functions, defined in the previous commit. As Greg explains at zulip#3952 (comment): """ * at save time, values that are `instanceof ZulipVersion` get turned into objects like `{__serializedType__: 'ZulipVersion', data: '2.0.0-rc1'}`, before being JSON-serialized * at load time, after JSON deserialization, values that are objects with a `__serializedType__` property get transformed in a way identified by that property's value: in particular if `__serializedType__: 'ZulipVersion'`, then `data` is fed to `new ZulipVersion` """ Since we've never dealt with the Zulip version in this "live" (i.e., non-serializable) form, we have to write a migration. This was straightforward, but we MUST remember to write this kind of migration in the future. For making a value "live", where it wasn't before, the migration needs to: 1) As input, take the previous shape of the data. Don't confuse this with the *current* way of storing the "dead" shape. Just like any other migration, the previous shape is the input. 2) As output, give the "live" form of the data. Once it's in Redux, the replacer will take care of persisting it in the correct "dead" form. As mentioned above, this approach further clears the way for ImmutableJS; zulip#3949 and zulip#3950 will be much easier after this. I've neglected to mention that the primary purpose of `remotedev-serialize` is to replace and revive ImmutableJS objects! Its "default" replacers and revivers do this. The custom replacer/reviver functions we use here are a nice feature provided on the side. (We added `immutable` as a dependency in a recent commit, since `remotedev-serialize` depends on it.) Fixes: zulip#3951 [1]: We actually use our own fork, `zulip/remotedev-serialize@5f9f759a4`, which fixes a bug where "__serializedType__" keys in data fail to round-trip properly.

gnprice · 2020-05-05T19:39:21Z

With #4047 completing #3951, I think we've now largely done the hard part for this! We're using remotedev-serialize in storing our state.

The next piece is to start converting pieces of our Redux state. I'm not sure we need #3950 as a further intermediate step; probably should just start trying migration straight to Immutable and see what obstacles come up.

An instance of zulip#3949 and zulip#3950. When I wrote the commit message for e834f33, I was most interested in the exciting new ability to serialize/deserialize custom, hand-made data types: in particular, ZulipVersion instances. An important thing that *also* happened in that commit was the new ability to store data structures from Immutable in Redux, without any additional setup! `remotedev-serialize` comes with off-the-shelf support for this. I gave this fact a brief shout-out near the end of the commit message for a4c29e9. So, do this, for the first time, paying careful attention to the instructions in a4c29e9 for writing a migration (copied here, as that commit message is quite long): """ For making a value "live", where it wasn't before, the migration needs to: 1) As input, take the previous shape of the data. Don't confuse this with the *current* way of storing the "dead" shape. Just like any other migration, the previous shape is the input. 2) As output, give the "live" form of the data. Once it's in Redux, the replacer will take care of persisting it in the correct "dead" form. """ The previous shape of the data was an object-as-map, which `Immutable.Map` takes as input quite cheerfully, and gives us our "live" Immutable.Map instance.

gnprice · 2020-12-14T04:51:03Z

And after #4201, we're now using Immutable.Map for state.narrows!

Another instance of this will be #4252, for state.flags.

In general I think the highest-priority places to do this are roughly:

state.flags has several maps each of which can have one element per message, and which get updated every time you scroll through some messages and when you get new messages. The number of messages can easily be a few thousand, if you've browsed around a few narrows since launching the app. These should each be Immutable.Map.
state.messages is a map with one element per message. This should be an Immutable.Map.
state.presence is a map with one element per currently-online user, and can get pretty frequent updates. This should be an Immutable.Map.
The values in state.narrows are arrays of message IDs, with perhaps thousands of elements if you've scrolled through a lot of history in some narrow. These should each be an Immutable.List.
state.unread is a bit complicated, but in particular contains arrays of message IDs that will in total have up to 50k messages among them, if the user has that many unreads. (Including in muted streams, I believe -- so that may be fairly common for users of busy orgs.)
- Each of those arrays should be an Immutable.List.
- There are probably further improvements to make here that will complement that one.

Then another category is where the data structures can get big but aren't so often updated:

state.users is the big one here -- total users can easily be a few thousand, in a large public org like chat.zulip.org. Currently this is an array. Instead it should be an Immutable.Map, or possibly a plain built-in Map. The reason here is mainly Avoid linear scans through all users, streams, etc. #3339.

chrisbobbe · 2020-12-14T15:24:02Z

state.messages is a map with one element per message. This should be an Immutable.Map.

I'll do this next!

An instance of zulip#3949 and zulip#3950, like 17bd752. One important difference from 17bd752 is that the `state.messages` map has numeric keys. We've handled the replace/revive logic for that, in the previous commit. But care must be taken whenever we use an `Immutable.Map(...)` call when we want a map with numeric keys, If you pass an object-as-map to `Immutable.Map`, it's impossible for the resulting `Immutable.Map`'s keys to be numbers, because the object-as-map's keys are necessarily strings, and that's up to JavaScript. The solution is to pass an array of key-value pairs, but unfortunately, Flow won't catch it if you forget to do this.

gnprice · 2021-01-27T04:06:50Z

We've continued making progress on this. I've made a checklist at the top, mostly from #3949 (comment), and checked off the items that are done. Still more to do!

gnprice added the a-redux label Mar 3, 2020

This was referenced Mar 4, 2020

Use Map rather than object-as-Map in our Redux state #3950

Closed

Keep the parsed ZulipVersion in Redux state, rather than raw string #3951

Closed

gnprice changed the title ~~Use better data structures in our Redux state~~ Use good data structures in our Redux state, avoiding quadratic work Mar 4, 2020

gnprice changed the title ~~Use good data structures in our Redux state, avoiding quadratic work~~ Use good data structures in Redux state, to avoid quadratic work Mar 4, 2020

gnprice mentioned this issue Mar 5, 2020

[WIP] redux: Add transform to keep parsed ZulipVersion in Redux state. #3952

Closed

chrisbobbe mentioned this issue Jul 10, 2020

Make state.narrows an Immutable.Map. #4187

Merged

This was referenced Sep 9, 2020

Store state.narrows as an Immutable.Map (continued) #4201

Merged

Use Immutable for state.flags. #4252

Open

chrisbobbe mentioned this issue Jan 8, 2021

Store state.messages as an Immutable.Map. #4390

Merged

gnprice mentioned this issue Jan 8, 2021

Get and maintain a handy optimized data structure of recent PM conversations #4392

Merged

This was referenced Jan 27, 2021

redux: Provide the global state to each sub-reducer #4437

Merged

Make "unread" model efficient at marking a message as read #4438

Closed

This was referenced Jan 27, 2021

Avoid linear scans through all users, streams, etc. #3339

Open

unread: Convert unread.streams to Immutable, and update efficiently #4448

Merged

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Use good data structures in Redux state, to avoid quadratic work #3949

Use good data structures in Redux state, to avoid quadratic work #3949

gnprice commented Mar 3, 2020 •

edited

Loading

rk-for-zulip commented Mar 10, 2020

gnprice commented May 5, 2020

gnprice commented Dec 14, 2020

chrisbobbe commented Dec 14, 2020

gnprice commented Jan 27, 2021

Use good data structures in Redux state, to avoid quadratic work #3949

Use good data structures in Redux state, to avoid quadratic work #3949

Comments

gnprice commented Mar 3, 2020 • edited Loading

rk-for-zulip commented Mar 10, 2020

gnprice commented May 5, 2020

gnprice commented Dec 14, 2020

chrisbobbe commented Dec 14, 2020

gnprice commented Jan 27, 2021

gnprice commented Mar 3, 2020 •

edited

Loading