15850 2007-11-06 00:27:46 -0800 Failed array lookups cause excessive Identifier creation 2009-03-24 11:30:22 -0700 1 1 1 Unclassified WebKit JavaScriptCore 528+ (Nightly build) Mac OS X 10.4 RESOLVED INVALID P2 Normal --- 1 eric webkit-unassigned emacemac7 ggaren oldest_to_newest 60376 0 eric 2007-11-06 00:27:46 -0800 Failed array lookups cause excessive Identifier creation getOwnPropertySlot has a numeric lookup optimization. However JSObject::getOwnPropertySlot(exec, unsigned, slot&) just defaults to converting the number back to an identifier and calling the original getOwnPropertySlot. It turns out that we hit this slow JSObject path any time we fail a lookup in an array. In SunSpider/tests/crypto-md5.js we have a line: bin[i >> 5] |= .... which hits this all the time since the initial lookup from bin generally fails. We end up making 2 or more identifier conversions in the failure case, instead of 0 in the success case. :( Maciej suggested that in our getProperty loop, we just test the fast-numeric path on the object itself and then give up for the prototypes, converting to an Identifier in that function and calling the non-numeric getOwnPropertySlot as we walk the prototype chain. 60377 1 17056 eric 2007-11-06 00:36:22 -0800 Created attachment 17056 naive fix (1.1% slower on SunSpider) 60378 2 eric 2007-11-06 00:39:58 -0800 Actually, looking at this again, I think we currently only do 1 conversion (I think we only walk down 1 prototype in the Array case), which is already best-case. 60440 3 darin 2007-11-06 15:26:49 -0800 A better way to solve this is to stay in the numeric case all the way up the prototype chain. All we need is some fast way to know that a given prototype has no numeric properties. 60444 4 darin 2007-11-06 16:09:58 -0800 I'm working on this. 60559 5 17111 darin 2007-11-07 08:59:58 -0800 Created attachment 17111 another approach, but no measurable speed-up on SunSpider 114962 6 ap 2009-03-24 10:57:23 -0700 Eric, is this bug still valid? 114977 7 eric 2009-03-24 11:30:22 -0700 No clue. I haven't worked on JSC in a long time. I would expect this is no longer an issue though. 17056 2007-11-06 00:36:22 -0800 2007-11-06 00:36:22 -0800 naive fix (1.1% slower on SunSpider) naive.patch text/plain 1297 eric SW5kZXg6IGtqcy9vYmplY3QuY3BwCj09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT0KLS0tIGtqcy9vYmplY3QuY3BwCShyZXZp c2lvbiAyNzQ2NSkKKysrIGtqcy9vYmplY3QuY3BwCSh3b3JraW5nIGNvcHkpCkBAIC0xNzYsMjAg KzE3NiwzMiBAQCBKU1ZhbHVlICpKU09iamVjdDo6Z2V0KEV4ZWNTdGF0ZSAqZXhlYywgCiAKIGJv b2wgSlNPYmplY3Q6OmdldFByb3BlcnR5U2xvdChFeGVjU3RhdGUgKmV4ZWMsIHVuc2lnbmVkIHBy b3BlcnR5TmFtZSwgUHJvcGVydHlTbG90JiBzbG90KQogewotICBKU09iamVjdCAqaW1wID0gdGhp czsKLSAgCi0gIHdoaWxlICh0cnVlKSB7CisgICAgSlNPYmplY3QqIGltcCA9IHRoaXM7CisKICAg ICBpZiAoaW1wLT5nZXRPd25Qcm9wZXJ0eVNsb3QoZXhlYywgcHJvcGVydHlOYW1lLCBzbG90KSkK LSAgICAgIHJldHVybiB0cnVlOwotICAgIAotICAgIEpTVmFsdWUgKnByb3RvID0gaW1wLT5fcHJv dG87CisgICAgICAgIHJldHVybiB0cnVlOworCisgICAgSlNWYWx1ZSogcHJvdG8gPSBpbXAtPl9w cm90bzsKICAgICBpZiAoIXByb3RvLT5pc09iamVjdCgpKQotICAgICAgYnJlYWs7CisgICAgICAg IHJldHVybiBmYWxzZTsKKworICAgIGltcCA9IHN0YXRpY19jYXN0PEpTT2JqZWN0Kj4ocHJvdG8p OwogICAgIAotICAgIGltcCA9IHN0YXRpY19jYXN0PEpTT2JqZWN0ICo+KHByb3RvKTsKLSAgfQot ICAKLSAgcmV0dXJuIGZhbHNlOworICAgIGlmIChpbXApIHsKKyAgICAgICAgSWRlbnRpZmllciBw cm9wZXJ0eU5hbWVJZGVudCA9IElkZW50aWZpZXI6OmZyb20ocHJvcGVydHlOYW1lKTsKKyAgICAg ICAgd2hpbGUgKHRydWUpIHsKKyAgICAgICAgICAgIGlmIChpbXAtPmdldE93blByb3BlcnR5U2xv dChleGVjLCBwcm9wZXJ0eU5hbWVJZGVudCwgc2xvdCkpCisgICAgICAgICAgICAgICAgcmV0dXJu IHRydWU7CisgICAgICAgICAgICAKKyAgICAgICAgICAgIEpTVmFsdWUqIHByb3RvID0gaW1wLT5f cHJvdG87CisgICAgICAgICAgICBpZiAoIXByb3RvLT5pc09iamVjdCgpKQorICAgICAgICAgICAg ICAgIGJyZWFrOworICAgICAgICAgICAgCisgICAgICAgICAgICBpbXAgPSBzdGF0aWNfY2FzdDxK U09iamVjdCo+KHByb3RvKTsKKyAgICAgICAgfQorICAgIH0KKworICAgIHJldHVybiBmYWxzZTsK IH0KIAogYm9vbCBKU09iamVjdDo6Z2V0T3duUHJvcGVydHlTbG90KEV4ZWNTdGF0ZSAqZXhlYywg dW5zaWduZWQgcHJvcGVydHlOYW1lLCBQcm9wZXJ0eVNsb3QmIHNsb3QpCg== 17111 2007-11-07 08:59:58 -0800 2007-11-07 08:59:58 -0800 another approach, but no measurable speed-up on SunSpider ArrayMissPatch.txt text/plain 5341 darin SW5kZXg6IEphdmFTY3JpcHRDb3JlL2tqcy9vYmplY3QuaAo9PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09Ci0tLSBKYXZhU2Ny aXB0Q29yZS9ranMvb2JqZWN0LmgJKHJldmlzaW9uIDI3NTY4KQorKysgSmF2YVNjcmlwdENvcmUv a2pzL29iamVjdC5oCSh3b3JraW5nIGNvcHkpCkBAIC00NTIsOCArNDUyLDEyIEBAIG5hbWVzcGFj ZSBLSlMgewogICAgIHZvaWQgc2F2ZVByb3BlcnRpZXMoU2F2ZWRQcm9wZXJ0aWVzICZwKSBjb25z dCB7IF9wcm9wLnNhdmUocCk7IH0KICAgICB2b2lkIHJlc3RvcmVQcm9wZXJ0aWVzKGNvbnN0IFNh dmVkUHJvcGVydGllcyAmcCkgeyBfcHJvcC5yZXN0b3JlKHApOyB9CiAKKyAgICAvLyBJdGVyYXRl cyBhbGwgdGhlIHByb3BlcnRpZXMsIHNvIGNhbiBiZSB2ZXJ5IHNsb3cgYW5kIHNob3VsZCBub3Qg YmUgdXNlZCBvbiBhcmJpdHJhcnkgb2JqZWN0cy4KKyAgICBib29sIGhhc1VJbnQzMlByb3BlcnR5 KCkgY29uc3QgeyByZXR1cm4gX3Byb3AuY29udGFpbnNVSW50MzJQcm9wZXJ0eSgpOyB9CisKICAg ICB2aXJ0dWFsIGJvb2wgaXNBY3RpdmF0aW9uKCkgeyByZXR1cm4gZmFsc2U7IH0KICAgICB2aXJ0 dWFsIGJvb2wgaXNHbG9iYWxPYmplY3QoKSBjb25zdCB7IHJldHVybiBmYWxzZTsgfQorCiAgIHBy b3RlY3RlZDoKICAgICBQcm9wZXJ0eU1hcCBfcHJvcDsKICAgcHJpdmF0ZToKSW5kZXg6IEphdmFT Y3JpcHRDb3JlL2tqcy9vYmplY3Rfb2JqZWN0LmNwcAo9PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09Ci0tLSBKYXZhU2NyaXB0 Q29yZS9ranMvb2JqZWN0X29iamVjdC5jcHAJKHJldmlzaW9uIDI3NTY4KQorKysgSmF2YVNjcmlw dENvcmUva2pzL29iamVjdF9vYmplY3QuY3BwCSh3b3JraW5nIGNvcHkpCkBAIC0zMiw2ICszMiw3 IEBAIHVzaW5nIG5hbWVzcGFjZSBLSlM7CiAKIE9iamVjdFByb3RvdHlwZTo6T2JqZWN0UHJvdG90 eXBlKEV4ZWNTdGF0ZSogZXhlYywgRnVuY3Rpb25Qcm90b3R5cGUqIGZ1bmNQcm90bykKICAgOiBK U09iamVjdCgpIC8vIFtbUHJvdG90eXBlXV0gaXMgbnVsbAorICAsIG1fc3RhdHVzKERvZXNOb3RI YXZlVUludDMyUHJvcGVydHkpCiB7CiAgICAgc3RhdGljIGNvbnN0IElkZW50aWZpZXIqIGhhc093 blByb3BlcnR5UHJvcGVydHlOYW1lID0gbmV3IElkZW50aWZpZXIoImhhc093blByb3BlcnR5Iik7 CiAgICAgc3RhdGljIGNvbnN0IElkZW50aWZpZXIqIHByb3BlcnR5SXNFbnVtZXJhYmxlUHJvcGVy dHlOYW1lID0gbmV3IElkZW50aWZpZXIoInByb3BlcnR5SXNFbnVtZXJhYmxlIik7CkBAIC01NSw2 ICs1NiwzOSBAQCBPYmplY3RQcm90b3R5cGU6Ok9iamVjdFByb3RvdHlwZShFeGVjU3RhCiAgICAg cHV0RGlyZWN0RnVuY3Rpb24obmV3IE9iamVjdFByb3RvRnVuYyhleGVjLCBmdW5jUHJvdG8sIE9i amVjdFByb3RvRnVuYzo6TG9va3VwU2V0dGVyLCAxLCAqbG9va3VwU2V0dGVyUHJvcGVydHlOYW1l KSwgRG9udEVudW0pOwogfQogCitib29sIE9iamVjdFByb3RvdHlwZTo6Z2V0T3duUHJvcGVydHlT bG90KEV4ZWNTdGF0ZSogZXhlYywgdW5zaWduZWQgcHJvcGVydHlOYW1lLCBQcm9wZXJ0eVNsb3Qm IHNsb3QpCit7CisgICAgc3dpdGNoIChtX3N0YXR1cykgeworICAgICAgICBjYXNlIERvZXNOb3RI YXZlVUludDMyUHJvcGVydHk6CisgICAgICAgICAgICByZXR1cm4gZmFsc2U7CisgICAgICAgIGNh c2UgSGFzVUludDMyUHJvcGVydHk6CisgICAgICAgICAgICByZXR1cm4gSlNPYmplY3Q6OmdldE93 blByb3BlcnR5U2xvdChleGVjLCBwcm9wZXJ0eU5hbWUsIHNsb3QpOworICAgICAgICBjYXNlIFVJ bnQzMlByb3BlcnR5U3RhdHVzVW5rbm93bjoKKyAgICAgICAgICAgIGJyZWFrOworICAgIH0KKyAg ICBpZiAoIWhhc1VJbnQzMlByb3BlcnR5KCkpIHsKKyAgICAgICAgbV9zdGF0dXMgPSBEb2VzTm90 SGF2ZVVJbnQzMlByb3BlcnR5OworICAgICAgICByZXR1cm4gZmFsc2U7CisgICAgfQorICAgIG1f c3RhdHVzID0gSGFzVUludDMyUHJvcGVydHk7CisgICAgcmV0dXJuIEpTT2JqZWN0OjpnZXRPd25Q cm9wZXJ0eVNsb3QoZXhlYywgcHJvcGVydHlOYW1lLCBzbG90KTsKK30KKwordm9pZCBPYmplY3RQ cm90b3R5cGU6OnB1dChFeGVjU3RhdGUqIGV4ZWMsIGNvbnN0IElkZW50aWZpZXImIHByb3BlcnR5 TmFtZSwgSlNWYWx1ZSogdmFsdWUsIGludCBhdHRyaWJ1dGVzKQoreworICAgIEpTT2JqZWN0Ojpw dXQoZXhlYywgcHJvcGVydHlOYW1lLCB2YWx1ZSwgYXR0cmlidXRlcyk7CisgICAgaWYgKG1fc3Rh dHVzID09IERvZXNOb3RIYXZlVUludDMyUHJvcGVydHkpCisgICAgICAgIG1fc3RhdHVzID0gVUlu dDMyUHJvcGVydHlTdGF0dXNVbmtub3duOworfQorCitib29sIE9iamVjdFByb3RvdHlwZTo6ZGVs ZXRlUHJvcGVydHkoRXhlY1N0YXRlKiBleGVjLCBjb25zdCBJZGVudGlmaWVyJiBwcm9wZXJ0eU5h bWUpCit7CisgICAgaWYgKCFKU09iamVjdDo6ZGVsZXRlUHJvcGVydHkoZXhlYywgcHJvcGVydHlO YW1lKSkKKyAgICAgICAgcmV0dXJuIGZhbHNlOworICAgIGlmIChtX3N0YXR1cyA9PSBIYXNVSW50 MzJQcm9wZXJ0eSkKKyAgICAgICAgbV9zdGF0dXMgPSBVSW50MzJQcm9wZXJ0eVN0YXR1c1Vua25v d247CisgICAgcmV0dXJuIHRydWU7Cit9CiAKIC8vIC0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0t LS0tLSBPYmplY3RQcm90b0Z1bmMgLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0KIApJ bmRleDogSmF2YVNjcmlwdENvcmUva2pzL29iamVjdF9vYmplY3QuaAo9PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09Ci0tLSBK YXZhU2NyaXB0Q29yZS9ranMvb2JqZWN0X29iamVjdC5oCShyZXZpc2lvbiAyNzU2OCkKKysrIEph dmFTY3JpcHRDb3JlL2tqcy9vYmplY3Rfb2JqZWN0LmgJKHdvcmtpbmcgY29weSkKQEAgLTE5LDgg KzE5LDggQEAKICAqCiAgKi8KIAotI2lmbmRlZiBfT0JKRUNUX09CSkVDVF9IXwotI2RlZmluZSBf T0JKRUNUX09CSkVDVF9IXworI2lmbmRlZiBPQkpFQ1RfT0JKRUNUX0gKKyNkZWZpbmUgT0JKRUNU X09CSkVDVF9ICiAKICNpbmNsdWRlICJmdW5jdGlvbi5oIgogCkBAIC0zNiw3ICszNiwxNiBAQCBu YW1lc3BhY2UgS0pTIHsKICAgICovCiAgIGNsYXNzIE9iamVjdFByb3RvdHlwZSA6IHB1YmxpYyBK U09iamVjdCB7CiAgIHB1YmxpYzoKLSAgICBPYmplY3RQcm90b3R5cGUoRXhlY1N0YXRlICpleGVj LCBGdW5jdGlvblByb3RvdHlwZSAqZnVuY1Byb3RvKTsKKyAgICBPYmplY3RQcm90b3R5cGUoRXhl Y1N0YXRlKiwgRnVuY3Rpb25Qcm90b3R5cGUqKTsKKworICAgIHZpcnR1YWwgYm9vbCBnZXRPd25Q cm9wZXJ0eVNsb3QoRXhlY1N0YXRlKiwgdW5zaWduZWQsIFByb3BlcnR5U2xvdCYpOworCisgICAg dmlydHVhbCB2b2lkIHB1dChFeGVjU3RhdGUqLCBjb25zdCBJZGVudGlmaWVyJiwgSlNWYWx1ZSos IGludCBhdHRyaWJ1dGVzKTsKKyAgICB2aXJ0dWFsIGJvb2wgZGVsZXRlUHJvcGVydHkoRXhlY1N0 YXRlKiwgY29uc3QgSWRlbnRpZmllciYpOworCisgIHByaXZhdGU6CisgICAgZW51bSBVSW50MzJQ cm9wZXJ0eVN0YXR1cyB7IERvZXNOb3RIYXZlVUludDMyUHJvcGVydHksIEhhc1VJbnQzMlByb3Bl cnR5LCBVSW50MzJQcm9wZXJ0eVN0YXR1c1Vua25vd24gfTsKKyAgICBVSW50MzJQcm9wZXJ0eVN0 YXR1cyBtX3N0YXR1czsKICAgfTsKIAogICAvKioKSW5kZXg6IEphdmFTY3JpcHRDb3JlL2tqcy9w cm9wZXJ0eV9tYXAuY3BwCj09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT0KLS0tIEphdmFTY3JpcHRDb3JlL2tqcy9wcm9wZXJ0 eV9tYXAuY3BwCShyZXZpc2lvbiAyNzU2OCkKKysrIEphdmFTY3JpcHRDb3JlL2tqcy9wcm9wZXJ0 eV9tYXAuY3BwCSh3b3JraW5nIGNvcHkpCkBAIC02NjksNiArNjY5LDMxIEBAIGJvb2wgUHJvcGVy dHlNYXA6OmNvbnRhaW5zR2V0dGVyc09yU2V0dGUKICAgICByZXR1cm4gZmFsc2U7CiB9CiAKK2Jv b2wgUHJvcGVydHlNYXA6OmNvbnRhaW5zVUludDMyUHJvcGVydHkoKSBjb25zdAoreworICAgIGlm ICghbV91c2luZ1RhYmxlKSB7CisjaWYgVVNFX1NJTkdMRV9FTlRSWQorICAgICAgICBib29sIGlz VUludDMyOworICAgICAgICBVU3RyaW5nKG1fc2luZ2xlRW50cnlLZXkpLnRvU3RyaWN0VUludDMy KCZpc1VJbnQzMik7CisgICAgICAgIHJldHVybiBpc1VJbnQzMjsKKyNlbHNlCisgICAgICAgIHJl dHVybiBmYWxzZTsKKyNlbmRpZgorICAgIH0KKworICAgIHVuc2lnbmVkIGVudHJ5Q291bnQgPSBt X3UudGFibGUtPmtleUNvdW50ICsgbV91LnRhYmxlLT5kZWxldGVkU2VudGluZWxDb3VudDsKKyAg ICBmb3IgKHVuc2lnbmVkIGkgPSAxOyBpIDw9IGVudHJ5Q291bnQ7IGkrKykgeworICAgICAgICBp ZiAobV91LnRhYmxlLT5lbnRyaWVzKClbaV0ua2V5KSB7CisgICAgICAgICAgICBib29sIGlzVUlu dDMyOworICAgICAgICAgICAgVVN0cmluZyhtX3UudGFibGUtPmVudHJpZXMoKVtpXS5rZXkpLnRv U3RyaWN0VUludDMyKCZpc1VJbnQzMik7CisgICAgICAgICAgICBpZiAoaXNVSW50MzIpCisgICAg ICAgICAgICAgICAgcmV0dXJuIHRydWU7CisgICAgICAgIH0KKyAgICB9CisKKyAgICByZXR1cm4g ZmFsc2U7Cit9CisKIHZvaWQgUHJvcGVydHlNYXA6OmdldEVudW1lcmFibGVQcm9wZXJ0eU5hbWVz KFByb3BlcnR5TmFtZUFycmF5JiBwcm9wZXJ0eU5hbWVzKSBjb25zdAogewogICAgIGlmICghbV91 c2luZ1RhYmxlKSB7CkluZGV4OiBKYXZhU2NyaXB0Q29yZS9ranMvcHJvcGVydHlfbWFwLmgKPT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PQotLS0gSmF2YVNjcmlwdENvcmUva2pzL3Byb3BlcnR5X21hcC5oCShyZXZpc2lvbiAy NzU2OCkKKysrIEphdmFTY3JpcHRDb3JlL2tqcy9wcm9wZXJ0eV9tYXAuaAkod29ya2luZyBjb3B5 KQpAQCAtNjksNiArNjksNyBAQCBuYW1lc3BhY2UgS0pTIHsKICAgICAgICAgdm9pZCBzZXRIYXNH ZXR0ZXJTZXR0ZXJQcm9wZXJ0aWVzKGJvb2wgZikgeyBtX2dldHRlclNldHRlckZsYWcgPSBmOyB9 CiAKICAgICAgICAgYm9vbCBjb250YWluc0dldHRlcnNPclNldHRlcnMoKSBjb25zdDsKKyAgICAg ICAgYm9vbCBjb250YWluc1VJbnQzMlByb3BlcnR5KCkgY29uc3Q7CiAKICAgICBwcml2YXRlOgog ICAgICAgICB0eXBlZGVmIFByb3BlcnR5TWFwRW50cnkgRW50cnk7Cg==