Support just-in-time measured content

bvaughn commented 6 years ago

In order to avoid adding cost to existing list and grid components, create a new variant (e.g. DynamicSizeList and DynamicSizeGrid). This variant should automatically measure its content during the commit phase.

MVP

The initial implementation of this could work similarly to how CellMeasurer works in react-virtualized:

Content is measured only if no current measurements exists.
Measurements need to be reset externally (imperatively) if something changes.
Cells at a given index can only be positioned after all cells before that index have been measured.

Goal

This component could perform better if we removed the third constraint above, allowing random access (by either item index or scroll offset) without measuring the preceding items. This would make react-window much more performant for use cases like chat applications.

This would also unlock the ability to use a ResizeObserver (via react-measure) to automatically detect item sizing and remove the position and measurements cache entirely. This would remove the need for imperatively resetting cached measurements and dramatically improve the API.

In order for the above to be possible, the dynamic list/grid components would need to use a dramatically different approach for mapping offset to index and vice versa. (This comment about "scroll anchoring" in react-virtualized has some nice visuals.) Essentially, we would need to do something like this:

Estimate total size based on the number of items multiplied by a estimatedItemSize prop. (This estimated size won't need to be adjusted, since the mapping described below doesn't is fuzzy.)
When scroll position changes, compare the new offset to the previous offset. If the delta is greater than some [to be determined] threshold, set the new offset as the "scroll anchor". Map the offset to an estimated index (e.g. divide the offset by total estimated scrollable size and multiply that by the number of items in the collection). Store this mapped index as the "anchor index". For example, if the list described by the image below had 250 items, the "anchor index" would be 132.

When scroll position changes, if the delta is less than the threshold, choose which new items to render relative to the anchor index. Position these items relative to the previously positioned items. Continuing with the example above, if the list was scrolled by a small amount (200px) then 200px worth of additional rows would need to be appended below the previously positioned items:

The above approach has only one major downside: aligning items correctly at list boundaries. If item indices are estimated (as described above) then they likely won't line up exactly with the beginning or end of the scrollable area.

The end could potentially be accounted for by adjusting the total estimated size as the user scrolls closer to the end (although this might make scrolling feel janky).
The start of the list is harder to handle, since the first item needs to align with offset zero while still appearing to connect contiguously with items from some offset greater than zero. Perhaps another threshold could be used, a "safe zone", near the start of the list (e.g. if the scroll offset is less than some absolute value) which would force the list to measure all cells up to that point so they align correctly. The cost of this forced measurement would be relatively low, since it would only be a small number of items.

The one case that would still not be handled correctly with the above approach would be a scroll anchor that is set outside of the "safe zone" but a current scroll that goes inside of the safe zone (as shown below). If the user scrolls slowly back toward the beginning of the list, it may be difficult to align the first cell with zero without introducing scroll janky.

bvaughn commented 6 years ago

Work in progress for MVP available at https://github.com/bvaughn/react-window/compare/master...issues/6

techniq commented 6 years ago

I use this within mui-downshift and currently still use UNSAFE_componentWillReceiveProps, although I plan to try to port to react-window in the near future (once the dynamic content height is available).

luoboding commented 6 years ago

is this a reusable mechanism in UITableView in IOS ？

bvaughn commented 6 years ago

@luoboding I don't understand your question. Could you elaborate?

luoboding commented 6 years ago

@bvaughn sorry, my friend, my english is not very good.

i have a problem in my project, i have thousands of options in select element, it get very slow and jammed when page reload, i tried to write a component to make it better, i was a IOS developer, i know a reusable mechanism in UITableView in IOS, if i need a 500px height select element, i configure option-element's height to 100px, so i just need create (Math.floor(500 / 100)) number of option element and capacity of queue(current displayed datasource queue), when i scroll select element up or down, just push or pop into the queue to re-render it.

i want import react-window in my project, does it work like i mentioned?

bvaughn commented 6 years ago

What you're describing is how react-window (and windowing, or occlusion culling, in general) works. It's not really related to this issue though. This is about just-in-time measuring the windowed content. In your case, objects have a fixed height– so you can use the FixedSizeList component: https://react-window.now.sh/#/examples/list/fixed-size

yuchi commented 6 years ago

Nice to see anchoring natively addressed in react-window.

By the way sorry if I raised the bar a little bit too much on diagrams… 😅

nihgwu commented 6 years ago

@bvaughn when will you release this feature, I'm looking for that

bvaughn commented 6 years ago

