Saturday, 11 February 2006

Anatomy Of Bloat

Yesterday I ran into some really nasty, bloaty code. This isn't particularly unusual, but this time I was bothered by the fact that this code was mostly written after a lot of people started working hard to de-bloat core parts of Gecko. This wasn't the first time I noticed problems in this code either, but for various reasons I felt particularly bothered yesterday. So I'm taking the opportunity to make something positive out of this by letting off some steam and exposing some practices that absolutely must be stamped out.

I have some examples from the SVG code. I do not intend to defame our SVG contributors, without whom we simply wouldn't have SVG support. Yet the fact that SVG has a lot of problems suggests they needed external code review and encouragement well before now.

Let's take a look at something simple: rectangles. An interesting question to ask is what gets created for an SVG <rect> element? Here's an answer:
TypeCountObject SizeTotal Size
nsSVGRectElement1104104
nsAttrAndChildArray::Impl12828
nsAttrAndChildArray::Impl14444
nsCSSStyleRule12828
nsCSSDeclaration12828
nsCSSCompressedDataBlock188
PRUint8[]188
nsSVGClassValue12424
nsSVGAnimatedTransformList13636
nsSVGAnimatedLength636216
nsSVGLength644264
nsSmallVoidArray::Impl740280
nsWeakReference81296
nsSVGTransformList17676
nsSVGRectFrame1116116
nsSVGRendererPathGeometry11616
This is only approximate, since I computed it by hand, and it doesn't include some details like the storage for the DOM attributes that the rect would presumably have, nor does it account for the frame's style context and some other generic data (which might, however, be shared if you have a lot of similar elements). It makes some optimistic assumptions about the allocation behaviour of some of the dynamically allocating arrays. It also doesn't account for intra-object padding and inter-object overhead for the heap objects. I apologize in advance for any errors. But it's good enough to get an idea of what's going on, especially with respect to SVG-specific data.

Overall, that's a lower bound of 1372 bytes on a normal 32-bit machine. I won my bet with Boris that it wouldn't be under 1K! For a single rectangle element! Other interesting statistics to think about: that's 39 heap allocated objects, 26 of which are reference counted XPCOM objects. Many of the objects support multiple C++ interfaces, hence require multiple vtable pointers per object; in fact 320 of those 1372 bytes are for vtable pointers. On a 64-bit machine, which we can no longer consider pie in the sky, the numbers are worse as pointers grow to 8 bytes each: 2376 bytes, of which 640 bytes are vtable pointers. Eeeep!

So how did we get to here, and how can we get out of here? I'm afraid the main culprit is XPCOM and a design that leans heavily on it; the critical decision was to have every object in the SVG DOM implemented directly as an XPCOM object. One of the biggest issues is the way SVG handles coordinates. Following the SVG DOM spec, each coordinate (an SVG rect has 6, x/y/width/height plus two bonus corner-rounding values) has been made an XPCOM object, an nsSVGAnimatedLength. An nsSVGAnimatedLength has two nsSVGLength components in theory: the "base value" and an "animated value". Since we don't support animation yet (if we did, a straightforward extension would make the above numbers significantly worse) our nsSVGAnimatedLength objects have just a single nsSVGLength child object, so that's 12 XPCOM objects accounted for already.

Another big problem is that the SVG code relies on an observer pattern implemented through XPCOM. Changes to SVG values like the coordinates are propagated to objects which have explicitly attached themselves as listeners. To avoid strong-reference cycles, the listeners implement a weak-reference pattern, which is where our nsWeakReference objects come in (each of which is a ref-counted XPCOM object). As you might expect, the frame listens for changes to each of its SVG coordinates. For no reason I can see, each nsSVGAnimatedLength listens to its base value. There's 7 more XPCOM objects for their nsWeakReferences.

