Bug 60323

Summary: RenderCounter::makeCounterNode is N^2, causing large view-source pages to take seconds to load
Product: WebKit Reporter: Evan Martin <evan>
Component: DOMAssignee: Nobody <webkit-unassigned>
Status: NEW    
Severity: Normal CC: abarth, bdakin, darin, dglazkov, eric, esprehn, macpherson, mikelawther, skylined
Priority: P2    
Version: 528+ (Nightly build)   
Hardware: Unspecified   
OS: Unspecified   
Attachments:
Description Flags
sharky
none
example with counter to 10,000 none

Evan Martin
Reported 2011-05-05 17:14:27 PDT
view-source on http://llvm.org/viewvc/llvm-project/libcxx/trunk/include/cmath?annotate=119395#l736 takes ~10 seconds to unstick for me.
Attachments
sharky (1.07 MB, application/octet-stream)
2011-05-05 18:29 PDT, Adam Barth 		no flags
Details
example with counter to 10,000 (291 bytes, text/html)
2011-05-06 09:16 PDT, Eric Seidel (no email) 		no flags
Details
View All Add attachment proposed patch, testcase, etc.
Adam Barth
Comment 1 2011-05-05 17:41:39 PDT
Yep. We should shark it.
Eric Seidel (no email)
Comment 2 2011-05-05 17:47:05 PDT
Thank you for filing Evan.
Adam Barth
Comment 3 2011-05-05 18:29:32 PDT
Created attachment 92522 [details] sharky All the time is being spent in WebCore::makeCounterNode
Adam Barth
Comment 4 2011-05-05 18:40:57 PDT
The counter algorithm is n^2. Each view-source line looks at all previous lines to figure out what its counter value should be.
Adam Barth
Comment 5 2011-05-05 18:59:09 PDT
We either need to make the counter code faster or not use counters for line numbers. I suspect making the counter code faster is the more virtuous path, but I don't touch WebCore/css.
Adam Barth
Comment 6 2011-05-06 09:09:54 PDT
*** Bug 54730 has been marked as a duplicate of this bug. ***
Eric Seidel (no email)
Comment 7 2011-05-06 09:16:24 PDT
Created attachment 92587 [details] example with counter to 10,000 Page with 10000 counters. This seems faster than the example page, so it may not be hitting the same bug.
Adam Barth
Comment 8 2011-05-06 09:18:31 PDT
> Page with 10000 counters. This seems faster than the example page, so it may not be hitting the same bug. The parser might be more efficient at building these structures than the view-source document. Maybe try building the DOM using the DOM API?
Eric Seidel (no email)
Comment 9 2011-05-09 23:09:10 PDT
How do I repro this in Safari? The LLVM page is only 1000 lines long...
Adam Barth
Comment 10 2011-05-10 00:48:32 PDT
(In reply to comment #9) > How do I repro this in Safari? The LLVM page is only 1000 lines long... <iframe src="...." viewsource></iframe>
Eric Seidel (no email)
Comment 11 2011-05-10 13:22:52 PDT
OK. Attempting to make a reduction now. I suspect that makeCounterNode is actually N*M where N is the number of counters, and M is the number of elements in the document... or possibly worse.
Note You need to log in before you can comment on or make changes to this bug.