99394 2012-10-15 17:24:45 -0700 Optimize QualifiedName-as-hash-key scenario. 2012-10-22 14:29:38 -0700 1 1 1 Unclassified WebKit DOM 528+ (Nightly build) Unspecified Unspecified RESOLVED FIXED P2 Normal --- 98798 1 kling kling darin eric fmalita hyatt mjs pdr schenney oldest_to_newest 742620 0 kling 2012-10-15 17:24:45 -0700 Using QualifiedName as the key type in WTF hash tables is currently a lot less efficient than it could be. 742626 1 kling 2012-10-15 17:26:01 -0700 In the RoboHornet svgresize.html benchmark, I'm seeing ~200ms below QualifiedName instantiation and hash lookups on my MBP. I have a patch to cut this in half. 742629 2 168815 kling 2012-10-15 17:28:14 -0700 Created attachment 168815 Proposed patch 742695 3 eric 2012-10-15 18:27:47 -0700 There is some debate as to if we should even be using QualifiedNames here. anyQName() is this odd hack that we seem to use to be the "null" QualifiedName, and it's basically only used for SVG code: http://code.google.com/p/chromium/source/search?q=anyQName&origq=anyQName&btnG=Search+Trunk I think this patch is totally reasonable, and I can see it being a huge speed win. I'm just not sure if the concept of a null QualifieName (or using QualfiedName in a hash) even makes sense as we currently do it. 742697 4 eric 2012-10-15 18:28:41 -0700 This patch makes me wonder if we shouldn't just ditch anyQName in prefernce for this nullQName anyway. :) 742704 5 pdr 2012-10-15 18:43:52 -0700 Love this patch. Nice work! 742736 6 168815 darin 2012-10-15 19:58:29 -0700 Comment on attachment 168815 Proposed patch View in context: https://bugs.webkit.org/attachment.cgi?id=168815&action=review > Source/WebCore/dom/QualifiedName.h:134 > + QualifiedNameComponents c = { name->m_prefix.impl(), name->m_localName.impl(), name->m_namespace.impl() }; > + name->m_existingHash = hashComponents(c); I think it’d be nice to have this part be out of line to keep the inlined code tighter. Worth testing to see if it makes things faster or slower. If it’s not slower, we should do it. Also, I’d name the local variable something other than c. > Source/WebCore/svg/SVGElement.h:164 > + QualifiedNameComponents c = { nullAtom.impl(), key.localName().impl(), key.namespaceURI().impl() }; > + return hashComponents(c); It’s be nice to name this something other than c. I think we could cache this no-prefix form of the qualified name too; just add another field to QualifiedName for that. 742739 7 168815 darin 2012-10-15 20:02:41 -0700 Comment on attachment 168815 Proposed patch View in context: https://bugs.webkit.org/attachment.cgi?id=168815&action=review > Source/WebCore/ChangeLog:3 > + Clean up QualifiedName-as-hash-key scenario. I would call this “optimize” not “clean up”. 742773 8 mjs 2012-10-15 21:12:13 -0700 anyQName is super mysterious to me. From the name and the "*" strings in it, I would expect it to have some sort of wildcard semantic, but it doesn't really. I wonder if Hyatt remembers what it's for? 742898 9 eric 2012-10-16 00:37:30 -0700 Oddly enough anyQName was added by hyatt! http://trac.webkit.org/changeset/9824 Just hijacked by SVG for null purposes. :( 742927 10 mjs 2012-10-16 01:07:17 -0700 (In reply to comment #9) > Oddly enough anyQName was added by hyatt! http://trac.webkit.org/changeset/9824 Just hijacked by SVG for null purposes. :( Indeed, I remembered that he added it because I reviewed that patch. But I do not remember the original purpose. 747009 11 kling 2012-10-20 16:12:43 -0700 Committed <http://trac.webkit.org/changeset/131993> (Darn, forgot to change the bug title in the ChangeLog.) 747887 12 pdr 2012-10-22 14:29:38 -0700 (In reply to comment #11) > Committed <http://trac.webkit.org/changeset/131993> > (Darn, forgot to change the bug title in the ChangeLog.) This progression is visible in various webkit-perf graphs (bigger is better): http://webkit-perf.appspot.com/graph.html#tests=[[8195914,2001,173262]]&sel=1350758073445.8484,1350797740907.5178,0.9000000000000004,6&displayrange=7&datatype=running Nice work! 168815 2012-10-15 17:28:14 -0700 2012-10-15 20:02:41 -0700 Proposed patch bug-99394.diff text/plain 5484 kling ZGlmZiAtLWdpdCBhL1NvdXJjZS9XZWJDb3JlL0NoYW5nZUxvZyBiL1NvdXJjZS9XZWJDb3JlL0No YW5nZUxvZwppbmRleCA3OGU2ODAyLi43NjNjMWFkIDEwMDY0NAotLS0gYS9Tb3VyY2UvV2ViQ29y ZS9DaGFuZ2VMb2cKKysrIGIvU291cmNlL1dlYkNvcmUvQ2hhbmdlTG9nCkBAIC0xLDUgKzEsMzYg QEAKIDIwMTItMTAtMTUgIEFuZHJlYXMgS2xpbmcgIDxrbGluZ0B3ZWJraXQub3JnPgogCisgICAg ICAgIENsZWFuIHVwIFF1YWxpZmllZE5hbWUtYXMtaGFzaC1rZXkgc2NlbmFyaW8uCisgICAgICAg IDxodHRwOi8vd2Via2l0Lm9yZy9iLzk5Mzk0PgorCisgICAgICAgIFJldmlld2VkIGJ5IE5PQk9E WSAoT09QUyEpLgorCisgICAgICAgIENhY2hlIHRoZSBoYXNoIG9uIFF1YWxpZmllZE5hbWVJbXBs IGFmdGVyIHRoZSBmaXJzdCB0aW1lIGl0J3MgY29tcHV0ZWQuCisgICAgICAgIFRoaXMgZ3Jvd3Mg UXVhbGlmaWVkTmFtZUltcGwgYnkgNCBieXRlcyBvbiAzMi1iaXQgKG5vIGNoYW5nZSBvbiA2NC1i aXQgZHVlIHRvIGJhc2UgY2xhc3MgcGFkZGluZykKKyAgICAgICAgd2hpY2ggSSBiZWxpZXZlIGlz IGZpbmUsIHNpbmNlIFF1YWxpZmllZE5hbWUgaXMgYSBzaGFyZWQgb2JqZWN0LgorCisgICAgICAg IEFkZCBhIGdsb2JhbCBudWxsUU5hbWUoKSBmdW5jdGlvbiB0aGF0IHJldHVybnMgYSBRdWFsaWZp ZWROYW1lKG51bGxBdG9tLCBudWxsQXRvbSwgbnVsbEF0b20pCisgICAgICAgIGFuZCB1c2UgdGhp cyB0byBpbXBsZW1lbnQgSGFzaFRyYWl0czxRdWFsaWZpZWROYW1lPjo6ZW1wdHlWYWx1ZSgpLiBU aGUgb2xkIGltcGxlbWVudGF0aW9uIHdvdWxkCisgICAgICAgIGNyZWF0ZSBhIG5ldyBRdWFsaWZp ZWROYW1lKG51bGxBdG9tLCBudWxsQXRvbSwgbnVsbEF0b20pIGVhY2ggdGltZSwgd2hpY2ggaGFk IHRvIGJlIGhhc2hlZCwKKyAgICAgICAgYWRkZWQgdG8gIHRoZSBnbG9iYWwgUXVhbGlmaWVkTmFt ZSBjYWNoZSwgZXRjLgorCisgICAgICAgIEZpbmFsbHksIGRvbid0IGhhdmUgU1ZHQXR0cmlidXRl SGFzaFRyYW5zbGF0b3IgY3JlYXRlIGEgdGVtcG9yYXJ5IFF1YWxpZmllZE5hbWUganVzdCB0byBj b21wdXRlCisgICAgICAgIHRoZSBoYXNoIG9mIGEgKG5hbWVzcGFjZSwgcHJlZml4LCBsb2NhbE5h bWUpIHR1cGxlLCB1c2UgUXVhbGlmaWVkTmFtZUNvbXBvbmVudHMgYW5kIGhhc2hDb21wb25lbnRz KCkKKyAgICAgICAgZGlyZWN0bHkgaW5zdGVhZC4KKworICAgICAgICBBbHRvZ2V0aGVyIHRoaXMg c2hhdmVzIH4xMDBtcyBvZmYgb2YgdGhlIFJvYm9Ib3JuZXQgc3ZncmVzaXplLmh0bWwgYmVuY2ht YXJrIG9uIG15IE1CUC4KKworICAgICAgICAqIGRvbS9RdWFsaWZpZWROYW1lLmNwcDoKKyAgICAg ICAgKFdlYkNvcmU6Om51bGxRTmFtZSk6CisgICAgICAgICogZG9tL1F1YWxpZmllZE5hbWUuaDoK KyAgICAgICAgKFF1YWxpZmllZE5hbWVJbXBsKToKKyAgICAgICAgKFdlYkNvcmU6OlF1YWxpZmll ZE5hbWU6OlF1YWxpZmllZE5hbWVJbXBsOjpRdWFsaWZpZWROYW1lSW1wbCk6CisgICAgICAgIChX ZWJDb3JlOjpRdWFsaWZpZWROYW1lSGFzaDo6aGFzaCk6CisgICAgICAgICogc3ZnL1NWR0VsZW1l bnQuaDoKKyAgICAgICAgKFdlYkNvcmU6OlNWR0F0dHJpYnV0ZUhhc2hUcmFuc2xhdG9yOjpoYXNo KToKKworMjAxMi0xMC0xNSAgQW5kcmVhcyBLbGluZyAgPGtsaW5nQHdlYmtpdC5vcmc+CisKICAg ICAgICAgUmVtb3ZlIFdURjo6ZmFzdERlbGV0ZUFsbFZhbHVlcygpLgogICAgICAgICA8aHR0cDov L3dlYmtpdC5vcmcvYi85OTM0NT4KIApkaWZmIC0tZ2l0IGEvU291cmNlL1dlYkNvcmUvZG9tL1F1 YWxpZmllZE5hbWUuY3BwIGIvU291cmNlL1dlYkNvcmUvZG9tL1F1YWxpZmllZE5hbWUuY3BwCmlu ZGV4IDc4MzYwNDcuLjA5ODljNDUgMTAwNjQ0Ci0tLSBhL1NvdXJjZS9XZWJDb3JlL2RvbS9RdWFs aWZpZWROYW1lLmNwcAorKysgYi9Tb3VyY2UvV2ViQ29yZS9kb20vUXVhbGlmaWVkTmFtZS5jcHAK QEAgLTEzNSw2ICsxMzUsMTIgQEAgdm9pZCBRdWFsaWZpZWROYW1lOjppbml0KCkKICAgICB9CiB9 CiAKK2NvbnN0IFF1YWxpZmllZE5hbWUmIG51bGxRTmFtZSgpCit7CisgICAgREVGSU5FX1NUQVRJ Q19MT0NBTChRdWFsaWZpZWROYW1lLCBudWxsTmFtZSwgKG51bGxBdG9tLCBudWxsQXRvbSwgbnVs bEF0b20pKTsKKyAgICByZXR1cm4gbnVsbE5hbWU7Cit9CisKIGNvbnN0IEF0b21pY1N0cmluZyYg UXVhbGlmaWVkTmFtZTo6bG9jYWxOYW1lVXBwZXIoKSBjb25zdAogewogICAgIGlmICghbV9pbXBs LT5tX2xvY2FsTmFtZVVwcGVyKQpkaWZmIC0tZ2l0IGEvU291cmNlL1dlYkNvcmUvZG9tL1F1YWxp ZmllZE5hbWUuaCBiL1NvdXJjZS9XZWJDb3JlL2RvbS9RdWFsaWZpZWROYW1lLmgKaW5kZXggMjhm YWI1NS4uMzJjMzMyZiAxMDA2NDQKLS0tIGEvU291cmNlL1dlYkNvcmUvZG9tL1F1YWxpZmllZE5h bWUuaAorKysgYi9Tb3VyY2UvV2ViQ29yZS9kb20vUXVhbGlmaWVkTmFtZS5oCkBAIC00NCw2ICs0 NCw3IEBAIHB1YmxpYzoKICAgICAgICAgICAgIHJldHVybiBhZG9wdFJlZihuZXcgUXVhbGlmaWVk TmFtZUltcGwocHJlZml4LCBsb2NhbE5hbWUsIG5hbWVzcGFjZVVSSSkpOwogICAgICAgICB9CiAK KyAgICAgICAgbXV0YWJsZSB1bnNpZ25lZCBtX2V4aXN0aW5nSGFzaDsKICAgICAgICAgY29uc3Qg QXRvbWljU3RyaW5nIG1fcHJlZml4OwogICAgICAgICBjb25zdCBBdG9taWNTdHJpbmcgbV9sb2Nh bE5hbWU7CiAgICAgICAgIGNvbnN0IEF0b21pY1N0cmluZyBtX25hbWVzcGFjZTsKQEAgLTUzLDcg KzU0LDggQEAgcHVibGljOgogCiAgICAgcHJpdmF0ZToKICAgICAgICAgUXVhbGlmaWVkTmFtZUlt cGwoY29uc3QgQXRvbWljU3RyaW5nJiBwcmVmaXgsIGNvbnN0IEF0b21pY1N0cmluZyYgbG9jYWxO YW1lLCBjb25zdCBBdG9taWNTdHJpbmcmIG5hbWVzcGFjZVVSSSkKLSAgICAgICAgICAgIDogbV9w cmVmaXgocHJlZml4KQorICAgICAgICAgICAgOiBtX2V4aXN0aW5nSGFzaCgwKQorICAgICAgICAg ICAgLCBtX3ByZWZpeChwcmVmaXgpCiAgICAgICAgICAgICAsIG1fbG9jYWxOYW1lKGxvY2FsTmFt ZSkKICAgICAgICAgICAgICwgbV9uYW1lc3BhY2UobmFtZXNwYWNlVVJJKQogICAgICAgICB7CkBA IC0xMTAsNiArMTEyLDggQEAgZXh0ZXJuIGNvbnN0IFF1YWxpZmllZE5hbWUgYW55TmFtZTsKIGlu bGluZSBjb25zdCBRdWFsaWZpZWROYW1lJiBhbnlRTmFtZSgpIHsgcmV0dXJuIGFueU5hbWU7IH0K ICNlbmRpZgogCitjb25zdCBRdWFsaWZpZWROYW1lJiBudWxsUU5hbWUoKTsKKwogaW5saW5lIGJv b2wgb3BlcmF0b3I9PShjb25zdCBBdG9taWNTdHJpbmcmIGEsIGNvbnN0IFF1YWxpZmllZE5hbWUm IHEpIHsgcmV0dXJuIGEgPT0gcS5sb2NhbE5hbWUoKTsgfQogaW5saW5lIGJvb2wgb3BlcmF0b3Ih PShjb25zdCBBdG9taWNTdHJpbmcmIGEsIGNvbnN0IFF1YWxpZmllZE5hbWUmIHEpIHsgcmV0dXJu IGEgIT0gcS5sb2NhbE5hbWUoKTsgfQogaW5saW5lIGJvb2wgb3BlcmF0b3I9PShjb25zdCBRdWFs aWZpZWROYW1lJiBxLCBjb25zdCBBdG9taWNTdHJpbmcmIGEpIHsgcmV0dXJuIGEgPT0gcS5sb2Nh bE5hbWUoKTsgfQpAQCAtMTI1LDggKzEyOSwxMSBAQCBzdHJ1Y3QgUXVhbGlmaWVkTmFtZUhhc2gg ewogCiAgICAgc3RhdGljIHVuc2lnbmVkIGhhc2goY29uc3QgUXVhbGlmaWVkTmFtZTo6UXVhbGlm aWVkTmFtZUltcGwqIG5hbWUpIAogICAgIHsKLSAgICAgICAgUXVhbGlmaWVkTmFtZUNvbXBvbmVu dHMgYyA9IHsgbmFtZS0+bV9wcmVmaXguaW1wbCgpLCBuYW1lLT5tX2xvY2FsTmFtZS5pbXBsKCks IG5hbWUtPm1fbmFtZXNwYWNlLmltcGwoKSB9OwotICAgICAgICByZXR1cm4gaGFzaENvbXBvbmVu dHMoYyk7CisgICAgICAgIGlmICghbmFtZS0+bV9leGlzdGluZ0hhc2gpIHsKKyAgICAgICAgICAg IFF1YWxpZmllZE5hbWVDb21wb25lbnRzIGMgPSB7IG5hbWUtPm1fcHJlZml4LmltcGwoKSwgbmFt ZS0+bV9sb2NhbE5hbWUuaW1wbCgpLCBuYW1lLT5tX25hbWVzcGFjZS5pbXBsKCkgfTsKKyAgICAg ICAgICAgIG5hbWUtPm1fZXhpc3RpbmdIYXNoID0gaGFzaENvbXBvbmVudHMoYyk7CisgICAgICAg IH0KKyAgICAgICAgcmV0dXJuIG5hbWUtPm1fZXhpc3RpbmdIYXNoOwogICAgIH0KIAogICAgIHN0 YXRpYyBib29sIGVxdWFsKGNvbnN0IFF1YWxpZmllZE5hbWUmIGEsIGNvbnN0IFF1YWxpZmllZE5h bWUmIGIpIHsgcmV0dXJuIGEgPT0gYjsgfQpAQCAtMTUwLDcgKzE1Nyw3IEBAIG5hbWVzcGFjZSBX VEYgewogICAgIAogICAgIHRlbXBsYXRlPD4gc3RydWN0IEhhc2hUcmFpdHM8V2ViQ29yZTo6UXVh bGlmaWVkTmFtZT4gOiBTaW1wbGVDbGFzc0hhc2hUcmFpdHM8V2ViQ29yZTo6UXVhbGlmaWVkTmFt ZT4gewogICAgICAgICBzdGF0aWMgY29uc3QgYm9vbCBlbXB0eVZhbHVlSXNaZXJvID0gZmFsc2U7 Ci0gICAgICAgIHN0YXRpYyBXZWJDb3JlOjpRdWFsaWZpZWROYW1lIGVtcHR5VmFsdWUoKSB7IHJl dHVybiBXZWJDb3JlOjpRdWFsaWZpZWROYW1lKG51bGxBdG9tLCBudWxsQXRvbSwgbnVsbEF0b20p OyB9CisgICAgICAgIHN0YXRpYyBXZWJDb3JlOjpRdWFsaWZpZWROYW1lIGVtcHR5VmFsdWUoKSB7 IHJldHVybiBXZWJDb3JlOjpudWxsUU5hbWUoKTsgfQogICAgIH07CiB9CiAKZGlmZiAtLWdpdCBh L1NvdXJjZS9XZWJDb3JlL3N2Zy9TVkdFbGVtZW50LmggYi9Tb3VyY2UvV2ViQ29yZS9zdmcvU1ZH RWxlbWVudC5oCmluZGV4IGMzZTZiNjEuLmU3N2E1YjEgMTAwNjQ0Ci0tLSBhL1NvdXJjZS9XZWJD b3JlL3N2Zy9TVkdFbGVtZW50LmgKKysrIGIvU291cmNlL1dlYkNvcmUvc3ZnL1NWR0VsZW1lbnQu aApAQCAtMTU5LDggKzE1OSwxMCBAQCBwcml2YXRlOgogc3RydWN0IFNWR0F0dHJpYnV0ZUhhc2hU cmFuc2xhdG9yIHsKICAgICBzdGF0aWMgdW5zaWduZWQgaGFzaChjb25zdCBRdWFsaWZpZWROYW1l JiBrZXkpCiAgICAgewotICAgICAgICBpZiAoa2V5Lmhhc1ByZWZpeCgpKQotICAgICAgICAgICAg cmV0dXJuIERlZmF1bHRIYXNoPFF1YWxpZmllZE5hbWU+OjpIYXNoOjpoYXNoKFF1YWxpZmllZE5h bWUobnVsbEF0b20sIGtleS5sb2NhbE5hbWUoKSwga2V5Lm5hbWVzcGFjZVVSSSgpKSk7CisgICAg ICAgIGlmIChrZXkuaGFzUHJlZml4KCkpIHsKKyAgICAgICAgICAgIFF1YWxpZmllZE5hbWVDb21w b25lbnRzIGMgPSB7IG51bGxBdG9tLmltcGwoKSwga2V5LmxvY2FsTmFtZSgpLmltcGwoKSwga2V5 Lm5hbWVzcGFjZVVSSSgpLmltcGwoKSB9OworICAgICAgICAgICAgcmV0dXJuIGhhc2hDb21wb25l bnRzKGMpOworICAgICAgICB9CiAgICAgICAgIHJldHVybiBEZWZhdWx0SGFzaDxRdWFsaWZpZWRO YW1lPjo6SGFzaDo6aGFzaChrZXkpOwogICAgIH0KICAgICBzdGF0aWMgYm9vbCBlcXVhbChjb25z dCBRdWFsaWZpZWROYW1lJiBhLCBjb25zdCBRdWFsaWZpZWROYW1lJiBiKSB7IHJldHVybiBhLm1h dGNoZXMoYik7IH0K