Recently, in the process of development iteration of a platform, we encountered the situation of slow loading and lag of super-long List nested in ANTD Modal. On a whim, I decided to implement a virtual scrolling list from scratch to optimize the overall experience.

Before modification:

We can see that before the transformation, there would be a temporary delay when opening the editing window Modal, and after clicking Cancel to close, it did not respond immediately but closed after a little hesitation

After transforming:

After the transformation, we can observe that the opening of the whole Modal becomes much smoother than before, and it can immediately respond to the user’s click event to arouse/close Modal

  • Performance comparison Demo: codesandbox. IO /s/ a-V-list -…

0x0 Basics

So what is a virtual scroll/list?

A virtual list refers to the article when we have tens of thousands of data need to be displayed but the user’s “Windows” (disposable visible content) is small, we can render users maximum visible only through clever article number + “BufferSize” elements and dynamic update when the user to scroll the contents of the each element so as to achieve a long list of and rolling Same effect but with much less resources.

(It can be seen from the figure above that the actual user can see only item-4 ~ item-13 elements each time)

0x1 Implements a fixed height virtual list

  • First we need to define a few variables/names.

    • From the figure above, we can see that the beginning element of the user’s actual visible area is item-4, so his corresponding index in the data array is oursstartIndex
    • Similarly, the array subscript for item-13 should be oursendIndex
    • So item-1, item-2, and item-3 are hidden by the user’s swipe up operation, so we call itstartOffset(scrollTop)

Since we only rendered the contents of the viewable area, to keep the container behaving like a long list (scrolling) we had to keep the height of the original list, so we designed the HTML structure as follows

<! - ver 1.0 -- >
<div className="vListContainer">
  <div className="phantomContent">.<! -- item-1 -->
    <! -- item-2 -->
    <! -- item-3 -->.</div>
</div>
Copy the code
  • Among them:
    • vListContainerContainer for visual area, withoverflow-y: autoProperties.
    • inphantomShould have each piece of data inposition: absoluteattribute
    • phantomContentIs our “phantom” section, whose main purpose is to restore the content height of the real List to simulate the scrolling behavior of a normal long List.

  • Then we bind an onScroll response function to vListContainer and calculate our startIndex and endIndex based on the scrollTop property of the native scroll event

    • Before we begin, we need to define a few values:
      • We need a fixed list element height:rowHeight
      • We need to know how many entries are in the current list:total
      • We need to know the height of the current user’s viewable area:height
    • With the above data, we can calculate the following data:
      • Total list height:phantomHeight = total * rowHeight
      • Display the number of elements in the visual range:limit = Math.ceil(height/rowHeight)

(Note that we’re rounding up here.)

  • So we can do the following calculation in the onScroll callback:
onScroll(evt: any) {
  // Determine if it is a rolling event that we need to respond to
  if (evt.target === this.scrollingContainer.current) {
    const { scrollTop } = evt.target;
    const { startIndex, total, rowHeight, limit } = this;

    // Calculate the current startIndex
    const currentStartIndex = Math.floor(scrollTop / rowHeight);

    // If currentStartIndex is different from startIndex (we need to update the data)
    if(currentStartIndex ! == startIndex ) {this.startIndex = currentStartIndex;
      this.endIndex = Math.min(currentStartIndedx + limit, total - 1);
      this.setState({ scrollTop }); }}}Copy the code
  • Once we have startIndex and endIndex we can render the corresponding data:
renderDisplayContent = () = > {
  const { rowHeight, startIndex, endIndex } = this;
  const content = [];
  
  // Note that we used <= to render x+1 elements in order to make scrolling continuous (always render judgment & render x+2)
  for (let i = startIndex; i <= endIndex; ++i) {
    // rowRenderer is a user-defined list element rendering method that receives an index I and
    // The current position corresponds to the style
    content.push(
      rowRenderer({
        index: i, 
        style: {
          width: '100%'.height: rowHeight + 'px'.position: "absolute".left: 0.right: 0.top: i * rowHeight,
          borderBottom: "1px solid #000",}})); }return content;
};
Copy the code

IO /s/a-naive-v…

Principle:

  • So how does this scrolling work? First we render a “phantom” container of real List height in vListContainer to allow the user to scroll. Secondly, we listen on the onScroll event, and dynamically calculate the starting index of the current scroll Offset (how much is hidden by the scroll) every time the user triggers the scroll. SetState triggers redraw when we find that the new subscript is not assigned at the same time as the one we are currently showing. When the user’s current scroll offset does not trigger a subscript update, the phantom’s length gives the virtual list the same scrolling capability as a regular list. When redrawing is triggered, the user does not perceive the redrawing of the page because we are calculating startIndex (because the next frame that is currently scrolling is the same as the content that we have redrawn).

