Three Monkeys, Three Typewriters, Two Days

October 18, 2009

Performance vs correctness tradeoffs

I've recently been running into a number of "benchmarks" where some rendering engines achieve better performance by simply doing the wrong thing because the right one would be "too slow". Here's a good example:

    // FIXME: This check is good enough for :hover + foo, but it is not good enough for :hover + foo + bar.
    // For now we will just worry about the common case, since it's a lot trickier to get the second case right
    // without doing way too much re-resolution.

and here's a testcase demonstrating that in this particular open-source rendering engine performance in selector matching and dynamic change handling is achieved at the expense of correctness:

  <style>
    div { color: red; }
    .foo + div + div { color: green; }
  </style>
  <body onload="document.getElementsByTagName('div')[0].className = 'foo'">
    <div></div>
    <div></div>
    <div>Text</div>

This is not exactly an isolated incident; a number of the performance issues I've run into recently in Gecko have had to do with correctly handling edge cases that this particular open-source engine happens to just not handle. I guess it's easier to do well on tests if you cheat.

More interestingly, Opera's performance on this sort of thing is still quite good, and I have yet to discover them cheating...

Posted by bzbarsky at October 18, 2009 12:39 PM | TrackBack
Comments

That's not a particularly interesting example - I can't imagine anyone using it.

Is there a place where WebKit's (??) CSS deficiencies are documented? IIRC WebKit doesn't update styles when attributes change. That's a pain.

cheers,
Sean

Posted by: Sean Hogan on October 18, 2009 2:53 PM

Sean, what about:

.foo ~ div { color: green; }

? Can you imagine someone using that? That doesn't work either.

As for attributes... that certainly explains why I couldn't find it anywhere in their code! Again, only when the + or ~ combinator is involved, but that issue bites with even a single '+'.

Posted by: Boris on October 18, 2009 3:15 PM

You found a FIXME in the code and declare it cheating? Thats pathetic and dishonest.

Posted by: DeadlyNinja on October 18, 2009 3:41 PM

Ah, interesting that you bring this up, I was running into this very bug today and it’s been annoying me greatly. I’m not even sure how to work around it given my markup and other CSS.

Posted by: Kroc Camen on October 18, 2009 3:45 PM

DeadlyNinja, I call it cheating if you harp on about how fast your code is while it just does the wrong thing. No problem with having a FIXME; I've had plenty of those. Just a problem with then dishonestly marketing the code.

Posted by: Boris on October 18, 2009 3:54 PM

I have to agree with deadlyninja -- you're accusing people of a greater degree of mustache-twirling than you have shown good evidence for here.

Posted by: david on October 18, 2009 5:33 PM

Speaking of correctness, this form is broken, since this page is served as us-ascii, there is no accept-charset on the form, and the value of the submit button contains non-ascii nbsp.

Posted by: david on October 18, 2009 5:44 PM

Boris: Actually, I don't find sibling selectors particularly useful.

However:

div[title=Before] li { color: green; }

doesn't seem to work when "title" is updated (and presumably other attribute selectors too, however "class" and "id" are ok). I can think of a few scenarios where this capability would be useful.

I wonder why they don't just support them anyway. If there is a code-path for comprehensive support and optimized paths for the common cases (which is already implemented) how much would it slow down the browser?

Posted by: Sean Hogan on October 18, 2009 5:57 PM

This is silly. Does Mozilla close out all of their known bugs before making performance claims? No, the bug tracker is full of the same sorts of issues.

This whinging puts a really bad face on the Mozilla camp.

Posted by: Paul on October 18, 2009 6:04 PM

Paul, david, this didn't come out of nowhere. There was a particular testcase that was part of a "dom performance test" that I was debugging when I ran into that.

Posted by: Boris on October 18, 2009 6:23 PM

Paul, DeadlyNinja:

Correctness before performance is the proper ordering. A FIXME or bug noting poor performance would be acceptable; a FIXME noting an intentionally given flat-out wrong answer because a corner was cut improperly is another thing entirely.

Posted by: Jeff Walden on October 18, 2009 6:25 PM

david, good point. File a bug on wordpress?

Posted by: Boris on October 18, 2009 6:25 PM

I'm also not sure, DeadlyNinja, how it's dishonest to explicitly point out a FIXME as such, without any hint of dissembling. :-)

Posted by: Jeff Walden on October 18, 2009 6:35 PM

Come on Jeff, we all know performance is more important than correctness.

Paul: Unfixed bugs is one thing. Deliberately doing stuff incorrectly so you can be faster is another.

Posted by: Robert O'Callahan on October 18, 2009 6:40 PM

So this "particular open source rendering engine" optimizes for the common case in a particular piece of code, and you call it cheating? Accusing the WebKit project of cheating based on a FIXME is a pretty huge accusation to make.

Posted by: Preston on October 18, 2009 10:40 PM

