271709 - [FIX]setAttribute unnecessarily slow on document.links collection?

Status: VERIFIED FIXED

(Core :: DOM: Core & HTML, defect, P1)

Description

[Martijn Wargers (dead)]

User-Agent:       Mozilla/5.0 (Windows; U; Windows NT 5.0; en-US; rv:1.8a5) Gecko/20041124 Firefox/0.9.1+
Build Identifier: Mozilla/5.0 (Windows; U; Windows NT 5.0; en-US; rv:1.8a5) Gecko/20041124 Firefox/0.9.1+

Gemal's front page blog on Mozilla freezes for me for quite some while. 
I think this happens because of the nicetitles script on that page:
http://gemal.dk/js/titles.js
It uses the document.links collection and uses setAttribute on that collection.
This is quite slow with Mozilla. I'll attach a testcase which demonstrates that.
Gemal's site happens to have a lot of links (appr. 3000), so that seems to be
the reason that the site freezes for me for a while.

Reproducible: Always
Steps to Reproduce:
1.
2.
3.

Comment 1

[Martijn Wargers (dead)]

Attachment: Testcase

Results for the different browsers are in the testcase.
When you click on the second button, first do a refresh, otherwise the test is
probably not fair.

Comment 2

[Henrik Gemal]

hmmm using latest branch build:
Mozilla/5.0 (Windows; U; Windows NT 5.1; da-DK; rv:1.7.5) Gecko/20041115 Firefox/1.0

I'm getting 203ms on the first and 344ms on the second
Pentium 4 3GHz Windows XP

Comment 3

[Martijn Wargers (dead)]

Indeed, this seems like a regression. Using Mozilla1.7, the first button takes
appr. 1150ms.
The bug seems to be there since the beginning of the 1.8a cycle. 
The first button is also very slow, using:
Mozilla/5.0 (Windows; U; Windows NT 5.0; en-US; rv:1.8a) Gecko/20040416
Firefox/0.8.0+

Comment 4

[Henrik Gemal]

Using latest night build (not branch):
Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.8a5) Gecko/20041124
Firefox/0.9.1+

I'm getting 3765ms on the first and 344ms on the second
Pentium 4 3GHz Windows XP

So this is fixed on the branch! This means that it's also fixed in Mozilla
Firefox 1.0. As soon as the aviavy branch lands of the trunk you'll see the
performance improvement as well.

Comment 5

[Martijn Wargers (dead)]

(In reply to comment #4)
> So this is fixed on the branch! This means that it's also fixed in Mozilla
> Firefox 1.0. As soon as the aviavy branch lands of the trunk you'll see the
> performance improvement as well.
I don't understand what you mean. The development of these kind of things
happens in the 1.8a development cycle, right?  I can see this bug also in
Mozilla. I really don't think this has got anything to do with some Firefox
specific code.

Comment 6

[Martijn Wargers (dead)]

Ok, I've built a 2004-04-14 trunk build (no debug).
Test results (approximately):
with document.links: 4100ms
with document.getelementsbytagname: 4700ms

After that I applied the patch from bug 240186 and rebuilt.
Test results after patch (approximately):
with document.links: 24000ms
with document.getelementsbytagname: 4700ms

Comment 7

[Boris Zbarsky [:bzbarsky]]

Fun.

So the issue, of course, is that the links nodelist uses a callback function. 
Which means that as far as the nodelist code goes it _could_ depend on the
attributes being changed, since the callback function could easily look at
attributes (and for getElementsByAttribute _does_, hence the dependency on bug
240186).

In this case, the list is dirtied on every attribute set, so every time through
the loop we have to completely traverse the document and build up the whole
links array....

Comment 8

[Boris Zbarsky [:bzbarsky]]

Oh, and the worst part is that document.links membership _does_ depend on the
value (well, existence) of the "href" attribute.  So we can't even get around
this by flagging certain functions as not depending on attributes, since this
one does depend on an attribute.

Comment 9

[Boris Zbarsky [:bzbarsky]]

Attachment: Strengthen optimization

Comment 10

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 167557 [details] [diff] [review]
Strengthen optimization

jst, would you review?	The basic idea is that if we now match aContent but
it's already in the list, there's no reason to do anything.  So we only need to
dirty when aContent is not yet in our list.

This patch puts the document.links times back on par with the
document.getElementsByTagName() times on the attached testcase.

Comment 11

[Johnny Stenback (:jst)]

Comment on attachment 167557 [details] [diff] [review]
Strengthen optimization

r+sr=jst

Comment 12

[Boris Zbarsky [:bzbarsky]]

Fix checked in.  Martijn, thank you for the wonderful bug report!

Comment 13

[Martijn Wargers (dead)]

Thank you for the wonderful fix! (well, I don't know if the fix is wonderful,
actually)
Verified.