55873 2011-03-07 06:00:39 -0800 Use HashMaps for caching primitive values 2011-03-07 11:10:49 -0800 1 1 1 Unclassified WebKit CSS 528+ (Nightly build) PC OS X 10.5 RESOLVED FIXED P2 Normal --- 1 koivisto webkit-unassigned abarth ap eric mitz oliver webkit.review.bot oldest_to_newest 363319 0 koivisto 2011-03-07 06:00:39 -0800 Both the memory efficiency and sharing efficiency of CSSPrimitiveValueCache can be improved by using HashMaps instead of fixed size arrays. 363320 1 84939 koivisto 2011-03-07 06:20:59 -0800 Created attachment 84939 use HashMaps instead of fixed size arrays for caching This removes the fixed per-document cost of empty cache (was ~10kb on 32bit) while also somewhat improving caching efficiency (~5% from expanded integer range which more than pays for itself). Caches usually cover only a fraction of possible values so increased per-item cost from the hash table is ok. 363323 2 webkit.review.bot 2011-03-07 06:24:03 -0800 Attachment 84939 did not pass style-queue: Failed to run "['Tools/Scripts/check-webkit-style', '--diff-files', u'Source/WebCore/ChangeLog', u'Source/WebCor..." exit_code: 1 Source/WebCore/css/CSSPrimitiveValueCache.cpp:97: Tests for true/false, null/non-null, and zero/non-zero should all be done without equality comparisons. [readability/comparison_to_zero] [5] Source/WebCore/css/CSSPrimitiveValueCache.cpp:102: Tests for true/false, null/non-null, and zero/non-zero should all be done without equality comparisons. [readability/comparison_to_zero] [5] Source/WebCore/css/CSSPrimitiveValueCache.cpp:107: Tests for true/false, null/non-null, and zero/non-zero should all be done without equality comparisons. [readability/comparison_to_zero] [5] Total errors found: 3 in 3 files If any of these errors are false positives, please file a bug against check-webkit-style. 363355 3 84939 mitz 2011-03-07 08:22:09 -0800 Comment on attachment 84939 use HashMaps instead of fixed size arrays for caching View in context: https://bugs.webkit.org/attachment.cgi?id=84939&action=review > Source/WebCore/css/CSSPrimitiveValueCache.cpp:53 > + m_identifierValueCache.add(ident, primitiveValue); A get() followed by an add() means two cache lookups. You can do this with a single add(). 363363 4 84939 sam 2011-03-07 09:00:35 -0800 Comment on attachment 84939 use HashMaps instead of fixed size arrays for caching View in context: https://bugs.webkit.org/attachment.cgi?id=84939&action=review > Source/WebCore/css/CSSPrimitiveValueCache.cpp:119 > + RefPtr<CSSPrimitiveValue> primitiveValue = cache->get(intValue); > if (!primitiveValue) { > primitiveValue = CSSPrimitiveValue::create(value, type); > - m_integerValueCache[intValue][type] = primitiveValue; > + cache->add(intValue, primitiveValue); > } Same comment as the the one mitz gave above. This can be done with one hash lookup. 363409 5 koivisto 2011-03-07 10:54:10 -0800 http://trac.webkit.org/changeset/80477 (with single hash lookups) 363421 6 webkit.review.bot 2011-03-07 11:10:49 -0800 http://trac.webkit.org/changeset/80477 might have broken Qt Linux Release 84939 2011-03-07 06:20:59 -0800 2011-03-07 09:00:35 -0800 use HashMaps instead of fixed size arrays for caching primitive-value-cache-hash.patch text/plain 6322 koivisto SW5kZXg6IFNvdXJjZS9XZWJDb3JlL0NoYW5nZUxvZwo9PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09Ci0tLSBTb3VyY2UvV2Vi Q29yZS9DaGFuZ2VMb2cJKHJldmlzaW9uIDgwNDY2KQorKysgU291cmNlL1dlYkNvcmUvQ2hhbmdl TG9nCSh3b3JraW5nIGNvcHkpCkBAIC0xLDMgKzEsMjEgQEAKKzIwMTEtMDMtMDcgIEFudHRpIEtv aXZpc3RvICA8YW50dGlAYXBwbGUuY29tPgorCisgICAgICAgIFJldmlld2VkIGJ5IE5PQk9EWSAo T09QUyEpLgorCisgICAgICAgIFVzZSBIYXNoTWFwcyBmb3IgY2FjaGluZyBwcmltaXRpdmUgdmFs dWVzCisgICAgICAgIGh0dHBzOi8vYnVncy53ZWJraXQub3JnL3Nob3dfYnVnLmNnaT9pZD01NTg3 MworICAgICAgICAKKyAgICAgICAgTW9zdCBkb2N1bWVudHMgdXNlIG9ubHkgc21hbGwgc3Vic2V0 IG9mIGNhY2hlYWJsZSBwcmltaXRpdmUgdmFsdWVzLiBCeSByZXBsYWNpbmcKKyAgICAgICAgZml4 ZWQgc2l6ZSBjYWNoZSBhcnJheXMgd2l0aCBIYXNoTWFwcyB3ZSBjYW4gcmVkdWNlIHRoZSBjb25z dGFudCBtZW1vcnkgdXNhZ2Ugd2hpbGUgYWxzbworICAgICAgICBleHBhbmRpbmcgdGhlIHJhbmdl IG9mIGNhY2hlYWJsZSB2YWx1ZXMuCisKKyAgICAgICAgKiBjc3MvQ1NTUHJpbWl0aXZlVmFsdWVD YWNoZS5jcHA6CisgICAgICAgIChXZWJDb3JlOjpDU1NQcmltaXRpdmVWYWx1ZUNhY2hlOjpDU1NQ cmltaXRpdmVWYWx1ZUNhY2hlKToKKyAgICAgICAgKFdlYkNvcmU6OkNTU1ByaW1pdGl2ZVZhbHVl Q2FjaGU6OmNyZWF0ZUlkZW50aWZpZXJWYWx1ZSk6CisgICAgICAgIChXZWJDb3JlOjpDU1NQcmlt aXRpdmVWYWx1ZUNhY2hlOjpjcmVhdGVDb2xvclZhbHVlKToKKyAgICAgICAgKFdlYkNvcmU6OkNT U1ByaW1pdGl2ZVZhbHVlQ2FjaGU6OmNyZWF0ZVZhbHVlKToKKyAgICAgICAgKiBjc3MvQ1NTUHJp bWl0aXZlVmFsdWVDYWNoZS5oOgorCiAyMDExLTAzLTA3ICBBbnR0aSBLb2l2aXN0byAgPGFudHRp QGFwcGxlLmNvbT4KIAogICAgICAgICBSZXZpZXdlZCBieSBPbGl2ZXIgSHVudC4KSW5kZXg6IFNv dXJjZS9XZWJDb3JlL2Nzcy9DU1NQcmltaXRpdmVWYWx1ZUNhY2hlLmNwcAo9PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09Ci0t LSBTb3VyY2UvV2ViQ29yZS9jc3MvQ1NTUHJpbWl0aXZlVmFsdWVDYWNoZS5jcHAJKHJldmlzaW9u IDgwNDYzKQorKysgU291cmNlL1dlYkNvcmUvY3NzL0NTU1ByaW1pdGl2ZVZhbHVlQ2FjaGUuY3Bw CSh3b3JraW5nIGNvcHkpCkBAIC0zMiw2ICszMiw5IEBAIENTU1ByaW1pdGl2ZVZhbHVlQ2FjaGU6 OkNTU1ByaW1pdGl2ZVZhbHUKICAgICA6IG1fY29sb3JUcmFuc3BhcmVudChDU1NQcmltaXRpdmVW YWx1ZTo6Y3JlYXRlQ29sb3IoQ29sb3I6OnRyYW5zcGFyZW50KSkKICAgICAsIG1fY29sb3JXaGl0 ZShDU1NQcmltaXRpdmVWYWx1ZTo6Y3JlYXRlQ29sb3IoQ29sb3I6OndoaXRlKSkKICAgICAsIG1f Y29sb3JCbGFjayhDU1NQcmltaXRpdmVWYWx1ZTo6Y3JlYXRlQ29sb3IoQ29sb3I6OmJsYWNrKSkK KyAgICAsIG1fcGl4ZWxaZXJvKENTU1ByaW1pdGl2ZVZhbHVlOjpjcmVhdGUoMCwgQ1NTUHJpbWl0 aXZlVmFsdWU6OkNTU19QWCkpCisgICAgLCBtX3BlcmNlbnRaZXJvKENTU1ByaW1pdGl2ZVZhbHVl OjpjcmVhdGUoMCwgQ1NTUHJpbWl0aXZlVmFsdWU6OkNTU19QRVJDRU5UQUdFKSkKKyAgICAsIG1f bnVtYmVyWmVybyhDU1NQcmltaXRpdmVWYWx1ZTo6Y3JlYXRlKDAsIENTU1ByaW1pdGl2ZVZhbHVl OjpDU1NfTlVNQkVSKSkKIHsKIH0KIApAQCAtNDEsMTMgKzQ0LDEzIEBAIENTU1ByaW1pdGl2ZVZh bHVlQ2FjaGU6On5DU1NQcmltaXRpdmVWYWwKIAogUGFzc1JlZlB0cjxDU1NQcmltaXRpdmVWYWx1 ZT4gQ1NTUHJpbWl0aXZlVmFsdWVDYWNoZTo6Y3JlYXRlSWRlbnRpZmllclZhbHVlKGludCBpZGVu dCkKIHsKLSAgICBpZiAoaWRlbnQgPCAwIHx8IGlkZW50ID49IG51bUNTU1ZhbHVlS2V5d29yZHMp CisgICAgaWYgKGlkZW50IDw9IDAgfHwgaWRlbnQgPj0gbnVtQ1NTVmFsdWVLZXl3b3JkcykKICAg ICAgICAgcmV0dXJuIENTU1ByaW1pdGl2ZVZhbHVlOjpjcmVhdGVJZGVudGlmaWVyKGlkZW50KTsK LQotICAgIFJlZlB0cjxDU1NQcmltaXRpdmVWYWx1ZT4gcHJpbWl0aXZlVmFsdWUgPSBtX2lkZW50 aWZpZXJWYWx1ZUNhY2hlW2lkZW50XTsKKyAgICAKKyAgICBSZWZQdHI8Q1NTUHJpbWl0aXZlVmFs dWU+IHByaW1pdGl2ZVZhbHVlID0gbV9pZGVudGlmaWVyVmFsdWVDYWNoZS5nZXQoaWRlbnQpOwog ICAgIGlmICghcHJpbWl0aXZlVmFsdWUpIHsKICAgICAgICAgcHJpbWl0aXZlVmFsdWUgPSBDU1NQ cmltaXRpdmVWYWx1ZTo6Y3JlYXRlSWRlbnRpZmllcihpZGVudCk7Ci0gICAgICAgIG1faWRlbnRp ZmllclZhbHVlQ2FjaGVbaWRlbnRdID0gcHJpbWl0aXZlVmFsdWU7CisgICAgICAgIG1faWRlbnRp ZmllclZhbHVlQ2FjaGUuYWRkKGlkZW50LCBwcmltaXRpdmVWYWx1ZSk7CiAgICAgfQogICAgIHJl dHVybiBwcmltaXRpdmVWYWx1ZS5yZWxlYXNlKCk7CiB9CkBAIC02NiwxMCArNjksMTEgQEAgUGFz c1JlZlB0cjxDU1NQcmltaXRpdmVWYWx1ZT4gQ1NTUHJpbWl0aQogICAgIFJlZlB0cjxDU1NQcmlt aXRpdmVWYWx1ZT4gcHJpbWl0aXZlVmFsdWUgPSBtX2NvbG9yVmFsdWVDYWNoZS5nZXQocmdiVmFs dWUpOwogICAgIGlmIChwcmltaXRpdmVWYWx1ZSkKICAgICAgICAgcmV0dXJuIHByaW1pdGl2ZVZh bHVlLnJlbGVhc2UoKTsKKwogICAgIHByaW1pdGl2ZVZhbHVlID0gQ1NTUHJpbWl0aXZlVmFsdWU6 OmNyZWF0ZUNvbG9yKHJnYlZhbHVlKTsKICAgICAvLyBKdXN0IHdpcGUgb3V0IHRoZSBjYWNoZSBh bmQgc3RhcnQgcmVidWlsZGluZyBpZiBpdCBnZXRzIHRvbyBiaWcuCi0gICAgY29uc3QgaW50IG1h eENvbG9yQ2FjaGVTaXplID0gNTEyOwotICAgIGlmIChtX2NvbG9yVmFsdWVDYWNoZS5zaXplKCkg Pj0gbWF4Q29sb3JDYWNoZVNpemUpCisgICAgY29uc3QgaW50IG1heGltdW1Db2xvckNhY2hlU2l6 ZSA9IDUxMjsKKyAgICBpZiAobV9jb2xvclZhbHVlQ2FjaGUuc2l6ZSgpID49IG1heGltdW1Db2xv ckNhY2hlU2l6ZSkKICAgICAgICAgbV9jb2xvclZhbHVlQ2FjaGUuY2xlYXIoKTsKICAgICBtX2Nv bG9yVmFsdWVDYWNoZS5hZGQocmdiVmFsdWUsIHByaW1pdGl2ZVZhbHVlKTsKICAgICAKQEAgLTc4 LDE3ICs4Miw0MiBAQCBQYXNzUmVmUHRyPENTU1ByaW1pdGl2ZVZhbHVlPiBDU1NQcmltaXRpCiAK IFBhc3NSZWZQdHI8Q1NTUHJpbWl0aXZlVmFsdWU+IENTU1ByaW1pdGl2ZVZhbHVlQ2FjaGU6OmNy ZWF0ZVZhbHVlKGRvdWJsZSB2YWx1ZSwgQ1NTUHJpbWl0aXZlVmFsdWU6OlVuaXRUeXBlcyB0eXBl KQogewotICAgIGlmICh0eXBlID4gbWF4Q2FjaGVkVW5pdFR5cGUgfHwgdmFsdWUgPCAwIHx8IHZh bHVlID49IGNhY2hlZEludGVnZXJDb3VudCkKKyAgICAvLyBTbWFsbCBwb3NpdGl2ZSBpbnRlZ2Vy cyByZXBlYXQgb2Z0ZW4uCisgICAgc3RhdGljIGNvbnN0IGludCBtYXhpbXVtQ2FjaGVhYmxlVmFs dWUgPSAyNTY7CisgICAgaWYgKHZhbHVlIDwgMCB8fCB2YWx1ZSA+IG1heGltdW1DYWNoZWFibGVW YWx1ZSkKICAgICAgICAgcmV0dXJuIENTU1ByaW1pdGl2ZVZhbHVlOjpjcmVhdGUodmFsdWUsIHR5 cGUpOwogCiAgICAgaW50IGludFZhbHVlID0gc3RhdGljX2Nhc3Q8aW50Pih2YWx1ZSk7CiAgICAg aWYgKHZhbHVlICE9IGludFZhbHVlKQogICAgICAgICByZXR1cm4gQ1NTUHJpbWl0aXZlVmFsdWU6 OmNyZWF0ZSh2YWx1ZSwgdHlwZSk7Ci0gICAgUmVmUHRyPENTU1ByaW1pdGl2ZVZhbHVlPiBwcmlt aXRpdmVWYWx1ZSA9IG1faW50ZWdlclZhbHVlQ2FjaGVbaW50VmFsdWVdW3R5cGVdOworICAgIAor ICAgIEludGVnZXJWYWx1ZUNhY2hlKiBjYWNoZTsKKyAgICBzd2l0Y2ggKHR5cGUpIHsKKyAgICBj YXNlIENTU1ByaW1pdGl2ZVZhbHVlOjpDU1NfUFg6CisgICAgICAgIGlmIChpbnRWYWx1ZSA9PSAw KQorICAgICAgICAgICAgcmV0dXJuIG1fcGl4ZWxaZXJvOworICAgICAgICBjYWNoZSA9ICZtX3Bp eGVsVmFsdWVDYWNoZTsKKyAgICAgICAgYnJlYWs7CisgICAgY2FzZSBDU1NQcmltaXRpdmVWYWx1 ZTo6Q1NTX1BFUkNFTlRBR0U6CisgICAgICAgIGlmIChpbnRWYWx1ZSA9PSAwKQorICAgICAgICAg ICAgcmV0dXJuIG1fcGVyY2VudFplcm87CisgICAgICAgIGNhY2hlID0gJm1fcGVyY2VudFZhbHVl Q2FjaGU7CisgICAgICAgIGJyZWFrOworICAgIGNhc2UgQ1NTUHJpbWl0aXZlVmFsdWU6OkNTU19O VU1CRVI6CisgICAgICAgIGlmIChpbnRWYWx1ZSA9PSAwKQorICAgICAgICAgICAgcmV0dXJuIG1f bnVtYmVyWmVybzsKKyAgICAgICAgY2FjaGUgPSAmbV9udW1iZXJWYWx1ZUNhY2hlOworICAgICAg ICBicmVhazsKKyAgICBkZWZhdWx0OgorICAgICAgICByZXR1cm4gQ1NTUHJpbWl0aXZlVmFsdWU6 OmNyZWF0ZSh2YWx1ZSwgdHlwZSk7CisgICAgfQorCisgICAgUmVmUHRyPENTU1ByaW1pdGl2ZVZh bHVlPiBwcmltaXRpdmVWYWx1ZSA9IGNhY2hlLT5nZXQoaW50VmFsdWUpOwogICAgIGlmICghcHJp bWl0aXZlVmFsdWUpIHsKICAgICAgICAgcHJpbWl0aXZlVmFsdWUgPSBDU1NQcmltaXRpdmVWYWx1 ZTo6Y3JlYXRlKHZhbHVlLCB0eXBlKTsKLSAgICAgICAgbV9pbnRlZ2VyVmFsdWVDYWNoZVtpbnRW YWx1ZV1bdHlwZV0gPSBwcmltaXRpdmVWYWx1ZTsKKyAgICAgICAgY2FjaGUtPmFkZChpbnRWYWx1 ZSwgcHJpbWl0aXZlVmFsdWUpOwogICAgIH0KKyAgICAKICAgICByZXR1cm4gcHJpbWl0aXZlVmFs dWUucmVsZWFzZSgpOwogfQogCkluZGV4OiBTb3VyY2UvV2ViQ29yZS9jc3MvQ1NTUHJpbWl0aXZl VmFsdWVDYWNoZS5oCj09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT0KLS0tIFNvdXJjZS9XZWJDb3JlL2Nzcy9DU1NQcmltaXRp dmVWYWx1ZUNhY2hlLmgJKHJldmlzaW9uIDgwNDYzKQorKysgU291cmNlL1dlYkNvcmUvY3NzL0NT U1ByaW1pdGl2ZVZhbHVlQ2FjaGUuaAkod29ya2luZyBjb3B5KQpAQCAtNDksNyArNDksNyBAQCBw dWJsaWM6CiBwcml2YXRlOgogICAgIENTU1ByaW1pdGl2ZVZhbHVlQ2FjaGUoKTsKIAotICAgIHR5 cGVkZWYgUmVmUHRyPENTU1ByaW1pdGl2ZVZhbHVlPiBJZGVudGlmaWVyVmFsdWVDYWNoZVtudW1D U1NWYWx1ZUtleXdvcmRzXTsKKyAgICB0eXBlZGVmIEhhc2hNYXA8aW50LCBSZWZQdHI8Q1NTUHJp bWl0aXZlVmFsdWU+ID4gSWRlbnRpZmllclZhbHVlQ2FjaGU7CiAgICAgSWRlbnRpZmllclZhbHVl Q2FjaGUgbV9pZGVudGlmaWVyVmFsdWVDYWNoZTsKIAogICAgIHR5cGVkZWYgSGFzaE1hcDx1bnNp Z25lZCwgUmVmUHRyPENTU1ByaW1pdGl2ZVZhbHVlPiA+IENvbG9yVmFsdWVDYWNoZTsKQEAgLTU4 LDEyICs1OCwxMyBAQCBwcml2YXRlOgogICAgIFJlZlB0cjxDU1NQcmltaXRpdmVWYWx1ZT4gbV9j b2xvcldoaXRlOwogICAgIFJlZlB0cjxDU1NQcmltaXRpdmVWYWx1ZT4gbV9jb2xvckJsYWNrOwog ICAgIAotICAgIC8vIFNtYWxsIGludGVnZXJzIGFyZSB2ZXJ5IGNvbW1vbi4gU2hhcmUgdGhlbS4K LSAgICBzdGF0aWMgY29uc3QgaW50IGNhY2hlZEludGVnZXJDb3VudCA9IDEyODsKLSAgICAvLyBP dGhlciBjb21tb24gcHJpbWl0aXZlIHR5cGVzIGhhdmUgVW5pdFR5cGVzIHNtYWxsZXIgdGhhbiB0 aGlzLgotICAgIHN0YXRpYyBjb25zdCBpbnQgbWF4Q2FjaGVkVW5pdFR5cGUgPSBDU1NQcmltaXRp dmVWYWx1ZTo6Q1NTX1BYOwotICAgIHR5cGVkZWYgUmVmUHRyPENTU1ByaW1pdGl2ZVZhbHVlPiBJ bnRlZ2VyVmFsdWVDYWNoZVtjYWNoZWRJbnRlZ2VyQ291bnRdW21heENhY2hlZFVuaXRUeXBlICsg MV07Ci0gICAgSW50ZWdlclZhbHVlQ2FjaGUgbV9pbnRlZ2VyVmFsdWVDYWNoZTsKKyAgICB0eXBl ZGVmIEhhc2hNYXA8aW50LCBSZWZQdHI8Q1NTUHJpbWl0aXZlVmFsdWU+ID4gSW50ZWdlclZhbHVl Q2FjaGU7CisgICAgUmVmUHRyPENTU1ByaW1pdGl2ZVZhbHVlPiBtX3BpeGVsWmVybzsKKyAgICBS ZWZQdHI8Q1NTUHJpbWl0aXZlVmFsdWU+IG1fcGVyY2VudFplcm87CisgICAgUmVmUHRyPENTU1By aW1pdGl2ZVZhbHVlPiBtX251bWJlclplcm87CisgICAgSW50ZWdlclZhbHVlQ2FjaGUgbV9waXhl bFZhbHVlQ2FjaGU7CisgICAgSW50ZWdlclZhbHVlQ2FjaGUgbV9wZXJjZW50VmFsdWVDYWNoZTsK KyAgICBJbnRlZ2VyVmFsdWVDYWNoZSBtX251bWJlclZhbHVlQ2FjaGU7CiB9OwogCiB9Cg==