1 comment:
Patchset:
Hi Mason, The idea of this patch comes from Webcore, it caches attribute value during parsing instead of AtomicString, the pinpoint result shows a 0.7% progression, would you help me to reivew this? Thanks very much!
The pinpoint result: https://pinpoint-dot-chromeperf.appspot.com/job/15fa0fc0060000
To view, visit change 4310894. To unsubscribe, or for help writing mail filters, visit settings.
Bin Liao uploaded patch set #5 to this change.
Add atomic string cache to speed up attribute value parsing
The idea of this patch comes from WebCore
https://github.com/WebKit/WebKit/commit/86c93355e0e01ca5f382b1b6b125eeb9c6d34ac5 and https://github.com/WebKit/WebKit/commit/153929d8a8d479703a52fc8a86a8303b0ad64995
It caches attribute value instead of constructing AtomicString and implements a simple hash algorithm, it gets 0.7% progression report by pinpoint test on Speedometer2.0
Change-Id: I3275fbe1135c256b011c925ff81a0f258a0d0815
---
M third_party/blink/renderer/core/dom/document.cc
M third_party/blink/renderer/core/html/build.gni
M third_party/blink/renderer/core/html/parser/atomic_html_token.h
A third_party/blink/renderer/core/html/parser/atomic_string_cache.h
M third_party/blink/renderer/core/html/parser/html_document_parser_fastpath.cc
M third_party/blink/renderer/core/html/parser/html_token.h
6 files changed, 114 insertions(+), 8 deletions(-)
To view, visit change 4310894. To unsubscribe, or for help writing mail filters, visit settings.
1 comment:
Patchset:
Hi Mason, The idea of this patch comes from Webcore, it caches attribute value during parsing instead of AtomicString, the pinpoint result shows a 0.7% progression, would you help me to reivew this? Thanks very much!
The pinpoint result: https://pinpoint-dot-chromeperf.appspot.com/job/15fa0fc0060000
To view, visit change 4310894. To unsubscribe, or for help writing mail filters, visit settings.
Attention is currently required from: Mason Freed.
Bin Liao would like Mason Freed to review this change.
Add atomic string cache to speed up attribute value parsing
The idea of this patch comes from WebCore
https://github.com/WebKit/WebKit/commit/86c93355e0e01ca5f382b1b6b125eeb9c6d34ac5 and https://github.com/WebKit/WebKit/commit/153929d8a8d479703a52fc8a86a8303b0ad64995
It caches attribute value instead of constructing AtomicString and implements a simple hash algorithm, it gets 0.7% progression report by pinpoint test on Speedometer2.0
Change-Id: I3275fbe1135c256b011c925ff81a0f258a0d0815
---
M third_party/blink/renderer/core/dom/document.cc
M third_party/blink/renderer/core/html/build.gni
M third_party/blink/renderer/core/html/parser/atomic_html_token.h
A third_party/blink/renderer/core/html/parser/atomic_string_cache.h
M third_party/blink/renderer/core/html/parser/html_document_parser_fastpath.cc
M third_party/blink/renderer/core/html/parser/html_token.h
6 files changed, 114 insertions(+), 8 deletions(-)
To view, visit change 4310894. To unsubscribe, or for help writing mail filters, visit settings.
Attention is currently required from: Bin Liao.
1 comment:
Patchset:
Sorry for the delay reviewing this one. Will get to it soon, sorry!
To view, visit change 4310894. To unsubscribe, or for help writing mail filters, visit settings.
Attention is currently required from: Bin Liao, Scott Violet.
Mason Freed would like Scott Violet to review this change authored by Bin Liao.
Add atomic string cache to speed up attribute value parsing
The idea of this patch comes from WebCore
https://github.com/WebKit/WebKit/commit/86c93355e0e01ca5f382b1b6b125eeb9c6d34ac5 and https://github.com/WebKit/WebKit/commit/153929d8a8d479703a52fc8a86a8303b0ad64995
It caches attribute value instead of constructing AtomicString and implements a simple hash algorithm, it gets 0.7% progression report by pinpoint test on Speedometer2.0
Change-Id: I3275fbe1135c256b011c925ff81a0f258a0d0815
---
M third_party/blink/renderer/core/dom/document.cc
M third_party/blink/renderer/core/html/build.gni
M third_party/blink/renderer/core/html/parser/atomic_html_token.h
A third_party/blink/renderer/core/html/parser/atomic_string_cache.h
M third_party/blink/renderer/core/html/parser/html_document_parser_fastpath.cc
M third_party/blink/renderer/core/html/parser/html_token.h
6 files changed, 114 insertions(+), 8 deletions(-)
To view, visit change 4310894. To unsubscribe, or for help writing mail filters, visit settings.
Attention is currently required from: Bin Liao, Scott Violet.
13 comments:
Commit Message:
Patch Set #5, Line 11: It caches attribute value instead of constructing AtomicString and implements a simple hash algorithm, it gets 0.7% progression report by pinpoint test on Speedometer2.0
Is the 0.7% progression something you measured locally? Or is that from the WebKit patch?
I think we'd want to run some of our own testing of this number. You could try running some pinpoints on speedometer, it should be able to see a 0.7% improvement, I'd hope.
Patchset:
Thanks for the patch! I added some comments. Also +sky@ - it'd be nice to get a second look.
File third_party/blink/renderer/core/html/parser/atomic_html_token.h:
// The string pointer in |value| is null for attributes with no values, but
// the null atom is used to represent absence of attributes; attributes with
// no values have the value set to an empty atom instead.
I think this comment now belongs in AtomicStringCache instead of here.
File third_party/blink/renderer/core/html/parser/atomic_string_cache.h:
Patch Set #5, Line 9: HTMLAtomicStringCache
This needs a comment explaining what it does, what it's used for, and most importantly, who owns this.
kMaxStringLengthForCache = 36;
static constexpr auto kCapacity = 512;
Can you comment (and add a comment above them) on how you chose these two values? 36 seems like a very specific number.
Patch Set #5, Line 31: kCapacity
Are we worried about memory? This will keep 512 strings alive for the life of the document, in the worst case. So I guess 18kB per document. Assuming ~10 frames, that's 180kB order of magnitude. Maybe ok, just asking to make sure.
Patch Set #5, Line 34: MakeAtomString
Maybe `MakeCachedAtomicString()` instead? Or at least s/Atom/Atomic.
Patch Set #5, Line 50: AtomicString result(string.data(), static_cast<unsigned>(length));
So this just keeps the latest attribute only, in the case of a cache collision, right? That'll be a perf regression in the case that two attributes that collide are used heavily on a page. Probably this is a very corner case.
Patch Set #5, Line 52: return result;
You could eliminate this return, since it'll get returned below.
ALWAYS_INLINE static AtomicString MakeAtomString(
base::span<const CharacterType> string) {
if (string.empty()) {
return g_empty_atom;
}
auto length = string.size();
if (length > kMaxStringLengthForCache) {
return AtomicString(string.data(), static_cast<unsigned>(length));
}
auto first_character = string[0];
auto last_character = string[length - 1];
auto& slot = AtomicStringCacheSlot(first_character, last_character, length);
if (!Equal(slot.Impl(), string.data(), static_cast<unsigned>(length))) {
AtomicString result(string.data(), static_cast<unsigned>(length));
slot = result;
return result;
}
return slot;
}
It sucks to have two essentially-copy-paste versions of this. Any cool way (via more template magic) to combine all three versions into one?
unsigned hash =
(first_character << 6) ^ ((last_character << 14) ^ first_character);
Can you comment (here and as a comment) how you chose this particular hash function?
File third_party/blink/renderer/core/html/parser/html_document_parser_fastpath.cc:
// The string pointer in |value| is null for attributes with no values, but
// the null atom is used to represent absence of attributes; attributes with
// no values have the value set to an empty atom instead.
I think this comment, plus the code at 899 below, can be removed. that's now handled by MakeAttributeValue.
if (value.IsNull()) {
value = g_empty_atom;
}
You could convert this to
`DCHECK(!value.IsNull());`
To view, visit change 4310894. To unsubscribe, or for help writing mail filters, visit settings.
Attention is currently required from: Mason Freed, Scott Violet.
13 comments:
Commit Message:
Patch Set #5, Line 11: It caches attribute value instead of constructing AtomicString and implements a simple hash algorithm, it gets 0.7% progression report by pinpoint test on Speedometer2.0
Is the 0.7% progression something you measured locally? Or is that from the WebKit patch? […]
This 0.7% improvement is reported by google pinpoint test of this patch.
https://pinpoint-dot-chromeperf.appspot.com/job/15fa0fc0060000
I also test it locally on intel platform, it also gets 0.6% ~ 0.8% progression on different devices.
Patchset:
Thanks for Mason's review.
File third_party/blink/renderer/core/html/parser/atomic_html_token.h:
// The string pointer in |value| is null for attributes with no values, but
// the null atom is used to represent absence of attributes; attributes with
// no values have the value set to an empty atom instead.
I think this comment now belongs in AtomicStringCache instead of here.
Done
File third_party/blink/renderer/core/html/parser/atomic_string_cache.h:
Patch Set #5, Line 9: HTMLAtomicStringCache
This needs a comment explaining what it does, what it's used for, and most importantly, who owns thi […]
Done
kMaxStringLengthForCache = 36;
static constexpr auto kCapacity = 512;
Can you comment (and add a comment above them) on how you chose these two values? 36 seems like a ve […]
This value I used the same as WebCore, maybe this is a tuned by WebCore to get a good performance
Patch Set #5, Line 31: kCapacity
Are we worried about memory? This will keep 512 strings alive for the life of the document, in the w […]
Yeah, this compacts the memory, do we have any memory benchmark? Maybe a memory benchmark is needed here
Patch Set #5, Line 34: MakeAtomString
Maybe `MakeCachedAtomicString()` instead? Or at least s/Atom/Atomic.
Done
Patch Set #5, Line 50: AtomicString result(string.data(), static_cast<unsigned>(length));
So this just keeps the latest attribute only, in the case of a cache collision, right? That'll be a […]
Actually this keeps latest kCapacity(512) attributes here
Patch Set #5, Line 52: return result;
You could eliminate this return, since it'll get returned below.
Done
ALWAYS_INLINE static AtomicString MakeAtomString(
base::span<const CharacterType> string) {
if (string.empty()) {
return g_empty_atom;
}
auto length = string.size();
if (length > kMaxStringLengthForCache) {
return AtomicString(string.data(), static_cast<unsigned>(length));
}
auto first_character = string[0];
auto last_character = string[length - 1];
auto& slot = AtomicStringCacheSlot(first_character, last_character, length);
if (!Equal(slot.Impl(), string.data(), static_cast<unsigned>(length))) {
AtomicString result(string.data(), static_cast<unsigned>(length));
slot = result;
return result;
}
return slot;
}
It sucks to have two essentially-copy-paste versions of this. […]
Yes, this copy-paste code is really bad, I have tried, but it's really hard to user template to simplify these two functions, however, I will optimize the LChar and UChar vector to user literal buffer in fast path parser after this CL landed, so this function can be simplified.
unsigned hash =
(first_character << 6) ^ ((last_character << 14) ^ first_character);
Can you comment (here and as a comment) how you chose this particular hash function?
This file is totally porting from WebCore, it claims that the default string hashing algorithm only barely outperforms
this simple hash function on Speedometer (i.e., a cache hit rate of 99.24% using the default hash algorithm vs.
99.15% using the "first/last character and length" hash)
File third_party/blink/renderer/core/html/parser/html_document_parser_fastpath.cc:
// The string pointer in |value| is null for attributes with no values, but
// the null atom is used to represent absence of attributes; attributes with
// no values have the value set to an empty atom instead.
I think this comment, plus the code at 899 below, can be removed. […]
Done
if (value.IsNull()) {
value = g_empty_atom;
}
You could convert this to […]
Done
To view, visit change 4310894. To unsubscribe, or for help writing mail filters, visit settings.
Attention is currently required from: Bin Liao, Mason Freed.
1 comment:
Patchset:
Bin, thanks for the patch. One comment on gaining confidence a patch improves things. Internal analysis has shown the m1 bots produce the most reliable data. I encourage you to use it for measuring impact of changes. I just started a pinpoint run for this.
To view, visit change 4310894. To unsubscribe, or for help writing mail filters, visit settings.
Attention is currently required from: Bin Liao, Mason Freed.
3 comments:
File third_party/blink/renderer/core/html/parser/atomic_string_cache.h:
While parsing html attributes, it spents a nontrivial amount of time mapping
// from UChar/LChar to AtomicString, and it's mainly because the AtomicString
// constructor.
// This class offers an AtomicString cache during attribute parsing, and
// implements a simple & fast hash algorithm to distinguishable strings from
// others.
To be clear, all of this is still done. If this helps, it would be because attribute values are repeated, and the hash you chose is good for the common case.
tic constexpr auto kMaxStringLengthForCache = 36;
static constexpr auto kCapacity = 512
I'm curious how you arrived at these numbers?
o first_character = string[0];
auto last_character = string[length - 1];
It would be good to document why we think this is a good hash choice.
To view, visit change 4310894. To unsubscribe, or for help writing mail filters, visit settings.
Attention is currently required from: Bin Liao, Mason Freed.
📍 Job complete.
See results at: https://pinpoint-dot-chromeperf.appspot.com/job/14ebc88e060000
Attention is currently required from: Mason Freed, Scott Violet.
4 comments:
Patchset:
Thanks very much for Scott's review, the m1 bot's pinpoint result also shows a 0.6% progression, it almost aligned with the winbot.
File third_party/blink/renderer/core/html/parser/atomic_string_cache.h:
While parsing html attributes, it spents a nontrivial amount of time mapping
// from UChar/LChar to AtomicString, and it's mainly because the AtomicString
// constructor.
// This class offers an AtomicString cache during attribute parsing, and
// implements a simple & fast hash algorithm to distinguishable strings from
// others.
To be clear, all of this is still done. […]
Yes, you description is much more precise, I will modify this in next patchset.
tic constexpr auto kMaxStringLengthForCache = 36;
static constexpr auto kCapacity = 512
I'm curious how you arrived at these numbers?
Yeah, this file mainly comes from the WebCore, so I just use these numbers they used.
o first_character = string[0];
auto last_character = string[length - 1];
It would be good to document why we think this is a good hash choice.
In WebCore patch, they claims that in terms
of the cache hit rate in this AtomString cache, the default string hashing algorithm only barely outperforms
this simple hash function on Speedometer (i.e., a cache hit rate of 99.24% using the default hash algorithm vs.
99.15% using the "first/last character and length" hash).
https://github.com/WebKit/WebKit/commit/86c93355e0e01ca5f382b1b6b125eeb9c6d34ac5
To view, visit change 4310894. To unsubscribe, or for help writing mail filters, visit settings.
Attention is currently required from: Bin Liao, Mason Freed.
4 comments:
Patchset:
I'm ok with this, will lg once changes have been made.
File third_party/blink/renderer/core/dom/document.cc:
if (GetFrame()->IsMainFrame()) {
HTMLAtomicStringCache::Clear();
}
Please document why this is done. This call really just releases the strings, and doesn't really shrink the size of the cache.
File third_party/blink/renderer/core/html/parser/atomic_html_token.h:
Patch Set #6, Line 357: DCHECK(!value.IsNull());
Please document why this DCHECK makes sense.
File third_party/blink/renderer/core/html/parser/html_document_parser_fastpath.cc:
Patch Set #6, Line 896: DCHECK(!value.IsNull());
Similar comment about why this DCHECK makes sense.
To view, visit change 4310894. To unsubscribe, or for help writing mail filters, visit settings.
Attention is currently required from: Mason Freed, Scott Violet.
6 comments:
Patchset:
Thanks for Scott's quick response.
File third_party/blink/renderer/core/dom/document.cc:
if (GetFrame()->IsMainFrame()) {
HTMLAtomicStringCache::Clear();
}
Please document why this is done. […]
Done
File third_party/blink/renderer/core/html/parser/atomic_html_token.h:
Patch Set #6, Line 357: DCHECK(!value.IsNull());
Please document why this DCHECK makes sense.
Done
File third_party/blink/renderer/core/html/parser/atomic_string_cache.h:
While parsing html attributes, it spents a nontrivial amount of time mapping
// from UChar/LChar to AtomicString, and it's mainly because the AtomicString
// constructor.
// This class offers an AtomicString cache during attribute parsing, and
// implements a simple & fast hash algorithm to distinguishable strings from
// others.
Yes, you description is much more precise, I will modify this in next patchset.
Done
o first_character = string[0];
auto last_character = string[length - 1];
In WebCore patch, they claims that in terms […]
Done
File third_party/blink/renderer/core/html/parser/html_document_parser_fastpath.cc:
Patch Set #6, Line 896: DCHECK(!value.IsNull());
Similar comment about why this DCHECK makes sense.
Done
To view, visit change 4310894. To unsubscribe, or for help writing mail filters, visit settings.
Attention is currently required from: Bin Liao, Mason Freed.
Patch set 8:Code-Review +1
5 comments:
File third_party/blink/renderer/core/dom/document.cc:
if (GetFrame()->IsMainFrame()) {
HTMLAtomicStringCache::Clear();
}
Done
I tend to think the reason to do this is more of:
"The cache of string values is very likely specific to a particular document. Empty it now to release any strings that may not be used by the next document."
But a renderer may have multiple documents, in which case this is a bit wrong.
I could go either way on whether this is worth it, and would likely not bother. Perhaps the right signal to use is low memory. I'm curious what Mason thinks here.
File third_party/blink/renderer/core/dom/document.cc:
Patch Set #8, Line 2939: empties
empties->empty
File third_party/blink/renderer/core/html/parser/atomic_html_token.h:
ttribute with no value will be set to a empty atom in
// MakeAttributeValue.
I think you mean "MakeAttributeValue() should never return a null value.".
File third_party/blink/renderer/core/html/parser/atomic_string_cache.h:
While parsing html attributes, it spents a nontrivial amount of time mapping
// from UChar/LChar to AtomicString, and it's mainly because the AtomicString
// constructor.
// This class offers an AtomicString cache during attribute parsing, and
// implements a simple & fast hash algorithm to distinguishable strings from
// others.
Done
How about something like:
HTMLAtomicStringCache provides a fixed size cache of strings that is used during parsing, and specifically for attribute values. The cache lookup is cheap (much cheaper than AtomicString). This benefits parsing when the same attribute values are repeated.
File third_party/blink/renderer/core/html/parser/html_document_parser_fastpath.cc:
Attribute with no value will be set to a empty atom in
// MakeAttributeValue.
Similar suggestion to other place you copied this from.
To view, visit change 4310894. To unsubscribe, or for help writing mail filters, visit settings.
Attention is currently required from: Bin Liao.
1 comment:
Patchset:
Sorry for the delay, I've been swamped with other things. I'll definitely get a chance to review this tomorrow.
To view, visit change 4310894. To unsubscribe, or for help writing mail filters, visit settings.
Attention is currently required from: Mason Freed.
7 comments:
Patchset:
Sorry for the delay, I've been swamped with other things. […]
NP, also thanks very much for your response.
Patchset:
Thanks for Scott and Mason, for the Clear() function in Document::Shutdown, I think we can delete it. How about your ideas?
File third_party/blink/renderer/core/dom/document.cc:
if (GetFrame()->IsMainFrame()) {
HTMLAtomicStringCache::Clear();
}
I tend to think the reason to do this is more of: […]
Actually, calling Clear function here is added by myself, the WebCore just call the clear function upon receiving a low memory warning, and upon top-level navigation. Thanks for Scott's careful review, I also think here is not needed.
Even document A's string values are different from document B's values, the cache can also be updated.
File third_party/blink/renderer/core/dom/document.cc:
Patch Set #8, Line 2939: empties
empties->empty
Done
File third_party/blink/renderer/core/html/parser/atomic_html_token.h:
ttribute with no value will be set to a empty atom in
// MakeAttributeValue.
I think you mean "MakeAttributeValue() should never return a null value.".
Yes, this DCHECK is added by the suggestion of Mason, now I thinks is not needed here. Since I have document inner MakeAttributeValue.
File third_party/blink/renderer/core/html/parser/atomic_string_cache.h:
While parsing html attributes, it spents a nontrivial amount of time mapping
// from UChar/LChar to AtomicString, and it's mainly because the AtomicString
// constructor.
// This class offers an AtomicString cache during attribute parsing, and
// implements a simple & fast hash algorithm to distinguishable strings from
// others.
How about something like: […]
Thanks for this, this seems much more clear.
File third_party/blink/renderer/core/html/parser/html_document_parser_fastpath.cc:
Attribute with no value will be set to a empty atom in
// MakeAttributeValue.
Similar suggestion to other place you copied this from.
Done
To view, visit change 4310894. To unsubscribe, or for help writing mail filters, visit settings.
Attention is currently required from: Bin Liao, Scott Violet.
11 comments:
Patchset:
This looks very close. Just a few more comments and questions. Thanks for all the changes, and for waiting for my very slow reviews. 😊
File third_party/blink/renderer/core/dom/document.cc:
if (GetFrame()->IsMainFrame()) {
HTMLAtomicStringCache::Clear();
}
Actually, calling Clear function here is added by myself, the WebCore just call the clear function u […]
I think the logic for performance is likely right - better to not clear the cache here.
I'm a little worried about some kind of information leakage side-channel attack, where you can see that some strings are faster in the new page, due to their being cached from the last page visited. But I actually think that isn't a concern since I'm sure (?) we throw away the document when we're doing any kind of origin change, right Scott?
If the above isn't a concern, I'd say remove this `Clear()` call completely.
File third_party/blink/renderer/core/html/parser/atomic_html_token.h:
Patch Set #6, Line 357: DCHECK(!value.IsNull());
Done
Shouldn't this DCHECK still be here, just with a comment? I think the reason is the same as this comment from below:
```
// Attribute with no value will be set to a empty atom in
// MakeAttributeValue.
```
Perhaps since that comment is there, you could just use:
```
DCHECK(!value.IsNull()) << "Attribute value should never be null";
```
here and below?
File third_party/blink/renderer/core/html/parser/atomic_string_cache.h:
Patch Set #5, Line 9: HTMLAtomicStringCache
Done
Perfect, thanks.
kMaxStringLengthForCache = 36;
static constexpr auto kCapacity = 512;
This value I used the same as WebCore, maybe this is a tuned by WebCore to get a good performance
Ok. In that case, at the very least, can you please add a comment above them that says something like that ("values taken from WebCore") and link to the corresponding code from WebCore? At least then someone coming later can go dig to see whether these are worth changing.
Patch Set #5, Line 31: kCapacity
Yeah, this compacts the memory, do we have any memory benchmark? Maybe a memory benchmark is needed […]
We have some memory benchmarks, but they're very noisy. I suspect you wouldn't see this with those benchmarks. Let's just land this and see if you get a memory performance regression bug detected.
Patch Set #5, Line 50: AtomicString result(string.data(), static_cast<unsigned>(length));
Actually this keeps latest kCapacity(512) attributes here
Sorry, what I mean is `<div v1="abcde" v2="azyxe">` will have a cache collision on those two values, because they have the same first/last letter and length. The `slot` will be the same, and the second one will evict the first one. If that happens often on a particular page, then this caching code will likely be slower than the previous, uncached code.
Again, likely not worth doing anything about, so ok.
ALWAYS_INLINE static AtomicString MakeAtomString(
base::span<const CharacterType> string) {
if (string.empty()) {
return g_empty_atom;
}
auto length = string.size();
if (length > kMaxStringLengthForCache) {
return AtomicString(string.data(), static_cast<unsigned>(length));
}
auto first_character = string[0];
auto last_character = string[length - 1];
auto& slot = AtomicStringCacheSlot(first_character, last_character, length);
if (!Equal(slot.Impl(), string.data(), static_cast<unsigned>(length))) {
AtomicString result(string.data(), static_cast<unsigned>(length));
slot = result;
return result;
}
return slot;
}
Yes, this copy-paste code is really bad, I have tried, but it's really hard to user template to simp […]
Ok. Thanks for trying, I figured that's what you'd say.
unsigned hash =
(first_character << 6) ^ ((last_character << 14) ^ first_character);
This file is totally porting from WebCore, it claims that the default string hashing algorithm only […]
That's fine, but like above, could you please add a comment to that effect?
File third_party/blink/renderer/core/html/parser/html_document_parser_fastpath.cc:
if (value.IsNull()) {
value = g_empty_atom;
}
Done
I think maybe you forgot the `DCHECK`, right?
File third_party/blink/renderer/core/html/parser/html_document_parser_fastpath.cc:
Patch Set #6, Line 896: DCHECK(!value.IsNull());
Done
Ditto above.
To view, visit change 4310894. To unsubscribe, or for help writing mail filters, visit settings.