In Part 1 we learned the basic principals behind building a virtual scroll mechanism, the math behind it, and saw some psuedo-code and some real code.
If you haven't read it yet, I suggest you start from there to get to know the terminology: part I
In Part 1 we assumed the row height is always fixed, which made our lives much easier. But how can we support dynamic height, and do we have to let the user supply the height or can we figure it out automatically?
Automatic Height?
Let's answer the second question first. Figuring out the height of unrendered nodes is not a trivial task, and a costly one. It requires rendering them offscreen and handling some potential edgecases, and is a big problem on its own. We won't be discussing this problem in this tutorial.
Dynamic Height
Nevertheless, we can support a dynamic height by allowing the user to supply a function that returns the height per row. This is something the user can calculate offline by rendering different types of rows per row type.
This makes our calculations more complex since we can't just multiply or divide by rowHeight.
Calculating the Nodes' Positions
When we initialize the component, we will calculate each node's position, which will help us with all the calculation steps that we had in Part 1.
We also need to react to changes in the array of items and recalculate the positions of the entire array if it changed. This is usually achievable in modern FE frameworks.
To calculate a node's position, we take the position of the previous node and add the height of the previous node.
We have to make a full pass when we start
The Container Height
Now that we have the nodes' positions, it's a very straightforward step. We simply take the last node's position and add its height.
Figuring Out the Visible Nodes
To figure this out, we need to start with the first visible node. Now that we have the node's positions calculated, this is basically finding the bottom-most node that is above the scroll position.
Sounds simple, but since the positions are dynamic, we cannot simply locate that node with a math calculation.
Naive Solution
The naive solution would be to iterate over the nodes from the start until we find a node whose position is larger than scrollTop. But this is obviously a bad strategy. This calculation will be done very frequently as the user scrolls and must be extremely performant.
Binary Search
Because our nodes are already sorted, we can do a binary search.
Binary Search: Search a sorted array by repeatedly dividing the search interval in half. Begin with an interval covering the whole array. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise, narrow it to the upper half. Repeatedly check until the value is found or the interval is empty. https://www.geeksforgeeks.org/binary-search/
The advantage is that the complexity is O(log n). Meaning that even if you have a million nodes, you will make only around 20 comparisons.
Usually, in binary search, we look for a specific value. Here, we look for a node that is above the scroll position, while the next node's position is below it.
After we find the first node we reduce the node padding as we did in Part 1.
Now to figure out the number of visible nodes, we simply add nodes until we reach a node position that's greater than scrollTop + viewport height and add the padding as well.
Shifting the nodes down
Since we have the node's positions, our offsetY is simply the first node's position.
Et voila
That's it, this gets us the same numbers we had in Part I, and we can render the visible nodes and shift them down.
Performance Optimizations
You probably realize that doing all of these calculations can be costly.
Scroll events can fire very rapidly as the user scrolls, and we want to make sure we don't make too many extra calculations otherwise the UI might be sluggish.
Most displays use 60fps, and recalculating faster than that is just a waste of resources.
Throttling
One way to accomplish that is by throttling.
Throttling gives us control over the rate at which a function is called. For example, if an event fires every millisecond, and we want the callback to handle events only every 17ms and ignore the events in between.
So you can throttle the scroll event callback to 17ms, and make sure the last event (tail) is also handled.
requestAnimationFrame
My preferred way is using requestAnimationFrame.
The window.requestAnimationFrame() method tells the browser that you wish to perform an animation and requests that the browser shall call a specified function to update an animation before the next repaint. The method takes a callback as an argument to be invoked before the repaint. More info: https://developer.mozilla.org/en-US/docs/Web/API/window/requestAnimationFrame
This will guarantee your calculations will run at 60fps. It means that the scroll event needs to run the calculations in requestAnimationFrame. But how can you prevent registering multiple callbacks in one animation frame? You can simply cancel the previous callback (if it exists), and request another one.
Example
Here is an example with dynamic heights using React, binary search, and virtual scrolling, using React and hooks:
https://codesandbox.io/s/virtual-scroll-dynamic-heights-using-hooks-6gmgu
Virtual scroll on a tree
One of the more complex things I've developed was virtual scrolling on a tree. The tree adds another complexity that each level might be expanded or collapsed, and the traversal on the tree is nested.
One way to overcome this is to flatten the tree. Meaning every time you expand or collapse a node you insert or remove nodes from the flat array, and recalculate the nodes' positions. Then, the virtual scroll behaves like a regular virtual scroll on a list.
The other way (which I took), is to calculate the node positions based on the current status of the tree (which one is expanded and which one is collapsed). Traversing the tree to find the visible nodes is done recursively on the tree.
You can check out the source code for that here:
https://github.com/500tech/angular-tree-component/blob/master/lib/models/tree-virtual-scroll.model.ts
Thanks and I hoped you enjoyed the 2 part blog!
Top comments (27)
Hi Adam, I got to ask some more about performance optimisations. I have also tried to build virtual scroll with feature of two-way infinite scroll. But I got to admit that the solution I built wasn't much performant. Now, related to my project, I got two major questions:
Hi,
Can you share a link to your code and I'll see if I can take a look?
I cannot share as I have done this in my current organisation
Hai, I need to perform virtual scroll in JavaScript can you provide me the code for it
how would you handle window resize in this? all the heights become stale as the window is resized, only a few items are on the DOM and only their modified heights can be obtained, you have to shift everything up or down
I guess if the container's dimensions change (for any reason) we need to recalculate from scratch.
But 'scrollTop' should remain the same, so probably no need to shift anything, just display more or less nodes depending on the new height.
i am talking about width change on resize, the displacement of each row from the top would totally get disturbed if the width were to change on resize, how do you think that should be handled? :) thank you for the response
Why should the width affect the calculations? I'm not following
you record heights of 50 rows, you change the width to compress the rows, depending on contents, some of the rows increase in their height, your stored heights are now invalid
I think this kind of situation is problematic for a virtual scroll of this sort, since the heights are returned per row, and usually not calculated based on measuring DOM nodes' dimensions.
So I would limit the "shrink factor" of the tree view and prevent the rows from wrapping and increasing in height.
Hey, thanks for this post. It's been extremely helpful in the last couple days.
I noticed you specify X items, but can scroll down only to X-1.
E.g. itemCount: 100, displayed items: 0-98
I'm trying to fix it right now, but would appreciate your help :D
Thanks!
The calculation for the end node was wrong, because it relied on the start node AFTER I reduced the renderAhead.
Also, visible count should be endNode - startNode + 1 (because if we're displaying nodes 1 to 10, we need 10 nodes, not 9).
Fixed in the example
I fixed like this:
But I'm not sure any side-effect would show up or not in a real world scenario.
Thoughts?
Curious question based on your react example, why have you written const totalHeight =
childPositions[itemCount - 1] + getChildHeight(itemCount - 1) + 35; what is this 35? average row height of an item since it starts at 30 and goes till 39?
Oh, thanks for noticing!
Probably leftover - I removed it
Thank you so much!!!
react-window and other solutions do not support native html tables (returns DIVs not TRs) so I had to try and solved it with no lib.
added minor cases support to your example like:
forked your code with the aforementioned cases: bit.ly/38nATie
native virtual table implementation using your code in: bit.ly/36dc4nu
Cool! Thanks for the addition.
I wonder if you could make it work with position: sticky
Hello, Thank you for your detailed series! I've translated your code to Vue for anybody struggling with React.
gist.github.com/derpdead/f35a2ec17...
Could you give as a hint about best practise of making row measurer for auto height content?
Thanks!
I've never done that, but sounds like a nice challenge :)
@adamklein The git repo mentioned in the article for the tree implementation doesn't seem to be available. Do you have a different link to access it?
I am currently working on a similar requirement in lightning web component (salesforce), so was hoping to find any documentation/ directions related to it.
Thanks!!
Could anyone kindly add a Vue.js version of this?
Great idea! If anyone adds one I'll add to the post
Hi Adam, how would you handle lazy load items on scroll, and jump to a specific index/row?
You know what would be awesome for part 3? How to make it circular. Like scrolling to the very bottom would make start from the beginning but on a infinite scroll like fashion.
Hello Adam, first of all, amazing work here you've done. I want the lib to use window scroll as in the window scrollbar should be used to scroll. How would I do that? Thanks.
Hello Adam, i really enjoy read this tutorial
How to you think of two direction virtual scroll? (horizontal and vertical)
I think that could be a great Part III :)