[DataGrid] Change virtualization implementation

[oliviertassinari]

• I have searched the issues of this repository and believe that this is not a duplicate.

Summary 💡

Based on this benchmark #1903 (comment) there might be a different implementation of the virtualization that could yield better performance. We are currently underperforming compared to popular existing alternatives.

Motivation 🔦

A data grid is meant to make it easy to navigate information, the quality of the UX is heavily impacted by its rendering performance.

Before we commit to a different direction, I think that it's critical we investigate the state of the art with a rigorous benchmark of the existing solution. We can measure the average frame rate when scrolling vertically relatively quickly (relative to the speed of reading/scanning with the yet). My viewport shows 9 columns and 20 rows. So far (to update & complement), we have, sorting by performance:

• React Virtualized

  • codesandbox: https://codesandbox.io/s/gallant-brook-v5d0c
  • deployed to production: https://csb-v5d0c.netlify.app/
  • Average frame rate: 45 FPS
  • Strategy: Use the native scroll feature. On scroll, each time a new row needs to be displayed, add it to the dom, and apply an absolute positioning, matching its position. Overscale 10 rows in each direction. ⚠️ doesn't render the correct DOM structure for a data grid.
  

• MUI+

  • codesandbox: https://codesandbox.io/s/recursing-jackson-4xgsl
  • deployed to production: https://csb-4xgsl.netlify.app/
  • Average frame rate: 36 FPS
  • Strategy: Use the native scroll feature. On scroll, each time a new row needs to be displayed, shift the translate value of the whole row container to account for rows that are unmounted. Overscan of 3 rows in each direction.
  

• AG Grid

  • codesandbox: https://codesandbox.io/s/hopeful-ride-4wb7n
  • deployed to production: https://csb-4wb7n.netlify.app/
  • Average frame rate: 28 FPS
  • Strategy: Use the native scroll feature. On scroll, each time a new row needs to be displayed, add it to the dom, and apply a translate, matching its position. Overscale about 10 rows in each direction.
  

• XGrid

  • codesandbox: https://codesandbox.io/s/awesome-shtern-6pyxl
  • deployed to production: https://csb-6pyxl.netlify.app/
  • Average frame rate: 25 FPS
  • Strategy: Override the native scroll feature. On each scroll, update the translate value of the whole row container. Each time a threshold is passed, render a new batch of ~10 rows. Overscan of viewport height/row height rows.
  

Once we find a solution that seems better and we commit to it, we will also very likely want to take new constraints in:

1. Make virtualization work correctly: [DataGrid] Virtualization not respecting scrollTop #1911, [DataGrid] iOS freeze on drag #443
2. Built-in support for no virtualization [DataGrid] Allow to disable virtualization #1781, [data grid] Testing with react testing library #1151
3. Variable row height [DataGrid] Variable row height #438
4. Dynamic row height [DataGrid] Dynamic row height #417
5. Performance, this one suggests an inserting path [DataGrid] Use binary search to find column indexes in virtualization #1903, it seems to match what react-virtuoso, react-virtual, react-window, and react-virtualized as using as a technique. We could maybe even market it as a standalone module.
6. Research into overscan [RFC] Row virtualization overscanning tradeoff #270

Benchmark

• https://github.com/bvaughn/react-virtualized
• https://github.com/bvaughn/react-window
• https://github.com/petyosi/react-virtuoso
• https://github.com/tannerlinsley/react-virtual

[m4theushw]

I also did a benchmark here. My viewport shows 15 columns and 20 rows. In each test I try to scroll from top to bottom in approximately 9 seconds. Using the Performance tab and the snippet from https://stackoverflow.com/a/52466954 I got the following frame rates:

• React Virtualized: 47.39
• MUI+: 26.19
• AG-Grid: 25.6
• X-Grid: 8.48

Analysing our performance, we're dropping a lot of frames.

By removing calls to forceUpdate in useGridVirtualRows I managed to zero the dropped frames but the frame rate is still not good:

I've the impression that we might have something to optimize yet. Even with our current virtualization implementation we should be doing better.

[Janpot]

Started looking into a bit of benchmarking as well. I have yet to fully validate how representative these results are, but so far the numbers seem to be quite consistent. The test opens one of the netlify urls above, waits one second, then scrolls down at a fixed rate for 4 seconds while measuring the framerate. For the benchmarks posted above I get:

React Virtualized:
      Min: 18.867 fps
      Max: 54.354 fps
   Median: 50.196 fps
  Average: 46.871 fps

Mui+:
      Min: 9.469 fps
      Max: 54.852 fps
   Median: 42.686 fps
  Average: 38.894 fps

AG Grid:
      Min: 18.698 fps
      Max: 53.836 fps
   Median: 49.23 fps
  Average: 48.161 fps

XGrid:
      Min: 8.348 fps
      Max: 53.282 fps
   Median: 15.655 fps
  Average: 14.82 fps

Which suggests AG grid even outperforms React Virtualized. As said, It's a naive implementation of a benchmark, I yet have to determine how conclusive these numbers are. Thoughts welcome.

edit: Just noticed the AG Grid case renders only 10.000 columns.

edit 2: Yeah, there's definitely a few things I'm going to need to sort out in this benchmark. For starters, on my machine puppeteer seems to take 32ms to roundtrip the mouse wheel command to chromium. Secondly, when enabling the devtools FPS meter, I see it settle on exactly 30FPS

[Janpot]

Interestingly, AG Grid does a whole lot worse scrolling horizontally:

React Virtualized:
      Min: 18.571 fps
      Max: 55.316 fps
   Median: 49.85 fps
  Average: 46.495 fps

Mui+:
      Min: 12.459 fps
      Max: 55.679 fps
   Median: 49.91 fps
  Average: 44.277 fps

AG Grid:
      Min: 18.986 fps
      Max: 53.385 fps
   Median: 41.01 fps
  Average: 39.708 fps

XGrid:
      Min: 6.336 fps
      Max: 53.588 fps
   Median: 15.656 fps
  Average: 13.77 fps

[oliviertassinari]

@Janpot Awesome, https://github.com/Janpot/mui-plus/blob/master/scripts/benchmark.ts is going in the right direction! We have a similar automation approach in the core repository. It's what we need. We should be able to run multiple time the same tests to start to get a good idea of the uncertainty/standard deviation. Then, we can leverage it to know if a change makes a difference or if we don't have enough precision to conclude.

This seems very relevant to the benchmark effort that @DanailH started in June. How is the effort going alone?

[Janpot]

We should be able to run multiple time the same tests to start to get a good idea of the uncertainty/standard deviation.

The method seems statistically significant, when I calculate the standard deviation for these numbers over 10 runs I get

     Min: 12.592 fps (σ = 0.432)
     Max: 56.377 fps (σ = 1.463)
  Median: 46.099 fps (σ = 0.132)
    Mean: 41.055 fps (σ = 0.279)