Bug 64546 - Redrawing dirty parts of a large table is very slow
Summary: Redrawing dirty parts of a large table is very slow
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: Layout and Rendering (show other bugs)
Version: 528+ (Nightly build)
Hardware: Unspecified Unspecified
: P2 Normal
Assignee: Nobody
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2011-07-14 12:10 PDT by Philip Rogers
Modified: 2011-09-23 12:55 PDT (History)
7 users (show)

See Also:


Attachments
Test case of slow table rendering (2.50 MB, text/html)
2011-07-14 12:10 PDT, Philip Rogers
no flags Details
Speedtracer info (78.31 KB, image/png)
2011-07-14 12:35 PDT, Philip Rogers
no flags Details
Changes and tests. (98.18 KB, patch)
2011-09-06 11:30 PDT, Konstantin Shcheglov
no flags Details | Formatted Diff | Diff
Changes and tests. (98.18 KB, patch)
2011-09-06 11:36 PDT, Konstantin Shcheglov
sam: review-
Details | Formatted Diff | Diff
Updated patch with fixes for review comments (98.29 KB, patch)
2011-09-07 07:07 PDT, Konstantin Shcheglov
no flags Details | Formatted Diff | Diff
Updated patch with fixes for review comments (98.28 KB, patch)
2011-09-07 07:16 PDT, Konstantin Shcheglov
no flags Details | Formatted Diff | Diff
Changes for review comments (68.25 KB, patch)
2011-09-08 11:26 PDT, Konstantin Shcheglov
no flags Details | Formatted Diff | Diff
Changes for review comments (68.33 KB, patch)
2011-09-09 07:55 PDT, Konstantin Shcheglov
hyatt: review-
Details | Formatted Diff | Diff
Changes for review comments (67.34 KB, patch)
2011-09-15 13:06 PDT, Konstantin Shcheglov
hyatt: review-
Details | Formatted Diff | Diff
Use better need*Layout() checks. New test with positioned block child. (71.28 KB, patch)
2011-09-21 11:49 PDT, Konstantin Shcheglov
hyatt: review+
scheglov: commit-queue?
Details | Formatted Diff | Diff
Patch for landing (73.92 KB, patch)
2011-09-23 11:48 PDT, Konstantin Shcheglov
webkit.review.bot: commit-queue-
Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Philip Rogers 2011-07-14 12:10:05 PDT
Created attachment 100837 [details]
Test case of slow table rendering

In a spreadsheet application we hit a performance issue when moving an absolutely positioned div over a large table. The time to redraw the dirty area of the table takes longer for larger tables, and even moderately sized tables of a few hundred rows will have unacceptably bad lag when a box is moved over top of it.

I created a small test case (see attached) displaying this issue:
On the left is a 10,000 row table, and on the right is 1,000 tables with 10 rows each. Moving the mouse over the left table, the box will lag by ~1s but moving it over the right table(s) is instantaneous.
Comment 1 Philip Rogers 2011-07-14 12:35:41 PDT
Created attachment 100843 [details]
Speedtracer info

Adding a screenshot showing the speedtracer log when moving the mouse over the large green table; all the time is taken in Paint.
Comment 2 Julien Chaffraix 2011-08-29 17:50:29 PDT
Seems to be caused "border-collapse: collapse" as WebKit will recompute the borders every time you paint (which is expensive as you can see). If you remove that property, the painting is more smooth.

This bug is likely a duplicate of bug 38810.
Comment 3 Konstantin Shcheglov 2011-08-31 13:40:59 PDT
I'd like to fix this bug.

So, we should cache calculated collapsed borders.
However they depend on many styles - cells, rows, row groups, etc.
How can we track all these dependencies to clear cache?

One possible approach is listening styleDidChange() in every cell, row,  etc and notify parent table that cache become invalid. Plus do same for addChild() and removeChild(). 

What do you think?

