📖 Reading and sharing
It is neither the people nor the state who maintain the death penalty system, but the murderers themselves 13 steps of disappearance [RI] Takano and Ming
Virtual scrolling: reuse your DOM elements and remove an element of your viewport according to the user's scrolling direction.
When the list needs to display tens of thousands of levels or even infinite data, the accumulation of DOM elements will reduce the performance of browser rendering, reduce the user experience and even fake the page. At this time, the use of virtual scrolling technology can keep the number of DOM at a fixed number, so as to solve the above problems. However, in the case of a small amount of data, the traditional loading method is better than virtual scrolling. The core of virtual scrolling is to listen to scrolling events for complex logical calculation. Under the two measures, the DOM consumption of a small amount of data is much less than that of virtual scrolling
Existing applications of virtual scrolling Technology: Google Music, Twitter, Facebook.
Next, the article will describe how to realize the virtual rolling from fixed height to dynamic height, what are the technical difficulties, and introduce the core points of the algorithm in the form of code based on the framework of React.
Fixed height
In order to achieve the same experience as traditional list loading, virtual scrolling needs to do the following:
- Calculate the DOM element capacity that the container can hold
- Simulated rolling height
- Real time calculation of displayed elements
1. Bearing capacity
In the computer field, there is a noun called viewport, which represents the currently visible computer graphics area. In virtual scrolling technology, a viewport is a container that carries DOM elements. DOM elements beyond the container are invisible and need to be displayed by scrolling. As shown in the figure below, the height of the white part is the height of the container, and the blue DOM element is the element visible to the user.
Assuming that the height of the container is h and the height of a single DOM element is DH, the number of visible containers is VISIBLE_COUNT = H / DH. However, in the actual rolling process, only rendering the visible quantity is not enough, because the real-time calculation of the rolling process will lead to the rendering of the browser is not timely enough, and there may be blank, so we need to add a DOM element for caching on both sides. Assume BUFFER_SIZE is 3. As shown in the above figure, the number of DOM to be rendered is 4 + 3 * 2 = 10, ITEM_COUNT = ⌈H / DH⌉ + BUFFER_SIZE * 2;
In order to filter the rendered DOM elements more conveniently, we set two variables to filter, firstItem and lastItem.
useLayoutEffect(() => {
ELEMENT_HEIGHT = outerHeight(itemRef.current);
const containerHeight = containerRef.current?.clientHeight ?? 0;
VISIBLE_COUNT = Math.ceil(containerHeight / ELEMENT_HEIGHT);
setLastItem(VISIBLE_COUNT + BUFFER_SIZE);
}, [])2. Simulate rolling height
To make users feel the same effect and experience as traditional scrolling, however, the limited DOM elements are not enough to open the list of thousands of data, so we need to use css to help open it. There are two ways to open it:
- Set the padding bottom of the container to make the scroll bar appear
- Setting a sentinel element and the value of translateY of the sentinel element can also make the container appear a scroll bar.
💡 PS: in reality, sentinels are used to solve the border problems between countries and do not directly participate in production activities. In the computer field, it is also to deal with boundary problems, which can reduce the judgment of many boundary problems and reduce the complexity of code.
I recommend the second method here because of the rearrangement and redrawing of the browser. In particular, when the dynamic height rolling is introduced later, the scrollable height will be continuously calculated, which is also some optimization for performance. Since it can be optimized, of course, it should be optimized thoroughly.
Because the height of each DOM element is fixed, you can calculate the height every time the list changes. Scrollheight = list length * ELEMENT_ HEIGHT;
<div onScroll={scroll} ref={containerRef} className={styles.container}>
// Sentry, used to spread the rolling height
<div className={styles.sentry} style={{ transform: `translateY(${scrollHeight}px)` }} ></div>
// You can ignore the code below first
{
visibleList.map((item, idx) =>
<div key={idx} style={{transform: `translateY(${item.scrollY}px)`}} className={styles.wrapItem} >
<Item ref={itemRef} item={item} />
</div>
)
}
</div>useLayoutEffect(() => {
// You can ignore this code first
list.forEach((item, idx) => {
item.scrollY = idx * ELEMENT_HEIGHT;
})
// Update the value of scrollHeight when the list changes
setScrollHeight(list.length * ELEMENT_HEIGHT);
}, [list]);3. Real time calculation of displayed elements
How to correctly display the elements corresponding to the current scrolled height? This is the problem to be solved in this section, and it is also the core of the whole virtual rolling technology (fixed or dynamic).
In the case of fixed height, the position of each element has been determined when loading the list. Just set the value of translateY like a sentry. At the same time, a visibleList variable is also set to filter the DOM elements to be rendered. This variable depends on the firstItem, lastItem and list mentioned above.
useLayoutEffect(() => {
// When the list changes, set scroll for each item
list.forEach((item, idx) => {
item.scrollY = idx * ELEMENT_HEIGHT;
})
// Update the value of scrollHeight when the list changes
setScrollHeight(list.length * ELEMENT_HEIGHT);
}, [list]);useLayoutEffect(() => {
setVisibleList(list.slice(firstItem, lastItem));
}, [list, firstItem, lastItem]);<div onScroll={scroll} ref={containerRef} className={styles.container}>
// Sentry, used to spread the rolling height
<div className={styles.sentry} style={{ transform: `translateY(${scrollHeight}px)` }} ></div>
// When displaying, set the value of translateY
{
visibleList.map((item, idx) =>
<div key={idx} style={{transform: `translateY(${item.scrollY}px)`}} className={styles.wrapItem} >
<Item ref={itemRef} item={item} />
</div>
)
}
</div>Here, everything is ready, only the processing of rolling events. In the scrolling process, we need to calculate which data should be displayed according to the scrollTop of the container, because the rendering of the whole list depends on the variables of visibleList, while the visibleList depends on firstItem and lastItem, and lastItem depends on firstItem, so scrolling only needs to calculate firstItem.
Under normal circumstances, most people simply think that since the element is of fixed height, you can directly use ⌊ scrollTop / ELEMENT_HEIGHT ⌋ you can get the firstItem.
exactly! This is the simplest and most effective way.
However, in order to give readers a sense of gradual progress in the following dynamic height technology, a new concept is extended here: [anchor element]. This anchor has two attributes index and offset, which point to the index of the first visible element. Offset indicates that the scrolling height exceeds the value of this element. If offset > elment_ When high, index + +.
const updateAnchorItem = useCallback(
(container) => {
const index = Math.floor(container.scrollTop / ELEMENT_HEIGHT);
const offset = container.scrollTop - ELEMENT_HEIGHT * index;
anchorItem.current = {
index,
offset
}
},
[],
)
const scroll = useCallback(
(event) => {
const container = event.target;
// const tempFirst = Math.floor(container.scrollTop / ELEMENT_HEIGHT);
// setFirstItem(tempFirst);
// There are so many fancy things below, which are not as simple as those above
const delta = container.scrollTop - lastScrollTop.current;
lastScrollTop.current = container.scrollTop;
const isPositive = delta >= 0;
anchorItem.current.offset += delta;
let tempFirst = firstItem;
if (isPositive) {
// Roll down
if (anchorItem.current.offset >= ELEMENT_HEIGHT) {
updateAnchorItem(container);
}
// Has the updated index changed
if (anchorItem.current.index - tempFirst >= BUFFER_SIZE) {
tempFirst = Math.min(list.length - VISIBLE_COUNT, anchorItem.current.index - BUFFER_SIZE)
setFirstItem(tempFirst);
}
} else {
// Roll up
if (container.scrollTop <= 0) {
anchorItem.current = { index:0, offset: 0 };
} else if (anchorItem.current.offset < 0) {
updateAnchorItem(container);
}
// Has the updated index changed
if (anchorItem.current.index - firstItem < BUFFER_SIZE) {
tempFirst = Math.max(0, anchorItem.current.index - BUFFER_SIZE)
setFirstItem(tempFirst);
}
}
setLastItem(Math.min(tempFirst + VISIBLE_COUNT + BUFFER_SIZE * 2, list.length));
// Pull to the bottom and load new data
if (container.scrollTop + container.clientHeight >=
container.scrollHeight - 10) {
setList([...list, ...generateItems()]);
}
},
[list, updateAnchorItem, firstItem],
)So far, the implementation of fixed height has been completed.
Dynamic height
Dynamic height, as the name suggests, is not fixed. Only when the rendering is completed can we know how high the DOM element is, so the difficulty will be:
- You need to know when the element is rendered, and then get the height
- The simulated rolling height is uncertain and needs real-time calculation
- The translateY value of each visual element is not fixed
- What is the effect on the scroll bar when the height of the element is adjusted
We will solve the above points one by one. Although the specific idea is similar to the implementation of fixed height, some control of details still needs to be carefully considered.
1. How to know when elements are rendered
ECMA has provided an object for us to use - ResizeObserver, which is used to monitor and observe the changes in the bounding box of DOM. The compatibility can be seen in the figure below, but you can use Mutationobserver to realize polyfill. Github has a great God to realize it, polyfill address . Through polyfill, we can safely use this object to achieve our goal. (unless you want to be compatible with IE, since it is IE, you can't think of using virtual height technology!!!)
const resizeObserver = useRef<ResizeObserver>(
new ResizeObserver((entries, observer) => {
sizeChange();
})
);// wrappedItem.tsx, wrap in child elements
useLayoutEffect(() => {
ob.observe(myRef.current!);
const ref = myRef.current!;
return () => {
ob.unobserve(ref);
}
}, [ob]);2. Calculate the rolling height in real time
Because the height of each DOM element is uncertain, it cannot be counted directly as a fixed height ✖️ Element height is so simple and rough. In order to record the height of each element, we need to set a more realistic height of each ELEMENT_HEIGHT. When this element has not been rendered, the default value is ELEMENT_HEIGHT, combined with ResizeObserver, itemHeights will become more and more perfect, and the rolling height will become more and more real.
useLayoutEffect(() => {
let scrollH = itemHeights.reduce((sum, h) => sum += h, 0);
setScrollHeight(scrollH + (list.length - itemHeights.length) * ELEMENT_HEIGHT);
}, [itemHeights, list]);const sizeChange = useCallback(() => {
updateScrollY();
}, [updateScrollY]);
const updateScrollY = useCallback(() => {
... // Omitting some code, the following is a loop to get the currently rendered DOM elements to update.
itemHeights[anchorItem.current.index] = outerHeight(anchorDom);
for (let i = domIndex + 1; i < items.length; i++) {
const index = items[i].index;
itemHeights[index] = outerHeight(item);
}
for (let i = domIndex - 1; i >= 0; i--) {
const index = items[i].index;
itemHeights[index] = outerHeight(item);
}
setItemHeights([...itemHeights]);
}, [itemHeights]);3. Calculate the translateY value of the visual element
In fact, this is the same as the height. It needs to rely on ResizeObserver for calculation, because the value of translateY of each element is through the translateY and height of the previous element, which has the smell of dynamic planning. They all depend on the value of the previous state. Of course, the value of translateY of the first element is 0. Therefore, we need to set an itemScrollYs to record the translateY value for each element, and directly set the style transform during rendering.
const updateScrollY = useCallback(() => {
// When updating, start recording through the anchor element
const items = itemRefs.current;
const domIndex = Array.from(items).findIndex((item) => item.index === anchorItem.current.index);
const anchorDom = items[domIndex].dom;
itemHeights[anchorItem.current.index] = outerHeight(anchorDom);
// Set translateY starting with the anchor
itemScrollYs[anchorItem.current.index] = containerRef.current!.scrollTop - anchorItem.current.offset;
for (let i = domIndex + 1; i < items.length; i++) {
// Calculate the translateY of each element later
const item = items[i].dom;
if (item === null) return;
const index = items[i].index;
itemHeights[index] = outerHeight(item);
const scrollY = itemScrollYs[index - 1] + itemHeights[index - 1];
itemScrollYs[index] = scrollY;
}
for (let i = domIndex - 1; i >= 0; i--) {
// Calculate the translateY of each element forward
const item = items[i].dom;
if (item === null) return;
const index = items[i].index;
itemHeights[index] = outerHeight(item);
const scrollY = itemScrollYs[index + 1] - itemHeights[index];
itemScrollYs[index] = scrollY;
}
... // Ignore partial code
setItemHeights([...itemHeights]);
setItemScrollYs([...itemScrollYs]);
}, [itemHeights, itemScrollYs]);4. What is the impact on the scroll bar after the element height is adjusted
At this time, it is estimated that some people will have some questions? The updateScrollY code above is so fancy that I can't understand why I do it?
When I first realized it, my idea was very simple. Normally, because each element translateY depends on the value of the previous element, because resizeObserver can pass parameters to tell me which element is highly updated. Just start with this element and update the translateY of the elements below it. The elements above it have no effect at all. But this idea is ideal, but in fact, in the browser, because the height is only known when rendering, the overall scrollHeight changes every time. At this time, if the rendered height of the element is higher than the set element_ When the value of height is quite different, the browser will automatically help us adjust the position of the scroll bar. At this time, the user sees crazy jitter! No sense of experience at all!
So here we go back to the implementation of fixed height, when there was a definition of anchor element. For a fixed height, it is a feeling of killing a chicken with an ox knife, while for a dynamic height, it is a fixed sea god needle to solve the problem of shaking. In reality, the anchor is used to help the ship dock and fix the position of the ship. Here, when the browser adjusts the rolling height, we need to recalculate its translateY value according to the scrollTop of the container through the anchor element, that is, the index and offset of the first visual element, so that the user can not feel the jitter, That's why the updateScrollY above is so complex.
5. Handle scroll events
With the help of anchor element, the processing of scroll event is similar to the implementation of fixed height, but there are still some changes. It is still necessary to know whether the current anchor element has changed through real-time calculation.
const updateAnchorItem = useCallback(
(container) => {
const delta = container.scrollTop - lastScrollTop.current;
lastScrollTop.current = container.scrollTop;
const isPositive = delta >= 0;
anchorItem.current.offset += delta;
let index = anchorItem.current.index;
let offset = anchorItem.current.offset;
const actualScrollHeight = itemScrollYs[lastItem - 1] + itemHeights[lastItem - 1];
... // Omit some codes
if (isPositive && offset > 0) {
// According to the value of offset, calculate whether the height of the lower element is greater than offset
while (index < list.length && offset >= itemHeights[index]) {
if (!itemHeights[index]) {
itemHeights[index] = ELEMENT_HEIGHT;
}
offset -= itemHeights[index];
index++;
}
if (index >= list.length) {
anchorItem.current = { index: list.length - 1, offset: 0 };
} else {
anchorItem.current = { index, offset };
}
} else {
// Similarly, when offset is negative, it is calculated in the same way
while (offset < 0) {
if (!itemHeights[index - 1]) {
itemHeights[index - 1] = ELEMENT_HEIGHT;
}
offset += itemHeights[index - 1];
index--;
}
if (index < 0) {
anchorItem.current = { index: 0, offset: 0 };
} else {
anchorItem.current = { index, offset };
}
}
... //Omit some codes
},
[itemHeights, list, updateScrollY, firstItem, itemScrollYs, scrollHeight, lastItem],
)6. Finishing and grinding
The core algorithm of dynamic height has been completed, but there are still some finishing work to be completed.
Because when the ResizeObserver callback is triggered, the translateY value of the visual element needs to be recalculated based on the anchor element. This will lead to problems with the translateY value of the top element and the tail element. The first element is not equal to zero, and the tail element is greater than or less than the container scrollHeight. Therefore, the rest of the work is to smooth out these situations and do these finishing work well.
const updateScrollY = useCallback(() => {
... // Is the value of translateY calculated by the anchor element
if (itemScrollYs[0] !== 0) {
/** If you scroll to the top and the first element appears,
When it is found that the translateY of the first element is not zero,
It needs to be readjusted, because the first one must be 0
**/
const diff = itemScrollYs[0];
for (let i = 0; i < items.length; i++) {
itemScrollYs[i] -= diff;
}
const actualScrollTop = anchorItem.current.index - 1 >= 0 ? itemScrollYs[anchorItem.current.index - 1] + anchorItem.current.offset : anchorItem.current.offset;
containerRef.current!.scrollTop = actualScrollTop;
lastScrollTop.current = actualScrollTop;
}
setItemHeights([...itemHeights]);
setItemScrollYs([...itemScrollYs]);
}, [itemHeights, itemScrollYs]);const updateAnchorItem = useCallback(
(container) => {
... // Omit the code for calculating offset
if (lastItem === list.length && actualScrollHeight < scrollHeight) {
// Need to fix the problem of leaving blank at the bottom
const diff = scrollHeight - actualScrollHeight;
offset -= diff;
setScrollHeight(actualScrollHeight);
}
... // Omit switching of calculated anchor elements
if (itemScrollYs[firstItem] < 0) {
// It should also be adjusted when the element of firstItem is less than 0, because the scroll value of the container is not 0
const actualScrollTop = itemHeights.slice(0, Math.max(0, anchorItem.current.index)).reduce((sum, h) => sum + h, 0);
containerRef.current!.scrollTop = actualScrollTop;
lastScrollTop.current = actualScrollTop;
if (actualScrollTop === 0) {
anchorItem.current = { index: 0, offset: 0 };
}
updateScrollY();
}
},
[itemHeights, list, updateScrollY, firstItem, itemScrollYs, scrollHeight, lastItem],
)So far, the implementation of dynamic height has been completed.
TroubleShooting
There is a special point to pay attention to when realizing dynamic height. Please observe the following code:
useLayoutEffect(() => {
ob.observe(myRef.current!);
const ref = myRef.current!;
return () => {
ob.unobserve(ref);
}
}, [ob]);This code actually uses useLayoutEffect. Students who are familiar with react should know the difference between it and useEffect. We must use useLayoutEffect here. Why? Here is just observe a DOM element, without any rendering operation. If you change to useEffect, you will find that when you scroll quickly, you will find that there will be relatively large white space above or below, and even report an error in serious cases.
Firstly, in the processing function updateScrollY of dynamic height ResizeObserver, you need to find the anchor element, and then start from the anchor element to update the translateY of other visual elements, and the update of anchor element only depends on the scroll function.
ResizeObserver is a micro task. When it observes the element for the first time, it will trigger a callback, and the border of subsequent elements will be updated when it changes. The Scroll event is a macro task, so in the execution order, the priority of ResizeObserver will be greater than the Scroll event.
Back to the principle of React, the Reconciliation of React is divided into two stages: render and commit. Both useLayoutEffect and useEffect are executed in commit. The difference is that useLayoutEffect is executed before the browser triggers rendering.
Consider this scenario:
Suppose that our container can hold 10 DOM elements. When the user scrolls quickly, these 10 DOM elements must be updated. If useEffect is used to observe elements, in fact, these 10 elements have been rendered. If ResizeObserver goes to observe again, 10 callbacks of ResizeObserver in the browser's Micro task queue are ready, Then the Scroll event will be delayed and the anchor element will not be updated in time, and the user will see the situation of leaving blank.
If you use useLayoutEffect to observe, the callback of ResizeObserver will not be executed at this time. You need to wait for React to be executed when it really goes to append to the document in the commit phase. However, these 10 ResizeObserver callbacks will not be ready at one time. Then Scroll events can be interspersed among them, so the user can't see the blank situation, and the experience is better.
Therefore, the native > Vue = react class > react function used to realize virtual scrolling.
reference
https://developers.google.com/web/updates/2016/07/infinite-scroller#the_right_thing™