Preston, there's a difference between optimizing for a particular common case (that is, making it faster while leaving rare cases slow) and giving incorrect answers in the uncommon cases to make the common case faster. The former is perfectly fine; the latter is what webkit is doing.

If you think the accusation of doing the latter is a huge deal, that's your business.

Posted by: Boris on October 18, 2009 10:54 PM

And to be clear, webkit is not the only browser engine that does this. Gecko has a similar issue with mutation events on style attributes, and I think that's equally bogus (and that we should drop support for DOMAttrModified instead).

Posted by: Boris on October 18, 2009 10:57 PM

I was going to respond to this, but I'm not even sure what to say. This particular FIXME Is just about a bug.

Our support for dynamic sibling selectors came along much later than Gecko's and still isn't fully formed. There's no deliberate "be fast at the expense of correctness" decision here. It's just not fully implemented.

Posted by: Dave Hyatt on October 19, 2009 9:42 AM

WebKit does update styles when attributes change.

Posted by: Dave Hyatt on October 19, 2009 9:45 AM

Boris, there's also a difference between a bug and a conspiracy to speed up benchmarks. Criticism of an implementation is one thing, but you went further and attributed malicious intent. There's just no evidence for you to make that claim, and finding a FIXME in under development code is not enough.

Posted by: Preston on October 19, 2009 11:33 AM

Preston, the comment says "we're doing this wrong so this code can be faster". To me it says precisely that the code is wrong on purpose so performance will be better. What do you take it to mean? Note that the comment has been there since March 2008 (so 18 months now); before that dynamic changes here were not handled at all. So it's only "under development" in the sense that the browser as a whole is. Safari 4 shipped with this code, in particular.

Dave, I'm not exactly looking for responses; though as I say above I can't see how there isn't a deliberate "fast at the expense of correctness" decision here, when the comment is precisely talking about such a decision.

Posted by: Boris on October 19, 2009 11:42 AM

Robert, I think we treat correctness as more important than performance in SpiderMonkey, to the extent that we have not written perf improvements that sometimes give wrong answers.

Posted by: Jeff Walden on October 19, 2009 12:01 PM

Boris, I'm just saying that I never looked at benchmarks or cared about benchmarks when adding this code. I held off on generalizing the code because I needed to think about a way to do it that would still be performant.

Our main concern with all of the dynamic selector code was that we not make the HTML5 spec unusable. It takes advantage of a lot of advanced selector stuff, and some of my initial checkins had such bad performance that they made that page really painful to load.

If we're faster on some benchmark purely because of this code, that's unfortunate I suppose, but it certainly wasn't any kind of deliberate decision.

If I had added the code, seen it slowed some benchmark down and then yanked it, that would be deliberate. However the code not having been added is just because I am trying to find out a way to do it that isn't completely awful. :)

Posted by: Dave Hyatt on October 19, 2009 12:08 PM

Also keep in mind that partial support is better than no support, and move you forward in terms of correctness. It's not like we went from being more correct to less correct with any of these checkins.

Posted by: Dave Hyatt on October 19, 2009 12:10 PM

Dave, "the HTML5 spec" is just as much a benchmark as Sunspider is, as far as the world at large is concerned. If I had a nickel for every snide comment I've gotten about how that page is slow to load in Gecko but fast in Safari... I'd probably have about $3 or so.

And I didn't say the checkin made your code less correct, by any means. I try to be pretty precise about what I'm saying and what I'm not saying; I basically stated facts: people are filing bugs on pages being slow in Gecko and fast in Webkit, and they're only slow in Gecko because it tries to behave correctly in the case Webkit punts on here.

Posted by: Boris on October 19, 2009 12:16 PM

Sure, although you understand what we're wrestling with then. By your own admission, those pages are slow in Gecko. That's what we're trying to avoid. We have a policy of not regressing performance of pages and so we run into that sometimes when adding new features.

When you have a browser that has shipped for years with no dynamic sibling selector support (Safari 3 and earlier) you can't just wreck the performance of pages like the HTML5 spec in an upgrade or you get yelled at by your users (believe me, people got pretty grumpy with me with some of the early checkins that started adding nth-child support, etc., and hurt the perf of that page).

I have some ideas as to how to add support for the general model without slowing things down, but it's complicated and that's why there's a followup bug filed about this issue in our bug database.

Posted by: Dave Hyatt on October 19, 2009 12:23 PM

Interesting discussion. And I suppose it would very from case to case whether you do things correctly or quickly... Correctness usually comes before quickness but I can imagine some cases where incorrectness is relatively unimportant or more likely that removal of a rarely used feature to save speed would be preferable to major speed decreases. I'm sure you get to have fun with these questions... being a user, I get no user complaints so I have a little less to worry about :)

Good luck on both your projects

Posted by: Fritz on October 19, 2009 1:48 PM

Boris:

