Monday, 20 December 2010

Iterated Prisoner's Dilemma

Last Sunday we had a sort of workshop on "negotiation" for some of the Mozilla managers. Part of this workshop was an exercise amounting to playing Iterated Prisoner's Dilemma, with some twists which aren't relevant here. There were three independent games, each with two players, each player being a team of three or four people. We were instructed to maximise our own score without regard to the other player's score.

My approach was to observe that if both teams behave perfectly rationally, they will use the same strategy. Then the optimal strategy is obviously to always cooperate. If the other team defects then you know the rationality assumption doesn't hold, so the game gets more difficult (probably devolving to the game-theoretic equilibrium of always defecting, but then asymptotically it doesn't matter what you did before detecting defection). Fortunately for us the other team was in fact rational enough to always cooperate and we played a perfect game. (If the number of iterations is known in advance, defecting on or before the last round might make sense, but we couldn't be sure how many rounds there were going to be so this didn't matter.) This approach is known as superrationality although I wasn't aware of that at the time...

One surprise for me was that at least three of the six teams did not always cooperate. I was a bit disappointed to find that not all my colleagues think like me :-). I don't think that was supposed to be the lesson of this exercise, though :-).

Another surprise was that some people expected me to play the game according to "Christian principles". In fact, I was purely trying to optimize the objective function we were given, regardless of what God would want. This raises a very interesting question: is it OK to disobey God's commands within the framework of an artificial game? In many games, especially games with more than two players that involve alliances, lies and betrayal are an essential part of the game. Is it OK for a Christian to lie and betray in such games?

I think the answer depends on the context. If everyone understand it's "just a game", the diabolical behaviour is demanded by the framework of the game, and there are absolutely no hard feelings about such behaviour, it seems harmless. But in any context where others might expect you to be obeying God even within the framework of the game, I think we have to follow Paul and play it safe so we do not "cause others to stumble". So I think in hindsight I was wrong to ignore Christian considerations in our negotiation exercise, although I think they lead to the same results anyway.

So what would Jesus do in a real-life Iterated Prisoner's Dilemma? It seems obvious: "do to others what you would have them do to you", which leads to the same analysis as I had before --- cooperate. If the other player defects, the Sermon on the Mount still applies --- "turn the other cheek --- and also "forgive seventy times seven times": we are asked to cooperate in the face of repeated defection.

Interestingly, in this game, belief in the trustworthiness of the other player --- or even belief in divine justice --- lead to superior joint outcomes on average even if the belief is false. Most people think it's obvious we should believe only what is true, but I don't think that principle is obvious at all in (for example) materialist utilitarian frameworks. It should be obvious to Christians.

Friday, 3 December 2010

GPU-Accelerated Video Playback In Firefox 4

Now that accelerated layers have been turned on for a while in Firefox 4 betas, I want to explain what this means for HTML5 <video> playback in Firefox and how it compares with what Adobe is doing in Flash 10.2.

I've already written about our layers framework and how that contributes to GPU-accelerated rendering. For each frame, our video decoder libraries (libvp8, libtheora) produce a YCbCr (aka YUV) image in their output buffer in system memory. This is usually, but not always, in 4:2:0 format. In the video decode thread we wrap this buffer up into a YCbCrImage object, which makes a copy. (We have to copy here because the decoder libraries overwrite their output buffer for every frame, and we're decoding a bit ahead of the current frame to avoid jitter.) Exactly how that copy is made depends on the layers backend:

  • For GPU backends that support multithreaded access to GPU resources (currently our D3D10 backend), the video decoder thread copies the output buffer directly into VRAM. This is the most efficient approach.
  • For GPU backends that don't support multithreaded access, we copy the output buffer in system memory. The buffer is uploaded to VRAM later when we paint on the main thread.
  • For CPU-only rendering, we convert the output buffer from YUV to RGB (while also scaling it to the expected output size) on the video decoder thread.

Actual rendering happens on the main thread. When we composite an ImageLayer containing a YCbCrImage into the window, the GPU converts to RGB at draw time using a shader program (and also handles scaling). When we're not using the GPU, we just draw the pre-converted image (possibly with some rescaling if the output size has changed since we did the convert-and-scale step).

This architecture seems optimal given the constraints we're currently working with, although it will need to evolve in a few directions. Other than being fast, it works well for Web authors. Unlike Adobe's "stage video", it just works without authors having to do anything. You can overlay and underlay content around the video without losing acceleration. You can wrap it in a container with CSS opacity and 2D transforms, scroll it and clip it, without losing acceleration. (Currently a few effects will cause us to deaccelerate --- if the video has an ancestor element with 'border-radius' and non-visible 'overflow', an ancestor with CSS mask, filter or clip-path, or an SVG ancestor. We'll fix those cases post-FF4 by accelerating them.)

This design will need to evolve in a few directions. We currently don't have hardware decoders for our video formats, but that will change as hardware support for VP8 spreads, and we'll need to take advantage of it. We may need to introduce a new Image type or even a new Layer type to encapsulate hardware decoding. I hope that there will be an efficient way to get decoded video data into textures, otherwise we'll have to limit the use of hardware decoders to whatever special cases their APIs support.

Some devices have GPUs with bad enough shader performance that doing YUV conversion with shaders is a noticeable performance hit. But some of them have native support for YUV-format textures or surfaces with dedicated hardware for YUV conversion. We should use those features. This won't require any architectural changes.

In Fennec, we composite the layer tree in a different process to the content process that actually does the video decoding. This will later be true for desktop Firefox too. This requires us to ship our YCbCr frames through shared memory or shared VRAM buffers, but we should be able to keep the same basic architecture.

The separate compositor process gives us one extra advantage. If the main thread of the content process is busy (e.g., running some in-page Javascript), we'll be able to deliver decoded video frames directly from the video decoder thread to the compositor process and render them on the screen. This means we'll be able to maintain smooth video playback no matter what else the browser is doing. (At least until the demands of video decoding and GPU compositing completely overwhelm your system...)

Friday, 26 November 2010

Measuring FPS

It seems standard practice for Web authors to measure performance in FPS (frames per second). There are two large problems with this.

First, FPS is meaningless above 60 or so, because you normally can't get more frames than that onto the screen. A well-designed software stack will actually prevent FPS from rising above 60 --- those extra frames are wasting power. More than 60 FPS means you have a bug (or you are doing very specialized full-screen gaming --- i.e. not a Web browser). I discussed this in more detail here.

Second, Web authors normally measure FPS as "how many times did my event handler run per second". But what they actually should be measuring is how many different frames the browser was able to paint to the screen per second, and that's a very different thing, since a setTimeout handler (for example) can run multiple times between browser repaints. It's understandable that Web authors would make such a mistake, since browsers haven't provided a way to measure the real FPS. However, in Firefox 4 we have added an API for this: mozPaintCount. Use it!

I think authors need to get into the habit of measuring FPS using mozPaintCount or something similar on other browsers and determining first whether their app is able to reach 50-60FPS. If it can, then further performance improvements can only be measured by increasing the complexity of the scene until FPS starts dropping off. Microsoft's FishIE Tank is the right approach. (I don't know how they try to measure FPS though; they're probably not using mozPaintCount, so it's probably not very accurate.)

Most Unusual Rugby Commentary

This is very weird. French philosopher Bernard-Henri Lévy writes about the recent rugby match between Ireland and the All Blacks ... in exactly the style you'd expect from a French philosopher. It's cool yet slightly annoying ... again, as you'd expect from a French philosopher!

Wednesday, 24 November 2010

Herald Interview

Adam Gifford from the Herald gave me a phone interview a couple of weekends ago, and his column is now online. I like it --- thanks Adam!

Tuesday, 23 November 2010

Brain Drain Vs Foreign Invasion

Apparently a lot of people in the USA are upset about the H1-B visa program, especially as it applies to "IT" workers.

I've always found it ironic that at the same time Americans complain about foreigners stealing US jobs, people in the originating countries complain about the "brain drain" of talent moving to the US. Can both groups be right? Would everyone be better off if talent stayed at home?

I tend to think not. I suspect the complainants on the US side undervalue the contributions of foreign workers. If they successfully shut down visa programs, jobs will simply be outsourced to where the workers are. If outsourcing is throttled, entire companies will move. In any event the whole US economy will suffer.

Personally, I think a reduced inflow of talent to the USA would be a good outcome. "Brain drain" effects are destabilizing; they create vicious cycles in the originating countries, and don't deliver commensurate benefits to the destination country.

A confounding issue here is that "IT" and "high tech" are not synonymous. A lot of H1B jobs are IT drudgery; changes there will not affect genuine innovation or national competitiveness. Making it difficult for PhD graduates to stay is a different story, but I suspect this important distinction will be lost in the battle.

Wednesday, 10 November 2010

Clinton Bedogni Prize

Last night at the New Zealand Open Source Awards in Wellington I was honoured to be presented with the Clinton Bedogni Prize for Open Systems. The prize is funded by an endowment from the Bedogni family to commemorate their son, who had a passion for Linux and open source.

