CellMeasurer optimizations

[kof]

Hey, I have seen you did a great job already. I am now about to drop my own custom implementation of the measurer and port everything to the latest react-virtualized.

A few things I noticed are not good enough for my use case:

Row height caching.

Current row height caching is done using the index. However in my case, it is not possible to cache by index, I need a different caching mechanism based on custom id's.

Row element caching.

Currently you create a row element twice, once for measuring, once for representation. I can introduce a caching in the user code, so element creation happens only once, however you might want to solve this in the library.

[bvaughn]

Hey @kof,

Not sure how I could accommodate cache-by-id, since react-virtualized doesn't know anything about the underlying data (only that there's a collection of N items). Do you have a proposal in mind? Let's chat about it. :)

I understand the appeal of managing row-element caching in the base library, but I'm not sure how it would be possible given the HOC approach of CellMeasurer. Again I would be open to suggestions here, but at least caching in user land is an option for the time being. :)

[kof]

• One option is to provide a callback to the user which can return the key for caching.
• Another option is to provide a getCachedSize callback and allow user code cache the height.

Row height caching in the user land is bit dirty right now, because there is no param for turning off the index based caching. One needs to call reset methods before every getRowHeight call.

[kof]

Element and size caching can be basically done in one caching logic and it is not very hard to do in user land anyways. So probably giving away that responsibility is not bad.

[kof]

One more option is to provide a separate HOC for caching, make it based on indexes by default, make this HOC cache elements and heights.

User can use such a HOC then as an example to implement any custom caching logic and create own caching HOC's.

[bvaughn]

Row height caching in the user land is bit dirty right now, because there is no param for turning off the index based caching. One needs to call reset methods before every getRowHeight call.

This hints at a problem though. You're implying that your underlying data (the ids) are not tied to index- and that the height varies per id. These 2 things would cause problems with react-virtualized since cell size (for a given index) is important.

That being said, react-virtualized is quick to recalculate its layout. The slow part is the rendering of a cell to measure its size. So if you were caching rendered cells (based on id) in user land, and you had a way to map index-to-id, then I'd think you should be able to tell react-virtualized to clear its cache without a significant performance hit (since the next set of measurements would be taken from your user land cache).

[bvaughn]

Another reason I shy away from caching the result of render operations is that it's unclear when I should purge the cache, which can lead to memory bloat. I think that's something that varies per-application, so it's another reason to leave it in user land.

[kof]

Yep, I agree, it may not fit all use cases and may need different caching strategies. So best thing would be to leave cache out of the library completely or make caching a separate optional HOC.

[bvaughn]

I like HOCs (obviously 😄 ) so I like that general idea.

Okay, so... I think we're settling on the fact that rendered-cell caching stays in user land (possibly with a HOC to help simplify it). But let's talk more about this row-height issue.

Can you explain to me why your data (ids) are shifting around within your collection (indexes)?

Also, if you were to be managing rendered-content-caching in user-land, then would that alleviate your performance concerns about CellMeasurer rendering you once for height and Grid (or whatever) rendering "again" for display? (Since the second render would be cached?)

