308401 - Investigate caching last found index for nsContentList::NamedItem

Status: NEW

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

Description

[Boris Zbarsky [:bzbarsky]]

It looks like code patterns like this are somewhat common:

function Clip()
{
  q=document.getElementsByTagName('div');
  
  for(i=0;i<200;i++)
  {
    q['lay'+i].style.clip='rect(0 100 100 0)';
  }
}

This walks the list starting at the front every time for the NamedItem call, so
the whole thing is O(N^2) in the number of divs involved (200 in this case).

Brendan suggested that having some hard data here would be good, so I'll attach
a patch that could be used to collect said data.  bc, would you be willing to
run this patch through a large set of pages in an opt build with standard output
going to a file and send me the resulting file, or tell me how I could do that
myself?

Comment 1

[Boris Zbarsky [:bzbarsky]]

Attachment: Logging patch

Comment 2

[Boris Zbarsky [:bzbarsky]]

Attachment: Log of loading 544 sites using bc's spider (then firefox crashed)

Comment 3

[Boris Zbarsky [:bzbarsky]]

Attachment: Perl script to analyze the data

It turned out that graphing the data is silly...  Here's the result:

Length: 35 Hits at: 34 34
Length: 123 Hits at: 122 122
Length: 9 Hits at: 8 8
Length: 22 Hits at: 10
Length: 2 Hits at: 1 1
Length: 49 Hits at: 48 48
Length: 1 Hits at: 0 0 0
Length: 1 Hits at: 0 0
Length: 1 Hits at: 0
Length: 54 Hits at: 52 52 53
Length: 87 Hits at: 86 86
Length: 1 Hits at: 0 0 0
Length: 121 Hits at: 120 120
Length: 3 Hits at: 0
Length: 3 Hits at: 1 1 1 1
Length: 168 Hits at: 167 167
Length: 22 Hits at: 21 21
Length: 18 Hits at: 17 17
Length: 25 Hits at: 24 24
Length: 2 Hits at: 1
Length: 104 Hits at: 14 13 15
Length: 2 Hits at: 1 1
--------------------
Total calls to NamedItem: 1686
Total misses: 1640
Total lists completely missed: 1594
Total lists hit: 22
Average length of a list that had a hit: 38.77
Max length of a list that had a hit: 168
Min length of a list that had a hit: 1
Average hit location: 17.07
1 lists hit 4 times.
4 lists hit 1 times.
4 lists hit 3 times.
13 lists hit 2 times.
1 hits differed by 1 from the previous hit on the same list.
21 hits differed by 0 from the previous hit on the same list.
1 hits differed by 2 from the previous hit on the same list.
1 hits differed by -1 from the previous hit on the same list.

Conclusion:  There is a very strong tendency towards repeat hits at the same
exact location.

Now the only question is whether we can relax the guarantee we have now that
list[name] returns the _first_ thing in the list with that name or id... :(

Comment 4

[Boris Zbarsky [:bzbarsky]]

Attachment: Er, this is the real script

Comment 5

[Boris Zbarsky [:bzbarsky]]

We can't relax that guarantee, of course.  So I'm not really sure there's a reasonable way to do this....

Comment 6

[Nathan Froyd [:froydnj]]

Why not just maintain a hashtable off to the side?  Too expensive?

Comment 7

[Boris Zbarsky [:bzbarsky]]

We could do that, yes.  It'd increase the size of nodelists, but that might be ok.  Just have to be careful to clear the hashtable whenever we dirty the list.

Comment 8

[Firefox Bug Husbandry Bot]

https://bugzilla.mozilla.org/show_bug.cgi?id=1472046

Move all DOM bugs that haven’t been updated in more than 3 years and has no one currently assigned to P5.

If you have questions, please contact :mdaly.