Chromium Code Reviews
|
|
Chromium Code Reviews
Issue
1708193003:
Reduce the memory footprint of expression classifiers (Closed)
DescriptionReduce the memory footprint of expression classifiers
This patch attempts to reduce the (stack) memory footprint of
expression classifiers. Instead of keeping space in each
classifier for all possible error messages that will
(potentially) be reported, if an expression turns out to be
a pattern or a non-pattern, such error messages are placed in
a list shared by the FunctionState and each classifier keeps a
couple of indices in this list. This requires that classifiers
are used strictly in a stack-based fashion, which is also in line
with my previous patch for revisiting non-pattern rewriting.
R=adamk@chromium.org
BUG=chromium:528697
Committed: https://crrev.com/dfb8d3331e7cb2c3e67ef820cbcb6cfbae7159e5
Cr-Commit-Position: refs/heads/master@{#36897}
Patch Set 1 #
Total comments: 10
Patch Set 2 : Rebase #Patch Set 3 : Fix enumeration types #Patch Set 4 : Hunting a weird bug with an enum #Patch Set 5 : Correctly fix enumeration types #Patch Set 6 : Simplify expression classifier accumulate #Patch Set 7 : Improve expression classifier accumulate #
Total comments: 23
Patch Set 8 : Fixes to address review comments #
Total comments: 5
Patch Set 9 : More fixes and space savings #
Total comments: 2
Patch Set 10 : Introduce implementation-limit error (too many non-pattern rewrites) #
Messages
Total messages: 78 (26 generated)
On 2016/02/18 16:41:45, nickie wrote: The baseline for this patch is Issue 1702063002: Non-pattern rewriting revisited
caitpotter88@gmail.com changed reviewers: + caitpotter88@gmail.com
https://codereview.chromium.org/1708193003/diff/1/src/parsing/expression-clas... File src/parsing/expression-classifier.h (right): https://codereview.chromium.org/1708193003/diff/1/src/parsing/expression-clas... src/parsing/expression-classifier.h:23: T(StrongModeFormalParametersProduction, 6) \ I feel like we could probably just take this opportunity to get rid of the strongmode errors, since they just take up extra space that isn't going to be used
https://codereview.chromium.org/1708193003/diff/1/src/parsing/expression-clas... File src/parsing/expression-classifier.h (right): https://codereview.chromium.org/1708193003/diff/1/src/parsing/expression-clas... src/parsing/expression-classifier.h:161: V8_INLINE const Error& binding_pattern_error() const { maybe if you added like a `accessor_name` parameter to the macro, you could shrink the code a little bit by defining them via the ERROR_CODES() macro? https://codereview.chromium.org/1708193003/diff/1/src/parsing/expression-clas... src/parsing/expression-classifier.h:434: reported_errors_->Add(e, zone_); It might be worth having the very commonly used ones allocated on the stack rather than heap, but test if that makes a difference, I guess. The cover-grammar variations in particular, can turn up quite frequently despite not being really used.
last DBC idea :p carry on https://codereview.chromium.org/1708193003/diff/1/src/parsing/parser-base.h File src/parsing/parser-base.h (right): https://codereview.chromium.org/1708193003/diff/1/src/parsing/parser-base.h#n... src/parsing/parser-base.h:1991: ExpressionClassifier::BindingPatternError( A thought I had on this duplication: A BindingPattern is never valid if an AssignmentPattern is invalid, but the inverse is not always true --- maybe we could use one for "general pattern errors", and a secondary version for binding patterns specifically --- this would avoid allocating an extra error for all these (numerous) duplicated cases. Validating a binding pattern would then perform the act of validating both GeneralPattern and BindingPattern errors, since binding patterns are more strict in a few places.
https://codereview.chromium.org/1708193003/diff/1/src/parsing/expression-clas... File src/parsing/expression-classifier.h (right): https://codereview.chromium.org/1708193003/diff/1/src/parsing/expression-clas... src/parsing/expression-classifier.h:23: T(StrongModeFormalParametersProduction, 6) \ On 2016/02/18 16:50:22, caitp wrote: > I feel like we could probably just take this opportunity to get rid of the > strongmode errors, since they just take up extra space that isn't going to be > used I assumed strong mode removal would be an independent (and pretty big) CL but I may be wrong about this. https://codereview.chromium.org/1708193003/diff/1/src/parsing/expression-clas... src/parsing/expression-classifier.h:161: V8_INLINE const Error& binding_pattern_error() const { On 2016/02/18 16:57:47, caitp wrote: > maybe if you added like a `accessor_name` parameter to the macro, you could > shrink the code a little bit by defining them via the ERROR_CODES() macro? While the error codes and the bit flags are named consistently (e.g. kBindingPatternProduction), the method names are not the same. In a few cases, e.g. DistinctFormalParametersProduction vs. duplicate_formal_parameter_error, this is even confusing. I'd be happy to clean this up further. Andreas? https://codereview.chromium.org/1708193003/diff/1/src/parsing/expression-clas... src/parsing/expression-classifier.h:434: reported_errors_->Add(e, zone_); On 2016/02/18 16:57:47, caitp wrote: > It might be worth having the very commonly used ones allocated on the stack > rather than heap, but test if that makes a difference, I guess. > > The cover-grammar variations in particular, can turn up quite frequently despite > not being really used. If you could suggest a subset, I could try to benchmark having those on the stack and see how it goes. https://codereview.chromium.org/1708193003/diff/1/src/parsing/parser-base.h File src/parsing/parser-base.h (right): https://codereview.chromium.org/1708193003/diff/1/src/parsing/parser-base.h#n... src/parsing/parser-base.h:1991: ExpressionClassifier::BindingPatternError( On 2016/02/18 17:04:09, caitp wrote: > A thought I had on this duplication: > > A BindingPattern is never valid if an AssignmentPattern is invalid, but the > inverse is not always true --- maybe we could use one for "general pattern > errors", and a secondary version for binding patterns specifically --- this > would avoid allocating an extra error for all these (numerous) duplicated cases. > > Validating a binding pattern would then perform the act of validating both > GeneralPattern and BindingPattern errors, since binding patterns are more strict > in a few places. I'm sorry, I'm not confident enough to talk about the logic of this. This is semantically equivalent to how it was before. If it can be further simplified, then by all means I agree.
https://codereview.chromium.org/1708193003/diff/1/src/parsing/expression-clas... File src/parsing/expression-classifier.h (right): https://codereview.chromium.org/1708193003/diff/1/src/parsing/expression-clas... src/parsing/expression-classifier.h:434: reported_errors_->Add(e, zone_); On 2016/02/19 08:56:31, nickie wrote: > On 2016/02/18 16:57:47, caitp wrote: > > It might be worth having the very commonly used ones allocated on the stack > > rather than heap, but test if that makes a difference, I guess. > > > > The cover-grammar variations in particular, can turn up quite frequently > despite > > not being really used. > > If you could suggest a subset, I could try to benchmark having those on the > stack and see how it goes. the main one is Object/Array Literals vs Assignment/Binding patterns, since it happens most times you parse these literals. Arrow Formals/Duplicate Parameter errors are other candidates when parsing a parenthesized expression. having two errors stack allocated in those scenarios would be a time saver
https://codereview.chromium.org/1708193003/diff/1/src/parsing/expression-clas... File src/parsing/expression-classifier.h (right): https://codereview.chromium.org/1708193003/diff/1/src/parsing/expression-clas... src/parsing/expression-classifier.h:434: reported_errors_->Add(e, zone_); On 2016/02/19 09:07:28, caitp wrote: > On 2016/02/19 08:56:31, nickie wrote: > > On 2016/02/18 16:57:47, caitp wrote: > > > It might be worth having the very commonly used ones allocated on the stack > > > rather than heap, but test if that makes a difference, I guess. > > > > > > The cover-grammar variations in particular, can turn up quite frequently > > despite > > > not being really used. > > > > If you could suggest a subset, I could try to benchmark having those on the > > stack and see how it goes. > > the main one is Object/Array Literals vs Assignment/Binding patterns, since it > happens most times you parse these literals. Arrow Formals/Duplicate Parameter > errors are other candidates when parsing a parenthesized expression. having two > errors stack allocated in those scenarios would be a time saver One way to go then is to always store BindingPatternProduction and AssignmentPatternProduction in the classifiers (right? was that your suggestion?). This should be very easy to implement and test. A different way to go would be to have a small array that could fit a few errors in the classifier and then put the rest in the global list. If the size of this list is 4, the global list will probably be redundant (I ran some statistics for classifiers, before starting this, and for all the test suites that I tried, it turned out that classifiers store on the average 1.8 errors and a maximum of 4). This will complicate the Accumulate method and I'm not sure if it's worth the effort.
The CQ bit was checked by nikolaos@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/patch-status/1708193003/20001 View timeline at https://chromium-cq-status.appspot.com/patch-timeline/1708193003/20001
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: Try jobs failed on following builders: v8_linux_gcc_compile_rel on tryserver.v8 (JOB_FAILED, http://build.chromium.org/p/tryserver.v8/builders/v8_linux_gcc_compile_rel/bu...)
The CQ bit was checked by nikolaos@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/patch-status/1708193003/40001 View timeline at https://chromium-cq-status.appspot.com/patch-timeline/1708193003/40001
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: Try jobs failed on following builders: v8_win64_rel_ng on tryserver.v8 (JOB_FAILED, http://build.chromium.org/p/tryserver.v8/builders/v8_win64_rel_ng/builds/7359) v8_win64_rel_ng_triggered on tryserver.v8 (JOB_FAILED, http://build.chromium.org/p/tryserver.v8/builders/v8_win64_rel_ng_triggered/b...) v8_win_rel_ng on tryserver.v8 (JOB_FAILED, http://build.chromium.org/p/tryserver.v8/builders/v8_win_rel_ng/builds/7251) v8_win_rel_ng_triggered on tryserver.v8 (JOB_FAILED, http://build.chromium.org/p/tryserver.v8/builders/v8_win_rel_ng_triggered/bui...)
The CQ bit was checked by nikolaos@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/patch-status/1708193003/60001 View timeline at https://chromium-cq-status.appspot.com/patch-timeline/1708193003/60001
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: This issue passed the CQ dry run.
The CQ bit was checked by nikolaos@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/patch-status/1708193003/80001 View timeline at https://chromium-cq-status.appspot.com/patch-timeline/1708193003/80001
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: This issue passed the CQ dry run.
Description was changed from ========== Expression classifiers revisited This patch attempts to reduce the (stack) memory footprint of expression classifiers. Instead of keeping space in each classifier for all possible error messages that will (potentially) be reported, if an expression turns out to be a pattern or a non-pattern, such error messages are placed in a list shared by the FunctionState and each classifier keeps a couple of indices in this list. This requires that classifiers are used strictly in a stack-based fashion, which is also in line with my previous patch for revisiting non-pattern rewriting. R=rossberg@chromium.org BUG=chromium:528697 ========== to ========== Expression classifiers revisited This patch attempts to reduce the (stack) memory footprint of expression classifiers. Instead of keeping space in each classifier for all possible error messages that will (potentially) be reported, if an expression turns out to be a pattern or a non-pattern, such error messages are placed in a list shared by the FunctionState and each classifier keeps a couple of indices in this list. This requires that classifiers are used strictly in a stack-based fashion, which is also in line with my previous patch for revisiting non-pattern rewriting. R=rossberg@chromium.org BUG=chromium:528697 ==========
littledan@chromium.org changed reviewers: + littledan@chromium.org
Does this still make CodeLoad 3% slower? Do we have a good understanding of how often the out-of-stack case hits in order to be able to evaluate this tradeoff? Has there been any attention at emscripten to see if we could get it to not emit code like that? I wonder if, based on what you learned on this patch, you have ideas for how to make CodeLoad faster, *rather than* focusing on saving stack space, if the out of stack case does not hit very often.
On 2016/02/19 09:25:50, nickie wrote: > https://codereview.chromium.org/1708193003/diff/1/src/parsing/expression-clas... > File src/parsing/expression-classifier.h (right): > > https://codereview.chromium.org/1708193003/diff/1/src/parsing/expression-clas... > src/parsing/expression-classifier.h:434: reported_errors_->Add(e, zone_); > On 2016/02/19 09:07:28, caitp wrote: > > On 2016/02/19 08:56:31, nickie wrote: > > > On 2016/02/18 16:57:47, caitp wrote: > > > > It might be worth having the very commonly used ones allocated on the > stack > > > > rather than heap, but test if that makes a difference, I guess. > > > > > > > > The cover-grammar variations in particular, can turn up quite frequently > > > despite > > > > not being really used. > > > > > > If you could suggest a subset, I could try to benchmark having those on the > > > stack and see how it goes. > > > > the main one is Object/Array Literals vs Assignment/Binding patterns, since it > > happens most times you parse these literals. Arrow Formals/Duplicate Parameter > > errors are other candidates when parsing a parenthesized expression. having > two > > errors stack allocated in those scenarios would be a time saver > > One way to go then is to always store BindingPatternProduction and > AssignmentPatternProduction in the classifiers (right? was that your > suggestion?). This should be very easy to implement and test. > > A different way to go would be to have a small array that could fit a few errors > in the classifier and then put the rest in the global list. If the size of this > list is 4, the global list will probably be redundant (I ran some statistics for > classifiers, before starting this, and for all the test suites that I tried, it > turned out that classifiers store on the average 1.8 errors and a maximum of 4). > This will complicate the Accumulate method and I'm not sure if it's worth the > effort. We can make propagation very easy by appending the entire array, and adding only the relevant production bits (which would get rid of a good number of test/branches). Its ok if the dynamic array contains duplicates or types we dont care about.
On 2016/05/18 01:11:04, Dan Ehrenberg wrote: > Does this still make CodeLoad 3% slower? Do we have a good understanding of how > often the out-of-stack case hits in order to be able to evaluate this tradeoff? > Has there been any attention at emscripten to see if we could get it to not emit > code like that? > > I wonder if, based on what you learned on this patch, you have ideas for how to > make CodeLoad faster, *rather than* focusing on saving stack space, if the out > of stack case does not hit very often. I'll test it with CodeLoad again today and let you know. I will also see if something can be done in the direction that Caitlin points out. But this patch was about making expression classifiers lighter, not about making CodeLoad (or anything) faster. Let's discuss it in the meeting today and see what we really want to do here.
On 2016/05/18 07:51:47, nickie wrote:
> On 2016/05/18 01:11:04, Dan Ehrenberg wrote:
> > Does this still make CodeLoad 3% slower?
>
> I'll test it with CodeLoad again today and let you know.
Yes, still around 3% slower (on my machine, Linux/x64).
CodeLoad-octane2.1(Score)
vanilla.txt:
samples: 100
average: 12695.77 base
median: 12768.50 base
stddev: 419.56 base
minimum: 10084 base
maximum: 13221 base
CI 95%: 12612.52 to 12779.02
modified.txt:
samples: 100
average: 13030.05 +2.63
median: 13203.00 +3.40
stddev: 603.47 +43.83
minimum: 9934 -1.49
maximum: 13626 +3.06
CI 95%: 12910.31 to 13149.79
On 2016/05/18 01:16:46, caitp wrote: > We can make propagation very easy by appending the entire array, and adding only > the relevant production bits (which would get rid of a good number of > test/branches). Its ok if the dynamic array contains duplicates or types we dont > care about. Yes, indeed, but we cannot avoid traversing the errors corresponding to the inner classifier, to remove (flag as kUnusedError) those that should not be accumulated. The complication with the kArrowFormalParametersProduction/kBindingPatternProduction pair would also remain. Plus, the array would only grow in size, therefore the benefits in saving memory would be reduced. Overall, I doubt that this approach will improve things.
On 2016/05/18 13:42:08, nickie wrote: > On 2016/05/18 01:16:46, caitp wrote: > > We can make propagation very easy by appending the entire array, and adding > only > > the relevant production bits (which would get rid of a good number of > > test/branches). Its ok if the dynamic array contains duplicates or types we > dont > > care about. > > Yes, indeed, but we cannot avoid traversing the errors corresponding to the > inner classifier, to remove (flag as kUnusedError) those that should not be > accumulated. The complication with the > kArrowFormalParametersProduction/kBindingPatternProduction pair would also > remain. Plus, the array would only grow in size, therefore the benefits in > saving memory would be reduced. Overall, I doubt that this approach will > improve things. There's no need to reflag them as `kUnused` --- because the bitset containing the error productions is all the info you need to determine what is actually in the set. Am I wrong about that? If the bitset does not include a certain production, then it doesn't matter if it shows up in the array, it can be treated as not present
On 2016/05/18 13:44:09, caitp wrote: > There's no need to reflag them as `kUnused` --- because the bitset containing > the error productions is all the info you need to determine what is actually in > the set. Am I wrong about that? If the bitset does not include a certain > production, then it doesn't matter if it shows up in the array, it can be > treated as not present OK, I think you're right. So, the remaining objection is that we'll lose part of the memory gain. I will try it with CodeLoad and see if it improves time performance.
On 2016/05/18 13:51:41, nickie wrote: > I will try it with CodeLoad and see if it improves time performance. The patch implementing this is here: https://codereview.chromium.org/1994643002 It's much simpler than the current CL (and simpler than what's now upstream), but it turns out that it's even slower than this CL: CodeLoad-octane2.1(Score) vanilla.txt: samples: 100 average: 12695.77 base median: 12768.50 base stddev: 419.56 base minimum: 10084 base maximum: 13221 base CI 95%: 12612.52 to 12779.02 modified.txt: samples: 100 average: 13030.05 +2.63 median: 13203.00 +3.40 stddev: 603.47 +43.83 minimum: 9934 -1.49 maximum: 13626 +3.06 CI 95%: 12910.31 to 13149.79 appending.txt: samples: 100 average: 13217.55 +4.11 median: 13316.00 +4.29 stddev: 443.37 +5.68 minimum: 10600 +5.12 maximum: 13763 +4.10 CI 95%: 13129.57 to 13305.53
On 2016/05/18 14:50:53, nickie wrote: > On 2016/05/18 13:51:41, nickie wrote: > > I will try it with CodeLoad and see if it improves time performance. > > The patch implementing this is here: https://codereview.chromium.org/1994643002 > It's much simpler than the current CL (and simpler than what's now upstream), > but it turns out that it's even slower than this CL: > > CodeLoad-octane2.1(Score) > vanilla.txt: > samples: 100 > average: 12695.77 base > median: 12768.50 base > stddev: 419.56 base > minimum: 10084 base > maximum: 13221 base > CI 95%: 12612.52 to 12779.02 > modified.txt: > samples: 100 > average: 13030.05 +2.63 > median: 13203.00 +3.40 > stddev: 603.47 +43.83 > minimum: 9934 -1.49 > maximum: 13626 +3.06 > CI 95%: 12910.31 to 13149.79 > appending.txt: > samples: 100 > average: 13217.55 +4.11 > median: 13316.00 +4.29 > stddev: 443.37 +5.68 > minimum: 10600 +5.12 > maximum: 13763 +4.10 > CI 95%: 13129.57 to 13305.53 I think there are some bugs in that simpler implementation. I can have a go at it and see if I can do any better. Question: how are you running your statistics on the Octane runs? manually, or do we have a script to simplify things?
On 2016/05/18 15:28:39, caitp wrote: > I think there are some bugs in that simpler implementation. I can have a go at > it and see if I can do any better. I'm taking a look at it too, there's definitely a bug. I'm having trouble with gyp/gn, which refuses to run the tests on my machine, at the moment. > Question: how are you running your statistics on the Octane runs? manually, or > do we have a script to simplify things? I'm using this: https://codereview.chromium.org/1672433003/
On 2016/05/18 15:45:33, nickie wrote:
> I'm taking a look at it too, there's definitely a bug. I'm having trouble
with
> gyp/gn, which refuses to run the tests on my machine, at the moment.
There was a stupid bug, I fixed it. The picture did not improve much:
CodeLoad-octane2.1(Score)
vanilla.txt:
samples: 100
average: 12695.77 base
median: 12768.50 base
stddev: 419.56 base
minimum: 10084 base
maximum: 13221 base
CI 95%: 12612.52 to 12779.02
modified.txt:
samples: 100
average: 13030.05 +2.63
median: 13203.00 +3.40
stddev: 603.47 +43.83
minimum: 9934 -1.49
maximum: 13626 +3.06
CI 95%: 12910.31 to 13149.79
appending.txt:
samples: 100
average: 13152.51 +3.60
median: 13221.50 +3.55
stddev: 326.61 -22.15
minimum: 12112 +20.11
maximum: 13872 +4.92
CI 95%: 13087.70 to 13217.32
Unless Caitlin meant something different and I misunderstood, I suggest that we
drop this idea. I don't think that ExpressionClassifier::Accumulate can be made
any simpler or faster than this. The zone list essentially (except in trivial
cases) replaces the C stack for expression classifiers.
On 2016/05/18 17:53:25, nickie wrote: > There was a stupid bug, I fixed it. Still one bot is failing there. I don't know why and I'm not sure if it's worth investigating more.
The CQ bit was checked by nikolaos@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/patch-status/1708193003/100001 View timeline at https://chromium-cq-status.appspot.com/patch-timeline/1708193003/100001
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: This issue passed the CQ dry run.
The CQ bit was checked by nikolaos@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/patch-status/1708193003/120001
nikolaos@chromium.org changed reviewers: + adamk@chromium.org
I've run some benchmarks on this and two alternative CLs (https://codereview.chromium.org/1994643002/ and https://codereview.chromium.org/2002113002/). There results are here: https://docs.google.com/a/google.com/document/d/1_wRYOsAt_C_3sviIa7R_xA7xQtON... I tend to favour this one. 2002113002 was promising but the numbers don't show it's actually better.
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: This issue passed the CQ dry run.
https://codereview.chromium.org/1708193003/diff/120001/src/parsing/expression... File src/parsing/expression-classifier.h (right): https://codereview.chromium.org/1708193003/diff/120001/src/parsing/expression... src/parsing/expression-classifier.h:382: // As an exception to the above, the result continues to be a valid arrow This comment is now out-of-order (it refers to "above"). https://codereview.chromium.org/1708193003/diff/120001/src/parsing/expression... src/parsing/expression-classifier.h:460: // been reported. But we're not... So this is to make sure we have This sounds odd, where does this show up? https://codereview.chromium.org/1708193003/diff/120001/src/parsing/expression... src/parsing/expression-classifier.h:466: V8_INLINE void Add(const Error& e) { Can you give each of Add, Move, and Replace a comment? Or maybe just Move and Replace. Add is fairly straightforward (and easy to read, but both Move and Replace look tricky enough that I'd like a comment explaining what the method is supposed to do. Those comments would also make reading Accumulate easier (it's much trickier than it used to be). https://codereview.chromium.org/1708193003/diff/120001/src/parsing/parser-base.h File src/parsing/parser-base.h (right): https://codereview.chromium.org/1708193003/diff/120001/src/parsing/parser-bas... src/parsing/parser-base.h:473: ZoneList<DestructuringAssignment> destructuring_assignments_to_rewrite_; Yikes, was this a memory leak before? Maybe pull this into a separate patch? https://codereview.chromium.org/1708193003/diff/120001/src/parsing/parser-bas... src/parsing/parser-base.h:1567: if (pattern_error) ArrowFormalParametersUnexpectedToken(classifier); Why was this reordering necessary? I think I'm missing exactly what you mean by using the classifier in a "stack-based fashion". https://codereview.chromium.org/1708193003/diff/120001/src/parsing/parser-bas... src/parsing/parser-base.h:1673: ExpressionClassifier binding_classifier(this); Can we wrap this and the next two lines in a block, now that the classifier used inside the loop is a different one? That'd avoid shadowing. https://codereview.chromium.org/1708193003/diff/120001/src/parsing/parser-bas... src/parsing/parser-base.h:1674: ExpressionT result = If you can do the above, this'll have to be declared outside the block obviously. https://codereview.chromium.org/1708193003/diff/120001/src/parsing/parser-bas... src/parsing/parser-base.h:2237: scanner()->peek_location(), MessageTemplate::kUnexpectedToken, Can you just store the location here, and move the call to RecordPatternError below? That'd save a good amount of boilerplate. https://codereview.chromium.org/1708193003/diff/120001/src/parsing/preparser.cc File src/parsing/preparser.cc (left): https://codereview.chromium.org/1708193003/diff/120001/src/parsing/preparser.... src/parsing/preparser.cc:632: Looks like you've got a spurious whitespace change here, if you revert it this file needn't be touched in this change.
Just popping in for some quick perf-related comments: as it turns out, at this very moment I am looking into parsing performance, and I have been running “parser-shell” under valgrind/callgrind to get a grasp of potential places where to optimize things. Yesterday I cooked up a proof-of-concept patch which reduces the amount of code executed (on x64) by ~32 million instructions —that is 0.6% of the total instruction count— when parsing ~6 MiB of JavaScript code from an actual application. For the curious, see: https://codereview.chromium.org/2045733004 Today caitp mentioned this CL, so of course I went ahead and ran the same test with this patch applied locally. With this patch, the instruction cound went up by ~71 million instructions — that's an 1.33% increase over the total instruction count. In both cases above the percentages may look small, but because there are changes in the hot code path of the parser both of them are to be noticeable. Of course I understand that is important to shave on the amount of stack space used by the ExpressionClassifier, so please do not take this as a request to prevent fixing the stack space usage. Maybe there is some other way in which stack space can be achieved without (so much of) the performance penalty. Thoughts? (If somebody wants a dump of the callgrind output, or more info about the input JavaScript files I am using for testing, drop me a line and most likely everything can be shared privately :D)
https://codereview.chromium.org/1708193003/diff/120001/src/parsing/expression... File src/parsing/expression-classifier.h (right): https://codereview.chromium.org/1708193003/diff/120001/src/parsing/expression... src/parsing/expression-classifier.h:356: invalid_productions_ &= ~CoverInitializedNameProduction; This was a bug, and fixed. Line 356 was moved after line 358. Otherwise, line 357 would not find the error and its 'kind' would not be set to kUnusedError. https://codereview.chromium.org/1708193003/diff/120001/src/parsing/expression... src/parsing/expression-classifier.h:363: invalid_productions_ &= ~AssignmentPatternProduction; Same thing. https://codereview.chromium.org/1708193003/diff/120001/src/parsing/expression... src/parsing/expression-classifier.h:382: // As an exception to the above, the result continues to be a valid arrow On 2016/06/06 20:51:02, adamk wrote: > This comment is now out-of-order (it refers to "above"). I removed the beginning of the sentence. https://codereview.chromium.org/1708193003/diff/120001/src/parsing/expression... src/parsing/expression-classifier.h:457: } I'm introducing an UNREACHABLE() here, partly to address the next comment. This should be OK; the errors in a classifier's reported list should always be consistent with the current value of invalid_productions_. https://codereview.chromium.org/1708193003/diff/120001/src/parsing/expression... src/parsing/expression-classifier.h:460: // been reported. But we're not... So this is to make sure we have On 2016/06/06 20:51:02, adamk wrote: > This sounds odd, where does this show up? If you replace these lines with UNREACHABLE(), you get a crash when building the snapshot. Autopsy shows that in line: https://cs.chromium.org/chromium/src/v8/src/parsing/parser.cc?rcl=0&l=4120 we're taking the location of a duplicate_formal_parameter_error when none has been recorded. They may be other cases like this. https://codereview.chromium.org/1708193003/diff/120001/src/parsing/expression... src/parsing/expression-classifier.h:466: V8_INLINE void Add(const Error& e) { On 2016/06/06 20:51:02, adamk wrote: > Can you give each of Add, Move, and Replace a comment? Or maybe just Move and > Replace. Add is fairly straightforward (and easy to read, but both Move and > Replace look tricky enough that I'd like a comment explaining what the method is > supposed to do. Those comments would also make reading Accumulate easier (it's > much trickier than it used to be). Done. I simplified this by merging Move and Replace. https://codereview.chromium.org/1708193003/diff/120001/src/parsing/parser-base.h File src/parsing/parser-base.h (right): https://codereview.chromium.org/1708193003/diff/120001/src/parsing/parser-bas... src/parsing/parser-base.h:473: ZoneList<DestructuringAssignment> destructuring_assignments_to_rewrite_; On 2016/06/06 20:51:02, adamk wrote: > Yikes, was this a memory leak before? Maybe pull this into a separate patch? As far as I understand, it was not a memory leak. It was just using the heap, instead of the zone, for storing the list of DestructuringAssignments. The list destructor clears the space. https://codereview.chromium.org/1708193003/diff/120001/src/parsing/parser-bas... src/parsing/parser-base.h:1567: if (pattern_error) ArrowFormalParametersUnexpectedToken(classifier); On 2016/06/06 20:51:02, adamk wrote: > Why was this reordering necessary? I think I'm missing exactly what you mean by > using the classifier in a "stack-based fashion". This one is not related to the "stack-based fashion", it's just an optimization. If you put the AFP before the BP in the list, when accumulating the AFP will not be copied and will force you to shift the BP one place to the left. This will save the trouble. It actually occurs several hundred thousand times. :-) https://codereview.chromium.org/1708193003/diff/120001/src/parsing/parser-bas... src/parsing/parser-base.h:1673: ExpressionClassifier binding_classifier(this); On 2016/06/06 20:51:02, adamk wrote: > Can we wrap this and the next two lines in a block, now that the classifier used > inside the loop is a different one? That'd avoid shadowing. What you're suggesting is a common pattern in parser.cc but not in parser-base.h It can be done but not so easily because, as you say in the next comment, result will have to be declared before the block, e.g. ExpressionT result; { ExpressionClassifier binding_classifier(this); result = this->ParseAssignmentExpression(...); classifier->Accumulate(&binding_classifier, ...); } Now, for the parser where ExpressionT is a pointer, this is equivalent. For the preparser, where ExpressionT is PreParserExpression, there is no default constructor, so we would have to replace the first line with something like: ExpressionT elem = this->EmptyExpression(); Again, in the case of the parser this would be almost equivalent, as EmptyExpression returns NULL and the compiler will probably figure out that initialization is not necessary. For the preparser, however, I think that this would first initialize a PreParserExpression object and then use the copy constructor to copy a new value there. In any case, this pattern with the extraneous initialization occurs in several places in parser-base.h and it would not harm much to add one more here, if you insist. https://codereview.chromium.org/1708193003/diff/120001/src/parsing/parser-bas... src/parsing/parser-base.h:1700: ExpressionClassifier binding_classifier(this); Same thing; a block could be introduced here. https://codereview.chromium.org/1708193003/diff/120001/src/parsing/parser-bas... src/parsing/parser-base.h:2237: scanner()->peek_location(), MessageTemplate::kUnexpectedToken, On 2016/06/06 20:51:02, adamk wrote: > Can you just store the location here, and move the call to RecordPatternError > below? That'd save a good amount of boilerplate. Done. https://codereview.chromium.org/1708193003/diff/120001/src/parsing/preparser.cc File src/parsing/preparser.cc (left): https://codereview.chromium.org/1708193003/diff/120001/src/parsing/preparser.... src/parsing/preparser.cc:632: On 2016/06/06 20:51:02, adamk wrote: > Looks like you've got a spurious whitespace change here, if you revert it this > file needn't be touched in this change. Reverting it.
The CQ bit was checked by nikolaos@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/patch-status/1708193003/140001
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: This issue passed the CQ dry run.
https://codereview.chromium.org/1708193003/diff/120001/src/parsing/parser-base.h File src/parsing/parser-base.h (right): https://codereview.chromium.org/1708193003/diff/120001/src/parsing/parser-bas... src/parsing/parser-base.h:473: ZoneList<DestructuringAssignment> destructuring_assignments_to_rewrite_; On 2016/06/08 11:38:46, nickie wrote: > On 2016/06/06 20:51:02, adamk wrote: > > Yikes, was this a memory leak before? Maybe pull this into a separate patch? > > As far as I understand, it was not a memory leak. It was just using the heap, > instead of the zone, for storing the list of DestructuringAssignments. The list > destructor clears the space. Ah, I forgot this was in FunctionState, not some ZoneObject. https://codereview.chromium.org/1708193003/diff/120001/src/parsing/parser-bas... src/parsing/parser-base.h:1673: ExpressionClassifier binding_classifier(this); On 2016/06/08 11:38:46, nickie wrote: > On 2016/06/06 20:51:02, adamk wrote: > > Can we wrap this and the next two lines in a block, now that the classifier > used > > inside the loop is a different one? That'd avoid shadowing. > > What you're suggesting is a common pattern in parser.cc but not in parser-base.h > It can be done but not so easily because, as you say in the next comment, > result will have to be declared before the block, e.g. > > ExpressionT result; > { > ExpressionClassifier binding_classifier(this); > result = this->ParseAssignmentExpression(...); > classifier->Accumulate(&binding_classifier, ...); > } > > Now, for the parser where ExpressionT is a pointer, this is equivalent. > For the preparser, where ExpressionT is PreParserExpression, there is no default > constructor, so we would have to replace the first line with something like: > > ExpressionT elem = this->EmptyExpression(); > > Again, in the case of the parser this would be almost equivalent, as > EmptyExpression returns NULL and the compiler will probably figure out that > initialization is not necessary. For the preparser, however, I think that this > would first initialize a PreParserExpression object and then use the copy > constructor to copy a new value there. > > In any case, this pattern with the extraneous initialization occurs in several > places in parser-base.h and it would not harm much to add one more here, if you > insist. If you think it's unlikely to be a significant perf regression, I do think that this block would make the code more understandable. At the moment it's a bit surprising to a casual reader that the Accumulate() call is to the outer |classifier|, not this binding_classifier, even though the latter is the closest one on the stack. https://codereview.chromium.org/1708193003/diff/140001/src/parsing/expression... File src/parsing/expression-classifier.h (right): https://codereview.chromium.org/1708193003/diff/140001/src/parsing/expression... src/parsing/expression-classifier.h:374: if (errors != 0) { Maybe it's the jetlag talking, but I still find this block somewhat impenetrable. I'm usual opposed to comments that explain what the code's doing ("code should be self-documenting", after all), but I think this might be an exception. How would you feel about some explanatory comments here? https://codereview.chromium.org/1708193003/diff/140001/src/parsing/expression... src/parsing/expression-classifier.h:472: int reported_errors_end_; Could we squeeze another word in on 32 bit platforms by using int16s here?
https://codereview.chromium.org/1708193003/diff/140001/src/parsing/expression... File src/parsing/expression-classifier.h (right): https://codereview.chromium.org/1708193003/diff/140001/src/parsing/expression... src/parsing/expression-classifier.h:374: if (errors != 0) { On 2016/06/09 08:25:37, adamk wrote: > Maybe it's the jetlag talking, but I still find this block somewhat > impenetrable. I'm usual opposed to comments that explain what the code's doing > ("code should be self-documenting", after all), but I think this might be an > exception. > > How would you feel about some explanatory comments here? Done. I made some simplifications too, I think now it's much clearer. https://codereview.chromium.org/1708193003/diff/140001/src/parsing/expression... src/parsing/expression-classifier.h:472: int reported_errors_end_; On 2016/06/09 08:25:37, adamk wrote: > Could we squeeze another word in on 32 bit platforms by using int16s here? Yes, unless we care about things like: eval("var x;" + "x=".repeat(65536) + "42"); This already causes a stack overflow while parsing, so I guess we don't care much. We can also do the same for non_pattern_begin and, after reordering, we could save one extra word on 64 bit platforms. This could fail in case of something like: eval("var x=[];" + "[" + "[...x],".repeat(65536) + "].length") which also causes a stack overflow while parsing. Both done. We're now down to 40 bytes on 64-bit architectures and 24 bytes on 32-bit ones. I believe we can live with this but, if we want to play 100% safe, we can introduce this check: CHECK_LT(non_patterns_to_rewrite_.length(), 1 << sizeof(uint16_t)); after this line: https://cs.chromium.org/chromium/src/v8/src/parsing/parser-base.h?rcl=0&l=440
The CQ bit was checked by nikolaos@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/patch-status/1708193003/160001
lgtm % comment/check Also maybe retitle the top of the CL description to be more explicit in what's changed? https://codereview.chromium.org/1708193003/diff/140001/src/parsing/expression... File src/parsing/expression-classifier.h (right): https://codereview.chromium.org/1708193003/diff/140001/src/parsing/expression... src/parsing/expression-classifier.h:472: int reported_errors_end_; On 2016/06/09 15:10:18, nickie wrote: > On 2016/06/09 08:25:37, adamk wrote: > > Could we squeeze another word in on 32 bit platforms by using int16s here? > > Yes, unless we care about things like: > eval("var x;" + "x=".repeat(65536) + "42"); > This already causes a stack overflow while parsing, so I guess we don't care > much. > > We can also do the same for non_pattern_begin and, after reordering, we could > save one extra word on 64 bit platforms. This could fail in case of something > like: > eval("var x=[];" + "[" + "[...x],".repeat(65536) + "].length") > which also causes a stack overflow while parsing. > > Both done. We're now down to 40 bytes on 64-bit architectures and 24 bytes on > 32-bit ones. > > I believe we can live with this but, if we want to play 100% safe, we can > introduce this check: > CHECK_LT(non_patterns_to_rewrite_.length(), 1 << sizeof(uint16_t)); > after this line: > https://cs.chromium.org/chromium/src/v8/src/parsing/parser-base.h?rcl=0&l=440 That CHECK seems like a good idea to me, maybe use std::numeric_limits? https://codereview.chromium.org/1708193003/diff/160001/src/parsing/expression... File src/parsing/expression-classifier.h (right): https://codereview.chromium.org/1708193003/diff/160001/src/parsing/expression... src/parsing/expression-classifier.h:480: uint16_t reported_errors_begin_; Can you add a comment here mentioning that these are big enough because we'd get a stack overflow if we were ever about to overflow?
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: This issue passed the CQ dry run.
On 9 June 2016 at 17:30, <adamk@chromium.org> wrote: > That CHECK seems like a good idea to me, maybe use std::numeric_limits? This CHECK seems to be a bit more complicated. If introduced, it leads to a crash before the stack overflow happens, in examples like: var N=65536; eval("var x=[];" + "[" + "[...x],".repeat(N) + "].length"); As we discussed, I'm making this a special (implementation limit) syntax error. https://codereview.chromium.org/1708193003/diff/160001/src/parsing/expression... File src/parsing/expression-classifier.h (right): https://codereview.chromium.org/1708193003/diff/160001/src/parsing/expression... src/parsing/expression-classifier.h:480: uint16_t reported_errors_begin_; On 2016/06/09 15:30:01, adamk wrote: > Can you add a comment here mentioning that these are big enough because we'd get > a stack overflow if we were ever about to overflow? Done.
The CQ bit was checked by nikolaos@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/patch-status/1708193003/180001
Description was changed from ========== Expression classifiers revisited This patch attempts to reduce the (stack) memory footprint of expression classifiers. Instead of keeping space in each classifier for all possible error messages that will (potentially) be reported, if an expression turns out to be a pattern or a non-pattern, such error messages are placed in a list shared by the FunctionState and each classifier keeps a couple of indices in this list. This requires that classifiers are used strictly in a stack-based fashion, which is also in line with my previous patch for revisiting non-pattern rewriting. R=rossberg@chromium.org BUG=chromium:528697 ========== to ========== Reduce the memory footprint of expression classifiers This patch attempts to reduce the (stack) memory footprint of expression classifiers. Instead of keeping space in each classifier for all possible error messages that will (potentially) be reported, if an expression turns out to be a pattern or a non-pattern, such error messages are placed in a list shared by the FunctionState and each classifier keeps a couple of indices in this list. This requires that classifiers are used strictly in a stack-based fashion, which is also in line with my previous patch for revisiting non-pattern rewriting. R=adamk@chromium.org BUG=chromium:528697 ==========
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: This issue passed the CQ dry run.
I ran the perfbots again for PS #10 and updated the design doc.
still lgtm I'm happy for you to land this and see what the bots say.
The CQ bit was checked by nikolaos@chromium.org
CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/patch-status/1708193003/180001
Message was sent while issue was closed.
Description was changed from ========== Reduce the memory footprint of expression classifiers This patch attempts to reduce the (stack) memory footprint of expression classifiers. Instead of keeping space in each classifier for all possible error messages that will (potentially) be reported, if an expression turns out to be a pattern or a non-pattern, such error messages are placed in a list shared by the FunctionState and each classifier keeps a couple of indices in this list. This requires that classifiers are used strictly in a stack-based fashion, which is also in line with my previous patch for revisiting non-pattern rewriting. R=adamk@chromium.org BUG=chromium:528697 ========== to ========== Reduce the memory footprint of expression classifiers This patch attempts to reduce the (stack) memory footprint of expression classifiers. Instead of keeping space in each classifier for all possible error messages that will (potentially) be reported, if an expression turns out to be a pattern or a non-pattern, such error messages are placed in a list shared by the FunctionState and each classifier keeps a couple of indices in this list. This requires that classifiers are used strictly in a stack-based fashion, which is also in line with my previous patch for revisiting non-pattern rewriting. R=adamk@chromium.org BUG=chromium:528697 ==========
Message was sent while issue was closed.
Committed patchset #10 (id:180001)
Message was sent while issue was closed.
On 2016/06/10 16:31:16, adamk wrote: > still lgtm > > I'm happy for you to land this and see what the bots say. Alea jacta est.
Message was sent while issue was closed.
Description was changed from ========== Reduce the memory footprint of expression classifiers This patch attempts to reduce the (stack) memory footprint of expression classifiers. Instead of keeping space in each classifier for all possible error messages that will (potentially) be reported, if an expression turns out to be a pattern or a non-pattern, such error messages are placed in a list shared by the FunctionState and each classifier keeps a couple of indices in this list. This requires that classifiers are used strictly in a stack-based fashion, which is also in line with my previous patch for revisiting non-pattern rewriting. R=adamk@chromium.org BUG=chromium:528697 ========== to ========== Reduce the memory footprint of expression classifiers This patch attempts to reduce the (stack) memory footprint of expression classifiers. Instead of keeping space in each classifier for all possible error messages that will (potentially) be reported, if an expression turns out to be a pattern or a non-pattern, such error messages are placed in a list shared by the FunctionState and each classifier keeps a couple of indices in this list. This requires that classifiers are used strictly in a stack-based fashion, which is also in line with my previous patch for revisiting non-pattern rewriting. R=adamk@chromium.org BUG=chromium:528697 Committed: https://crrev.com/dfb8d3331e7cb2c3e67ef820cbcb6cfbae7159e5 Cr-Commit-Position: refs/heads/master@{#36897} ==========
Message was sent while issue was closed.
Patchset 10 (id:??) landed as https://crrev.com/dfb8d3331e7cb2c3e67ef820cbcb6cfbae7159e5 Cr-Commit-Position: refs/heads/master@{#36897} |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