You would still need to inform both that the underlying data (and thus the related cell sizes) may have changed though. (Grid has a method recomputeGridSize for this and CellMeasurer passes similar functions resetMeasurementForColumn and resetMeasurementForRow to its child function.

[kof]

Can you explain to me why your data (ids) are shifting around within your collection (indexes)?

My application is a chat with last-to-first message scrolling (reverse order). When I scroll back, index 0 becomes a different message than it was before.

Also, if you were to be managing rendered-content-caching in user-land, then would that alleviate your performance concerns about CellMeasurer rendering you once for height and Grid (or whatever) rendering "again" for display? (Since the second render would be cached?)

CellMeasurer would still mount the element to the dom and detect height/width on it using DOM properties. This is still dangerous because we never know when they might hit our performance, the only way is to ensure to touch dom as rare as possible.

You would still need to inform both that the underlying data (and thus the related cell sizes) may have changed though. (Grid has a method recomputeGridSize for this and CellMeasurer passes similar functions resetMeasurementForColumn and resetMeasurementForRow to its child function.

yep I am currently resetting both

      this.cellMeasurer.resetMeasurements()
      this.virtualScroll.recomputeRowHeights()

[bvaughn]

Ah, gotcha. Reverse order scrolling. Makes sense. :D

Roger that about the mounting/layout hit. Okay. So let's talk about the interface to this cache. Currently, CellMeasurer just keeps an object that maps column and row indices to cached sizes. I could imagine this being moved into a caching util that could be overridden via a prop. Maybe something with an interface like...

interface CellMeasurerCache {
  clearAllColumnWidths(): void;
  clearAllRowHeights(): void;
  clearColumnWidth(index: Number): void;
  clearRowHeight(index: Number): void;
  getColumnWidth(index: Number): Number;
  getRowHeight(index: Number): Number;
  hasColumnWidth(index: Number): Boolean;
  hasRowHeight(index: Number): Boolean;
  setColumnWidth(index: Number, value: Number): void;
  setRowHeight(index: Number, value: Number): void;
}

...then you could manage your own mapping of index-to-id in user land. Thoughts?

This interface would support a backwards-compatible release which is important to me. :)

I think this change would make this.cellMeasurer.resetMeasurements() and this.virtualScroll.recomputeRowHeights() very fast.

[kof]

Do you think we could have a caching interface for both, elements and height?

[kof]

For elements it would need to be a component, because it will need to do shallowEqual of data. However maybe there is a away to do it as a separate caching class too.

[kof]

In your interface example you have a typo with types.

[bvaughn]

Do you think we could have a caching interface for both, elements and height?

I thought we agreed to leave caching elements in user land (for the time being)? Since cache invalidation / expiration is kind of tricky to implement in the lib.

[bvaughn]

Although I assume your CellMeasurerCache implementation could also cache rendered cells.

[kof]

I thought we agreed to leave caching elements in user land (for the time being)? Since cache invalidation / expiration is kind of tricky to implement in the lib.

I thought we were talking about both, heights caching and elements caching are equally tricky. So when we are able to create a good interface for both and have an optional class handling it - why not.

[kof]

Although I assume your CellMeasurerCache implementation could also cache rendered cells.

Yes it does it already. I am just trying to simplify the whole thing if it is possible, because the logic for caching heights and elements seems to be mostly the same.

[kof]

What if we reduce the caching interface to something minimal and universal for any data? Kinda universal index based caching interface.

[bvaughn]

I thought we agreed to leave caching elements in user land (for the time being)? Since cache invalidation / expiration is kind of tricky to implement in the lib.

I thought we were talking about both, heights caching and elements caching are equally tricky. So when we are able to create a good interface for both and have an optional class handling it - why not.

They aren't equally tricky, actually. Caching numbers is a pretty lightweight thing. Caching rendered React elements would cause memory usage to climb much faster. (Basically the "expiration" problem.)

Although I assume your CellMeasurerCache implementation could also cache rendered cells.

Yes it does it already. I am just trying to simplify the whole thing if it is possible, because the logic for caching heights and elements seems to be mostly the same.

I think this is a reasonable thing to leave in user land. No reason you couldn't cache both with the same object, but I don't think I want to make it an official part of the interface. I don't think it's complex enough to need its own HOC anyway. It would just be a getter function and a map of index (or id, or whatever) to rendered object, right?

What if we reduce the caching interface to something minimal and universal for any data?

I think that would make it a bit harder to work with. For example, if it's a generic caching util, it would have an interface more like this:

interface Cache {
  clearAll(): void;
  clear(id: any): void;
  get(id: any): Number;
  has(id: any): Boolean;
  set(id: any, value: Number): void;
}

But at this point you wouldn't be able to use the same object to cache columns and rows. You'd have to have 2 (and a 3rd to cache rendered cells). Seems like this would make things more complicated on end users.

[kof]

They aren't equally tricky, actually. Caching numbers is a pretty lightweight thing. Caching rendered React elements would cause memory usage to climb much faster. (Basically the "expiration" problem.)

This is right. However if it is all replaceable, shouldn't be a big deal once it is a problem. If your concern is to cache elements by default in the lib - you could make it optional and false by default.

But at this point you wouldn't be able to use the same object to cache columns and rows.

Yep, you would need a cache instance per use case. I am not sure this is less nicer. The interface itself is nicer, because simpler names and less methods. When user doesn't want to have a custom caching implementation, library creates the cache object automatically, user doesn't need to do anything.

In the rare case where user wants to have a custom caching logic like me, he created an own caching class, now he will need to create 2-3 instances of it and pass them to proper component. It looks actually very nice to me, based on imagination). Also user could pass the custom caching class itself to the component and let component instantiate it.