There's also an nsSVGAnimatedTransformList for the rect, just in case it has a "transform" attribute I suppose, with a child nsSVGTransformList that it listens to. That's 3 XPCOM objects for those two plus the listener's nsWeakReference. The other XPCOM objects are the content element, the nsCSSStyleRule to hold a CSS rule expressing the style impact of any presentational attributes that might be on a <rect>, the nsSVGClassValue which seems to hold the element's class in case you want to animate it (!), and an nsSVGRendererPathGeometry which gets attached to the frame. I'm not sure why this last one needs to be a separate object.

Clearly it's imperative to simplify the coordinates, especially animated coordinates, so they're not XPCOM objects. I actually have a suggestion for how to do this that's been languishing for a while. It would shrink an animated coordinate down to 8 bytes for the common case where the value is not animated (compared to 92 bytes currently). The DOM interfaces would be implemented as "tearoffs" so we only allocate them if they're used.

Another imperative (actually a prerequisite for the above) is to eliminate the observer pattern and the use of weak references. We do not need to support an arbitrary graph of notifications in almost all cases; storing the explicit dependence graph is hugely wasteful. Attribute changes, style changes and DOM method calls already notify or are implemented by the content element, which can directly notify its frame. This can eliminate a huge amount of code and data. If we just do these two items I think we'll have made a huge step getting the code back under control.

While studying this code I discovered some interesting additional problems which I'd better mention before I forget. They may prove instructive.

  • A CSS style rule is created for every SVG element that might have presentational attributes, even if there aren't any on the element. This is just silly and should be easy to fix (as a comment in the code mentions!).
  • SVG values are expected to have zero or one observers, so nsSVGValue uses an nsSmallVoidArray to represent the observer list which is optimized for the 0-1 case. This is a pointer-sized field that can either store a direct pointer to an observer, or a heap-allocated array for the hopefully rare case of multiple observers. But it turns out the rectangle's six nsSVGLength values are observed by both the frame and its containing nsSVGAnimatedLength! So the common case is to have 2 elements, and each value has to heap-allocate an nsSmallVoidArray::Impl, and happens to allocate one with a default size of 8 pointer elements (plus overhead). nsSVGTransformList suffers the same fate. Welcome to 7 heap allocations and 280 bytes.
  • nsSVGTransformList contains an nsAutoVoidArray member for its list of transforms. This array type is meant for use on the stack, and lets you avoid a heap allocation if the maximum count required is no more than 8 elements. Since most SVG elements don't have any transforms, we burn 8 pointer elements plus overhead for nothing most of the time. This is actually a good place to use nsSmallVoidArray. (But why can't nsSVGRectElement::mTransforms just be null if there are no transforms? Beats me.) Generally speaking one should not use nsAutoVoidArray (or similar classes such as nsAuto(C)String) as object fields.
  • Not actually seen in this example, but seen in code nearby: some SVG classes contain PRBool fields. PRBool is a 4-byte type and should never be used in objects. Space could be saved just by making these fields PRPackedBool (or even PRPackedBool mField:1, for one bit!) and rearranging the fields to avoid padding.
  • There are other things I could complain about, like the presence of "mFillGradient" and "mStrokeGradient" in every single rectangle frame regardless of whether the frame actually uses gradients, but those are small fry compared to the above.


I haven't said much about code size yet. Just constructing and maintaining the big graph of objects takes considerable code. Much of it is boilerplate code
repeated over and over with little or no sharing. There is other evidence of copy-paste coding. It's been said so many times, but I'll say it again: copy-paste coding is evil. It bloats source and object code, breeds inconsistency, discourages the creation of useful mental abstractions, and will inevitably make you fix the same bugs many times.

An overarching lesson is that XPCOM is a disease. It tempts people who should know better to create systems which are nasty, large, and inevitably, slow. It is a contagious disease; people acquire it by being exposed to infected code. Developers can be immunised, as many of us have, mostly by suffering through a bout of it. Perhaps diatribes like mine can help immunise others with less suffering. XPCOM does have its uses --- as a component mechanism in situations where one absolutely requires dynamic component loading and binding, and where we need to cross language boundaries --- but wherever it spreads beyond that, it must be stamped out.


