13445 2007-04-22 01:55:45 -0700 NodeList access by index is slow 2007-04-25 11:42:09 -0700 1 1 1 Unclassified WebKit DOM 523.x (Safari 3) Mac OS X 10.4 RESOLVED FIXED http://www.hixie.ch/tests/adhoc/perf/dom/artificial/core/001.html P2 Normal --- 1 ap ap oldest_to_newest 13316 0 ap 2007-04-22 01:55:45 -0700 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. 12974 1 14161 ap 2007-04-24 13:31:58 -0700 Created attachment 14161 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. 12756 2 14161 darin 2007-04-25 01:04:25 -0700 Comment on attachment 14161 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 12499 3 ap 2007-04-25 11:42:09 -0700 Ah, I got confused by std::abs from cstdlib. Hoping MSVC won't be confused similarly :-). Committed revision 21090. 14161 2007-04-24 13:31:58 -0700 2007-04-25 01:04:25 -0700 easy way out 13445r1_patch.txt text/plain 2744 ap SW5kZXg6IFdlYkNvcmUvQ2hhbmdlTG9nCj09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT0KLS0tIFdlYkNvcmUvQ2hhbmdlTG9n CShyZXZpc2lvbiAyMTA3MikKKysrIFdlYkNvcmUvQ2hhbmdlTG9nCSh3b3JraW5nIGNvcHkpCkBA IC0xLDMgKzEsMTUgQEAKKzIwMDctMDQtMjUgIEFsZXhleSBQcm9za3VyeWFrb3YgIDxhcEB3ZWJr aXQub3JnPgorCisgICAgICAgIFJldmlld2VkIGJ5IE5PQk9EWSAoT09QUyEpLgorCisgICAgICAg IGh0dHA6Ly9idWdzLndlYmtpdC5vcmcvc2hvd19idWcuY2dpP2lkPTEzNDQ1CisgICAgICAgIE5v ZGVMaXN0IGFjY2VzcyBieSBpbmRleCBpcyBzbG93CisKKyAgICAgICAgKiBkb20vQ2hpbGROb2Rl TGlzdC5jcHA6CisgICAgICAgIChXZWJDb3JlOjpDaGlsZE5vZGVMaXN0OjppdGVtKTogU3VwcG9y dCBpdGVyYXRpbmcgYmFja3dhcmRzIGZyb20gdGhlIGxhc3QgYWNjZXNzZWQgbm9kZQorICAgICAg ICBvciBmcm9tIHRoZSBsYXN0IGNoaWxkLgorICAgICAgICAqIGRvbS9Ob2RlTGlzdC5oOiBNYWtl IGNhY2hlZExlbmd0aCB1bnNpZ25lZC4KKwogMjAwNy0wNC0yNCAgRGFyaW4gQWRsZXIgIDxkYXJp bkBhcHBsZS5jb20+CiAKICAgICAgICAgUmV2aWV3ZWQgYnkgSnVzdGluLgpJbmRleDogV2ViQ29y ZS9kb20vQ2hpbGROb2RlTGlzdC5jcHAKPT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PQotLS0gV2ViQ29yZS9kb20vQ2hpbGRO b2RlTGlzdC5jcHAJKHJldmlzaW9uIDIxMDcwKQorKysgV2ViQ29yZS9kb20vQ2hpbGROb2RlTGlz dC5jcHAJKHdvcmtpbmcgY29weSkKQEAgLTUxLDI1ICs1MSw0NCBAQCB1bnNpZ25lZCBDaGlsZE5v ZGVMaXN0OjpsZW5ndGgoKSBjb25zdAogICAgIHJldHVybiBsZW47CiB9CiAKLU5vZGUgKkNoaWxk Tm9kZUxpc3Q6Oml0ZW0odW5zaWduZWQgaW5kZXgpIGNvbnN0CitOb2RlKiBDaGlsZE5vZGVMaXN0 OjppdGVtKHVuc2lnbmVkIGluZGV4KSBjb25zdAogewogICAgIHVuc2lnbmVkIGludCBwb3MgPSAw OwotICAgIE5vZGUgKm4gPSBtX3Jvb3ROb2RlLT5maXJzdENoaWxkKCk7CisgICAgTm9kZSogbiA9 IG1fcm9vdE5vZGUtPmZpcnN0Q2hpbGQoKTsKIAogICAgIGlmIChtX2NhY2hlcy0+aXNJdGVtQ2Fj aGVWYWxpZCkgewogICAgICAgICBpZiAoaW5kZXggPT0gbV9jYWNoZXMtPmxhc3RJdGVtT2Zmc2V0 KQogICAgICAgICAgICAgcmV0dXJuIG1fY2FjaGVzLT5sYXN0SXRlbTsKLSAgICAgICAgaWYgKGlu ZGV4ID4gbV9jYWNoZXMtPmxhc3RJdGVtT2Zmc2V0KSB7CisgICAgICAgIAorICAgICAgICB1bnNp Z25lZCBkaXN0ID0gKHVuc2lnbmVkKWFicygobG9uZylpbmRleCAtIChsb25nKW1fY2FjaGVzLT5s YXN0SXRlbU9mZnNldCk7CisgICAgICAgIGlmIChkaXN0IDwgaW5kZXgpIHsKICAgICAgICAgICAg IG4gPSBtX2NhY2hlcy0+bGFzdEl0ZW07CiAgICAgICAgICAgICBwb3MgPSBtX2NhY2hlcy0+bGFz dEl0ZW1PZmZzZXQ7CiAgICAgICAgIH0KICAgICB9CiAKLSAgICB3aGlsZSAobiAmJiBwb3MgPCBp bmRleCkgewotICAgICAgICBuID0gbi0+bmV4dFNpYmxpbmcoKTsKLSAgICAgICAgcG9zKys7Cisg ICAgaWYgKG1fY2FjaGVzLT5pc0xlbmd0aENhY2hlVmFsaWQpIHsKKyAgICAgICAgaWYgKGluZGV4 ID49IG1fY2FjaGVzLT5jYWNoZWRMZW5ndGgpCisgICAgICAgICAgICByZXR1cm4gMDsKKworICAg ICAgICB1bnNpZ25lZCBkaXN0ID0gKHVuc2lnbmVkKWFicygobG9uZylpbmRleCAtIChsb25nKXBv cyk7CisgICAgICAgIGlmIChkaXN0ID4gbV9jYWNoZXMtPmNhY2hlZExlbmd0aCAtIDEgLSBpbmRl eCkgeworICAgICAgICAgICAgbiA9IG1fcm9vdE5vZGUtPmxhc3RDaGlsZCgpOworICAgICAgICAg ICAgcG9zID0gbV9jYWNoZXMtPmNhY2hlZExlbmd0aCAtIDE7CisgICAgICAgIH0KICAgICB9CiAK KyAgICBpZiAocG9zIDw9IGluZGV4KQorICAgICAgICB3aGlsZSAobiAmJiBwb3MgPCBpbmRleCkg eworICAgICAgICAgICAgbiA9IG4tPm5leHRTaWJsaW5nKCk7CisgICAgICAgICAgICArK3BvczsK KyAgICAgICAgfQorICAgIGVsc2UKKyAgICAgICAgd2hpbGUgKG4gJiYgcG9zID4gaW5kZXgpIHsK KyAgICAgICAgICAgIG4gPSBuLT5wcmV2aW91c1NpYmxpbmcoKTsKKyAgICAgICAgICAgIC0tcG9z OworICAgICAgICB9CisKICAgICBpZiAobikgewogICAgICAgICBtX2NhY2hlcy0+bGFzdEl0ZW0g PSBuOwogICAgICAgICBtX2NhY2hlcy0+bGFzdEl0ZW1PZmZzZXQgPSBwb3M7CkluZGV4OiBXZWJD b3JlL2RvbS9Ob2RlTGlzdC5oCj09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT0KLS0tIFdlYkNvcmUvZG9tL05vZGVMaXN0LmgJ KHJldmlzaW9uIDIxMDcwKQorKysgV2ViQ29yZS9kb20vTm9kZUxpc3QuaAkod29ya2luZyBjb3B5 KQpAQCAtNDIsNyArNDIsNyBAQCBwdWJsaWM6CiAgICAgICAgIENhY2hlcygpOwogICAgICAgICB2 b2lkIHJlc2V0KCk7CiAgICAgICAgIAotICAgICAgICBpbnQgY2FjaGVkTGVuZ3RoOworICAgICAg ICB1bnNpZ25lZCBjYWNoZWRMZW5ndGg7CiAgICAgICAgIE5vZGUqIGxhc3RJdGVtOwogICAgICAg ICB1bnNpZ25lZCBsYXN0SXRlbU9mZnNldDsKICAgICAgICAgYm9vbCBpc0xlbmd0aENhY2hlVmFs aWQgOiAxOwo=