[bvaughn]

I still prefer the simplicity of a single cache (mentioned here) for cell sizes. I think it fits better within the rest of the Api.

I think it's reasonable to leave rendered-cell-contents entirely in user land. I don't see a need for an explicit interface for this. There's only 1 connection point (the cellRenderer method itself, a getter). Given that the default behavior is (and would continue to be) no-caching* then I don't think there would be any additional methods to add. (Put another way, when would Grid ever call clear or clearAll for the rendered cell cache? When would it ever call has or set? It wouldn't.)

1. Grid does temporarily cache cells when a user is scrolling. This cache is immediately flushed once scrolling stops though. This helps when performance is most needed without introducing any tricky expiration problems. (I purge the cache once the scroll is complete each time, so I don't have to worry about a growing memory footprint.)

[kof]

All right then, maybe my suggestions are over engineered, maybe it is enough to just make the heights caching optional in CellMeasurer.

[bvaughn]

Didn't mean to suggest they were over-engineered. I think you're focused on an application usage and I'm trying to think generically of library usage. We're just looking at it from different angles. :)

I am okay with adding a cache interface for cell sizes. Hopefully that will enable performance wins for your user case. :)

[kof]

Just found the real bottleneck, I was measuring performance of the entire _measureCell call, which is pretty bad in my case. I was thinking it is the element creation step, but it turns out it is the renderSubtreeIntoContainer call.

renderRow: 0.292ms
renderSubtree: 17.716ms

[bvaughn]

Good to know. Caching heights will help a lot with this then, even if you didn't cache rendered rows. :)

[kof]

My problem is even worth, it is too slow on initial render, it spends 20-50ms on every message, after rendering 30, the slowness hurts the ux

[bvaughn]

Ah, worse? Hm. Any other ideas?

[kof]

Trying to find a way to not just reuse the element, but to reuse the whole mounted thing, so that there is almost no overhead for cell measuring.

[bvaughn]

Hm... this cache interface could actually provide an escape hatch to break out of the React ecosystem entirely... if your content is just text, you could use a single hidden/offscreen container to render into and measure...

[kof]

So the problem is how to clean up the measured rows if they are not needed for visual rendering?

[bvaughn]

Well, that's a problem. The other is how to coordinate this kind of hand-off between CellMeasurer and Grid.

[kof]

There might be a way to decouple those 2 also in this approach, will need some grid modifications though.

[bvaughn]

I'll admit up front that I'm reluctant to modify Grid for this.

[kof]

And I know why)))) Grid code is way too complex....

[bvaughn]

The amount of performance tuning and edge-case handling that's gone into it is more complicated than you'd expect.

[bvaughn]

I don't know if I'd call it "too complex".

[bvaughn]

I didn't add features or code just for the fun of it.

[kof]

Too complex means for me that understanding of that code is very hard. Doesn't mean complexity was invented for fun.

