Tracking Reflows for Fun and Profit

One of the biggest performance problem's we're seeing in Firefox OS is lots of reflows. A reflow is when the layout engine needs to calculate the size of the elements in your web page. If your app changes the CSS appearance of an element or modifies the DOM, a reflow calculates how big and where elements should be laid out. Previously, figuring out when / how a reflow occurred was basically guess and check. Thanks to some awesome work by Paul Rouget, Vivien Nicolas, and Etienne Segonzac in Bug 926371. It's just become a lot easier to check when and how expensive your reflow is.

To do this on Firefox Desktop, simply enable the preference 'devtools.webconsole.filter.csslog' in about:config. Then load up Tools->Developer->Web Console and you should see some reflows occurring. I think you need a debug build though? At the moment, you'll need at least Firefox 27 to try this out (Mozilla Aurora branch).

For Firefox OS, it's a little more complicated. You have to setup the app manager, connect to your device, and click debug on the app you want to check your reflows on. This is the only currently supported way to check reflows on a Firefox OS app. Using desktop-b2g, or adb logcat just quite doesn't work. But once it does, you should get something like this:

reflow.png

Now you can see how much time is spent in a reflow. Awesome!

Better Know an OpenGL

One of the nice things about working at Mozilla is just how much ground there is to cover! Lots of performance problems are due to graphics and reflow issues. Since I didn't know a single thing about either of time, it's a great time to learn. Starting from the bottom up on a whole new topic is a really unique chance, so let's start with Graphics.

I've been starting off by watching these great lectures by UC Davis Professor Ken Joy on computer graphics. The first thing to note is that we need a lot of math to get started, a lot of math. Everything you see on a computer is just a pixel, which translates to a Point in our Cartesian plane. (Hello geometry!) How do we actually draw a curve on a computer?

We mostly use the OpenGL API, which I've learned requires a ton of cruft code. To reduce the cruft code, we use GLUT, which abstracts a lot of the cruft away as well as the platform specific windowing APIs. The ton of cruft code basically tells the OS that we want a window with buttons as well as how big to make the window (800 X 600) etc. The crux of the problem is actually how do we draw shapes and curves on a screen?

In the real world, we can draw curves as a contiguous connected line, creating smooth curves. In computers, we can only represent curves as single points connected by a single line. The fewer points we have, the less "smooth" our curve is. The more points we have, the "smoother" the curve is. Consider a parabola (Excuse me for my horrible handwriting, I should learn matlab or something to draw pretty figures). It is defined by three points [1,1], [2,3], and [4,1], with the peak being at [2,3]. In the analog world, we get a nice clean curve if we draw a parabola with these points:

analog.png

However, in the discrete / OpenGL world, we aren't so lucky. With OpenGL, we can only draw a line between two points, so we draw the same thing but in the discrete world:

discrete.png

What we see looks more like a pyramid than a real curve. To fix the issue, we can add imaginary midpoints between our original 3 points, and draw line segments between these midpoints.

fewerPoints.png

We see that our curve looks a little better, but not quite the same as the analog case. What if we add more points:

morePoints.png

And here is a large crux of the problem with computer graphics. The more midpoints we add, the smoother our curve looks, but the more work our computer has to do. Finding the balance seems to be the key to drawing smooth curves.

Now theoretically, this is great, we just have to find what those midpoints are and we can draw nice clean curves! Essentially, to do 2d curves, we calculate a bunch of points. We feed those points to OpenGL and tell OpenGL to draw lines between them. At the end, we tell OpenGL to draw and voila! A Curve!

Calculating Midpoints

There are tons of different ways of calculating midpoints, mostly named after mathematicians. The one we hear about all the time is a Bezier Curve. A bezier curve is defined by using 4 points, known as the control points. My current understanding of them is that we actually have two sets of two points.

End points - Two points to describe the end points of the curve
Tangent points - Two "invisible" points that pull the curve.

Consider this spline editor. Change the Interpolate from linear to basis and you'll see four points. The two end points where the curve actually goes through determine where the curve starts and ends. The two middle points act almost like gravity, pulling the line towards those points, but not at it.

When we define a bezier curve, we have to define these four points. We can just make them up as we go. Now why is this called a bezier curve? Because once we have these four points, we can plug these numbers into the bezier's formula and we get midpoints! Where do we get bezier's formula? Wikipedia!

B(t) = (1-t^3)P0 + 3(1-t)^2P1 + 3(1-t)t^2P2 + t^3P3

This looks really daunting. What we're really using is what's called a cubic bezier curve since we have 2 tangents (e.g. 2 points in the middle). If you plot y=x^3, you'll see what I mean. It kind of looks like an S rather than x^2. P0 and P3 here are our two end points. P1 and P2 are our two tangent points. Bezier also introduces a new variable t. T is a value between [0-1]. It basically says how many midpoints do we want between our two end points? Plug that number in and we'll get a new midpoint! But t must be between [0-1]. So if we want 20 points, we usually do something like:

1
2
3
4
5
for (int i = 0; i < 20; i++) {
  float t = i / 20.0;
  // Gives us our midpoint
  bezier(P0, P1, P2, P3, t);  
}

Whew that's a lot of math, but now we can finally get some code. Essentially, we have a bezier curve formula, we have 4 points that we made up, and now we just have to decide how many midpoints we want. The more midpoints we have, the smoother the curve. One thing to note is that each point in the bezier curve is actually one axis of the point. So we need to do something like:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
GLfloat bezier(float t, GLfloat P0,
                  GLfloat P1, GLfloat P2, GLfloat P3) {
  // Cubic bezier Curve
  GLfloat point = (pow((1-t), 3.0) * P0) +
    (3 * pow((1-t),2) * t * P1) +
    (3 * (1-t) * t * t * P2) +
    (pow(t, 3) * P3);
  return point;
}

void drawStuff() {
  midpoint_x = bezier(P0.x, P1.x, P2.x, P3.x, t);
  midpoint_y = bezier(P0.y, P1.y, P2.y, P3.y, t);

  drawPoint(midpoint_x, midpoint_y);
}

Now for our final concept. OpenGL has the concept of a "current" point. We have to feed OpenGL a list of points, and tell OpenGL to draw lines between each point. We start by giving OpenGL a single point, calculate the next point using our bezier curve (var newMidPoint), then feed the new point to OpenGL. OpenGL automatically draws the line between those two points, but our new "current" point now points to (newMidPoint). So we go through the loop, calculate another new bezier curve point (var secondMidPoint), feed secondMidPoint to OpenGL, and OpenGL draws a line between (newMidPoint -> secondMidPoint), and we do this over and over.

Let's have an experiment. Let's just tell OpenGL to draw only our bezier curve points, not a line between each one, and let's draw 5 points for now:

5Points.png

We have 6 points total, our starting points plus our 5 bezier midpoints. Now if we tell open gl to draw lines between them:

5Line.png

Not too shabby! Let's make it smoother, let's draw 30 points:

30Points.png

And segments between them:

30Line.png

Not too shabby huh. You can see the final code here. You can play with the number of points by changing t on line 63. You can disregard the z points as we're doing only 2d for the moment.

Combining Curves

Well drawing a single curve isn't too fun, but what if we want something more complicated. All complicated pictures are just a bunch of bezier curves hooked together. These are called a bezier spline. Once I finish drawing something useful, I'll update my blog, but it's a good starting point.

Building Firefox OS On OS X and Hamachi

At my first day at Mozilla, they gave me two brand spanking new Firefox OS phones. Of course, the first thing we do is build Firefox OS and flash the devices with the latest OS from the repositories. Of course, it's much easier said than done! There were a few extra steps that I needed to do to get the build working.

Preparing the Build
There's a nice link on what you need here. If you're lucky, you can just run B2G/scripts/bootstrap-mac.sh and be good to go. Then ignore this post :)

Firefox OS requires a specific version of gcc - 4.6.3, with custom patches, to build Firefox OS. Unfortunately, the bootstrap-mac.sh script only checks that you have gcc 4.6,  not necessarily 4.6.3. However, this version of gcc wasn't quite building correctly for me. As it stands, the clang that comes with OS X as well as the clang that is released on llvm.org cannot build the specific version of GCC. Only GCC can build the custom GCC!

The first step then, is to download the latest stable build of gcc. I used gcc 4.7 and recompiled and installed it by following the instructions. This version of gcc built just fine with clang 3.3. Next, I tried to build the gcc version used with Firefox OS, but I was getting a lot of errors. The main one was:

{standard input}:82:no such instruction: `vmovaps %xmm2, %xmm0'

This is because the homebrew script assumes you're using a newer Macbook Pro that supports the newer AVX instruction set provided by Intel. I had to modify the homebrew script to remove a few flags. If I did a brew --env, I'd get the following output:

brew --env
CC: /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/clang
CXX: /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/clang++ => /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/clang
CFLAGS: -Os -w -pipe -march=native -Qunused-arguments -mmacosx-version-min=10.8
CXXFLAGS: -Os -w -pipe -march=native -Qunused-arguments -mmacosx-version-min=10.8
LDFLAGS: -L/usr/local/lib
MAKEFLAGS: -j4
MACOSX_DEPLOYMENT_TARGET: 10.8
PKG_CONFIG_LIBDIR: /usr/local/lib/pkgconfig:/usr/local/Library/ENV/pkgconfig/10.8:/usr/lib/pkgconfig
OBJC: /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/clang
PATH: /Library/Frameworks/Python.framework/Versions/2.7/bin:/usr/local/bin:/usr/bin:/usr/bin:/bin:/usr/sbin:/sbin:/usr/local/bin:/opt/X11/bin:/usr/local/go/bin:/usr/texbin:/Users/masonchang/Projects/adt-bundle-mac-x86_64-20130911/sdk/platform-tools:/Users/masonchang/Projects/moz-git-tools:/Users/masonchang/Projects/llvm/build/Release/bin:/usr/local/Library/Contributions/cmd:/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin:/Applications/Xcode.app/Contents/Developer/usr/bin
CPATH: /usr/local/include

We can see a few things here that don't quite work well. First, the "-march=native" enables AVX features that might not be available on your computer unless you have the latest Intel processors. Next, we have a minimum OSX version of 10.8, which prevents Firefox OS from building because it'll use the 10.8 SDK libraries rather than the required 10.6 SDK libraries. I couldn't find anything on the home brew web page about changing default configurations, but we can modify the home brew formula for Firefox OS' gcc version to this: 

    ENV['CFLAGS'] = '-Os -w -pipe'
    ENV['CXXFLAGS'] = '-Os -w -pipe'
    ENV['CC'] = '/usr/local/bin/gcc'
    ENV['CXX'] = '/usr/local/bin/g++'

We change the CC and CXX flags to use our explicit gcc 4.7 rather than clang. Then we remove the CFLAGS and CXXFLAGS to be bare bones and not require a minimum OS X version or set the architecture. If we brew install gcc 4.6.3 required by Firefox OS, we should be good to go! 

Running the Build 

After these GCC steps, we should be able to run config.sh and everything should work. The next problem was while actually building Firefox OS, I got an error saying my python version was incorrect. I need python 2.7.3 but I had python 2.7.2. After some discussion with Gregor Wagner, installing the binary distribution of python 2.7.5 worked where as building Python 2.7.5 doesn't. After installing python, I was able to build. Woot, day one complete!

Getting Your Geolocation in Firefox / Firefox OS

Getting your Geolocation in a browser is a fairly easy feature to understand yet has quite a large amount of complexity to implement. First, let's go back to our starting point, we can build a web application that displays our geolocation using the Geolocation Web API. What happens underneath the covers in the browser level to actually get your geolocation?

We start by parsing some of the Javascript, and thus the SpiderMonkey VM. Since our application isn't performance critical, the JavaScript is actually interpreted in Interpreter.cpp. We hit the js::Invoke function to call our native function. A native function is a function built into the VM rather than another JavaScript function in the same script. By this time, the JavaScript interpreter has looked up the function and determined that to get the geolocation, it has to call a native C function in the VM. The function that's called is Navigator::GetGeolocation, which initiates a new Geolocation Object.

During the initialization phase of the Geolocation object, it attaches itself as an "observer", which is just a listener to a GeolocationServices object. The GeolocationServices object is what actually maintains all the information about our Geolocation. Everything discussed so far applies to both Firefox OS and Firefox Desktop. However, how we actually fetch our location now differs between the two platforms.

Firefox Desktop
Firefox Desktop on Mac is a little bit easier to explain. When Firefox requests for your location, it jumps to nsGeolocationRequest::Allow, which fires after you allow Firefox to use your location. Allow() then checks for a cached Geolocation. If it exists, it fires off a new event with your current Geolocation. This is an important underpinning in the browser and JavaScript in general - Everything is an event.

A main thread constantly checks a queue to see if an event has arrived. Once it has, it processes the event. This is called the Event Loop. Our Geolocation just creates a new event and submits it to the queue, where another thread will pick it up and process our location.

Now what happens if we don't have a cached position? Actually what happens is once we create the nsGeolocationService, Firefox uses OS X's CoreLocation service. CoreLocation is an OSX provided API to get your location. You supply CoreLocation with a callback function whenever you want to get an updated location. What Firefox does is tell CoreLocation to callback nsGeolocationService::Update, which calls nsGeoLocationService::SetCachedPosition and sets our cached location. Thus, Firefox actually always has your location due to CoreLocation. When Firefox requests your location, it just reads the cached location which is constantly being updated by OS X's CoreLocation. If you deny your location to a website, Firefox just returns an error and the website doesn't get your address, but internally, (I think) the OS X and Firefox have your location ready to reply.

Firefox OS
Firefox OS has mostly the same logic as Firefox Desktop except there is one big difference. Apps in Firefox OS, like apps on Desktop, are different processes, but core functionality such as getting your Geolocation belong to the core B2G process. Different apps talk to the core B2G process to request your Geolocation. Each app has it's own event queue that's being run.

When an app requests your location, it creates a new event requesting your Geolocation. Through IPC, the event gets pushed onto the main B2G's event loop queue. When the main B2G process handles your Geolocation request, it submits the position event back through IPC to your app. The app then gets a Geolocation update, which pushes another event to update whatever part of the app needed the location.

Finally, there is some part of the OS that has to actually call the GPS driver to get the location. I haven't found that part yet, but I'm on the hunt!