I explained to the audience that I love making software, and I'm actually amazed that people pay me to do it, and especially to then give the results away to the world! To get a prize on top of that is incredible :-). I went on to thank my wife for all the time I spent hacking on Gecko, especially during the first five years when it was strictly a hobby. Then I thanked the partners and family members of open source contributors everywhere for the same reason.

Tuesday, 9 November 2010

Eclipse Breakthrough

I've been using Eclipse for quite a while now as my code editor. A few years ago I tried using the "smart" CDT features on Gecko but they didn't work very well. Now, five years later (how time flies!) I am very pleased to report that they work much much better! I'm sure the software has improved (Eclipse 3.6.1, CDT 7), but my laptop now having four CPU cores and 8GB of memory has probably helped too :-).

I create an "empty" C++ project with the source directory pointing to an existing hg repository. I turn off the automatic build options, but enable all the indexing features. I turn off the "scalability" option for the C++ editor --- setting the number-of-lines threshold to 100,000 doesn't seem to cause any problems for me. In the project properties, I add resource filters to exclude everything under the .hg and object directories. In the "Paths And Symbols" page of the project properties, I add all the symbol definitions from the generated mozilla-config.h file of my debug build. This probably could be automated but I did it manually. Then I let the indexer run to completion. It doesn't take very long --- minutes, not hours.

With all that done, many features seem to mostly work, at least in layout and gfx code:

  • Ctrl-click on an identifier jumps to its definition
  • Ctrl-click on an identifier at its definition jumps to the declaration if there's a separate declaration
  • Hovering over an identifer shows its definition
  • Opening a "Type Hierarchy" shows the superclasses and subclasses of the selected class (or the class of the method containing the caret)
  • Opening a "Call Hierarchy" shows the callers/callees of the selected method
  • Opening "Quick Type Hierarchy" on a virtual method declaration shows the classes implementing that method
  • Opening "References / Project" shows all references to the selected declaration
  • Context-sensitive autocomplete often works.

All very useful! And all very smooth and fast, on my laptop anyway. Major kudos to the Eclipse team, this should really improve my productivity.

Of course, it's not perfect. For example, autocomplete after "foo->", where 'foo' is an nsCOMPtr or nsRefPtr, doesn't seem to work. However, the features work well enough that I'm getting into the habit of using the features and expecting them to work.

Tuesday, 2 November 2010

Implementing A High-Performance Emulator In Javascript Using Run-Time Code Generation

For a while I've been thinking about exploiting fast browser JITs and JS "eval()" to build really fast emulators and other language runtimes. Tonight I was feeling jumpy so I went ahead and hacked something up.

I started by defining a really simple imaginary CPU instruction set, writing a simple program for that instruction set, and implementing a trivial interpreter to execute it. It executes 100M instructions in about 7.5 seconds (Firefox opt trunk on my laptop), which is already pretty good! But we can do a lot better.

My idea is to write a trace compiler in Javascript for the emulated CPU. It's actually very easy. When we need to execute CPU instructions starting at a given PC address, we build up a string containing the Javascript code that needs to be executed for each instruction starting at the given address. I terminate the trace after any branch instruction. I then wrap the code string up into a function and call eval() on it to get a real Javascript function I can execute to get the effect of the trace. From there the browser JIT will compile my function into real native machine code, which I can call over and over again, every time control reaches that address. We're effectively translating from the emulated CPU all the way down to bare-metal x86, and in just a couple of hundred lines of JS! (Ok, plus the JS engine :-).) This very hacked-together compiler runs 100M instructions in about 1.2 seconds. That's a 6x speedup over the interpreter, but more importantly it means I'm getting over 80MIPS of performance, in the browser! Insane!!!

The compiler is super-simple and it could probably be improved in many ways to get even better performance. The key optimization I implemented was to deal with the "cycle counter" my imaginary CPU has --- essentially an emulated interrupt timer that counts down once per instruction executed. I generate two versions of each trace --- one with cycle counter checks at each instruction, and another with all the checks removed and a simple guard at the top of the trace to ensure that the cycle counter won't fire before we reach the end of the trace; if the guard fails, we take the slow check-on-every-instruction path. The demo page shows the Javascript code that the compiler emits to do this.

Of course, there isn't anything special about JS here, you could do the same thing with Java or .NET bytecodes, or in other languages with "eval". Still, since there are a lot of browser-based emulators out there, it would be cool to see people try this technique. It's hard to predict how well it would do in a real emulator, but I have hopes. Real CPU instruction sets involve more complex instruction decoding than my toy, and the trace compiler is able to hide that.

