Virtual Rendering 1,000,000 Items Efficiently

You probably haven’t heard from me for a while, and probably some reasons, and one could well be attributed to my dark periods of un-productivity.

Link to the Demo. Recommended that you’re run it with Chrome.

But if you are hearing from me now, that’s because there’s some progress I would like to share on a small experiment, which is an attempt to render large amount of data using html, javascript in the browser efficiently.

Here’s the problem: Let’s say you have a million rows of data, and to simply create a million Divs and placing them to your html document’s body is a good way to freeze or crash your browser, that’s after chewing up large amount of RAM and CPU. That doesn’t only to browser applications, because many text editors are pretty incapable of opening large files.

One example of how I encountered this problem was running three.js inspector with a particle scene, and I realized attempting that the couple thousand or even hundred elements representing them was locking up the browser. One motivation for this experiment was also to try creating new UI components for a more efficient three.js scene inspector.

Solution: Placing objects in memory are way faster than placed in the dom or rendered. In the case of huge list in a scroll panel, the trick is to hide all objects and render only the items in view. Though this isn’t super simple, it isn’t totally new, and a couple of good libraries have already utilized such techniques. CodeMirror, the extensible and powerful browser based code editor, uses handles large amount of code in this manner. Slickgrid, a powerful open source grid/spreadsheet library created by a Google employee, is built on this technique to allow large rows of data. Sites that implement the “infinity” scrolling interface (eg. Pinterest, Facebook timeline) utilizes a similar technique to reduce huge memory footprint (twitter, I’m looking at you).

Approach: So why did I try to do this myself? Similar to reasons why one would write a library is to have more understanding and control over your own code, while experimenting on stuff you otherwise wouldn’t have ever try. In this experiment, I got to attempt skinning my own scrollbar, as well as to experiment and benchmark a DOM versus a Canvas implementation of Virtual Rendering. In this post, we would look at the DOM approach, which is similar to how CodeMirror and Slickgrid do it.

If you take a look at the source, there 4 simple classes.

1. SimpleEvent
A minimalistic approach to do the observer patten in the style of Signals.

For example usage,

2. ScrollBar
This is a UI component that displays a scrolltrack and slider, that fires some scroll events when scrollbar is clicked or dragged via .onScroll. Its 2 public interfaces are .setLength() for defining the size of the slider block in percentage, while .setPosition() moves the slider according to the document viewport’s position by a fraction.

(See bottom for more UI/UX notes on the scrollbar)

3. RowItem
The row item is responsible for storing its own data and rendering its dom representation when it comes into view. Here, it simply stores a string for its text data.

For visual representation, its needs to store its x, y, width and height to be activated and positioned correctly for rendering.

4. ScrollPane
This is class which integrates all the above into this Virtual Rendering component. Firstly, it needs to be represented as a div element to be inserted to the dom. ScrollPane tracks the items, and keeps the total virtual area it contains. Based on its dimension, it calls ScrollPane to update its visual elements. The ScrollPane listens to its component for mousewheel events and listens to the ScrollBar for scroll events.

On any request to update its viewport, ScrollPane iterates over its item, quickly find which RowItem are in view and calls draw(). RowItem would create dom objects on demand, and position it. Upon another update, dom objects found visible in the previous render would be reused and those elements scrolled out of view would be remove from dom and destroyed to free memory.

Results: While this has only been tested and ran in Chrome, I’m pretty satisfied with the results of this hack. At a million objects (I’ve tested up to 6 million objects), scrolling is pretty responsive, initially loading it takes ~2 seconds to load, each repaint takes ~25ms, and the heap memory footprint stays below 100Mb. Apart from requiring more refactoring, i think its has quite minimal javascript and css.

Applications: Apart of my planned usage for a revamp three.js inspector, there are perhaps a few mini usages for this widget. For example, the developer’s console can choke up when displaying huge amount of data (now chrome devtools splits them up into small sub chunks, so it works but not the best way imho), and such could be a solution to this problem.

So hopefully this little experiment would find itself some nice usage. Until you hear from me again, continue reading for more side thoughts when I was playing around on the scrollbar. And the link to the demo if you didn’t see it earlier.

UI/UX notes on the scrollbar.
While working on the Scrollbar implementation, I observed that clicking in the track outside the slider has a same effect of “page up” and “page down” both in mac and windows. Instead of moving the slider to the clicked position (as I thought was the correct behavior initially), it fires onScroll event to a controller listener. While it seems that Mac Lion “un-obstructive” scrollbars are “in”, evidenced by sites like Facebook that imitate that, I’m however not a fan of it. Somehow I find those scrollbars ugly for applications that have a non-white background, so I’ve tried to style my scrollbars in the dark gradient colors after Sublime Editor instead.

Another challenge is that the slider would not be able to size proportionally as it would result in thinner than a pixel height for huge list. Therefore the scrollbar has an minimal size which makes it more practical for dragging. There’s probably more tweaks that can be done here, and there are alternative UI designs that eliminates the scrollbar in large lists (eg. your iphone contact list).

2 thoughts on “Virtual Rendering 1,000,000 Items Efficiently

  1. Wow, very impressive!
    Thanks a lot for sharing! This will definitely come in very handy.

    P.S. When dragging the ‘handle’ of the scrollbar, the scrollbar only updates if your mouse is over the scrollbar’s track – which makes it feel sort of broken.

Comments are closed.