218062 2020-10-21 16:49:24 -0700 Replace O(n^2) algorithm from r268709 with O(n) algorithm 2021-03-16 11:01:00 -0700 1 1 1 Unclassified WebKit New Bugs WebKit Nightly Build Unspecified Unspecified RESOLVED FIXED InRadar P2 Normal --- 1 achristensen achristensen ashvayka ggaren webkit-bug-importer oldest_to_newest 1700465 0 achristensen 2020-10-21 16:49:24 -0700 Replace O(n^2) algorithm from r268709 with O(n) algorithm 1700468 1 412047 achristensen 2020-10-21 16:53:02 -0700 Created attachment 412047 Patch 1700536 2 ews-feeder 2020-10-21 21:50:38 -0700 Committed r268852: <https://trac.webkit.org/changeset/268852> All reviewed patches have been landed. Closing bug and clearing flags on attachment 412047. 1700537 3 webkit-bug-importer 2020-10-21 21:51:26 -0700 <rdar://problem/70559804> 1700730 4 412047 ggaren 2020-10-22 10:45:52 -0700 Comment on attachment 412047 Patch View in context: https://bugs.webkit.org/attachment.cgi?id=412047&action=review > Source/WebCore/bindings/js/JSDOMConvertRecord.h:141 > + auto iterator = resultMap.find(typedKey); > + if (iterator != resultMap.end()) { > + ASSERT(result[iterator->value].key == typedKey); > + result[iterator->value].value = WTFMove(typedValue); > continue; > } > + resultMap.add(typedKey, result.size()); You can avoid the double hash lookup here by doing the add first and then checking its result: auto addResult = resultMap.add(typedKey, result.size()); if (!addResult.isNewEntry) { ASSERT(result[addResult.iterator->value].key == typedKey); result[addResult.iterator->value].value = WTFMove(typedValue); continue; } (The default behavior of add() does not overwrite existing entries.) Also: Why are you storing both the key and the value in both data structures? Seems like putting just the key into a HashSet would be slightly more efficient. 1740043 5 ashvayka 2021-03-16 11:01:00 -0700 (In reply to Geoffrey Garen from comment #4) > You can avoid the double hash lookup here by doing the add first and then > checking its result: I've applied this comment as part of https://bugs.webkit.org/show_bug.cgi?id=223219. Thanks! > Also: Why are you storing both the key and the value in both data > structures? Seems like putting just the key into a HashSet would be slightly > more efficient. We store an index of the first |key| occurrence as the |value| so we can update it when the duplicate is found. 412047 2020-10-21 16:53:02 -0700 2020-10-21 21:50:39 -0700 Patch bug-218062-20201021175301.patch text/plain 2972 achristensen U3VidmVyc2lvbiBSZXZpc2lvbjogMjY4ODQyCmRpZmYgLS1naXQgYS9Tb3VyY2UvV2ViQ29yZS9D aGFuZ2VMb2cgYi9Tb3VyY2UvV2ViQ29yZS9DaGFuZ2VMb2cKaW5kZXggYmQxNmMzMzk3N2RjN2Iy MDk0ZGZkMWI3MzM5NTY1MGYyYmQ0YWQwMy4uYzA5NDc4ZTEyNWVhY2UyYzdkMWI5ZDQ4Nzc4OGFl MzE2N2U4MWEyMyAxMDA2NDQKLS0tIGEvU291cmNlL1dlYkNvcmUvQ2hhbmdlTG9nCisrKyBiL1Nv dXJjZS9XZWJDb3JlL0NoYW5nZUxvZwpAQCAtMSwzICsxLDE3IEBACisyMDIwLTEwLTIxICBBbGV4 IENocmlzdGVuc2VuICA8YWNocmlzdGVuc2VuQHdlYmtpdC5vcmc+CisKKyAgICAgICAgUmVwbGFj ZSBPKG5eMikgYWxnb3JpdGhtIGZyb20gcjI2ODcwOSB3aXRoIE8obikgYWxnb3JpdGhtCisgICAg ICAgIGh0dHBzOi8vYnVncy53ZWJraXQub3JnL3Nob3dfYnVnLmNnaT9pZD0yMTgwNjIKKworICAg ICAgICBSZXZpZXdlZCBieSBOT0JPRFkgKE9PUFMhKS4KKworICAgICAgICByMjY4NzA5IGludHJv ZHVjZWQgYSBWZWN0b3I6OmZpbmRNYXRjaGluZyBjYWxsIGluc2lkZSBhIGxvb3AgdGhhdCBwb3B1 bGF0ZXMgdGhlIFZlY3Rvci4KKyAgICAgICAgVGhpcyBjYXVzZXMgdmVyeSBzbG93IGNvbnN0cnVj dGlvbiBvZiBVUkxTZWFyY2hQYXJhbXMgd2l0aCBsYXJnZSBkaWN0aW9uYXJpZXMgd2l0aCAxNi1i aXQga2V5cy4KKyAgICAgICAgVG8gc3BlZWQgdGhpbmdzIHVwLCBrZWVwIGEgSGFzaE1hcCBvZiB0 aGUgMTYtYml0IHN0cmluZ3Mgd2UgaGF2ZSBhbHJlYWR5IGluc2VydGVkIHRvIHRoZWlyIGluZGV4 IGluIHRoZSBWZWN0b3IKKyAgICAgICAgc28gd2UgZG9uJ3QgbmVlZCB0byBzZWFyY2ggdGhlIFZl Y3Rvci4KKworICAgICAgICAqIGJpbmRpbmdzL2pzL0pTRE9NQ29udmVydFJlY29yZC5oOgorCiAy MDIwLTEwLTIxICBDaHJpcyBEdW1leiAgPGNkdW1lekBhcHBsZS5jb20+CiAKICAgICAgICAgQWRk cmVzcyBwb3N0LWxhbmRpbmcgcmV2aWV3IGZlZWRiYWNrIGZyb20gU2FtIFdlaW5pZyBmb3IgcjI2 ODgyMC4KZGlmZiAtLWdpdCBhL1NvdXJjZS9XZWJDb3JlL2JpbmRpbmdzL2pzL0pTRE9NQ29udmVy dFJlY29yZC5oIGIvU291cmNlL1dlYkNvcmUvYmluZGluZ3MvanMvSlNET01Db252ZXJ0UmVjb3Jk LmgKaW5kZXggYzI1MWRiMTE3OTViMTUzMmI0MWUyZDM5YzM5NzczYzU1NmU4ZDJhNy4uNGY2NTM2 ZDVjNzQ5MmRkNjYzZWFmN2Y2NGQ0ODA2MDJhNWIxYmJiYyAxMDA2NDQKLS0tIGEvU291cmNlL1dl YkNvcmUvYmluZGluZ3MvanMvSlNET01Db252ZXJ0UmVjb3JkLmgKKysrIGIvU291cmNlL1dlYkNv cmUvYmluZGluZ3MvanMvSlNET01Db252ZXJ0UmVjb3JkLmgKQEAgLTk2LDYgKzk2LDcgQEAgcHJp dmF0ZToKICAgICAgICAgSlNDOjpKU09iamVjdCogb2JqZWN0ID0gSlNDOjphc09iamVjdCh2YWx1 ZSk7CiAgICAgCiAgICAgICAgIFJldHVyblR5cGUgcmVzdWx0OworICAgICAgICBIYXNoTWFwPEtl eVR5cGUsIHNpemVfdD4gcmVzdWx0TWFwOwogICAgIAogICAgICAgICAvLyA0LiBMZXQga2V5cyBi ZSA/IE8uW1tPd25Qcm9wZXJ0eUtleXNdXSgpLgogICAgICAgICBKU0M6OlByb3BlcnR5TmFtZUFy cmF5IGtleXModm0sIEpTQzo6UHJvcGVydHlOYW1lTW9kZTo6U3RyaW5ncywgSlNDOjpQcml2YXRl U3ltYm9sTW9kZTo6RXhjbHVkZSk7CkBAIC0xMzEsMTUgKzEzMiwxOSBAQCBwcml2YXRlOgogICAg ICAgICAgICAgICAgIC8vIE5vdGU6IEl0J3MgcG9zc2libGUgdGhhdCB0eXBlZEtleSBpcyBhbHJl YWR5IGluIHJlc3VsdCBpZiBLIGlzIFVTVlN0cmluZyBhbmQga2V5IGNvbnRhaW5zIHVucGFpcmVk IHN1cnJvZ2F0ZXMuCiAgICAgICAgICAgICAgICAgaWYgY29uc3RleHByIChzdGQ6OmlzX3NhbWVf djxLLCBJRExVU1ZTdHJpbmc+KSB7CiAgICAgICAgICAgICAgICAgICAgIGlmICghdHlwZWRLZXku aXM4Qml0KCkpIHsKLSAgICAgICAgICAgICAgICAgICAgICAgIGF1dG8gaW5kZXggPSByZXN1bHQu ZmluZE1hdGNoaW5nKFsmXShhdXRvJiBlbnRyeSkgeyByZXR1cm4gZW50cnkua2V5ID09IHR5cGVk S2V5OyB9KTsKLSAgICAgICAgICAgICAgICAgICAgICAgIGlmIChpbmRleCAhPSBub3RGb3VuZCkg ewotICAgICAgICAgICAgICAgICAgICAgICAgICAgIHJlc3VsdFtpbmRleF0udmFsdWUgPSB0eXBl ZFZhbHVlOworICAgICAgICAgICAgICAgICAgICAgICAgYXV0byBpdGVyYXRvciA9IHJlc3VsdE1h cC5maW5kKHR5cGVkS2V5KTsKKyAgICAgICAgICAgICAgICAgICAgICAgIGlmIChpdGVyYXRvciAh PSByZXN1bHRNYXAuZW5kKCkpIHsKKyAgICAgICAgICAgICAgICAgICAgICAgICAgICBBU1NFUlQo cmVzdWx0W2l0ZXJhdG9yLT52YWx1ZV0ua2V5ID09IHR5cGVkS2V5KTsKKyAgICAgICAgICAgICAg ICAgICAgICAgICAgICByZXN1bHRbaXRlcmF0b3ItPnZhbHVlXS52YWx1ZSA9IFdURk1vdmUodHlw ZWRWYWx1ZSk7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgY29udGludWU7CiAgICAgICAg ICAgICAgICAgICAgICAgICB9CisgICAgICAgICAgICAgICAgICAgICAgICByZXN1bHRNYXAuYWRk KHR5cGVkS2V5LCByZXN1bHQuc2l6ZSgpKTsKICAgICAgICAgICAgICAgICAgICAgfQotICAgICAg ICAgICAgICAgIH0KKyAgICAgICAgICAgICAgICB9IGVsc2UKKyAgICAgICAgICAgICAgICAgICAg VU5VU0VEX1ZBUklBQkxFKHJlc3VsdE1hcCk7CiAgICAgICAgICAgICAgICAgCi0gICAgICAgICAg ICAgICAgcmVzdWx0LmFwcGVuZCh7IHR5cGVkS2V5LCB0eXBlZFZhbHVlIH0pOworICAgICAgICAg ICAgICAgIC8vIDUuIE90aGVyd2lzZSwgYXBwZW5kIHRvIHJlc3VsdCBhIG1hcHBpbmcgKHR5cGVk S2V5LCB0eXBlZFZhbHVlKS4KKyAgICAgICAgICAgICAgICByZXN1bHQuYXBwZW5kKHsgV1RGTW92 ZSh0eXBlZEtleSksIFdURk1vdmUodHlwZWRWYWx1ZSkgfSk7CiAgICAgICAgICAgICB9CiAgICAg ICAgIH0KIAo=