Update I thought of a couple more simple optimizations overnight, plus Jesse suggested one, so I implemented them all in about 15 minutes. Developing compilers with an edit/reload cycle is fun!

  • Jesse suggested using "new Function(code)" instead of eval(). Total time now 1.05 seconds.
  • I wrapped the body of each function in "while (true)". Then, wherever the trace sets the new PC to the PC at the start of the trace (i.e., it's a simple loop), we can replace that with "continue;" to actually loop inside our trace function without returning to the trace dispatch loop. Total time now 0.8 seconds.
  • I turned the "memory" and "regs" arrays into JS typed arrays (using feature detection to fall back for older browsers). Total time now 0.65 seconds.

So performance about doubled, now we're at 150MIPS. That's enough for one day!

(For perspective, the maximum clock of my laptop CPU is about 3GHz, so we're executing one emulated instruction every 20 native processor cycles.That's amazing!)

Oh, and just for kicks, totally unscientific benchmarks of other browsers. IE9 beta 1: interpreter 7.3 seconds, trace compiler 2.8 seconds. Chrome 7.0.517.41: interpreter 6.7 seconds, trace compiler 1.6 seconds. Neither of those browsers support typed arrays. I should note that typed arrays sped up the interpreter a lot in Firefox, now about 3.3 seconds.

Sunday, 31 October 2010

Stepping Stones

Last Sunday I spoke to our church congregation about a few things that had helped me grow spiritually. Many of those things were books. Here's the list:

  • The NIV Study Bible. This is the Bible I bought when I first became a Christian and I've mostly relied on it since then. The notes helped me understand a lot, especially in the beginning. The notes cover a lot of ground: translation issues, interpretations, and controversies. They're pretty good about presenting multiple sides of controversial issues in a fair way.
  • Basic Christianity by John Stott. This was one of the first Christian books I read. It's a particularly good introduction to what Christianity is all about, for non-Christians and Christians alike. It focuses strongly on Jesus: who he was (and is), why he came, and what that means for us. Highly recommended.
  • The Screwtape Letters by C.S. Lewis. A senior demon advises a minor demon on how to handle his “patient” --- a new Christian whom the demon has been assigned to corrupt. This is a very fun read, with lots of useful insights into the Christian life. Phillip Pullman likes it, so it must be good.
  • The Great Divorce by C.S. Lewis. An imaginary tour of heaven and hell --- not at all intended to be taken literally, but to stimulate one's thinking.
  • The Knowledge Of The Holy by A. W. Tozer. Much more dry than the above, but lays out key truths about God and strongly encourages the reader to take them seriously. Tozer emphasizes God's ineffability, and acknowledges the tension this creates for his own book!
  • Jesus by A. N. Wilson. A portrait of Jesus written from a skeptical/secular point of view. I read it quite soon after I became a Christian. It's interesting because it's clear from the book Wilson was fascinated by Jesus --- maybe even entranced --- even though he didn't really believe in him. I wasn't all that surprised when Wilson recently become a believer.

Wednesday, 20 October 2010

Bye Bye HWNDs

Spy++ showing that Firefox only has one HWND

As Firefox 4 races towards completion, we are discovering that quite a few extensions, pointing-device drivers and accessibility tools have been broken by the fact that Firefox no longer creates child HWNDs for its internal use.

These child HWNDs were been removed as a necessary step towards providing the best possible graphics acceleration performance in Firefox 4. Supporting child HWNDs was also architecturally painful; removing them has let us simplify or remove a lot of code, and we'll be able to remove a lot more later. It also fixed many bugs, and helped us to smoothly support new UI features such as Firefox UI element layered over Web page content. These HWNDs are not coming back.

It's unfortunate that various third party software components were messing with our internal HWNDs, since they were never supported API and we've been gradually removing them over a long period of time. But I suppose being molested is the price of popularity...

We're doing a few different things to deal with the fallout. We have some hacks in place to keep ATs working (fortunately ATs mostly use interfaces that do not depend on HWNDs), plus we've worked with AT vendors directly to fix issues. We have some more hacks in place to deal with pointing-device drivers, and we'll likely have to add even more hacks for them :-(. For extensions, we probably won't do anything, since the things they've been doing --- e.g. inserting a native child window under the HWND for our sidebar, or even Web content --- are mostly not things we want to support directly.

If you maintain a Firefox extension that is broken on Firefox 4 because it has native components relying on HWNDs that no longer exist, your best solution depends on what your extension actually does. But there are two main approaches you can take:

  1. Give up using native HWNDs and use Web platform features instead. This is the most future-proof, most portable and often the most performant route. Firefox 4 has many new features to handle use-cases the browser couldn't support before: audio synthesis, GPU-accelerated 2D and 3D graphics, touch input, etc.
  2. Wrap your HWND-using code in an NPAPI plugin. If you have large amounts of legacy HWND-dependent code that you can't rewrite, or there's platform functionality that you still can't get without an HWND, you may be able to wrap an HWND up as an NPAPI plugin, then you can insert a plugin instance into Web content or browser UI. NPAPI plugins are a bit of a pain to work with, but this might be a practical approach for some situations.

Good luck!

Hopefully now that we're down to a single HWND (most of the time), we'll see less breakage in future releases simply because there's little left to abuse or change...

Sunday, 17 October 2010

Distrusting Research

Here's an interesting article about bias in medical research. Almost everything they say about medical research applies to computer science too.

So you have to be very skeptical of empirical results in computer science, especially "we tried this and it worked" results. Fortunately --- unlike biology, I suspect --- at the heart of many computer science papers is just a clever idea or observation someone came up with. You can take that idea and try it for yourself. But don't bet the company on it just because some researcher said it worked great.

Of course, the situation is still pretty bad overall. The sick research culture that only rewards positive results doesn't just create selection bias in reported results; it also deprives us of interesting data about ideas that don't work. After all, people only try things they think will work, so failures on average should be more surprising --- and therefore more interesting --- than successes.

At PLDI this year not a single paper reported a negative result. However, during the short talks session one group from Microsoft presented a cute piece of work applying an automated reasoning tool to perform compilation; nice idea, but it didn't really work. I was so excited I ran up to the microphone just to say "thank you for presenting a negative result!". Then I added "We need more results like this", and everyone laughed...

Friday, 15 October 2010

Mitigating Dangling Pointer Bugs Using Frame Poisoning

The most important data structure in Gecko layout is the frame tree. Roughly speaking each frame object corresponds to a CSS box. The lifetimes of these frame objects are explicitly managed, and the structures get fairly complicated, so we sometimes have bugs where there is a dangling pointer to a frame object after it has been deleted. These bugs often used to be exploitable security bugs, since making a virtual call through a pointer to a deleted object can often be used to take control of the process using heap spraying. We fixed these bugs as fast as we could, but even after fixing all the ones we know about, experience suggests there are additional dangling frame pointer bugs we don't know about yet. So last year we implemented a mitigation technique that makes it impossible to exploit almost all bugs involving dangling pointers to frames. We call this technique frame poisoning. It incorporates some ideas that I first saw presented in a paper Memory Safety Without Runtime Checks or Garbage Collection. Most of the work was done by Zack Weinberg, who is now a PhD student working with Collin Jackson at CMU West.

Exploiting dangling pointers is essentially about exploiting type errors. An attacker writes an attacker-controlled data value to some memory location L in a deallocated object, typically by causing a new object to be allocated there. This data value is invalid for the type T the program expects when it accesses L through a pointer to the deallocated object. For example, the program may expect L to be a pointer to a C++ vtable, but the attacker has overwritten L with an integer --- which when interpreted as a vtable pointer, lets the attacker trigger arbitrary behavior.

Our approach is to prevent the first phase of the attack by making it impossible to overwrite fields of deallocated objects with values of the wrong type. We do this by ensuring that whenever the memory used by a deallocated frame object is reallocated to a new object, the new object must always be exactly the same type as the old object and at exactly the same address. Thus whenever code writes a value to a field of the new object, the value must be valid for the type T the program expects when it access that location through a pointer to the new object *or* the old object. Thus, dangling-frame-pointer attacks cannot get started.

This is implemented by keeping a "free list" of deallocated frames, one freelist per frame type. When a frame is deallocated, its memory is added to the freelist for its type. When a new frame is allocated, we check the freelist for its type and reuse memory from that freelist if the freelist is not empty, otherwise we allocate new memory for the frame.

One complication is that we actually keep one set of freelists per document (i.e., Web page). When a document goes away, all frames are destroyed and all frame memory is returned to the general application heap. This is safe because almost all persistent pointers to frames are from data structures associated with that document, data structures which are torn down when the document goes away. Thus it is very unlikely we will see bugs involving dangling pointers to frames whose document has gone away (experience bears this out).

An additional line of defense is that when frames are deallocated we fill the memory with a "poison value" --- a nonsense value which, when interpreted as a pointer, always points into a large region of invalid memory. This ensures that if the program loads a value from the memory of a deallocated object and dereferences that value as a pointer, it will almost certainly crash in a way that cannot be exploited. In practice this means when someone finds a bug involving a dangling frame pointer, the browser usually crashes immediately before doing anything an attacker would find interesting. "Frame poisoning crashes" are easy to identify because they're accesses through a pointer that is (or is close to) the "frame poison value". For more details see TestPoisonArea.

We didn't use NULL (zero) for the poison value because a lot of code tests to see if a pointer is non-null, and if so dereferences it. If that code operates on a deallocated object, we want it to crash immediately, not carry on trying to use the deallocated object in some other way.

We shipped frame poisoning in Firefox 3.6. In the end there was no significant performance impact, although we had to be careful because some of our earlier attempts did hurt performance! In particular, we optimize by not writing the poison value over deallocated frame objects when the entire document is going away.

Like all mitigations, frame poisoning is not ideal. We still fix dangling frame pointer bugs on trunk as quickly as we can. However, we know of no way to bypass frame poisoning to exploit dangling frame pointer bugs, so we may choose to not fix certain bugs on a maintenance branch where we believe frame poisoning blocks exploitation and a proper fix would be very destabilizing.

Sunday, 10 October 2010

South Island Trip

I'm well and truly back again! Our holiday around the northern end of the South Island was wonderful. One of the best things about living in New Zealand is that it's easy to take holidays around New Zealand.

We flew to Wellington, took the ferry to Picton for a night, then took the TranzCoastal train to Christchurch via Kaikoura --- amazing views of the Kaikoura Ranges and the coast. We crossed over large cracks in the ground near Kaiapoi showing exactly where the recent earthquake had hit. We had a couple of nights in Christchurch; during our full day we walked from Cashmere up into the Port Hills, then east along the Crater Rim track for a few hours before descending into Lyttleton on the Bridle Path --- fantastic 5-6 hour walk with amazing views west to the Southern Alps and south into Lyttleton Harbour and Banks Peninsula.

From Christchurch we took the TranzAlpine train up to Arthur's Pass, where we spent a couple of days. The first day was wet so we walked up the Devil's Punchbowl falls, which were a raging, spraying torrent. Awesome! The next day our big walk took us from the village along the Bridal Veil track, then up into Bealey Valley below Mount Rolleston, then back to the road and along the road to the Dobson Nature Walk before returning back down the road to the village. We saw lots of keas --- wonderful alpine parrots --- and the alpine/bush environment is stunning with snow reaching nearly down to the village.

We took the train the rest of the way to Greymouth, picked up a rental car and drove to Murchison via the Pancake Rocks at Paekakariki and the Buller Gorge (both spectacular). Our day trip from Murchison was to Mount Robert at Lake Rotoiti in Nelson Lakes National Park; another 5-6 hours up, across the top (with lots of snow), down, and back to the carpark. The weather was perfect, the view staggering; we could see at least 100km in most directions. We could easily see all the way to Motueka on the coast. Bush, snow, sun, lake, staggering views --- amazing.

From Murchison we drove via Motueka to Takaka for the last three nights of our trip. The highlight of this section was the limestone country and exploring the caves at the Aorere goldfields and Rawhiti Cave. (Note: documentation says that you can drive a car up a "farm track" to a parking area for the Aorere goldfields walk, but the "road" is very rough. I suggest parking at the first gate and walking the rest of the way.) The initial descent into Stafford's Cave was slightly tricky, given I have no real climbing/caving experience and had children to assist, but then (having a torch) it was easy to make our way through a series of chambers to an area with glow-worms. Wow! We also drove up to the base of Farewell Spit and did a short 1.5 hour walk there; it looks worth spending more time there.

On our last day we drove from Takaka to Nelson airport to fly back to Auckland. Along the way we visited the Stoneridge Cafe and had great fun in their hedge maze.

It was an amazing, wonderful trip. We had half a day of rain in the eleven days we were away, which is completely unreasonable for this time of year. Consequently we did more walking than I had expected, but we made up for it with more eating! Everyone raves about the South Island's scenery, but the superlatives are fully deserved. As a bonus, the areas we covered are very compact; apart from the TranzCoastal train, each step of our trip was just two to three hours of travel.

Accommodations and food were great. All the motels were more than adequate, but Golden Bay Motel in Takaka was exceptional. Even where there were only a few options to buy food, the food was excellent (albeit sometimes expensive).

Cellphone coverage was mysteriously ubiquitous! In particular I made calls from the depths of Bealey Valley and the peak of Mount Robert.

Contrary to the predictions of some, I did not miss my computer one bit, although I did a lot of thinking --- and praying! With no distractions I was able to sleep eight to ten hours a night, which I think was excellent for my health. All in all, it was a great time of physical, emotional, mental, and spiritual refreshment.

Now I've dropped straight back into the front lines ... ready for battle again!

Saturday, 9 October 2010

Raising Awareness

I want to ride a tricycle from Vladivostok to Glasgow to raise awareness of the critical shortage of human attention.

Seriously, "raising awareness" campaigns make no sense to me in a world awash with campaigns on all sorts of issues. Instead of spending money on these global jaunts, let's spend it on actually trying to fix problems.

Sunday, 19 September 2010


I'm in the middle of my current US trip. Last week I was in Mountain View for a Mozilla work week (lots of excitement). Last night I arrived in Pittsburgh, where I am about to go to the wedding of some friends and then hang around until Tuesday, when I'll have a talk about browser development and my research wish list --- it'll be similar to my LFX talk. I'll be online on and off while in Pittsburgh, and back in the NZ office on Thursday (Wednesday for North Americans).

Being in Pittsburgh again is great, it brings back lots of good memories.

On the following Monday (September 27), I'm going on a holiday with my family. I will be out of the office until October 8. During that time I plan to be entirely offline. So I won't be on IRC, replying to email, doing reviews, or even checking AWFY. I'm looking forward to it :-).

Thursday, 16 September 2010

The Ten Commandments

I watched DeMille's "The Ten Commandments" the other day. Unfortunately I have to put it in the category of classic films which have not stood the test of time. I can overlook the stony acting, but it's even harder to overlook the special effects, which are unsurprisingly laughable by today's standards. The most disappointing aspect is that Moses is a far less interesting character in the movie than he is in the Bible. The movie adds a lot of extra-Biblical material, some from ancient sources but a lot that they just made up (like a romance with Pharoah's future wife), but that isn't very interesting. Yet after the encounter with the burning bush, Moses is portrayed as essentially a one-dimensional inerrant servant of God. We see nothing of his lack of self-confidence (even faith!) before God that led to God appointing Aaron as his mouthpiece. We don't see Moses pleading with God for mercy for the Israelites after the golden calf episode, or the conflicts he had with Aaron then and at other times. We don't see Moses' sin at Meribah, or the grief he must have had over God preventing him from entering the promised land. It's telling that the Bible gives us a more nuanced portrait of major characters than some modern storytellers can manage.

