Bug 30988 – Attribute cache purged too eagerly

• Status: UNCONFIRMED
• Component: WebCore Misc.

[James Robinson]

The following code runs in O(N) time on Firefox and O(N^2) time on WebKit based browsers:

  var elems = document.getElementsByName('elem_name');
  for (var i=0; i<elems.length; i++) {
    var e = elems.item(i);
    e.className = 'elem_class';
  }

document.getElementsByName() returns a NodeList which is backed by a WebCore::DynamicNodeList.  The reason for the slowdown is that assigning to e.className forces the document's entire node list cache to be dumped, even though the DynamicNodeList backing the 'elems' variable has nothing to do with the class name attribute.  This means in each loop iteration the 'elems' variable has to be recalculated by evaluating every node in the entire DOM to see if its name is 'elem_name'.  There's two obvious optimizations that can be made:

1) When an attribute is mutated only purge node list caches associated with the attribute mutated
2) When an attribute with value X has X written into it (i.e. if the className was already 'elem_class' in this example), do not purge any node list caches

It's of course possible to rewrite the javascript snippet to perform much better by copying the elements in 'elems' into a javascript array before mutating them, but I think the javascript is fairly idiomatic and reasonable.  Additionally since Firefox performs fine on this code developers are less likely to notice how badly this performs.

[James Robinson]

Created attachment 42268 [details]
Test page to see behavior

Attached is a simple test page to try out.  There's three versions of the loop - the naive solution from the bug report, a version that stores the 'length' property in a javascript variable, and a version that copies the entire node list into a javascript array before mutating values.  On a pretty recent WebKit nightly in Safari on OS X I get these times:

time elapsed (naive) for 5000 was 1490 ms
time elapsed (naive) for 5000 was 1393 ms
time elapsed (cache length) for 5000 was 471 ms
time elapsed (cache length) for 5000 was 481 ms
time elapsed (cache array) for 5000 was 10 ms
time elapsed (cache array) for 5000 was 10 ms

On Firefox 3.5.4 on OS X I get these times:

time elapsed (naive) for 5000 was 82 ms
time elapsed (naive) for 5000 was 24 ms
time elapsed (cache length) for 5000 was 128 ms
time elapsed (cache length) for 5000 was 13 ms
time elapsed (cache array) for 5000 was 130 ms
time elapsed (cache array) for 5000 was 29 ms