Possible (minor) speed/stability optimization to room sorting algorithm

[turt2live]

This is just an ephemeral thought while working on something else, hence the issue.

TLDR: Track where the list categories start and insert at the top when a category change happens. Also track the position of the sticky room rather than the room ID.

In the new sorting algorithm (by-importance / breadcrumbs) we split the list into 4 categories: red, grey, bold, and idle. When we want to stick a room into a category we start top-down in hopes that the categories are short until we hit idle, and then we do recents sorting within the categories. During these steps we also track when we jump categories so we can start a new grouping.

This causes problems like #9216 - a potential theory for this is while the iteration runs it loses track of the changes it made, so it re-inserts into the top of the list where it thinks the boundary lives. For example, consider the situation where the user has only bold and idle rooms and they receive 2 notifications: 1 grey and 1 red. When the algorithm goes to slot the rooms in, it might slot the red in first at the top of the list (because it saw the first room was bold), but it won't have remembered that so when it goes to slot the grey room in it also realizes that the first room of the working set is bold still, therefore inserting at position zero and above the red room.

Instead of iterating over an immutable list, we could statically track the position of each category, knowing that red is always going to be at zero. Then when we want to go slot a room in, we simply grab the slice between the start of the category we want and the next category (which might be the end of the list) and iterate to sort it into the recents collection. Afterwards, we update the position of any category boundaries which follow the change we made.

This is theoretically faster for grey, bold, and idle rooms (with idle being the fastest) because a potentially large chunk of the room list can be skipped before iterating.

Further assumptions can be made about the iteration too: when a category change occurs we just have to bump it to position zero of the category regardless of timestamp, which is closer to how it was supposed to work anyways. We don't do true recents ordering this way, but that is probably more desirable as fresher notifications are pushed to the top, similar to how the idle list works.

This would also fix the idle category not respecting the fact that it's supposed to push freshly unread rooms to the top rather than somewhere miles down the list - in theory breadcrumbs fixes this though.

A complication arises though: the room you're looking at is supposed to be sticky. That is to say even though it transitions from red to idle it's supposed to stay in the spot of the room list to avoid confusing the user. Instead of triggering the category change on the leading edge of the event, we use the falling edge (moving to a different room), therefore keeping the algorithm moderately sane. We could also improve the jumpiness by tracking the position within the category the room is supposed to be at so we know that if we end up re-sorting the category to keep N rooms above the sticky room. For example, if there are 2 rooms above our sticky room and a 3rd needs to be pushed on top, we make the stack form around the sticky room (insert at zero, switch 2 and 3, publish). Again, we avoid iteration in doing this.

All told, it probably won't be dramatically faster, but it should be dramatically more stable. Hopefully.

[turt2live]

This is on hold until time permits, with a code dump at matrix-org/matrix-react-sdk#4253 - it's very much incomplete and missing features.

[turt2live]

The stability improvement mentioned here is for a slightly different issue, though the effect of the work being done should fix the bug you're seeing (hopefully).

[t3chguy]

👏 that is expected given this issue is still open.

[martinvonwittich]

I stumbled over the following issue when configuring Riot like this:

• Order rooms by name: yes
• Show rooms with unread notifications first: yes

I would have expected Riot to sort first by read/unread, and then by alphabetical room name. Ie. the list of (unread) rooms should be sorted alphabetically, and rooms with unread messages should be at the top where I immediately notice them. Instead it sorts all rooms (both read and unread) alphabetically, and this leads me to overlook unread messages.

I'm hoping that resolving this issue will fix this :)

Thanks for your hard work on Riot!

[turt2live]

@martinvonwittich indeed, this issue should solve that, I think. The room list is a bit complicated to give a short answer :(

[turt2live]

Just to manage expectations for subscribers of this issue: matrix-org/matrix-react-sdk#4253 is the algorithm implementation though is missing nearly every feature someone might expect of a room list. Track #13635 to see when we are able to turn this thing on for everyone.