Sunday, 30 December 2007

Our Rectangles Overfloweth

When we're laying out content in Gecko, we create an nsIFrame object for each CSS box for each element, as I've described previously. CSS actually defines several kinds of boxes: margin boxes, border boxes, padding boxes and content boxes, depending on exactly what part of each element is included. In nsIFrames we store border-boxes always, and can reconstruct margin, padding and content boxes on demand.

CSS boxes for an element do not necessarily contain the boxes for that element's children. However, there are some situations where we want to aggregate geometry information for an entire subtree of elements:

  • For "overflow:scroll/auto" elements we need to figure out how far we should permit scrolling in each direction. A reasonable thing to do here would be to compute, and possibly store, the smallest rectangle containing the border-boxes for all elements which have the scrollable element as a containing block ancestor. Note that for overflow:auto elements, we need to know this during layout because we need to decide whether scrollbars should be shown.
  • To optimize repainting, we want to be able to quickly test whether a subtree of content is responsible for painting anything visible in a given rectangle that needs repainting. An obvious solution is to store on some or all elements a rectangle which contains all pixels drawn by the subtree rooted at the element.

In Gecko we mash together both of these concepts into the single concept of an "overflow rect". Every nsIFrame has an "overflow rect" which is the smallest rect containing both every pixel drawn by the frame and its descendants, and also the border-boxes of the frame and its descendants. We do the obvious optimization of not storing the rect when it's equal to the frame's border-box --- usually true since overflow is still the uncommon case. Combining the two concepts simplifies code and reduces memory usage. It usually doesn't produce any noticeable effects, but there are some unfortunate and relatively rare situations where it does. For example, adding a CSS "outline" to the child of an overflow:auto element can result in a scrollbar being displayed just so you can scroll the edge of the outline into view.

One unfortunate thing is that right now every container frame's Reflow method is responsible for computing the overflow area for the frame by unioning together the overflow areas of all child frames. It's only a few lines per Reflow method but like all code duplication it's unnecessary bloat and it's fragile too.

Another unfortunate thing is that the "bounding box of drawn pixels" area can be expensive to compute, in particular because it means you have to retrieve the ink extents for every glyph.

In a perfect world, I think we'd separate these two concepts, and store 0, 1 or 2 additional rectangles for each nsIFrame. We'd compute "scrollable overflow areas" by walking the frame tree directly from scrollframes instead of spraying code through Reflow() implementations. We'd compute the "drawing overflow area" lazily, possibly even while painting; this would get the expensive glyph extents operations off the layout path, which would speed up layout flushes, e.g. when script requests geometry data via getBoundingClientRect() or offsetTop.

I've thought pretty hard about ways to avoid computing the "drawing overflow area" at all. It's certainly possible for content that remains hidden, such as a hidden IFRAME or background tab. Unfortunately for the common case of page loading you almost always load the page, render it, and then something changes on the page --- a caret blink, an animated GIF, incremental content load --- and that usually forces you to compute the "drawing overflow area" of most elements in the page, in case they overlap the area you need to repaint. For example we should get the extents of each glyph on the page, to see if there's an insanely large glyph that might overlap the repaint area. (As I've explained in other posts, currently, even on trunk, for performance reasons we fudge and assume that at small font sizes glyphs stay within their regular font boxes. Webkit does something similar.)

Sunday, 23 December 2007

Drive-By Debugging

My trunk dogfood build was feeling sluggish yesterday so I thought I should have a poke to see why. I'd noticed sluggish episodes on and off over the last week or two so I thought there might be some kind of problem. "top" showed firefox-bin using 75% CPU even when I wasn't doing anything in the browser, and there were no animations or other obvious activity going on in my windows, so something was definitely wrong.

Fortunately I always dogfood debug builds so it was just a matter of attaching gdb... The first thing I did was poor-man's profiling, just hit ctrl-C to interrupt the process several times and look at the stacks. It was quickly obvious that we were constantly in painting code. I fired up QuartzDebug and confirmed that my GMail window was being fully repainted many times a second.

The next step was to figure out what was triggering the painting. I set a breakpoint on nsIFrame::Invalidate, which is what most Gecko code goes through to force part of a window to be eventually repainted. That breakpoint wasn't being hit very often, so it wasn't related to the problem. I then looked for lower-level Cocoa APIs that could be being used to force the window to repaint, and discovered nsChildView::Invalidate calling those APIs. So I set a breakpoint in nsChildView::Invalidate. Bingo! That was being called very frequently, invalidating a 2000x2000 pixel area of the window.

The stack for that call showed the whole story; you can see it here. Basically the window was being invalidated by a Flash plugin instance requesting a repaint. The Flash plugin was responding to an "idle" event which we send to the plugin at a fairly high rate; each one of these events was causing the plugin to request a repaint of the window. I'm not really sure of the purpose of these events, but it's part of the NPAPI plugin API on Mac that we send them frequently. I'm even more unsure why Flash was requesting repaints of the whole window all the time; it was easy to see that the plugin's layout frame was only 100x100 pixels, and furthermore, the plugin was hidden. I think GMail only uses Flash to play sounds. I suspect there's a deeper bug here somewhere in the intersection of Flash, Gecko and GMail. Eep. It could be related to Quartz drawing model support that we added in the last year that has some other known nasty bugs (whether on our side or the Flash side, again I'm not sure).

Anyway if the plugin is hidden, we should be able to ignore its invalidate requests, working around this bug and maybe other addressing other performance issues. It turns out that the invalidate requests pass through nsPluginInstanceOwner, which has a mWidgetVisible field which is false in this case because we know the plugin isn't visible. It's a one-line patch to drop invalidation requests on the floor when this field is false, and that's what we're going to do. I couldn't be sure of reproducing the bug in a fresh Gecko build but I used a gdb conditional breakpoint with an associated command to simulate the fix in my running build, and it worked.

Episodes of unexplained sluggishness that are hard to reproduce are very frightening from my point of view, because they can really hurt the user experience but it's very hard to track them down; they don't leave stack traces and often there are no steps to reproduce so it's hard to write up a useful bug report. The moral of my story, I suppose, is to dogfood a debug build and if it seems to suddenly be afflicted by a problem like this, be willing to attach a debugger, collect some stacks and do whatever else is necessary to track down the problem ... because you may be our best chance to find and fix the bug before millions of users hit it.

Saturday, 22 December 2007

Official Notice

David Cunliffe was New Zealand's Minister of Telecommunications, IT and Immigration until he recently switched to Health. (Personally I would have stuck with IT!) I just found his speech at the Open Source Awards on October 18. There's actually a great mention of our local Firefox operation!

Just imagine for a moment our world without open source.

More than two-thirds of the websites out there would simply disappear. But then you probably wouldn't be able to find the remainder because most of major search engines use open source. And if you did, you wouldn't be able to use what has become many people's favourite browser, Firefox: a piece of software developed in large measure by New Zealanders and right here in New Zealand.

Cool! Well, "large measure" is probably a bit of an exaggeration but I'll let him off!


One year ago I left Novell and joined MoCo full-time to start the Auckland office. It's been quite a year and overall I think things have gone well. We've got some good people on board, set up a nice little office, had our first intern, and most importantly, got a lot of work done. For many of us it's been a bit of a grind as we try to fix a lot of bugs before shipping Firefox 3. Hopefully next year we'll all have a chance to do more focused and interesting projects, new features and stuff like that.

But overall I'm having a great time --- working on something I'm really passionate about, face to face with a group of really smart people who I can talk to and work with and eat lunch with, at home in New Zealand! It's exactly what I've dreamed about for a long time. I've had to learn a little bit of management and a little bit of office logistics, which has been tedious at times but these are good skills to be learning.

I'm looking forward to next year. It's going to be challenging on many fronts, but Firefox 3 is looking good, Mozilla has momentum and we have the opportunity to do many exciting things in Gecko and outside it too. During the 1.9 cycle we developed some great test infrastructure that will help us move faster on the trunk and also help us maintain better branch stability for Firefox 3 maintenance than we had for Firefox 2/Gecko 1.8.1. Moving to Mercurial will help us make more changes in parallel. We also have a lot more (twice as many?) full-time developers than we had at the start of the 1.9 cycle, developers who've been climbing the learning curve and who are ready to storm ahead. This is good because we have a lot of work to do, a lot of areas that need fixing and a lot of items on our wishlist.

Here in the Auckland office I hope we can continue as successfully as we have been operating so far. We have space for a few more people! University graduate hiring was disappointing this year, we didn't find anyone who was really suitable. Very few students are exposed to low-level (C/C++) programming at a significant scale, and bright students are either surprisingly unambitious or their ambitions lie in creating the next hot Web startup. That's OK but I find browser development fundamentally more compelling --- we get to make the rules of the Web --- and I'd like to find more people who think that way. For now we've been successful finding oddball self-taught hackers, hopefully there are more out there!

Sunday, 16 December 2007

Barcamp Auckland

