Friday, April 19, 2013

How LinkedIn WebView app mitigate the infinite scrolling: HTML5 developer perspective

This is a 2 part article. Please refer to the following blogs(see below) on issues faced by WebView apps in handling page scrolling scenario (infinite page scroll).
One advantage gained by the WebView application is the content is infinite and can be fetched from the web servers forever. This results in the DOM tree in WebKit growing infinitely. This advantage of WebView application is used by book store, mp3 store, video store vendors to provide an infinite list of books, songs, videos they prefer to sell. The disadvantage of this model is how effectively the local device memory is managed and how the user interactions are made smooth enough to hit the 60 fps scrolling rate (for the video mode LCD panels).
The first part of the article is looking at the infinite scrolling problem from the HTML5 perspective. Second part of the article will cover from WebKit perspective.

Please refer to this article [http://engineering.linkedin.com/linkedin-ipad-5-techniques-smooth-infinite-scrolling-html5] for what changes as an HTML5 app developer you can adopt to achieve smooth, crash free infinite page scrolling.

In short the article recommends:
  • unloading offscreen images
  • hiding offscreen pages
  • removing offscreen pages
  • avoid scaling for images and CSS box-shadow effects
  • minimizing DOM nodes
All the above techniques are aimed at  keeping DOM tree to a reasonable size (removing DOM tree nodes which are few pages away from the current view port) thereby ensuring WebKit Threads and UI threads have reasonable data to work with.

How LinkedIn WebView app effectively uses the local storage in mobile devices.

Excerpts from the article: http://engineering.linkedin.com/mobile/linkedin-ipad-using-local-storage-snappy-mobile-apps

In short LinkedIn WebView application is designed bottom up to effectively use local storage.
  • they used the local storage as persistent storage
  • they reduced the number of network fetches by effectively using the local storage and using a stale time for a resource
  • asynchronous network requests similar to AJAX running in background

Another article on why not WebView App - By Zynga

Expressing similar sentiments by Zynga CTO. Excerpts from the article: http://lists.w3.org/Archives/Public/public-web-perf/2012Sep/0016.html

Memory
While the navigation timing APIs help us understand bottlenecks in our loading time performance,
we’d like you to help us analyze what’s happening during runtime.

On mobile devices, the biggest performance bottleneck for large scale, high fidelity apps and games turns out to be memory consumption. As soon as you run out of physical memory, constant swapping occurs and runtime performance of your web project dramatically suffers.

As web developers, we currently have no way of understanding how memory is consumed.

1. Javascript

  *   We don’t know how much memory a newly created object or function allocates
  *   We can’t call the GC manually, and there is no guarantee that calling “delete” will trigger the GC right away

2. Images

  *   We do not have access to the resource of an image, just the DOM representation
  *   We can’t “unload” images reliably
  *   We don’t know when assets are uncompressed
  *   We don’t know when an uncompressed, compressed or both representations of an image is kept in memory and for how long

3. Static assets

  *   Static assets include:
     *   Non-interpreted JavaScript
     *   Stylesheets
     *   Uncompressed images
  *   We want to know how much total memory is consumed by these static assets, as memory is usually shared across all of the above

4. HW Acceleration
This is tricky as it is a platform specific problem, but it doesn’t make it less important. A large number of browsers is using a different render path for content they can hardware accelerate. Said content is usually composited on the CPU first and then uploaded as a texture to the GPU. At this point, it
 becomes a “layer” and easy modifications like opacity and moving the layer around to not trigger recreating the layer. We need information on when layers are created, destroyed and recomposited. We need this to understand performance characteristics, but we also need it to control our total memory heap - an image wrapped in a div with a red border that gets uploaded as a GPU layer consumes twice the amount of uncompressed pixel memory.

We realize and appreciate that browser vendors work hard on abstracting this issue and ideally agree that
 acceleration should be automatic and no concern to the web developer – but reality shows that we do not have that luxury yet, as false layer management is hazardous.

Canvas
Almost all modern browsers hardware accelerate Canvas nowadays and do so by trying to understand how long a certain texture is needed on the GPU through a set of deterministic algorithms. Unfortunately as developer, this often does more harm than good in an environment when you have to be in full control of the situation. We want to be able to understand when textures are kept in a buffer and when they’re released again.

As a practical example: We have implemented a scrolling worldmap as a proof-of-concept in canvas that 
you could pan with the mouse/touch, and one viewport was represented by one image drawn to the canvas. At first, we’d always draw two adjacent pictures (so the user never see’s white background), but if you let go of the mouse, we’d do a “bounce” deceleration of the movement that shows the next logical image in the row. As soon as the logic detects that it needs to draw a new image, texture swapping happens in the background (especially visible on iOS) and you will notice a visible hitch (50+ms).  The unfortunate solution was to always draw all three images at any given time, even when one of them was off -screen. 

5. Total available memory
We want to be able to query the total available physical memory on the device running the browser 
(or if it is capped for my web app, the capped size).

Even though it doesn’t guarantee anything, it allows us to better judge what we can do, and what we shouldn’t do. 

6. Display refresh rates
It needs to be understood how much of a real world problem this is, but it is relevant with any screen that isn’t set to 60 Hz or a multiple of it.

We’d like to query the display refresh rate and the rAF interval in order to minimize jutter.

7. Garbage Collection
We want to be able to:

  *   Trigger garbage collection manually
  *   Understand the execution interval of GC (i.e an event triggered on the window)
  *   Understand the time a GC took (in order to optimize our framerate against it, could be reported through the same event)
  *   Disable GC and only trigger it manually


What's slowing down Mobile Facebook?

Reasons cited by Facebook for switching from WebView to native app in iOS platform. 
In short the issues to some extent can be resolved by exposing new JS APIs:


  • API to enable JS to query/manage available physical/image memory, total texture memory, # of tiles, etc.
  • API to query HW FPS (PVRTune like)
  •  API to query JS heap size, object count
  • API to invoke JS GC manually
  • API to query display refresh rate and requestAnimationFrame trigger frequency
  • API to query browser composition info (# layers, # SW composited, # HW composited, etc.)
Excerpts from http://lists.w3.org/Archives/Public/public-coremob/2012Sep/0021.html.

Following the recent announcements[1] we (Facebook) made about rebuilding
our iOS app using more native technology, we have had a lot of requests to
provide detailed feedback on the performance issues we encountered while
building for the mobile Web. Here it is. Comments welcomed.

1. Tooling / Developer APIs
---------------------------

The lack of tooling in mobile browsers makes it very difficult to dig down
and find out what the real issues are. Hence tooling, or rather,
lack-thereof is a key issue.

The biggest issues we've been facing here are memory related. Given the
size of our content, it's not uncommon for our application to exhaust the
hardware capabilities of the device, causing crashes. Unfortunately, it's
difficult for us to understand exactly what's causing these issues. GPU
buffer exhaustion? Reaching resource limits? Something else? hard to say.

### What's missing? ###

Mainly, dev tools on the device and/or easily accessible remotely.

Things we'd want to know more about as we develop:

#### Down memory lane ####

- Heap size,
- Object count,
- GC cycles,
- GPU buffer size,
- resource limits.

Some of those are very much useful outside of the development phase,
however. E.g.: Linkedin uses UA string sniffing[2] to determine how many
pictures can be kept in memory before hitting the device's limit, an API
to the device's memory resource would be a much more appropriate (albeit
finger-printable) way of doing that.

#### FPS ####

- The ability to measure fps at the hardware level. This is essential for
testing[3], but would also be very useful to determine whether to use
infinite scrolling or pagination, for example. Same fingerprinting caveat
as above.


2. Scrolling performance
------------------------
I've already started sharing some of it with the W3C WebPerf WG[4]. Will
continue bringing it to other relevant WG in the upcoming weeks.

This is one of our most important issues. It's typically a problem on the
newsfeed and on Timeline which use infinite scrolling (content is
prefetched as the user scrolls down the app and appended) and end up
containing large amounts of content (both text AND images). Currently, we
do all of the scrolling using JS, as other options were not fast enough
(because of implementation issues).

### QoI Issues

- Inconsistent framerates, UI thread lag (stuttering).
- GPU buffer exhaustion due to size of content and number of images.
- Native momentum scrolling has a different feel across operating systems.
JS implementation end up being tailored for one OS and feels wrong on
other ones (uncanny valley).
- Perf issue with touch events on Android devices (latency, not enough
events) which makes JS implementations of scrolling more brittle there.

### Requirements:

- Scrolling must be fast and smooth (this is really important for
engagement).
- It must trigger a given set of events so content can be prefetched,
computed and appended as the user scrolls towards the bottom of the loaded
content.
- It must allow i/o and computation in the background (without affecting
the smoothness).
- It must allow appending fresh content to the main content while
scrolling (again, without affecting the smoothness).
- It must reliably handle scrolling though a lot of content, including
lots of images.
- It must be possible to capture touch events during scrolling.

### new API suggestions:

- A standardized way to enable momentum scrolling across browsers.
- `onscroll` events triggered *during* scrolling.
- Structured cloning of rootless document fragments (for building doc
fragments in workers and moving them back to the main thread to be
appended).
- Simple way to implement pull to refresh (via dedicated off-bound-scroll
events?). 


3. GPU
------

Currently, the GPU is a black-box (which from what I understand is what
vendors would like to keep it as). In truth however, developers rely on
tricks[5] to force given content to be hardware accelerated. So it
basically a black-box with a clunky API to add things to it. Given the
size of GPU buffers relative to the size of content consumed on devices
nowadays, I doubt well get to a place where managing GPU can be left
strictly to the browser in a reasonable amount of time.

Think there's value in at least discussing the pros and cons of providing
some form of API to the GPU, if that's possible at all.


4. Other
--------

- Better touch tracking support, especially on Android.
- Smoother animations are always an asset.
- Better caching.
- AppCache is soooooo busted we stopped using it[6].

Best,

--tobie

---
[1]: 
https://www.facebook.com/notes/facebook-engineering/under-the-hood-rebuildi
ng-facebook-for-ios/10151036091753920
[2]: 
http://engineering.linkedin.com/linkedin-ipad-5-techniques-smooth-infinite-
scrolling-html5
[3]: http://lists.w3.org/Archives/Public/public-coremob/2012Aug/0014.html
[4]: http://www.w3.org/2012/09/12-webperf-minutes.html
[5]: http://davidwalsh.name/translate3d
[6]: https://etherpad.mozilla.org/appcache-london

Good resources for Web App developers


(1) To get involved with the World Wide Web Consortium (W3C)
Now anyone can form a W3C community group that could lead to standardization.
It would be good to monitor these W3C sponsored community groups and any new ones that are formed. I expect some of these to evolve into full W3C level (or even at ISO level) standards. Declarative-3D and Web Payments groups looks interesting from our perspective.

 (2)  Graphics and OGL programming
·         
(3) Benchmarks

·         
(4) Testing
·        A neat tool from Google GWT team that will give you lot of insight into a Chrome desktop browser – unlike Firebug/FF or WebInspector/Chrome, Speed Tracer tool will break down all Chrome web processing – including paint, layout, style calculations.But it only works on a desktop Chrome browser and on a dev channel Chrome build.So next time you want to compare a scenario on desktop Chrome, I suggest try it with Speed Tracer.

http://code.google.com/webtoolkit/speedtracer/ (To monitor time spent on different WebKit activities likes loading resources, parsing (html, css, & js),  layout, painting, and rendering)


(5) Good resources on HTML5 know-how

  • http://www.webplatform.org/


Bit Twiddling Hacks

Recently I have come across this interesting article on bit twiddling hacks from Stanford university.


"When totaling the number of operations for algorithms here, any C operator is counted as one operation. Intermediate assignments, which need not be written to RAM, are not counted. Of course, this operation counting approach only serves as an approximation of the actual number of machine instructions and CPU time. All operations are assumed to take the same amount of time, which is not true in reality, but CPUs have been heading increasingly in this direction over time. There are many nuances that determine how fast a system will run a given sample of code, such as cache sizes, memory bandwidths, instruction sets, etc. In the end, benchmarking is the best way to determine whether one method is really faster than another, so consider the techniques below as possibilities to test on your target architecture" [Source: http://graphics.stanford.edu/~seander/bithacks.htm]

Link: http://graphics.stanford.edu/~seander/bithacks.html

A Performace Study On Using Uncached Buffers In WLAN Drivers



This is short study conducted in SDIO WLAN driver (Linux) in August 2010. I am publishing it to gain some traction on the idea of "how marking some buffers as uncached can significantly reduces the CPU load and improve the embedded system performance."

Introduction
A short study on the benefits of using uncached buffers in WLAN driver. I did an experiment with WLAN driver to get rid of some cache coherency overhead on DMA buffers by making them uncached. The results are encouraging and would like to share with the rest of the driver developers.Give it a try in your respective embedded components on a case by case basis.

In the below code snippets uncached buffers will be enabled if you define the ENABLE_DMA_UNCACHED_BUFF. 
Follow the code appropriately.

Section 1: 
How to allocate Uncached DMA buffers? Note that I am storing the base address after the allocation of 8KB and call it physical_base_readaddress. I need to do it since for every DMA transaction I will be using any portion of the 8 KB chunk i.e. Say if I am transmitting something, then my data will be located any where within the 8 KB. In that case I need to compute the actual dma_bus_address based on the dma_base_readaddress and physical address offset of the data chunk I will be transmitting. (Refer Section 3)

/* Allocate a DMA-able buffer and provide it to the upper layer to be used for all read and write transactions */
    if (pDmaReadBufAddr == 0) /* allocate only once (in case this function is called multiple times) */
    {
#ifndef ENABLE_DMA_UNCACHED_BUFF      
        pDmaReadBufAddr = kmalloc (MAX_BUS_TXN_SIZE, GFP_ATOMIC | GFP_DMA);
#else
        pDmaReadBufAddr = dma_alloc_writecombine(g_drv.dev, 8192, &g_drv.dma_base_readaddress, GFP_KERNEL);
#endif
        if (pDmaReadBufAddr == 0) { return -1; }
    }

#ifndef ENABLE_DMA_UNCACHED_BUFF       
        *pRxDmaBufAddr = pDmaReadBufAddr;
        *pTxDmaBufAddr = pDmaWriteBufAddr;
#else
        g_drv.physical_base_readaddress = *pRxDmaBufAddr = pDmaReadBufAddr;
        g_drv.physical_base_writeaddress = *pTxDmaBufAddr = pDmaWriteBufAddr;
#endif   

Section 2:
Uncached DMA buffer clean up

if (pDmaReadBufAddr)
    {
#ifndef ENABLE_DMA_UNCACHED_BUFF
        kfree (pDmaReadBufAddr);
#else
        dma_free_writecombine(g_drv.dev, 8192, pDmaReadBufAddr, g_drv.dma_base_readaddress);
#endif
        pDmaReadBufAddr = 0;
    }
   
Section 3:
 DMA Transaction (Only for Tx Buffer). Note I am avoiding the dma_map_single () call.

#ifndef ENABLE_DMA_UNCACHED_BUFF
    {
        dma_bus_address = dma_map_single(g_drv.dev, pData, uLen, DMA_FROM_DEVICE);
        if (!dma_bus_address) {
            PERR("sdioDrv_WriteAsync: dma_map_single failed\n");
            return -1;
        }
    }
#else
    {
        dma_bus_address = g_drv.dma_base_readaddress + (dma_addr_t)(pData - g_drv.physical_base_readaddress);
    }
#endif

Section 4:
 DMA Callback. Note I am avoiding the dma_unmap_single() call.

if (g_drv.dma_read_addr != 0) {
        //printk(KERN_INFO "in return sdioDrv_ReadAsync ret\n");
#ifndef ENABLE_DMA_UNCACHED_BUFF       
        dma_unmap_single(g_drv.dev, g_drv.dma_read_addr, g_drv.dma_read_size, DMA_FROM_DEVICE);
#endif        
        g_drv.dma_read_addr = 0;
        g_drv.dma_read_size = 0;
    }

Based on the DMA direction (DMA_FROM_DEVICE / DMA_TO_DEVICE) appropriate cache invalidate or cache flush operations are performed to maintain the cache coherency for every dma_map_single() call and dma_unmap_single().
Apart from the above cache operations which take CPU cycles, there is a possibility of heavy cache misses (pollution) because of frequent cache operations. This is of high importance for web browsing use case, where webkit caches lot of data that makes a given web page. Cache misses are costly in web browsing use cases. Of course this does comes with cost. In my case, I was doing a memcpy on those DMA buffers (uncached buffer) with my internal buffer (cached skb buffer) and thereby taking a hit.

From the internal tests I did, following are the performance numbers I have gathered.
Http Throughput
Uncached DMA buffer
Cached DMA buffer
18.67 Mbsec
17.1 Mbsec

Avg CPU Utilization - HTTP throughput test (8MB file download)
Avg CPU Utilization - Static CNN web page load
Uncached DMA buffer (%)
Cached DMA buffer (%)
Uncached DMA buffer (%)
Cached DMA buffer (%)
User (50) + Sys(8)
User(63) + Sys (8)
User (25) + Sys (33)
User (50) + Sys (31)


[*Apart from the user and system cpu utilization reduction, wlan workqueue cpu utilization dropped down (by around 10%) because of eliminating the dma_map_single() and dma_unmap_single() calls , but at the same time sdio workqueue increased (by around 6%) because of memcpy from uncached to cached buffers.]

Afer bit of literature survey, I came across this interesting research paper [http://quning.org/self/pku_cache.pdf] worth reading. It talks about advantages of using uncached buffers in certain use cases.
(1)   Talks about making DMA buffers uncached within Ethernet driver (similar to what I did in my experiment). Conclusion is it helps significantly in increasing throughput in TCP Tx and to some extent in TCP Rx.
(2)   Takes implementation (1) one step higher by making the skb buffers (descriptors that holds that actual TCP packet) uncached. I didn’t try this.
(3)   Talks about pushing the TLB page table to uncached memory region.