I think that DeMille's stated theme for the movie --- that people everywhere should be free from slavery and the despotism of kings, being subject only to (God's) law --- is misplaced. Worthy as it is, as far as I can tell it is not a significant theme anywhere in the Torah. God delivered the Israelites from oppression, explicitly not because of they deserved it, but rather because of his promises to Abraham and his desire to set apart a chosen people for his own glory. DeMille's theme would not have sat well if the movie had shown the non-democratic aspects of Moses' rule, or the Israelites continuing to take slaves; I think he was imposing his own priorities on the story. (The story of Samuel would be much better foundation for that theme --- when the Israelites demand a "king such as other nations have", with severe consequences.)

One part of the movie I thought was really good was the depiction of the night of the first Passover. It captured just a little of the horror and dread that must have been experienced by everyone, including the Israelites.

Sunday, 12 September 2010

"Full Hardware Acceleration"

Microsoft marketing is making noises about IE9 having a monopoly on "full hardware acceleration". They're wrong; Firefox 4 has all the three levels of acceleration they describe. It's surprising they got this wrong, since Paul Rouget published a great overview on a few days ago (and our plans, source code, and nightly builds have been public since we started working on this stuff many months ago).

One of the messages of their post (and other IE9 marketing materials) is that a browser that only works with D3D and D2D will be superior to one that works on more platforms (e.g. having the option to use GL or D3D for compositing), because they need less of an abstraction layer. They're probably thinking of Chrome, which is basing everything on GL and using ANGLE to map GL to D3D for Windows. We also have an abstraction layer --- which we call "Layers" --- with D3D9, GL and "non-accelerated" implementations, but it's a lot higher-level than GL/ANGLE. (And of course we already have cairo for the content-rendering phase.) It's certainly true that only having to target Vista and Windows 7 would mean less development effort, but an extra abstraction layer need not hurt performance --- if you do it right. I personally like our approach so far; we have to write similar code for GL and D3D often, but having a D3D-specific layers backend makes it easier to integrate D3D-specific features --- like D2D!

I'm pretty confident that our architecture will not cause us any performance disadvantages vs IE9. On the other hand, our architecture does let us deliver D3D acceleration for Windows XP users --- which is still a very large market. I'm surprised Microsoft has been prepared to just hand XP users over to Firefox and Chrome (all those not captive to IE6, at least). Our architecture also lets us deliver GL acceleration for Mac, X, and mobile devices, which is very important.

When we started pushing on Layers at the beginning of the year, I had no idea we'd end up going toe to toe with Microsoft like this. It's exciting!

BTW "full hardware acceleration" is a bogus phrase. All browser pick and choose how to use the GPU, and more use of the GPU isn't necessarily better. There are certainly things no browser is ever going to "hardware accelerate" ... e.g. CSS margin collapsing :-).

In Microsoft's favour, I want to point out that although GPU acceleration for Web graphics isn't going to be a coup for IE9, it is going to be a coup for Windows. As far as I know there simply isn't anything comparable to D2D for GL at this time. (If there was, we'd use it!) cairo-gl is the closest thing I know of that we'd want to use, and but it doesn't seem ready yet. Apple has Quartz 2D Extreme, but they don't enable it for their own apps so one has to assume it's not a clear win. So, kudos to Microsoft for creating D2D, backporting it to Vista, and making it awesome. The free software world really needs to get behind cairo-gl (or something comparable) in a big way. I'd love to have some Mozilla people on it, but we're pretty busy... I'm sure we'd consider funding someone else to work on that stuff, though!

Thursday, 2 September 2010

New Google Maps Imagery Of Auckland

At some point relatively recently, Google added much higher-resolution images of Auckland to Google Maps. These images appear to have been taken by aerial photography and they're quite amazing.

Tuesday, 31 August 2010

A Night Out

I had a very nice dinner at "Wildfire Churrascaria" courtesy of Microsoft. Lots of yummy, fatty, salty meat.

I went to catch my bus and missed it by one minute. At 10:41pm, the next bus was at 11:10pm.

Being impatient, instead of waiting for the next bus I ran home ... well, half-ran, half-walked ... 5.5km In 42 minutes. Not fast, but then I had a backpack full of Microsoft swag plus my laptop, and a belly full of meat. Faster than the bus anyway.


I'm at Microsoft TechEd in Auckland today and tomorrow --- they reached out to invite a few open source people, so I thought I'd go and check out their messages. It's fun too. One of the highlights of today was a talk about geolocation APIs ... the presenter showed the creation of a toy HTML geolocation app, but couldn't get it working in Chrome and had to switch to Firefox :-). And apparently IE9 isn't going to support the geo APIs at all as far as anyone knows. Funny sort of demo for a Microsoft conference!

In fact so far I haven't seen anything about IE9 at all. There's a lot more Silverlight/WIndows Phone 7. I wonder if that's accidental (this is just the first day after all) ... or not.

Sunday, 29 August 2010

More Dell Fail (Or Maybe NVidia)

I bought a Dell ST2410 monitor for my new home computer (a Dell XPS 8100 shipped with an NVidia GTX260 graphics card, which has two DVI ports). Dell shipped a VGA cable and a DVI-VGA converter, so I thought I'd go out and buy a digital connector. Dell shipped me a DVI-HDMI converter dongle (made by NVidia apparently), the Dell monitor has HDMI and my TV has HDMI so I thought I'd get an HDMI cable and this would be easy. Wrong. The monitor completely fails to detect any signal from the computer. I tried everything I can think of. Even my old Macbook Pro can drive the monitor through its DVI port, the DVI-HDMI dongle and the HDMI cable. So apart from the cable, which obviously works, we have here three parts all shipped by Dell that don't work together. Sigh. I guess I'll try a DVI cable next...

Sunshine Rises Again

As previously reported, the wonderful "Sunshine" Chinese restaurant in Market Place near the Viaduct Harbour suffered a tragic demise. And also as previously reported, it has been reincarnated. Today our family visited the new incarnation, "Crystal Harbour". I am very pleased to report that the new version is very similar indeed to the old "Sunshine". The decor is the same, the layout is the same, the lack of queues is the same, and most importantly the food is very much as it was. Where Sunshine excelled --- the unique barbeque pork buns, the seaweed plate, the ice cream dumplings --- so does Crystal Harbour. Crystal Harbour's promotional material claims there's a new chef, but clearly (and fortunately) a lot has been preserved. One change is that there were a lot more people there today than I ever saw at Sunshine. It could be the novelty factor, but I hope Crystal Harbour does well. I certainly plan to contribute as often as I can!

Thursday, 26 August 2010

-moz-element Landed

Markus Stange picked up the work I did in 2008 on the "-moz-element()" CSS extension (which was later extended by Ryo Kawaguchi), made some major improvements and got it reviewed and landed. Check out his blog post. -moz-element lets you render the contents of an element as the background image for any other element. This is a very powerful tool that can be used in very interesting ways; check out Markus' amazing demos. This feature is on trunk now and will be in Firefox 4. We will also propose this to the CSS WG.

Note for browser UI and extension authors: eventually -moz-element will be the preferred way to render "live" copies of Web page contents (insteading of using MozAfterPaint/drawWindow). Right now, -moz-element can be used to render the contents of a <browser> element elsewhere, although it's less well-tested and is less tweakable for performance. Post-FF4, we can tie -moz-element into the layers framework so that in many cases --- such as tab thumbnails --- rendering -moz-element just recomposites a layer subtree, fully GPU-accelerated.

