Infinite List and React

I have worked on Twitter’s new mobile website for the past year. We rebuilt the website using the latest web technologies: React, Redux, Node.js/Express to name a few. It is absolutely an exciting project to work on since you rarely get a chance to rework a large-scale website from the ground up and experiment with the latest tools without having to worry about any historical baggage.

One of the problems that we realized early on is that our Tweet is fairly complex in both the React tree and the DOM tree. A Tweet does not only contain the body text and metadata; it also involves processing #hashtags, @mentions, cards and a lot of Unicode ordeals (one of the most prominent examples is emoji) to make sure we are rendering everything correctly across all platforms.

▲ Tweet can have a complex DOM representation

This normally would not be a problem on a desktop browser, as they have enough processing power to deal with a highly complex DOM tree. However, this is not the case with mobile browsers. We discovered that the performance degrades as the user scrolls further down. What’s even worse is that if we want to implement caching and pre-download say 200 tweets for a user, this will cause our app to effectively render 200 tweets at the same time and lock up the app for a few seconds. I started to look into this problem and realized that a solution to this is to maintain only the visible portion of an infinite list in the DOM tree and render/remove invisible parts as the user scrolls.

How did we solve it?

In the search for a component to support both lazy-rendering and dynamic item height, we developed a component called LazyList. Supporting items of dynamic height can make the system much more complex but unfortunately Tweets have non-deterministic heights due to variable content like cards/picture and text.

The Basics

LazyList works by measuring an item’s height and calculating what slice of items should be displayed on the screen given the scrolled coordinates, this is called a projection. It also applies before/after padding to maintain the facade of out-of-view items, thus not affecting the scroll bar pill in terms of size and position.

Illustration of on-screen layout digraph "Illustration of on-screen layout" { graph [rankdir=RL,splines=false]; node [shape=record,fontname="sans-serif"]; edge [fontname="sans-serif"]; list [ label = "<bp> beforePadder | <it> *invisibleItems* | <v1> visibleItem 1 | visibleItem 2 | visibleItem 3 | visibleItem 4 | <v5> visibleItem 5 | <ib> *invisibleItems* | afterPadder"; ]; viewport_start [shape=plaintext,label="viewport start"]; viewport_end [shape=plaintext,label="viewport end"]; extra_items_before [shape=plaintext,label="extra items for buffering"]; extra_items_after [shape=plaintext,label="extra items for buffering"]; viewport_start -> list:v1; viewport_end -> list:v5; extra_items_before -> list:it [style=dashed]; extra_items_after -> list:ib [style=dashed]; } Illustration of on-screen layout list beforePadder *invisibleItems* visibleItem 1 visibleItem 2 visibleItem 3 visibleItem 4 visibleItem 5 *invisibleItems* afterPadder viewport_start viewport start viewport_start->list:v1 viewport_end viewport end viewport_end->list:v5 extra_items_before extra items for buffering extra_items_before->list:it extra_items_after extra items for buffering extra_items_after->list:ib
▲ Illustration of on-screen layout

In addition to the items visible in the viewport, in order to allow the page to scroll smoothly, we needed to render extra items both above and below the visible region. Typically, this results in one to one-and-a-half pages worth of items. This also gives us a bit of buffer in order to preload the next page of Tweets before the user hits the bottom of the scrollable area. Now that we have a strategy of how this component would work, we will need to fit this into React’s lifecycle methods. Theoretically we will want this to be just like a ListView component – give us items and render function and get lazy-rendering for free.

Lifecycle

The only thing that LazyList is required to know for rendering is a projection of items. A projection is defined as a slice of input items that is visible in the viewport. In order to calculate the projection at any given moment, we will need to figure out the height for each item. A typical approach on the web is to render it off-screen, taking a measurement and re-render it on-screen with the cached measurements. However, this doubles the rendering costs which is impractical for a product used by millions of users on lower-end mobile devices. We moved to an in-place measurement technique: we render items on screen first with a guestimate average height, caching the actual item height for rendered items. We repeat this process until the estimation/cached heights matches all the items on-screen. Using the in-place measurement also allow us to accommodate cases where the item height is changed after rendering, such as when loaded images change the overall height of a tweet.

