Chromium Code Reviews
|
|
Chromium Code Reviews
Issue
2188153002:
Speed up parsing w/ grammar shortcut. (Closed)
DescriptionSpeed up parsing w/ grammar shortcut.
Certain token combinations (e.g. number literal followed by semicolon) will
result in a single AST node, but require many levels of recursive descent
parsing to determine this (11 in this example). For some 'obvious'
combinations, we'll simply generate the appropriate AST node fairly far up
in the call tree.
This yields a mild but consistent parser speedup. The main con is code duplication.
[Speedup between 0..20ms in parse time among a set of 25 commonly used sites. Speedup of ~180ms for a site w/ a very large codebase (adwords.google.com). Minor slow-downs between 0..8ms for <20% of sites.]
R=marja@chromium.org
BUG=v8:4947
Committed: https://crrev.com/7a100dffc669a1e261831a37dbe67d2a9f8075fa
Cr-Commit-Position: refs/heads/master@{#38591}
Patch Set 1 #Patch Set 2 : Formatting fix. #
Total comments: 4
Patch Set 3 : Seperate function. #Patch Set 4 : Fix PreParserTraits::EmptyExpression #
Total comments: 7
Patch Set 5 : Review feedback. #Patch Set 6 : Rebase. #Patch Set 7 : Reduced code duplication. #
Total comments: 3
Patch Set 8 : Review feedback. #Messages
Total messages: 47 (29 generated)
The CQ bit was checked by vogelheim@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
Patchset #2 (id:20001) has been deleted
Please have a look. https://codereview.chromium.org/2188153002/diff/40001/src/parsing/parser-base.h File src/parsing/parser-base.h (left): https://codereview.chromium.org/2188153002/diff/40001/src/parsing/parser-base... src/parsing/parser-base.h:1554: return this->ExpressionFromLiteral(Next(), beg_pos, scanner(), factory()); [drive-by cleanup]
marja@chromium.org changed reviewers: + adamk@chromium.org
lgtm from my part, relaying parts to adamk@. https://codereview.chromium.org/2188153002/diff/40001/src/parsing/parser-base.h File src/parsing/parser-base.h (right): https://codereview.chromium.org/2188153002/diff/40001/src/parsing/parser-base... src/parsing/parser-base.h:2278: // Parser shortcut: The following scope is a micro-optimization to reduce Can you put all this into a separate function, just to keep ParseAssignmentExpression short? So ParseAssignmentExpression would begin with: if (RV* v = ParseAssignmentExpressionShortcut()) { return v; } https://codereview.chromium.org/2188153002/diff/40001/src/parsing/parser-base... src/parsing/parser-base.h:2326: FuncNameInferrer::State fni_state(fni_); I don't understand the expression classifying stuff, so no idea if this is correct or not. Relaying this part to adamk@.
The CQ bit was checked by vogelheim@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
https://codereview.chromium.org/2188153002/diff/40001/src/parsing/parser-base.h File src/parsing/parser-base.h (right): https://codereview.chromium.org/2188153002/diff/40001/src/parsing/parser-base... src/parsing/parser-base.h:2278: // Parser shortcut: The following scope is a micro-optimization to reduce On 2016/07/28 10:01:28, marja wrote: > Can you put all this into a separate function, just to keep > ParseAssignmentExpression short? > > So ParseAssignmentExpression would begin with: > > if (RV* v = ParseAssignmentExpressionShortcut()) { > return v; > } Done. The hardest part was to figure out how to test for an empty ExpressionT. :-/ I also changed the name to ParseTrivialAssignmentExpression, which is probably a better description of what this does.
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: Try jobs failed on following builders: v8_linux_chromium_gn_rel on master.tryserver.v8 (JOB_FAILED, http://build.chromium.org/p/tryserver.v8/builders/v8_linux_chromium_gn_rel/bu...)
The CQ bit was checked by vogelheim@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: This issue passed the CQ dry run.
In your CL description, can you quantify the "mild but consistent parser speedup" (how mild? on which benchmarks?) https://codereview.chromium.org/2188153002/diff/80001/src/parsing/parser-base.h File src/parsing/parser-base.h (right): https://codereview.chromium.org/2188153002/diff/80001/src/parsing/parser-base... src/parsing/parser-base.h:2310: ExpressionT expression = this->ParseConditionalExpression( What if, rather than putting ParseTrivialAssignmentExpression() up at the top, you put it here instead, after checking for the case that'll be trivially parseable? That would let you eliminate a lot of the worst duplication (the FuncNameInferrer, the ExpressionClassifier) since those are already set up correctly at this point. https://codereview.chromium.org/2188153002/diff/80001/src/parsing/parser-base... src/parsing/parser-base.h:2475: // Parser shortcut: The following scope is a micro-optimization to reduce This can be rewritten now that it's in its own function: s/Parser shortcut: The following scope/This parser shortcut/
https://codereview.chromium.org/2188153002/diff/80001/src/parsing/parser-base.h File src/parsing/parser-base.h (right): https://codereview.chromium.org/2188153002/diff/80001/src/parsing/parser-base... src/parsing/parser-base.h:2283: if (!Traits::IsEmptyExpression(trivial_result)) return trivial_result; Ah right, since we have 2 expression types, this check is more complicated. How about passing the "is trivial" return value explicitly: bool is_trivial = false; ... trivial_result = ParseTrivialAssignmentExpression(..., &is_trivial); if (is_trivial) return trivial_result; Or the other way around: ExpressionT trivial_result; if (ParseTrivialAssignmentExpression(... , &trivial_result)) return trivial_result; Would one of these be clearer than the somewhat artificial emptiness check? I like the second version... In reality, we'd like to pass both the expression and the success bool as return values, and it's just a limitation of C++ that we can't.
The CQ bit was checked by vogelheim@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
Description was changed from ========== Speed up parsing w/ grammar shortcut. Certain token combinations (e.g. number literal followed by semicolon) will result in a single AST node, but require many levels of recursive descent parsing to determine this (11 in this example). For some 'obvious' combinations, we'll simply generate the appropriate AST node fairly far up in the call tree. This yields a mild but consistent parser speedup. The main con is code duplication. R=marja@chromium.org BUG=v8:4947 ========== to ========== Speed up parsing w/ grammar shortcut. Certain token combinations (e.g. number literal followed by semicolon) will result in a single AST node, but require many levels of recursive descent parsing to determine this (11 in this example). For some 'obvious' combinations, we'll simply generate the appropriate AST node fairly far up in the call tree. This yields a mild but consistent parser speedup. The main con is code duplication. [Speedup between 0..20ms in parse time among a set of 25 commonly used sites. Speedup of ~180ms for a site w/ a very large codebase (adwords.google.com). Minor slow-downs between 0..8ms for <20% of sites.] R=marja@chromium.org BUG=v8:4947 ==========
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: Try jobs failed on following builders: v8_linux64_gyp_rel_ng on master.tryserver.v8 (JOB_FAILED, http://build.chromium.org/p/tryserver.v8/builders/v8_linux64_gyp_rel_ng/build...) v8_linux_gcc_compile_rel on master.tryserver.v8 (JOB_FAILED, http://build.chromium.org/p/tryserver.v8/builders/v8_linux_gcc_compile_rel/bu...) v8_linux_mipsel_compile_rel on master.tryserver.v8 (JOB_FAILED, http://build.chromium.org/p/tryserver.v8/builders/v8_linux_mipsel_compile_rel...) v8_mac_rel_ng on master.tryserver.v8 (JOB_FAILED, http://build.chromium.org/p/tryserver.v8/builders/v8_mac_rel_ng/builds/6627)
The CQ bit was checked by vogelheim@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
https://codereview.chromium.org/2188153002/diff/80001/src/parsing/parser-base.h File src/parsing/parser-base.h (right): https://codereview.chromium.org/2188153002/diff/80001/src/parsing/parser-base... src/parsing/parser-base.h:2283: if (!Traits::IsEmptyExpression(trivial_result)) return trivial_result; On 2016/07/29 07:56:04, marja wrote: > Ah right, since we have 2 expression types, this check is more complicated. > > How about passing the "is trivial" return value explicitly: > > bool is_trivial = false; > ... trivial_result = ParseTrivialAssignmentExpression(..., &is_trivial); > if (is_trivial) return trivial_result; > > Or the other way around: > > ExpressionT trivial_result; > if (ParseTrivialAssignmentExpression(... , &trivial_result)) return > trivial_result; > > Would one of these be clearer than the somewhat artificial emptiness check? I > like the second version... > > In reality, we'd like to pass both the expression and the success bool as return > values, and it's just a limitation of C++ that we can't. Done. (2nd version) https://codereview.chromium.org/2188153002/diff/80001/src/parsing/parser-base... src/parsing/parser-base.h:2310: ExpressionT expression = this->ParseConditionalExpression( On 2016/07/28 17:51:55, adamk wrote: > What if, rather than putting ParseTrivialAssignmentExpression() up at the top, > you put it here instead, after checking for the case that'll be trivially > parseable? That would let you eliminate a lot of the worst duplication (the > FuncNameInferrer, the ExpressionClassifier) since those are already set up > correctly at this point. Well... it would also do a lot of work that I'm now skipping. E.g., notice that most branches (all except the Identifier one) don't instantiate a separate classifier and instead record the proper effect directly with the one that's passed in. https://codereview.chromium.org/2188153002/diff/80001/src/parsing/parser-base... src/parsing/parser-base.h:2475: // Parser shortcut: The following scope is a micro-optimization to reduce On 2016/07/28 17:51:55, adamk wrote: > This can be rewritten now that it's in its own function: > > s/Parser shortcut: The following scope/This parser shortcut/ Done.
On 2016/07/28 17:51:55, adamk wrote: > In your CL description, can you quantify the "mild but consistent parser > speedup" (how mild? on which benchmarks?) Done.
lgtm
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: Try jobs failed on following builders: v8_win_rel_ng on master.tryserver.v8 (JOB_FAILED, http://build.chromium.org/p/tryserver.v8/builders/v8_win_rel_ng/builds/12149) v8_win_rel_ng_triggered on master.tryserver.v8 (JOB_FAILED, http://build.chromium.org/p/tryserver.v8/builders/v8_win_rel_ng_triggered/bui...)
https://codereview.chromium.org/2188153002/diff/80001/src/parsing/parser-base.h File src/parsing/parser-base.h (right): https://codereview.chromium.org/2188153002/diff/80001/src/parsing/parser-base... src/parsing/parser-base.h:2310: ExpressionT expression = this->ParseConditionalExpression( On 2016/08/09 11:26:08, vogelheim wrote: > On 2016/07/28 17:51:55, adamk wrote: > > What if, rather than putting ParseTrivialAssignmentExpression() up at the top, > > you put it here instead, after checking for the case that'll be trivially > > parseable? That would let you eliminate a lot of the worst duplication (the > > FuncNameInferrer, the ExpressionClassifier) since those are already set up > > correctly at this point. > > Well... it would also do a lot of work that I'm now skipping. E.g., notice that > most branches (all except the Identifier one) don't instantiate a separate > classifier and instead record the proper effect directly with the one that's > passed in. But we'd still be skipping the function calls, right (my understanding was that the function calls were what was expensive here)? I don't see anything horribly expensive above. And it's the ExpressionClassifier that I especially would like to not see duplicated, since the logic is quite subtle. The FuncNameInferrer would also be nice not to duplicate. The only other expensive work I see is the call to PeekAhead(), but you already do that in ParseTrivial. This seems like something we could measure. Would you mind giving it a shot?
On 2016/08/09 16:39:16, adamk wrote: > https://codereview.chromium.org/2188153002/diff/80001/src/parsing/parser-base.h > File src/parsing/parser-base.h (right): > > https://codereview.chromium.org/2188153002/diff/80001/src/parsing/parser-base... > src/parsing/parser-base.h:2310: ExpressionT expression = > this->ParseConditionalExpression( > On 2016/08/09 11:26:08, vogelheim wrote: > > On 2016/07/28 17:51:55, adamk wrote: > > > What if, rather than putting ParseTrivialAssignmentExpression() up at the > top, > > > you put it here instead, after checking for the case that'll be trivially > > > parseable? That would let you eliminate a lot of the worst duplication (the > > > FuncNameInferrer, the ExpressionClassifier) since those are already set up > > > correctly at this point. > > > > Well... it would also do a lot of work that I'm now skipping. E.g., notice > that > > most branches (all except the Identifier one) don't instantiate a separate > > classifier and instead record the proper effect directly with the one that's > > passed in. > > But we'd still be skipping the function calls, right (my understanding was that > the function calls were what was expensive here)? > > I don't see anything horribly expensive above. And it's the ExpressionClassifier > that I especially would like to not see duplicated, since the logic is quite > subtle. The FuncNameInferrer would also be nice not to duplicate. > > The only other expensive work I see is the call to PeekAhead(), but you already > do that in ParseTrivial. > > This seems like something we could measure. Would you mind giving it a shot? Performance-wise it's a wash. I find it less readable, because it's doesn't eliminate much of the code, and it's now harder to see what the 'shortcut' actually does. I'll clean the patch up & see how it looks like with the 'middle' shortcut.
On 2016/08/10 17:17:19, vogelheim wrote: > On 2016/08/09 16:39:16, adamk wrote: > > > https://codereview.chromium.org/2188153002/diff/80001/src/parsing/parser-base.h > > File src/parsing/parser-base.h (right): > > > > > https://codereview.chromium.org/2188153002/diff/80001/src/parsing/parser-base... > > src/parsing/parser-base.h:2310: ExpressionT expression = > > this->ParseConditionalExpression( > > On 2016/08/09 11:26:08, vogelheim wrote: > > > On 2016/07/28 17:51:55, adamk wrote: > > > > What if, rather than putting ParseTrivialAssignmentExpression() up at the > > top, > > > > you put it here instead, after checking for the case that'll be trivially > > > > parseable? That would let you eliminate a lot of the worst duplication > (the > > > > FuncNameInferrer, the ExpressionClassifier) since those are already set up > > > > correctly at this point. > > > > > > Well... it would also do a lot of work that I'm now skipping. E.g., notice > > that > > > most branches (all except the Identifier one) don't instantiate a separate > > > classifier and instead record the proper effect directly with the one that's > > > passed in. > > > > But we'd still be skipping the function calls, right (my understanding was > that > > the function calls were what was expensive here)? > > > > I don't see anything horribly expensive above. And it's the > ExpressionClassifier > > that I especially would like to not see duplicated, since the logic is quite > > subtle. The FuncNameInferrer would also be nice not to duplicate. > > > > The only other expensive work I see is the call to PeekAhead(), but you > already > > do that in ParseTrivial. > > > > This seems like something we could measure. Would you mind giving it a shot? > > Performance-wise it's a wash. I find it less readable, because it's doesn't > eliminate much of the code, and it's now harder to see what the 'shortcut' > actually does. I'll clean the patch up & see how it looks like with the 'middle' > shortcut. I'm surprised to hear it doesn't eliminate much of the code. Would be interested in seeing a cleaned up patch, I would have imagined it would be much smaller than what you've got now...
On 2016/08/10 17:59:20, adamk wrote: > On 2016/08/10 17:17:19, vogelheim wrote: > > On 2016/08/09 16:39:16, adamk wrote: > > > > > > https://codereview.chromium.org/2188153002/diff/80001/src/parsing/parser-base.h > > > File src/parsing/parser-base.h (right): > > > > > > > > > https://codereview.chromium.org/2188153002/diff/80001/src/parsing/parser-base... > > > src/parsing/parser-base.h:2310: ExpressionT expression = > > > this->ParseConditionalExpression( > > > On 2016/08/09 11:26:08, vogelheim wrote: > > > > On 2016/07/28 17:51:55, adamk wrote: > > > > > What if, rather than putting ParseTrivialAssignmentExpression() up at > the > > > top, > > > > > you put it here instead, after checking for the case that'll be > trivially > > > > > parseable? That would let you eliminate a lot of the worst duplication > > (the > > > > > FuncNameInferrer, the ExpressionClassifier) since those are already set > up > > > > > correctly at this point. > > > > > > > > Well... it would also do a lot of work that I'm now skipping. E.g., notice > > > that > > > > most branches (all except the Identifier one) don't instantiate a separate > > > > classifier and instead record the proper effect directly with the one > that's > > > > passed in. > > > > > > But we'd still be skipping the function calls, right (my understanding was > > that > > > the function calls were what was expensive here)? > > > > > > I don't see anything horribly expensive above. And it's the > > ExpressionClassifier > > > that I especially would like to not see duplicated, since the logic is quite > > > subtle. The FuncNameInferrer would also be nice not to duplicate. > > > > > > The only other expensive work I see is the call to PeekAhead(), but you > > already > > > do that in ParseTrivial. > > > > > > This seems like something we could measure. Would you mind giving it a shot? > > > > Performance-wise it's a wash. I find it less readable, because it's doesn't > > eliminate much of the code, and it's now harder to see what the 'shortcut' > > actually does. I'll clean the patch up & see how it looks like with the > 'middle' > > shortcut. > > I'm surprised to hear it doesn't eliminate much of the code. Would be interested > in seeing a cleaned up patch, I would have imagined it would be much smaller > than what you've got now... Well... I worked on it a bit more and prioritized code reduction. It's now much smaller, since I eliminated all differences to ParsePrimaryExpression and can thus just call it directly.
Wow, this is much more appealing! lgtm besides one comment on if/else vs ternary operator. https://codereview.chromium.org/2188153002/diff/140001/src/parsing/parser-base.h File src/parsing/parser-base.h (right): https://codereview.chromium.org/2188153002/diff/140001/src/parsing/parser-bas... src/parsing/parser-base.h:2317: if (!*ok) return this->EmptyExpression(); I'd rather you use an if/else above so you can keep using CHECK_OK, these manual if (!*ok) checks scare me.
The CQ bit was checked by vogelheim@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
https://codereview.chromium.org/2188153002/diff/140001/src/parsing/parser-base.h File src/parsing/parser-base.h (right): https://codereview.chromium.org/2188153002/diff/140001/src/parsing/parser-bas... src/parsing/parser-base.h:2317: if (!*ok) return this->EmptyExpression(); On 2016/08/11 17:11:05, adamk wrote: > I'd rather you use an if/else above so you can keep using CHECK_OK, these manual > if (!*ok) checks scare me. I'm more scared by CHECK_OK-makes-control-flow-look-like-a-parameter, but ... Done. :)
lgtm! https://codereview.chromium.org/2188153002/diff/140001/src/parsing/parser-base.h File src/parsing/parser-base.h (right): https://codereview.chromium.org/2188153002/diff/140001/src/parsing/parser-bas... src/parsing/parser-base.h:2317: if (!*ok) return this->EmptyExpression(); On 2016/08/11 17:44:08, vogelheim wrote: > On 2016/08/11 17:11:05, adamk wrote: > > I'd rather you use an if/else above so you can keep using CHECK_OK, these > manual > > if (!*ok) checks scare me. > > I'm more scared by CHECK_OK-makes-control-flow-look-like-a-parameter, but ... > Done. :) Heh, to each their own I suppose. But CHECK_OK is clearly the consistent style, and nikolaos@ recently tweaked some macros to make it even more consistent, so I'd rather stay on that road at least for now.
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 vogelheim@chromium.org
The patchset sent to the CQ was uploaded after l-g-t-m from marja@chromium.org Link to the patchset: https://codereview.chromium.org/2188153002/#ps160001 (title: "Review feedback.")
CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
Message was sent while issue was closed.
Description was changed from ========== Speed up parsing w/ grammar shortcut. Certain token combinations (e.g. number literal followed by semicolon) will result in a single AST node, but require many levels of recursive descent parsing to determine this (11 in this example). For some 'obvious' combinations, we'll simply generate the appropriate AST node fairly far up in the call tree. This yields a mild but consistent parser speedup. The main con is code duplication. [Speedup between 0..20ms in parse time among a set of 25 commonly used sites. Speedup of ~180ms for a site w/ a very large codebase (adwords.google.com). Minor slow-downs between 0..8ms for <20% of sites.] R=marja@chromium.org BUG=v8:4947 ========== to ========== Speed up parsing w/ grammar shortcut. Certain token combinations (e.g. number literal followed by semicolon) will result in a single AST node, but require many levels of recursive descent parsing to determine this (11 in this example). For some 'obvious' combinations, we'll simply generate the appropriate AST node fairly far up in the call tree. This yields a mild but consistent parser speedup. The main con is code duplication. [Speedup between 0..20ms in parse time among a set of 25 commonly used sites. Speedup of ~180ms for a site w/ a very large codebase (adwords.google.com). Minor slow-downs between 0..8ms for <20% of sites.] R=marja@chromium.org BUG=v8:4947 ==========
Message was sent while issue was closed.
Committed patchset #8 (id:160001)
Message was sent while issue was closed.
Description was changed from ========== Speed up parsing w/ grammar shortcut. Certain token combinations (e.g. number literal followed by semicolon) will result in a single AST node, but require many levels of recursive descent parsing to determine this (11 in this example). For some 'obvious' combinations, we'll simply generate the appropriate AST node fairly far up in the call tree. This yields a mild but consistent parser speedup. The main con is code duplication. [Speedup between 0..20ms in parse time among a set of 25 commonly used sites. Speedup of ~180ms for a site w/ a very large codebase (adwords.google.com). Minor slow-downs between 0..8ms for <20% of sites.] R=marja@chromium.org BUG=v8:4947 ========== to ========== Speed up parsing w/ grammar shortcut. Certain token combinations (e.g. number literal followed by semicolon) will result in a single AST node, but require many levels of recursive descent parsing to determine this (11 in this example). For some 'obvious' combinations, we'll simply generate the appropriate AST node fairly far up in the call tree. This yields a mild but consistent parser speedup. The main con is code duplication. [Speedup between 0..20ms in parse time among a set of 25 commonly used sites. Speedup of ~180ms for a site w/ a very large codebase (adwords.google.com). Minor slow-downs between 0..8ms for <20% of sites.] R=marja@chromium.org BUG=v8:4947 Committed: https://crrev.com/7a100dffc669a1e261831a37dbe67d2a9f8075fa Cr-Commit-Position: refs/heads/master@{#38591} ==========
Message was sent while issue was closed.
Patchset 8 (id:??) landed as https://crrev.com/7a100dffc669a1e261831a37dbe67d2a9f8075fa Cr-Commit-Position: refs/heads/master@{#38591} |
