112084 2013-03-11 17:42:36 -0700 Add a single character cache to WidthCache 2013-03-12 16:09:31 -0700 1 1 1 Unclassified WebKit New Bugs 528+ (Nightly build) Unspecified Unspecified RESOLVED FIXED P2 Normal --- 1 benjamin benjamin ggaren kling mitz oldest_to_newest 852918 0 benjamin 2013-03-11 17:42:36 -0700 Add a single character cache to WidthCache 852920 1 192608 benjamin 2013-03-11 17:47:34 -0700 Created attachment 192608 Patch 852977 2 kling 2013-03-11 18:46:33 -0700 Would it make sense to special-case even harder with a 256-entry array for the Latin1 characters? 853004 3 benjamin 2013-03-11 19:21:44 -0700 (In reply to comment #2) > Would it make sense to special-case even harder with a 256-entry array for the Latin1 characters? To test your hypothesis, I loaded a bunch of wikipedia pages and dumped the characters in a file. Here are all the characters used in that case: '\n', ' ', '"', "'", ')', '(', '\xab', '-', ',', '/', '.', '1', '0', '3', '2', '5', '4', '7', '6', '9', '8', 'E', '\xa0', '[', ']', 'a', 'c', 'e', 'g', 'f', 'i', 'h', 'k', 'j', 'l', 't', '|' The single space is the most common one, with 2773 out of 4269 chars. Given that the data is sparse, I think it is not needed to have a special case for Latin1 characters. What do you think? 853517 4 192608 ggaren 2013-03-12 08:58:15 -0700 Comment on attachment 192608 Patch View in context: https://bugs.webkit.org/attachment.cgi?id=192608&action=review r=me The data here convinces me that a 256-entry fixed array is probably not worth the space. Hashing a UChar will be cheap. > Source/WebCore/platform/graphics/WidthCache.h:158 > + float *value; "float*", please. > Source/WebCore/platform/graphics/WidthCache.h:161 > + isNewEntry = addResult.isNewEntry; I wonder if the single character should influence the cache's ramp-up strategy. A few reasons we might not want it to: (1) Single character hits -- especially single space -- will always be common. So, they're not a good indicator that we're laying out lots of duplicated words. (2) The single character cache has a small, fixed size limit, so its memory tradeoff is much much smaller. (3) The single character cache has a tiny lookup cost, so its speed tradeoff is smaller. That change would probably require extensive testing, though. 853859 5 192608 benjamin 2013-03-12 15:41:03 -0700 Comment on attachment 192608 Patch Clearing flags on attachment: 192608 Committed r145601: <http://trac.webkit.org/changeset/145601> 853860 6 benjamin 2013-03-12 15:41:04 -0700 All reviewed patches have been landed. Closing bug. 853869 7 benjamin 2013-03-12 15:44:32 -0700 > I wonder if the single character should influence the cache's ramp-up strategy. > > A few reasons we might not want it to: > > (1) Single character hits -- especially single space -- will always be common. So, they're not a good indicator that we're laying out lots of duplicated words. > > (2) The single character cache has a small, fixed size limit, so its memory tradeoff is much much smaller. > > (3) The single character cache has a tiny lookup cost, so its speed tradeoff is smaller. > > That change would probably require extensive testing, though. I completely agree with you. Do you have good test cases I can use to do this analysis? 853888 8 ggaren 2013-03-12 16:09:31 -0700 PerformanceTests/Layout/chapter-reflow*.html and PLT3 are what I would use to test. 192608 2013-03-11 17:47:34 -0700 2013-03-12 15:41:02 -0700 Patch bug-112084-20130311174334.patch text/plain 4253 benjamin U3VidmVyc2lvbiBSZXZpc2lvbjogMTQ1NDA1CmRpZmYgLS1naXQgYS9Tb3VyY2UvV2ViQ29yZS9D aGFuZ2VMb2cgYi9Tb3VyY2UvV2ViQ29yZS9DaGFuZ2VMb2cKaW5kZXggYzFlOGUwODM5NzYyYmQ1 NTY1ZTAxNTYxYzUwOTVjMDJjNmMyNGE2Mi4uZWMxN2Q5ZTgwNjRhMGRjNjcwZmM1YjE2NmEzZjk0 YTU3MzM5NTYzYyAxMDA2NDQKLS0tIGEvU291cmNlL1dlYkNvcmUvQ2hhbmdlTG9nCisrKyBiL1Nv dXJjZS9XZWJDb3JlL0NoYW5nZUxvZwpAQCAtMSwzICsxLDI1IEBACisyMDEzLTAzLTExICBCZW5q YW1pbiBQb3VsYWluICA8YnBvdWxhaW5AYXBwbGUuY29tPgorCisgICAgICAgIEFkZCBhIHNpbmds ZSBjaGFyYWN0ZXIgY2FjaGUgdG8gV2lkdGhDYWNoZQorICAgICAgICBodHRwczovL2J1Z3Mud2Vi a2l0Lm9yZy9zaG93X2J1Zy5jZ2k/aWQ9MTEyMDg0CisKKyAgICAgICAgUmV2aWV3ZWQgYnkgTk9C T0RZIChPT1BTISkuCisKKyAgICAgICAgTW9yZSB0aGFuIGhhbGYgb2YgdGhlIHZhbHVlcyBzdG9y ZWQgaW4gV2lkdGhDYWNoZSBhcmUgdmFsdWVzCisgICAgICAgIGZvciBhIHNpbmdsZSBjaGFyYWN0 ZXIuCisKKyAgICAgICAgUHJldmlvdXNseSwgd2Ugd2VyZSBjcmVhdGluZyBhIG5ldyBTbWFsbFN0 cmluZ0tleSBmb3IgZWFjaCBvbmUgb2YKKyAgICAgICAgdGhlbSwgY2F1c2luZyBhIGxvdCBvZiBl eHRyYSBtZW1vcnkgb3BlcmF0aW9ucyBldmVuIGZvciB0aGUgc2ltcGxlCisgICAgICAgIGNhc2Vz LgorCisgICAgICAgIFRoaXMgcGF0Y2ggYWRkcyBhIHNlY29uZCBtYXAsIG1fc2luZ2xlQ2hhck1h cCwgdG8gc2ltcGxpZnkgdGhlCisgICAgICAgIGNvbXB1dGF0aW9uIGZvciB0aGUgY29tbW9uIGNh c2Ugb2YgYSBzaW5nbGUgY2hhciBUZXh0UnVuLgorCisgICAgICAgICogcGxhdGZvcm0vZ3JhcGhp Y3MvV2lkdGhDYWNoZS5oOgorICAgICAgICAoV2ViQ29yZTo6V2lkdGhDYWNoZTo6Y2xlYXIpOgor ICAgICAgICAoV2lkdGhDYWNoZSk6CisgICAgICAgIChXZWJDb3JlOjpXaWR0aENhY2hlOjphZGRT bG93Q2FzZSk6CisKIDIwMTMtMDMtMTEgIEphbWVzIFJvYmluc29uICA8amFtZXNyQGNocm9taXVt Lm9yZz4KIAogICAgICAgICBDb21waWxlIGZpeC4gUnViYmVyLXN0YW1wIGJ5IEVyaWMgU2VpZGVs LgpkaWZmIC0tZ2l0IGEvU291cmNlL1dlYkNvcmUvcGxhdGZvcm0vZ3JhcGhpY3MvV2lkdGhDYWNo ZS5oIGIvU291cmNlL1dlYkNvcmUvcGxhdGZvcm0vZ3JhcGhpY3MvV2lkdGhDYWNoZS5oCmluZGV4 IDI1ZTc2YjRlZjc1ZTJkZWJhMWMwNjAyYjA0NTg1MDU2NzkxMjkyODIuLjExNDgzN2Y5MzI5MzI4 ZGYzZGM1YmI3NzI0Zjg3MTgwYjMxYzc3YjkgMTAwNjQ0Ci0tLSBhL1NvdXJjZS9XZWJDb3JlL3Bs YXRmb3JtL2dyYXBoaWNzL1dpZHRoQ2FjaGUuaAorKysgYi9Tb3VyY2UvV2ViQ29yZS9wbGF0Zm9y bS9ncmFwaGljcy9XaWR0aENhY2hlLmgKQEAgLTE0NCwyMCArMTQ0LDM4IEBAIHB1YmxpYzoKICAg ICAgICAgcmV0dXJuIGFkZFNsb3dDYXNlKHJ1biwgZW50cnkpOwogICAgIH0KIAotICAgIGZsb2F0 KiBhZGRTbG93Q2FzZShjb25zdCBUZXh0UnVuJiBydW4sIGZsb2F0IGVudHJ5KQorICAgIHZvaWQg Y2xlYXIoKQogICAgIHsKLSAgICAgICAgU21hbGxTdHJpbmdLZXkgc21hbGxTdHJpbmdLZXk7Ci0g ICAgICAgIGlmIChydW4uaXM4Qml0KCkpCi0gICAgICAgICAgICBzbWFsbFN0cmluZ0tleSA9IFNt YWxsU3RyaW5nS2V5KHJ1bi5jaGFyYWN0ZXJzOCgpLCBydW4ubGVuZ3RoKCkpOwotICAgICAgICBl bHNlCi0gICAgICAgICAgICBzbWFsbFN0cmluZ0tleSA9IFNtYWxsU3RyaW5nS2V5KHJ1bi5jaGFy YWN0ZXJzMTYoKSwgcnVuLmxlbmd0aCgpKTsKKyAgICAgICAgbV9zaW5nbGVDaGFyTWFwLmNsZWFy KCk7CisgICAgICAgIG1fbWFwLmNsZWFyKCk7CisgICAgfQogCi0gICAgICAgIE1hcDo6QWRkUmVz dWx0IGFkZFJlc3VsdCA9IG1fbWFwLmFkZChzbWFsbFN0cmluZ0tleSwgZW50cnkpOworcHJpdmF0 ZToKKyAgICBmbG9hdCogYWRkU2xvd0Nhc2UoY29uc3QgVGV4dFJ1biYgcnVuLCBmbG9hdCBlbnRy eSkKKyAgICB7CisgICAgICAgIGludCBsZW5ndGggPSBydW4ubGVuZ3RoKCk7CisgICAgICAgIGJv b2wgaXNOZXdFbnRyeTsKKyAgICAgICAgZmxvYXQgKnZhbHVlOworICAgICAgICBpZiAobGVuZ3Ro ID09IDEpIHsKKyAgICAgICAgICAgIFNpbmdsZUNoYXJNYXA6OkFkZFJlc3VsdCBhZGRSZXN1bHQg PSBtX3NpbmdsZUNoYXJNYXAuYWRkKHJ1blswXSwgZW50cnkpOworICAgICAgICAgICAgaXNOZXdF bnRyeSA9IGFkZFJlc3VsdC5pc05ld0VudHJ5OworICAgICAgICAgICAgdmFsdWUgPSAmYWRkUmVz dWx0Lml0ZXJhdG9yLT52YWx1ZTsKKyAgICAgICAgfSBlbHNlIHsKKyAgICAgICAgICAgIFNtYWxs U3RyaW5nS2V5IHNtYWxsU3RyaW5nS2V5OworICAgICAgICAgICAgaWYgKHJ1bi5pczhCaXQoKSkK KyAgICAgICAgICAgICAgICBzbWFsbFN0cmluZ0tleSA9IFNtYWxsU3RyaW5nS2V5KHJ1bi5jaGFy YWN0ZXJzOCgpLCBsZW5ndGgpOworICAgICAgICAgICAgZWxzZQorICAgICAgICAgICAgICAgIHNt YWxsU3RyaW5nS2V5ID0gU21hbGxTdHJpbmdLZXkocnVuLmNoYXJhY3RlcnMxNigpLCBsZW5ndGgp OworCisgICAgICAgICAgICBNYXA6OkFkZFJlc3VsdCBhZGRSZXN1bHQgPSBtX21hcC5hZGQoc21h bGxTdHJpbmdLZXksIGVudHJ5KTsKKyAgICAgICAgICAgIGlzTmV3RW50cnkgPSBhZGRSZXN1bHQu aXNOZXdFbnRyeTsKKyAgICAgICAgICAgIHZhbHVlID0gJmFkZFJlc3VsdC5pdGVyYXRvci0+dmFs dWU7CisgICAgICAgIH0KIAogICAgICAgICAvLyBDYWNoZSBoaXQ6IHJhbXAgdXAgYnkgc2FtcGxp bmcgdGhlIG5leHQgZmV3IHdvcmRzLgotICAgICAgICBpZiAoIWFkZFJlc3VsdC5pc05ld0VudHJ5 KSB7CisgICAgICAgIGlmICghaXNOZXdFbnRyeSkgewogICAgICAgICAgICAgbV9pbnRlcnZhbCA9 IHNfbWluSW50ZXJ2YWw7Ci0gICAgICAgICAgICByZXR1cm4gJmFkZFJlc3VsdC5pdGVyYXRvci0+ dmFsdWU7CisgICAgICAgICAgICByZXR1cm4gdmFsdWU7CiAgICAgICAgIH0KIAogICAgICAgICAv LyBDYWNoZSBtaXNzOiByYW1wIGRvd24gYnkgaW5jcmVhc2luZyBvdXIgc2FtcGxpbmcgaW50ZXJ2 YWwuCkBAIC0xNjUsMjMgKzE4MywyNCBAQCBwdWJsaWM6CiAgICAgICAgICAgICArK21faW50ZXJ2 YWw7CiAgICAgICAgIG1fY291bnRkb3duID0gbV9pbnRlcnZhbDsKIAotICAgICAgICBpZiAobV9t YXAuc2l6ZSgpIDwgc19tYXhTaXplKQotICAgICAgICAgICAgcmV0dXJuICZhZGRSZXN1bHQuaXRl cmF0b3ItPnZhbHVlOworICAgICAgICBpZiAoKG1fc2luZ2xlQ2hhck1hcC5zaXplKCkgKyBtX21h cC5zaXplKCkpIDwgc19tYXhTaXplKQorICAgICAgICAgICAgcmV0dXJuIHZhbHVlOwogCi0gICAg ICAgIG1fbWFwLmNsZWFyKCk7IC8vIE5vIG5lZWQgdG8gYmUgZmFuY3k6IHdlJ3JlIGp1c3QgdHJ5 aW5nIHRvIGF2b2lkIHBhdGhvbG9naWNhbCBncm93dGguCisgICAgICAgIC8vIE5vIG5lZWQgdG8g YmUgZmFuY3k6IHdlJ3JlIGp1c3QgdHJ5aW5nIHRvIGF2b2lkIHBhdGhvbG9naWNhbCBncm93dGgu CisgICAgICAgIG1fc2luZ2xlQ2hhck1hcC5jbGVhcigpOworICAgICAgICBtX21hcC5jbGVhcigp OwogICAgICAgICByZXR1cm4gMDsKICAgICB9CiAKLSAgICB2b2lkIGNsZWFyKCkgeyBtX21hcC5j bGVhcigpOyB9Ci0KLXByaXZhdGU6CiAgICAgdHlwZWRlZiBIYXNoTWFwPFNtYWxsU3RyaW5nS2V5 LCBmbG9hdCwgU21hbGxTdHJpbmdLZXlIYXNoLCBTbWFsbFN0cmluZ0tleUhhc2hUcmFpdHM+IE1h cDsKKyAgICB0eXBlZGVmIEhhc2hNYXA8VUNoYXIsIGZsb2F0PiBTaW5nbGVDaGFyTWFwOwogICAg IHN0YXRpYyBjb25zdCBpbnQgc19taW5JbnRlcnZhbCA9IC0zOyAvLyBBIGNhY2hlIGhpdCBwYXlz IGZvciBhYm91dCAzIGNhY2hlIG1pc3Nlcy4KICAgICBzdGF0aWMgY29uc3QgaW50IHNfbWF4SW50 ZXJ2YWwgPSAyMDsgLy8gU2FtcGxpbmcgYXQgdGhpcyBpbnRlcnZhbCBoYXMgYWxtb3N0IG5vIG92 ZXJoZWFkLgogICAgIHN0YXRpYyBjb25zdCBpbnQgc19tYXhTaXplID0gNTAwMDAwOyAvLyBKdXN0 IGVub3VnaCB0byBndWFyZCBhZ2FpbnN0IHBhdGhvbG9naWNhbCBncm93dGguCiAKICAgICBpbnQg bV9pbnRlcnZhbDsKICAgICBpbnQgbV9jb3VudGRvd247CisgICAgU2luZ2xlQ2hhck1hcCBtX3Np bmdsZUNoYXJNYXA7CiAgICAgTWFwIG1fbWFwOwogfTsKIAo=