Optimization:

  • For the virtual list we implemented above, it is not difficult to find that a quick slide will appear the list flicker phenomenon/too late to render, blank phenomenon. Remember when we started talking about **Render user maximum number of visible + “BufferSize”? For the actual content we render, we can add the concept of Buffer up and down (i.e. render a few more elements up and down to overcome the problem of not being able to render when sliding fast). The optimized onScroll function is as follows:
onScroll(evt: any){...// Calculate the current startIndex
  const currentStartIndex = Math.floor(scrollTop / rowHeight);
    
  // If currentStartIndex is different from startIndex (we need to update the data)
  if(currentStartIndex ! == originStartIdx) {// Notice that we have introduced a new variable called originStartIdx, which is the same as startIndex
    // Same effect, record the current real start index.
    this.originStartIdx = currentStartIndex;
    // Calculate the head buffer of startIndex
    this.startIndex = Math.max(this.originStartIdx - bufferSize, 0);
    // Compute the tail buffer of endIndex
    this.endIndex = Math.min(
      this.originStartIdx + this.limit + bufferSize,
      total - 1
    );

    this.setState({ scrollTop: scrollTop }); }}Copy the code

Codesandbox.io /s/ a-better -…

0x2 List elements are highly adaptive

Now that we’ve implemented a virtual list of “fixed-height” elements, what about a business scenario with a very long list of variable heights?

  • In general, there are three ways to implement a virtual list when encountering an indeterminate list element:

  1. Change the input data by passing in the corresponding height of each element dynamicHeight[I] = x x is the row height of element I

    The implementation needs to know the height of each element (impractical)

  2. Draw the current element out of the screen and measure its height before rendering it into the user’s visual area

    This approach is equivalent to doubling the rendering cost (impractical)

  3. An estimateHeight attribute is passed to estimate and render the row height, and then the true implementation height is obtained after rendering and updated and cached

    Redundant transforms will be introduced (acceptable), and why redundant transforms are needed will be explained later…

  • Let’s go back to the HTML for a moment
<! --ver1.0 -->
<div className="vListContainer">
  <div className="phantomContent">.<! -- item-1 -->
    <! -- item-2 -->
    <! -- item-3 -->.</div>
</div><! --ver1.1 -->
<div className="vListContainer">
  <div className="phantomContent" />
  <div className="actualContent">.<! -- item-1 -->
    <! -- item-2 -->
    <! -- item-3 -->.</div>
</div>
Copy the code

  • When we implemented the “fixed height” virtual list, we rendered the elements in the phantomContent container and set the position of each item to absolute and defined the top property to be equal to I * rowHeight to achieve scrolling no matter what, Render content is always visible to the user. In the case that the height of the list is not determined, we cannot accurately calculate the y position of the current element by estimateHeight, so we need a container to help us do the absolute positioning.

  • ActualContent is our new list content rendering container, which avoids setting on each item by setting the position: Absolute property on it.

  • It’s a little different because we switched to the actualContent container. When sliding, we need to dynamically perform a Y-transform of the container’s position so that the container will always be in the user’s window:

getTransform() {
  const { scrollTop } = this.state;
  const { rowHeight, bufferSize, originStartIdx } = this;

  // Current slide offset - currently truncated (not completely disappeared elements) distance - header buffer distance
  return `translate3d(0,${
    scrollTop -
    (scrollTop % rowHeight) -
    Math.min(originStartIdx, bufferSize) * rowHeight
  }px,0)`;

}
Copy the code

IO /s/a-v-list-…

