Possible performance improvement when using rangeExtractor

[olee]

I tried to optimize the scroll performance in my list by only updating the rendered items in small "batches" by using this range extractor:

export function createSnappingRangeExtractor(snap: number = 5) {
    return (range: Range) => {
        const start = Math.max(Math.floor(range.start / snap) * snap - range.overscan, 0);
        const end = Math.min(Math.ceil(range.end / snap) * snap + range.overscan, range.size - 1);
        const arr: number[] = [];
        for (let i = start; i <= end; i++) {
            arr.push(i);
        }
        return arr;
    };
}

export const snappingRangeExtractor = createSnappingRangeExtractor(5);

However, when investigating why it was still rendering my component all the time, I noticed that the result of the range extractor is not actually properly memoized.
The following lines from here should imho be changed from

const virtualItems = React.useMemo(() => {
  const indexes = rangeExtractor({
    start: range.start,
    end: range.end,
    overscan,
    size: measurements.length,
  })

  const virtualItems = []
  for (let k = 0, len = indexes.length; k < len; k++) {
    // ... snip ...
  }
  return virtualItems
}, [
  defaultScrollToFn,
  horizontal,
  measurements,
  overscan,
  range.end,
  range.start,
  rangeExtractor,
])

to

const indexes = React.useMemo(() => rangeExtractor({
  start: range.start,
  end: range.end,
  overscan,
  size: measurements.length,
}), [
  range.start,
  range.end,
  overscan,
  measurements,
  rangeExtractor,
]);

const virtualItems = React.useMemo(() => {
  const virtualItems = []
  for (let k = 0, len = indexes.length; k < len; k++) {
    // ... snip ...
  }
  return virtualItems
}, [
  indexes,
  defaultScrollToFn,
  horizontal,
  measurements,
])

This would allow reducing the amount of DOM updates and could improve performance in some scenarios.

[piecyk]

Looks like good idea 👍 Just curious when do you memo the item?

[piecyk]

It would not fix creating new virtualItems ( that is pretty cheap ) but MemoItem should not be re-rendered.

Only problem in context of dynamic measurement is that measureRef will be new, and because of react ref caveat https://reactjs.org/docs/refs-and-the-dom.html#caveats-with-callback-refs offsetHeight/offsetWidth will be called, causing browser to do layout.

When combining ResizeObserver with react-virtual one option is to build stale cache of measureRefs, then using data attribute to call original measureRef in callback of ResizeObserver, that's why in example above there is data-key={item.key}

IMHO this is max what we can do now in context of dynamic sizes https://codesandbox.io/s/usevirtualresizeobserver-04-11-2021-75ye2

[olee]

Looks like good idea 👍 Just curious when do you memo the item?

So would you want to add this change to the lib?

[piecyk]

I don't think so, or at least not now We don't foce how dynamic measurement logic is implement, if it's via ResizeObserver or something else.

[omgoshjosh]

any consideration for async support to help with cases where async changes to the virtualized rows update the cache and trigger the rerender? when looking at your code sandbox from this reply, it seems like you've done a lot of the legwork there to at least get basic support without "forc[ing] how dynamic measurement logic is implement[ed]".

i guess my question is really this: when async changes happen to underlying virtualized rows, is the only way to trigger a rerender to have some local state that needs to be updated in order to trigger the rerender and remeasurement? and then that's where the resize observer comes into play?

[xaun]

@piecyk be great if the lib exported an optional way to leverage the ResizeObserver wrapper in your example. Basically every endless scroll feed is going to have image/video content in it that needs this. Took me all day of trying things with the heights and estimateSize prop, to finally end up with it only not working on initial load. Then after a long google tunnel, I end up on this thread, to then copy and paste that custom code, to then get the images working like this 🎉

Considering how common this is Im surprised this just isn't default, or there isn't an exported helper to plugin this functionality, or this isn't in the docs. But anyway, now that this is in the lib works much better with less code than react-virtualized CellMeasurer so that's great 🙏

[owanturist]

I believe I discovered almost the same workaround when I was implementing a virtual grid with lots of elements. Here is a playful DEMO. Notice the red border highlighting the rows/cols ranges in the top right corner each time when any of them is changing (== react render). The cells have a hover state, so you can notice how performance degrades for a second each time when a new line appears on the screen.

The roots of the implementation go to a Dynamic array (wiki) solution, where an array expands twice in size as soon as it reaches maximum capacity, and shrink twice in size as soon as there is less than a quarter of capacity.

Imagine a static array, like in Java with 6 elements, its capacity will be 2³ = 8:

["1", "2", "3", "4", "5", "6", null, null]
                                 ^-----^----- placeholders

The array keeps the same when the 7th element pushes into it:

["1", "2", "3", "4", "5", "6", "7", null]

But when it pushes the 8th element, it creates a new twice longer array, and copies all elements into it:

["1", "2", "3", "4", "5", "6", "7", "8", null, null, null, null, null, null, null, null]

From now and until the 16th element it pushes into the array with a constant time O(1).

But if it pops the 8th item the array does not shrink twice, because in this case it might cause too much back and forth if it needs to push and pop the "edge" element.

["1", "2", "3", "4", "5", "6", "7", null, null, null, null, null, null, null, null, null]

So instead the array will shrink twice as soon as there is a quarter capacity full:

["1", "2", "3", "4", null, null, null, null]

It should shrink twice (not four times) in this case, to prevent immediate expansion on the following push:

["1", "2", "3", "4", "5", null, null, null]

You might notice that this is a pretty smart and simple algorithm to implement a dynamic array with a static one under the hood. The only price we pay is space O(n).

The virtual scrolling might do the same trick but for starting and ending points of a range: it should expand 2 * overscan when it goes closer than overscan and shrink it 2 * overscan when it goes further than 4 * overscan. So the library guarantees that it never renders fewer elements outside of visible range than overscan, but at the same time it will not update a range each time when a new item (dis)appears for instance when an end-user scrolls 1 item back and forth.

In my opinion, this is a low-hanging fruit to improve the library's performance for all of the current users (bug-fix change) because none of the exposing API changes. In the worst case, a library user might override the rangeExtractor and avoid that "buffering". In future releases, it might be nice to include prevRange to rangeExtractor so it will be easier to implement other strategies for the range selection.

I am not sure I see which memorization @olee mentioned in the idea description but I didn't get any extra re-renders when the custom range is applied. @piecyk let me know if that makes sense at all, I'd be happy to contribute 🙏