[Webkit-unassigned] [Bug 13785] Counters exhibit O(n^2) creation/destruction behavior

[bugzilla-daemon at webkit.org]

http://bugs.webkit.org/show_bug.cgi?id=13785


hyatt at apple.com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |darin at apple.com,
                   |                            |bdakin at apple.com




------- Comment #1 from hyatt at apple.com  2007-05-19 02:27 PDT -------
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.


-- 
Configure bugmail: http://bugs.webkit.org/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are the assignee for the bug, or are watching the assignee.