Robin Freyler (Nov 21 2024 at 15:11): Robin Freyler (Nov 21 2024 at 15:11):In Wasmi I was experimenting with a new macro-op fusion of call instructions in tail position.
While this optimization is semantics preserving the Wasm spec testsuite has some exhaustion checks which started to fail and state the following:
;; Stack exhaustion
;; Implementations are required to have every call consume some abstract
;; resource towards exhausting some abstract finite limit, such that
;; infinitely recursive test cases reliably trap in finite time. This is
;; because otherwise applications could come to depend on it on those
;; implementations and be incompatible with implementations that don't do
;; it (or don't do it under the same circumstances).
With fuel consumption enabled we still exhaust some abstract resources even with this tail call optimization enabled.
Thus I conclude that optimizations like this are only possible when fuel consumption is enabled. I wondered: does Wasmtime/Cranelift already apply this optimization conditionally? Would it be a good idea? Why? Why not?
Chris Fallin (Nov 21 2024 at 16:43):The way I read specification is that it must be a finite resource that tracks call depth -- so that recursing too deeply traps -- and one can't "reload" the resource. Fuel on the other hand is meant to be a metering mechanism that one uses to, say, pause execution every so often; it's underneath the level of Wasm semantics.
Explored with a particular example: if we rely only on fuel to limit us in this sense, then both a regular infinite loop ((loop (br 0))) and a tail-recursive loop should fail in the same way; but what the specification above is trying to say (the spirit of its intent I think) is that regular infinite loops must be allowed but tail-recursive loops must not
Robin Freyler (Nov 22 2024 at 15:15):To me there is no statement of relation between infinite loops and infinite recursion from the above sentence. It simply states that every call has to consume some abstract finite resource which to me is given if fuel metering is enabled. Therefore I assumed that with fuel metering enabled an optimization like this should be fine. If fuel metering is disabled this optimization would not be applied and thus the max (call) stack depth acts as this finite abstract resource that is consumed for each function call.
Chris Fallin (Nov 22 2024 at 16:27):OK. I think that's a mis-reading, in context. I'm going from this:
;; This is
;; because otherwise applications could come to depend on it on those
;; implementations and be incompatible with implementations that don't do
;; it (or don't do it under the same circumstances).
as I mentioned, fuel is often used in a way that lets one periodically interrupt; that wouldn't prevent a producer from using tail-recursion to implement iteration. The intent here seems to me to be to push iteration toward intra-function loops rather than tail recursion, for community-dynamics reasons.
If you disagree I'd recommend filing an issue on the tail-calls repo and seeing if we can get a canonical answer...
Last updated: Nov 22 2024 at 17:03 UTC