Tuesday, 24 August 2010


The first Vernor Vinge books I read were A Fire Upon The Deep and A Deepness In The Sky ... not surprising, since they're the most famous, and also the best. I was a bit disappointed by Rainbows End. Just recently I read two of his earlier novels (written in the 80s), The Peace War and Marooned In Realtime --- the latter being a sequel to the former --- and I think they're excellent, perhaps not as good as Fire and Deepness, but Marooned in particular I found more intriguing and even quite moving.

Warning: if you haven't read these books, go out now and read them before you come back to the rest of this post, because spoilers are ahead...

Marooned and Rainbows End present two rather different visions of human development, and Rainbows End is far closer to my own thinking even though I like the book less. I'm ignoring the bobbles here --- they're a wonderful plot device, but I think the real themes of Marooned are the technological Singularity and a yearning for anarcho-capitalism. At heart I think Marooned is fundamentally an optimistic view of human progress to the Singularity. Rainbows End, on the other hand, seems to me to be a much darker view, a view of humanity lurching from one potential planet-killing catastrophe to the next at decreasing intervals, with no Singularity-salvation in sight. Now, Vinge may make a liar of me yet, since he's said he'd like to do a sequel to Rainbows End, but based on what he's written so far I guess in the twenty years between the books he's become more pessimistic. Although curiously, he may have become a lot more optimistic about governments --- in Marooned he hates governments, in Rainbows End we see a benign totalitarian state.

Personally I think Rainbows End is too optimistic :-). I wrote about this a while ago and I stand by it: the technology that could eventually lead to some kind of Singularity (very eventually; this stuff is way, way harder than most techo-futurists imagine), leads much sooner to either the total elimination of cognitive freedom or the destruction of all intelligent life. It's just not realistic to imagine we can walk the ever-thinning razor's edge for long. Man is fallen, but he still has a long way to fall. God is going to have to save us from ourselves, again.

Time to stop. Excessive futurist navel-gazing is definitely a sin :-).

Saturday, 21 August 2010

CSS Units Changes Landed

The CSS units changes that I blogged about in January have landed and will be in the next Firefox milestone. With these changes, 1in = 96px always. Likewise 3pt = 4px, 25.4mm = 96px, etc.
This matches the behaviour of Internet Explorer, Safari and Chrome.

By default, when printing, 1in is rendered as one physical inch. For other output media, all these units are scaled in a medium-dependent and platform-dependent way by default. One goal of this scaling is to give results consistent with user expectations and other applications on the system. For example, standard form controls such as checkboxes should look the same in Web pages as in other applications, by default. Another goal is to choose default scaling so that a document designed to print well on normal-sized paper will be readable on the output device, e.g., a phone. So, the advice for authors using CSS physical units is to set lengths so the document looks good when printed without scaling; the browser will then scale those lengths to display the document suitably on different kinds of screens.

There are some rare cases where it makes sense to include true physical measurements in a Web document --- for example, "life size" diagrams, or elements in a touch interface. For these cases we have introduced a new experimental unit, "mozmm". For media such as screens that can be touched, 1mozmm is rendered as one physical millimetre (or as close as we can get based on what we know about the medium). For other media, such as contact lens displays, brain-implanted electrodes, or lasers projecting into the sky, we reserve the right to treat 'mozmm' similarly to 'mm'. Authors should only use mozmm for elements which really need the same physical size on, for example, a 4" phone screen and a 24" monitor. This is hardly ever going to be what you want.

Internally, our DPI code has been overhauled. Everything is now controlled by two parameters: for each window, the number of device pixels per inch (returned by nsIWidget::GetDPI), and also for each window, the default scale (returned by nsIWidget::GetDefaultScale). The 'layout.css.dpi' about:config pref overrides the result of nsIWidget::GetDPI, if present. nsIWidget::GetDPI only affects the interpretation of mozmm (unlike before, where on some platforms, some DPI values would trigger automatic scaling). We set CSS 1px to one device pixel times GetDefaultScale times the current zoom factor. Currently GetDefaultScale always returns 1.0 on all platforms, although on Mac we should set it to the system "default UI scale" (and change some other code to compensate), and on Windows we should set it based on the "system font DPI", which is essentially a user preference that controls scaling of all applications on the system. It's important that the default scale be based on a system-wide setting; that will keep Firefox consistent with the rest of the system, and ensure that the user doesn't get a surprise.

Tuesday, 17 August 2010

The mozRequestAnimationFrame Frame Rate Limit

A few people have been playing with mozRequestAnimationFrame and noticed that they can't get more than 50 frames per second. This is intentional, and it's a good feature.

On modern systems an application usually cannot get more than 50-60 frames per second onto the screen. There are multiple reasons for this. Some of them are hardware limitations: CRTs have a fixed refresh rate, and LCDs are also limited in the rate at which they can update the screen due to bandwidth limitations in the DVI connector and other reasons. Another big reason is that modern operating systems tend to use "compositing window managers" which redraw the entire desktop at a fixed rate. So even if an application updates its window 100 times a second, the user won't be able to see more than about half of those updates. (Some applications on some platforms, typically games, can go full-screen, bypass the window manager and get updates onto the screen as fast as the hardware allows, but obviously desktop browsers aren't usually going to do that.)

So, firing a MozBeforePaint event more than about 50 times a second is going to achieve nothing other than wasting CPU (i.e., power). So we don't. Apart from saving power, reducing animation CPU usage helps overall performance because we can use the free time to perform garbage collection or other house-cleaning tasks, reducing the incidence or length of frame skips.

We need to do some followup work to make sure that on each platform we use the optimal rate; modern platforms have APIs to tell us the window manager's composition rate. But 50Hz is almost always pretty close.

This all means that measuring FPS is a bad way to measure performance, once you're up to 50 or more. At that point you need to increase the difficulty of your workload.

Monday, 16 August 2010

Auckland Food

For cheap tasty food, BBQ King on Wyndham Street West is hard to beat. Today I went there with family and based on past experience, we ordered only two dishes for four people, "BBQ pork and crispy pork stirred noodle" for $13.50 and "seafood fried rice" for $12. After eating the free soup and then dividing the first dish among four of us, we were pretty much satisfied, so boxed the second dish and brought it home. Crazy!

Tragically, my favourite Chinese restaurant in the city --- Sunshine --- closed several months ago. I can understand when a bad restaurant goes under, but not a good one; the imperfections of a market economy! But I have heard rumours that a new Chinese restaurant has taken its place. This needs investigation.

Daikoku Teppanyaki on Quay St is now open for lunch seven days a week. The $13.50 lunch special is still great value.

Around Newmarket: Happy Valley, the Chinese cafe, has closed down. That's sad, since they'd been serving pretty good food since the early 90s.

The Organic Pizza Co.'s $10 lunch specials are pretty good. Their pizzas are about as good as Archie's, but you get a free drink and the place is far less crowded.

Selera, Night Spice, Crazy Noodle and Dee Jai are frequent targets of visits from the Mozilla office, as is the food court under the Rialto carpark. The actual Rialto food court next to the cinema seems to be declining --- two outlets have closed recently --- but they still have the only Subway in the area. We'd go to Hansan more but we're too lazy to walk there except for special occasions.

Pearl Garden still the best yum cha in Newmarket, followed by Sun World and Sunnytown. There's a new place whose name escapes me over near Davis Crescent; not bad, but not great. I need to try it again.

Firefox Sync

I just tried using Firefox Sync to synchronize data between my main Firefox profile and my newly-installed home computer's Firefox profile. It was easy to set up and worked perfectly --- and it was fast too! I have to confess my expectations were not high for a feature that just got turned on for beta 4 :-). Well done everyone! This is definitely going to make my life a little easier.

Sunday, 15 August 2010


In Firefox 4 we've added support for two major standards for declarative animation --- SVG Animation (aka SMIL) and CSS Transitions. However, I also feel strongly that the Web needs better support for JS-based animations. No matter how rich we make declarative animations, sometimes you'll still need to write JS code to compute ("sample") the state of each animation frame. Furthermore there's a lot of JS animation code already on the Web, and it would be nice to improve its performance and smoothness without requiring authors to rewrite it into a declarative form.

Obviously you can implement animations in JS today using setTimeout/setInterval to trigger animation samples and calling to track animation progress. There are two big problems with that approach. The biggest problem is that there is no "right" timeout value to use. Ideally, the animation would be sampled exactly as often as the browser is able to repaint the screen, up to some maximum limit (e.g., the screen refresh rate). But the author has no idea what that frame rate is going to be, and of course it can even vary from moment to moment. Under some conditions (e.g. the animation is not visible), the animation should stop sampling altogether. A secondary problem is that when there are multiple animations running --- some in JS, and some declarative animations --- it's hard to keep them synchronized. For example you'd like a script to be able to start a CSS transition and a JS animation with the same duration and have agreement on the exact moment in time when the animations are deemed to have started. At each paint you'd also like to have them sampled using the same "current time".