I published 1.0.0 without this functionality because I'm having trouble finding the time (and energy) to finish this right now. Still plan to add it in the future. No estimate on when.

bvaughn commented 6 years ago

Looks like Polymer's "iron list" uses a similar technique as what I'm proposing here: https://github.com/domenic/infinite-list-study-group/blob/master/studies/Polymer-iron-list.md#virtual-list-sizing

kevinder commented 5 years ago

this would be really useful for us, right now it seems like we have to keep CSS in sync with component logic that duplicates the height computation just to pass it to the virtual list.

carlosagsmendes commented 5 years ago

@kevinder can you share how you are addressing just-in-time measured content? Thanks in advance

ghost commented 5 years ago

@carlosagsmendes not sure if this will help but here is what I am doing when using this to display chat history:

1.) In the constructor create a ref for the list and for my ChatHistory component:

  constructor(props) {
    super(props);
    this.listRef = createRef();
    this.chatHistoryRef = createRef();
    this.listHeight = 0;
  }

I then pass the refs down to the ChatHistory which is responsible for rendering the list

2.) In componentDidMount of the parent component I use the ChatHistory ref to get the height of the element:

componentDidMount() {
    this.listHeight = this.chatHistoryRef.current.offsetHeight;
}

3.) In the parent component I maintain an array in it's state with the chathistory details. When adding a new item to that array I do it like this:

  // find out how many pixels in height the text is going to use
  const size = getSize({
    text: displayText,
    className: styles.message,
  });

  let { height } = size;
  height += 20; // adds some spacing in pixels between messages
...rest of items needed for the chat history item..add them all to an array and update state

getSize is based on https://github.com/schickling/calculate-size but I modified it to support accepting a class name. That class is the same one used as the container for displaying the individual messages

I'm sure there's a better way to achieve this but it seems pretty fast and I haven't hit any issues yet

bvaughn commented 5 years ago

@osdlge: Any chance you have a demo of this anywhere I could check out– like Code Sandbox (or similar)?

ghost commented 5 years ago

@bvaughn sure thing, I extracted the relevant parts of my code to https://codesandbox.io/s/5z282z7q1l

bvaughn commented 5 years ago

Thank you for sharing! 😄

bvaughn commented 5 years ago

I've pushed some work in progress to an initial approach on lazily measured content to a branch named issue/6

I've also deployed a demo: https://react-window-next.now.sh/#/examples/list/dynamic-size

carlosagsmendes commented 5 years ago

Very cool.

I'm still trying to make sense of the general problems with infinite scrolling while going through the issue/6 branch source and this discussion. So the question following question may not make sense, but here it goes since I would really like to understand this further:

Is the above mention to 'Scroll Anchor' related to scroll Anchoring as a technique like in the linked article or the CSS Scroll Anchoring specification?

Thanks in advance

bvaughn commented 5 years ago

It's kind of tangentially related to your first link, but not to the second one. It's just a term I chose to use for the issue because it made sense to me, not because it's related to any other spec or proposal.

bvaughn commented 5 years ago

I've also published a pre-release version of react-window to NPM as "next" (e.g. yarn add react-window@next).

You can play around with it by forking this Code Sandbox: https://codesandbox.io/s/5x8vlm0o7n

akraines commented 5 years ago

I just tested it out. I tried 10000 paragraphs and tried to jump to the end. It was jerky. If I understood correctly, it should have only measured the rows estimated to be at the end an therefore it should have jumped instantaneously to the end. Is this correct?

On 12 Oct 2018, at 12:53, Brian Vaughn notifications@github.com wrote:

I've also published a pre-release version of react-window to NPM as "next" (e.g. yarn add react-window@next).

You can play around with it by forking this Code Sandbox: https://codesandbox.io/s/5x8vlm0o7n https://codesandbox.io/s/5x8vlm0o7n — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/bvaughn/react-window/issues/6#issuecomment-429271555, or mute the thread https://github.com/notifications/unsubscribe-auth/AOf2h7RmSEyGmyrEdMY6GgyZFjCKlDDFks5ukGafgaJpZM4UTb3P.

bvaughn commented 5 years ago

No, the initial branch I've pushed doesn't implement the algorithm described in this issue. It takes a more naive approach the requires measuring earlier content before rendering later content.

Sorry for the confusion!

On Fri, Oct 12, 2018, 6:34 PM akraines notifications@github.com wrote:

