21633 2008-10-15 17:43:52 -0700 Avoid using a HashMap when there is only a single transition 2008-10-15 21:38:07 -0700 1 1 1 Unclassified WebKit JavaScriptCore 528+ (Nightly build) All All RESOLVED FIXED P2 Normal --- 21513 1 zwarich zwarich oldest_to_newest 95483 0 zwarich 2008-10-15 17:43:52 -0700 We have determined through testing that the vast majority of StructureIDs have only 0 or 1 transition. We should not create a whole HashMap in these cases. 95490 1 24382 zwarich 2008-10-15 19:10:55 -0700 Created attachment 24382 Proposed patch It would be nice if someone else (Maciej?) ran benchmarks on his own machine to verify. 95494 2 24382 mjs 2008-10-15 20:46:42 -0700 Comment on attachment 24382 Proposed patch r=me But it would be nice if we could abstract away the single-transition optimization a bit, by having some helper functions that hide the core logic (e.g. one to get an existing transition for a property - it could check either the single entry or the hashtable as appropriate) etc. 95497 3 zwarich 2008-10-15 21:38:07 -0700 Landed in r37627. 24382 2008-10-15 19:10:55 -0700 2008-10-15 20:46:42 -0700 Proposed patch single-transition.diff text/plain 5733 zwarich SW5kZXg6IENoYW5nZUxvZwo9PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09Ci0tLSBDaGFuZ2VMb2cJKHJldmlzaW9uIDM3NjIy KQorKysgQ2hhbmdlTG9nCSh3b3JraW5nIGNvcHkpCkBAIC0xLDMgKzEsMjAgQEAKKzIwMDgtMTAt MTUgIENhbWVyb24gWndhcmljaCAgPHp3YXJpY2hAYXBwbGUuY29tPgorCisgICAgICAgIFJldmll d2VkIGJ5IE5PQk9EWSAoT09QUyEpLgorCisgICAgICAgIEJ1ZyAyMTYzMzogQXZvaWQgdXNpbmcg YSBIYXNoTWFwIHdoZW4gdGhlcmUgaXMgb25seSBhIHNpbmdsZSB0cmFuc2l0aW9uCisgICAgICAg IDxodHRwczovL2J1Z3Mud2Via2l0Lm9yZy9zaG93X2J1Zy5jZ2k/aWQ9MjE2MzM+CisKKyAgICAg ICAgVGhpcyBpcyBhIDAuOCUgc3BlZWR1cCBvbiBTdW5TcGlkZXIgYW5kIGJldHdlZW4gYSAwLjUl IGFuZCAxLjAlIHNwZWVkdXAKKyAgICAgICAgb24gdGhlIFY4IGJlbmNobWFyayBzdWl0ZS4KKwor ICAgICAgICAqIGtqcy9TdHJ1Y3R1cmVJRC5jcHA6CisgICAgICAgIChKU0M6OlN0cnVjdHVyZUlE OjpTdHJ1Y3R1cmVJRCk6CisgICAgICAgIChKU0M6OlN0cnVjdHVyZUlEOjp+U3RydWN0dXJlSUQp OgorICAgICAgICAoSlNDOjpTdHJ1Y3R1cmVJRDo6YWRkUHJvcGVydHlUcmFuc2l0aW9uKToKKyAg ICAgICAgKiBranMvU3RydWN0dXJlSUQuaDoKKyAgICAgICAgKEpTQzo6U3RydWN0dXJlSUQ6Oik6 CisKIDIwMDgtMTAtMTUgIEdlb2ZmcmV5IEdhcmVuICA8Z2dhcmVuQGFwcGxlLmNvbT4KIAogICAg ICAgICBSZXZpZXdlZCBieSBDYW1lcm9uIFp3YXJpY2guCkluZGV4OiBranMvU3RydWN0dXJlSUQu Y3BwCj09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT0KLS0tIGtqcy9TdHJ1Y3R1cmVJRC5jcHAJKHJldmlzaW9uIDM3NjIxKQor Kysga2pzL1N0cnVjdHVyZUlELmNwcAkod29ya2luZyBjb3B5KQpAQCAtNTMsMTIgKzUzLDE1IEBA IFN0cnVjdHVyZUlEOjpTdHJ1Y3R1cmVJRChKU1ZhbHVlKiBwcm90b3QKICAgICAsIG1fcHJldmlv dXMoMCkKICAgICAsIG1fbmFtZUluUHJldmlvdXMoMCkKICAgICAsIG1fdHJhbnNpdGlvbkNvdW50 KDApCisgICAgLCBtX3VzaW5nU2luZ2xlVHJhbnNpdGlvblNsb3QodHJ1ZSkKICAgICAsIG1fcHJv cGVydHlTdG9yYWdlQ2FwYWNpdHkoSlNPYmplY3Q6OmlubGluZVN0b3JhZ2VDYXBhY2l0eSkKICAg ICAsIG1fY2FjaGVkVHJhbnNpc3Rpb25PZmZzZXQoV1RGOjpub3RGb3VuZCkKIHsKICAgICBBU1NF UlQobV9wcm90b3R5cGUpOwogICAgIEFTU0VSVChtX3Byb3RvdHlwZS0+aXNPYmplY3QoKSB8fCBt X3Byb3RvdHlwZS0+aXNOdWxsKCkpOwogCisgICAgbV90cmFuc2l0aW9ucy5zaW5nbGVUcmFuc2l0 aW9uID0gMDsKKwogI2lmbmRlZiBOREVCVUcKICAgICBpZiAoc2hvdWxkSWdub3JlTGVha3MpCiAg ICAgICAgIGlnbm9yZVNldC5hZGQodGhpcyk7CkBAIC03MCwxMyArNzMsMjQgQEAgU3RydWN0dXJl SUQ6OlN0cnVjdHVyZUlEKEpTVmFsdWUqIHByb3RvdAogU3RydWN0dXJlSUQ6On5TdHJ1Y3R1cmVJ RCgpCiB7CiAgICAgaWYgKG1fcHJldmlvdXMpIHsKLSAgICAgICAgQVNTRVJUKG1fcHJldmlvdXMt Pm1fdHJhbnNpdGlvblRhYmxlLmNvbnRhaW5zKG1ha2VfcGFpcihtX25hbWVJblByZXZpb3VzLCBt X2F0dHJpYnV0ZXNJblByZXZpb3VzKSkpOwotICAgICAgICBtX3ByZXZpb3VzLT5tX3RyYW5zaXRp b25UYWJsZS5yZW1vdmUobWFrZV9wYWlyKG1fbmFtZUluUHJldmlvdXMsIG1fYXR0cmlidXRlc0lu UHJldmlvdXMpKTsKKyAgICAgICAgaWYgKG1fcHJldmlvdXMtPm1fdXNpbmdTaW5nbGVUcmFuc2l0 aW9uU2xvdCkgeworICAgICAgICAgICAgbV9wcmV2aW91cy0+bV90cmFuc2l0aW9ucy5zaW5nbGVU cmFuc2l0aW9uLT5kZXJlZigpOworICAgICAgICAgICAgbV9wcmV2aW91cy0+bV90cmFuc2l0aW9u cy5zaW5nbGVUcmFuc2l0aW9uID0gMDsKKyAgICAgICAgfSBlbHNlIHsKKyAgICAgICAgICAgIEFT U0VSVChtX3ByZXZpb3VzLT5tX3RyYW5zaXRpb25zLnRhYmxlLT5jb250YWlucyhtYWtlX3BhaXIo bV9uYW1lSW5QcmV2aW91cywgbV9hdHRyaWJ1dGVzSW5QcmV2aW91cykpKTsKKyAgICAgICAgICAg IG1fcHJldmlvdXMtPm1fdHJhbnNpdGlvbnMudGFibGUtPnJlbW92ZShtYWtlX3BhaXIobV9uYW1l SW5QcmV2aW91cywgbV9hdHRyaWJ1dGVzSW5QcmV2aW91cykpOworICAgICAgICB9CiAgICAgfQog CiAgICAgaWYgKG1fY2FjaGVkUHJvcGVydHlOYW1lQXJyYXlEYXRhKQogICAgICAgICBtX2NhY2hl ZFByb3BlcnR5TmFtZUFycmF5RGF0YS0+c2V0Q2FjaGVkU3RydWN0dXJlSUQoMCk7CiAKKyAgICBp ZiAobV91c2luZ1NpbmdsZVRyYW5zaXRpb25TbG90KSB7CisgICAgICAgIGlmIChtX3RyYW5zaXRp b25zLnNpbmdsZVRyYW5zaXRpb24pCisgICAgICAgICAgICBtX3RyYW5zaXRpb25zLnNpbmdsZVRy YW5zaXRpb24tPmRlcmVmKCk7CisgICAgfSBlbHNlCisgICAgICAgIGRlbGV0ZSBtX3RyYW5zaXRp b25zLnRhYmxlOworCiAjaWZuZGVmIE5ERUJVRwogICAgIEhhc2hTZXQ8U3RydWN0dXJlSUQqPjo6 aXRlcmF0b3IgaXQgPSBpZ25vcmVTZXQuZmluZCh0aGlzKTsKICAgICBpZiAoaXQgIT0gaWdub3Jl U2V0LmVuZCgpKQpAQCAtMTY4LDEwICsxODIsMTkgQEAgUGFzc1JlZlB0cjxTdHJ1Y3R1cmVJRD4g U3RydWN0dXJlSUQ6OmFkZAogICAgIEFTU0VSVCghc3RydWN0dXJlSUQtPm1faXNEaWN0aW9uYXJ5 KTsKICAgICBBU1NFUlQoc3RydWN0dXJlSUQtPnR5cGVJbmZvKCkudHlwZSgpID09IE9iamVjdFR5 cGUpOwogCi0gICAgaWYgKFN0cnVjdHVyZUlEKiBleGlzdGluZ1RyYW5zaXRpb24gPSBzdHJ1Y3R1 cmVJRC0+bV90cmFuc2l0aW9uVGFibGUuZ2V0KG1ha2VfcGFpcihwcm9wZXJ0eU5hbWUudXN0cmlu ZygpLnJlcCgpLCBhdHRyaWJ1dGVzKSkpIHsKLSAgICAgICAgb2Zmc2V0ID0gZXhpc3RpbmdUcmFu c2l0aW9uLT5jYWNoZWRUcmFuc2lzdGlvbk9mZnNldCgpOwotICAgICAgICBBU1NFUlQob2Zmc2V0 ICE9IFdURjo6bm90Rm91bmQpOwotICAgICAgICByZXR1cm4gZXhpc3RpbmdUcmFuc2l0aW9uOwor ICAgIGlmIChzdHJ1Y3R1cmVJRC0+bV91c2luZ1NpbmdsZVRyYW5zaXRpb25TbG90KSB7CisgICAg ICAgIFN0cnVjdHVyZUlEKiBleGlzdGluZ1RyYW5zaXRpb24gPSBzdHJ1Y3R1cmVJRC0+bV90cmFu c2l0aW9ucy5zaW5nbGVUcmFuc2l0aW9uOworICAgICAgICBpZiAoZXhpc3RpbmdUcmFuc2l0aW9u ICYmIGV4aXN0aW5nVHJhbnNpdGlvbi0+bV9uYW1lSW5QcmV2aW91cyA9PSBwcm9wZXJ0eU5hbWUu dXN0cmluZygpLnJlcCgpICYmIGV4aXN0aW5nVHJhbnNpdGlvbi0+bV9hdHRyaWJ1dGVzSW5QcmV2 aW91cyA9PSBhdHRyaWJ1dGVzKSB7CisgICAgICAgICAgICBvZmZzZXQgPSBzdHJ1Y3R1cmVJRC0+ bV90cmFuc2l0aW9ucy5zaW5nbGVUcmFuc2l0aW9uLT5jYWNoZWRUcmFuc2lzdGlvbk9mZnNldCgp OworICAgICAgICAgICAgQVNTRVJUKG9mZnNldCAhPSBXVEY6Om5vdEZvdW5kKTsKKyAgICAgICAg ICAgIHJldHVybiBleGlzdGluZ1RyYW5zaXRpb247CisgICAgICAgIH0KKyAgICB9IGVsc2Ugewor ICAgICAgICBpZiAoU3RydWN0dXJlSUQqIGV4aXN0aW5nVHJhbnNpdGlvbiA9IHN0cnVjdHVyZUlE LT5tX3RyYW5zaXRpb25zLnRhYmxlLT5nZXQobWFrZV9wYWlyKHByb3BlcnR5TmFtZS51c3RyaW5n KCkucmVwKCksIGF0dHJpYnV0ZXMpKSkgeworICAgICAgICAgICAgb2Zmc2V0ID0gZXhpc3RpbmdU cmFuc2l0aW9uLT5jYWNoZWRUcmFuc2lzdGlvbk9mZnNldCgpOworICAgICAgICAgICAgQVNTRVJU KG9mZnNldCAhPSBXVEY6Om5vdEZvdW5kKTsKKyAgICAgICAgICAgIHJldHVybiBleGlzdGluZ1Ry YW5zaXRpb247CisgICAgICAgIH0gICAgICAgIAogICAgIH0KIAogICAgIGlmIChzdHJ1Y3R1cmVJ RC0+bV90cmFuc2l0aW9uQ291bnQgPiBzX21heFRyYW5zaXRpb25MZW5ndGgpIHsKQEAgLTE5OCw3 ICsyMjEsMjEgQEAgUGFzc1JlZlB0cjxTdHJ1Y3R1cmVJRD4gU3RydWN0dXJlSUQ6OmFkZAogCiAg ICAgdHJhbnNpdGlvbi0+c2V0Q2FjaGVkVHJhbnNpc3Rpb25PZmZzZXQob2Zmc2V0KTsKIAotICAg IHN0cnVjdHVyZUlELT5tX3RyYW5zaXRpb25UYWJsZS5hZGQobWFrZV9wYWlyKHByb3BlcnR5TmFt ZS51c3RyaW5nKCkucmVwKCksIGF0dHJpYnV0ZXMpLCB0cmFuc2l0aW9uLmdldCgpKTsKKyAgICBp ZiAoc3RydWN0dXJlSUQtPm1fdXNpbmdTaW5nbGVUcmFuc2l0aW9uU2xvdCkgeworICAgICAgICBp ZiAoIXN0cnVjdHVyZUlELT5tX3RyYW5zaXRpb25zLnNpbmdsZVRyYW5zaXRpb24pIHsKKyAgICAg ICAgICAgIHN0cnVjdHVyZUlELT5tX3RyYW5zaXRpb25zLnNpbmdsZVRyYW5zaXRpb24gPSB0cmFu c2l0aW9uLmdldCgpOworICAgICAgICAgICAgdHJhbnNpdGlvbi0+cmVmKCk7CisgICAgICAgICAg ICByZXR1cm4gdHJhbnNpdGlvbi5yZWxlYXNlKCk7CisgICAgICAgIH0KKworICAgICAgICBTdHJ1 Y3R1cmVJRCogZXhpc3RpbmdUcmFuc2l0aW9uID0gc3RydWN0dXJlSUQtPm1fdHJhbnNpdGlvbnMu c2luZ2xlVHJhbnNpdGlvbjsKKyAgICAgICAgc3RydWN0dXJlSUQtPm1fdXNpbmdTaW5nbGVUcmFu c2l0aW9uU2xvdCA9IGZhbHNlOworICAgICAgICBUcmFuc2l0aW9uVGFibGUqIHRyYW5zaXRpb25U YWJsZSA9IG5ldyBUcmFuc2l0aW9uVGFibGU7CisgICAgICAgIHN0cnVjdHVyZUlELT5tX3RyYW5z aXRpb25zLnRhYmxlID0gdHJhbnNpdGlvblRhYmxlOworICAgICAgICB0cmFuc2l0aW9uVGFibGUt PmFkZChtYWtlX3BhaXIoZXhpc3RpbmdUcmFuc2l0aW9uLT5tX25hbWVJblByZXZpb3VzLCBleGlz dGluZ1RyYW5zaXRpb24tPm1fYXR0cmlidXRlc0luUHJldmlvdXMpLCBleGlzdGluZ1RyYW5zaXRp b24pOworICAgICAgICBleGlzdGluZ1RyYW5zaXRpb24tPmRlcmVmKCk7CisgICAgfQorICAgIHN0 cnVjdHVyZUlELT5tX3RyYW5zaXRpb25zLnRhYmxlLT5hZGQobWFrZV9wYWlyKHByb3BlcnR5TmFt ZS51c3RyaW5nKCkucmVwKCksIGF0dHJpYnV0ZXMpLCB0cmFuc2l0aW9uLmdldCgpKTsKICAgICBy ZXR1cm4gdHJhbnNpdGlvbi5yZWxlYXNlKCk7CiB9CiAKSW5kZXg6IGtqcy9TdHJ1Y3R1cmVJRC5o Cj09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT0KLS0tIGtqcy9TdHJ1Y3R1cmVJRC5oCShyZXZpc2lvbiAzNzYyMSkKKysrIGtq cy9TdHJ1Y3R1cmVJRC5oCSh3b3JraW5nIGNvcHkpCkBAIC0xNTIsNyArMTUyLDExIEBAIG5hbWVz cGFjZSBKU0MgewogICAgICAgICB1bnNpZ25lZCBtX2F0dHJpYnV0ZXNJblByZXZpb3VzOwogCiAg ICAgICAgIHNpemVfdCBtX3RyYW5zaXRpb25Db3VudDsKLSAgICAgICAgVHJhbnNpdGlvblRhYmxl IG1fdHJhbnNpdGlvblRhYmxlOworICAgICAgICBib29sIG1fdXNpbmdTaW5nbGVUcmFuc2l0aW9u U2xvdDsKKyAgICAgICAgdW5pb24geworICAgICAgICAgICAgU3RydWN0dXJlSUQqIHNpbmdsZVRy YW5zaXRpb247CisgICAgICAgICAgICBUcmFuc2l0aW9uVGFibGUqIHRhYmxlOworICAgICAgICB9 IG1fdHJhbnNpdGlvbnM7CiAKICAgICAgICAgUmVmUHRyPFByb3BlcnR5TmFtZUFycmF5RGF0YT4g bV9jYWNoZWRQcm9wZXJ0eU5hbWVBcnJheURhdGE7CiAK