24 comments:

  1. Wow... this is one interesting post Robert. Is this code before Tim actually started working on the SVG code in Mozilla?
    Another question, does this analyzing of several pieces of code within Gecko derive from the work you did in bug 317375? Or is this an ongoing effort of the core Gecko hackers to make the code more elegant/performant/easier to maintain?
    Thank you so much for posting this, this is fascinating stuff.

    ReplyDelete
  2. "It's been said so many times, but I'll say it again: copy-paste coding is evil. It bloats source and object code, breeds inconsistency, discourages the creation of useful mental abstractions, and will inevitably make you fix the same bugs many times."
    This should make it into some quote collection, like "the xxx most important quotes in history of life". Amen!

    ReplyDelete
  3. No no, you're completely missing the point. XPCOM rules :-)
    The reason XPCOM is so pervasive in the SVG implementation is because we are replicating the SVG DOM structure internally.
    This decision was mainly taken for two reasons:
    - Limited man-power: We had the SVG standard as a design template for the internal object model. This was much quicker than developing our own internal object model. Also, if something in SVG worked from C++, it would work from JS via the DOM. With different object models for JS and C++ maintaining and testing the code would be almost twice the amount of work.
    - The main use case that the SVG code was originally implemented for (Crocodile Mathematics) manipulates most SVG dynamically from JS via the SVG DOM. Here tear-offs would be counter-productive for performance.
    I don't know whether you are just ranting for the sake of it or whether you had a _real_ problem with the SVG code, but here are some performance tips:
    - Don't use lots of objects if you don't plan to manipulate them via the DOM. Use <path>s.
    - The major performance bottleneck in SVG is the rendering backend. Ever since the decision was taken to replace libart/gdi+, interactive SVG performance has droppen by an order of magnitude (at least for my testcases). Performance might have improved since I last looked (1/2year ago), but I would start any optimizations here.
    - Why rant about CSS style rules, nsSmallVoidArrays, PRBools etc. when you could just fix them?
    - Replacing the observer patterns with something more centrally coordinated is a great idea.
    Here's another thought:
    Maybe the real problem is SVG as such. I don't think you can come up with an implementation that performs well under all use cases. The SVG DOM is just a nightmare.
    Maybe it would be a better idea to start from scratch building some lean vector graphics primitives into XUL. SVG could be then be implemented in XTF/XBL.

    ReplyDelete
  4. I've found information how to tweak firefox.
    You can significantly accelerate firefox.
    You can find information how to do it over here: http://www.mozila.pl/firefox-speed-up.html

    ReplyDelete
  5. Andy Cartwright11 February 2006 09:31

    Why is it that many commits seem to go without a bug number and without mentioning any reviews? This seems true of Thebes especially. I'm worried how many bugs (or bad practices) like the ones you have mentioned here, go in to the tree unnoticed...

    ReplyDelete
  6. > The SVG DOM is just a nightmare.
    Oh yes, especialy for newbies. I just recently learned the SVG DOM and it was really a pain.

    ReplyDelete
  7. Robert O'Callahan11 February 2006 16:36

    > Is this code before Tim actually started working
    > on the SVG code in Mozilla?
    It started before Tim, but things have continued along the same path since.
    > does this analyzing of several pieces of code
    > within Gecko derive from the work you did in bug
    > 317375?
    No.
    > Or is this an ongoing effort of the core Gecko
    > hackers to make the code more
    > elegant/performant/easier to maintain?
    This is not part of anything big and organized. It's just something I ran into recently and have thought about in the past.
    > Why is it that many commits seem to go without a
    > bug number and without mentioning any reviews?
    > This seems true of Thebes especially. I'm
    > worried how many bugs (or bad practices) like
    > the ones you have mentioned here, go in to the
    > tree unnoticed...
    That is a real concern. We've been allowing review-less commits for new stuff that is not yet part of the build; the idea is that it'll get reviewed before it gets turned on. But review at that stage is too late and so unwieldy that no-one wants to do it; review guidance needs to be applied earlier to be effective. We need to fix this process. For Thebes, the situation is not so bad ... there's not a lot of Thebes code yet, and I have been looking at it from time to time and it looks OK. Much of the Thebes/cairo work is actually happening in cairo and that code eventually gets reviewed by the cairo people.

    ReplyDelete
  8. Robert O'Callahan11 February 2006 17:12

    BTW everyone who dislikes the SVG DOM needs to make their concerns clear to the SVG WG. It's too late to fix some of it, but they could make some improvements now or in later revisions and they need to know where they've gone wrong.

    ReplyDelete
  9. > Some issues are known, such as the cairo
    > tesselator being crappy, and I think they're being
    > worked on. But the resource I'm concerned about
    > here is space, not time, and I do not believe that
    > the cairo rendering backend is anywhere near as
    > greedy as the upper SVG code.
    Cairo's current clip via masking approach takes a fair bit of memory, and judging from the Quantify results of some content we've dealt with is likely the cause of one class of performance problems.

    ReplyDelete
  10. Interesting, I see the table in this post collide with the text on initial display (when the screen width is wide enough to contain 2 columns, not more), resizing a browser window immediately fixes it... another incremental reflow issue?
    Steps to reproduce :-/
    - resize the window with this blog post so it shows 3 columns
    - start to reduce the window size, stop when the content snaps into 2 columns
    - press reload
    - observe the table overflowing the text
    - resize the window, the text snaps back into its place from under the table

    ReplyDelete
  11. Interesting reading, all of this.
    I have to agree that Cairo is considerably slower than what is used now, not just for SVG.
    I guess I could make testcases for that, but aren't there already tests that keep track of that?

    ReplyDelete
  12. Robert O'Callahan11 February 2006 22:37

    > Cairo's current clip via masking approach takes a
    > fair bit of memory
    Only during actual painting, though. That's less serious.
    > and judging from the Quantify results of some
    > content we've dealt with is likely the cause of
    > one class of performance problems.
    Yep. I've also seen it suck up huge amounts of time. We avoid clip masking painting regular HTML content, but for SVG and transformed HTML we're going to need to fix this. I want to fix it inside cairo by painting to a temporary surface while clipping is in effect and then compositing the temporary surface under the clip mask back to the canvas in one go.

    ReplyDelete
  13. Robert O'Callahan11 February 2006 22:41

    kmike: yeah, I saw that. Someone should file a bug :-)
    Martijn: we have Trender/Tgfx tests to track and compare painting performance. Even in the last few days cairo build performance has improved significantly. I think the current numbers are that they're about 20% slower than non-cairo, on Windows. This is something people will be working on from now till the end of the year --- not just Mozilla people, but other users of cairo too.
    Although we have Trender/Tgfx tests, we could certainly use more tests, especially any that show really pathological behaviour of cairo vs non-cairo. If you can find anything like that, please file bugs.

    ReplyDelete
  14. > Why is it that many commits seem to go without a
    > bug number and without mentioning any reviews? This
    > seems true of Thebes especially. I'm worried how
    > many bugs (or bad practices) like the ones you have
    > mentioned here, go in to the tree unnoticed...
    upstream cairo checkins aside, vlad and I are pretty good at reviewing each others checkins even though the checkin comments don't always reflect that. I'll try to do better with including them in my checkins from now on though. Also there haven't been bugs filed for everything we've been working on as we've been working on very vast areas and changes. As we've been moving closer to landing, we've started filing more bugs and tried using them for checkins. We're doing a lot of constant review of Thebes and its surrounding code to try and keep the API clean, the code clean, and the code simple. We are reving the API and adding new things somewhat frequently, although we've slowed down recently.

    ReplyDelete
  15. Robert O'Callahan12 February 2006 01:05

    > The main use case that the SVG code was
    > originally implemented for (Crocodile
    > Mathematics) manipulates most SVG dynamically
    > from JS via the SVG DOM. Here tear-offs would
    > be counter-productive for performance.
    Actually, it's not clear this is true. It could well be that the cost of tear-offs would be lower that the penalty exacted by the bloaty architecture we have today, even for DOM-intensive apps like Crocodile Mathematics.

    ReplyDelete
  16. Peter Van der Beken12 February 2006 10:44

    Especially since XPConnect already caches tearoffs, so the only cost there is the creation of the tearoff. One can also cache them for C++ callers, but then you add bloat for the cache.

    ReplyDelete
  17. Congratulations, by using the magic word "bloat" you've just given more ammunition against Firefox and open source in general to the anti-opensource, Microsoft-whoring munchkins at zdnet and elsewhere....
    1372 bytes for a rectangle, O my God! I'm crying already. Specially since my Feb-2005 made, $1400 retail Gateway notebook came with 1 GIGABYTE of ram... and now I can't even run Firefox SVG because a rectangle takes 1372 *BYTES* (pun intended).
    Continue being so picky, and the Microsoft lovers in the media will have a field day. In the meantime Microsoft Office System 2003 is a 400+ MB hairball and I don't see you complaining about how much resources it takes.
    http://www.microsoft.com/office/editions/prodinfo/entreq.mspx
    "400 MB of available hard-disk space"
    JW

    ReplyDelete
  18. The last time I looked at the SVG code in mozilla there were a crapload of places that didn't check if allocation failed or not (I didn't even bother reporting it). From what I vaguely remember this was the GDI+ based SVG code, but I could be mistaken.

    ReplyDelete
  19. Robert O'Callahan20 February 2006 10:55

    JW: If I censored myself to avoid making statements that could be misinterpreted or misquoted by losers, I would never say anything.

    ReplyDelete
  20. Alex says, "don't use lots of objects if you don't plan to manipulate them via the DOM. Use s."
    Um, Alex, you're telling the user what kinds of SVG documents they get to display? You're telling the user, "Don't display that document, it uses objects! But you can display this document with everything artificially broken down into paths."
    Wow, I think you've hit on something really great here. We can use this on all Firefox bugs! Is PNG compositing broken? Just tell the user to not display PNGs! Preferences dialog unorganized? Tell the user to not open the preferences dialog!
    Alex, that's brilliant! Using this technique, you could close at least 3/4 of open firefox bugs by the end of the week. Let's get cracking!

    ReplyDelete
  21. For what it's worth: Firefox's SVG rendering is so slow as to be unusable with large SVG files (~1 MB). I have a project which would be perfectly suited for SVG, but I'm going to have to use something else, because Firefox simply can't handle it. I can't make users wait 20 seconds for the screen to redraw when they manipulate the SVG image.
    Anyone who thinks there aren't SERIOUS speed issues with the current SVG code and cairo is deluding themselves.

    ReplyDelete
  22. filed bug # 370974 re: layout issue exposed by this blog post

    ReplyDelete
  23. I realize this comment is rather late, but you do know that your rant merely reflects the horrible support for new mozilla developers, right?
    Internal documentation is arcane, and not only is there no obvious "new developer" intern process, the SOP of most established developers creates a false but very convincing image of a culture of utter hostility and apathy.
    The original SVG code was written by a person that wanted to get SVG working in mozilla. He asked but found no one with adequate knowledge willing to help him. He set off on his own, and finding no adequate documentation on mozilla internals, he had no option but to reverse engineer API's from some XPCOM code he found and understood.
    That's just a guess, of course, but it is how I had to write my first few chunks of code for mozilla, too.
    You have one of the hardest learning curves in open source (eg. linux kernel is somewhat worse), and your dev culture for newcomers has the initial feel of outright hostility.
    New developers do write COMtaminated code, but the only reason they would know not to do that is if they had made sure to find and read the handful of blog posts mocking wasteful XPCOM usage.
    Unrelated, but I was wondering: kids these day seem to use less punctation. Has that also been deprecated? Was there an official post at blog.grammar.org that explains the new standard?
    Thanks for your help.

    ReplyDelete
  24. What I’d like instead to see is a DOM-less SVG implementation; dump scripting, event handling, DOM manipulation, all of that junk. Not having to keep the DOM around would, I think, be a pretty big win for both memory usage and performance — you could transform the SVG markup representation into a more efficient form.

    ReplyDelete