LazyList lifecycle diagram digraph "LazyList lifecycle diagram" { graph [splines=ortho]; node [shape=box,fontname="sans-serif"]; edge [fontname="sans-serif"]; render_empty [label="render (empty)"]; update_projection [label="Update Projection"]; events [label="events\nresize,scroll"]; height_change [label="item height changed"]; mount -> render_empty; render_empty -> update_projection; { rank=same; mount -> events [style=invis]; } events -> update_projection; update_projection -> render; render -> height_change; height_change -> update_projection [color=green,tailport=ne]; { rank=same; height_change -> end [color=red]; } } LazyList lifecycle diagram render_empty render (empty) update_projection Update Projection render_empty->update_projection render render update_projection->render events events resize,scroll events->update_projection height_change item height changed height_change:ne->update_projection end end height_change->end mount mount mount->render_empty render->height_change
▲ LazyList lifecycle diagram

Initial rendering (mount)

When the component is mounted for the first time, it has no knowledge about what items will fall within the viewport. It renders nothing and simply triggers projection update.

Update Projection

The projection can be generated by adding up the item heights sequentially until it reaches the scroll offset of the container. This is when we know items after this will be in the viewport. We continue to add it up until it is more than the container height. If there’s any item in the process that we do not have the height for, we will guestimate one. The incorrect number will be corrected after we cache its height and update the projection again.

This step will also be triggered when input events, like resize and scroll happens.

Render

Render is fairly straightforward after we’ve established the projection to use. We simply run it through a loop and call the renderer function supplied by the user to render it on screen.

Prologue

After rendering, we update our internal cache of item heights. If we encounter any inconsistencies, it means our current projection is incorrect. We will repeat the process until it settles down. The difference in heights are also deducted from the scroll position so the list will stay at a stable position.

Resizing

Resizing a window changes all item widths which effectively invalidates all cached item heights. However, we definitely do not want to invalidate the entire cache. Think of the case where a user has scrolled down 5 pages: if they choose to resize the window, we will want the app to adapt to it gradually instead of waiting for LazyList to remeasure all items; fortunately the in-place measurement technique works with this scenario. We update new item heights into cache and allow the system to correct itself as the user scrolls. The downside to applying this technique is that the scroll bar pill will be a bit jerky or show sudden resizing due to first-pass rendering using cached heights and correcting itself on second-pass. However, this outcome is preferable to having the app locked up for several seconds.

Scroll Position Stabilization & Restoration

▲ Notice the first tweet is always in the viewport during resizing

Whenever there is a difference in expected item heights and the actual item heights, the scroll position will be affected. This problem manifests as the list jumping up and down randomly due to miscalculation. We will need an anchoring solution to keep the list stable.

LazyList used a top-aligning strategy which means it kept the first rendered item at the same position. This strategy improves the symptom but did not fix it completely because we’re not necessarily aligning items within the viewport. We have since improved it to use an anchor-based solution. It searches for an anchor that is present in both projections before and after updates, usually the first item within the viewport. The anchor is used as a point of reference to adjust scroll position to keep it in the same place. This strategy works pretty well. However, it is tricky to programmatically control scroll position when the inertia scrolling is still in-effect. It stops the animation on Safari and causes slight slow down on Chrome for Windows while working fine on Chrome for Mac and Android, for which we do not have a perfect solution yet.

▲ Timeline position is remembered

Remembering timeline position is one of the feature that most Twitter users expected a client to have. However, it is an interesting challenge due to each browser having their own slightly different strategies to restore scroll positions when navigating to a previously loaded page. Some wait for the whole page to finish loading, some wait extra bit to account for dynamically loaded data. To implement a cross-browser solution, we take the matter into our own hands. We give each infinite scrolling list a unique ID and persist the item heights cache and anchor candidates with it. When the user navigates back from other screens, we use that information to re-initialize the component and re-render the screen exactly as you left it. We take advantage of the scrollRestoration attribute of the history object to take over the restoration whenever available and compensate accordingly if manual takeover is not possible.

Onwards

Being a component that is centered around our performance, this is still a critical component that we work on from time to time. It has a new name VirtualScroller too. We have taken on refactoring, performance tuning (minimizing layout thrashing, optimizing for browser schedulers, etc.) largely thanks to Marius, Paul, the Google Chrome team(especially “Complexities of an Infinite Scroller”; we have taken some advice from it for our improvement plan.) and the Microsoft Edge team.