237117 2022-02-23 15:25:47 -0800 Small optimizations to TinyLRUCache 2022-03-04 17:33:26 -0800 1 1 1 Unclassified WebKit Web Template Framework WebKit Nightly Build Unspecified Unspecified RESOLVED FIXED InRadar P2 Normal --- 1 cdumez cdumez benjamin cmarcelo darin ews-watchlist ggaren sam webkit-bug-importer ysuzuki oldest_to_newest 1845348 0 cdumez 2022-02-23 15:25:47 -0800 Small optimizations to TinyLRUCache. 1845350 1 453035 cdumez 2022-02-23 15:31:24 -0800 Created attachment 453035 Patch 1845468 2 453035 darin 2022-02-23 17:48:15 -0800 Comment on attachment 453035 Patch View in context: https://bugs.webkit.org/attachment.cgi?id=453035&action=review > Source/WTF/ChangeLog:14 > + - Use Vector::uncheckedAppend() instead of Vector::append() to bypass capacity > + checks given that the vector has an inline capacity that is the size of the > + cache (vector capacity never grows or shrinks). Maybe we should us FixedVector instead? > Source/WTF/wtf/TinyLRUCache.h:56 > + Entry entry = WTFMove(m_cache[index]); I’d use auto here. 1845471 3 453035 cdumez 2022-02-23 17:58:23 -0800 Comment on attachment 453035 Patch View in context: https://bugs.webkit.org/attachment.cgi?id=453035&action=review >> Source/WTF/ChangeLog:14 >> + cache (vector capacity never grows or shrinks). > > Maybe we should us FixedVector instead? I am not super familiar with FixedVector but doesn't it have a fixed size? Here the vector size is dynamic but the vector *capacity* is static. I guess we could use a vector of fixed size (FixedVector) but then we'd need to fill the vector with "empty" values, distinguishable from actually cache values? >> Source/WTF/wtf/TinyLRUCache.h:56 >> + Entry entry = WTFMove(m_cache[index]); > > I’d use auto here. OK. 1845475 4 453062 cdumez 2022-02-23 18:06:00 -0800 Created attachment 453062 Patch 1845542 5 ews-feeder 2022-02-24 00:56:50 -0800 Committed r290415 (247723@main): <https://commits.webkit.org/247723@main> All reviewed patches have been landed. Closing bug and clearing flags on attachment 453062. 1845544 6 webkit-bug-importer 2022-02-24 00:57:21 -0800 <rdar://problem/89405387> 1848459 7 sam 2022-03-04 17:09:34 -0800 (In reply to Chris Dumez from comment #3) > Comment on attachment 453035 [details] > Patch > > View in context: > https://bugs.webkit.org/attachment.cgi?id=453035&action=review > > >> Source/WTF/ChangeLog:14 > >> + cache (vector capacity never grows or shrinks). > > > > Maybe we should us FixedVector instead? > > I am not super familiar with FixedVector but doesn't it have a fixed size? > Here the vector size is dynamic but the vector *capacity* is static. > I guess we could use a vector of fixed size (FixedVector) but then we'd need > to fill the vector with "empty" values, distinguishable from actually cache > values? > > >> Source/WTF/wtf/TinyLRUCache.h:56 > >> + Entry entry = WTFMove(m_cache[index]); > > > > I’d use auto here. > > OK. Given the name (Tiny...) I think we can probably just a fixed size array for this. Im don't think we ever use this for something with more than 32 elements and we know the max capacity at compile time. 1848465 8 ggaren 2022-03-04 17:33:26 -0800 std::array or whatever would be fine. Just a bother to have to implement your own size(), remove(), and append() functions. Maybe not worth the bother? 453035 2022-02-23 15:31:24 -0800 2022-02-23 18:05:57 -0800 Patch bug-237117-20220223153123.patch text/plain 3045 cdumez U3VidmVyc2lvbiBSZXZpc2lvbjogMjkwMzkyCmRpZmYgLS1naXQgYS9Tb3VyY2UvV1RGL0NoYW5n ZUxvZyBiL1NvdXJjZS9XVEYvQ2hhbmdlTG9nCmluZGV4IDljZTJkY2YwNDcwOTU2Y2Q1NDQ5YzY0 MTI4YTIyZDQ5ODUyNzY0OTEuLjUyZTc4YWE5ZjE0Yjg2ZmI3NTMxZTg2YWZhOWNiYzIzMjZmMWFl YjQgMTAwNjQ0Ci0tLSBhL1NvdXJjZS9XVEYvQ2hhbmdlTG9nCisrKyBiL1NvdXJjZS9XVEYvQ2hh bmdlTG9nCkBAIC0xLDMgKzEsMjEgQEAKKzIwMjItMDItMjMgIENocmlzIER1bWV6ICA8Y2R1bWV6 QGFwcGxlLmNvbT4KKworICAgICAgICBTbWFsbCBvcHRpbWl6YXRpb25zIHRvIFRpbnlMUlVDYWNo ZQorICAgICAgICBodHRwczovL2J1Z3Mud2Via2l0Lm9yZy9zaG93X2J1Zy5jZ2k/aWQ9MjM3MTE3 CisKKyAgICAgICAgUmV2aWV3ZWQgYnkgTk9CT0RZIChPT1BTISkuCisKKyAgICAgICAgU21hbGwg b3B0aW1pemF0aW9ucyB0byBUaW55TFJVQ2FjaGU6CisgICAgICAgIC0gV2hlbiB0cnlpbmcgdG8g ZmluZCBhbiBlbnRyeSBpbiB0aGUgY2FjaGUsIHN0YXJ0IGZyb20gdGhlIGVuZCBvZiB0aGUgdmVj dG9yCisgICAgICAgICAgc2luY2UgdGhpcyBpcyB3aGVyZSB0aGUgbW9zdCByZWNlbnQgZW50cmll cyBhcmUuCisgICAgICAgIC0gVXNlIHJldmVyc2VGaW5kKCkgaW5zdGVhZCBvZiBhIGZvciBsb29w IHRvIHNpbXBsaWZ5IHRoZSBjb2RlIGEgYml0CisgICAgICAgIC0gVXNlIFZlY3Rvcjo6dW5jaGVj a2VkQXBwZW5kKCkgaW5zdGVhZCBvZiBWZWN0b3I6OmFwcGVuZCgpIHRvIGJ5cGFzcyBjYXBhY2l0 eQorICAgICAgICAgIGNoZWNrcyBnaXZlbiB0aGF0IHRoZSB2ZWN0b3IgaGFzIGFuIGlubGluZSBj YXBhY2l0eSB0aGF0IGlzIHRoZSBzaXplIG9mIHRoZQorICAgICAgICAgIGNhY2hlICh2ZWN0b3Ig Y2FwYWNpdHkgbmV2ZXIgZ3Jvd3Mgb3Igc2hyaW5rcykuCisKKyAgICAgICAgKiB3dGYvVGlueUxS VUNhY2hlLmg6CisgICAgICAgIChXVEY6OlRpbnlMUlVDYWNoZTo6Z2V0KToKKwogMjAyMi0wMi0y MyAgS2ltbW8gS2lubnVuZW4gIDxra2lubnVuZW5AYXBwbGUuY29tPgogCiAgICAgICAgIFRocmVh ZCBzYWZldHkgYW5hbHlzaXMgbWFjcm9zIGFyZSBjb25mdXNpbmcgZm9yIG5vbi1Mb2NrIHVzZS1j YXNlcwpkaWZmIC0tZ2l0IGEvU291cmNlL1dURi93dGYvVGlueUxSVUNhY2hlLmggYi9Tb3VyY2Uv V1RGL3d0Zi9UaW55TFJVQ2FjaGUuaAppbmRleCA5MDNlNWJiYTczODFkODM0ZTczMzRkOTFjZmJh OWFlNDg3MTA1MTJlLi5lNjhkMWRhMDdkNjIyYTVjZDJjOGM2ZTJkNTAyMzA1NmVmOWYxZjkyIDEw MDY0NAotLS0gYS9Tb3VyY2UvV1RGL3d0Zi9UaW55TFJVQ2FjaGUuaAorKysgYi9Tb3VyY2UvV1RG L3d0Zi9UaW55TFJVQ2FjaGUuaApAQCAtNDksMTcgKzQ5LDE0IEBAIHB1YmxpYzoKICAgICAgICAg ICAgIHJldHVybiB2YWx1ZUZvck51bGw7CiAgICAgICAgIH0KIAotICAgICAgICBmb3IgKHNpemVf dCBpID0gMDsgaSA8IG1fY2FjaGUuc2l6ZSgpOyArK2kpIHsKLSAgICAgICAgICAgIGlmIChtX2Nh Y2hlW2ldLmZpcnN0ICE9IGtleSkKLSAgICAgICAgICAgICAgICBjb250aW51ZTsKLQotICAgICAg ICAgICAgaWYgKGkgPT0gbV9jYWNoZS5zaXplKCkgLSAxKQotICAgICAgICAgICAgICAgIHJldHVy biBtX2NhY2hlW2ldLnNlY29uZDsKLQotICAgICAgICAgICAgLy8gSWYgdGhlIGVudHJ5IGlzIG5v dCB0aGUgbGFzdCBvbmUsIG1vdmUgaXQgdG8gdGhlIGVuZCBvZiB0aGUgY2FjaGUuCi0gICAgICAg ICAgICBFbnRyeSBlbnRyeSA9IFdURk1vdmUobV9jYWNoZVtpXSk7Ci0gICAgICAgICAgICBtX2Nh Y2hlLnJlbW92ZShpKTsKLSAgICAgICAgICAgIG1fY2FjaGUuYXBwZW5kKFdURk1vdmUoZW50cnkp KTsKKyAgICAgICAgYXV0byBpbmRleCA9IG1fY2FjaGUucmV2ZXJzZUZpbmRJZihbJmtleV0oYXV0 byYgZW50cnkpIHsgcmV0dXJuIGVudHJ5LmZpcnN0ID09IGtleTsgfSk7CisgICAgICAgIGlmIChp bmRleCAhPSBub3RGb3VuZCkgeworICAgICAgICAgICAgLy8gTW92ZSBlbnRyeSB0byB0aGUgZW5k IG9mIHRoZSBjYWNoZSBpZiBuZWNlc3NhcnkuCisgICAgICAgICAgICBpZiAoaW5kZXggIT0gbV9j YWNoZS5zaXplKCkgLSAxKSB7CisgICAgICAgICAgICAgICAgRW50cnkgZW50cnkgPSBXVEZNb3Zl KG1fY2FjaGVbaW5kZXhdKTsKKyAgICAgICAgICAgICAgICBtX2NhY2hlLnJlbW92ZShpbmRleCk7 CisgICAgICAgICAgICAgICAgbV9jYWNoZS51bmNoZWNrZWRBcHBlbmQoV1RGTW92ZShlbnRyeSkp OworICAgICAgICAgICAgfQogICAgICAgICAgICAgcmV0dXJuIG1fY2FjaGVbbV9jYWNoZS5zaXpl KCkgLSAxXS5zZWNvbmQ7CiAgICAgICAgIH0KIApAQCAtNjcsMTcgKzY0LDE3IEBAIHB1YmxpYzoK ICAgICAgICAgaWYgKG1fY2FjaGUuc2l6ZSgpID09IGNhcGFjaXR5KQogICAgICAgICAgICAgbV9j YWNoZS5yZW1vdmUoMCk7CiAKLSAgICAgICAgbV9jYWNoZS5hcHBlbmQoc3RkOjptYWtlX3BhaXIo UG9saWN5OjpjcmVhdGVLZXlGb3JTdG9yYWdlKGtleSksIFBvbGljeTo6Y3JlYXRlVmFsdWVGb3JL ZXkoa2V5KSkpOworICAgICAgICBtX2NhY2hlLnVuY2hlY2tlZEFwcGVuZChzdGQ6OnBhaXIgeyBQ b2xpY3k6OmNyZWF0ZUtleUZvclN0b3JhZ2Uoa2V5KSwgUG9saWN5OjpjcmVhdGVWYWx1ZUZvcktl eShrZXkpIH0pOwogICAgICAgICByZXR1cm4gbV9jYWNoZS5sYXN0KCkuc2Vjb25kOwogICAgIH0K IAogcHJpdmF0ZToKLSAgICB0eXBlZGVmIHN0ZDo6cGFpcjxLZXlUeXBlLCBWYWx1ZVR5cGU+IEVu dHJ5OwotICAgIHR5cGVkZWYgVmVjdG9yPEVudHJ5LCBjYXBhY2l0eT4gQ2FjaGU7CisgICAgdXNp bmcgRW50cnkgPSBzdGQ6OnBhaXI8S2V5VHlwZSwgVmFsdWVUeXBlPjsKKyAgICB1c2luZyBDYWNo ZSA9IFZlY3RvcjxFbnRyeSwgY2FwYWNpdHk+OwogICAgIENhY2hlIG1fY2FjaGU7CiB9OwogCi19 Cit9IC8vIG5hbWVzcGFjZSBXVEYKIAogdXNpbmcgV1RGOjpUaW55TFJVQ2FjaGU7CiB1c2luZyBX VEY6OlRpbnlMUlVDYWNoZVBvbGljeTsK 453062 2022-02-23 18:06:00 -0800 2022-02-24 00:56:52 -0800 Patch bug-237117-20220223180559.patch text/plain 3033 cdumez U3VidmVyc2lvbiBSZXZpc2lvbjogMjkwNDA3CmRpZmYgLS1naXQgYS9Tb3VyY2UvV1RGL0NoYW5n ZUxvZyBiL1NvdXJjZS9XVEYvQ2hhbmdlTG9nCmluZGV4IDlmMGM2N2JkNjJjY2VkN2U3NjMxYzA0 NzBhZWYyYzBkZGRlMzMwNjYuLmE5YzY2ODlmMWYyZTA3YzgxMzdlYzcwZDA5YTM0YmE5OGNjODdl YTUgMTAwNjQ0Ci0tLSBhL1NvdXJjZS9XVEYvQ2hhbmdlTG9nCisrKyBiL1NvdXJjZS9XVEYvQ2hh bmdlTG9nCkBAIC0xLDMgKzEsMjEgQEAKKzIwMjItMDItMjMgIENocmlzIER1bWV6ICA8Y2R1bWV6 QGFwcGxlLmNvbT4KKworICAgICAgICBTbWFsbCBvcHRpbWl6YXRpb25zIHRvIFRpbnlMUlVDYWNo ZQorICAgICAgICBodHRwczovL2J1Z3Mud2Via2l0Lm9yZy9zaG93X2J1Zy5jZ2k/aWQ9MjM3MTE3 CisKKyAgICAgICAgUmV2aWV3ZWQgYnkgRGFyaW4gQWRsZXIuCisKKyAgICAgICAgU21hbGwgb3B0 aW1pemF0aW9ucyB0byBUaW55TFJVQ2FjaGU6CisgICAgICAgIC0gV2hlbiB0cnlpbmcgdG8gZmlu ZCBhbiBlbnRyeSBpbiB0aGUgY2FjaGUsIHN0YXJ0IGZyb20gdGhlIGVuZCBvZiB0aGUgdmVjdG9y CisgICAgICAgICAgc2luY2UgdGhpcyBpcyB3aGVyZSB0aGUgbW9zdCByZWNlbnQgZW50cmllcyBh cmUuCisgICAgICAgIC0gVXNlIHJldmVyc2VGaW5kKCkgaW5zdGVhZCBvZiBhIGZvciBsb29wIHRv IHNpbXBsaWZ5IHRoZSBjb2RlIGEgYml0CisgICAgICAgIC0gVXNlIFZlY3Rvcjo6dW5jaGVja2Vk QXBwZW5kKCkgaW5zdGVhZCBvZiBWZWN0b3I6OmFwcGVuZCgpIHRvIGJ5cGFzcyBjYXBhY2l0eQor ICAgICAgICAgIGNoZWNrcyBnaXZlbiB0aGF0IHRoZSB2ZWN0b3IgaGFzIGFuIGlubGluZSBjYXBh Y2l0eSB0aGF0IGlzIHRoZSBzaXplIG9mIHRoZQorICAgICAgICAgIGNhY2hlICh2ZWN0b3IgY2Fw YWNpdHkgbmV2ZXIgZ3Jvd3Mgb3Igc2hyaW5rcykuCisKKyAgICAgICAgKiB3dGYvVGlueUxSVUNh Y2hlLmg6CisgICAgICAgIChXVEY6OlRpbnlMUlVDYWNoZTo6Z2V0KToKKwogMjAyMi0wMi0yMyAg Q2hyaXMgRHVtZXogIDxjZHVtZXpAYXBwbGUuY29tPgogCiAgICAgICAgIEFkb3B0IG1vcmUgd2lk ZWx5IHRoZSBuZXcgVVJMIGNvbnN0cnVjdG9yIHRoYXQgdGFrZXMgaW4gYSBTdHJpbmcKZGlmZiAt LWdpdCBhL1NvdXJjZS9XVEYvd3RmL1RpbnlMUlVDYWNoZS5oIGIvU291cmNlL1dURi93dGYvVGlu eUxSVUNhY2hlLmgKaW5kZXggOTAzZTViYmE3MzgxZDgzNGU3MzM0ZDkxY2ZiYTlhZTQ4NzEwNTEy ZS4uZjdjN2JjYjAzNDEyYjc1OTJkZDc2ZGQ0OTEwMzNjNjY5MDA5MjlhNSAxMDA2NDQKLS0tIGEv U291cmNlL1dURi93dGYvVGlueUxSVUNhY2hlLmgKKysrIGIvU291cmNlL1dURi93dGYvVGlueUxS VUNhY2hlLmgKQEAgLTQ5LDE3ICs0OSwxNCBAQCBwdWJsaWM6CiAgICAgICAgICAgICByZXR1cm4g dmFsdWVGb3JOdWxsOwogICAgICAgICB9CiAKLSAgICAgICAgZm9yIChzaXplX3QgaSA9IDA7IGkg PCBtX2NhY2hlLnNpemUoKTsgKytpKSB7Ci0gICAgICAgICAgICBpZiAobV9jYWNoZVtpXS5maXJz dCAhPSBrZXkpCi0gICAgICAgICAgICAgICAgY29udGludWU7Ci0KLSAgICAgICAgICAgIGlmIChp ID09IG1fY2FjaGUuc2l6ZSgpIC0gMSkKLSAgICAgICAgICAgICAgICByZXR1cm4gbV9jYWNoZVtp XS5zZWNvbmQ7Ci0KLSAgICAgICAgICAgIC8vIElmIHRoZSBlbnRyeSBpcyBub3QgdGhlIGxhc3Qg b25lLCBtb3ZlIGl0IHRvIHRoZSBlbmQgb2YgdGhlIGNhY2hlLgotICAgICAgICAgICAgRW50cnkg ZW50cnkgPSBXVEZNb3ZlKG1fY2FjaGVbaV0pOwotICAgICAgICAgICAgbV9jYWNoZS5yZW1vdmUo aSk7Ci0gICAgICAgICAgICBtX2NhY2hlLmFwcGVuZChXVEZNb3ZlKGVudHJ5KSk7CisgICAgICAg IGF1dG8gaW5kZXggPSBtX2NhY2hlLnJldmVyc2VGaW5kSWYoWyZrZXldKGF1dG8mIGVudHJ5KSB7 IHJldHVybiBlbnRyeS5maXJzdCA9PSBrZXk7IH0pOworICAgICAgICBpZiAoaW5kZXggIT0gbm90 Rm91bmQpIHsKKyAgICAgICAgICAgIC8vIE1vdmUgZW50cnkgdG8gdGhlIGVuZCBvZiB0aGUgY2Fj aGUgaWYgbmVjZXNzYXJ5LgorICAgICAgICAgICAgaWYgKGluZGV4ICE9IG1fY2FjaGUuc2l6ZSgp IC0gMSkgeworICAgICAgICAgICAgICAgIGF1dG8gZW50cnkgPSBXVEZNb3ZlKG1fY2FjaGVbaW5k ZXhdKTsKKyAgICAgICAgICAgICAgICBtX2NhY2hlLnJlbW92ZShpbmRleCk7CisgICAgICAgICAg ICAgICAgbV9jYWNoZS51bmNoZWNrZWRBcHBlbmQoV1RGTW92ZShlbnRyeSkpOworICAgICAgICAg ICAgfQogICAgICAgICAgICAgcmV0dXJuIG1fY2FjaGVbbV9jYWNoZS5zaXplKCkgLSAxXS5zZWNv bmQ7CiAgICAgICAgIH0KIApAQCAtNjcsMTcgKzY0LDE3IEBAIHB1YmxpYzoKICAgICAgICAgaWYg KG1fY2FjaGUuc2l6ZSgpID09IGNhcGFjaXR5KQogICAgICAgICAgICAgbV9jYWNoZS5yZW1vdmUo MCk7CiAKLSAgICAgICAgbV9jYWNoZS5hcHBlbmQoc3RkOjptYWtlX3BhaXIoUG9saWN5OjpjcmVh dGVLZXlGb3JTdG9yYWdlKGtleSksIFBvbGljeTo6Y3JlYXRlVmFsdWVGb3JLZXkoa2V5KSkpOwor ICAgICAgICBtX2NhY2hlLnVuY2hlY2tlZEFwcGVuZChzdGQ6OnBhaXIgeyBQb2xpY3k6OmNyZWF0 ZUtleUZvclN0b3JhZ2Uoa2V5KSwgUG9saWN5OjpjcmVhdGVWYWx1ZUZvcktleShrZXkpIH0pOwog ICAgICAgICByZXR1cm4gbV9jYWNoZS5sYXN0KCkuc2Vjb25kOwogICAgIH0KIAogcHJpdmF0ZToK LSAgICB0eXBlZGVmIHN0ZDo6cGFpcjxLZXlUeXBlLCBWYWx1ZVR5cGU+IEVudHJ5OwotICAgIHR5 cGVkZWYgVmVjdG9yPEVudHJ5LCBjYXBhY2l0eT4gQ2FjaGU7CisgICAgdXNpbmcgRW50cnkgPSBz dGQ6OnBhaXI8S2V5VHlwZSwgVmFsdWVUeXBlPjsKKyAgICB1c2luZyBDYWNoZSA9IFZlY3RvcjxF bnRyeSwgY2FwYWNpdHk+OwogICAgIENhY2hlIG1fY2FjaGU7CiB9OwogCi19Cit9IC8vIG5hbWVz cGFjZSBXVEYKIAogdXNpbmcgV1RGOjpUaW55TFJVQ2FjaGU7CiB1c2luZyBXVEY6OlRpbnlMUlVD YWNoZVBvbGljeTsK