I spent the whole day today at Barcamp Auckland. I had a great time talking to Web developers and users about what they do and about Firefox, Gecko and Web standards. I had a particularly interesting conversation with a guy who builds MythTV boxes, about the situation with media codecs and free software.

As usual, I really enjoyed talking to Nigel Parker from Microsoft. The cone of silence around IE8 puts him in a tough spot at a conference like this, but that's not his fault. I was surprised that his talk hardly mentioned Silverlight, he seemed to be most interested in multitouch screens, which is fine I guess although it's not what keeps me awake at night :-).

I gave two talks, one about "The Future Of Web Standards" and one about "What's New For Developers And Users In Firefox 3". Both were well-attended. I burned up most of Friday putting together my FF3 demos so I only started working on the actual talks about 1am this morning. I was exhausted so I just wrote down just a few headings in the hope I could flesh them out on the fly. I'll have to read the blogs to see how successful I was but from my perspective it went about as well as a normal talk. I'd really like to develop the ability to talk with an absolute minimum of slide support.

"The Future Of Web Standards" basically went like this:

  • Standards are hard Creating and implementing standards is harder then just shipping whatever you feel like...
  • Standards are necessary But the alternative to standards is single-vendor domination, which would be extremely dangerous in the case of the Internet.
  • Clean up existing standards We have to improve the completeness and accuracy of existing standards...
  • Add new features But we also have to add new features or the open Web will become obsolete.
  • WHATWG/HTML5 Addresses both of these goals.
  • Video Video should be a first-class HTML element, but codecs are a problem.
  • ES4 Javascript must evolve to become a powerful and complete language, but there is opposition to this.
  • Politics Organizations are always trying to game the system to further their own interests, often at the expense of the open Web.
  • Your needs I solicit feedback about where Web developers are feeling pain and what they desire.
  • HTML matters HTML retains a position of strength because it's the only universal container format. HTML can contain anything but Silverlight and Flash are leaf elements.

"What's New In Firefox 3" went like this:

  • Who am I?
  • What is Mozilla? Not a Web browser company, but a nonprofit supporting the open Web and its users.
  • What is the open Web? A Web that allows anyone to participate in implementing and using, that is not dominated by a single player.
  • What is Mozilla doing in New Zealand? Gecko development!
  • Hiring Strong C++ developers: the open Web needs you
  • Demos: Pushing the Web forward Lots of demos.
  • Use this stuff if you care about open Web The best thing that Web developers can do for the open Web is to use Web standards, particularly new-feature standards, even (or especially) those not yet supported by IE. This won't always be possible when working for paying clients, but take advantage of any opportunities; graceful degradation helps. Adoption is the only way to pressure Microsoft to implement this stuff.

I demoed some Gecko features:

and some Firefox UI features:

The HTML/SVG containers demo actually shows a couple of problems. First, dragging the round window handles doesn't work when the mouse is outside the handles and over the child document, because the child document gets the events and they don't bubble out. I'm not sure what to do about that. Also, putting more than one page in the demo doesn't work quite right because SVG has no z-order control, to the photo-table code moves things to the front by removing them from the DOM and re-adding them at the top, but removing and re-adding an IFRAME reloads it, which sucks in this case. I'm not sure what to do about that either.

During the Firefox talk I attempted to demo Vlad's 3D-canvas extension but screwed up because I was using a debug build and I had built the extension for an optimized build. (Stupid me, I should have used an opt build for the demos, they would have looked smoother.) So right at the very end of the day I snagged a demo slot to show the teapot and GPU-based fractals.

The 3D canvas is sensational; I hadn't tried it before last night. (Vlad's prebuilt extension no longer works on trunk, but if you're making your own trunk builds you can configure with --enable-extensions=default,canvas3d and then install dist/xpi-stage/canvas3d.xpi into Firefox and it should work.) It's really great how his JS support code pulls GLSL programs straight from the HTML page; you get the "edit; save; reload" Web development cycle for GPU programming. I think this could be an excellent way to learn GPU programming; imagine an online tutorial with a bunch of starter examples.

Also, if we can make it secure for untrusted content, it addresses JS performance issues head on (for a certain class of problems): forget fancy JIT compilers and runtimes, just stick shader code in your Web page and we'll run it right on the GPU for maximal performance! Woohoo! The fractal demo is a superb example of this: a regular C program couldn't nearly keep up with that Web page.

Anyway, after a series of late nights and today's work I need a rest! I plan to take the first half of Monday off.

Standards are hard,

Wednesday, 12 December 2007

Video Wars

Cory Doctorow on BoingBoing has an eloquent survey of the battle lines over codecs for Web video ... a battle which is starting to heat up. Chris Double is over in San Jose right now preparing for the W3C Video on the Web workshop where this will no doubt be a critical issue.

We have here a culture clash. On the Web we have more or less established an expectation that standards will be implementable royalty-free. Attempts to introduce royalty-bearing standards are shot down or worked around. Audio and video standards, on the other hand, have a tradition of patent encumbrance and licensing pools --- not to mention DRM attempts. Now these two worlds are colliding.

My personal opinion is that DRM is an expensive and futile exercise. DRM schemes promote monopolies, hamstring innovation, and exclude free software. Moreover the experiment has been tried and it has failed, as the music industry seems to be acknowledging. Mere patent encumbrance isn't as bad as DRM, but it's still a problem for free software and truly open standards.

The good news is that browsers can support more than one codec. The W3C and others who favour an open Web should promote unencumbered codecs as a baseline, which today probably means Ogg Theora and Vorbis. Then everyone will have at least the option of free (both senses) production and consumption of media. Whichever vendors are willing to pay patent taxes can also offer encumbered codecs, and I suppose big media companies will be able to continue their DRM attempts that way.

Monday, 10 December 2007

Video Star

PC World has an article about standards-based video-on-the-Web with a few quotes from our own Chris Double. The quotes sound pretty good, congratulations Chris on surviving your encounter with the media.

It's too bad PC World NZ didn't pick up on the local angle. I guess they're just serving up a syndicated story, and they probably would not even have known Chris is based here in Auckland anyway. (Big hint to any media types who might catch this blog!)

Saturday, 8 December 2007

Interpreting Failure

Big news in New Zealand today is Graham Henry's reappointment as coach of the All Blacks. This is big news given that the All Blacks recently fell out of the four-yearly Rugby World Cup at the quarter-final stage. It's the first time ever a coach who failed to win the World Cup has been reappointed. Remarkably, the majority of public opinion backs his reappointment.

I think it's a great rejoinder to all those who think NZers are over-obsessed with rugby and World Cups in particular. I also think it's remarkably rational to concede that results are sometimes outside the coach's (or anyone's) control and that statistics are more meaningful than one-off results.

Naturally, there are a lot of misguided people complaining both that Henry was too focused on the World Cup and that World Cup results are everything so he should have been sacked.

Small Mammals

Ian Hickson writes interesting stuff about the evolution of companies. One quibble: what he describes is "evolution" only in a very loose sense. Evolution, even non-biological evolution, generally requires reproduction with heritable characteristics that affect fitness, and that doesn't seem to be present here. All we have here is adaptation IMHO.

That aside, he's basically right: people have learned to adopt business models that can't easily be crushed by Microsoft, but they all have the weakness that a superior Microsoft product would hit them hard.

He omits, though, that there are other things Microsoft could do (and is trying to do) that would also hit their competitors hard --- for example, patent assaults. And open-source isn't as immune from a cut-off-their-air-supply attack as I think he makes out.

Friday, 7 December 2007

Script Safety Annotations

I've been encountering a trunk bug where we make a call to an XPCOM method that happens to be implemented in Javascript. Unfortunately we make this call while we're tearing down a DOM element, during garbage collection. Running JS code during garbage collection is a very bad idea, so we crash.

This is a specific case of a general problem: some code is not safe to call at certain times. I would like to be able to add checkable annotations to functions and methods that indicate the following:

  • The function may spin the event loop or execute any script (these are equivalent).
  • The function may execute trusted script but will not spin the event loop or execute untrusted script.
  • The function will not execute script or spin the event loop (default, so dangerous methods have to be annotated).

We would need a way to specify these attributes on XPCOM IDL interface methods. (It would also be useful to have syntax for setting a default annotation for all methods of an interface.) Most of the scriptable Gecko API methods implemented in C++ could use these annotations. This might help Taras' refactoring work. It could help code analysis tools quite a lot by constraining what can run. I think it would help us catch a lot of bugs where we make unsafe calls.

We would want an escape hatch to "cast away" annotation checks, where some dynamic test guarantees that it's OK to call nominally less-safe code.

Saturday, 1 December 2007

Friday, 30 November 2007

A New Antipodean Free Software Outpost

Yesterday a Telecom engineer managed to connect some wires in the new office to a live phone line, so today we moved into 8 Kent St. I'm really excited about this. It gives us a lot more space and the location is great. We celebrated the move with lunch at the fabulous Hansan Vietnamese restaurant in Nuffield St. (I can't recommend that place enough --- cheap, tasty, filling, and great milkshakes!)