I just tested it out. I tried 10000 paragraphs and tried to jump to the end. It was jerky. If I understood correctly, it should have only measured the rows estimated to be at the end an therefore it should have jumped instantaneously to the end. Is this correct?

On 12 Oct 2018, at 12:53, Brian Vaughn notifications@github.com wrote:

I've also published a pre-release version of react-window to NPM as "next" (e.g. yarn add react-window@next).

You can play around with it by forking this Code Sandbox: https://codesandbox.io/s/5x8vlm0o7n <https://codesandbox.io/s/5x8vlm0o7n

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub < https://github.com/bvaughn/react-window/issues/6#issuecomment-429271555>, or mute the thread < https://github.com/notifications/unsubscribe-auth/AOf2h7RmSEyGmyrEdMY6GgyZFjCKlDDFks5ukGafgaJpZM4UTb3P .

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/bvaughn/react-window/issues/6#issuecomment-429282228, or mute the thread https://github.com/notifications/unsubscribe-auth/AABznR5R1N0ErukleIfvaLQORF_NECgRks5ukHBHgaJpZM4UTb3P .

gnir-work commented 5 years ago

Hey, I wanted to ask if there is an estimate for an official release?

My team uses react-virtualized for a new project we started however we need the functionality of scrolling up and jumping to specific row index (as you can assume our rows have dynamic content, containing images and other changing content).

Would you recommend migrating to react-window in its alpha release? Or should we wait for an official release?

Also if there is any way i can contribute to finishing this feature i would love to help out 😄

bvaughn commented 5 years ago

Unfortunately I can't commit to a release timeline at the moment because I haven't done a lot of testing and I don't know what kinds of issues I'll run into when I do (or how long it will take to fix them).

If you'd like to contribute, one way would be to test the alpha release and let me know how well it works, and if you find any bugs.

I'll probably be focusing more on this soon, but I can't say how soon. Especially for the next week or two I'm distracted by React conf and getting the 16.6 release ready.

piecyk commented 5 years ago

@bvaughn great work 👏 Finally have some time to play around. 🕹

It looks like we need some tweaks when hiding list with display: none For example you have page with two tabs and want to switch between them without loosing your current state ( scroll position etc.), imho it's not a rare use case.

Simple Code Sandbox presenting the issue: https://codesandbox.io/s/p7vq18wmjq

It's happening because when we trigger display none, all children will have offsetHeight === 0 resize observes kiks in and updated's new values. react-window should not care for this situations if caller decided to hide it, basic should handle it by blocking handleNewMeasurements

if this line https://github.com/bvaughn/react-window/blob/issues/6/src/DynamicSizeList.js#L443 would change to

handleNewMeasurements: instance._handleNewMeasurements

then we can override default logic

let _handleNewMeasurements

<DynamicSizeList  
  ref={current => {
    if (current) {
      _handleNewMeasurements = current._handleNewMeasurements
      current._handleNewMeasurements = (...args) => {
        if (!isHidden) {
          return _handleNewMeasurements(...args)
        }
      }
    }
  }}
  {...otherProps}

bvaughn commented 5 years ago

I pushed an update to this branch (and published a new @next tag to NPM) that fixes the Firefox smooth scrolling bug by using margin-top to account for resized items while scrolling is in progress. It's more complicated than I'd like but I don't know of a better way to handle this at the moment. (I also need to do some more testing of this approach, because I think that it might have some rough edges still in extreme cases.)

I appreciate the feedback above, @piecyk. I haven't had time to dig into it yet. (This is still kind of just a side project for me at the moment.)

bvaughn commented 5 years ago

Seems like I may be able to remove the margin hack in favor of scrollBy for Firefox at least. Need to test IE and Edge first though. They may have their own challenges.

piecyk commented 5 years ago

Yeah @bvaughn i know, awesome work 👏 Don't know how you find the time! 🥇Kudos to you!

But let's back to the issue when the list is in some DOM element that is hidden with display none, basic we need to check if the wrapper has height, width if not we don't want to start rendering ( current it will try to render whole list ) Will try tomorrow to fix it ( have something stash )

bvaughn commented 5 years ago

Yup. I understand the core of the issue you're describing. I dislike the idea of hacking around it by overriding/monkey-patching more instance methods though, so I'd like to give it some more thought first.

marcneander commented 5 years ago

Seems like the @next package is broken?

https://codesandbox.io/s/5x8vlm0o7n

vtripolitakis commented 5 years ago

Don't know if that's the proper place to leave a question, so excuse me if I'm wrong. So, in short:

I've used DynamicSizeList along with AutoResizer and in general it works, nicely. Kudos!
I've been asked to introduce Rows whose content can expand (adding an extra div with supplementary information) and retract.
I've also added (via redux) a prop on these Rows that listens for global expand/retract actions.
Fun stuff starts. I click expand/retract and everything looks great!
If I scroll a little and then expand/retract all the rows, the number of retracted rows is the same as to that of the expanded rows. If I expand retract again, number goes to half and so on. (i.e. 30 rows retracted -> 10 expanded ->click retract -> 10 rows retracted -> click expand -> 3 rows expanded -> click retract -> 3 rows retracted).

I tried to reload the itemData by supplying a different yet same object with the JSON.parse(JSON.stringify(data)) hack. No luck :-(

I suspect a miscalculation of the height. Any idea to overcome this issue?

carlosagsmendes commented 5 years ago

Could you share a codesandbox example? I need to do something similar so maybe we can help each other

carlosagsmendes commented 5 years ago

@vtripolitakis I've just found an example with expandable rows. Here's the link to the discussion

vtripolitakis commented 5 years ago

@carlosagsmendes thanks for this, but my case study is a little different as I use the the DynamicSizeList :-(

vtripolitakis commented 5 years ago

So I found the reason of the issue: state.scrollOffset was taking negative values.

on src/DynamicSizeList.js we need to add the following code on line 299

if (sizeDeltaForStateUpdate < 0) {
          sizeDeltaForStateUpdate = 0;
        }

bvaughn commented 5 years ago

Hm... I wouldn't expect that fix to be right, at a glance. A size delta might legitimately be negative, no?

Maybe we should have a guard (Math.max(0, prevState.scrollOffset + sizeDeltaForStateUpdate)) around where the state.scrollOffset value is updated?

vtripolitakis commented 5 years ago

Hello, as I debugged my case sizeDeltaTotal took negative values and accordingly made sizeDeltaForStateUpdate negative, yielding a negative state.scrollOffset after state update.

This happened when I expanded and retracted items and then scrolled to the top having scrollOffset 0 and direction backwards. Then If I expand and retract a few times, I got the negatives. Yes, your suggestion should be equally good. ~Testing it right now.~ Works properly.

superandrew213 commented 5 years ago

@marcneander try version 1.4.0-alpha.1

piecyk commented 5 years ago

Regarding ignoring resize events when list is hidden, maybe something like this https://github.com/piecyk/react-window/commit/acfd88822156611cfd38872acdafbbefd2d0f78f @bvaughn what do you think ?

xaviergmail commented 5 years ago

I'm trying to add auto-scroll in a chatbox-style app and I'm running into this issue: DynamicSizeList does not support scrolling to items that have not yet measured. scrollToItem() was called with index 111 but the last measured item was 110.

I'm trying to call scrollToItem(items.length-1) in componentDidUpdate

Is this intended behavior?

bvaughn commented 5 years ago

Yeah, maybe something like that could work @piecyk 👍

Is this intended behavior?

Doesn't sound like it @xaviergmail, no. Maybe a bug.

trxcllnt commented 5 years ago

hey @bvaughn I don't mean to derail this issue, but I wanted to chime in to say that there's a neat sparse array implementation from the Flex 4 DataGrid internals that may be able to help here. I know Flash is :-1:, but the last version of Flex actually had a pretty great virtualized layout engine... because Flash :-)

The LinearLayoutVector is a sparse array for mapping between item indices and pixel positions in a single dimension. The three basic operations are:

interface LinearLayoutVector {
   start: (index) => position;
     end: (index) => position;
  indexOf: (position) => index;
}

Internally it allocates buckets in powers of 2 for storing item positions (the specific power can be tuned to better accommodate larger or smaller item sizes). This enables constant-time O(1) index -> position lookups, and an efficient linear block scan for position -> index lookups. It supports padding, gaps, default sizes, and random-access insertion, removal, and updates.

I ported it to JS about 6 years ago when I was doing a lot of virtualized UIs for mobile. It could use an update to ES6 for readability, and could probably squeeze out more speed by switching to typed arrays, but the basic logic is sound.

I submitted a draft PR to react-virtualized a few weeks back that switched out the internals of CellSizeAndPositionManager with the LLV and it did solve a few perf/cache invalidation things. If you're down, I'd be happy to submit a similar PR to react-window in the next few weeks.

bvaughn commented 5 years ago

Hi @trxcllnt 👋

If you'd be interested in sharing a PR, I'd be happy to take a look. You would want to make it against the issues/6 branch (WIP PR #102).

At a glance, linear-layout-vector doesn't look like it's got any tests or being used too heavily, so I would have a little bit of initial reluctance but I'd still be willing to take a look. I'd also want to look at how much weight it adds to a bundle after being uglified+minified but I wouldn't expect it to add too much. 😄

trxcllnt commented 5 years ago

@bvaughn no sweat, I totally understand. It was a thing I did years ago over xmas IIRC. I'll clean it up and ensure it lands with a full test suite. Don't worry about incurring an extra dependency either. It's such a small class, I'm happy to contribute it directly.

After I commented, I remembered I had the demo I did the port for: https://github.com/trxcllnt/virt-list. Hit up that GH pages site and throw the movies list left and right (this was related to some discussions about render perf we were having in the iOS team at Netflix).

milieu commented 5 years ago

@bvaughn Thank you for all of the work that has gone in the issues/6 branch for the past year! I am currently testing ^1.6.0-alpha.1 and plan on shipping to production with that version.

Thought I'd post what I needed to do in order to work with the new DynamicSizeList for anyone else looking at this issue and using the latest on the branch.

Following the docs linked above and those generated from the issues/6 branch will lead to

Warning: Function components cannot be given refs. Attempts to access this ref will fail. Did you mean to use React.forwardRef()?

and so the fix was to imitate what you do in tests and...

import { DynamicSizeList as List } from 'react-window';
import AutoSizer from 'react-virtualized-auto-sizer';

// in constructor(props) for handling scrolling
this.listRef = React.createRef();

// in render()
const allItems = [...];
const Renderer = ({ forwardedRef, style, index, ...rest }) => (
  <div ref={forwardedRef} style={style}>
    <MyCoolComponent index={index} otherProps={otherPropsBasedOnAllItems} />
  </div>
);

const RefForwarder = React.forwardRef((props, ref) => (
  <Renderer forwardedRef={ref} {...props} />
));

return <div style={{ display: 'flex', flexDirection: 'column', height: '100%' }}>
  <div style={{ flexGrow: 0, flexShrink: 0, width: '100%', position: 'sticky', top: 0, zIndex: zIndexHideLayers }}>
    <MyCoolComponentThatControlsScrolling listRef={this.listRef} />
  </div>
  <div style={{ flex: 1, width: '100%' }}>
    <AutoSizer>
      {({ height, width }) => (
        <List ref={this.listRef} itemCount={allItems.length} width={width} height={height}>
          {RefForwarder}
        </List>
      )}
    </AutoSizer>
  </div>
</div>;

My example probably includes more than what you'd want on that docs page, but hopefully will make the doc update easier for you

Feedback on the current version of the branch? 💯 works well 🎉 thanks again for all the work!

edit: DynamicSizeList seriously makes this library so easy to use now.

bvaughn commented 5 years ago

Thanks for sharing the details! When I get some bandwidth to pick this issue back up, I'll dig into them.

bvaughn commented 5 years ago

I think this approach may be usable along with the original proposal in this issue.

Rather than using the item's previous size, we could just use the estimated sizes– and refine with actual sizes as someone scrolls. (I don't think there's an important distinction between "previously measured size" and "estimated size" except for the fact that the previously measured size is likely to be more accurate. Still, this might be an acceptable trade off since it would allow us to jump to arbitrary places in the data without rendering things that came before, and it would free us up from having to maintain an item size cache.)

I think this could simplify the scroll anchoring problem significantly. We could just do the initial jump (as described) and then pretend everything "before" (above or left) was exactly the estimated size. Then as we scroll, refine.

Could maybe work?

mgustin12 commented 5 years ago

@bvaughn Will this fix the issue that @xaviergmail addressed, with initially scrolling to the "bottom" like a chat? I created a codesandbox of an example of it not working. If not, are there any workarounds?

https://codesandbox.io/s/vr648ywy3

bvaughn commented 5 years ago

Let's keep the comments on this issue focused on API discussion, not troubleshooting.

I suggest Stack Overflow for asking questions.

sirlukecoop commented 5 years ago

Is it possible to expose the resetAfterIndex in this API? I add, edit, and remove from my DynamicSizeList and, at least from what I can gather, this would be the method to call to fix heights up, yes?

bvaughn / react-window

Support just-in-time measured content #6

MVP

Goal