[bvaughn]

Haha, gotcha. 😁 No worries. It is also sometimes hard for me to understand if I haven't looked at it in a while. That's why I write so many tests and inline comments.

[kof]

From what I can see, modification in Grid would need allow having "ghost" cells, which are visually hidden and are ignored by auto positioning in the grid.

Every row can be wrapped into a CellMeasurer HOC. CellMeasurer measures it's size, then tells the grid (not sure how) that the row is measured now and can be used (ghost mode off)

Once Grid knows that a cell can be used, it uses it, if grid doesn't need it because (like you say) it's been scrolled away or jumped, grid removes the ghost cell.

[bvaughn]

Unfortunately I don't have the bandwidth for any refactoring approaching the scale of what would be required to try out this idea.

[kof]

I have been also trying to do the following approach:

• wrap every row in a CachedRenderer HOC
• once it is rendered clone the dom (node.cloneNode(true))
• once it is rendered again and we have a clone, don't render children, render only wrapper, insert cloned children directly via dom.

There is one problem though ... events handling doesn't work. Didn't find a way to active events handling on manually inserted dom nodes.

[bvaughn]

Hm. Afraid I don't have any experience in that area (working with cloned elements) so I'm not of any help.

[kof]

Oh of course it won't work, handlers are registered once it's been measured, after that it was unmounted. In the second render, I don't do any createElement calls with handlers ... #selfrealized

[rexmondo]

Thanks, @bvaughn and @kof for the discussion in this thread, it has enabled me and my team to get a solution for a very similar problem we were having. I have a notification component that is displayed in reverse chronological order, where each notification has a unique height that is fixed through its lifetime, mounted inside a parent that can filter and reorder the collection. I needed a way to get the cache to work off a unique ID inside the data entity instead of the rowIndex, and making my own cache did the trick!

I figured I would post my solution here since @bvaughn asked for an example in #341 (comment). I broke this out into a wrapper component and a cache and I will give you what the invocation looks like at the callsite too.

Here's the first part, IdCellSizeCache.js

export default class IdCellSizeCache {
  constructor(baseCollection, lookupFn) {
    this.baseCollection = baseCollection;
    this.lookupFn = lookupFn.bind(this);
    this.rowHeightCache = {};
    this.columnWidthCache = {};
  }

  /*
   * new methods
   */
  updateCollection(newCollection) { this.baseCollection = newCollection; }
  getId(index) { return this.lookupFn(this.baseCollection, index); }

  /*
   * required methods
   */
  clearAllColumnWidths() { this.columnWidthCache = {}; }
  clearAllRowHeights() { this.rowHeightCache = {}; }
  clearColumnWidth(index) { delete this.columnWidthCache[this.getId(index)]; }
  clearRowHeight(index) { delete this.rowHeightCache[this.getId(index)]; }
  getColumnWidth(index) { return this.columnWidthCache[this.getId(index)]; }
  getRowHeight(index) { return this.rowHeightCache[this.getId(index)]; }
  hasColumnWidth(index) { return this.columnWidthCache[this.getId(index)] >= 0; }
  hasRowHeight(index) { return this.rowHeightCache[this.getId(index)] >= 0; }
  setColumnWidth(index, value) { this.columnWidthCache[this.getId(index)] = value; }
  setRowHeight(index, value) { this.rowHeightCache[this.getId(index)] = value; }
}

the wrapper component, called VariableHeightList.jsx

import React from 'react';
import Immutable from 'immutable';
import { AutoSizer, CellMeasurer, VirtualScroll } from 'react-virtualized';

import IdCellSizeCache from './IdCellSizeCache';

