99118 2012-10-11 16:49:39 -0700 [JSC] >10% of Dromaeo dom-query.html is atomizing the same StringImpl's passed from JSC to getElementByTagName 2012-10-15 16:19:29 -0700 1 1 1 Unclassified WebKit JavaScriptCore 528+ (Nightly build) Unspecified Unspecified NEW InRadar P2 Normal --- 75571 92486 99191 1 eric webkit-unassigned barraclough ggaren haraken msaboff oliver webkit-bug-importer oldest_to_newest 740430 0 eric 2012-10-11 16:49:39 -0700 JSC Should atomize constant strings before handing them to WebCore The Dromaeo dom-query benchmark has the following subtest: for ( var i = 0; i < num; i++ ) { var elems = document.getElementsByTagName("*"); ret = elems[elems.length-1].nodeType; } That spends nearly 10% of total time in AtomicString hash lookups for "*". "*" is of course already in the AtomicString hash (also a global called WTF::starAtom). I suspect that JSC may already have code to identify "*" as a constant. If it were to notice that it is a short string, and to do an AtomicString lookup for it, then it could pass WebCore an already atomized StringImpl, which would cause the AtomicString(const String&) constructor to go down the fast-path, and presumably drop 10% off this test! I suspect variants of this may affect real world usage, but I don't know how much of a cost Atomizing constants in JSC would be on other benchmarks (or how complicated it would be). I leave those up to you JSC experts. I have not yet tested V8 to see if they already do this. 740447 1 ggaren 2012-10-11 16:59:42 -0700 <rdar://problem/12484322> 740448 2 ggaren 2012-10-11 17:00:57 -0700 For this optimization, JSC could put Identifiers in the AtomicString table instead of or in addition to the Identifier table. 740540 3 eric 2012-10-11 19:19:54 -0700 Looking at the sample more, it looks like this is more like avoiding AtomicString lookup due to Identifier/AtomicString StringImpl* mismatches has the potential to be more like at 15+% win on dom-query.html: Running Time Self Symbol Name 3472.0ms 7.5% 3472.0 WTF::HashTableAddResult<WTF::HashTableIterator<WTF::StringImpl*, WTF::StringImpl*, WTF::IdentityExtractor, WTF::StringHash, WTF::HashTraits<WTF::StringImpl*>, WTF::HashTraits<WTF::StringImpl*> > > WTF::HashTable<WTF::StringImpl*, WTF::StringImpl*, WTF::IdentityExtractor, WTF::StringHash, WTF::HashTraits<WTF::StringImpl*>, WTF::HashTraits<WTF::StringImpl*> >::add<WTF::IdentityHashTranslator<WTF::StringHash>, WTF::StringImpl*, WTF::StringImpl*>(WTF::StringImpl* const&, WTF::StringImpl* const&) 1615.0ms 3.4% 1615.0 WTF::StringHash::equal(WTF::StringImpl const*, WTF::StringImpl const*) 1524.0ms 3.2% 1524.0 WTF::AtomicString::addSlowCase(WTF::StringImpl*) 561.0ms 1.2% 561.0 WTF::StringImpl::hashSlowCase() const Are all samples which stem from this in dom-query.html. :) 740547 4 eric 2012-10-11 19:34:16 -0700 This is also another 8-10% of dom-attr.html. 741096 5 oliver 2012-10-12 12:04:48 -0700 JSC does intern all string literals in source code. I'm unsure how feasible sharing jsc's interned strings with AtomicString is (multiple JSC contexts have separate interned strings for the same literal for example). Also it would require some communication between JSC and WebCore of the sort that would be easier if we weren't having to deal with two JS engines. That said, what strings are we seeing that aren't being atomised? There are some ways to optimize these kinds of lookup to avoid hashing in common cases. 741127 6 eric 2012-10-12 12:58:50 -0700 (In reply to comment #5) > JSC does intern all string literals in source code. I'm unsure how feasible sharing jsc's interned strings with AtomicString is (multiple JSC contexts have separate interned strings for the same literal for example). Also it would require some communication between JSC and WebCore of the sort that would be easier if we weren't having to deal with two JS engines. For what it's worth, I believe v8 has the same bug. > That said, what strings are we seeing that aren't being atomised? The case is that "*" or "div" or whatever the author has specified is correctly being Interned (as you noted above), but then that same Interned StringImpl is being handed to getElementsByTagName, getElementById, etc. every time. Since that StringImpl is not marked isAtomic(), we do a hash-lookup to find the corresponding Atomized StringImpl (which is slow): http://trac.webkit.org/browser/trunk/Source/WTF/wtf/text/AtomicString.h#L176 A win here would either be to have JSC use the same underlying StringImpl as WebCore (or vice-versa), or to have some fancy way to map between them. One possible fix might be to pre-warm JSC's unique StringImpl table with the ones from WebCore? 741129 7 eric 2012-10-12 13:01:06 -0700 I'm not sure I was clear above. JSC hands WebCore the same StringImpl for constants, every time. But unfortunately that StringImpl is not marked isAtomic(), so when WebCore needs an AtomicString, it does a hash-lookup from the StringImpl provided by JSC, to find the corresponding "Atomic" StringImpl in WebCore. That hash lookup is slow, and ideally would be avoided by having a faster way to map from JSC constants to AtomicStrings. :) 741141 8 oliver 2012-10-12 13:15:14 -0700 (In reply to comment #6) > (In reply to comment #5) > > JSC does intern all string literals in source code. I'm unsure how feasible sharing jsc's interned strings with AtomicString is (multiple JSC contexts have separate interned strings for the same literal for example). Also it would require some communication between JSC and WebCore of the sort that would be easier if we weren't having to deal with two JS engines. > > For what it's worth, I believe v8 has the same bug. > > > That said, what strings are we seeing that aren't being atomised? > > The case is that "*" or "div" or whatever the author has specified is correctly being Interned (as you noted above), but then that same Interned StringImpl is being handed to getElementsByTagName, getElementById, etc. every time. Since that StringImpl is not marked isAtomic(), we do a hash-lookup to find the corresponding Atomized StringImpl (which is slow): > http://trac.webkit.org/browser/trunk/Source/WTF/wtf/text/AtomicString.h#L176 > > A win here would either be to have JSC use the same underlying StringImpl as WebCore (or vice-versa), or to have some fancy way to map between them. > > One possible fix might be to pre-warm JSC's unique StringImpl table with the ones from WebCore? StringImpl's are unique per JSC-heap, which isn't a guarantee that they're unique in the context of the DOM. We could maybe fix that for commonJSGlobalData, but that feels fragile. What I was wanting to know is how many unique strings end up missing the cache hit (i mean non-Atomic strings coming from JS)? Some stats on what those strings are just accumulated via printf logging into a histogram. Depending on the spread I have an idea for a way to greatly improve the lookup speed even on a miss, when the string is already present in the Atomics table. 741151 9 eric 2012-10-12 13:33:19 -0700 (In reply to comment #8) > (In reply to comment #6) > > (In reply to comment #5) > What I was wanting to know is how many unique strings end up missing the cache hit (i mean non-Atomic strings coming from JS)? Do you mean specific to this benchmark? Or some larger set of pages? My understanding is that any string created in JS, by JSC, will be Interned, but never be an AtomicString, and thus need to go through a hash lookup before it can be used in WebCore as an AtomicString? Every DOM API which takes an AtomicString as a parameter, will require a Hash lookup when taking a string from JSC, if I'm understanding correctly. If JSC got the string from the DOM/WebCore originally and handed us back the same StringImpl, then we'd avoid this hit of course. > Some stats on what those strings are just accumulated via printf logging into a histogram. > > Depending on the spread I have an idea for a way to greatly improve the lookup speed even on a miss, when the string is already present in the Atomics table. Happy to oblidge, but could you restate what data you're looking for, I'm not sure I understand yet? It sounds like you'd be interested in having some information on how often a StringImpl which came from JSC is used for a hash lookup in AtomicString? Or maybe how often an Interned string from JSC is? I assume over something like the PLT or some representative set of pages? 741152 10 eric 2012-10-12 13:33:56 -0700 (I hope I'm using "Interned" correctly, I've interpreted that to mean the JSC equivilent of unique/atomic.) 741167 11 oliver 2012-10-12 13:44:12 -0700 > Happy to oblidge, but could you restate what data you're looking for, I'm not sure I understand yet? I want to know what strings we end up doing a hash lookup for - i don't care if they're interned in the JS engine, as that isn't something we can take advantage of (multiple GC heaps == multiple "unique" versions of the same string). What I want is a histogram of strings that require a hash lookup to get to the atomicstring. 741262 12 eric 2012-10-12 15:16:47 -0700 By hist(In reply to comment #11) > > Happy to oblidge, but could you restate what data you're looking for, I'm not sure I understand yet? > > I want to know what strings we end up doing a hash lookup for - i don't care if they're interned in the JS engine, as that isn't something we can take advantage of (multiple GC heaps == multiple "unique" versions of the same string). > > What I want is a histogram of strings that require a hash lookup to get to the atomicstring. Which buckets did you want for such a histogram? Were you looking for a histogram over strings bucketed by length? Are you looking for a frequency count based on string content? (Like "foo" : 1M times, "bar": 9 times, "baz" 75 times)? I added the following to: PassRefPtr<StringImpl> AtomicString::add(StringImpl* r) { if (!r) return r; printf("add\n"); if (r->isAtomic()) return r; printf("slow\n"); return addSlowCase(r); } And then did run-safari Dromeao/dom-query.html > strings.txt % grep add strings.txt | wc -l 151839657 % grep slow strings.txt | wc -l 115803580 So 76% of all AtomicString(StringImpl*) calls, ended up doing a hash lookup during Dromeao/dom-query.html. I don't think that number is particularly interesting, other than that it's lower than I expect it to be (I expected something like 99% on this benchmark.) NOTE: That is counting strings which came into AtomicString() already as a StringImpl. Meaning they were turned into a String, w/o being atomized (this excludes constants from C++, buffers from the parser, etc.) 741265 13 eric 2012-10-12 15:23:38 -0700 To be clear, the add(StringImpl*) case covers AtomicStrings which had been converted to String/StringImple somewhere else in the engine. I chose this entry point to avoid counting strings which came from some other source (like constants in c++, or the HTML parser), or for strings which are created from a substring of other strings (add(StringImpl*, int start, int end) is a wholly separate beast). I'm generating frequency count data for add(StringImpl*) from the web now. (I don't think frequency count data from dom-query.html would be very interesting... and it's huge anyway.) 741266 14 oliver 2012-10-12 15:24:58 -0700 (In reply to comment #13) > To be clear, the add(StringImpl*) case covers AtomicStrings which had been converted to String/StringImple somewhere else in the engine. > > I chose this entry point to avoid counting strings which came from some other source (like constants in c++, or the HTML parser), or for strings which are created from a substring of other strings (add(StringImpl*, int start, int end) is a wholly separate beast). > > I'm generating frequency count data for add(StringImpl*) from the web now. (I don't think frequency count data from dom-query.html would be very interesting... and it's huge anyway.) I don't care about the frequency of hit vs. non-hit, i want a histogram of what strings take the slow case 741286 15 eric 2012-10-12 15:55:26 -0700 1469 addSlowCase(StringImpl*) calls loading apple.com top 10 strings by content: 430 data-hires 126 Referer 115 User-Agent 57 http 40 Accept 33 \u000A\u0009 30 onclick 21 mousedown 19 div 15 \u000A\u0009\u0009\u0009\u0009\u0009 8835 addSlowCase(StringImpl*) calls loading my gmail.com top 10 strings by content: 274 div 250 User-Agent 243 Referer 219 mouseover 200 email 195 keydown 183 mouseout 174 click 146 \u000A 145 .ajl 26518 addSlowCase(StringImpl*) calls loading a docs.google.com spreadsheet 2536 div 1286 role 747 -webkit-user-select: none; 601 goog-menuitem-content 542 goog-menuitem 537 * 488 mousedown 470 span 346 mouseup 342 id Remember, these stats only track strings which are being added to the AtomicString hash, which already existed as StringImpls in our engine before that point. 741292 16 ggaren 2012-10-12 16:01:54 -0700 FWIW, I believe this problem case only arises if WebCore already has an entry in the AtomicString table for the same string. (If the JS string is the first instance of the string, it will "win" in the table.) 741294 17 168504 eric 2012-10-12 16:07:34 -0700 Created attachment 168504 Patch I used to generate addSlowCase stats 741295 18 eric 2012-10-12 16:08:14 -0700 Sorry, webkit-patch upload doesn't have a --no-assign option yet. :) 741483 19 ggaren 2012-10-13 09:50:35 -0700 Since JSC has looser threading rules than WebCore, I wonder if WebCore could drive this optimization. For example, WebCore could put AtomicStrings in the Identifier table, or JSC could have an optional interface for supplying your own identifier table, and WebCore could supply the AtomicString table. 742557 20 eric 2012-10-15 16:13:32 -0700 I've now confirmed v8 has the same trouble. Filing a separate bug for that. 742568 21 eric 2012-10-15 16:19:29 -0700 bug 99383 is the v8 equivalent. Feel free to re-title, close, however you like to this bug. I think I've added all the necessary information at this point. 168504 2012-10-12 16:07:34 -0700 2012-10-12 16:07:34 -0700 Patch I used to generate addSlowCase stats bug-99118-20121012160636.patch text/plain 2634 eric U3VidmVyc2lvbiBSZXZpc2lvbjogMTMxMTIwCmRpZmYgLS1naXQgYS9Tb3VyY2UvV1RGL3d0Zi90 ZXh0L0F0b21pY1N0cmluZy5jcHAgYi9Tb3VyY2UvV1RGL3d0Zi90ZXh0L0F0b21pY1N0cmluZy5j cHAKaW5kZXggY2JiNWEyMGVlZDE2YjE3OGY5NDVjY2I0ZTZkNzA1ZjliNmExM2NiNC4uMjNiNjhi ODUzMzY3Y2QyN2M0YTNmMWRiMWMwMzhiZDEwOTU1OTVlYiAxMDA2NDQKLS0tIGEvU291cmNlL1dU Ri93dGYvdGV4dC9BdG9taWNTdHJpbmcuY3BwCisrKyBiL1NvdXJjZS9XVEYvd3RmL3RleHQvQXRv bWljU3RyaW5nLmNwcApAQCAtMjYsNiArMjYsNyBAQAogCiAjaW5jbHVkZSAiU3RyaW5nSGFzaC5o IgogI2luY2x1ZGUgPHd0Zi9IYXNoU2V0Lmg+CisjaW5jbHVkZSA8d3RmL0hleE51bWJlci5oPgog I2luY2x1ZGUgPHd0Zi9UaHJlYWRpbmcuaD4KICNpbmNsdWRlIDx3dGYvV1RGVGhyZWFkRGF0YS5o PgogI2luY2x1ZGUgPHd0Zi91bmljb2RlL1VURjguaD4KQEAgLTI4MSw2ICsyODIsNDAgQEAgc3Ry dWN0IFN1YnN0cmluZ1RyYW5zbGF0b3IgewogICAgIH0KIH07CiAKK1ZlY3RvcjxjaGFyPiBhc2Np aURlYnVnKFN0cmluZ0ltcGwqKTsKKworVmVjdG9yPGNoYXI+IGFzY2lpRGVidWcoU3RyaW5nSW1w bCogaW1wbCkKK3sKKyAgICBpZiAoIWltcGwpCisgICAgICAgIHJldHVybiBhc2NpaURlYnVnKFN0 cmluZygiW251bGxdIikuaW1wbCgpKTsKKworICAgIFZlY3RvcjxjaGFyPiBidWZmZXI7CisgICAg Zm9yICh1bnNpZ25lZCBpID0gMDsgaSA8IGltcGwtPmxlbmd0aCgpOyArK2kpIHsKKyAgICAgICAg VUNoYXIgY2ggPSAoKmltcGwpW2ldOworICAgICAgICBpZiAoaXNBU0NJSVByaW50YWJsZShjaCkp IHsKKyAgICAgICAgICAgIGlmIChjaCA9PSAnXFwnKQorICAgICAgICAgICAgICAgIGJ1ZmZlci5h cHBlbmQoY2gpOworICAgICAgICAgICAgYnVmZmVyLmFwcGVuZChjaCk7CisgICAgICAgIH0gZWxz ZSB7CisgICAgICAgICAgICBidWZmZXIuYXBwZW5kKCdcXCcpOworICAgICAgICAgICAgYnVmZmVy LmFwcGVuZCgndScpOworICAgICAgICAgICAgYXBwZW5kVW5zaWduZWRBc0hleEZpeGVkU2l6ZShj aCwgYnVmZmVyLCA0KTsKKyAgICAgICAgfQorICAgIH0KKyAgICBidWZmZXIuYXBwZW5kKCdcMCcp OworICAgIHJldHVybiBidWZmZXI7Cit9CisKK1Bhc3NSZWZQdHI8U3RyaW5nSW1wbD4gQXRvbWlj U3RyaW5nOjphZGQoU3RyaW5nSW1wbCogcikKK3sKKyAgICBpZiAoIXIpCisgICAgICAgIHJldHVy biByOworICAgIGlmIChyLT5pc0F0b21pYygpKQorICAgICAgICByZXR1cm4gcjsKKyAgICBwcmlu dGYoIiVzXG4iLCBhc2NpaURlYnVnKHIpLmRhdGEoKSk7CisgICAgcmV0dXJuIGFkZFNsb3dDYXNl KHIpOworfQorCiBQYXNzUmVmUHRyPFN0cmluZ0ltcGw+IEF0b21pY1N0cmluZzo6YWRkKFN0cmlu Z0ltcGwqIGJhc2VTdHJpbmcsIHVuc2lnbmVkIHN0YXJ0LCB1bnNpZ25lZCBsZW5ndGgpCiB7CiAg ICAgaWYgKCFiYXNlU3RyaW5nKQpkaWZmIC0tZ2l0IGEvU291cmNlL1dURi93dGYvdGV4dC9BdG9t aWNTdHJpbmcuaCBiL1NvdXJjZS9XVEYvd3RmL3RleHQvQXRvbWljU3RyaW5nLmgKaW5kZXggYzI1 YjEzNTliY2VlZGRkYWEyOTZjMDcyZGVmNDNiNGJiODdkNjA2Mi4uNGVlN2QxMmQ2OTg2N2QxM2Jm NjI2NzZhOWYwNWNhM2ZmMDIxNzc1MSAxMDA2NDQKLS0tIGEvU291cmNlL1dURi93dGYvdGV4dC9B dG9taWNTdHJpbmcuaAorKysgYi9Tb3VyY2UvV1RGL3d0Zi90ZXh0L0F0b21pY1N0cmluZy5oCkBA IC0xNzMsMTIgKzE3Myw3IEBAIHByaXZhdGU6CiAgICAgV1RGX0VYUE9SVF9TVFJJTkdfQVBJIHN0 YXRpYyBQYXNzUmVmUHRyPFN0cmluZ0ltcGw+IGFkZChjb25zdCBVQ2hhciosIHVuc2lnbmVkIGxl bmd0aCwgdW5zaWduZWQgZXhpc3RpbmdIYXNoKTsKICAgICBXVEZfRVhQT1JUX1NUUklOR19BUEkg c3RhdGljIFBhc3NSZWZQdHI8U3RyaW5nSW1wbD4gYWRkKGNvbnN0IFVDaGFyKik7CiAgICAgV1RG X0VYUE9SVF9TVFJJTkdfQVBJIHN0YXRpYyBQYXNzUmVmUHRyPFN0cmluZ0ltcGw+IGFkZChTdHJp bmdJbXBsKiwgdW5zaWduZWQgb2Zmc2V0LCB1bnNpZ25lZCBsZW5ndGgpOwotICAgIEFMV0FZU19J TkxJTkUgc3RhdGljIFBhc3NSZWZQdHI8U3RyaW5nSW1wbD4gYWRkKFN0cmluZ0ltcGwqIHIpCi0g ICAgewotICAgICAgICBpZiAoIXIgfHwgci0+aXNBdG9taWMoKSkKLSAgICAgICAgICAgIHJldHVy biByOwotICAgICAgICByZXR1cm4gYWRkU2xvd0Nhc2Uocik7Ci0gICAgfQorICAgIFdURl9FWFBP UlRfU1RSSU5HX0FQSSBzdGF0aWMgUGFzc1JlZlB0cjxTdHJpbmdJbXBsPiBhZGQoU3RyaW5nSW1w bCopOwogICAgIFdURl9FWFBPUlRfU1RSSU5HX0FQSSBzdGF0aWMgUGFzc1JlZlB0cjxTdHJpbmdJ bXBsPiBhZGRGcm9tTGl0ZXJhbERhdGEoY29uc3QgY2hhciogY2hhcmFjdGVycywgdW5zaWduZWQg bGVuZ3RoKTsKICAgICBXVEZfRVhQT1JUX1NUUklOR19BUEkgc3RhdGljIFBhc3NSZWZQdHI8U3Ry aW5nSW1wbD4gYWRkU2xvd0Nhc2UoU3RyaW5nSW1wbCopOwogICAgIFdURl9FWFBPUlRfU1RSSU5H X0FQSSBzdGF0aWMgQXRvbWljU3RyaW5nIGZyb21VVEY4SW50ZXJuYWwoY29uc3QgY2hhciosIGNv bnN0IGNoYXIqKTsK