As you can see from the photos below, we still have quite a bit of unpacking to do, plus we need to buy some items and clean things up a bit. We also need to settle the all-important question of where to put our "Fathead" four-foot Firefox logo sticker.

Michael Ventnor arrived on Saturday from Brisbane to work full time with us for the summer, probably focused on Linux chrome. He certainly picked an interesting week to arrive!

In the picture below, our office is on the second floor from above the "8 Kent St" sign to the rightmost end of the building. Yes, we could open those doors but we haven't figured out a use for them yet! There is not a ten-pin bowling alley above the office, that's another building and I think the bowling alley has been replaced by a car park.

View outside 8 Kent St

Here's the main room of the interior. Clockwise from left are Michael Ventnor, Karl Tomlinson, Chris Pearce and Matthew Gregan. Chris Double was out; I'll try to get a better group shot tomorrow when he's around. There's a meeting room behind the partition on the left and there's additional space where I'm standing, beside the high-altitude doors in the first photo. Looking out from those doors (to the right of this photo) you can see in the distance the summit of Mt Eden and also the towers of the main Auckland Grammar School building (my old high school!). I'll get a photo of that.

Inside 8 Kent St

Thursday, 22 November 2007

Gripping Reality

Just watched Normal Again --- brilliant television. It made me wonder, if I was faced with two competing realities each claiming that the other is my delusion, how could I determine which one is real?

