Bug 100306 – Add non-virtual firstChild/lastChild overrides to RenderBlock and RenderTableCol for a > 30% speedup on table from bug 100304

• Status: RESOLVED
• Resolution: FIXED
• Component: New Bugs

[Eric Seidel (no email)]

Add non-virtual firstChild/lastChild overrides to RenderBlock and RenderTableCol for a > 30% speedup on table from bug 100304

[Eric Seidel (no email)]

Created attachment 170505 [details]
Patch

[Eric Seidel (no email)]

Created attachment 170518 [details]
Patch

[Emil A Eklund]

Nice! Does it benefit large tables with fewer tbodies as well?

[Eric Seidel (no email)]

It benefits any rendering code in a RenderBlock subclass which uses firstChild/lastChild in a hot code path.  RenderTable is one such example.  I don't know the effect on smaller tables, but I would not be surprised if this showed up in a variety of rendering benchmarks as a small win.

[Emil A Eklund]

(In reply to comment #4)
> It benefits any rendering code in a RenderBlock subclass which uses firstChild/lastChild in a hot code path.  RenderTable is one such example.  I don't know the effect on smaller tables, but I would not be surprised if this showed up in a variety of rendering benchmarks as a small win.

Right, I was curious if you've seen any performance improvements from this change in large tables with a single tbody or if it only applies to tables with multiple bodies.

[Eric Seidel (no email)]

The problem in bug 100304 seems to have little to do with it's many tbodies.  I was mistaken yesterday (if you heard my discussion in the office).

This method is hot because we call RenderTable::colElement() 4 times for every cell.  The first thing that method does is call firstColumn() which calls firstChild().

So we end up calling firstChild a lot. :)  We'll do that for any table with lots of cells, regardless of the number of tbodies.  I haven't yet, but I can run this against https://github.com/dglazkov/performance-tests and I expect we'll see some small win.

[Eric Seidel (no email)]

Actually, I believe dglazkov's tests do not have columns and thus go down the fast-path which avoids the firstChild call all together.

[Elliott Sprehn]

Comment on attachment 170518 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=170518&action=review

> Source/WebCore/rendering/RenderObject.h:184
> +    // functions to make these fast when we already have a more specific poitner type.

typo: poitner

[Julien Chaffraix]

The part of this change that makes me sad is that it assumes you have properly downcasted your object (ie RenderBlock treated as RenderObject will miss the mark :-/). Thus this really feels like a fragile effort to work around our current design.

We should think of a good way to avoid the bad / slow pattern instead of assuming that it is going to stay and that we should make it fast. As a whole, I don't think the whole children()->firstChild() vs firstChild() performance impacts are that well known among people (or it is super easy to forget the cost which is why something _enforceable_ would be nice). This is obviously a long term goal, not sure if it's possible to tackle it as part of this change.

A more manageable action item is to add some ASSERT to this change that catches if we start calling back into RenderObject's firstChild / lastChild, like using some debug-only flag.

[Eric Seidel (no email)]

