30988 2009-10-31 21:35:53 -0700 Attribute cache purged too eagerly 2017-07-18 08:29:24 -0700 1 1 1 Unclassified WebKit WebCore Misc. 528+ (Nightly build) All All UNCONFIRMED P2 Normal --- 0 jamesr webkit-unassigned hamaji paranoid.android.dev oldest_to_newest 159611 0 jamesr 2009-10-31 21:35:53 -0700 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. 159614 1 42268 jamesr 2009-10-31 21:39:27 -0700 Created attachment 42268 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 42268 2009-10-31 21:39:27 -0700 2009-10-31 21:39:27 -0700 Test page to see behavior name.html text/html 2127 jamesr PGh0bWw+CjxoZWFkPgo8c3R5bGU+Ci5lbGVtX2NsYXNzIHsgY29sb3I6IHJlZH0KLmVsZW1fY2xh c3MyIHsgY29sb3I6IGdyZWVufQouZWxlbV9jbGFzczMgeyBjb2xvcjogYmx1ZX0KPC9zdHlsZT4K PHNjcmlwdD4KZnVuY3Rpb24gbG9nKHMpIHsKICB2YXIgZCA9IGRvY3VtZW50LmNyZWF0ZUVsZW1l bnQoJ2RpdicpOwogIGQuaW5uZXJIVE1MID0gczsKICBkb2N1bWVudC5nZXRFbGVtZW50QnlJZCgn bG9nJykuYXBwZW5kQ2hpbGQoZCk7CiAgY29uc29sZS5sb2cocyk7Cn0KCmZ1bmN0aW9uIHRlc3Qo KSB7CiAgdmFyIHN0YXJ0VGltZSA9IG5ldyBEYXRlKCkuZ2V0VGltZSgpOwogIHZhciBlbGVtcyA9 IGRvY3VtZW50LmdldEVsZW1lbnRzQnlOYW1lKCdlbGVtX25hbWUnKTsKICBmb3IgKHZhciBpPTA7 IGk8ZWxlbXMubGVuZ3RoOyBpKyspIHsKICAgIHZhciBlID0gZWxlbXMuaXRlbShpKTsKICAgIGUu Y2xhc3NOYW1lID0gJ2VsZW1fY2xhc3MnOwogIH0KICB2YXIgZW5kVGltZSA9IG5ldyBEYXRlKCku Z2V0VGltZSgpOwogIGxvZygidGltZSBlbGFwc2VkIChuYWl2ZSkgZm9yICIgKyBlbGVtcy5sZW5n dGggKyAiIHdhcyAiCiAgICAgICAgICAgICAgKyAoZW5kVGltZSAtIHN0YXJ0VGltZSkgKyAiIG1z Iik7Cn0KCmZ1bmN0aW9uIHRlc3QyKCkgewogIHZhciBzdGFydFRpbWUgPSBuZXcgRGF0ZSgpLmdl dFRpbWUoKTsKICB2YXIgZWxlbXMgPSBkb2N1bWVudC5nZXRFbGVtZW50c0J5TmFtZSgnZWxlbV9u YW1lJyk7CiAgdmFyIGwgPSBlbGVtcy5sZW5ndGg7CiAgZm9yICh2YXIgaT0wOyBpPGw7IGkrKykg ewogICAgdmFyIGUgPSBlbGVtcy5pdGVtKGkpOwogICAgZS5jbGFzc05hbWUgPSAnZWxlbV9jbGFz czInOwogIH0KICB2YXIgZW5kVGltZSA9IG5ldyBEYXRlKCkuZ2V0VGltZSgpOwogIGxvZygidGlt ZSBlbGFwc2VkIChjYWNoZSBsZW5ndGgpIGZvciAiICsgZWxlbXMubGVuZ3RoICsgIiB3YXMgIgog ICAgICAgICAgICAgICsgKGVuZFRpbWUgLSBzdGFydFRpbWUpICsgIiBtcyIpOwp9CgpmdW5jdGlv biB0ZXN0MygpIHsKICB2YXIgc3RhcnRUaW1lID0gbmV3IERhdGUoKS5nZXRUaW1lKCk7CiAgdmFy IGVsZW1zID0gZG9jdW1lbnQuZ2V0RWxlbWVudHNCeU5hbWUoJ2VsZW1fbmFtZScpOwogIHZhciBs ID0gZWxlbXMubGVuZ3RoOwogIHZhciBlbGVtc0FyciA9IFtdOwogIGZvciAodmFyIGk9MDsgaTxs OyBpKyspIHsKICAgIGVsZW1zQXJyLnB1c2goZWxlbXMuaXRlbShpKSk7CiAgfQogIGZvciAodmFy IGk9MDsgaTxsOyBpKyspIHsKICAgIHZhciBlID0gZWxlbXNBcnJbaV07CiAgICBlLmNsYXNzTmFt ZSA9ICdlbGVtX2NsYXNzMyc7CiAgfQogIHZhciBlbmRUaW1lID0gbmV3IERhdGUoKS5nZXRUaW1l KCk7CiAgbG9nKCJ0aW1lIGVsYXBzZWQgKGNhY2hlIGFycmF5KSBmb3IgIiArIGVsZW1zLmxlbmd0 aCArICIgd2FzICIKICAgICAgICAgICAgICArIChlbmRUaW1lIC0gc3RhcnRUaW1lKSArICIgbXMi KTsKfQoKd2luZG93Lm9ubG9hZCA9IGZ1bmN0aW9uKCkgewogIHZhciByb290ID0gZG9jdW1lbnQu Z2V0RWxlbWVudEJ5SWQoJ3Jvb3QnKTsKICBmb3IgKHZhciBpPTA7IGk8NTA7IGkrKykgewogICAg dmFyIHIgPSBkb2N1bWVudC5jcmVhdGVFbGVtZW50KCdkaXYnKTsKICAgIGZvciAodmFyIGo9MDsg ajwxMDA7IGorKykgewogICAgICB2YXIgZCA9IGRvY3VtZW50LmNyZWF0ZUVsZW1lbnQoJ2Rpdicp OwogICAgICBkLnNldEF0dHJpYnV0ZSgnbmFtZScsICdlbGVtX25hbWUnKTsKICAgICAgZC5pbm5l ckhUTUwgPSAnYSc7CiAgICAgIHIuYXBwZW5kQ2hpbGQoZCk7CiAgICB9CiAgICByb290LmFwcGVu ZENoaWxkKHIpOwogIH0KfQo8L3NjcmlwdD4KPC9oZWFkPgo8Ym9keT4KPGRpdiBvbmNsaWNrPSJq YXZhc2NyaXB0OnRlc3QoKSI+Y2xpY2sgdG8gdGVzdCBuYWl2ZSBsb29wPC9kaXY+CjxkaXYgb25j bGljaz0iamF2YXNjcmlwdDp0ZXN0MigpIj5jbGljayB0byB0ZXN0IGNhY2hpbmcgbGVuZ3RoPC9k aXY+CjxkaXYgb25jbGljaz0iamF2YXNjcmlwdDp0ZXN0MygpIj5jbGljayB0byB0ZXN0IGNhY2hp bmcgYXJyYXk8L2Rpdj4KPGRpdiBpZD0ibG9nIj48L2Rpdj4KPGRpdiBpZD0icm9vdCI+PC9kaXY+ CjwvYm9keT4KPC9odG1sPgoK