These problems have come up from time to time on mailing lists, for example on public-webapps. A while ago I worked out an API proposal and Boris Zbarsky just implemented it; it's in Firefox 4 beta 4. Here's the API, it's really simple:

  • window.mozRequestAnimationFrame(): Signals that an animation is in progress, requests that the browser schedule a repaint of the window for the next animation frame, and requests that a MozBeforePaint event be fired before that repaint.
  • The browser fires a MozBeforePaint event at the window before we repaint it. The timeStamp attribute of the event is the time, in milliseconds since the epoch, deemed to be the "current time" for all animations for this repaint.
  • There is also a window.mozAnimationStartTime attribute, also in milliseconds since the epoch. When a script starts an animation, this attribute indicates when that animation should be deemed to have started. This is different from because we ensure that between any two repaints of the window, the value of window.mozAnimationStartTime is constant, so all animations started during the same frame get the same start time. CSS transitions and SMIL animations triggered during that interval also use that start time. (In beta 4 there's a bug that means we don't quite achieve that, but we'll fix it.)

That's it! Here's an example; the relevant sample code:

var start = window.mozAnimationStartTime;
function step(event) {
var progress = event.timeStamp - start; = Math.min(progress/10, 200) + "px";
if (progress < 2000) {
} else {
window.removeEventListener("MozBeforePaint", step, false);
window.addEventListener("MozBeforePaint", step, false);

It's not very different from the usual setTimeout/ implementation. We use window.mozAnimationStartTime and event.timeStamp instead of calling We call window.mozRequestAnimationFrame() instead of setTimeout(). Converting existing code should usually be easy. You could even abstract over the differences with a wrapper that calls setTimeout/ if mozAnimationStartTime/mozRequestAnimationFrame are not available. Of course, we want this to become a standard so eventually such wrappers will not be necessary!

Using this API has a few advantages, even in this simple case. The author doesn't have to guess a timeout value. If the browser is overloaded the animation will degrade gracefully instead of uselessly running the step script more times than necessary. If the page is in a hidden tab, we'll be able to throttle the frame rate down to a very low value (e.g. one frame per second), saving CPU load. (This feature has not landed yet though.)

One important feature of this API is that mozRequestAnimationFrame is "one-shot". You have to call it again from your event handler if your animation is still running. An alternative would be to have a "beginAnimation"/"endAnimation" API, but that seems more complex and slightly more likely to leave animations running forever (wasting CPU time) in error situations.

This API is compatible with browser implementations that offload some declarative animations to a dedicated "compositing thread" so they can be animated even while the main thread is blocked. (Safari does this, and we're building something like it too.) If the main thread is blocked on a single event for a long time (e.g. if a MozBeforePaint handler takes a very long time to run) it's obviously impossible for JS animations to stay in sync with animations offloaded to a compositing thread. But if the main thread stays responsive, so MozBeforePaint events can be dispatched and serviced between each compositing step performed by the compositing thread, I think we can keep JS animations in sync with the offloaded animations. We need to carefully choose the animation timestamps returned by mozAnimationStartTime and event.timeStamp and dispatch MozBeforePaint events "early enough".

mozRequestAnimationFrame is an experimental API. We do not guarantee to support it forever, and I wouldn't evangelize sites to depend on it. We've implemented it so that people can experiment with it and we can collect feedback. At the same time we'll propose it as a standard (minus the moz prefix, obviously), and author feedback on our implementation will help us make a better standard.

Saturday, 14 August 2010

Google vs Oracle

I don't know much about the Google/Oracle dispute so I'll limit my remarks, but here they are:

I don't understand why Oracle is doing this. They may wish Google was using Java ME, but I would have thought having more developers using Java was good for Java overall. Probably there are important background discussions we are not privy to.

Dalvik is open source, but it's very much a Google project that Google happens to release under an open source license, rather than a community project. So I think of this as two big companies scrapping rather than Oracle launching an attack on the open source community.

However, this extends a disturbing trend of large mainstream companies using software patents to attack competitors, especially prominent in the mobile space. Observers of software patents, including myself --- and even Bill Gates in his infamous 1991 memo --- have always seen that volumes of easily obtained software patents on straightforward ideas could be a powerful weapon to crush competition; software development is so inventive that most programmers daily write code that someone patented somewhere. Fortunately, for a long time, other than "patent trolls", serious industry players declined to use that power. But now that grace has departed and I fear patent armageddon is upon us. In the end the open source community is likely to be particularly hard-hit, since it's easy to detect infringement, and open source communities have limited funds for defense. People have argued that open source communities are less of a target because they have less money to extract, but the most dangerous suits are about shutting down competition, not about extracting licensing fees --- like this Google/Oracle suit, apparently.

Overall I'm extremely gloomy about the situation. A world where each programmer has to be shepherded by a dozen lawyers through patent minefields is not one I will enjoy working in, and it will be disastrous for the progress of software. I call on employees of Oracle, Apple and other litigating companies to protest to their management in the strongest possible terms, including resignation. Google and Mozilla are hiring :-).

It's little consolation that some enlightened countries --- like New Zealand, apparently --- will hopefully remain free of software patents. A software company --- or an open source project --- that can't do business or get distribution in the USA or many other countries (including most of Europe, given the 'method patent' regime) is somewhat crippled.

Thursday, 12 August 2010

Dell Fail

Separate from the laptop discussion, I just bought a new home machine. I just wanted a generic PC, high-ish end for longevity and in case I (or someone else) wants to hack on it. This machine will definitely run Linux, but I'm going to keep the Windows 7 install in a partition in case we ever need it. So I'm going through Dell's Windows 7 first-run experience, and it's not great.

The initial Microsoft setup screens are pretty good, although it all seems to take longer than it should. Then you get to a Dell screen asking you to opt into some Dell stuff, which for some unfathomable reason is rendered in the Windows 95/2000 "Classic" theme, gray box scrollbars and all. It's ugly, jarring and totally mystifying.

Soon you're offered the chance to burn system recovery DVDs. I don't understand why they ask users to obtain blank DVDs and burn them instead of just shipping those DVDs; shipping them with every system would add a few dollars to the system cost, but probably save more in support calls and give a much better user experience.

The application that burns the recovery DVDs has one crazy screen that shows you some information and asks you to click "Next". But there is no "Next" button visible. But there's a vertical scrollbar! Scrolling down, you can get to a "Next" button. Of course, the window is not resizable, and it contains lots of blank vertical space so there is no possible reason why the "Next" button should not be visible.

Microsoft's initial Windows network setup asks you whether you're on a "Home", "Work" or "Public" network, which I bet is often hard for people to answer. I wonder how Windows uses that information. But right after choosing that option, the (preinstalled) McAfee antivirus software pops up an ugly little box in which you have to choose those same options again.

Of course I still have to analyze the system for the paid-to-be-there crapware (including McAfee) and uninstall most of it.

I'm genuinely curious about what motivates system vendors like Dell to sully what could have been a better experience. It's not apathy, since they obviously paid people to develop many of these "extras". Whatever it is, it's no surprise platform vendors want to sell directly to the customer instead of working through partners like Dell.

Wednesday, 11 August 2010

Choosing Sides

My Macbook Pro is 3.5 years old and still works pretty well, apart from the disk being full, frequently spontaneous wake-ups in my backpack which heat everything up alarmingly, and flaky wireless connection. Plus the turn of Moore's Law means I can now get a quad-core laptop and a lot more RAM and disk. So it's finally time to upgrade. I'm opting for non-Apple hardware; Apple have gone beyond the pale pursuing patent warfare and platform lockdown, and I can no longer live with buying their products. A Lenovo W510 is probably in my future.

Now I'm faced with a somewhat difficult decision: Linux vs Windows. There are good reasons on both sides. The best thing about developing in Windows is that it's good to have developers on the platform that most of our users use. VMWare record and replay is also very attractive. The Mozilla build and tools situation on Windows used to be terrible --- very slow builds, horrible profiling --- but it's gotten a lot better thanks to pymake and xperf. But Microsoft, while not as dangerous as Apple at the moment, still aspires to be, and I won't embrace them gladly.

Linux, of course, has the virtue of freedom, and a chance to regain Miguel's love. On Linux you get valgrind. But not many of our users use Linux, and VMWare's record and replay doesn't really work there. I'd have to use X11, which I loathe with passion.

Tough call. Another thing to consider is that whichever way I go, I'll end up using the other in a VM quite often. Dual-booting is also an option.

Wednesday, 28 July 2010

Unexpected Downtime

I seem to have picked up some sort of virus. I'm mostly offline while I wait for this to clear up. Please forgive any delays...

Thursday, 22 July 2010

Coding Style As A Failure Of Language Design

Variance in coding style is a huge problem. Reading code where the style varies all over the place is painful. Moving code from one place to another and having to restyle it is awful. Constantly adjusting the style in which you're writing code to conform to the local style of the project, module, file, function or line you're modifying is miring.

Therefore projects adopt style rules to encourage and enforce a uniform style for the project's code. However, these rules still have to be learned, and adherence to them checked and corrected, usually by humans. This takes a lot of time and effort, and imperfect enforcement means code style consistency gradually decays over time. And even if it were not so, code moving between projects looks out of place because style rules are rarely identical between projects --- unless you reformat it all, in which case you damage the relationship with the original code.

I see this as a failure of language design. Languages already make rules about syntax that are somewhat arbitrary. Projects imposing additional syntax restrictions indicate that the language did not constrain the syntax enough; if the language syntax was sufficiently constrained, projects would not feel the need to do it. Syntax would be uniform within and across projects, and developers would not need to learn multiple variants of the same language. More syntactic restrictions would be checked and enforced by the compiler, reducing the need for human (or even tool-assisted) review. IDE assistance could be more precise.

Two major counter-arguments arise. People will argue that coding style is a personal preference and therefore diversity should be allowed. This is true if you only participate in particularly small projects, but if you work in a large project then --- unless you are exceptionally fortunate --- you will have to deal with a coding style that is not your preference, no matter what. (Maciej Stachowiak once said that willingness to subjugate one's personal preferences to a project's preferences is a useful barometer of character, and I agree!)

A more interesting counter-argument is that many coding style rules aren't sufficiently formalized so as to be machine-checkable, and might even be very difficult to formalize at all. This is true; for example, line-breaking rules or variable naming rules might be very difficult to formalize. So I relax my thesis to claim that at least those rules which can be formalized should be baked into the language.

(Figuring out exactly which rules can be formalized, and exploring alternative syntax designs that maximize automatic style checkability while still being nice syntax, sound like fun research! Programming language syntax is one of those areas that I think has been greatly under-researched, especially from the HCI point of view.)

Tuesday, 20 July 2010


Working on plugin bugs sucks, but sometimes it's fun to watch a video clip over and over again.


I'd better say something about the Mozilla summit at Whistler before it recedes into the past...

It was fabulous, of course. The setting, the food, the people, the talks, the work, the demos, the mission, all really good.

Whistler was lovely. It had been cold up to the week we arrived so while it was 30C in the village at times later in the week, 20 minutes in a chairlift brought you up into the snow. And on top of Whistler Mountain the snow banks were six metres deep in places.

I wisely arrived a couple of days early and on the Monday I spent almost the entire day hiking alone up to Singing Pass. Unfortunately I didn't reach Singing Pass --- around the snow line the track was completely blocked by fallen trees (see below). I climbed over a couple of dozen of them but with no end in sight, decided that was a losing proposition and turned back. Nevertheless it was a wonderful time and some solitude was excellent fortification for the subsequent social overload.

I'm not really a party person and working large groups of people is a learned skill for me. It's helpful when I have goals to accomplish and I know a lot of the people. In some ways it wasn't all that different from networking at an academic conference, except we're all on the same side.

The main downside of the summit was that I was completely exhausted during most of it because I was simply too excited to sleep. Talking to people, going to sessions, playing games, and hacking code are irresistible.

Next time we should plan some "work week" days immediately after the summit. This would give us more time to talk in depth --- there were so many people at the summit I wanted to talk to, I couldn't give lots of time to more than a few. It would give us more time to code. We should have done it this time but I wasn't on the ball.

As usual I met many contributors for the first time. That's one of the best things about the summits. A few I really wanted to meet didn't make it --- you know who you are!

I managed to get together with some Mozilla Christians for some prayer time. That was very encouraging.

I saw bears. Woohoo!

trees fallen across the path up to Singing Pass

This is the track near the head of the valley leading up to Singing Pass. I'm looking back along the track at the trees I've already clambered over! Definitely more trees than track at this point. People told me it was probably the leftovers of an avalanche.

view over Whistler valley

View over Whistler valley from the top of Whistler Peak.

Saturday, 17 July 2010

Retained Layers

Retained Layers has landed and seems to have stuck.

In a previous post I talked about our layers framework. Up until now we've constructed a new layer tree on every paint. With retained layers, we update our layer tree incrementally as content changes in the window. More importantly, we are able to cache the contents of layers. So for example if you have an element with partial opacity, we can cache the rendering of that element in a layer and every time you paint (perhaps with a different opacity each time), we can paint the cached contents without rerendering the element. This provides noticeable speedups for some kinds of fade effects. When we use layers to render CSS transforms, we'll get speedups there too.

One side effect is that we were able to totally reimplement scrolling. Our current scrolling code relies on shifting pixels around in the window for speed, and that often doesn't work well, for example on pages where scrolling content overlays stationary content or vice versa. It's also prone to visible tearing on some platforms because we can't scroll and repaint in a single atomic paint operation. But now, our retained layer tree effectively contains the entire window contents pre-rendered. We can scroll by just adjusting the offsets of some layers and recompositing the layer tree. (Well, almost ... it's slightly more complicated.) This is a relatively simple approach. It eliminates tearing. It lets us aggressively accelerate the scrolling of nasty scrolling pages with complex contents, because we're able to separate the moving content into different layers from the non-moving content and scrolling becomes a matter of simply repainting the scrolled-into-view strip of the moving content and then blending layers together. We're seeing significant improvements in scrolling many kinds of pages. Soon I hope to blog again with more about how this works, what it can do and what the current limitations are.

Immediate improvements are nice, but the most important benefit of retained layers is that it lays down infrastructure we will be exploiting in all kinds of ways. Our D3D and GL layer implementations benefit from reducing browser rendering and caching more rendered content in layer buffers, since compositing buffers is very cheap with GPUs. With those backends, because scrolling is fully layer-based, it will be accelerated by the GPU! Chris Jones is working on enabling layer composition to be in a dedicated process, at which point we'll be able to scroll without synchronizing with the Web content process --- in particular we'll be able to maintain a constant frame rate of smooth scrolling no matter what the Web content is doing, i.e. super-smooth. This will especially benefit Fennec. Fennec will also benefit because its current tile-caching implementation can be replaced with something layer-based; our layer-based scrolling permits the layer manager to cache prerendered content that's not (yet) visible.

Before we ship the next Firefox release there are a few regressions to work on and some performance and quality knobs to tweak. But I'm feeling quite relieved, since this was one of the long poles for that release and the one I've been most on the hook for.

Wednesday, 7 July 2010

Mozilla And Software Patents In New Zealand

Mozilla produces the Firefox Web browser, used by more than three hundred
million people around the world. Firefox is open source and is the result of a
collaboration of a large group of paid developers and volunteers. In fact,
Mozilla funds a team of paid developers in New Zealand working on core Firefox
code; some key innovations in Firefox, such as HTML5 video, are the work of our
New Zealand team. The work we do is some of the most highly skilled and
high-impact software development to be found anywhere in the world. I write
about software patents in my personal capacity as one of Mozilla's senior
software developers, and manager of our Auckland-based development team and
also our worldwide layout engine team. I also formerly worked for three years
at the IBM T.J. Watson Research Center where I participated in the filing of
several software patents based on my research.

The development and distribution of Firefox, like other open source software,
is threatened by the rise of software patents, because the patent system was
not designed for our environment. In software, especially cutting-edge software
like Firefox, every developer is an inventor; coming up with new ways of doing
things is not exceptional, it's what our developers do every single day.
Invention created at such a rate does not deserve or benefit from years of
monopoly protection. Indeed, it will be crippled if we are forced to play the
patent system "to the hilt", to acquire vast numbers of our own software
patents and to navigate the minefield of other people's patents.

The patent system was designed to promote invention and especially the
disclosure of "trade secrets" so that others can build on them. Research casts
doubt on whether it has succeeded at those goals (see

an example
), but even if it did, in software development --- especially
open-source software development --- it is clear that no patent incentive is
needed to encourage innovation and publication of our work. Copyright has long
been adequate protection for both closed-source and open source software.
(Open-source software permits copying, but relies on copyright protection to
enforce terms and conditions on copying.) Indeed, the patent system restricts
the dissemination of our work because the best way to distribute knowledge about
software is in the form of code, and that can make us liable for patent

Software development is uniquely able to have huge impact on the world because
copies can be made available to users for free. If we had charged users for each
copy of Firefox there is no doubt we would not be nearly as successful as we
have been, either at changing the world or even at raising money --- Mozilla
has substantial revenues from "tie-ins" such as search-related advertising.
The patent system threatens this business model, because most patent licensing
arrangements require the licensee to pay a per-unit fee. This is not
necessarily a problem for traditional manufacturing, where there is a per-unit
manufacturing cost that must be recouped anyway, but it completely rules out
a large class of software business models that have been very successful.

As well as developing software, Mozilla does a lot of work to improve Web
standards, and here too we have seen damage from the rise of software patents.
We want to ensure that people can communicate over the Internet, especially
on the Web, without being forced to "pay to play". We especially don't want
any organisation to be able to control what people can do and say on the Web via
their patent portfolio. We're already having problems with Web video because
many popular video encoding techniques are patented so the production,
distribution and playback of Web video often requires patent licensing from
organisations such as the MPEG-LA. This has slowed down the standardization and
improvement of Web video and forces the use of effectively non-free software in many

In summary, the patent system is not suited to software development. Software
development, especially open-source software development, is harmed by patents
and does not need patent protection. Development of the Internet is also
hampered by patents. New Zealand stands to benefit directly and indirectly from
the rise of the Internet and collaborative software development and should
protect these benefits by making a clear statement by rejecting the patentability of "inventions" implemented in software.

Friday, 18 June 2010

Thank God For Science

Lord, thank you for making the universe simple enough that we can understand the principles of how it works, from the smallest atom to the largest galaxy; that could have been otherwise. But thank you also for making the working out of those principles so wonderfully complex and beautiful; that could also have been otherwise.

Two of the more disturbing books I've read are China Miéville's Perdido Street Station and Iron Council. They give me a peculiarly strong impression of a world where there is no underlying order --- where real science is impossible. They're wonderful stories though --- highly recommended :-).

(Yes, I need to locate The Scar...)

Tuesday, 15 June 2010

Thursday, 10 June 2010

Sleepless In Toronto

For some reason I often don't sleep very well on trips these days. So despite having had exhausting days and only about five hours sleep a night, I find myself awake in my hotel room at 5am reflecting on the last few days. Quite possibly I'm awake because the sheer excitement of this trip has my head buzzing. Maybe the good food, lack of exercise, and almost complete confinement to the hotel has thrown me off. I also suspect that over the years I'm becoming more dependent on home, my wife and children --- that's a good thing. Anyway, this has been a good time to take a mental break, to reflect, pray, recenter myself on God and update my blog :-).

It's been amazing to attend PLDI and the workshops after not having been to a major conference for five years. Even after five years away, I still feel like I fit right into this research community. I know a surprising large fraction of these people --- ex-colleagues and friends one or two degrees removed --- and more surprisingly, I remember most of them; normally my memory of faces and names is extremely poor. I've even found people I haven't met before who know who I am; that's gratifying, since I've been off the radar for so long and was never prolific.

Research trajectories have continued as one might have expected. Interest in parallelism has increased sharply, for obvious reasons. Interest in Web browsers and Javascript has increased even more sharply, since there was none among PLDI researchers five years ago. This is great; it gives me something to contribute to conversations in lieu of research results :-).

I am surprised to find that interest in parallelism has kept work on dynamic data race detection very active --- I thought that DRD work was being mined out in my day :-). There's not as much good evaluation on real systems as I'd like to see, though. I've also been sharing my anecdotal experiences with thread programming at Mozilla, which boil down to the observation that races and deadlocks are not actually a huge problem in themselves, since we try hard to minimize sharing between threads and keep communication patterns simple. The way threads hurt us is by adding nondeterminism, which can make reproducing even simple bugs much more difficult.