Any alternative ideas how to solve this?
Comment 4 Julien Chaffraix 2011-08-31 14:11:36 PDT
(CC'ing dhyatt as he is the table expert)

> One possible approach is listening styleDidChange() in every cell, row,  etc and notify parent table that cache become invalid. Plus do same for addChild() and removeChild(). 

It's extremely complicated to do it this way as there are cross-dependencies:
* a cell changing its border style would (potentially) impact all the surrounding cells.
* a table changing its border may impact all or some cells.
* ...

> What do you think?

You will have to watch for memory explosion as tables are already using a lot of memory (see bug 23193). One problem is that we don't know the usage of "border-collapse" in the wild to know if it is worth the investment for each cell (likely not but we have no clue).

Also our table coverage is less than perfect: I tested some simple caching schemes that showed very promising improvements but were completely wrong and yet our tests only caught some the badness.

> Any alternative ideas how to solve this?

Another (likely better) way would be to recompute them at layout time. There may be ways to mitigate the re-computations but I haven't thought about it enough.
Comment 5 Konstantin Shcheglov 2011-09-02 15:21:36 PDT
I've implemented recomputing collapsed borders during layout(), however I found that this breaks fast/repaint/table-collapsed-border.html test. As I understand, problem is that this test forces repaint without layout, so we don't recompute borders. I was able to reproduce this just by delaying border color change using setTimeout(), because I can not use display() just in browser, outside of tests.

Moreover, it seems that may be cached information references invalid objects, because it does not paint border even using previous color, it becomes just transparent.

So... May be we still have to track all changes in styles of elements which may have effect on cached borders: BOFF, BTABLE, BCOLGROUP, BCOL, BROWGROUP, BROW, BCELL. Probably more-less like now RenderTableCell tracks specific changes and performs invalidate actions.


void RenderTableCell::styleWillChange(StyleDifference diff, const RenderStyle* newStyle)
{
    if (parent() && section() && style() && style()->height() != newStyle->height())
        section()->setNeedsCellRecalc();

Objections?
Better ideas?
Comment 6 Konstantin Shcheglov 2011-09-06 11:30:00 PDT
Created attachment 106451 [details]
Changes and tests.
Comment 7 WebKit Review Bot 2011-09-06 11:33:27 PDT
Attachment 106451 [details] did not pass style-queue:

Failed to run "['Tools/Scripts/check-webkit-style', '--diff-files', u'LayoutTests/ChangeLog', u'LayoutTests/fast..." exit_code: 1

Source/WebCore/rendering/RenderTableSection.h:122:  The parameter name "diff" adds no information, so it should be removed.  [readability/parameter_name] [5]
Total errors found: 1 in 40 files


If any of these errors are false positives, please file a bug against check-webkit-style.
Comment 8 Konstantin Shcheglov 2011-09-06 11:36:35 PDT
Created attachment 106453 [details]
Changes and tests.
Comment 9 Eric Seidel (no email) 2011-09-06 17:03:07 PDT
I'm not sure who our table expert is, but I suspect Beth or Adele know more about them than I.
Comment 10 Sam Weinig 2011-09-06 18:42:31 PDT
Comment on attachment 106453 [details]
Changes and tests.

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

> Source/WebCore/rendering/RenderTable.cpp:434
> +    if (!m_collapsedBordersValid) {
> +        m_collapsedBordersValid = true;

This should use an early return.

> Source/WebCore/rendering/RenderTable.h:263
> +    CollapsedBorderValues m_collapsedBorders;

This seems like it is making all RenderTables much much bigger (sizeof(CollapsedBorderValues) * 100).  Why is that ok?

> Source/WebCore/rendering/RenderTableCol.cpp:50
> +    if (table() && style() && style()->border() != newStyle->border())
> +            table()->invalidateCollapsedBorders();

The indentation is wrong here.

> Source/WebCore/rendering/RenderTableSection.cpp:83
> +    if (table() && style() && style()->border() != newStyle->border())
> +            table()->invalidateCollapsedBorders();

The indentation is wrong here.
Comment 11 Konstantin Shcheglov 2011-09-07 07:07:57 PDT
Created attachment 106580 [details]
Updated patch with fixes for review comments
Comment 12 WebKit Review Bot 2011-09-07 07:11:26 PDT
Attachment 106580 [details] did not pass style-queue:

Failed to run "['Tools/Scripts/check-webkit-style', '--diff-files', u'LayoutTests/ChangeLog', u'LayoutTests/fast..." exit_code: 1

Source/WebCore/rendering/RenderTable.cpp:435:  One line control clauses should not use braces.  [whitespace/braces] [4]
Total errors found: 1 in 40 files


If any of these errors are false positives, please file a bug against check-webkit-style.
Comment 13 Konstantin Shcheglov 2011-09-07 07:16:25 PDT
Created attachment 106582 [details]
Updated patch with fixes for review comments
Comment 14 Eric Seidel (no email) 2011-09-07 11:36:34 PDT
Comment on attachment 106582 [details]
Updated patch with fixes for review comments

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

The change looks sane (and well tested) to me, but I know very little about our table code. I'm willing to approve it if no one comments within the next couple of days, but I would like to leave the table authors adequate time to say something.

> Source/WebCore/rendering/RenderTable.cpp:440
> +        if (o->isTableCell())
> +            toRenderTableCell(o)->collectBorderValues(m_collapsedBorders);

If these only come from TableCells why do we need to invalidate them from columns and sections?
Comment 15 Julien Chaffraix 2011-09-07 11:44:38 PDT
Comment on attachment 106582 [details]
Updated patch with fixes for review comments

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

Your tests should be self-explanatory (look at some other tests for reference). There is no way for people to know if your tests is passing or failing as there is no explanation as to what you are expecting.

> LayoutTests/fast/table/border-collapsing/cached-cell-append.html:10
> +                // do change

This comment does not add anything in any of the tests. It should be removed.

> LayoutTests/fast/table/border-collapsing/cached-cell-append.html:23
> +                <td style="border:4px solid lime">foo</td>

This text does not add anything. It has also the downside of making your tests platform specific due to font differences.

I think you should remove the text and just set up the width / height explicitly. Hoisting the CSS into a common style sheet would also be nice.

> Source/WebCore/ChangeLog:5
> +        Invalidate cache when cell, row, row group, col, col group or table border it changed.

This goes after the bug description / id or it will likely confuse our tools.

> Source/WebCore/ChangeLog:50
> +        * rendering/style/CollapsedBorderValue.h:

It is nice to detail here the different changes you made to the different files so that people can follow what happened.

> Source/WebCore/rendering/RenderTable.cpp:-510
> -        // from lowest precedence to highest precedence.

You split this comment but missed out part of it which would be neat to keep.

> Source/WebCore/rendering/RenderTable.cpp:536
> +        recalcCollapsedBorders();

Your use case is repainting. However it means that querying border on a border-collapsing table is still slow and will still be after your change. Maybe there is something we could do to avoid that too as we are keeping the borders here anyway. If we can also improve querying the border values through JS, then we could also write a performance test to check that we don't regress performance.

I would also be interested in some numbers as to the improvement you are seeing with this change.

> Source/WebCore/rendering/RenderTable.h:263
> +    CollapsedBorderValues m_collapsedBorders;

We are expanding the size of RenderTable for every type of tables regardless of whether "border-collapse" was defined. I would better see a trade-off where we either introduce a rare map (like for Node or Element) or just a pointer placeholder that lazily gets filled when we really need the CollapsedBorderValues. The choice depends on the distribution of border-collapse value in the wild but at least it should be defined why it is fine to one way or another (as Sam pointed out).

> Source/WebCore/rendering/style/CollapsedBorderValue.h:71
> +typedef Vector<CollapsedBorderValue> CollapsedBorderValues;

I don't see why you removed RenderTableCell::CollapsedBorderStyles and replaced it with that. If it is to avoid blowing off RenderTable memory, it is a wrong change (not to mention that adding it here is definitely not the right place).
Comment 16 Konstantin Shcheglov 2011-09-07 12:42:28 PDT
(In reply to comment #15)
> (From update of attachment 106582 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=106582&action=review
> 
> Your tests should be self-explanatory (look at some other tests for reference). There is no way for people to know if your tests is passing or failing as there is no explanation as to what you are expecting.

  I've looked on LayoutTests/fast/table/border-collapsing/002.html and other tests in same folder.
  Some of them have some description, some - not.
  Actually each test has description, for example:
<!-- Invalidate cache: when we change colgroup border color. -->
  Is it not good enough?
  What if I will improve it to say something like this?
---
Calculating collapsed borders for big tables in expensive, so we cache them and recalculate when needed.
Here we change colgroup border color and test that cache is invalidated and painted table has border with correct color.
---


> 
> > LayoutTests/fast/table/border-collapsing/cached-cell-append.html:10
> > +                // do change
> 
> This comment does not add anything in any of the tests. It should be removed.

  OK

  I've used to add many comments, sometimes just to split code into logical sections.
  But if having such sections is against of WebKit code style, I can live without them.

  Returning from Java to C++ I see with sorrow that C++ code has almost no comments and almost everything should be deduced from name, usage, etc.


> 
> > LayoutTests/fast/table/border-collapsing/cached-cell-append.html:23
> > +                <td style="border:4px solid lime">foo</td>
> 
> This text does not add anything. It has also the downside of making your tests platform specific due to font differences.
> 
> I think you should remove the text and just set up the width / height explicitly. Hoisting the CSS into a common style sheet would also be nice.

  Aha!
  Thanks.


> 
> > Source/WebCore/ChangeLog:5
> > +        Invalidate cache when cell, row, row group, col, col group or table border it changed.
> 
> This goes after the bug description / id or it will likely confuse our tools.

  OK


> 
> > Source/WebCore/ChangeLog:50
> > +        * rendering/style/CollapsedBorderValue.h:
> 
> It is nice to detail here the different changes you made to the different files so that people can follow what happened.

  OK


> 
> > Source/WebCore/rendering/RenderTable.cpp:-510
> > -        // from lowest precedence to highest precedence.
> 
> You split this comment but missed out part of it which would be neat to keep.

  Sorry, I don't understand which part to keep.
  "from lowest precedence to highest precedence" is included.


> 
> > Source/WebCore/rendering/RenderTable.cpp:536
> > +        recalcCollapsedBorders();
> 
> Your use case is repainting. However it means that querying border on a border-collapsing table is still slow and will still be after your change. Maybe there is something we could do to avoid that too as we are keeping the borders here anyway. If we can also improve querying the border values through JS, then we could also write a performance test to check that we don't regress performance.

  Hm...
  I don't see other invocations of RenderTableCell::collectBorderValues() than from RenderTable.
  RenderTableCell::collapsedStartBorder() is also called only from RenderTableCell during paint.

  Well, probably I just don't know some trick how it is accessed from JS.
  Can you give me hint?
  Is there way to get collapsed border values in JS?


> 
> I would also be interested in some numbers as to the improvement you are seeing with this change.

  Is there any known way to test performance?
  Something like get start thread CPU time, request 10 repaints, calculate time difference and ensure that it is faster than some reasonable time?

  For provided test case performance is visible to the unaided eye, probably tens times faster.


> 
> > Source/WebCore/rendering/RenderTable.h:263
> > +    CollapsedBorderValues m_collapsedBorders;
> 
> We are expanding the size of RenderTable for every type of tables regardless of whether "border-collapse" was defined. I would better see a trade-off where we either introduce a rare map (like for Node or Element) or just a pointer placeholder that lazily gets filled when we really need the CollapsedBorderValues. The choice depends on the distribution of border-collapse value in the wild but at least it should be defined why it is fine to one way or another (as Sam pointed out).

  If table does not use collapsed borders, then we use memory only for empty Vector; I don't know exact memory footprint (how to check this?), but in theory this can be as small as two ints (capacity and size) plus pointer. Is it worth optimizing?


> 
> > Source/WebCore/rendering/style/CollapsedBorderValue.h:71
> > +typedef Vector<CollapsedBorderValue> CollapsedBorderValues;
> 
> I don't see why you removed RenderTableCell::CollapsedBorderStyles and replaced it with that. If it is to avoid blowing off RenderTable memory, it is a wrong change (not to mention that adding it here is definitely not the right place).

  To avoid bigger memory consumption I did change suggested by Sam - removed size 100 for Vector.

  Actual reason for moving CollapsedBorderStyles from RenderTableCell is that I can not use it in RenderTable.h, because I can not forward declare it.
  Well, at least I don't know how to do this. See also
  http://stackoverflow.com/questions/2600385/c-nested-class-forward-declaration-issue

  Should I move CollapsedBorderValues into RenderTable.h instead?
Comment 17 Konstantin Shcheglov 2011-09-07 12:46:15 PDT
 
> > Source/WebCore/rendering/RenderTable.cpp:440
> > +        if (o->isTableCell())
> > +            toRenderTableCell(o)->collectBorderValues(m_collapsedBorders);
> 
> If these only come from TableCells why do we need to invalidate them from columns and sections?

  RenderTableCell talks with columns and section itself inside of this method.
Comment 18 Julien Chaffraix 2011-09-07 14:00:28 PDT
Comment on attachment 106582 [details]
Updated patch with fixes for review comments

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

>>> LayoutTests/fast/table/border-collapsing/cached-cell-append.html:10
>>> +                // do change
>> 
>> This comment does not add anything in any of the tests. It should be removed.
> 
> OK
> 
>   I've used to add many comments, sometimes just to split code into logical sections.
>   But if having such sections is against of WebKit code style, I can live without them.
> 
>   Returning from Java to C++ I see with sorrow that C++ code has almost no comments and almost everything should be deduced from name, usage, etc.

Note that WebKit style has nothing against comments.

We value important comments. However we usually prefer comments about the 'why' rather than the 'what'. The latter should be clear from the code (and if it is not, then a comment is totally welcome but it is a bad sign).

>>> Source/WebCore/rendering/RenderTable.cpp:-510
>>> -        // from lowest precedence to highest precedence.
>> 
>> You split this comment but missed out part of it which would be neat to keep.
> 
> Sorry, I don't understand which part to keep.
>   "from lowest precedence to highest precedence" is included.

I was hinting at the middle "Once we have all the style sorted, we then do individual passes." Even if you kept the gist of the comment, I found that this part helped understand the articulation between the 2 parts you split.
How about for the following comment:

// Using our cached sorted styles, we then do individual passes, painting each style of border from lowest precedence to highest precedence.

>>> Source/WebCore/rendering/RenderTable.cpp:536
>>> +        recalcCollapsedBorders();
>> 
>> Your use case is repainting. However it means that querying border on a border-collapsing table is still slow and will still be after your change. Maybe there is something we could do to avoid that too as we are keeping the borders here anyway. If we can also improve querying the border values through JS, then we could also write a performance test to check that we don't regress performance.
>> 
>> I would also be interested in some numbers as to the improvement you are seeing with this change.
> 
> Hm...
>   I don't see other invocations of RenderTableCell::collectBorderValues() than from RenderTable.
>   RenderTableCell::collapsedStartBorder() is also called only from RenderTableCell during paint.
> 
>   Well, probably I just don't know some trick how it is accessed from JS.
>   Can you give me hint?
>   Is there way to get collapsed border values in JS?

Sure, here is how you can access the border value through JS:

var cell = document.getElementById('thisCell');
getComputedStyle(cell, '').borderLeftWidth

Maybe more importantly, all the virtual border* method on RenderTableCell will still trigger a recomputation and completely miss the cache. The invocations of those function are spread in the rendering code but they are nevertheless important.

>>> Source/WebCore/rendering/RenderTable.h:263
>>> +    CollapsedBorderValues m_collapsedBorders;
>> 
>> We are expanding the size of RenderTable for every type of tables regardless of whether "border-collapse" was defined. I would better see a trade-off where we either introduce a rare map (like for Node or Element) or just a pointer placeholder that lazily gets filled when we really need the CollapsedBorderValues. The choice depends on the distribution of border-collapse value in the wild but at least it should be defined why it is fine to one way or another (as Sam pointed out).
> 
> If table does not use collapsed borders, then we use memory only for empty Vector; I don't know exact memory footprint (how to check this?), but in theory this can be as small as two ints (capacity and size) plus pointer. Is it worth optimizing?

Ah, sorry about that, I thought the Vector's did have a default size of 16, not 0. Just discard what I said.

>>> Source/WebCore/rendering/style/CollapsedBorderValue.h:71
>>> +typedef Vector<CollapsedBorderValue> CollapsedBorderValues;
>> 
>> I don't see why you removed RenderTableCell::CollapsedBorderStyles and replaced it with that. If it is to avoid blowing off RenderTable memory, it is a wrong change (not to mention that adding it here is definitely not the right place).
> 
> To avoid bigger memory consumption I did change suggested by Sam - removed size 100 for Vector.
> 
>   Actual reason for moving CollapsedBorderStyles from RenderTableCell is that I can not use it in RenderTable.h, because I can not forward declare it.
>   Well, at least I don't know how to do this. See also
>   http://stackoverflow.com/questions/2600385/c-nested-class-forward-declaration-issue
> 
>   Should I move CollapsedBorderValues into RenderTable.h instead?

About CollapsedBorderStyles, you can move it to RenderTable.h. It looks like part of your problem arise from the fact that RenderTableCell / RenderTableSection are doing unneeded #include and could use some forward-declarations. You could redefine the symbol if moving is proving problematic but I think you would need to solve the #include issue then.

I feared setting the size to 0 in CollapsedBorderValues would actually hurt other use cases: when you *do* need to collect borders, you can easily need 100 entries in your Vector. 100 entries is only 25 cells (4 borders per cell). You could mitigate that by pre-allocating the Vector before collecting your borders as you can estimate the size needed.
Comment 19 Konstantin Shcheglov 2011-09-08 10:26:00 PDT

> I was hinting at the middle "Once we have all the style sorted, we then do individual passes." Even if you kept the gist of the comment, I found that this part helped understand the articulation between the 2 parts you split.
> How about for the following comment:
> 
> // Using our cached sorted styles, we then do individual passes, painting each style of border from lowest precedence to highest precedence.

  OK


> >   Well, probably I just don't know some trick how it is accessed from JS.
> >   Can you give me hint?
> >   Is there way to get collapsed border values in JS?
> 
> Sure, here is how you can access the border value through JS:
> 
> var cell = document.getElementById('thisCell');
> getComputedStyle(cell, '').borderLeftWidth

  I don't observe that in JS you access collapsed border values.
  I think that collapsed borders are paint/presentation feature instead of style feature.

    <body onload="test()">
        <table style="border-collapse:collapse; border:2px solid blue">
            <tr>
                <td style="border:4px solid lime" id="foo"/>
                <td style="border-left:6px solid yellow" id="bar"/>
                <td/>
            </tr>
        </table>
        <div id="console"/>
    </body>

            function test() {
                fooCell = document.getElementById("foo");
                barCell = document.getElementById("bar");
                log("foo borderRightWidth: " + getComputedStyle(fooCell, '').borderRightWidth);
                log("bar borderLeftWidth: " + getComputedStyle(barCell, '').borderLeftWidth);
            }

      RenderBlock {DIV} at (0,70) size 784x56
        RenderBlock {P} at (0,0) size 784x20
          RenderText {#text} at (0,0) size 163x19
            text run at (0,0) width 163: "foo borderRightWidth: 4px"
        RenderBlock {P} at (0,36) size 784x20
          RenderText {#text} at (0,0) size 156x19
            text run at (0,0) width 156: "bar borderLeftWidth: 6px"




> Maybe more importantly, all the virtual border* method on RenderTableCell will still trigger a recomputation and completely miss the cache. The invocations of those function are spread in the rendering code but they are nevertheless important.

  RenderTable.paintObject() asks every RenderTableCell about its collapsed border, so if table is huge, this takes a lot of time.
  In contrast RenderTableCell talks only with its direct parents and siblings.
  Single RenderTableCell::collapsedStartBorder() method requires about 1/1000 ms on my computer.

  Only place where this is important is table loading, this calls border*() methods hundreds thousands times.
  For test case replacing collapsed*Border() with NOP reduces reload time from 4500ms to 2900ms.
  As I can see, this happens because of periodical re-parsing and re-layout during loading.
  No sure however what part of test case causes this - single table with 10000 rows or 1000 tables with 10 rows.
  So, it seems that it worth optimization.

  Can we however do this in separate bug?
  RenderTable.paintObject() still worth optimization to avoid visiting every cell on each paint.


> >   Should I move CollapsedBorderValues into RenderTable.h instead?
> 
> About CollapsedBorderStyles, you can move it to RenderTable.h. It looks like part of your problem arise from the fact that RenderTableCell / RenderTableSection are doing unneeded #include and could use some forward-declarations. You could redefine the symbol if moving is proving problematic but I think you would need to solve the #include issue then.

  Unfortunately with forward declarations we can almost do the trick, but we loose ability to inline toRenderTable(), which is declared in RenderTable.h.
  So, I end up moving CollapsedBorderValues as inner class of RenderTable.


> I feared setting the size to 0 in CollapsedBorderValues would actually hurt other use cases: when you *do* need to collect borders, you can easily need 100 entries in your Vector. 100 entries is only 25 cells (4 borders per cell). You could mitigate that by pre-allocating the Vector before collecting your borders as you can estimate the size needed.

  As I can see, even for huge table CollapsedBorderValues contains only 2 elements, because we remember only unique CollapsedBorderValue objects.
Comment 20 Konstantin Shcheglov 2011-09-08 11:26:43 PDT
Created attachment 106766 [details]
Changes for review comments

1. Tests without text.
2. Tests comments.
3. CollapsedBorderValues in RenderTable.h
Comment 21 Konstantin Shcheglov 2011-09-09 07:55:58 PDT
Created attachment 106870 [details]
Changes for review comments
Comment 22 Julien Chaffraix 2011-09-09 10:40:53 PDT
(In reply to comment #19)
> > >   Well, probably I just don't know some trick how it is accessed from JS.
> > >   Can you give me hint?
> > >   Is there way to get collapsed border values in JS?
> > 
> > Sure, here is how you can access the border value through JS:
> > 
> > var cell = document.getElementById('thisCell');
> > getComputedStyle(cell, '').borderLeftWidth
> 
>   I don't observe that in JS you access collapsed border values.
>   I think that collapsed borders are paint/presentation feature instead of style feature.

I am not sure why you are making some distinction here. getComputedStyle should return the computed value for the property. borderLeftWidth is a layout value which is derived from the different style properties.

>     <body onload="test()">
>         <table style="border-collapse:collapse; border:2px solid blue">
>             <tr>
>                 <td style="border:4px solid lime" id="foo"/>
>                 <td style="border-left:6px solid yellow" id="bar"/>
>                 <td/>
>             </tr>
>         </table>
>         <div id="console"/>
>     </body>
> 
>             function test() {
>                 fooCell = document.getElementById("foo");
>                 barCell = document.getElementById("bar");
>                 log("foo borderRightWidth: " + getComputedStyle(fooCell, '').borderRightWidth);
>                 log("bar borderLeftWidth: " + getComputedStyle(barCell, '').borderLeftWidth);
>             }
> 
>       RenderBlock {DIV} at (0,70) size 784x56
>         RenderBlock {P} at (0,0) size 784x20
>           RenderText {#text} at (0,0) size 163x19
>             text run at (0,0) width 163: "foo borderRightWidth: 4px"
>         RenderBlock {P} at (0,36) size 784x20
>           RenderText {#text} at (0,0) size 156x19
>             text run at (0,0) width 156: "bar borderLeftWidth: 6px"

Looks like the values returned by getComputedStyle don't take into account the border-collapse indeed. We match IE and Opera here (FF being the only one returning the collapsed computed values).

> > Maybe more importantly, all the virtual border* method on RenderTableCell will still trigger a recomputation and completely miss the cache. The invocations of those function are spread in the rendering code but they are nevertheless important.
> 
>   RenderTable.paintObject() asks every RenderTableCell about its collapsed border, so if table is huge, this takes a lot of time.
>   In contrast RenderTableCell talks only with its direct parents and siblings.
>   Single RenderTableCell::collapsedStartBorder() method requires about 1/1000 ms on my computer.

>   Can we however do this in separate bug?

I agree with your assessment and that it can be postponed.

> > I feared setting the size to 0 in CollapsedBorderValues would actually hurt other use cases: when you *do* need to collect borders, you can easily need 100 entries in your Vector. 100 entries is only 25 cells (4 borders per cell). You could mitigate that by pre-allocating the Vector before collecting your borders as you can estimate the size needed.
> 
>   As I can see, even for huge table CollapsedBorderValues contains only 2 elements, because we remember only unique CollapsedBorderValue objects.

Indeed, I missed that addBorderStyle checks for unique style before adding it.
Comment 23 Konstantin Shcheglov 2011-09-12 08:54:01 PDT
> >   I don't observe that in JS you access collapsed border values.
> >   I think that collapsed borders are paint/presentation feature instead of style feature.
> 
> I am not sure why you are making some distinction here. getComputedStyle should return the computed value for the property. borderLeftWidth is a layout value which is derived from the different style properties.

  Hm...
  This is like we have small rectangle div of RED color and above it bit div of GREEN color, which fully covers RED one.
  Even if visually we don't see that small div is RED, we still should return its color as RED.

  Basically this is what happens with borders - we paint one border and other border, but they are separate things.


> 
> Looks like the values returned by getComputedStyle don't take into account the border-collapse indeed. We match IE and Opera here (FF being the only one returning the collapsed computed values).

  Yes.
  It seems that there are different approaches here.
  I can not find anything related in standards.


> > 
> >   As I can see, even for huge table CollapsedBorderValues contains only 2 elements, because we remember only unique CollapsedBorderValue objects.
> 
> Indeed, I missed that addBorderStyle checks for unique style before adding it.

  So...
  Is there anything else I can make to get positive review and land this patch?
Comment 24 Konstantin Shcheglov 2011-09-13 12:50:08 PDT

> > 
> >   I don't observe that in JS you access collapsed border values.
> >   I think that collapsed borders are paint/presentation feature instead of style feature.
> 
> I am not sure why you are making some distinction here. getComputedStyle should return the computed value for the property. borderLeftWidth is a layout value which is derived from the different style properties.

  BTW http://www.webkit.org/blog/114/webcore-rendering-i-the-basics/ section "The CSS Box Model" speaks about difference between box model and RenderStyle.
Comment 25 Dave Hyatt 2011-09-14 11:34:20 PDT
Comment on attachment 106870 [details]
Changes for review comments

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

You should use styleDidChange to do invalidation and not styleWillChange. The big advantage of doing so is you could call the base class first and it would mark for layout in the case where the border change results in needing a layout. This would allow you to refine your check so that you only do it if the table and cell don't need relayout. So for example here's what RenderTableSection::styleDidChange might look like:

void RenderTableSection::styleDidChange(StyleDifference diff, const RenderStyle* oldStyle)
 
    RenderBox::styleWillChange(diff, oldStyle);
     if (!selfNeedsLayout() && !normalChildNeedsLayout() && oldStyle && oldStyle->border() != style()->border()) {
        RenderTable* tableRenderer = table();
        if (!tableRenderer->selfNeedsLayout() && !tableRenderer->normalChildNeedsLayout())
            tableRenderer->invalidateCollapsedBorder();
}

This would save you from having to check for borders in a lot of cases, e.g., when the border width of the cell changes, since the cell will already be marked as needing layout, and so you don't have to worry about it.

> Source/WebCore/ChangeLog:10
> +        Invalidate cache when cell, row, row group, col, col group or table border it changed.

Typo. "it" should be "is"

> Source/WebCore/rendering/RenderTable.h:237
> +    virtual void recalcCollapsedBorders();

This should be private and non-virtual. Move it.

> Source/WebCore/rendering/RenderTable.h:270
> +    bool m_collapsedBordersValid;

Move this after m_currentBorder and make it part of the bitfield with m_hasColElements
Comment 26 Konstantin Shcheglov 2011-09-15 13:06:26 PDT
Created attachment 107534 [details]
Changes for review comments

1. I've moved invalidating cache into styleDidChange() method and guarded it with parent()/table()/needsLayout() check before comparing border values. Only table's needsLayout() is used because we invalidate cache only in RenderTable::layout().

2. Fixes for small things.
Comment 27 Dave Hyatt 2011-09-20 11:26:58 PDT
Comment on attachment 107534 [details]
Changes for review comments

table->needsLayout() is too broad. The table may only need "simplified" layout (e.g., only a positioned child moved for example, in which case it won't ever get to the code you added in layout() that invalidates collapsed borders.

You need the check to be !table->selfNeedsLayout() && !table->normalChildNeedsLayout() rather than simply !table->needsLayout().

You might want to add a test case for this situation just to cover it. Make a table with a positioned block child. Do something to cause that positioned child to need a layout and then change a cell's border style (such that it would only need a repaint).
Comment 28 Konstantin Shcheglov 2011-09-21 11:49:44 PDT
Created attachment 108196 [details]
Use better need*Layout() checks. New test with positioned block child.
Comment 29 Dave Hyatt 2011-09-21 14:59:32 PDT
Comment on attachment 108196 [details]
Use better need*Layout() checks. New test with positioned block child.

r=me
Comment 30 WebKit Review Bot 2011-09-22 18:56:29 PDT
Comment on attachment 108196 [details]
Use better need*Layout() checks. New test with positioned block child.

Rejecting attachment 108196 [details] from commit-queue.

Failed to run "['/mnt/git/webkit-commit-queue/Tools/Scripts/webkit-patch', '--status-host=queues.webkit.org', '-..." exit_code: 1

Last 500 characters of output:
ommit-queue/Tools/Scripts/webkitpy/tool/commands/stepsequence.py", line 64, in _run
    step(tool, options).run(state)
  File "/mnt/git/webkit-commit-queue/Tools/Scripts/webkitpy/tool/steps/validatereviewer.py", line 57, in run
    if self._has_valid_reviewer(changelog_entry):
  File "/mnt/git/webkit-commit-queue/Tools/Scripts/webkitpy/tool/steps/validatereviewer.py", line 42, in _has_valid_reviewer
    if changelog_entry.reviewer():
AttributeError: 'NoneType' object has no attribute 'reviewer'

Full output: http://queues.webkit.org/results/9797506
Comment 31 Konstantin Shcheglov 2011-09-23 11:48:27 PDT
Created attachment 108503 [details]
Patch for landing
Comment 32 WebKit Review Bot 2011-09-23 11:49:21 PDT
Comment on attachment 108503 [details]
Patch for landing

Rejecting attachment 108503 [details] from commit-queue.

scheglov@google.com does not have committer permissions according to http://trac.webkit.org/browser/trunk/Tools/Scripts/webkitpy/common/config/committers.py.

- If you do not have committer rights please read http://webkit.org/coding/contributing.html for instructions on how to use bugzilla flags.

- If you have committer rights please correct the error in Tools/Scripts/webkitpy/common/config/committers.py by adding yourself to the file (no review needed).  The commit-queue restarts itself every 2 hours.  After restart the commit-queue will correctly respect your committer rights.
Comment 33 Dave Hyatt 2011-09-23 12:17:02 PDT
Comment on attachment 108196 [details]
Use better need*Layout() checks. New test with positioned block child.

r=me
Comment 34 Julien Chaffraix 2011-09-23 12:55:32 PDT
Committed r95852: <http://trac.webkit.org/changeset/95852>