(In reply to comment #9)
> The part of this change that makes me sad is that it assumes you have properly downcasted your object (ie RenderBlock treated as RenderObject will miss the mark :-/). Thus this really feels like a fragile effort to work around our current design.

Correct.  Our current design, of making RenderObject have a firstChild method, w/o storing the actual child pointers (or have a single RenderChildren subclass to cast to), makes it so that firstChild, etc. must cost a virtual dispatch.

This is a transparent solution which allows primarily classes which *already* know that they are a RenderBlock subclass to use firstChild/lastChild w/o thinking about it.  Code which deals with RenderObjects (which I'm not interested in atm) still must take the virtual dispatch hit.

One way to make this less "fragile" would be to rename RenderObject::firstChild to slowFirstChild or something to make it explicit that it's slow.

I think the main trouble we have here is that those who work on both the DOM and rendering, don't necessarily remember when moving to rendering that firstChild is slow.

> We should think of a good way to avoid the bad / slow pattern instead of assuming that it is going to stay and that we should make it fast. As a whole, I don't think the whole children()->firstChild() vs firstChild() performance impacts are that well known among people (or it is super easy to forget the cost which is why something _enforceable_ would be nice). This is obviously a long term goal, not sure if it's possible to tackle it as part of this change.

I don't see any way to avoid virtual dispatch if RenderObject isn't going to contain the child pointers.

But, as I noted in the FIXME, we certainly could make the cost more obvious by renaming RenderObject::firstChild.  I decided that would be too big a change for this patch (which I assumed would generate some small amount of discussion).

> A more manageable action item is to add some ASSERT to this change that catches if we start calling back into RenderObject's firstChild / lastChild, like using some debug-only flag.

I don't think that's possible.  There are some sections of code which do tree-traversal, and don't know the type of the object.  ASSERTing if we called the RenderObject::firstChild would require all callers to check the type of the object before calling firstChild, which would defeat the purpose of firstChild being on RenderObject in the first place. :)

I think this is a good, short-term mediation of this problem, with the possibility of expanding deployment of these fast firstChild methods and/or renaming RenderObject::firstChild in the longer-term.

[Abhishek Arya]

Comment on attachment 170518 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=170518&action=review

> Source/WebCore/rendering/RenderBlock.h:89
> +    RenderObject* firstChild() const { ASSERT(children() == virtualChildren()); return children()->firstChild(); }

Probably add a comment here so that someone does not remove them in future without understanding the loss. Also, this function will look a little better 2 lines below after children() function definition. The assert is pretty useless i think since virtualChildren is just used to reference from RenderObject, i dont think there can be a case where children() != virtualChildren()

>> Source/WebCore/rendering/RenderObject.h:184
>> +    // functions to make these fast when we already have a more specific poitner type.
> 
> typo: poitner

typo: poitner

[Tony Chang]

Comment on attachment 170518 [details]
Patch

Eric explained this to me and it seems safe.  It's a bit unconventional, but I think that's fine because most functions aren't as hot as these.

I wasn't super excited by the naming since it's not obvious why the methods are slow.  Renaming virtualChildren, RenderObject::firstChild and RenderObject::lastChild to something more clear sounds useful to me.

[Julien Chaffraix]

Comment on attachment 170518 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=170518&action=review

> I don't think that's possible.  There are some sections of code which do tree-traversal, and don't know the type of the object.  ASSERTing if we called the RenderObject::firstChild would require all callers to check the type of the object before calling firstChild, which would defeat the purpose of firstChild being on RenderObject in the first place. :)

There may be some clever trick to catch that (using template) but I agree, it may not buy us much.

> I think this is a good, short-term mediation of this problem, with the possibility of expanding deployment of these fast firstChild methods and/or renaming RenderObject::firstChild in the longer-term.

Fair enough. I still think the change is extremely fragile but the  performance implications are compelling enough that I won't block it. We should definitely track firstChild -> slowFirstChild renaming and globally making cheaper to iterate over children.

> Source/WebCore/ChangeLog:28
> +

I would advocate to land this pattern on all objects that have overridden virtualChildren() instead of just the one you spotted in your testing. This means that the following classes would need to be modified: RenderMedia, RenderFrameSet, RenderInline, RenderTableRow and RenderTableSection.

[Eric Seidel (no email)]

(In reply to comment #13)
> (From update of attachment 170518 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=170518&action=review
> I would advocate to land this pattern on all objects that have overridden virtualChildren() instead of just the one you spotted in your testing. This means that the following classes would need to be modified: RenderMedia, RenderFrameSet, RenderInline, RenderTableRow and RenderTableSection.

That's fine.  My goal was to limit the scope of this change as much as possible.

If I were to do that, would you suggest I override all 4 methods which use virtualChildren?
http://trac.webkit.org/browser/trunk/Source/WebCore/rendering/RenderObject.h#L181

It seemed like firstChild is really the only commonly used of the 4.

[Julien Chaffraix]

> If I were to do that, would you suggest I override all 4 methods which use virtualChildren?
> http://trac.webkit.org/browser/trunk/Source/WebCore/rendering/RenderObject.h#L181
> 
> It seemed like firstChild is really the only commonly used of the 4.

Not really, as you are pointing out, some functions are more popular and thus it's not worth the time / maintenance cost extending this hack to more than just firstChild / lastChild.

[Eric Seidel (no email)]

Created attachment 171589 [details]
Patch for landing

[Eric Seidel (no email)]

Hopefully I addressed everyones' comments.  Let me know and I'm happy to make follow-up patches.

We should also go back and remove many of the children().firstChild() callers now that firstChild() is fast when you know your own type. :)

[WebKit Review Bot]

Comment on attachment 171589 [details]
Patch for landing

Clearing flags on attachment: 171589

Committed r132995: <http://trac.webkit.org/changeset/132995>

[WebKit Review Bot]

All reviewed patches have been landed.  Closing bug.

[Darin Adler]

Comment on attachment 171589 [details]
Patch for landing

This is a fantastic improvement, but I also think we should ponder a way to accomplish this without so much copied and pasted code.

[Eric Seidel (no email)]

(In reply to comment #20)
> (From update of attachment 171589 [details])
> This is a fantastic improvement, but I also think we should ponder a way to accomplish this without so much copied and pasted code.

I fully support this idea!