3 ms·

Or even better yet, use a language with a sensible SSA implementation that can identify local only variables and allocate them on the stack (like golang).

eru 5y ago
That technique is useful _and_ independent of what I suggested. Ie you can do it whether you have garbage collection or not. Though it's less important on languages with compacting garbage collectors, because there allocation can be just a pointer bump, which is pretty similar to what you do for stack allocation. See also this Scheme implementation which allocates everything on the C stack: > Previous Schemes for implementing full tail-recursion when compiling into C have required some form of "trampoline" to pop the stack. We propose solving the tail-recursion problem in the same manner as Standard ML of New Jersey, by allocating all frames in the (garbage-collected) heap. The Scheme program is translated into continuation-passing style, so the target C functions never return. The C stack pointer then becomes the allocation pointer for a Cheney-style copying garbage collection scheme. Our Scheme can use C function calls, C arguments, C variable-arity functions, and separate compilation without requiring complex block-compilation of entire programs. Introduction IEEE Scheme [IEEE90] requires that all functions be properly tail-recursive, in order that tail-recursive programs not require an unbounded amount of stack space. Several Scheme compilers have targeted the C language [Bartlett89], because C is an efficient systems programming language which is available on nearly ev... http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.54.7143 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.54.7... Do keep in mind that some languages like Scheme (because of call/cc) and Haskell (because of laziness) in general don't have a single stack. See eg https://en.wikipedia.org/wiki/Parent_pointer_tree https://en.wikipedia.org/wiki/Parent_pointer_tree for what Scheme needs to do. Of course, allocation of variables with hierarchically nested lifetimes (ie stack allocation) is still an important and common special case that your compiler/interpreter should probably recognize and handle well. Escape analysis is a well studied field after all. https://en.wikipedia.org/wiki/Escape_analysis https://en.wikipedia.org/wiki/Escape_analysis

eru 5y ago

That technique is useful _and_ independent of what I suggested. Ie you can do it whether you have garbage collection or not. Though it's less important on languages with compacting garbage collectors, because there allocation can be just a pointer bump, which is pretty similar to what you do for stack allocation. See also this Scheme implementation which allocates everything on the C stack: > Previous Schemes for implementing full tail-recursion when compiling into C have required some form of "trampoline" to pop the stack. We propose solving the tail-recursion problem in the same manner as Standard ML of New Jersey, by allocating all frames in the (garbage-collected) heap. The Scheme program is translated into continuation-passing style, so the target C functions never return. The C stack pointer then becomes the allocation pointer for a Cheney-style copying garbage collection scheme. Our Scheme can use C function calls, C arguments, C variable-arity functions, and separate compilation without requiring complex block-compilation of entire programs. Introduction IEEE Scheme [IEEE90] requires that all functions be properly tail-recursive, in order that tail-recursive programs not require an unbounded amount of stack space. Several Scheme compilers have targeted the C language [Bartlett89], because C is an efficient systems programming language which is available on nearly ev... http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.54.7143 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.54.7... Do keep in mind that some languages like Scheme (because of call/cc) and Haskell (because of laziness) in general don't have a single stack. See eg https://en.wikipedia.org/wiki/Parent_pointer_tree https://en.wikipedia.org/wiki/Parent_pointer_tree for what Scheme needs to do. Of course, allocation of variables with hierarchically nested lifetimes (ie stack allocation) is still an important and common special case that your compiler/interpreter should probably recognize and handle well. Escape analysis is a well studied field after all. https://en.wikipedia.org/wiki/Escape_analysis https://en.wikipedia.org/wiki/Escape_analysis