Bug 13785 – Counters exhibit O(n^2) creation/destruction behavior

• Status: RESOLVED
• Resolution: FIXED
• Component: CSS

[Dave Hyatt]

Counters appear to have both O(n^2) creation and destruction behavior, even in non-dynamic cases (just a normal forward parse of a document).

This can be seen in the view source mode that uses counters.  I will either have to stop using counters for view source mode, or we'll have to fix this extreme slowness.

[Dave Hyatt]

Some observations from studying the code:

(1) The search for the previous "reset" node is O(n^2), since nobody caches anything.
(2) The search for the previous "increment" node is O(n^3), since every previous item in the render tree is walked once during buildup, but then each one does the O(n^2) search for the reset node because of recurrence.

These two problems alone make counters pathologically slow even in simple sibling cases.

I haven't studied destruction closely but I do see no checks for documentBeingDestroyed, which implies a bunch of unnecessary teardown work is probably being performed.

[Dave Hyatt]

Never mind. It's "just" O(n^2). I didn't notice the alwaysCreateCounter arg was set to false. :)

[Dave Hyatt]

Ok, verified that construction slowness is pretty much entirely due to the first loop in findPlaceForCounter.  Each subsequent counter has to crawl all the previous siblings before going up to the parent.

[Dave Hyatt]

The two loops should be combined.

The second loop (the one that does the previous in pre-order walk) should be modified and used to also find the reset node.  While walking backwards in pre-order, look for any counter-increment or counter-reset counters.  If you hit an increment node before hitting any reset node, then you have both your previous counter node and your parent counter node (by just geting the increment's parent). 

At the same time this backwards pre-order walk is being done, track the next previous sibling or parent (as the first loop was doing).  Refuse to look at any increment nodes if you hit a reset before hitting the next previous sibling or parent candidate.  Once you hit that next candidate, you can safely look at increment nodes again as far as using them to find the reset.

[Dave Hyatt]

Created attachment 14622 [details]
Patch that fuses the two loops

[Dave Hyatt]

Note this patch also cuts the # of counter nodes created in half, since text nodes were needlessly creating duplicates of their before/after containing content's counter node.

[Dave Hyatt]

(In reply to comment #4)
> The two loops should be combined.
> 
> The second loop (the one that does the previous in pre-order walk) should be
> modified and used to also find the reset node.  While walking backwards in
> pre-order, look for any counter-increment or counter-reset counters.  If you
> hit an increment node before hitting any reset node, then you have both your
> previous counter node and your parent counter node (by just geting the
> increment's parent). 
> 
> At the same time this backwards pre-order walk is being done, track the next
> previous sibling or parent (as the first loop was doing).  Refuse to look at
> any increment nodes if you hit a reset before hitting the next previous sibling
> or parent candidate.  Once you hit that next candidate, you can safely look at
> increment nodes again as far as using them to find the reset.
> 

Just ignore the details of this comment, since they're all wrong.  I understand how counters work now after failing all the test cases. :)  Anyway, the idea of fusing the loops remained valid and provides a nice speed boost.

[Darin Adler]

Comment on attachment 14622 [details]
Patch that fuses the two loops

Looks fine. r=me if all layout tests still pass

[Mark Rowe (bdash)]

This was landed in r21606.