Add CellMeasurer cache per item

[Mathieuu]

Hi,

First, I would like to say how much I like react-virtualized, it is a beautiful piece of software and it helped me a lot.

This issue can be related to #341.

Problem

When using <CellMeasurer> with a <Grid/>, the current cache strategy is to store/retrieve the row height and the column width. While this is helpful, it leads to pretty complex cache systems if we have the following constraints:

• An item can be inserted/moved/removed anywhere in the list
• An item can be modified (which would modify its dimensions)

Let's say I have a grid 3 columns by 3 rows.

If I cache per id, I would have to cache a value for each combination. For instance after the first render I would have a row height cache looking like that:

{
  Item1Id&Item2Id&Item3Id: 400
  Item4Id&Item5Id&Item6Id: 200
  Item7Id&Item8Id&Item9Id: 300
}

If I insert a 10th item between 2 and 3, I am going to have to recompute the row height which will consist in re-rendering the height of each item in the row (which is super slow).

I would then end up with three more values in my cache:

{
  // Previous values
  Id1-Id2-Id3: 400,
  Id4-Id5-Id6: 200,
  Id7-Id8-Id9: 300,

  // New values
  Id1-Id2-Id10: 400
  Id3-Id4-Id5: 200
  Id6-Id7-Id8: 300
  Id9-IdPlaceholder-IdPlaceholder: 150
}

So our cache table would keep growing for each combination and except if by luck an insertion or deletion, bring us to a case we already computed, most of the time the cache will not be used.

This is a simplified version of a cache strategy I tried to implement, in reality I also had to keep track of a reference of each item to make sure their content didn't change (which would make the cached value invalid)

Solution

Instead of caching per row/column we should cache per item. Once an item width and height has been cached, it is quick and easy to get the size of the row or column.

When inserting an item, only the new component will be rendered to be measured.
When removing or shuffling items, no component will have to be rendered

Also, our cache table will only contains as many entries as the number of items we have.
With the current cache, we could end up with an entry for each possible permutation.

Implementation

You can see how that would be implemented here: https://github.com/bvaughn/react-virtualized/pull/561/files

I also provided an example of how I have implemented the cache for my specific problem.

The PR is not ready:

• Maybe expose the interface to clearItemHeights, clearItemHeight, clearItemWidth, clearItemWidths.
• Replace item by cell, I found it confusing since you called the Row/Column cache, cellCache, when actually it doesn't cache anything about the cell. So I used item in the meantime but it is probably a poor choice.
• Write tests

But if you are interested to include those changes in react-virtualized, I can finish the work to make it clean.

[bvaughn]

Have you seen the idCellMeasurerCellSizeCache for CellMeasurer? It looks very similar to your perItemSizeCache unless I'm misunderstanding something.

CellMeasurer is only useful when you don't know the height and/or width of your cells ahead of time. It measures each cell once and then caches the measurements so it doesn't have to measure it again. Certain things (eg state) invalidate cached measurements and so you can also clear the cache.

As you pointed out, insertions or sorting can also invalidate measurements which is why the idCellMeasurerCellSizeCache implementation exists. It does a little more work of caching a measurement based on the underlying data id rather than the row/column number- (which is why it's not the default, because many virtualized lists aren't sortable). This enables the cached sizes to be reused even in cases like you describe above.

Based on PR #561, I think maybe you were unaware of this caching option? Admittedly this is my fault because I don't cover it very well in the docs. Sorry! You would use it like so:

import { CellMeasurer, Grid, idCellMeasurerCellSizeCache } from 'react-virtualized';

<CellMeasurer
  cellRenderer={cellRenderer}
  cellSizeCache={idCellMeasurerCellSizeCache}
  columnCount={columnCount}
  rowCount={rowCount}
>
  {({ getColumnWidth, getRowHeight }) => (
    <Grid
      {...gridProps}
      columnWidth={getColumnWidth}
      rowHeight={getRowHeight}
    />
  )}
</CellMeasurer>

If I misunderstood something, let's chat more.

[bvaughn]

Added to the docs here

[Mathieuu]

I am aware of idCellMeasurerCellSizeCache but it seems to me that this cache system still cache the height of an entire row or the width of an entire column no?

The goal of my PR is to cache the size of each cell (item) individually (instead of the whole row/column).

If I have:

Cell1, Cell2, Cell3
Cell4, Cell5, Cell6

And I cache the result with idCellMeasurerCellSizeCache, I would have a row height cache looking like:

{ 
   row1: 10,
   row2: 12,
}

But let's say that at the next re-render I replace Cell1 by Cell42:

Cell42, Cell2, Cell3
Cell4, Cell5, Cell6

Then I need to recompute the size of Cell42, Cell2, Cell3 right ?

With a per item cache, my cache would have looked like:

{ 
   cell1: 10,
   cell2: 11,
   cell3: 12,
   cell4: 8,
   cell5: 9,
   cell6: 10,
}

and after the change:

{ 
   cell1: 10,
   cell2: 11,
   cell3: 12,
   cell4: 8,
   cell5: 9,
   cell6: 10,
   cell42: 15, // Added to the cache, only this one will be re-rendered
}

With my fix, I will remember the height of Cell2 and Cell3 and will only recompute the size of Cell42.

[bvaughn]

I understand the difference now. That does seem like a useful option to support as well, yes!

Sorry for not catching this the first time. I'm on vacation at the moment and I just quickly glanced at the PR. I'll give it a closer look and more thought when I get the chance. 😄

[bvaughn]

This feature will be available in the upcoming RV release. Currently that release is tracked via PR #577. Going to close this issue (even though it's a bit premature, prior to the release) because it helps me to prune the issues list as I go to make sure I've pulled all of the things I want to pull into v9.

Thanks for the detailed write-up and the proposal here. Very helpful!