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

[gnprice]

Priority checklist (with updates from our progress):

• [x] Completed the general infrastructure (particularly with #4047), so that what remains is converting individual data structures.
• [x] (#4201) state.narrows
• [ ] (filed as #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.
• [x] (done as #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 #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 #3339.
• [x] (#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 https://github.com/zulip/zulip-mobile/issues/3339#issuecomment-462963242 .

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 (https://github.com/zulip/zulip-mobile/issues/3339#issuecomment-462963242), 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 2eb654f41. 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

[rk-for-zulip]

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.

[gnprice]

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.

[gnprice]

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 #3339.

[chrisbobbe]

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

I'll do this next!

[gnprice]

We've continued making progress on this. I've made a checklist at the top, mostly from https://github.com/zulip/zulip-mobile/issues/3949#issuecomment-744164250, and checked off the items that are done. Still more to do!