Here's an idea. Make up a very large number and ask one's friends in each world to factorize it in a reasonably short amount of time. You can check the answers manually via simple arithmetic. The inhabitants of the real world have access to computers and will be able to give a correct answer. The inhabitants of the imaginary world will not. (I'm making some reasonable assumptions, e.g. that my mental illness does not grant superhuman cognitive abilities or force me to cheat on multiplication!)

This probably would have worked for John Nash too. Who would have suspected that cryptographic primitives would be useful for psychotherapy and metaphysics!

Friday, 16 November 2007

Pegs, Holes And Reflow

I already blogged about Gecko's frame continuations being a mistake. It's time to rant about another big layout design error: the uniformity of the Reflow() API.

During layout, frames (i.e. CSS boxes) call Reflow to lay out their children and then position those children in some manner. The core problem is that Reflow's signature is the same for every frame type. That means that in theory, table frames have to interact with their row(group) frames in exactly the same way that inline frames have to interact with their inline children, or XUL boxes have to interact with their box children, etc. But this is nonsense, since the invariants, dependencies and data that need to cross the parent/child boundary are entirely different in each of these cases.

So in practice we have various kinds of magic probing and/or magic fields of structures that are only used in certain cases. This inevitably leads to breakage and overcomplex code. Problems are particularly acute in line layout, where we really would like to work with a flattened list of inline leaf items, but thanks to Reflow we can't. The textrun work has moved us to a situation where we construct a flattened representation of at least the text of a paragraph for line breaking and text shaping, and then we pull data from that in a hokey way as we Reflow text frames. It's somewhat painful as the two traversal models fight each other in nsLineLayout. Of course the aforementioned frame continuations crash the party too.

What we really should do is admit that parent-child frame type pairs are actually tightly constrained, i.e. an inline frame can only have an inline parent or a block parent, a table row frame can only have a table rowgroup parent which can only have a table parent, etc. (These invariants already exist actually, although the code sometimes doesn't want to admit it.) Then we should toss Reflow over the side and give each frame type its own specialized layout interface. Only a few frame types (e.g. blocks and tables) would be able to occur in "unknown" contexts and offer a generic layout interface.

In fact, we could go further and specialize further the types of child frames or even get rid of a uniform nsIFrame tree altogether. There's no particular reason why it makes sense to have tables, table rowgroups, table rows and table cells all be the same kind of object as text frames or SVG frames. Sure, we want to be able to iterate over CSS box tree geometry and style somehow, but there's a whole lot of generality exposed in nsIFrame that doesn't really make sense everywhere.

As an aside, the conflict between textrun layout and inline layout is an example of a general problem I've seen with cleaning up code. You rework module A to make it nice and clean, but because modules B and C are quirky, you have to add complexity to module A to keep things working and shippable. Eventually you rework B and C too but A's already been contaminated, so B and C inherit some of the sins of their fathers. You can reduce the effect by enlarging the scope of rework, but that adds risk and schedule issues of course --- in the limit you rewrite everything and sink your entire project.

Thursday, 8 November 2007

8 Kent St

As I mentioned recently, our team is growing to six people over the summer, so we need new space. After trials and tribulations reported previously on this blog, we finally have a lease on new office space at 8 Kent St, Newmarket.

This is a pretty cool area. There are lots of great food options in Newmarket. On the very block of the office there's O'Callahan family favourite Crazy Noodle Bar plus two yum cha (dim sum) restaurants (Sunnytown and Sun World) and a Mongolian BBQ place Gengy's. Nearby there's Happy Valley, Hansan, T-Mark, three food courts, a Chinese bakery, and lots of other places I don't know well ... yet. The office is actually above Lone Star, a big American-style place.

Given that, it's fortunate that I'll be able to walk to and from work. It's about 30 minutes each way at a fast pace. For people who live further away, there are great bus and train connections.

I'll be able to go for a walk in the Domain when I need to get away from my computer and actually think.

The Rialto movie theatre is about a block away from the office. Maybe interns will have enough time to use it.

My old high school, Auckland Grammar, is only about a kilometer away. It feels like after 20 years I haven't come all that far :-).

Wednesday, 7 November 2007

Intranet Explorer

I'm fascinated by the silence surrounding IE8. It suggests two possibilities: they're silent because there's nothing happening at all, or they're silent because they're cooking up something astounding. Both seem improbable; the latter, because Microsoft likes to advertise broadly and early to developers, and the former, because what was the point of waking up to do IE7 and then going back to sleep again?

Either way, they're showing little interest in implementing new Web standards such as ES4 or the WHATWG APIs (nor old ones such as CSS2.1 or DOM Events). Since ES4 is backwards compatible with ES3, the argument that it would break compatibility is bogus, but nevertheless that's their line. We heard the same thing during the IE team's three-year holiday between IE6 and IE7, interestingly enough --- the "compatibility matrix" made it too hard to do anything. Sometimes they seem to argue that they were right the first time, IE7 was a mistake and it actually was too hard.

Attitudes to compatibility are actually very interesting. Microsoft seems to take the position that any change that negatively affects a Web site is bad. Mozilla --- and our friends at Apple, Opera and elsewhere, I think --- insist that when sites rely on a bug that clearly violates a standard, we will fix the bug even if it hurts sites. (In some cases, we might push to change the standard instead, but only if the "bug" is at least tolerably sensible behaviour.) So for every major release we fix a lot of bugs, and we risk breaking sites.

I always expect Web developers to grumble about this, and every time I meet some, I ask them whether our relaxed compatibility causes them problems. The answer is invariably "no"! Or at least, the developers I meet prefer us to fix the bugs because although it may break things here or there, overall our more consistent behaviour makes it a lot easier to develop Web apps for Firefox than for IE. Almost everyone tells me they develop their sites first in Firefox, and when everything's working, they backport it to IE. (For some reason I always feel shy when I hear this.) I guess if you're going to iterate your site design, you want to do that with the browser that's easiest to work with.

Actually I think both attitudes are right, because we're addressing different sets of users. I suspect when Microsoft talks about compatibility they're largely talking about intranet sites inside corporations, which are often maintained poorly or not at all, so anything that's broken by a browser change will remain broken forever. And it's easy to see how the needs of large corporate customers can come to dominate the thinking of a software organization --- they're large accounts with focused contact and are used to getting what they want. (Hey, I worked at IBM!) As another example, we've seen how Microsoft's slow security update cycle trades off the security of home users against the convenience of large customers.

Maybe the time has come for Microsoft to split (at least at the engine level) the "intranet" browser from the "Internet" browser. Otherwise they actually risk painting themselves into a corner, where more and more Internet sites are optimized for Firefox or anything but IE. It sucks to be late to the party and having to be the third or fourth implementor of a bunch of new APIs; you've lost your say in how those APIs are designed and may be compelled to reverse engineer the behaviour of other browsers (although thanks to Ian I hope the latter is less of a problem than it used to be!).

Of course, there's a whole other perspective on this: Silverlight and .NET. "Compatibility constraints" in IE make a handy brake on the evolution of the open Web, very useful when pushing a competitor to the Web*. (Many have pointed out the big joke about Microsoft's ES4 objections, namely that C# has gone through two huge revisions in the last few years.) Shiny new platforms like Silverlight and WPF don't have to worry about compatibility now, but it will be interesting to see how they handle compatibility going forward. We're in a marathon, not a sprint, it will be a few releases before they get traction, and if they have to ship side-by-side Silverlight assemblies, one for each version they've released, it's not going to be a small download or a mobile-friendly footprint.

* It's uncouth to speculate that Microsoft's representatives might act in bad faith. Unfortunately, history shows it's a real possibility. I want to be polite, but not naive.

Finding The Core

A little while ago the New York Times had an interesting article about Christians and politics in the USA. It has its own predictable slant, and quotes broadly and therefore pulls in a lot of loons. It perpetuates confusing use of the noun "conservative" to mean either "theologically conservative" or "politically conservative" when these are very different things --- whose divergence the article is supposed to be analyzing. There are some quotes I really like, though.

But many younger evangelicals — and some old-timers — take a less fatalistic view. For them, the born-again experience of accepting Jesus is just the beginning. What follows is a long-term process of “spiritual formation” that involves applying his teachings in the here and now. They do not see society as a moribund vessel. They talk more about a biblical imperative to fix up the ship by contributing to the betterment of their communities and the world. They support traditional charities but also public policies that address health care, race, poverty and the environment.

Amen --- though there is nothing new or radical about that in the history of the church.

If more Christians worked to alleviate needs in their local communities, he [Rick Warren] suggests in the church’s promotional materials, “the church would become known more for the love it shows than for what it is against” a thinly veiled dig at the conservative Christian “culture war."


On the Sunday before the referendum on a state constitutional amendment banning same-sex marriage, Carlson reminded his congregation that homosexuality was hardly the only form of sex the Bible condemned. Any extramarital sex is a sin, he told his congregation, so they should not point fingers.


"I think they are going to have a hard time going out into the pews and saying tax policy is what Jesus is about, that he said, ‘Come unto me all you who are overtaxed and I will give you rest.’ ”

The article mentions "the Gospel" many times without actually saying what that is, except that it has political and social dimensions and evangelicals struggle over the emphasis placed on them. That gives the impression that evangelicals are more divided than they really are, because the core of the gospel is more important than anything mentioned there.

That core is, roughly --- acknowledging that each of us is guilty before God; recognizing that God has provided for our forgiveness by having Jesus take punishment that we deserve; and claiming that forgiveness by committing ourselves to Jesus as Lord.

That's really what we're all about. Of course that has huge social, political and other implications. But to me, that article and most others like it feel hollow. They pick at the fringes and try to understand what's going on (cue the "blind men and the elephant" analogy). I wonder whether the author actually know what "the Gospel" means themselves. I wonder who out there does. I didn't myself, for twenty years.

Sunday, 4 November 2007


Lately at work I've been focused on driving down the layout blocker-bug list, the bugs that we want fixed in Firefox 3/Gecko 1.9. These bugs are mostly regressions due to work done during the 1.9 cycle. At this point most of the bugs that are "obviously" mine, such as regressions from my text work, have been fixed, or have fixes waiting for review or landing, or depend on other such fixes. Now I'm picking off unowned layout blockers to work on. That unowned bug list is down to 46 bugs and falling quickly, which I think is very good news. The bad news is that some of those unowned bugs have been shunned for a reason...

One reason is that it seems in just the last couple of weeks, the usually-constant flow of obscure crashers and regressions detected by our demonic duo Martijn and Jesse has shrunk to almost nothing. Apparently they're still alive and working, so maybe this means we're over the hump? I hope so!

As regular readers will know, I've also been spending time looking for new office space to accommodate our growing team. This has been frustrating. We've expanded our search to Newmarket and have a couple of promising opportunities there. Hopefully I'll have good news to report soon.

Speaking of the team, here's what the other guys have been doing:

  • Karl Tomlinson has accepted the challenge of getting MathML on its feet again for the Firefox 3 release, after a severe lack of maintenance. Good luck Karl!
  • Chris Double has continued working on video. He has a patch which is almost ready to land (disabled!) on trunk.
  • New guy Chris Pearce has been working on blocker bugs, mainly text and editor bugs so far.
  • Even newer guy Matthew Gregan fixed a bad old Linux bug, worked on a crashtest harness, and is now working on layout bugs.
  • Michael Ventnor is currently still studying (I think) but he's planning to join us in Auckland for a summer internship! He'll probably be working on GTK themes and Firefox front-end issues.

And we're still looking for more people!

A word about Chris's video work... The WHATWG video spec changed a lot --- actually, grew considerably --- over the last few months. We don't want to make developers' lives hard by shipping a half-baked implementation of that spec so it will probably be necessary to delay enabling video support until after Firefox 3. We'll see how it goes.

We're in a similar situation with offline apps. There is a WHATWG spec now and it's somewhat different to what we've implemented. We definitely aren't interested in pushing a sole agenda so we're working out what we can ship in Firefox 3 that's aligned with the WHATWG spec.

These are tough calls, but our commitment to Web standards trumps checking boxes in the Firefox 3 feature list.

Tuesday, 30 October 2007

Linux Matters, Addendum

There's another thing I wanted to talk about but which really deserves its own blog post: the relationship between XUL, the Web, and free desktops.

First, I think XUL and the Web are both great for free desktops. They attack the "applications barrier to entry" that has made Windows too strong for too long.

Second, XUL does not compete with free desktops. For one thing it's very much open source, and furthermore, it's a toolkit and sits above GNOME etc.

Third, the distinction between XUL and the Web will erode over time, in the sense that the features you need XUL for today will eventually be offered as regular Web standards (CSS box model, enhanced widgets, offline execution, WHATWG APIs, etc).

Therefore the interesting question is not "how do we best integrate Firefox with GNOME?", but "how do we best integrate GMail (etc) with GNOME?" We've got some ideas but there's a lot more that could be done.

Monday, 29 October 2007

Linux Matters

I've been reading some dissastisfaction with the state of Firefox and Gecko on Linux. I feel I should comment because for a couple of years I was Novell's "Firefox guy" and did significant work on Gecko/GNOME integration.

I take exception to comments like:

However it geniunely seems that Mozilla does not care about Linux the slightest.

The truth is that during every development cycle we sink a ton of effort into making sure that Gecko and all its features work well on Linux. In 1.9 we've done lots of work to integrate with Pango, fix cairo-on-X issues, make sure <video> works, wrangle build-system and compiler issues, etc. If we didn't care about Linux, we'd just drop support for it. That would help us get Mac and Windows releases out faster, and after all they're where most users are. Fortunately we don't make decisions purely for economic reasons. I'd like to see people recognise that.

Part of the problem is that people are using Gecko 1.8.1 which is over two years old now. We'll ship Gecko 1.9 soon which has a ton of good stuff for Linux users:

  • Michael Ventnor (awesome volunteer contributor) has fixed a bunch of GTK theme bugs and turned on GTK themes for HTML form widgets --- very sexy. (MoCo is hiring him as an intern to carry on working on these and other issues during the summer.)
  • Teune van Steege (another contributor) has implemented GTK theme support for tree headers, which fixes the most important remaining non-native-looking UI element.
  • We've ripped out our own cross-platform drawing code and are now using cairo for everything. Along the way we've made a lot of contributions to cairo. We're trying really hard to be good community players here.
  • We integrate nicely with Pango now, using it to shape all complex scripts and also Latin text in many situations. By tweaking one pref you can disable the non-Pango fast path and get Pango for all text.
  • Thanks to Theppitak Karoonboonyanan and other contributors we use Pango line-breaking for scripts that have extraordinary line-breaking needs such as Thai, Lao, and Tibetan.
  • Karl Tomlinson (MoCo) designed and implemented "windowless plugin" support for X so that Linux can have platform parity with Mac and Windows users when Adobe supports it in their Linux Flash player (or if swfdec beats them to it!).
  • We've landed in 1.9 some of the GNOME integration work that I did for Novell, in particular startup notification support and dbus-based NetworkManager integration. (Some of the other work I did, like improved GConf integration has still to land ... just needs someone to push it in.)
  • Update Aaron Leventhal (IBM) and many other contributors have done a ton of work to make Firefox and the entire Mozilla platform accessible on Linux. This includes helping out with Linux-specific accessibility infrastructure and assistive technologies such as Orca.

There's definitely more we could do. I've been soliciting volunteers to implement RGBA translucent windows for X, for example, and it would be nice to support the GNOME print dialog. But I think we've made good progress.

One observation is that the number of Mozilla developers who are Linux users has dropped quite a bit as many of us (including me) have switched to Macs. I think this is partly due to Apple's hardware and software being very good and partly due to the fact that because Apple is evil, you can virtualize Linux on Mac but not the other way around. No doubt this has impacted Linux support a little bit. I still think that Linux is ultimately very important to Mozilla because proprietary client platforms will always pose a threat to the open Internet; the client vendors will constantly be trying to find ways to extend their control into the network. (And of course an open Internet is crucial to the survival of open clients, which is one of the main reasons I do what I do.)

Let me just address a few other complaints while I'm here:

  • The list of things Firefox could do to improve integration with the underlying environment goes on and on

    I'd like to see that list. Now that we have more heads, we might get some of those things done within MoCo, and I'd be more than happy to help other contributors get them done.
  • We have done a lot of work on memory consumption, some with help from Federico Mena-Quintero. We know this is a big deal. We're getting better in this and other areas and we're going to keep getting better.
  • Webkit is a good engine and getting it running in GNOME is a good thing, but be careful about comparing a two-year-old engine you use all the time (and hence see all the bugs of) with something that isn't quite there yet. Also, I would hate to see Apple with too much power over the free desktop ... keep options open.

  • WebKit ... happily uses GTK the way it was meant to be used instead of doing crappy hacks like cloning several instances of one widget and overloading its painting context.

    I'm not sure if this person knows what they're talking about, but if the Webkit/GTK port is using real GTK widgets in Web pages, then either they're doing some wizardry that I don't understand or they're going to have serious problems rendering content like this:

    (This demo might be mangled by feed readers etc.) Even Webkit on Mac and IE on Windows don't use real native widgets. I agree our theming approach on GTK is a crappy hack; I've been begging for years for a real GTK theme-drawing API we could use, like Mac and Windows provide.

Update Here's a screenshot of the Bugzilla query page in Firefox 3 trunk using Clearlooks:

Shiny Bugzilla

Friday, 26 October 2007

Growing Pains

Our NZ team is growing (hi Chris, Matt!) so we're searching for new office space. This is proving traumatic.

I got in touch with the operators of a building downtown. The location was perfect, terms agreeable, good space, everything looked fine, but then another prospective tenant came along and offered to sign a three-year lease; we can only sign for one year, so we lost the race. But then there was another smaller but still agreeable space in the same building where the tenants were delinquent, incommunicado and on the fast track to having their lease terminated. So we waited a bit more, and then on the very day their lease was to be terminated, the tenants reappear and want to carry on, so we lose again.

All this has happened at glacial speed so a couple of months have gone by without results. At least I know what we're looking for now (70-100 square metres, open plan, one-year lease, downtown) and a price range.

I've called a bunch of real estate agents and either they don't call me back, or they don't deal with offices this small, or they don't deal with one-year leases, or they offer me places which are totally hopeless. Yet I know what I'm looking for exists, because I've already found it on my own (almost)!

I found some listings on Trademe but they're mostly unappealing or stale, or direct me to real estate agents who don't call me back.

Today I wandered around my target area and noted down all the buildings that seemed to contain the sort of small leased offices I'm looking for. There are lots, about 18 actually. But only a few of them had contact information on display, and despite my best Internet search efforts, I'm unable to locate building management for the others.

I wonder how this is supposed to work. Are there real estate agents who are actually helpful? Is there a listing service or classified ad network that everybody uses, that I just don't know about? Am I deluded about the availability of the sort of space I'm looking for? Or does the market have the liquidity of granite?

I'd rather be fixing frame construction bugs!

Wednesday, 24 October 2007

Abstraction Penalties, Stack Allocation And Ownership Types

Sometimes, cleaning up your code makes it slower even when it shouldn't. For example, you might extract code from a function and make it a separate function. Maybe the compiler should inline your code, but it doesn't, or it does but the result still isn't the same as the original single function. This is an abstraction penalty: you use the programming language to structure your code with additional abstractions, and you pay a performance penalty.

Grouping variables into structs or objects is a common source of abstraction penalties. For example, converting local variables nscoord x, y; to nsPoint pt; may prevent the coordinates from being placed in registers, in some compilers. Or the coordinates may need to be placed in memory if you pass an nsPoint to another function instead of two nscoords.

That aside, there's a much worse abstraction penalty associated with objects in common "safe" languages such as Java or C#: they require heap allocation and garbage collection. (I'm ignoring C# structs for now for reasons that will hopefully become obvious.) And despite what people will tell you, garbage collection is still slower than stack allocation, often by a lot. When I was doing serious Java programming a few years ago, the way to make Java code fast was still to avoid using objects or manually recycle them to avoid allocation and GC costs. And the problem is that a whole lot of language features are tied up with objects --- interfaces, casting, information hiding, code reuse. I suspect one of the biggest performance issues switching from C++ to Java or C# may be that in C++ you can stack-allocate objects, but in Java and C# you can't. Just look at all the places where Gecko uses nsAutoString or nsAutoTArray to good effect.

The problem is of course that in a safe language, you can't just hand out pointers to stack-allocated objects like candy, because someone might store one away in a dark place and then later, long after the method has returned, start using it as a dangling pointer. This cannot be allowed.

What the world needs is a type system that allows references to stack objects to be given out, but restricts their usage so that no-one can use them after the objects are destroyed. Fortunately many such systems exist. A whole family of "region calculi" have been developed, for example. However, I prefer "ownership types" as a more intuitive and generally useful framework; in particular I like Boyapati-style "explicitly parametric ownership types".

These work by adding an "ownership parameter" to each class type. These parameters are a lot like generic type parameters, but they denote the "owner" of the object. The basic rule is that an object cannot outlive its owner. This rule is enforced by the typechecker. Here's an example of how this can work:

class Vector<O@P> {
(O@P[])@this array;
int size;
Vector() { array = new (O@P[100])@this; }
void add(O@P o) { array[size++] = o; }
class Iterator<O@P, Q> where Q <= P {
Vector<O@P>@Q inner;
int i;
Iterator(Vector<O@P>@Q inner) { this.inner = inner; }
O@P next() { return inner.array[i++]; }
void f() {
C@method c1 = new C@method(), c2 = new C@method();
C@method c3 = g(c1, c2);
C@R g<R>(C@R c1, C@R c2) {
Vector@method v = new Vector@method<C@R>();
return new C@R();
void h<R,S>(Vector<C@R>@S v) where S <= R {
Iterator@method iter = new Iterator@method<C@R, S>(v);
while (C@R c = { ... }

This code creates two objects, puts them into a standard growable vector class, then passes the vector to another function which uses a standard iterator to iterate over the vector. What's cool is that the compiler knows a lot about the lifetimes of these objects. In particular the objects which are @method, i.e., owned by "the current method", cannot outlive the method --- even though we pass these objects to other methods and even store references to them in other objects.

These properties are enforced in two ways. The main constraint is that code can only refer to objects whose owners are in scope. For example, you cannot declare C@R glob; and set glob = c1; in g to "leak" a reference to c1 --- the correct R is not in scope at the global level.

Similarly, an object like Vector that takes ownership parameters can only take parameters that "outlive" the object itself. This guarantees that fields of the object cannot become dangling references. In some cases, such as Iterator, we need to add "outlives" constraints to its ownership parameters; Q <= P would be read "P outlives Q". The semantics of ownership mean that "P outlives method" for all in-scope ownership parameters P.

Given the code above, the compiler could, using only local reasoning,

  • Stack allocate c1, c2, v and iter
  • Allocate space for g's result in f's stack
  • Inline the array object directly into Vector --- the compiler knows that the array object cannot outlive its Vector, and because there is only one assignment, it cannot die before Vector either.

Therefore the above code requires no heap allocations at all. ("Inlining" objects into their containing objects is another important optimization, much like stack allocation, that common safe OO languages do not support.)

It's important to note that although a really good compiler could discover these optimizations in Java, for example, using escape analysis, there are major problems leaving it up to the compiler. The primary problem is that escape analysis is expensive and fragile and compilers don't do it very well. A secondary problem is that if you change your program so that escape analysis no longer works, the only way to tell is that your performance gets mysteriously worse. With explicit type constraints, you get a compile error instead. That's especially useful here because quite often when you create objects in a method you expect them to be method-local, and it would be great for the compiler to check that for you and give you an error if you're wrong (instead of generating code that's slow in Java or crashy in C++).

Another note is that although the annotation burden appears large, the code can be slimmed down considerably using sensible default ownership parameters and other shortcuts such as local type inference:

class Vector<O> { // O contains @P
O[] array; // fields default to @this
int size;
Vector() { array = new O[100]@this; }
void add(O o) { array[size++] = o; }
class Iterator<O, Q> where Q <= O@ {
Vector<O>@Q inner;
int i;
Iterator(Vector<O>@Q inner) { this.inner = inner; }
O next() { return inner.array[i++]; }
void f() {
// local objects default to @method
var c1 = new C(), c2 = new C();
var c3 = g(c1, c2);
C@R g(C@R c1, C@R c2) {
Vector v = new Vector<C@R>();
return new C@R();
// implicit type and ownership parameters
void h(Vector v) {
var iter = new Iterator(v); // infer type parameters
while (var c = { ... }

There are even more tricks we can pull! For example, we know a @method object can't be accessed by other threads, so we can easily remove locking from it. In a transactional memory system we would know not to log accesses to it. When a method containing a @method object returns, we know the object must die, so we can deterministically run a destructor at that point, giving us the handy C++ pattern of using destructors for general cleanup on method exit. And when an object is about to go out of scope, we can often easily prove that the method's reference to the object is the only outstanding reference ("uniqueness"). In that case we are allowed to safely change the owner of the object to something else (which is never normally allowed)! This may require copying, depending on what optimizations have been performed. For example:

C@R f<R>() {
var c1 = new C@method(), c2 = new C@method();
var c = ... ? c1 : c2;
// may copy the object from our stack to elsewhere
return (C@R)c;

Tragically, this stuff doesn't really exist yet in a usable language, nor has anyone proven it to work programming at large scales. Sigh...

Tuesday, 23 October 2007

Backing Store #2: Dependency Tracking

I had another lovely Labour Day weekend away with my family at the beach. Naturally my thoughts turned to browser engines and again I'll take the liberty of recording them here...

One of the reasons Web layout is difficult is that you have to handle incremental layout efficiently. That means whenever your layout code accesses style data (e.g., GetStylePosition()->GetOffsets()), you need to think about what happens if 'left' changes. How do you guarantee that the layout will be updated?

In Gecko, this is mostly handled using "style change hints". When style changes, we compare the old and new styles and produce a set of bits summarizing what needs to be changed. One bit indicates that the frame (i.e. layout object) associated with the element needs to be reflowed. When a style change finds that bit set, we mark the associated frame "dirty" and eventually a reflow will happen for that frame.

The problem with this approach (and other similar approaches that we use for incremental layout and rendering) is that it decouples the code that consumes style data from the code that causes updates when that style data changes. This is fragile. For example, if you add new code that reads style data during layout, you'd better make sure that the style change hints are set correctly for when that style changes (and this code will be in an entirely different place), otherwise you will have subtle incremental layout bugs. It's also inflexible because it forces a strict pattern of dependencies; the layout of a frame can depend only on the style of its own element; if you want to look at the style of other elements, that's just not supported and you'll have to hack around it with more fragile code.

It would be helpful to have a technique that let us write only on the code that consumes style data, automatically ensuring that sufficient updates are issued when that data changes. Actually we would want this technique to extend beyond style data to other data sources too.

(What I'm asking for is really a form of reactive programming. I unfortunately don't know much about research in that area, except that it seems to be mostly conducted in specialized domains with exotic languages such as Haskell and Esterel, so probably not of much use to us.)

Of course the hard part is performance; we'd want a solution that's as least as efficient as what we currently do. For example, a solution that creates a pile of explicit one-way constraints, one per dependence, would be hopeless.

So here's one idea. Define an Updater class representing a no-arg function that will cause a computation (say layout of an element) to be re-executed in response to a change in underlying data. Make style data getters take an Updater parameter:

class Updater {
virtual void Update() = 0;
class nsIFrame {
nsMargin GetStylePositionOffsets(Updater* updater);

The contract is that when the offsets change, the updater will be invoked. I've moved style data access from a style object directly to the frame, because changes to the frame's style need to be tracked, not changes to the style context itself (it's basically immutable in Gecko). GetStylePositionOffsets will record a set of updaters that depend on the offsets of this frame. The caller will do something like:
class ReflowUpdater {
ReflowUpdater(nsIFrame* frame) : mFrame(frame) {}
void Update() { mFrame->PresShell()->FrameNeedsReflow(mFrame); }
nsIFrame* Frame();
nsIFrame* frame;
nsBlockFrame::Reflow(...) {
ReflowUpdater* updater = new ReflowUpdater(this);
nsMargin offsets = GetStylePositionOffsets(updater);

Now it's impossible, or at least hard, to depend on style data without the dependency being recorded.

This would of course be appallingly inefficient, so how can we make it efficient? We can adapt Gecko's current approach. Let's make a rule that changing certain style properties, such as the offsets, will always force the frame to be reflowed. In that case we don't need to record the dynamic dependency. If we're a little bit clever we can avoid almost all run-time overhead. First let's index all the style properties with integers and then have a table that tells us if we need to reflow when that property changes:

enum nsStylePropID { ..., POSITION_OFFSETS, ... };
const PRPackedBool styleChangeForcesReflow[];

We delay realization of dynamic Updater objects until they're really necessary:
class Updater {
class Realized {
virtual void Updater() = 0;
virtual Realized* Realize() = 0;

Then we refactor the style getters:
class nsIFrame {
template <class U> nsMargin GetStylePositionOffsets(const U& updater) {
TrackDependency(updater, POSITION_OFFSETS);
return GetStylePosition()->GetOffsets();
void TrackDependency(const Updater& updater, nsStylePropID style) {
... add updater->Realize() to dynamic dependency storage ...
void TrackDependency(const ReflowUpdater& updater, nsStylePropID style) {
if (styleChangeForcesReflow[style] && updater->Frame() == this)
TrackDependency(static_cast<const Updater&>(updater), style);

Assuming the compiler can constant-fold the load of styleChangeForcesReflow[style], this becomes very low overhead. When properties are accessed in a scope where the compiler knows updater->Frame() == this, there is no overhead.

So what's gained? It's now much harder to screw up, and we support more complex dependencies (such as dynamically conditional dependencies, and dependence of one frame on another's style) along with static dependencies in a uniform API. The hard-coded dependencies are now just an optimization that we can easily meter and tune. Similar tricks can be used to track dependencies of painting and other activities.)

Other things you'd want to do when implementing this: support revocation of outstanding ReflowUpdater::Realized objects when a frame is actually reflowed; have the style change processing actually use the same styleChangeForcesReflow array to decide whether to reflow frames.

There is extra complexity in some places, so it's not a no-brainer. Just something to think about.

Saturday, 20 October 2007

A Tale Of Two Zooms

Daniel Glazman is concerned about the behaviour of our zoom implementation. In particular he's bothered by the fact that zooming can change the layout of a page.

This is intentional. There are actually two ways you can implement zooming:

  1. Just scale everything by the zoom factor when drawing, and leave the page layout unchanged. This is what Daniel wants.
  2. Try make the page look as good as possible when zooming, by changing the layout as necessary. This is what we have implemented.

One key difference between the approaches is the way text hinting is handled. When you draw text at a certain size, a good font engine will "hint" the glyphs, e.g. make sure that the vertical lines of an "n" are aligned on pixel boundaries, and this can change glyph metrics. For example, the width of a hinted "n" in 20pt is not necessarily twice the width of "n" in 10pt. So, if we want text to look its best, we must allow the advance width of text to change non-linearly when we change the zoom factor, and that can change layout in arbitrary ways. If we insist on preserving layout, we have to have to use unnatural glyph advance widths, which can't look as good.

Another difference is the handling of native widgets. They may not look good or work well when scaled to odd sizes, so we might not scale them or scale them differently, if we're free to modify the layout.

Another difference is how the available width is handled. If you insist on preserving layout when zooming in, you will almost always force the user to scroll horizontally to see all the content, or when zooming out in a desktop browser, the full width of the window will not be used.

Furthermore as a practical matter we currently have no foolproof way to scale rendering of plugins without actually changing their size, so we can't implement approach 1 for plugins.

For all these reasons I think exposing the second zooming approach in the Firefox 3 UI is the right way to go.

However, Daniel is absolutely right to point out that this is not what you want for a "zoom out and pan" UI in a mobile browser --- or a "magnifying glass" UI, for that matter! For those, it is important to preserve layout. Fortunately, implementing them is easy in principle, now that we're based on cairo; just scale the transform when drawing. There are a few problems, such as handling plugin rendering as I mentioned, but those can be hacked around or fixed. Some work would need to be done to expose this zoom mode as an additional prescontext/presshell API. I'm sure that in the future we'll offer both modes (to embedders and XUL apps, if not to Firefox users). (You can actually mock up this approach today by embedding an <iframe> in an SVG <foreignobject> and scaling that, although there are some problems.)

Monday, 15 October 2007

Exploring Auckland

I've developed a habit of taking our family off on a whim to explore some park or reserve in Auckland because it looks interesting on the map. Yesterday we explored parts of Greenhithe. The primary goal was to check out Taihinu Historical Reserve, which should have a view across Hellyer's Creek to the shores of Beachhaven where I grew up. I found the head of the track down to the reserve (which someone has obscured with a makeshift wire fence, grrr), but the track was a bit steep, overgrown and too wet to tackle yesterday. We'll come back at a more suitable time.

Then we visited Marae Reserve at the end of Marae Road. My map suggests it has tracks heading north and south along the beach but as far as I can tell they don't exist, it's just a clifftop lookout with a nice view over Herald Island. Next stop, a shoreline reserve at the end of Kingfisher Grove. This has a nice view up Lucas Creek, but again, tracks shown on my map don't exist.

So we went back along Roland Road and found a walkway that cuts across a small creek to Churchouse Road. It's in a reserve used to graze pet sheep, and a few were gamboling around. Also backing on to it was someone's paddock with a large pig and some chickens. The kids enjoyed watching the animals and there were a lot of blooming lilies to enjoy too. At Churchouse Road the walkway ends at a playground in Wainoni Park. This playground is quite interesting --- including a maypole, a tractor, a very wide slide, a huge roundabout, and an installation of channels and gates for playing with flowing water. Most intriguing is a set of large plastic cups on stems set in the ground at an angle of about thirty degrees from the vertical. You can sit in them and spin around. The intriguing part is that if you just set yourself spinning gently then through no apparent effort, the spinning seems to speed up over time! It's a very convincing illusion of violating conservation of energy. I think that the secret is that because of the incline, as you spin you unconsciously try to straighten yourself vertically, and this motion drives the spinning somehow. Anyway, definitely worth checking out! Be careful with your kids though, because the spinning can be a runaway process...

Friday, 12 October 2007

Welcome To My Backing Store

In an earlier post I raised the question of whether a truly radical redesign of the Gecko frame system could be developed incrementally (which is almost the same as asking whether it can be developed at all). I think I figured out how that could be done.

What I would do is bolt on the new layout subsystem in parallel with the old one. So basically as well as running the frame constructor to build and update frame trees in response to DOM changes, and restyling and reflowing those trees, we could also have another DOM listener that builds and maintains some other kind of structure, and hooks to run layout in that structure. Initially all rendering and other uses of layout would continue using the frame tree. With this approach, we'd always have a working browser, and it would be possible to gradually extend the second layout engine to handle more and more element and styles, and to measure its space and time performance and compare them to the existing layout, and even to check its results for consistency with the existing layout. Then at some point we'd make it possible to render using the new layout, possibly even selectable at run time. Then we'd convert over other users of the frame tree and finally stop buildling it. This approach also has the advantage that the riskiest and most uncertain work --- how easy is it to fit the requirements of real-world Web layout into the new model, and how does it perform --- is tackled first.

I'm not saying we should do anything like this. I'm mainly leaving a note for myself in case this becomes important later.

Thursday, 11 October 2007

One More Reason Why We Need Audio (And Video) In The Browser

Via Slashdot

But the content experience on the Web is crap. Go to Aquarium Drunkard, click an MP3. If you don’t get a 404, you’ll get a Save As… dialog or the SAME GOD DAMN QUICKTIME BAR FROM 1995. OMFG. ARE YOU KIDDING ME? THIS IS ALL WE’VE ACCOMPLISHED IN 15 YEARS ON THE WEB? It makes me insane.

So we have media consumption experiences with no context (desktop media players) and an incredible, endless, emergent contextual experience where media consumption is a pain in the ass, illegal, or non-existent (the Web). FIX IT. Your fans are pouring their music-loving hearts into blogs, Wikipedia, etc and what tools have you given them to work with? Not much, unfortunately.

Tuesday, 9 October 2007

Fish, Water

Surprisingly, I will be giving a talk tomorrow at the Auckland University Bioengineering Institute, titled "Small, Hot And Parallel: The Future Of Web Browsing (And Computing)".

Since I don't know anything about biology, I'll talk about Web browsers instead. I'm planning to borrow shamelessly from Ras & Co's slides (with permission) to speculate about how one might build an awesome browser for small devices given the physical constraints of both humans and computers. Should be fun.

Monday, 8 October 2007

Tabula Fracta

When considering massive changes to existing code, to cope with fundamental new requirements, it's appropriate to think about whether there is an opportunity to do something completely new. Joel Spolsky isn't always right.

As I mentioned before I think there is an opportunity for someone to create a new browser engine and possibly win. Here's what they could do:

  • Target 8 cores or more --- i.e., pay no attention to performance on fewer cores. Existing engines can't afford to do this, so there's a market niche that they can't enter that will eventually grow to become the entire market --- a classic disruptive play.
  • Leverage the incredible work of the WHATWG on documenting HTML parsing, DOM APIs, etc, to really design code based on specifications that are close to Web-compatible, instead of designing something and having to hack it a hundred different ways to get Web compatibility. Where the WHATWG hasn't covered a topic yet, help them out. Existing engines couldn't do this because they predate the WHATWG work.
  • Use a new programming language with the following features:

    • Memory safety
    • Non-sucky exceptions
    • Real modules
    • UTF8 strings with an iterator API
    • Real global optimization with profile-driven, whole-program, ahead-of-time compilation
    • Immutable types
    • Generators and other syntactic sugar du jour
    • Garbage collection, of course
    • Safe manual memory management using ownership types (I'll write more about this later)
    • Copy-on-write cloning
    • Transactional memory and/or other modern parallel programming primitives
    • Typed message passing (messages should be typed for the same reasons as functions; see Microsoft's Singularity)
    • No crappy, hard-to-optimize, but inexplicably popular features such as identity and synchronization primitives on every object
    • Pluggable runtime, so at compile time you can choose what ABI, GC, etc you want to use ... so you can build components that will play nice in a variety of environments

    This is worth doing because if you're going to make a clean break, you should take the opportunity to make things so much better than C++. Memory safety alone would be a giant step forward for security (and many of the other items are ways to claw back the performance hit of memory safety).

While I think this approach might be a winner, it's still an extremely hard and risky road. Beyond the Joel risks, the biggest problem is the Web compatibility catch-22: you won't really be Web-compatible until you have enough market share that Web developers test against your engine, but you can't get that market share without being Web-compatible. (I suspect this is almost the entire reason why Opera hasn't been a runaway success.) To break out, you either have to work incredibly hard and be astonishingly compelling, or you have to be backed by some organization with great market power. Having said that, WHATWG and Mozilla are working to erode this catch-22, with some success, so things might be easier now than they used to be.

Clearly this approach would be much too risky for an established player to bother with. I would love to see a startup working in this area, though.

Update I should add to the above language requirements list:

    • Natural and efficient mapping to commodity hardware (sorry Haskell fans)

Changing Horses

Matt at Allpeers posted about the pros and cons of Mozilla switching from Gecko to Webkit.

This is something that people in Mozilla have discussed, multiple times, because the pros are quite clear. We get feedback from many channels that Webkit is cleaner and a lot easier to hack on, and I believe that; its code footprint is also clearly better. Beyond that, open source Web browsers and the Web itself could make progress much faster if we were pulling together on the same code base instead of doing everything twice. It would also reduce compatibility pain for Web developers.

The cons are also quite clear, however. We really really really don't want to leave XUL developers --- that is, developers of Firefox addons and XULrunner applications, not to mention our own Firefox and Thunderbird developers --- in the lurch. So XUL and attendant technologies (XBL(2), some XPCOM glue) would have to be ported. Generally any Gecko features that Webkit doesn't have would have to be ported. Considerably bug-compatibility would be inevitably lost.

It's not clear how project management would work. Apple probably doesn't want all that stuff in their tree. Anyway, it would be unsafe for the Web to put all our eggs in their basket.

Some people argue that having two open source Web engines is good because it avoids the problems of monoculture. It can also help in standards bodies to have multiple interoperating implementations of a feature. There's some truth to it, although I think I'd rather have one awesome open source implementation than two less awesome ones. (I think in the long run, a single dominant open source system would be a healthier, more monopoly-resistant software infrastructure than several competing implementations unified via fractious standards bodies. I also think that the split between KDE and GNOME is about the worst thing that ever happened to the free software world.)

The biggest problem, however, is getting from here to there. Mozilla can't leave the market for a few years to attempt a risky transition plan. That would be bad for us and bad for the Web. We have to keep improving Gecko to get maximum leverage from our existing market share, mindshare, and developer share. Also, as I suggested in my second-to-last post, Webkit is not the epitome of engines. It would suck to spend all our resources getting there and then discover we should have gone in another direction.

None of this rules out Mozilla --- or a third party --- doing a XUL-on-Webkit project on the side! I actually think it could be terrific territory for a startup ... far more worthwhile than yet another buzzy social networking site. Or, dare I say it, Flock.

I also think we should keep working on converging the XUL universe with the Web. That means projects like standardizing flex-box layout as a CSS3 module, implementing XBL2, implementing WHATWG drag-drop and bringing it to XUL, ditto for WHATWG SQL APIs, getting missing XUL widgets into HTML5, perhaps creating better standardized ways to bind native code to Javascript, WHATWG APIs for Webrunner-style desktop application management, and more. This would be good for the Web and eventually make it easier to port XUL apps to another engine.

Lastly, let me deflect the charge of "Not Invented Here"ism by stating for the record that I have no great love for Gecko. I did not invent it, I think it has major flaws, and I would be most happy if it vanished and was replaced with something superior in every way. For the forseeable future, that's not an option.

Tragic Vindication

Sadly, I was right; the All Blacks lost to France. The details of my prediction were a little off, but the irrational reactions I expected are appearing now.

The core irrationality is the belief that if you lose a close rugby game, there must be some fundamental reason, some fundamental failure that could have and should have been prevented. This ignores role of chance and circumstances beyond the team's control, which is clearly huge. Refereeing decisions alone can account for a large margin in almost every game. If success requires eliminating the possibility of losing, then a truly successful team would have to win almost every game by 20 points. No team in rugby has ever been that good.

I hope that NZ rugby fans put this in perspective and satisfy themselves with crushing all and sundry between World Cups. Some people also need to get it into perspective with life in general.

A more general lesson: sometimes you can do everything right and you still don't win. Corollary: if you don't win, that doesn't mean you did something wrong ... and you shouldn't panic and make changes unnecessarily. I hear that this is a lesson that poker players need to learn early.

Sunday, 7 October 2007

If I Did It

I think Gecko's frame model is a big mistake.

For those just tuning in, Gecko builds a tree of nsIFrame objects for each document. Each frame represents one CSS box, a rectangular area which renders some content. A single DOM node can generate multiple CSS boxes when it breaks. For example, an inline element or text node can break across multiple lines, creating multiple boxes, and hence multiple nsIFrames in Gecko. The frames for a single DOM node are linked into a doubly-linked list, the "continuation chain".

Continuations are the root of a lot of problems. Changes in layout require changes to the frame tree; frames must be created and destroyed, pointers updated, etc. This requires a lot of code, and it's fragile, lots of bugs leading to memory-safety violations. It also consumes quite a lot of memory. For example suppose you have K nested spans wrapping a large chunk of text, which get laid out across N lines. We create K*N frames, and each one's about 50 bytes. Creating and destroying these frames is probably slow --- it's hard to measure the performance cost of
the continuation model, though.

Continuations are, in principle, good for complicated layout like pagination, columns and advanced layouts like "fill text into this box here, and then when that's full, this other box over here". But over the years, as we've worked out the details, it's become clear that in a CSS context there are grave problems. For example, with vertical breaking and elements with a specified CSS height whose children overflow that height, you run into situations where an element's children have more continuations than the element itself, and so you have no natural parent for the children's continuations. All the options are bad; lately in Gecko fantasai has created "overflow continuations", ghostly additional continuations for the element just to host its overflowing children. It works surprisingly well but nevertheless, the continuation model is leading us down an increasingly complex and disturbing road. And we will need to add still more complexity to fully handle breaking of positioned elements.

Let's take a step back and ask the question, "what's the minimal information that we really need to compute and store during layout, that will let us efficiently paint any section of a page (or handle events or compute offsets requested by script)?" For discussion's sake let's focus on blocks containing inlines.

Here's one answer: all we really need are the line breaks and some information about the y geometry of each line. A line break can be stored as a pair (DOM node, (optional) text offset). For each line we could store the y-offset of its baseline, its ascent and descent, and occasionally an "overflow area" containing the area rendered by all its descendant content if that sticks out beyond the normal line bounds.

In most cases we wouldn't need any kind of layout object for the inlines themselves! From the line information we can compute everything we need easily enough, except for complex stuff like inline-block/inline-table and replaced elements. This could really slash memory usage. It could also speed up layout and even simplify code. (By the way, Webkit doesn't use continuations like ours --- a good
move --- but they do have one render-object per element, so I think it can be improved on.)

Of course lots of code (e.g. painting) needs to inspect the geometry of actual CSS boxes. I'd provide for that by exposing a "box iterator" API that lets clients walk a
hypothetical CSS box tree.

One nifty thing this approach would allow is fairly easy implementation of vertical
writing: the box iterator could transform its output boxes to the correct orientation.
Relative positioning could also be done in the iterator.

Vertical breaking (e.g. columns and pages) could be handled in a similar way, perhaps, by storing the DOM offsets of vertical breaks. So if you have a block that breaks across pages you only have one layout object for the block, but when you ask for the CSS box subtree for the block, you specify the DOM boundaries of the page you're interested in and you get just the boxes for the content in that page.

This isn't a real proposal. There are huge questions about how all the rest of layout could be expressed in this model, huge questions about what happens to frame construction, how to cache things so that painting isn't slow, and so on. There are even huger questions about how even if this was designed, it could be implemented incrementally in Gecko or any other context. It's mainly my daydreaming. But I think there is a point here worth taking, which is that there's probably considerable headroom to improve the design of Gecko, and Webkit too.

Friday, 5 October 2007


David Baron and I tried a new approach to layout triage, using a Google Docs spreadsheet to record our decisions collaboratively. I added some automation steps so the overall workflow goes like this:

  • Use the Bugzilla query to locate bugs which have been requested as 1.9 blockers.
  • Download the query results in CSV format.
  • Use a trivial Perl script to trim off columns I don't want and add a new column which is the Bugzilla URI for each bug.
  • Import the CSV into a new Google Docs spreadsheet.
  • Add columns in which David and I can each write our evaluations.
  • Invite David and Damon as collaborators.
  • David and I read the bugs (with the help of the URIs, which Google Docs makes clickable) and add evaluations to the spreadsheet (the Real Work).
  • Discuss any differing evaluations until we converge on a decision. Mark decisions by bolding the evaluation we settle on.
  • Export the spreadsheet to HTML and save it locally.
  • Run another Perl script to identify the bolded decision for each bug and generate a Coscripter script to update all the Bugzilla bugs!
  • Run the Coscripter script.
  • Go to lunch.
  • Return from lunch, discover that my laptop went to sleep while running the script, and restart it from the last not-updated bug.

I'm not sure whether this saved much time, in the end, compared to just exchanging comments via email and marking bugs manually, but it was a lot more fun! (And marking bugs manually is very very tedious, at least when you're on a different continent to Bugzilla.)

Also, during this exercise I played around with Google Docs a little bit and discovered that their charting tools use SVG! Excellent!

Here's the Coscripter-generation-script, by the way:

#!/usr/bin/perl -w
sub resolve {
my ($bug, $resolution) = @_;
if ($resolution eq "blocking") {
print "* go to \"$bug\"
* select \"+\" from the \"blocking1.9\"'s \"blocking1.9\" listbox
* click the \"Commit\" button\n";
} elsif ($resolution eq "wanted") {
print "* go to \"$bug\"
* select \"-\" from the \"blocking1.9\"'s \"blocking1.9\" listbox
* enter \"[wanted-1.9]\" into the \"W\" textbox
* click the \"Commit\" button\n";
} elsif ($resolution eq "minus") {
print "* go to \"$bug\"
* select \"-\" from the \"blocking1.9\"'s \"blocking1.9\" listbox
* click the \"Commit\" button\n";
my $bug;
while (<>) {
foreach my $cell (split(/<td/)) {
if ($cell =~ m!(http://.*)!) {
$bug = $1;
if ($cell =~ m!class='g s4'>(\w+)!) {
&resolve($bug, $1);

Wednesday, 26 September 2007

Parallel DOM Access

Suppose we want to exploit parallelism to load and run an existing Web application faster. How might that be done?

Here's a very high level diagram of the data flow inside the browser. I believe it's reasonably accurate for Webkit as well as Gecko.

There are some missing edges in some cases; for example, the style system can affect the DOM via XBL. I'm going to gloss over those for now.

Observe that the DOM is really the center of the universe. It's a big blob of mutable state that everything else depends on. Any parallelization of single-page applications is going to have to carefully manage access to the DOM.

For performance reasons, changes to the DOM are lazily propagated to the style system, layout and rendering. The goal is to batch changes so that these phases are not reexecuted too often --- they're expensive, even when incremental. DOM updates make method calls to registered listeners. Listeners record which styles might have been affected and post a restyle event (if one hasn't already been queued) to be processed later. Similarly, they set dirty bits in the frame tree and then post a reflow event. On the other side, the parser batches its appends to the DOM as well. It's primarily only script execution that makes many fine-grained, interleaved reads and writes.

[There are times when scripts need access to up-to-date style and layout data. In Gecko, at those times we invoke FlushPendingNotifications to force synchronous restyling and layout. Because this is already a significant performance hit, Web developers should already be trying to avoid triggering it (e.g., by accessing DOM offset* properties).]

I think we could leverage these access patterns to help parallelize browser execution:

  • Parsing can be mostly asynchronous; it should only need to synchronize with the DOM when it's ready to append a bunch of elements.
  • Styling, layout and rendering can take a snapshot of the DOM and use it while the real DOM is being updated by other tasks. It's OK for the display of a page to lag slightly behind; it already does today. The snapshot will be refreshed each time we need to update the window again, or when layout results must be return synchronously to scripts.
  • To run scripts, such as JS event handlers, in parallel, we could use optimistic concurrency via transactions. The idea is that we run a script speculatively against a snapshot of the DOM, recording which parts of the DOM it reads and suppressing its changes to the state of the DOM and other parts of the world. When the script has completed, we synchronize with the real DOM and check whether anything the script depended on has changed. If not, then we can commit the script's global changes. Otherwise, its execution is invalid; we throw out its changes and reexecute it all over again.
  • Some DOM-accessing code cannot be executed speculatively, such as plugins, or Javascript that takes actions that cannot be rolled back, such as sending a message to a server. (At CMU, the canonical example of an irrevocable message was "fire missile!") Therefore at any point in time there can be (at most) one thread accessing the "real DOM" which is not speculative and will never be asked to abort.

This model would be particularly useful for Firefox where extensions written in Javascript have access to the DOMs of all browsed pages. We could allow extensions to execute in parallel with client code as long as at least one of them is speculative.

None of this is easy to implement. Making real snapshots of the DOM would be prohibitively expensive, so some kind of versioning or copy-on-write scheme is required. Which state constitutes "the DOM" that needs versioning is actually a little nebulous; for example, would we version the state of <canvas> elements? How about DOM Storage or the proposed DOM SQL API? However, the good news is that some of this can be done incrementally. For example, we could start with a limited slice of DOM state that is versioned, and decree that speculative script accessing any other state is aborted, and then gradually increase the scope of versioning.

There's a lot more to think and talk about in this area.