74284 2011-12-12 04:01:06 -0800 Bloom filter has unnecesary collisions 2011-12-14 05:52:18 -0800 1 1 1 Unclassified WebKit CSS 528+ (Nightly build) Unspecified Unspecified RESOLVED FIXED P2 Minor --- 0 allan.jensen allan.jensen kling koivisto macpherson mjs webkit.review.bot oldest_to_newest 519122 0 allan.jensen 2011-12-12 04:01:06 -0800 The bloom filter used to optimize tag, id and class selectors on ancestor has a minor inefficiency in that the value those three different types all use the same hash value in the bloom-filter. This means that if a site uses a class or id-selector on something that is also a common tag name, it bloom-filter will produce unnecessary false positives and forcing the styler into slow path. My proposed solution is to add a salt to the hash so that the different selectors only collide by random chance, not because they use common words. This is an minor optimization only, not a functionality bug. 519124 1 118772 allan.jensen 2011-12-12 04:02:20 -0800 Created attachment 118772 Patch 519189 2 118772 koivisto 2011-12-12 07:43:16 -0800 Comment on attachment 118772 Patch View in context: https://bugs.webkit.org/attachment.cgi?id=118772&action=review r=me, with a comment > Source/WebCore/css/SelectorChecker.cpp:85 > + identifierHashes.append(element->localName().impl()->existingHash() * TagNameSalt); It might consider adding an inline function for computing hash type from AtomicString. 519264 3 koivisto 2011-12-12 09:15:52 -0800 s/It/You/ 520882 4 118772 webkit.review.bot 2011-12-14 05:52:13 -0800 Comment on attachment 118772 Patch Clearing flags on attachment: 118772 Committed r102770: <http://trac.webkit.org/changeset/102770> 520883 5 webkit.review.bot 2011-12-14 05:52:18 -0800 All reviewed patches have been landed. Closing bug. 118772 2011-12-12 04:02:20 -0800 2011-12-14 05:52:13 -0800 Patch bug-74284-20111212130018.patch text/plain 4381 allan.jensen U3VidmVyc2lvbiBSZXZpc2lvbjogMTAyNTY1CmRpZmYgLS1naXQgYS9Tb3VyY2UvV2ViQ29yZS9D aGFuZ2VMb2cgYi9Tb3VyY2UvV2ViQ29yZS9DaGFuZ2VMb2cKaW5kZXggZGY2OWZhYjMxNGU4M2Ex MGU1ZWU2MWZmOGE0NTcyYjA3M2FiNGI4Mi4uZDg5MGE1YzdmZTllOWEyMGExYjcyMmZjM2VhNDRj ZTJhZTc2ZDQzNiAxMDA2NDQKLS0tIGEvU291cmNlL1dlYkNvcmUvQ2hhbmdlTG9nCisrKyBiL1Nv dXJjZS9XZWJDb3JlL0NoYW5nZUxvZwpAQCAtMSwzICsxLDE3IEBACisyMDExLTEyLTEyICBBbGxh biBTYW5kZmVsZCBKZW5zZW4gIDxhbGxhbi5qZW5zZW5Abm9raWEuY29tPgorCisgICAgICAgIEFk ZCBkaWZmZXJlbnQgc2FsdCB0byBkaWZmZXJlbnQgdHlwZXMgb2Ygc2VsZWN0b3JzLiBTbyB0aGUg Q1NTIGZhc3QKKyAgICAgICAgcGF0aCBjYW4gdGVsbCB0aGUgZGlmZmVyZW50IGJldHdlZW4gdGFn cyBhbmQgY2xhc3MgYXR0cmlidXRlcyB3aXRoCisgICAgICAgIG90aGVyd2lzZSBpZGVudGljYWwg dmFsdWVzLgorICAgICAgICBodHRwczovL2J1Z3Mud2Via2l0Lm9yZy9zaG93X2J1Zy5jZ2k/aWQ9 NzQyODQKKworICAgICAgICBSZXZpZXdlZCBieSBOT0JPRFkgKE9PUFMhKS4KKworICAgICAgICAq IGNzcy9TZWxlY3RvckNoZWNrZXIuY3BwOgorICAgICAgICAoV2ViQ29yZTo6Y29sbGVjdEVsZW1l bnRJZGVudGlmaWVySGFzaGVzKToKKyAgICAgICAgKFdlYkNvcmU6OmNvbGxlY3REZXNjZW5kYW50 U2VsZWN0b3JJZGVudGlmaWVySGFzaGVzKToKKyAgICAgICAgKiBjc3MvU2VsZWN0b3JDaGVja2Vy Lmg6CisKIDIwMTEtMTItMTIgIE5vZWwgR29yZG9uICA8bm9lbC5nb3Jkb25AZ21haWwuY29tPgog CiAgICAgICAgIFdlYlBJbWFnZURlY29kZXI6IEluY3JlYXNlIGltYWdlL3dlYnAgZGVjb2Rpbmcg cGVyZm9ybWFuY2UgMTAtMjAlCmRpZmYgLS1naXQgYS9Tb3VyY2UvV2ViQ29yZS9jc3MvU2VsZWN0 b3JDaGVja2VyLmNwcCBiL1NvdXJjZS9XZWJDb3JlL2Nzcy9TZWxlY3RvckNoZWNrZXIuY3BwCmlu ZGV4IDJjNWM3MzIwMGQxOTdhZmQ5NmQwOWJlNjllOWVhYTdmYTk5YzFmOWUuLmFhZjAyMjc5NjIx OWQ4ZWQ0MDAxZWE2YzdmOGUwMjhhM2ExZTE1NzEgMTAwNjQ0Ci0tLSBhL1NvdXJjZS9XZWJDb3Jl L2Nzcy9TZWxlY3RvckNoZWNrZXIuY3BwCisrKyBiL1NvdXJjZS9XZWJDb3JlL2Nzcy9TZWxlY3Rv ckNoZWNrZXIuY3BwCkBAIC03NywxNyArNzcsMjAgQEAgU2VsZWN0b3JDaGVja2VyOjpTZWxlY3Rv ckNoZWNrZXIoRG9jdW1lbnQqIGRvY3VtZW50LCBib29sIHN0cmljdFBhcnNpbmcpCiB7CiB9CiAK Ky8vIFNhbHQgdG8gc2VwYXJhdGUgb3RoZXJ3aXNlIGlkZW50aWNhbCBzdHJpbmcgaGFzaGVzIHNv IGEgY2xhc3Mtc2VsZWN0b3IgbGlrZSAuYXJ0aWNsZSB3b24ndCBtYXRjaCA8YXJ0aWNsZT4gZWxl bWVudHMuCitlbnVtIHsgVGFnTmFtZVNhbHQgPSAxMywgSWRBdHRyaWJ1dGVTYWx0ID0gMTcsIENs YXNzQXR0cmlidXRlU2FsdCA9IDE5IH07CisKIHN0YXRpYyBpbmxpbmUgdm9pZCBjb2xsZWN0RWxl bWVudElkZW50aWZpZXJIYXNoZXMoY29uc3QgRWxlbWVudCogZWxlbWVudCwgVmVjdG9yPHVuc2ln bmVkLCA0PiYgaWRlbnRpZmllckhhc2hlcykKIHsKLSAgICBpZGVudGlmaWVySGFzaGVzLmFwcGVu ZChlbGVtZW50LT5sb2NhbE5hbWUoKS5pbXBsKCktPmV4aXN0aW5nSGFzaCgpKTsKKyAgICBpZGVu dGlmaWVySGFzaGVzLmFwcGVuZChlbGVtZW50LT5sb2NhbE5hbWUoKS5pbXBsKCktPmV4aXN0aW5n SGFzaCgpICogVGFnTmFtZVNhbHQpOwogICAgIGlmIChlbGVtZW50LT5oYXNJRCgpKQotICAgICAg ICBpZGVudGlmaWVySGFzaGVzLmFwcGVuZChlbGVtZW50LT5pZEZvclN0eWxlUmVzb2x1dGlvbigp LmltcGwoKS0+ZXhpc3RpbmdIYXNoKCkpOworICAgICAgICBpZGVudGlmaWVySGFzaGVzLmFwcGVu ZChlbGVtZW50LT5pZEZvclN0eWxlUmVzb2x1dGlvbigpLmltcGwoKS0+ZXhpc3RpbmdIYXNoKCkg KiBJZEF0dHJpYnV0ZVNhbHQpOwogICAgIGNvbnN0IFN0eWxlZEVsZW1lbnQqIHN0eWxlZEVsZW1l bnQgPSBlbGVtZW50LT5pc1N0eWxlZEVsZW1lbnQoKSA/IHN0YXRpY19jYXN0PGNvbnN0IFN0eWxl ZEVsZW1lbnQqPihlbGVtZW50KSA6IDA7CiAgICAgaWYgKHN0eWxlZEVsZW1lbnQgJiYgc3R5bGVk RWxlbWVudC0+aGFzQ2xhc3MoKSkgewogICAgICAgICBjb25zdCBTcGFjZVNwbGl0U3RyaW5nJiBj bGFzc05hbWVzID0gc3R5bGVkRWxlbWVudC0+Y2xhc3NOYW1lcygpOwogICAgICAgICBzaXplX3Qg Y291bnQgPSBjbGFzc05hbWVzLnNpemUoKTsKICAgICAgICAgZm9yIChzaXplX3QgaSA9IDA7IGkg PCBjb3VudDsgKytpKQotICAgICAgICAgICAgaWRlbnRpZmllckhhc2hlcy5hcHBlbmQoY2xhc3NO YW1lc1tpXS5pbXBsKCktPmV4aXN0aW5nSGFzaCgpKTsKKyAgICAgICAgICAgIGlkZW50aWZpZXJI YXNoZXMuYXBwZW5kKGNsYXNzTmFtZXNbaV0uaW1wbCgpLT5leGlzdGluZ0hhc2goKSAqIENsYXNz QXR0cmlidXRlU2FsdCk7CiAgICAgfQogfQogCkBAIC0xNjEsMTMgKzE2NCwyMyBAQCB2b2lkIFNl bGVjdG9yQ2hlY2tlcjo6cG9wUGFyZW50KEVsZW1lbnQqIHBhcmVudCkKIAogc3RhdGljIGlubGlu ZSB2b2lkIGNvbGxlY3REZXNjZW5kYW50U2VsZWN0b3JJZGVudGlmaWVySGFzaGVzKGNvbnN0IENT U1NlbGVjdG9yKiBzZWxlY3RvciwgdW5zaWduZWQqJiBoYXNoLCBjb25zdCB1bnNpZ25lZCogZW5k KQogewotICAgIGlmICgoc2VsZWN0b3ItPm1fbWF0Y2ggPT0gQ1NTU2VsZWN0b3I6OklkIHx8IHNl bGVjdG9yLT5tX21hdGNoID09IENTU1NlbGVjdG9yOjpDbGFzcykgJiYgIXNlbGVjdG9yLT52YWx1 ZSgpLmlzRW1wdHkoKSkKLSAgICAgICAgKCpoYXNoKyspID0gc2VsZWN0b3ItPnZhbHVlKCkuaW1w bCgpLT5leGlzdGluZ0hhc2goKTsKKyAgICBzd2l0Y2ggKHNlbGVjdG9yLT5tX21hdGNoKSB7Cisg ICAgY2FzZSBDU1NTZWxlY3Rvcjo6SWQ6CisgICAgICAgIGlmICghc2VsZWN0b3ItPnZhbHVlKCku aXNFbXB0eSgpKQorICAgICAgICAgICAgKCpoYXNoKyspID0gc2VsZWN0b3ItPnZhbHVlKCkuaW1w bCgpLT5leGlzdGluZ0hhc2goKSAqIElkQXR0cmlidXRlU2FsdDsKKyAgICAgICAgYnJlYWs7Cisg ICAgY2FzZSBDU1NTZWxlY3Rvcjo6Q2xhc3M6CisgICAgICAgIGlmICghc2VsZWN0b3ItPnZhbHVl KCkuaXNFbXB0eSgpKQorICAgICAgICAgICAgKCpoYXNoKyspID0gc2VsZWN0b3ItPnZhbHVlKCku aW1wbCgpLT5leGlzdGluZ0hhc2goKSAqIENsYXNzQXR0cmlidXRlU2FsdDsKKyAgICAgICAgYnJl YWs7CisgICAgZGVmYXVsdDoKKyAgICAgICAgYnJlYWs7CisgICAgfQogICAgIGlmIChoYXNoID09 IGVuZCkKICAgICAgICAgcmV0dXJuOwogICAgIGNvbnN0IEF0b21pY1N0cmluZyYgbG9jYWxOYW1l ID0gc2VsZWN0b3ItPnRhZygpLmxvY2FsTmFtZSgpOwogICAgIGlmIChsb2NhbE5hbWUgIT0gc3Rh ckF0b20pCi0gICAgICAgICgqaGFzaCsrKSA9IGxvY2FsTmFtZS5pbXBsKCktPmV4aXN0aW5nSGFz aCgpOworICAgICAgICAoKmhhc2grKykgPSBsb2NhbE5hbWUuaW1wbCgpLT5leGlzdGluZ0hhc2go KSAqIFRhZ05hbWVTYWx0OwogfQogCiB2b2lkIFNlbGVjdG9yQ2hlY2tlcjo6Y29sbGVjdElkZW50 aWZpZXJIYXNoZXMoY29uc3QgQ1NTU2VsZWN0b3IqIHNlbGVjdG9yLCB1bnNpZ25lZCogaWRlbnRp Zmllckhhc2hlcywgdW5zaWduZWQgbWF4aW11bUlkZW50aWZpZXJDb3VudCkKZGlmZiAtLWdpdCBh L1NvdXJjZS9XZWJDb3JlL2Nzcy9TZWxlY3RvckNoZWNrZXIuaCBiL1NvdXJjZS9XZWJDb3JlL2Nz cy9TZWxlY3RvckNoZWNrZXIuaAppbmRleCA3NjBiYTUyMDdiZTU3NGM1ZGZlOGE5YTA0Yjk3MDBl NGQwY2RmMjhkLi40OGE2ZDliYThhYTQxZmZmYTVkZDkxNGU2MTkyYmFiOGZlNzg0NzM1IDEwMDY0 NAotLS0gYS9Tb3VyY2UvV2ViQ29yZS9jc3MvU2VsZWN0b3JDaGVja2VyLmgKKysrIGIvU291cmNl L1dlYkNvcmUvY3NzL1NlbGVjdG9yQ2hlY2tlci5oCkBAIC0xMTgsNyArMTE4LDcgQEAgcHJpdmF0 ZToKICAgICAgICAgVmVjdG9yPHVuc2lnbmVkLCA0PiBpZGVudGlmaWVySGFzaGVzOwogICAgIH07 CiAgICAgVmVjdG9yPFBhcmVudFN0YWNrRnJhbWU+IG1fcGFyZW50U3RhY2s7Ci0KKyAgICAKICAg ICAvLyBXaXRoIDEwMCB1bmlxdWUgc3RyaW5ncyBpbiB0aGUgZmlsdGVyLCAyXjEyIHNsb3QgdGFi bGUgaGFzIGZhbHNlIHBvc2l0aXZlIHJhdGUgb2YgfjAuMiUuCiAgICAgc3RhdGljIGNvbnN0IHVu c2lnbmVkIGJsb29tRmlsdGVyS2V5Qml0cyA9IDEyOwogICAgIE93blB0cjxCbG9vbUZpbHRlcjxi bG9vbUZpbHRlcktleUJpdHM+ID4gbV9hbmNlc3RvcklkZW50aWZpZXJGaWx0ZXI7Cg==