michael-weigelt opened PR #14042 from michael-weigelt:mwe/fuel to bytecodealliance:main:
This has been briefly discussed in a private zulip chat with @alexcrichton.
With this PR, 1 fuel is charged for every declared local when a function is invoked.
The reason is that functions may declare up to 50'000 locals without using them on some execution path. In this case, no fuel is spent on accessing them, but the runtime and memory cost of initializing them is paid anyway. In a loop, this can cause significant work that is unaccounted for by fuel.
michael-weigelt requested alexcrichton for a review on PR #14042.
michael-weigelt requested wasmtime-compiler-reviewers for a review on PR #14042.
michael-weigelt requested wasmtime-core-reviewers for a review on PR #14042.
michael-weigelt edited PR #14042:
This has been briefly discussed in a private zulip chat with @alexcrichton.
With this PR, 1 fuel is charged for every declared local when a function is invoked.
The reason is that functions may declare up to 50'000 locals without using them on some execution path. In this case, no fuel is spent on accessing them, but the runtime and memory cost of initializing them is paid anyway. In a loop, this can cause significant work that is unaccounted for by fuel.Locals may have different sizes which could be respected, if we wanted to charge for every byte. Should we? Fuel is currently very coarse-grained, so it does not seem appropriate to get into the details here.
bjorn3 commented on PR #14042:
Why would locals which don't have any definition or use will consume any resources at runtime? The SSA transformation would completely ignore them, right? There is a compile time cost, but fuel is not meant to cover compile time costs. A function with 1000 defined locals and no instructions to run only emits 5 machine instructions on x86_64:
https://rust.godbolt.org/z/r3KjsrTj6
wasm[0]::function[0]: push rbp mov rbp, rsp mov rsp, rbp pop rbp retOr is this about some other cost?
michael-weigelt commented on PR #14042:
@bjorn3 consider a function that returns immediately if its argument is 0. Otherwise, it does some non-constant-foldable computation using its declared locals and returns the result.
I checked the x86 artifact of such a function and saw a big difference (after seeing runtime tests which definitely did some spurious work). I should add here that our use case requires Wasmtime to use no optimizations at all, so it could be that some of my assumptions is wrong, but I am pretty sure that due to the function's conditional return, this issue also exists for optimized code.
michael-weigelt edited a comment on PR #14042:
@bjorn3 consider a function that returns immediately if its argument is 0. Otherwise, it does some non-constant-foldable computation using its declared locals and returns the result.
I checked the x86 artifact of such a function and saw a big difference (after seeing runtime tests which definitely did some spurious work). I should add here that our use case requires Wasmtime to use no optimizations at all, so it could be that some of my assumptions are wrong, but I am pretty sure that due to the function's conditional return, this issue also exists for optimized code.
michael-weigelt edited PR #14042:
This has been briefly discussed in a private zulip chat with @alexcrichton.
With this PR, 1 fuel is charged for every declared local when a function is invoked.
The reason is that functions may declare up to 50'000 locals without using them on some execution path. In this case, no fuel is spent on accessing them, but the runtime and memory cost of initializing them may be paid anyway (if the optimizer cannot remove them due to some other execution path). In a loop, this can cause significant work that is unaccounted for by fuel.Locals may have different sizes which could be respected, if we wanted to charge for every byte. Should we? Fuel is currently very coarse-grained, so it does not seem appropriate to get into the details here.
michael-weigelt edited a comment on PR #14042:
@bjorn3 consider a function that returns immediately if its argument is 0. Otherwise, it does some non-constant-foldable computation using its declared locals and returns the result.
I checked the x86 artifact of such a function and saw a big difference (after seeing runtime tests which also definitely did some spurious work). I should add here that our use case requires Wasmtime to use no optimizations at all, so it could be that some of my assumptions are wrong, but I am pretty sure that due to the function's conditional return, this issue also exists for optimized code.
cfallin commented on PR #14042:
@michael-weigelt actually using the locals requires Wasm opcodes, and for
nlocals one will needO(n)opcodes; is that not enough? Note also that locals are rewritten to SSA dataflow during compilation, and no work is done to "initialize" (generate a 0 value as the initial SSA definition) unless actually used (the way this works in practice: the compiler backend will see that theiconst 0initial values are dead, and just not codegen them).As a variant on bjorn3's test, the WAT
(module (func (result i32) (local i32 i32 i32 i32 i32 i32 i32 i32 i32 i32 i32 i32 i32 i32 i32 i32) local.get 5))also results in a clean function body that's 6 instructions on x86-64 (with
xor eax, eaxto generate the 0 return value).Given this, I believe that charging fuel for initializing locals actually misrepresents the cost -- locals are "free" at runtime, only the dataflow + computation counts.
cfallin commented on PR #14042:
(Note that the "no code unless actually used" is true even with all optimizations disabled: the DCE of the
iconst 0for unused locals is inherent in the lowering algorithm, it's not a separate pass)
michael-weigelt commented on PR #14042:
@cfallin I am not sure your comment takes into account my response to bjorn, perhaps you submitted it before mine was visible on your end (happens to me all the time on github).
the compiler backend will see that the iconst 0 initial values are dead,
But they may not be dead if their usage depends on a runtime argument, right? I should perhaps also say that we use AOT compilation, in case that makes a difference here.
cfallin commented on PR #14042:
Can you provide a WAT showing the behavior you are experiencing?
Your initial description states that there is significant work that occurs that does not cause fuel consumption. What you're describing (locals live on one path, dead on another, control flows through the path where they are dead but initialization still happens) does not make sense with respect to the way we handle locals: we rewrite them into SSA, so if they are live on one path and dead on another, there will not be any defs on the path where they are dead. The original description seems to have an implied world-model where we see that a local is live and generate initialization at function entry, or something like that, which is not the case. So I'd love to see an example to understand exactly what you are seeing!
michael-weigelt commented on PR #14042:
I will follow up, in the meantime thanks for the clarification.
alexcrichton commented on PR #14042:
I'm not sure if this is what you're driving at @michael-weigelt, but for Winch an unused local does indeed generate code. This means that a function with 50k locals generates a significant amount of code in Winch that doesn't have fuel accounting at all. That probably is something we should have fuel for, and then adding it to Cranelift would in spirit be matching the fuel consumption of Winch/Cranelift. I'm not certain if we should do that (match the exact fuel consumption between compilers), but metering code generated by Winch seems reasonable to me (which would be a different shape of PR at least)
michael-weigelt commented on PR #14042:
I reproduced the problem like this:
- Wasmtime 47 with Cranelift and
OptLevel::None.- A function
gowith 100/1000/10000 locals, which returns immediately if its argument is 0, otherwise does some calculation with the locals.- A function
repeatwhich callsgomany times in a loop in order to amplify the overhead.- Measure the time to call
repeat. If the number or locals does not matter, then we should observe the same runtimes in the 100/1000/10000 modules. But that's not the case.Looking at the disassembly of the locals100 artifact (
objdump -p <serialized module>), we have
- a large block of locals calculations
- but just before, there is a
je 93ejump to the end of that block in case the argument is 0.- however, in the locals1000 case, there is a stack probe before that jump.
1c: sub $0x1000,%rsp 23: movl $0x0,(%rsp) 2a: add $0x1000,%rsp 31: sub $0x1f10,%rspand I think that must be the culprit of the slowdown. We dirty pages we never end up needing.
In the 10'000 locals case, it's a loop over 20 pages, and we can go up to 50k locals.Here are the prologues (with LLM annotations):
100 locals — frame 752 bytes, 0.18 pages, no probe 0: push %rbp 1: mov %rsp,%rbp 4: mov 0x8(%rdi),%r10 ; load stack limit from vmctx 8: mov 0x18(%r10),%r10 c: add $0x2f0,%r10 ; limit + frame size 13: cmp %rsp,%r10 16: ja 974 ; -> trap if we'd overflow 1c: sub $0x2f0,%rsp ; allocate frame 23: mov %rbx,0x2c0(%rsp) ; save 5 callee-saved registers ... 43: mov %r15,0x2e0(%rsp) 4b: test %edx,%edx 4d: mov %rdx,(%rsp) 51: je 93e ; the input-dependent skip over the locals block Sixteen instructions. The frame is a fraction of a page, so nothing is probed. 1000 locals — frame 7952 bytes, 1.94 pages, one unrolled probe c: add $0x1f10,%r10 ; same limit check, bigger frame 16: ja 6197 1c: sub $0x1000,%rsp ; <-- NEW: step down one 4 KiB page 23: movl $0x0,(%rsp) ; <-- touch it 2a: add $0x1000,%rsp ; <-- undo 31: sub $0x1f10,%rsp ; allocate frame 38: mov %rbx,0x1ee0(%rsp) ; still exactly 5 saves Three extra instructions, one of which writes to a page 4 KiB away. 1.34x slower than 100locals. 10000 locals — frame 79952 bytes, 19.5 pages, a probe loop c: cmp %rsp,%r10 ; <-- check #1: bare limit f: ja 3d247 15: add $0x13850,%r10 ; <-- check #2: limit + frame 1c: cmp %rsp,%r10 1f: ja 3d249 25: mov %rsp,%r11 28: sub $0x14000,%r11 ; r11 = target, 20 pages down 2f: sub $0x1000,%rsp ; loop: next page 36: movl $0x0,(%rsp) ; touch it 3d: cmp %rsp,%r11 40: jne 2f ; 20 iterations 46: add $0x14000,%rsp 4d: sub $0x13850,%rsp ; allocate frame 54: mov %rbx,0x13820(%rsp) ; still exactly 5 saves 31.93x slower than 100localsThis repro only works with
OptLevel::None, but I think I have in the meantime found an example where the locals calculation is too complex to optimize away - so the problem is present withOptLevel::Speedas well.The change as proposed in this PR may not be a fair way to charge fuel if the optimizer can remove the problem in most cases, so I am open to inputs and better ideas.
But if people depend on fuel to measure compute (be it for security purposes or other), then fuel should probably be charged conservatively. Wdyt?
locals1000.asm.txt
locals100.asm.txt
locals1000.wat.txt
locals100.wat.txt
michael-weigelt edited a comment on PR #14042:
I reproduced the problem like this:
- Wasmtime 47 with Cranelift and
OptLevel::None.- A function
gowith 100/1000/10000 locals, which returns immediately if its argument is 0, otherwise does some calculation with the locals.- A function
repeatwhich callsgomany times in a loop in order to amplify the overhead.- Measure the time to call
repeat. If the number or locals does not matter, then we should observe the same runtimes in the 100/1000/10000 modules. But that's not the case.Looking at the disassembly of the locals100 artifact (
objdump -p <serialized module>), we have
- a large block of locals calculations
- but just before, there is a
je 93ejump to the end of that block in case the argument is 0.- however, in the locals1000 case, there is a stack probe before that jump.
1c: sub $0x1000,%rsp 23: movl $0x0,(%rsp) 2a: add $0x1000,%rsp 31: sub $0x1f10,%rspand I think that must be the culprit of the slowdown. We dirty pages we never end up needing.
In the 10'000 locals case, it's a loop over 20 pages, and we can go up to 50k locals.Here are the prologues (with LLM annotations):
100 locals — frame 752 bytes, 0.18 pages, no probe 0: push %rbp 1: mov %rsp,%rbp 4: mov 0x8(%rdi),%r10 ; load stack limit from vmctx 8: mov 0x18(%r10),%r10 c: add $0x2f0,%r10 ; limit + frame size 13: cmp %rsp,%r10 16: ja 974 ; -> trap if we'd overflow 1c: sub $0x2f0,%rsp ; allocate frame 23: mov %rbx,0x2c0(%rsp) ; save 5 callee-saved registers ... 43: mov %r15,0x2e0(%rsp) 4b: test %edx,%edx 4d: mov %rdx,(%rsp) 51: je 93e ; the input-dependent skip over the locals block Sixteen instructions. The frame is a fraction of a page, so nothing is probed. 1000 locals — frame 7952 bytes, 1.94 pages, one unrolled probe c: add $0x1f10,%r10 ; same limit check, bigger frame 16: ja 6197 1c: sub $0x1000,%rsp ; <-- NEW: step down one 4 KiB page 23: movl $0x0,(%rsp) ; <-- touch it 2a: add $0x1000,%rsp ; <-- undo 31: sub $0x1f10,%rsp ; allocate frame 38: mov %rbx,0x1ee0(%rsp) ; still exactly 5 saves Three extra instructions, one of which writes to a page 4 KiB away. 1.34x slower than 100locals. 10000 locals — frame 79952 bytes, 19.5 pages, a probe loop c: cmp %rsp,%r10 ; <-- check #1: bare limit f: ja 3d247 15: add $0x13850,%r10 ; <-- check #2: limit + frame 1c: cmp %rsp,%r10 1f: ja 3d249 25: mov %rsp,%r11 28: sub $0x14000,%r11 ; r11 = target, 20 pages down 2f: sub $0x1000,%rsp ; loop: next page 36: movl $0x0,(%rsp) ; touch it 3d: cmp %rsp,%r11 40: jne 2f ; 20 iterations 46: add $0x14000,%rsp 4d: sub $0x13850,%rsp ; allocate frame 54: mov %rbx,0x13820(%rsp) ; still exactly 5 saves 31.93x slower than 100localsThis repro only works with
OptLevel::None, but I think I have in the meantime found an example where the locals calculation is too complex to optimize away - so the problem is present withOptLevel::Speedas well.The change as proposed in this PR may not be a fair way to charge fuel if the optimizer can remove the problem in most cases, so I am open to inputs and better ideas.
But if people depend on fuel to measure compute (be it for security purposes or other), then fuel should probably be charged conservatively. Wdyt?
locals1000.asm.txt
locals100.asm.txt
locals1000.wat.txt
locals100.wat.txt
michael-weigelt edited a comment on PR #14042:
I reproduced the problem like this:
- Wasmtime 47 with Cranelift and
OptLevel::None.- A function
gowith 100/1000/10000 locals, which returns immediately if its argument is 0, otherwise does some calculation with the locals.- A function
repeatwhich callsgomany times in a loop in order to amplify the overhead.- Measure the time to call
repeat. If the number or locals does not matter, then we should observe the same runtimes in the 100/1000/10000 modules. But that's not the case.Looking at the disassembly of the locals100 artifact (
objdump -p <serialized module>), we have
- a large block of locals calculations
- but just before, there is a
je 93ejump to the end of that block in case the argument is 0.- however, in the locals1000 case, there is a stack probe before that jump.
1c: sub $0x1000,%rsp 23: movl $0x0,(%rsp) 2a: add $0x1000,%rsp 31: sub $0x1f10,%rspand I think that must be the culprit of the slowdown. We dirty pages we never end up needing.
In the 10'000 locals case, it's a loop over 20 pages, and we can go up to 50k locals.Here are three versions of the code leading up to the conditional branching instruction (with LLM annotations):
100 locals — frame 752 bytes, 0.18 pages, no probe 0: push %rbp 1: mov %rsp,%rbp 4: mov 0x8(%rdi),%r10 ; load stack limit from vmctx 8: mov 0x18(%r10),%r10 c: add $0x2f0,%r10 ; limit + frame size 13: cmp %rsp,%r10 16: ja 974 ; -> trap if we'd overflow 1c: sub $0x2f0,%rsp ; allocate frame 23: mov %rbx,0x2c0(%rsp) ; save 5 callee-saved registers ... 43: mov %r15,0x2e0(%rsp) 4b: test %edx,%edx 4d: mov %rdx,(%rsp) 51: je 93e ; the input-dependent skip over the locals block Sixteen instructions. The frame is a fraction of a page, so nothing is probed. 1000 locals — frame 7952 bytes, 1.94 pages, one unrolled probe c: add $0x1f10,%r10 ; same limit check, bigger frame 16: ja 6197 1c: sub $0x1000,%rsp ; <-- NEW: step down one 4 KiB page 23: movl $0x0,(%rsp) ; <-- touch it 2a: add $0x1000,%rsp ; <-- undo 31: sub $0x1f10,%rsp ; allocate frame 38: mov %rbx,0x1ee0(%rsp) ; still exactly 5 saves Three extra instructions, one of which writes to a page 4 KiB away. 1.34x slower than 100locals. 10000 locals — frame 79952 bytes, 19.5 pages, a probe loop c: cmp %rsp,%r10 ; <-- check #1: bare limit f: ja 3d247 15: add $0x13850,%r10 ; <-- check #2: limit + frame 1c: cmp %rsp,%r10 1f: ja 3d249 25: mov %rsp,%r11 28: sub $0x14000,%r11 ; r11 = target, 20 pages down 2f: sub $0x1000,%rsp ; loop: next page 36: movl $0x0,(%rsp) ; touch it 3d: cmp %rsp,%r11 40: jne 2f ; 20 iterations 46: add $0x14000,%rsp 4d: sub $0x13850,%rsp ; allocate frame 54: mov %rbx,0x13820(%rsp) ; still exactly 5 saves 31.93x slower than 100localsThis repro only works with
OptLevel::None, but I think I have in the meantime found an example where the locals calculation is too complex to optimize away - so the problem is present withOptLevel::Speedas well.The change as proposed in this PR may not be a fair way to charge fuel if the optimizer can remove the problem in most cases, so I am open to inputs and better ideas.
But if people depend on fuel to measure compute (be it for security purposes or other), then fuel should probably be charged conservatively. Wdyt?
locals1000.asm.txt
locals100.asm.txt
locals1000.wat.txt
locals100.wat.txt
alexcrichton commented on PR #14042:
That seems compelling enough to me to warrant charging fuel here, but it also raises an interesting question for me. It seems like what this is more-or-less doing is charging for stack usage, and while the number of locals can be a proxy for stack usage it's not the only factor. For example another factor is the depth of the wasm operand stack at any one point in the function as well. Replacing usage of the locals in your example with:
(func $mk (result i32) (i32.const 0)) ;; call $mk call $mk ;; ... i32.add i32.add ;; ...shows a similar slowdown as you're seeing here. With 10k (dynamically dead) calls to
$mkthe program takes ~0.4s with10000000iterations, but with 5k dead calls to$mkit takes ~0.2s. In the limit fuel should be charged per-stack-frame-size, but that means fuel is now nondeterministic based on optimization level and across Wasmtime versions. One possibility would be to charge based on the operand stack depth, but that doesn't captureblocks I believe.Basically I think there's a lot of ways to increase the stack size of a program which can make it run a bit slower, and if that's problematic this probably wants a slightly different solution to handle all the cases of this happening instead of just one
michael-weigelt commented on PR #14042:
Yeah. I think given that this PR would overcharge most of the time and that addressing the problem in a more principled way needs a bit of thinking, I'll close this PR (unless we want to be very conservative until a better solution is found).
Will you make an issue where you give the broader picture, @alexcrichton ?
alexcrichton commented on PR #14042:
Sure, I wrote things up at https://github.com/bytecodealliance/wasmtime/issues/14075 if you want to double-check that too
:cross_mark: michael-weigelt closed without merge PR #14042.
michael-weigelt commented on PR #14042:
On hold until the bigger picture crystallizes at https://github.com/bytecodealliance/wasmtime/issues/14075
michael-weigelt edited a comment on PR #14042:
I reproduced the problem like this:
- Wasmtime 47 with Cranelift and
OptLevel::None.- A function
gowith 100/1000/10000 locals, which returns immediately if its argument is 0, otherwise does some calculation with the locals.- A function
repeatwhich callsgomany times in a loop in order to amplify the overhead.- Measure the time to call
repeat. If the number or locals does not matter, then we should observe the same runtimes in the 100/1000/10000 modules. But that's not the case.Looking at the disassembly of the locals100 artifact (
objdump -p <serialized module>), we have
- a large block of locals calculations
- but just before, there is a
je 93ejump to the end of that block in case the argument is 0.- however, in the locals1000 case, there is a stack probe before that jump.
1c: sub $0x1000,%rsp 23: movl $0x0,(%rsp) 2a: add $0x1000,%rsp 31: sub $0x1f10,%rspand I think that must be the culprit of the slowdown. We dirty pages we never end up needing.
In the 10'000 locals case, it's a loop over 20 pages, and we can go up to 50k locals.[
Edit:
Actually the page would be dirtied only the first timegois called, afterwards it's resident. So that's not it. But some perf stats indicate that it likely is some unlucky caching. Not sure! An LLM analysis which I can't assess myself claims:All twenty probe addresses sit exactly 4096 bytes apart. This L1d has 64 sets, so its set index is bits [11:6] of the address — which means the set index repeats every 4096 bytes. Addresses that differ by a multiple of 4096 have identical set index bits, so all twenty lines are competing for one single set, which has 8 ways. The other 63 sets sit completely idle.
-> Every probe is a cache miss and incurs an L2 roundtrip including write-back.
]Here are three versions of the code leading up to the conditional branching instruction (with LLM annotations):
100 locals — frame 752 bytes, 0.18 pages, no probe 0: push %rbp 1: mov %rsp,%rbp 4: mov 0x8(%rdi),%r10 ; load stack limit from vmctx 8: mov 0x18(%r10),%r10 c: add $0x2f0,%r10 ; limit + frame size 13: cmp %rsp,%r10 16: ja 974 ; -> trap if we'd overflow 1c: sub $0x2f0,%rsp ; allocate frame 23: mov %rbx,0x2c0(%rsp) ; save 5 callee-saved registers ... 43: mov %r15,0x2e0(%rsp) 4b: test %edx,%edx 4d: mov %rdx,(%rsp) 51: je 93e ; the input-dependent skip over the locals block Sixteen instructions. The frame is a fraction of a page, so nothing is probed. 1000 locals — frame 7952 bytes, 1.94 pages, one unrolled probe c: add $0x1f10,%r10 ; same limit check, bigger frame 16: ja 6197 1c: sub $0x1000,%rsp ; <-- NEW: step down one 4 KiB page 23: movl $0x0,(%rsp) ; <-- touch it 2a: add $0x1000,%rsp ; <-- undo 31: sub $0x1f10,%rsp ; allocate frame 38: mov %rbx,0x1ee0(%rsp) ; still exactly 5 saves Three extra instructions, one of which writes to a page 4 KiB away. 1.34x slower than 100locals. 10000 locals — frame 79952 bytes, 19.5 pages, a probe loop c: cmp %rsp,%r10 ; <-- check #1: bare limit f: ja 3d247 15: add $0x13850,%r10 ; <-- check #2: limit + frame 1c: cmp %rsp,%r10 1f: ja 3d249 25: mov %rsp,%r11 28: sub $0x14000,%r11 ; r11 = target, 20 pages down 2f: sub $0x1000,%rsp ; loop: next page 36: movl $0x0,(%rsp) ; touch it 3d: cmp %rsp,%r11 40: jne 2f ; 20 iterations 46: add $0x14000,%rsp 4d: sub $0x13850,%rsp ; allocate frame 54: mov %rbx,0x13820(%rsp) ; still exactly 5 saves 31.93x slower than 100localsThis repro only works with
OptLevel::None, but I think I have in the meantime found an example where the locals calculation is too complex to optimize away - so the problem is present withOptLevel::Speedas well.The change as proposed in this PR may not be a fair way to charge fuel if the optimizer can remove the problem in most cases, so I am open to inputs and better ideas.
But if people depend on fuel to measure compute (be it for security purposes or other), then fuel should probably be charged conservatively. Wdyt?
locals1000.asm.txt
locals100.asm.txt
locals1000.wat.txt
locals100.wat.txt
michael-weigelt commented on PR #14042:
For completeness and because you sort of asked, @cfallin, here is a Wasm module with 1000 locals which cannot be optimized away. And a script to generate similar modules, in case you want to confirm that the effect grows with increasing locals.
I wonder if the stack probing could be avoided. Perhaps that can already be achieved with the right config/optimization flags? Not that I could use them, since we unfortunately must run with
OptLevel::None. But others could.In any case I am curious what you think of all this. Is it all working as intended from your perspective?
gen_wat.py
no_opt_locals1000.wat.txt
(txt because github won't accept wat)
Last updated: Aug 30 2026 at 09:07 UTC