I think my LFX talk went pretty well. A few people told me it made them take notes and think, which is a good sign. I managed to get my slides online in spite of the hotel network being awful, at least in my room. The talk is basically a summary of what we do in Mozilla development, followed by requests for research in specific problem areas. One key idea I pushed is that the right place to introduce analysis results into the development process is probably during code review --- in other words, we should apply static and dynamic analysis tools to assist code review of specific changes, rather than in the traditional mode of analyzing large bodies of code to try to find important bugs. In general, finding bugs in code we've already shipped is less interesting, because either we've already found the bug, or the fact we haven't found the bug is evidence it's not important. Interestingly, Bill Pugh --- who has been pushing static bugfinding at Google for a few years now --- has independently come to similar conclusions.

I've also been advocating researchers work more on improving the process of fixing bugs, rather than just finding bugs, since it's bug fixing that is probably our true bottleneck for improving code quality. There's some sympathy, but it will take a while for that ship to turn.

Before I came here I wondered whether PLDI would give me an urge to get back into research. I certainly miss the people, the work and the environment, and it would be incredibly fun to get into research again, but so far nothing has challenged my view that my work at Mozilla is far more important than the impact I would have in research. The parable of the talents applies. It sure would be nice to figure out a way to push out a PLDI paper once in a while, though :-).

