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

bugzilla-daemon at webkit.org bugzilla-daemon at webkit.org
Sat May 19 02:27:47 PDT 2007


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
(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.

More information about the webkit-unassigned mailing list