"To me it says precisely that the code is wrong on purpose so performance will be better. What do you take it to mean?"

I take it to mean that it's incomplete code which performs well for the common case until the implementation is finished. It's labeled as a "FIXME" for a reason. For whatever reason, you're citing this as evidence that there's a conspiracy to cheat on benchmarks, and it appears that you'll not be persuaded otherwise.

Posted by: Preston on October 21, 2009 2:57 PM

Preston, I didn't say that there's a conspiracy. I just said that this is an example where the side effect is such that performance on benchmarks is better at the expense of correctness, and that in this particular case, the code is incorrect on purpose for performance reasons.

I also say that this is not the only case, in my performance testing, of cases where Webkit performs better than Gecko precisely in cases where Gecko's performance suffers due to dealing with correctness issues that Webkit just punts on.

If you want to perceive this as a conspiracy, that's your business. I see it as a difference in development philosophy, myself.

Posted by: Boris on October 21, 2009 3:06 PM

And to be even more precise, in the Gecko CSS implementation when an issue like this comes up the top priority is making the code correct, and if performance suffers a bit in some edge cases (and face it, the single-page HTML5 spec is an edge case), so be it.

Given Webkit's zero-tolerance performance regression policy they have no choice but to go the other way in case of such a conflict, with correctness suffering in ways that don't obviously break major sites but might well be causing grief to authors in general, as Sean and Kroc point out.

Note that Gecko has a policy that performance regressions are not tolerated, but an exception is made for cases where the old code was fast by just being wrong.

Posted by: Boris on October 21, 2009 3:12 PM

Yeah that's the difference. We don't make an exception for the old code being fast because it was wrong, especially if we shipped it to users already. We have to find a way to retain the speed while fixing the correctness issues.

Posted by: Dave Hyatt on October 21, 2009 3:41 PM

what they did was right and proper

if you ever want to ship code:
1) write for the easy most common case first
2) tweak performance, if needed
3) extend the code to handle edge cases as needed
4) tweak performance, if needed

this ordering also allows outside help to
jump in and make positive contributions, without
a steep learning curve

it's just a truism:

1) all code has bugs
2) no code handles all cases
3) code gets better over time (or at least it should)
4) eventualy all code rots and ends up in a landfill or that great big bit bucket up in the sky


Posted by: on October 27, 2009 6:15 PM

what they did was right and proper

if you ever want to ship code:
1) write for the easy most common case first
2) tweak performance, if needed
3) extend the code to handle edge cases as needed
4) tweak performance, if needed

this ordering also allows outside help to
jump in and make positive contributions, without
a steep learning curve

it's just a truism:

1) all code has bugs
2) no code handles all cases
3) code gets better over time (or at least it should)
4) eventualy all code rots and ends up in a landfill or that great big bit bucket up in the sky


Posted by: on October 27, 2009 6:17 PM

The problem is that there _was_ code to do the edge cases (which aren't even so edge, given the comments on this entry about authors running into the ensuing issues). And it was removed in the step 2 of your proposed algorithm.

I also think your truism list is wrong on point 2, and not applicable to this situation since the code to do the right thing _did_ exist and was deemed to not be worth the performance tradeoff.

Posted by: Boris on October 27, 2009 6:30 PM

It is pathetic this was even brought up.

To Mozilla: Suck it up, admit you are slow. Move on. Fix your shit. Ship it. Enjoy the fact that to sunk to a new low. Rise and repeat.

To WebKit: Just implement this. Make it fast. That way the Mozilla wankers will shut the fuck up until they dig up more dirt. Rise and repeat until you bury them in said dirt.

Posted by: on October 28, 2009 6:33 AM

It is pathetic this was even brought up.

To Mozilla: Suck it up, admit you are slow. Move on. Fix your shit. Ship it. Enjoy the fact that you sunk to a new low. Rise and repeat.

To WebKit: Just implement this. Make it fast. That way the Mozilla wankers will shut the fuck up until they dig up more dirt. Rise and repeat until you bury them in said dirt.

Posted by: Luke Fraser on October 28, 2009 6:37 AM

Luke, I look forward to webkit making this work correctly as much as you do.

I wonder why it's "pathetic" to discuss issues one runs into while developing a web browser. I also wonder how much you've done on the web browser development front lately.

Posted by: Boris on October 28, 2009 9:53 AM

Boris, no. The edge cases were never handled. No code was removed.

Posted by: Dave Hyatt on October 28, 2009 10:46 AM

I get why you sound a bit negative now. We never handled this generally. We never got this right. We did not ever remove some more general correct code for the sake of performance. The general cases never worked.

Posted by: Dave Hyatt on October 28, 2009 10:51 AM

Ah, ok. Your "October 19, 2009 12:08 PM" comment and the comment in the code certainly led me to believe otherwise.

Posted by: Boris on October 28, 2009 10:59 AM
Post a comment