Better performance for grids with thousands of items

[niklasramo]

I've been benchmarking the latest version of Muuri (dev branch) with large grids (1000 - 10000 items) and I'm not really happy with the performance. After a bit of thinking and quick testing I identified three bottlenecks:

1. Browser rendering. No matter what magic tricks you pull off the browser will slow down if you render thousands of items. However, with quick testing it seems that setting el.style.display = 'none' to all the grid items that are not in the screen makes that issue go away. In Chrome you can also do el.style.visibility = 'hidden', but that trick does not work so well on other browsers. The bottom line is that some kind of "virtualization/windowing" needs to be done to keep the UI smooth and responsive.
2. Item manipulation: At the moment when you layout the grid all the active items go through quite a lengthy series of checks and manipulation. The pipeline is optimized well for not causing unnecessary reflows, but it's still not fast enough to handle thousands of items in an acceptable timeframe. We need to be more clever and only process the items that the user has a chance of seeing. The other items can lay dormant until they have a chance of being seen.
3. Synchronous layout: I've been hesitant to refactor Muuri to support asynchronous layout, because the default layout algorithm can already handle all the items that the browser can render smoothly. However, it has its limits and there might very well be user provided layout algorithms that are much more complex than the default layout algorithm. This is why we need to support asynchronous layout so that web workers can be leveraged in the calculations.

All of these bottlenecks can be fixed so let's fix them 🙂

[paol-imi]

Hi Niklas,

I'm finishing the new version of muuri-react, and I was also reflecting on how I can optimize the use cases with thousands of items, since there are several windowing/virtualization libraries for react. I started looking on github but there seems to be nothing compatible with the project. I thought of a possible implementation but came to the conclusion that it cannot be external and must be provided directly by Muuri. I take advantage of this issue to show you the idea I was working on. I don't have a broad vision like yours that you created this library, and I don't know if this could work but I hope it could be useful. Muuri is really fantastic :)

Given the following hypotheses:

• In a project there are n types of items with n different sizes.
• We can determine which type of item is 'larger' and 'smaller' (These terms need a more accurate definition, for now let's say that these items are unique).
• We can determine which part of the grid element is visible on the screen.

Taking this representation of the grid element:

Grid area
________________________________  
|                               |  
|                               |
|                               |
|Visible area                   |
|...............................|  <-- top border 
|...............................|
|...............................|
|...............................|
|...............................|
|...............................|  <-- bottom border
|                               |
|                               |
|                               |
|                               |
|_______________________________|

We can easily establish (with simple equations) the minimum number of items before the visible area (Vmin) and the maximum number of items within the visible area (Vmax).

 Vmin = 3 (Big items)                                    Vmax = 20 (Small items)
________________________________                        ________________________________
|   ______    ______    ______  |                       |   ___     ___    ___    ___   |
|  |      |  |      |  |      | |                       |  |___|   |___|  |___|  |___|  |
|  |      |  |      |  |      | |                       |   ___     ___    ___    ___   |
|  |______|  |______|  |______| |                       |  |___|   |___|  |___|  |___|  |
|...............................| <--- top border --->  |...___ ....___....___ ...___...|
|...............................|                       |..|___|...|___|..|___|..|___|..|
|...............................|                       |...___ ....___....___ ...___...|
|...............................|                       |..|___|...|___|..|___|..|___|..|
|...............................|                       |...___ ....___....___ ...___...|
|...............................| <-- bottom border --> |..|___|...|___|..|___|..|___|..|
|                               |                       |                               |   
|                               |                       |                               |
|                               |                       |                               |
|                               |                       |                               |
|_______________________________|                       |_______________________________|  

Now we are sure that the items to be displayed are definitely between the positions [ Vmin, Vmax ].
The layout work will then be minimized to represent the visible items. It could be partially redone for the part that will become visible over time (for example linked to a scroll event).
Reading the tests you did, maybe it's enough to put display none to the non-visible item.

[niklasramo]

Hi @Paol-imi ! You've done great work with muuri-react, thanks for that 👍

This virtualization problem is very tricky with Muuri, because there's no restrictions on the layout. Any item (regardless of their index in the _items array) can be positioned anywhere in the grid. This is why we always need to compute all the item positions before we can determine if an item will be visible in the viewport (or the grid) when the positions are applied to the elements. Of course we could provide some heuristics for specific layout modes, but that's a another optimization later down the road.

Ideally, we would render (add to DOM) items only when they are in view and remove them from the DOM when they are out of the view. This would probably be optimal in terms of performance and memory. However, that's also a bit complex to implement compared just setting item's display value based on if it's in view or not. In my tests display:none trick worked wonders and made the UI very responsive even in the 5000-10000 item range. That's already a big upgrade compared to the current state of affairs and would be awesome if that optimization just worked out of the box without any extra configuration. Let's see if I can make it happen, it actually should not be that hard to implement.