Bug 13445

Summary: NodeList access by index is slow
Product: WebKit Reporter: Alexey Proskuryakov <ap>
Component: DOMAssignee: Alexey Proskuryakov <ap>
Status: RESOLVED FIXED    
Severity: Normal    
Priority: P2    
Version: 523.x (Safari 3)   
Hardware: Mac   
OS: OS X 10.4   
URL: http://www.hixie.ch/tests/adhoc/perf/dom/artificial/core/001.html
Attachments:
Description Flags
easy way out darin: review+

Alexey Proskuryakov
Reported 2007-04-22 01:55:45 PDT
On the "index" part of this test (see bug URL), WebKit is much slower than other browsers. On my machine, TOT is even somewhat slower than shipping Safari (~6 seconds vs. ~7 seconds), but I'm hesitant to make the bug P1 because of this. Almost all of the time is spent calling nextSibling(), which is a single memory access instruction, so the test is memory-bound, and it's probably semi-random changes in memory layout that cause this. while (n && pos < index) { n = n->nextSibling(); pos++; } Looking at the assembly, I noticed that gcc 3.3 and gcc 4.0.1 generate slightly different PowerPC code for this loop. That doesn't appear to affect performance much - I made a reduced test, and gcc 4 code was not slower.
Attachments
easy way out (2.68 KB, patch)
2007-04-24 13:31 PDT, Alexey Proskuryakov 		darin: review+
DetailsFormatted DiffDiff
View All Add attachment proposed patch, testcase, etc.
Alexey Proskuryakov
Comment 1 2007-04-24 13:31:58 PDT
Created attachment 14161 [details] easy way out Just add support for iterating backwards. On my machine, results on the "Index" test look OK now (~7000 ms TOT, ~100 ms TOT + this patch, ~120 ms Opera, ~1300 ms Firefox). KHTML also has support for iterating backwards, and according to Maks Orlovich, it was added to fix a real site, forums.tweakers.nl. I've also added support for iteration from lastChild. I still think that there might be a better data structure for a list of child nodes in ContainerNode, and that would speed up other operations, too. Obviously, performance of data structures is always a trade-off, so it would probably take someone with access to PLT to play with it.
Darin Adler
Comment 2 2007-04-25 01:04:25 PDT
Comment on attachment 14161 [details] easy way out + unsigned dist = (unsigned)abs((long)index - (long)m_caches->lastItemOffset); Since the parameter to abs is an int, the cast here should be to int, not long. But also no casts are needed. If you do unsigned - unsigned, then pass to int, and then extract it into unsigned it will do the right thing with no casts at all. Otherwise looks fine. r=me
Alexey Proskuryakov
Comment 3 2007-04-25 11:42:09 PDT
Ah, I got confused by std::abs from cstdlib. Hoping MSVC won't be confused similarly :-). Committed revision 21090.
Note You need to log in before you can comment on or make changes to this bug.