Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Support just-in-time measured content #6

Open
bvaughn opened this Issue May 30, 2018 · 48 comments

Comments

Projects
None yet
@bvaughn
Copy link
Owner

bvaughn commented May 30, 2018

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:

  1. Content is measured only if no current measurements exists.
  2. Measurements need to be reset externally (imperatively) if something changes.
  3. 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.

screen shot 2018-06-10 at 11 58 38 am

  • 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:

screen shot 2018-06-10 at 12 01 01 pm

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.

screen shot 2018-06-10 at 5 04 42 pm

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.
screen shot 2018-06-10 at 5 08 26 pm

@bvaughn bvaughn self-assigned this Jun 8, 2018

@bvaughn bvaughn changed the title CellMeasurer Support just-in-time measured content Jun 10, 2018

@bvaughn

This comment has been minimized.

Copy link
Owner Author

bvaughn commented Jun 17, 2018

Work in progress for MVP available at master...issues/6

@techniq

This comment has been minimized.

Copy link

techniq commented Jun 17, 2018

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

This comment has been minimized.

Copy link

luoboding commented Jul 10, 2018

is this a reusable mechanism in UITableView in IOS ?

@bvaughn

This comment has been minimized.

Copy link
Owner Author

bvaughn commented Jul 10, 2018

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

@luoboding

This comment has been minimized.

Copy link

luoboding commented Jul 12, 2018

@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

This comment has been minimized.

Copy link
Owner Author

bvaughn commented Jul 12, 2018

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

This comment has been minimized.

Copy link

yuchi commented Jul 21, 2018

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

This comment has been minimized.

Copy link
Contributor

nihgwu commented Jul 21, 2018

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

@bvaughn

This comment has been minimized.

Copy link
Owner Author

bvaughn commented Jul 22, 2018

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

This comment has been minimized.

Copy link
Owner Author

bvaughn commented Jul 24, 2018

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

This comment has been minimized.

Copy link

kevinder commented Aug 10, 2018

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

This comment has been minimized.

Copy link

carlosagsmendes commented Aug 29, 2018

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

@osdlge

This comment has been minimized.

Copy link

osdlge commented Sep 26, 2018

@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

This comment has been minimized.

Copy link
Owner Author

bvaughn commented Sep 26, 2018

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

@osdlge

This comment has been minimized.

Copy link

osdlge commented Sep 26, 2018

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

paradoxxxzero added a commit to Kozea/formol that referenced this issue Sep 27, 2018

@bvaughn

This comment has been minimized.

Copy link
Owner Author

bvaughn commented Sep 27, 2018

Thank you for sharing! 😄

@bvaughn

This comment has been minimized.

Copy link
Owner Author

bvaughn commented Oct 11, 2018

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

This comment has been minimized.

Copy link

carlosagsmendes commented Oct 11, 2018

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

This comment has been minimized.

Copy link
Owner Author

bvaughn commented Oct 11, 2018

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

This comment has been minimized.

Copy link
Owner Author

bvaughn commented Oct 12, 2018

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

This comment has been minimized.

Copy link

akraines commented Oct 12, 2018

@bvaughn

This comment has been minimized.

Copy link
Owner Author

bvaughn commented Oct 12, 2018

@gnir-work

This comment has been minimized.

Copy link

gnir-work commented Oct 21, 2018

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 😄

@piecyk

This comment has been minimized.

Copy link

piecyk commented Nov 2, 2018

@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

This comment has been minimized.

Copy link
Owner Author

bvaughn commented Dec 7, 2018

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

This comment has been minimized.

Copy link
Owner Author

bvaughn commented Dec 7, 2018

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

This comment has been minimized.

Copy link

piecyk commented Dec 7, 2018

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

This comment has been minimized.

Copy link
Owner Author

bvaughn commented Dec 7, 2018

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

This comment has been minimized.

Copy link

marcneander commented Jan 22, 2019

Seems like the @next package is broken?

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

@vtripolitakis

This comment has been minimized.

Copy link

vtripolitakis commented Feb 2, 2019

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

This comment has been minimized.

Copy link

carlosagsmendes commented Feb 2, 2019

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

@carlosagsmendes

This comment has been minimized.

Copy link

carlosagsmendes commented Feb 5, 2019

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

@vtripolitakis

This comment has been minimized.

Copy link

vtripolitakis commented Feb 5, 2019

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

@vtripolitakis

This comment has been minimized.

Copy link

vtripolitakis commented Feb 6, 2019

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

This comment has been minimized.

Copy link
Owner Author

bvaughn commented Feb 6, 2019

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

This comment has been minimized.

Copy link

vtripolitakis commented Feb 6, 2019

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

This comment has been minimized.

Copy link

superandrew213 commented Feb 15, 2019

@marcneander try version 1.4.0-alpha.1

@piecyk

This comment has been minimized.

Copy link

piecyk commented Feb 17, 2019

Regarding ignoring resize events when list is hidden, maybe something like this piecyk@acfd888
@bvaughn what do you think ?

@xaviergmail

This comment has been minimized.

Copy link

xaviergmail commented Feb 18, 2019

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

This comment has been minimized.

Copy link
Owner Author

bvaughn commented Feb 18, 2019

Yeah, maybe something like that could work @piecyk 👍

Is this intended behavior?

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

@trxcllnt

This comment has been minimized.

Copy link

trxcllnt commented Mar 3, 2019

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 👎, 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

This comment has been minimized.

Copy link
Owner Author

bvaughn commented Mar 3, 2019

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

This comment has been minimized.

Copy link

trxcllnt commented Mar 4, 2019

@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

This comment has been minimized.

Copy link

milieu commented Mar 11, 2019

@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

This comment has been minimized.

Copy link
Owner Author

bvaughn commented Mar 11, 2019

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

@bvaughn

This comment has been minimized.

Copy link
Owner Author

bvaughn commented Mar 14, 2019

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

This comment has been minimized.

Copy link

mgustin12 commented Mar 18, 2019

@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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.