Issue metadata
Sign in to add a comment
|
Recursive functions run out of stack space earlier with Chrome 60 than 59
Reported by
andrew.h...@gmail.com,
Aug 9 2017
|
||||||||||||||||||||||
Issue descriptionUserAgent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_12_6) AppleWebKit/603.3.8 (KHTML, like Gecko) Version/10.1.2 Safari/603.3.8 Steps to reproduce the problem: 1. Load the attached index.html 2. Click the button 3. Look in the JavaScript console What is the expected behavior? 10004 should be printed What went wrong? Uncaught RangeError: Maximum call stack size exceeded Did this work before? Yes 59.0.3071.86 Chrome version: 60.0.3112.90 (Official Build) (64-bit) Channel: stable OS Version: OS X 10.12.6 Flash Version: I'm executing code generated by Bucklescript. This code is heavily recursive, but it did operate with my target use case on Chrome 59. In Chrome 60 with the same input it's running out of stack space. I first saw this in the 60 beta, but after chatting with the Bucklescript developer I decided to wait for the stable release. It still has this problem. I've tracked the issue down to some specific functions that are mutually tail-recursive. Using `Error.stackTraceLimit = Infinity` I can see my code is failing in Chrome 60 on macOS Sierra at a stack size of about 5000. I've created a small pure JS test case showing the pattern of the code created by Bucklescript. The example continues recursing until it counts up to a maximum. The "max" variable is global so it can be adjusted from the console; it defaults to 10000. I used console commands such as `max=20000;main()` to update and re-run the test. Chrome does optimise the example code after executing it a few times, so I'm including two values for it. I'm only using round numbers for testing given that the limit is likely dependent on the environment and other context. - Chrome 60 fails. After slowly lowering max it only started passing on load at 8900, optimised it can reach 50k - Chrome 59 passes, in fact it can do about 19k on page load, after optimisation I can push it to 90k - Firefox 54 passes, can do 400k on page load - Safari with PTC has no limit, I tested as far as 10 million and figured that was enough I generated these numbers using Chrome on Windows 10 for ease of comparison between 60 and 59. I used macOS Sierra for FF54 and Safari. I also tried copy/pasting the code into a Node.js v8.2.1 repl - 17k on load, 48k after optimisation. The problem here is not that I want infinite recursion and PTC. I understand that's a hard problem. But the available stack space for recursion appears to be significantly reduced in 60 vs 59. I have also checked this in Canary 62.0.3180.0 and it only managed 6900 on page load.
,
Aug 11 2017
Tested the issue on mac os 10.12.6 (Retina & Non-Retina) using chrome M60 #60.0.3112.90 and M59 #59.0.3071.86 and observed same behavior. Attached screencast for reference. @andrew.herron-- Could you please check attached screenshot and confirm if this is the issue and expected result screenshot for better understanding. Thanks!
,
Aug 14 2017
Ah, my apologies, I just loaded up Chrome 59 on a Mac VM and it does indeed break. I'm sure it used to work (I switched to 60 beta on my laptop long before my code started getting recursive enough to see this issue). Your screenshot shows the bug; when it works there is no error. Please try again with Windows 10, where I've just re-confirmed the sample works in Chrome 59.
,
Aug 14 2017
Thank you for providing more feedback. Adding requester "hdodda@chromium.org" to the cc list and removing "Needs-Feedback" label. For more details visit https://www.chromium.org/issue-tracking/autotriage - Your friendly Sheriffbot
,
Aug 15 2017
,
Aug 15 2017
,
Aug 15 2017
,
Aug 16 2017
,
Aug 21 2017
There are two regressions going on here: 1) 19,000 recursions down to ~8900 recursions between m58/59 and m60. 2) The regression from 8900 to 6900 in m62. Regression (1) is almost certainly due to the switch from Full-Codegen to Ignition (the switch happened in m59 but we had a small population running the old full-codegen pipeline in m59 which is presumably why the original reporter didn't see this in m59). There isn't much we can do about this without fundamental changes to the interpreter. There is one change I've made in m62 which should help slightly, although it's masked by regression (2) below. I've bisected regression (2) down "[ic] Properly integrate the CallIC into Ignition". Since Benedikt is OOO this week I'll take a look and see if I can recover the regression.
,
Aug 23 2017
Issue v8:6438 has been merged into this issue.
,
Aug 23 2017
I have a change in-progress which should improve this to around 12,500 recursive iterations on x64. I'll try to get this landed soon, however it's quite involved so it's not something we can back-merge. As such, the first version which will see the fix will be m62. We will still have the regression to ~8900 recursive calls in m59-m61 (although not the further regression to 6900 recursive calls mentioned in #9).
,
Aug 24 2017
Thanks, that's pretty good! I guess a full fix for this style of coding will have to wait for ES6 proper tail calls. I'm aware they are a bit of a sticking point, hopefully with the rise of AltJS compilers and functional programming there will be a growing use case to have them ;) I've been talking to the bucklescript developer some more and he's considering an option to add trampolines to solve this for now.
,
Aug 25 2017
The following revision refers to this bug: https://chromium.googlesource.com/v8/v8.git/+/5716fe8de7cfac4b583d3c2ab4499083f3e22ecc commit 5716fe8de7cfac4b583d3c2ab4499083f3e22ecc Author: Ross McIlroy <rmcilroy@chromium.org> Date: Fri Aug 25 10:05:28 2017 [Interpreter] Saving bytecode offset for the prefix bytecode on wide bytecodes For wide bytecodes, save the bytecode offset as the offset of the prefix bytecode, rather than the bytecode itself. This means that any code that reads the bytecode can explicitly know the width of the bytecode at the offset without having to iterate through the complete bytecode array. Also simplifies some code in the bytecode analysis that had to work around the previous approach. BUG= chromium:753705 Change-Id: I8a42e7cfff27791e39f3452e2b9e52c0608d28cb Reviewed-on: https://chromium-review.googlesource.com/634003 Commit-Queue: Ross McIlroy <rmcilroy@chromium.org> Reviewed-by: Michael Starzinger <mstarzinger@chromium.org> Cr-Commit-Position: refs/heads/master@{#47599} [modify] https://crrev.com/5716fe8de7cfac4b583d3c2ab4499083f3e22ecc/src/compiler/bytecode-analysis.cc [modify] https://crrev.com/5716fe8de7cfac4b583d3c2ab4499083f3e22ecc/src/interpreter/interpreter-assembler.cc [modify] https://crrev.com/5716fe8de7cfac4b583d3c2ab4499083f3e22ecc/src/interpreter/interpreter-assembler.h
,
Aug 25 2017
The following revision refers to this bug: https://chromium.googlesource.com/v8/v8.git/+/51a15140166c9d18debd241f7d81da9918403363 commit 51a15140166c9d18debd241f7d81da9918403363 Author: Ross McIlroy <rmcilroy@chromium.org> Date: Fri Aug 25 21:32:09 2017 [Interpreter] Adapt Call bytecode handlers to drop their stack-frame. This change adapts the Call bytecode handlers such that they don't require a stack frame. It does this by modifying the call bytecode handler to tail-call the Call or InterpreterPushArgsAndCall builtins. As a result, the callee function will return to the InterpreterEntryTrampoline when it returns (since this is the return address on the interpreter frame), which is adapted to dispatch to the next bytecode handler. The return bytecode handler is modified to tail-call a new InterpreterExitTramoline instead of returning to the InterpreterEntryTrampoline. Overall this significanlty reduces the amount of stack space required for interpreter frames, increasing the maximum depth of recursive calls from around 6000 to around 12,500 on x64. BUG= chromium:753705 Change-Id: I23328e4cef878df3aca4db763b47d72a2cce664c Reviewed-on: https://chromium-review.googlesource.com/634364 Commit-Queue: Ross McIlroy <rmcilroy@chromium.org> Reviewed-by: Michael Starzinger <mstarzinger@chromium.org> Reviewed-by: Leszek Swirski <leszeks@chromium.org> Cr-Commit-Position: refs/heads/master@{#47617} [modify] https://crrev.com/51a15140166c9d18debd241f7d81da9918403363/src/arm/interface-descriptors-arm.cc [modify] https://crrev.com/51a15140166c9d18debd241f7d81da9918403363/src/arm64/interface-descriptors-arm64.cc [modify] https://crrev.com/51a15140166c9d18debd241f7d81da9918403363/src/assembler.cc [modify] https://crrev.com/51a15140166c9d18debd241f7d81da9918403363/src/assembler.h [modify] https://crrev.com/51a15140166c9d18debd241f7d81da9918403363/src/builtins/arm/builtins-arm.cc [modify] https://crrev.com/51a15140166c9d18debd241f7d81da9918403363/src/builtins/arm64/builtins-arm64.cc [modify] https://crrev.com/51a15140166c9d18debd241f7d81da9918403363/src/builtins/builtins-definitions.h [modify] https://crrev.com/51a15140166c9d18debd241f7d81da9918403363/src/builtins/ia32/builtins-ia32.cc [modify] https://crrev.com/51a15140166c9d18debd241f7d81da9918403363/src/builtins/mips/builtins-mips.cc [modify] https://crrev.com/51a15140166c9d18debd241f7d81da9918403363/src/builtins/mips64/builtins-mips64.cc [modify] https://crrev.com/51a15140166c9d18debd241f7d81da9918403363/src/builtins/x64/builtins-x64.cc [modify] https://crrev.com/51a15140166c9d18debd241f7d81da9918403363/src/code-factory.cc [modify] https://crrev.com/51a15140166c9d18debd241f7d81da9918403363/src/code-factory.h [modify] https://crrev.com/51a15140166c9d18debd241f7d81da9918403363/src/compiler/code-assembler.cc [modify] https://crrev.com/51a15140166c9d18debd241f7d81da9918403363/src/compiler/code-assembler.h [modify] https://crrev.com/51a15140166c9d18debd241f7d81da9918403363/src/external-reference-table.cc [modify] https://crrev.com/51a15140166c9d18debd241f7d81da9918403363/src/ia32/interface-descriptors-ia32.cc [modify] https://crrev.com/51a15140166c9d18debd241f7d81da9918403363/src/interface-descriptors.cc [modify] https://crrev.com/51a15140166c9d18debd241f7d81da9918403363/src/interface-descriptors.h [modify] https://crrev.com/51a15140166c9d18debd241f7d81da9918403363/src/interpreter/bytecode-operands.h [modify] https://crrev.com/51a15140166c9d18debd241f7d81da9918403363/src/interpreter/bytecodes.cc [modify] https://crrev.com/51a15140166c9d18debd241f7d81da9918403363/src/interpreter/bytecodes.h [modify] https://crrev.com/51a15140166c9d18debd241f7d81da9918403363/src/interpreter/interpreter-assembler.cc [modify] https://crrev.com/51a15140166c9d18debd241f7d81da9918403363/src/interpreter/interpreter-assembler.h [modify] https://crrev.com/51a15140166c9d18debd241f7d81da9918403363/src/interpreter/interpreter-generator.cc [modify] https://crrev.com/51a15140166c9d18debd241f7d81da9918403363/src/interpreter/interpreter-intrinsics-generator.cc [modify] https://crrev.com/51a15140166c9d18debd241f7d81da9918403363/src/mips/interface-descriptors-mips.cc [modify] https://crrev.com/51a15140166c9d18debd241f7d81da9918403363/src/mips64/interface-descriptors-mips64.cc [modify] https://crrev.com/51a15140166c9d18debd241f7d81da9918403363/src/runtime/runtime-interpreter.cc [modify] https://crrev.com/51a15140166c9d18debd241f7d81da9918403363/src/runtime/runtime.h [modify] https://crrev.com/51a15140166c9d18debd241f7d81da9918403363/src/x64/interface-descriptors-x64.cc [modify] https://crrev.com/51a15140166c9d18debd241f7d81da9918403363/test/unittests/interpreter/interpreter-assembler-unittest.cc
,
Aug 25 2017
#14 - sorry for hijacking - can you also look at this serious regression? issue 752081 . Thank you.
,
Aug 25 2017
This is unrelated to issue 752081 - this is recursion in JS code where issue 752081 is running out of stack while the parser recurses.
,
Aug 25 2017
,
Aug 25 2017
#16 - I know it is unrelated, this is why this is "hijacking". ;)
,
Aug 25 2017
I dnn't own the parser so I'm not the right person to look at issue 752081 (but I added the parser component so they know about the regression).
,
Aug 29 2017
The following revision refers to this bug: https://chromium.googlesource.com/v8/v8.git/+/e5b93bd57f2bbed54a6e353b7945e07acc57dab3 commit e5b93bd57f2bbed54a6e353b7945e07acc57dab3 Author: Jaideep Bajwa <bjaideep@ca.ibm.com> Date: Tue Aug 29 22:46:46 2017 PPC/s390: [Interpreter] Adapt Call bytecode handlers to drop their stack-frame. Port 51a15140166c9d18debd241f7d81da9918403363 Original Commit Message: This change adapts the Call bytecode handlers such that they don't require a stack frame. It does this by modifying the call bytecode handler to tail-call the Call or InterpreterPushArgsAndCall builtins. As a result, the callee function will return to the InterpreterEntryTrampoline when it returns (since this is the return address on the interpreter frame), which is adapted to dispatch to the next bytecode handler. The return bytecode handler is modified to tail-call a new InterpreterExitTramoline instead of returning to the InterpreterEntryTrampoline. Overall this significanlty reduces the amount of stack space required for interpreter frames, increasing the maximum depth of recursive calls from around 6000 to around 12,500 on x64. R=rmcilroy@chromium.org, joransiu@ca.ibm.com, jyan@ca.ibm.com, michael_dawson@ca.ibm.com BUG= chromium:753705 LOG=N Change-Id: Ieac490d82098c13741080061eda762d54baf8c04 Reviewed-on: https://chromium-review.googlesource.com/639315 Reviewed-by: Junliang Yan <jyan@ca.ibm.com> Commit-Queue: Jaideep Bajwa <bjaideep@ca.ibm.com> Cr-Commit-Position: refs/heads/master@{#47694} [modify] https://crrev.com/e5b93bd57f2bbed54a6e353b7945e07acc57dab3/src/builtins/ppc/builtins-ppc.cc [modify] https://crrev.com/e5b93bd57f2bbed54a6e353b7945e07acc57dab3/src/builtins/s390/builtins-s390.cc [modify] https://crrev.com/e5b93bd57f2bbed54a6e353b7945e07acc57dab3/src/ppc/interface-descriptors-ppc.cc [modify] https://crrev.com/e5b93bd57f2bbed54a6e353b7945e07acc57dab3/src/s390/interface-descriptors-s390.cc
,
Sep 5 2017
The following revision refers to this bug: https://chromium.googlesource.com/v8/v8.git/+/30f08f39f947bf94923dd8eb150589ad30b27a16 commit 30f08f39f947bf94923dd8eb150589ad30b27a16 Author: Ross McIlroy <rmcilroy@chromium.org> Date: Tue Sep 05 16:20:39 2017 [Interpreter] Remove InterpreterExitTrampoline. Always return to the InterpreterEntryTrampoline rather than calling the InterpreterExitTrampoline from the Return bytecode handler. This fixes a regression which occured if we upset the call/return stack by skipping the return to the InterpreterEntryTrampoline from the return bytecode handler. BUG=chromium:759390, chromium:753705 Change-Id: Ib625654a4a5072ac6c8d8e9611d1b9c0bbced4ca Reviewed-on: https://chromium-review.googlesource.com/649517 Commit-Queue: Ross McIlroy <rmcilroy@chromium.org> Reviewed-by: Leszek Swirski <leszeks@chromium.org> Cr-Commit-Position: refs/heads/master@{#47826} [modify] https://crrev.com/30f08f39f947bf94923dd8eb150589ad30b27a16/src/arm/interface-descriptors-arm.cc [modify] https://crrev.com/30f08f39f947bf94923dd8eb150589ad30b27a16/src/arm64/interface-descriptors-arm64.cc [modify] https://crrev.com/30f08f39f947bf94923dd8eb150589ad30b27a16/src/builtins/arm/builtins-arm.cc [modify] https://crrev.com/30f08f39f947bf94923dd8eb150589ad30b27a16/src/builtins/arm64/builtins-arm64.cc [modify] https://crrev.com/30f08f39f947bf94923dd8eb150589ad30b27a16/src/builtins/builtins-definitions.h [modify] https://crrev.com/30f08f39f947bf94923dd8eb150589ad30b27a16/src/builtins/ia32/builtins-ia32.cc [modify] https://crrev.com/30f08f39f947bf94923dd8eb150589ad30b27a16/src/builtins/mips/builtins-mips.cc [modify] https://crrev.com/30f08f39f947bf94923dd8eb150589ad30b27a16/src/builtins/mips64/builtins-mips64.cc [modify] https://crrev.com/30f08f39f947bf94923dd8eb150589ad30b27a16/src/builtins/x64/builtins-x64.cc [modify] https://crrev.com/30f08f39f947bf94923dd8eb150589ad30b27a16/src/code-factory.cc [modify] https://crrev.com/30f08f39f947bf94923dd8eb150589ad30b27a16/src/code-factory.h [modify] https://crrev.com/30f08f39f947bf94923dd8eb150589ad30b27a16/src/ia32/interface-descriptors-ia32.cc [modify] https://crrev.com/30f08f39f947bf94923dd8eb150589ad30b27a16/src/interface-descriptors.cc [modify] https://crrev.com/30f08f39f947bf94923dd8eb150589ad30b27a16/src/interface-descriptors.h [modify] https://crrev.com/30f08f39f947bf94923dd8eb150589ad30b27a16/src/interpreter/interpreter-assembler.cc [modify] https://crrev.com/30f08f39f947bf94923dd8eb150589ad30b27a16/src/interpreter/interpreter-generator.cc [modify] https://crrev.com/30f08f39f947bf94923dd8eb150589ad30b27a16/src/mips/interface-descriptors-mips.cc [modify] https://crrev.com/30f08f39f947bf94923dd8eb150589ad30b27a16/src/mips64/interface-descriptors-mips64.cc [modify] https://crrev.com/30f08f39f947bf94923dd8eb150589ad30b27a16/src/runtime/runtime-debug.cc [modify] https://crrev.com/30f08f39f947bf94923dd8eb150589ad30b27a16/src/x64/interface-descriptors-x64.cc
,
Sep 7 2017
The following revision refers to this bug: https://chromium.googlesource.com/v8/v8.git/+/a7d21a613e6c850314217100829602223988c0f3 commit a7d21a613e6c850314217100829602223988c0f3 Author: Ross McIlroy <rmcilroy@chromium.org> Date: Thu Sep 07 09:21:52 2017 Merged: [Interpreter] Remove InterpreterExitTrampoline. Revision: 30f08f39f947bf94923dd8eb150589ad30b27a16 BUG= chromium:753705 ,chromium:759390 LOG=N NOTRY=true NOPRESUBMIT=true NOTREECHECKS=true TBR=leszeks Change-Id: I1f347e54054bb0babc17d4124d992e683c2ba530 Reviewed-on: https://chromium-review.googlesource.com/654043 Reviewed-by: Leszek Swirski <leszeks@chromium.org> Cr-Commit-Position: refs/branch-heads/6.2@{#5} Cr-Branched-From: efa2ac4129d30c7c72e84c16af3d20b44829f990-refs/heads/6.2.414@{#1} Cr-Branched-From: a861ebb762a60bf5cc2a274faee3620abfb06311-refs/heads/master@{#47693} [modify] https://crrev.com/a7d21a613e6c850314217100829602223988c0f3/src/arm/interface-descriptors-arm.cc [modify] https://crrev.com/a7d21a613e6c850314217100829602223988c0f3/src/arm64/interface-descriptors-arm64.cc [modify] https://crrev.com/a7d21a613e6c850314217100829602223988c0f3/src/builtins/arm/builtins-arm.cc [modify] https://crrev.com/a7d21a613e6c850314217100829602223988c0f3/src/builtins/arm64/builtins-arm64.cc [modify] https://crrev.com/a7d21a613e6c850314217100829602223988c0f3/src/builtins/builtins-definitions.h [modify] https://crrev.com/a7d21a613e6c850314217100829602223988c0f3/src/builtins/ia32/builtins-ia32.cc [modify] https://crrev.com/a7d21a613e6c850314217100829602223988c0f3/src/builtins/mips/builtins-mips.cc [modify] https://crrev.com/a7d21a613e6c850314217100829602223988c0f3/src/builtins/mips64/builtins-mips64.cc [modify] https://crrev.com/a7d21a613e6c850314217100829602223988c0f3/src/builtins/x64/builtins-x64.cc [modify] https://crrev.com/a7d21a613e6c850314217100829602223988c0f3/src/code-factory.cc [modify] https://crrev.com/a7d21a613e6c850314217100829602223988c0f3/src/code-factory.h [modify] https://crrev.com/a7d21a613e6c850314217100829602223988c0f3/src/ia32/interface-descriptors-ia32.cc [modify] https://crrev.com/a7d21a613e6c850314217100829602223988c0f3/src/interface-descriptors.cc [modify] https://crrev.com/a7d21a613e6c850314217100829602223988c0f3/src/interface-descriptors.h [modify] https://crrev.com/a7d21a613e6c850314217100829602223988c0f3/src/interpreter/interpreter-assembler.cc [modify] https://crrev.com/a7d21a613e6c850314217100829602223988c0f3/src/interpreter/interpreter-generator.cc [modify] https://crrev.com/a7d21a613e6c850314217100829602223988c0f3/src/mips/interface-descriptors-mips.cc [modify] https://crrev.com/a7d21a613e6c850314217100829602223988c0f3/src/mips64/interface-descriptors-mips64.cc [modify] https://crrev.com/a7d21a613e6c850314217100829602223988c0f3/src/runtime/runtime-debug.cc [modify] https://crrev.com/a7d21a613e6c850314217100829602223988c0f3/src/x64/interface-descriptors-x64.cc
,
Sep 7 2017
The following revision refers to this bug: https://chromium.googlesource.com/v8/v8.git/+/06d6b55ff20197fb91deca525b7949d8acc35800 commit 06d6b55ff20197fb91deca525b7949d8acc35800 Author: Jaideep Bajwa <bjaideep@ca.ibm.com> Date: Thu Sep 07 17:09:53 2017 Merged: Squashed multiple commits. Merged: PPC/s390: [Interpreter] Adapt Call bytecode handlers to drop their stack-frame. Revision: e5b93bd57f2bbed54a6e353b7945e07acc57dab3 Merged: s390/PPC: Remove InterpreterExitTrampoline. Revision: 40c98daa177d8b06b2996c005a7886d36e19184f Merged: PPC: use the correct condition register Revision: b9747f357fc9c097bb9ec4b56ac19a988e2399a7 BUG= chromium:753705 LOG=N NOTRY=true NOPRESUBMIT=true NOTREECHECKS=true R=hablich@chromium.org, joransiu@ca.ibm.com, jyan@ca.ibm.com, rmcilroy@chromium.org Change-Id: Ide8d15f6c3a3f11bce9359e481426007735708bb Reviewed-on: https://chromium-review.googlesource.com/655123 Reviewed-by: Junliang Yan <jyan@ca.ibm.com> Commit-Queue: Junliang Yan <jyan@ca.ibm.com> Cr-Commit-Position: refs/branch-heads/6.2@{#7} Cr-Branched-From: efa2ac4129d30c7c72e84c16af3d20b44829f990-refs/heads/6.2.414@{#1} Cr-Branched-From: a861ebb762a60bf5cc2a274faee3620abfb06311-refs/heads/master@{#47693} [modify] https://crrev.com/06d6b55ff20197fb91deca525b7949d8acc35800/src/builtins/ppc/builtins-ppc.cc [modify] https://crrev.com/06d6b55ff20197fb91deca525b7949d8acc35800/src/builtins/s390/builtins-s390.cc [modify] https://crrev.com/06d6b55ff20197fb91deca525b7949d8acc35800/src/ppc/code-stubs-ppc.cc |
|||||||||||||||||||||||
►
Sign in to add a comment |
|||||||||||||||||||||||
Comment 1 by phistuck@chromium.org
, Aug 9 2017Labels: Hotlist-Interop