export default class VariableHeightList extends React.Component {
  static propTypes = {
    /**
     * The collection that the list will be based off of
     */
    baseCollection: React.PropTypes.oneOfType([
      React.PropTypes.instanceOf(Immutable.Map),
      React.PropTypes.instanceOf(Immutable.List),
    ]).isRequired,

    /*
     * The function used to map indexes to collection ids
     * the signature should be (baseCollection, index) -> unique collection item id
     */
    idLookupFunction: React.PropTypes.func.isRequired,

    /*
     * The index -> element function used to measure and render the list items
     */
    elementGenerator: React.PropTypes.element.isRequired,
  };

  constructor(props) {
    super(props);
    const { baseCollection, idLookupFunction } = props;
    this.SizeCache = new IdCellSizeCache(baseCollection, idLookupFunction);
  }

  componentWillReceiveProps(nextProps) {
    // use strict equality checking (shallow compare) to determine whether the
    // cache needs a new index -> id map
    if (this.props.baseCollection !== nextProps.baseCollection) {
      this.SizeCache.updateCollection(nextProps.baseCollection);
    }
  }

  render() {
    const { elementGenerator, baseCollection } = this.props;
    const elementCount = baseCollection.count();

    return (
      <AutoSizer>
        {({ height, width }) => (
          <CellMeasurer
            cellRenderer={({ rowIndex }) => elementGenerator(rowIndex)}
            cellSizeCache={this.SizeCache}
            columnCount={1}
            rowCount={elementCount}
            width={width}
          >
            {({ getRowHeight }) => (
              <VirtualScroll
                height={height}
                rowCount={elementCount}
                rowHeight={getRowHeight}
                rowRenderer={({ index }) => elementGenerator(index)}
                width={width}
              />
            )}
          </CellMeasurer>
        )}
      </AutoSizer>
    );
  }
}

and here's what the callsite looks like

      <VariableHeightList
        baseCollection={notifications}
        idLookupFunction={(cacheNotifications, index) => (
          cacheNotifications.getIn([index, 'noteId'])
        )}
        elementGenerator={index => (
          <Notification
            key={`${index}-${notifications.getIn([index, 'noteId'])}`}
            notification={notifications.get(index)}
          />
        )}
      />

Great work with react-virtualized, too @bvaughn, we were in quite the pickle when we realized that Facebook's fixed-data-table component was being dumped but we switched and realized we could virtualize way more stuff in our application than we even thought, and this has been a huge boon to our optimization process.

[kof]

If your company makes some profit, try to convince your boss to become a sponsor or baker. @bvaughn totally earned it. I have tried too, but my company is currently in a shift between seed and A-round and tries to stretch the money until then ...

[rexmondo]

Hopefully by the time this gets out and starts making money we can have a little bit to put back into the community that has enabled us to put our system together. React people all do such great work, its a very enjoyable community to watch and work with.

[rexmondo]

Oh, and one more thing @bvaughn, most of the actual virtualized code is lifted straight from the wizard on the excellent documentation, but one thing I did notice is that the CellMeasurer and VirtualScroll functions were not wrapped in {} and it took me a few minutes of scratching my head before i noticed it.

[bvaughn]

D'oh! Thanks for pointing that out @rexmondo. I'll update the wizard this afternoon. :)

I'm glad to hear it's useful for people. Put it together on a whim. Haven't used it myself yet. :D

Thanks for the kind words (both of you) and for sharing your approach too. Really cool to see!

[thealjey]

@bvaughn how about using canvas api to measure the pixel size of text (or at least provide an option to the user to specify something like a measurer function)?
sure, we would need to know the font face, font size, etc, but it would be much more performant than using the DOM
I've done it before manually (that project didn't even use react at all), and I've seen an amazing performance improvement over any DOM based solution

[bvaughn]

There's nothing preventing you from doing this instead of using CellMeasurer. There's not a lot of react-virtualized-specific magic in CellMeasurer other than this and this but that would be easy enough to do in a custom measuring component. And if you think the custom measuring component is generically useful enough, submit it as a PR! 😄

[thealjey]

😃 good point! thanks for a quick response) this project is awesome, btw

[bvaughn]

Thank you~