WebM Landed

Our initial WebM support has landed on mozilla-central. The main holdup was ensuring that Google's VP8 source license was GPL-compatible; that has now been resolved to everyone's satisfaction. Good stuff!

Of course, this is only the beginning. Currently we're working on support for the 'buffered' attribute, and there are many other bug fixes and improvements to make.

Friday, 4 June 2010

Not Implementing Features Is Hard

Sometimes we take heat for deliberately not implementing certain Web platform features. Three significant examples are SVG Fonts, WebSQLDatabase and H.264 in <video>.

SVG Fonts --- at least the subset implemented in Opera and Webkit --- don't offer anything significant over downloadable Opentype (or WOFF) fonts ... except the last three points of the Acid3 test :-(. And people keep asking for it "because it's in SVG 1.1". But I don't think those are good enough reasons on their own to make SVG Fonts an essential part of the Web platform.

WebSQLDatabase has a completely different problem. It's the only way of doing structured, queryable client-side storage in any browser right now, and a lot of mobile apps targeting Webkit-based browsers use it. The problem with WebSQLDatabase is that it isn't good for the Web, because it depends completely to the semantics and query planning of SQL as implemented by SQLite --- which is a somewhat quirky SQL implementation.

The pros and cons of H.264 have been well documented in this blog and elsewhere...

SVG Fonts and WebSQLDatabase would actually be very easy for us to implement. SQLite is already embedded in Firefox and even exposed to non-Web Javascript. The SVG Fonts subset implemented by Opera and Webkit is very simple. We could even support H.264 by hooking into specific codecs that may be present on various platforms (I think; the licensing for platform codecs is rather vague). It's certainly tempting to just cave in, implement these features, and move on. The people who complain that we're lazy, stubborn, or just wrong would move on or find something else to complain about. If we were only interested in market share, that's definitely what we'd do. But I honestly think we're doing the Web a service by resisting these things.

I think not implementing certain features is one of the hardest and most altruistic things we do.

Update I should also point out that we're not just exerting "stop energy" here; for each of these features that we're not adding, we are promoting superior alternatives --- namely WOFF, IndexedDB, and WebM.

Monday, 31 May 2010

Visiting Toronto

On Friday afternoon I'm flying to Toronto to attend PLDI and the associated LFX workshop, where I'll be giving a talk on "A Browser Developer's Wish List":

Web browser development is extremely challenging: compatibility with billions of legacy Web pages, specification and implementation of new Web-standard platform features, a wide range of devices and platforms to target, hundreds of millions of users to support, and severe security and performance challenges, all in an environment of white-hot competition. At Mozilla we use a variety of tools and processes to try to cope. This talk will analyze where they have been successful and where they fall down, with particular focus on major pain points such as nondeterministic test failures, mismatch between conditions "in the lab" and "in the field", and grappling with legacy code. We have bright hopes for the future, such as static array bounds checking and record-and-replay debugging, but other areas look dire, so I'll present my research wish-list --- including better performance analysis tools, verified refactorings, and static analysis packaged as assistance for code reviewers.

I arrive on Friday night, plan to attend workshops on Saturday and Sunday, PLDI itself Monday through Wednesday, and then on Thursday and Friday I plan to be in the Mozilla Toronto office, possibly with a side trip to the University of Toronto. I fly out on Friday afternoon, hopefully arriving home on Sunday morning. It'll be a great chance for me to reconnect with the research community I used to be part of, and catch up with a lot of old friends and colleagues. I'm really looking forward to it!

Dear Conservatives

One of the things that bothers me about "conservative" political movements is that in spite of their advocacy of self-reliance, private enterprise and limited government (which I agree with!), in times of trouble their members tend to look to the government to solve problems. It happens in economic crises and national disasters, it happens with trade and farm subsidies, and now it's happening again with the BP oil spill. Private enterprise created the problem, surely private enterprise can solve it? Why are conservative pundits blaming the federal government for not solving it?

Yeah, I know why.

Tuesday, 25 May 2010


Nero's complaint against the MPEG-LA is interesting. It seems to be primarily about the MPEG-LA deciding that Nero needs to pay H.264 license fees for "free trial" copies ... an interesting case study of the risks of murky license agreements. But there's a side antitrust issue. They dug up a Department of Justice memo that OK'ed the formation of the MPEG-LA on the condition that the patents in the MPEG-2 pool were limited to "essential" ones by having an independent expert verify that the patents were essential. The MPEG-LA chose as the independent expert their own co-founder and general counsel. Oops! Also, after telling the DoJ that 27 patents constituted "most" of the essential patents in the MPEG-2 pool, they proceeded to add 800 more. (The H.264 pool has even more.)

Saturday, 22 May 2010

Ip Man Fail

I just finished watching Ip Man on DVD. It was a good movie, but the subtitles were literally the worst I have ever seen in 20 years of watching many, many subtitled Chinese movies. I'm accustomed to confusing, silly, stilted, and absurd subtitles, but these were simply gibberish. My wife provided a running translation of the Cantonese but the Japanese left us both bemused.

It's hard to convey the awfulness ... None of the characters were named; the names were just translated into English and rendered without capitals, so the protagonist is referred to variously as "leaf teacher" and "leaf ask", his son is rendered as "leaf quasi", another character is just "wood", a villain is "three general", but some characters get names like "LIU2 BAO3". Word order is basically completely random. Martial arts challenges are described as "exchanging views" or "vexing". People kept saying "are you dry" --- I have no idea what that was about. Forget about punctuation.

I'm actually curious about the process that could lead to such terrible results. There's must be fifty million people who could do a better translation, not to mention Google Translate, so how did they end up with someone doing it this badly? Maybe the DVD I borrowed is actually an illegal copy, but why would they make their own subtitles? And surely there are Laotian street kids who can do a better job than this.