DEV Community

adam klein
adam klein

Posted on

Build your own virtual scroll - Part II

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
calculate node position and container height

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.

find visible nodes

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!

Discussion (25)

Collapse
devin6391 profile image
Vineet Dev

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:

  1. What about dynamically adding data to this component?
  2. What about mobile web performance? Mobile scroll is a totally different game which is much more complex to manage than desktop scroll and 60fps really matters there.(specially iOS)
Collapse
adamklein profile image
adam klein Author

Hi,

  1. Changing the data means you have to recalculate the positions of all the nodes
  2. In my projects, I haven't encountered any specific problems related to mobile, but obviously it depends on the device and the code

Can you share a link to your code and I'll see if I can take a look?

Collapse
devin6391 profile image
Vineet Dev

I cannot share as I have done this in my current organisation

Collapse
indumathi1701 profile image
indumathi1701

Hai, I need to perform virtual scroll in JavaScript can you provide me the code for it

Collapse
slidenerd profile image
slidenerd

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

Collapse
adamklein profile image
adam klein Author

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.

Collapse
slidenerd profile image
slidenerd

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

Thread Thread
adamklein profile image
adam klein Author

Why should the width affect the calculations? I'm not following

Thread Thread
slidenerd profile image
slidenerd

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

Thread Thread
adamklein profile image
adam klein Author

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.

Collapse
trumbitta profile image
William Ghelfi • Edited

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

Collapse
adamklein profile image
adam klein Author

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

Collapse
trumbitta profile image
William Ghelfi • Edited

I fixed like this:

// endNode = Math.min(itemCount - 1, endNode + renderAhead);
endNode = Math.min(itemCount, endNode + renderAhead);

But I'm not sure any side-effect would show up or not in a real world scenario.
Thoughts?

Collapse
derpdead profile image
Maciej Kaczorowski

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?

Collapse
adamklein profile image
adam klein Author

Thanks!
I've never done that, but sounds like a nice challenge :)

Collapse
slidenerd profile image
slidenerd

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?

Collapse
adamklein profile image
adam klein Author

Oh, thanks for noticing!
Probably leftover - I removed it

Collapse
okvv profile image
Vladimir Okun • Edited

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:

  • table header
  • TRs not shown because of additional height (let's say header height)
  • no rows at all just change the itemCount={...} prop value per needed case (0/2/10000).

forked your code with the aforementioned cases: bit.ly/38nATie
native virtual table implementation using your code in: bit.ly/36dc4nu

Collapse
adamklein profile image
adam klein Author

Cool! Thanks for the addition.
I wonder if you could make it work with position: sticky

Collapse
slidenerd profile image
slidenerd

Could anyone kindly add a Vue.js version of this?

Collapse
adamklein profile image
adam klein Author

Great idea! If anyone adds one I'll add to the post

Collapse
siba2893 profile image
Daniel Sibaja

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.

Collapse
9z2f4f3 profile image
9z2f4F3

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.

Collapse
ceomurky profile image
Moonjongmin

Hello Adam, i really enjoy read this tutorial

How to you think of two direction virtual scroll? (horizontal and vertical)

Collapse
adamklein profile image
adam klein Author

I think that could be a great Part III :)