(Note: Rendering elements in the Phantom using Absolute is better than using Transform when there is no high adaptive requirement and cell reuse is not implemented. Because every time content is rendered, it’s rearranged, but if you use transform, it’s (rearranged + transform) > rearranged.

  • Getting back to the list element height adaptation, now that we have an actualContent that allows normal block arrangement internally, we can now simply render the content in first without giving the height. For the place where we need to calculate the height with rowHeight before, we replace it with estimateHeight uniformly for calculation.

    • limit = Math.ceil(height / estimateHeight)
    • phantomHeight = total * estimateHeight

  • Also, to avoid double-counting the rendered heights of each element (getBoundingClientReact().height) we need an array to store these heights

interface CachedPosition {
  index: number;         // The subscript of the current pos element
  top: number;           // Top position
  bottom: number;        // The bottom position
  height: number;        // Element height
  dValue: number;        // Whether the height is different from the previous (estimate)
}

cachedPositions: CachedPosition[] = [];

// Initialize cachedPositions
initCachedPositions = () = > {
  const { estimatedRowHeight } = this;
  this.cachedPositions = [];
  for (let i = 0; i < this.total; ++i) {
    this.cachedPositions[i] = {
      index: i,
      height: estimatedRowHeight,             // Start with estimateHeight
      top: i * estimatedRowHeight,            / / same as above
      bottom: (i + 1) * estimatedRowHeight,   // same above
      dValue: 0}; }};Copy the code
  • After we have computed (initialized) the cachedPositions, since we have computed the top and bottom of each element, the phantom height is the bottom value of the last element in the cachedPositions
this.phantomHeight = this.cachedPositions[cachedPositionsLen - 1].bottom;
Copy the code
  • After rendering elements in the user window according to estimateHeight, we need to update the actual height of the rendered elements. At this point, we can use the componentDidUpdate lifecycle hook to calculate, judge and update:
componentDidUpdate(){...ActualContentRef must have current (already rendered) + total must > 0
  if (this.actualContentRef.current && this.total > 0) {
    this.updateCachedPositions();
  }
}

updateCachedPositions = () = > {
  // update cached item height
  const nodes: NodeListOf<any> = this.actualContentRef.current.childNodes;
  const start = nodes[0];

  // calculate height diff for each visible node...
  nodes.forEach((node: HTMLDivElement) = > {
    if(! node) {// scroll too fast? .
      return;
    }
    const rect = node.getBoundingClientRect();
    const { height } = rect;
    const index = Number(node.id.split(The '-') [1]);
    const oldHeight = this.cachedPositions[index].height;
    const dValue = oldHeight - height;

    if (dValue) {
      this.cachedPositions[index].bottom -= dValue;
      this.cachedPositions[index].height = height;
      this.cachedPositions[index].dValue = dValue; }});// perform one time height update...
  let startIdx = 0;
  
  if (start) {
    startIdx = Number(start.id.split(The '-') [1]);
  }
  
  const cachedPositionsLen = this.cachedPositions.length;
  let cumulativeDiffHeight = this.cachedPositions[startIdx].dValue;
  this.cachedPositions[startIdx].dValue = 0;

  for (let i = startIdx + 1; i < cachedPositionsLen; ++i) {
    const item = this.cachedPositions[i];
    // update height
    this.cachedPositions[i].top = this.cachedPositions[i - 1].bottom;
    this.cachedPositions[i].bottom = this.cachedPositions[i].bottom - cumulativeDiffHeight;

    if(item.dValue ! = =0) {
      cumulativeDiffHeight += item.dValue;
      item.dValue = 0; }}// update our phantom div height
  const height = this.cachedPositions[cachedPositionsLen - 1].bottom;
  this.phantomHeight = height;
  this.phantomContentRef.current.style.height = `${height}px`;
};
Copy the code

  • When we now have the exact height and position values for all elements, we change the way we get the starting element corresponding to the current scrollTop (Offset) to cachedPositions:

    Because our cachedPositions are an ordered array, we can take advantage of binary lookups to reduce time complexity when searching

getStartIndex = (scrollTop = 0) = > {
  let idx = binarySearch<CachedPosition, number> (this.cachedPositions, scrollTop, 
    (currentValue: CachedPosition, targetValue: number) = > {
      const currentCompareValue = currentValue.bottom;
      if (currentCompareValue === targetValue) {
        return CompareResult.eq;
      }

      if (currentCompareValue < targetValue) {
        return CompareResult.lt;
      }

      returnCompareResult.gt; });const targetItem = this.cachedPositions[idx];

  // Incase of binarySearch give us a not visible data(an idx of current visible - 1)...
  if (targetItem.bottom < scrollTop) {
    idx += 1;
  }

  return idx;
};

  

onScroll = (evt: any) = > {
  if (evt.target === this.scrollingContainer.current) {
    ....
    const currentStartIndex = this.getStartIndex(scrollTop); . }};Copy the code
  • Binary search implementation:
export enum CompareResult {
  eq = 1,
  lt,
  gt,
}



export function binarySearch<T.VT> (list: T[], value: VT, compareFunc: (current: T, value: VT) => CompareResult) {
  let start = 0;
  let end = list.length - 1;
  let tempIndex = null;

  while (start <= end) {
    tempIndex = Math.floor((start + end) / 2);
    const midValue = list[tempIndex];
    const compareRes: CompareResult = compareFunc(midValue, value);

    if (compareRes === CompareResult.eq) {
      return tempIndex;
    }
    
    if (compareRes === CompareResult.lt) {
      start = tempIndex + 1;
    } else if (compareRes === CompareResult.gt) {
      end = tempIndex - 1; }}return tempIndex;
}
Copy the code
  • Finally, the method of obtaining transform after scrolling is transformed as follows:
getTransform = () = >
    `translate3d(0,The ${this.startIndex >= 1 ? this.cachedPositions[this.startIndex - 1].bottom : 0}px,0)`;
Copy the code

Online Demo: codesandbox. IO/s/a – v – list -…