Monday 17 February 2014
Implementing Virtual Widgets On The Web Platform
Some applications need to render large data sets in a single document, for example an email app might contain a list of tens of thousands of messages, or the FirefoxOS contacts app might have thousands of contacts in a single scrolling view. Creating explicit GUI elements for each item can be prohibitively expensive in memory usage and time. Solutions to this problem often involve custom widgets defined by the platform, e.g. the XUL tree widget, which expose a particular layout and content model and issue some kind of callback to the application to populate the widget with data incrementally, e.g. to get the data for the currently visible rows. Unfortunately these built-in widgets aren't a good solution to the problem, because they never have enough functionality to handle the needs of all applications --- they're never as rich as the language of explicit GUI elements.
Another approach is to expose very low-level API such as paint events and input events and let the developer reimplement their own widgets from scratch, but that that's far too much work.
I think the best approach is for applications to dynamically create UI elements that render the visible items. For this to work well, the platform needs to expose events or callbacks informing the application of which part of the list is (or will be) visible, and the application needs to be able to efficiently generate the UI elements in time for them to be displayed when the user is scrolling. We want to minimize the "checkerboarding" effect when a user scrolls to a point that app hasn't been able to populate with content.
I've written a demo of how this can work on the Web. It's quite simple. On receiving a scroll event, it creates enough items to fill the viewport, and then some more items within a limited distance of the viewport, so that browsers with async scrolling will (mostly) not see blank space during scrolling. Items far away from the viewport are recycled to reduce peak memory usage and speed up the item-placement step.
The demo uses absolute positioning to put items in the right place; this is more efficient than moving elements around in the DOM to reorder them vertically. Moving elements in the DOM forces a significant amount of restyling work which we want to avoid. On the other hand, this approach messes up selection a bit. The correct tradeoff depends on the application.
The demo depends on the layout being a simple vertical stack of identically-sized items. These constraints can be relaxed, but to avoid CSS layout of all items, we need to build in some application-specific knowledge of heights and layout. For example, if we can cheaply compute the height of each item (including the important case where there are a limited number of kinds of items and items with the same kind have the same height), we can use a balanced tree of items with each node in the tree storing the combined height of the items to get the performance we need.
It's important to note that the best implementation strategy varies a lot based on the needs and invariants of the application. That's one reason why I think we should not provide high-level functionality for these use-cases in the Web platform.
The main downside of this approach, IMHO, is that async scrolling (scrolling that occurs independently of script execution) can occasionally and temporarily show blank space where items should be. Of course, this is difficult to avoid with any solution to the large-data-set problem. I think the only alternative is to have the application signal to the async scroll thread the visible area that is valid, and have the async scroll thread prevent scrolling from leaving that region --- i.e. jank briefly. I see no way to completely avoid both jank and checkboarding.
Is there any API we can add to the platform to make this approach work better? I can think of just a couple of things:
- Make sure that at all times, an application can reliably tell which contents of a scrollable element are going to be rendered. We need not just the "scroll" event but also events that fire on resize. We need some way to determine which region of the scrolled content is going to be prerendered for async scrolling.
- Provide a way for an application to choose between checkerboarding and janking for a scrollable element.
Comments