3 ms·

It essentially lets you turn your stack state into closures on the heap which are passed to tail recursive functions.

by ori_b 15y ago

beagle3 15y ago
but how is that related to CPS? (or closures for that matter?) If you're allocating the stack frame on the heap, you can just replace the prologue (e.g. x86 intel syntax, cdecl calling convention) sub esp, LOCAL_SPACE_NEEDED with push LOCAL_SPACE_NEEDED push ARG_SIZE_TO_COPY call allocate_frame (where allocate_frame allocates enough space for storing link to previous stack frame, all args and all locals; then, it copies all arguments, return address and stack pointer, switches stacks to the new stacks and returns from the call) You can modify the return to call "deallocate_frame" (which would switch stacks back before returning), or you can just make sure the return address on the new stack points to "deallocate_frame_and_return", and use a regular return in place. [Actually, come to think of it, it's an excellent idea for a stack protection system that can be turned off for speed - the call to "allocate_frame" could be configured at runtime to patch its caller to just do "sub esp, LOCAL_SPACE_NEEDED" for maximum speed. Or it could just check stack overflow; or it could allocate frames on heap for better memory use; and it could mprotect/virtualprotect the edges of this frame for protection]
- ori_b 15y ago
  That's another option for doing it. However, writing in CPS implies that your calls are all tail calls, and they all take a continuation closure as an argument.
  - beagle3 15y ago
    I know what CPS is. But Dan states that "CPS is more efficient than growable stacks", and I can't see how CPS plays a nontrivial part in the stack size optimization.
pcwalton 15y ago
Stack allocation for call frames is a very important feature of Rust. SML/NJ does heap allocation for all frames and its performance suffers as a result (they have to invest very heavily in a good generational garbage collector, because the nursery fills up very quickly with stack frames). Graydon decided early on that in order to be competitive with C++ we would need first-class stack allocation, and I agree.

It essentially lets you turn your stack state into closures on the heap which are passed to tail recursive functions.

by ori_b 15y ago

It essentially lets you turn your stack state into closures on the heap which are passed to tail recursive functions.

but how is that related to CPS? (or closures for that matter?) If you're allocating the stack frame on the heap, you can just replace the prologue (e.g. x86 intel syntax, cdecl calling convention) sub esp, LOCAL_SPACE_NEEDED with push LOCAL_SPACE_NEEDED push ARG_SIZE_TO_COPY call allocate_frame (where allocate_frame allocates enough space for storing link to previous stack frame, all args and all locals; then, it copies all arguments, return address and stack pointer, switches stacks to the new stacks and returns from the call) You can modify the return to call "deallocate_frame" (which would switch stacks back before returning), or you can just make sure the return address on the new stack points to "deallocate_frame_and_return", and use a regular return in place. [Actually, come to think of it, it's an excellent idea for a stack protection system that can be turned off for speed - the call to "allocate_frame" could be configured at runtime to patch its caller to just do "sub esp, LOCAL_SPACE_NEEDED" for maximum speed. Or it could just check stack overflow; or it could allocate frames on heap for better memory use; and it could mprotect/virtualprotect the edges of this frame for protection]

ori_b 15y ago
That's another option for doing it. However, writing in CPS implies that your calls are all tail calls, and they all take a continuation closure as an argument.
- beagle3 15y ago
  I know what CPS is. But Dan states that "CPS is more efficient than growable stacks", and I can't see how CPS plays a nontrivial part in the stack size optimization.

pcwalton 15y ago

Stack allocation for call frames is a very important feature of Rust. SML/NJ does heap allocation for all frames and its performance suffers as a result (they have to invest very heavily in a good generational garbage collector, because the nursery fills up very quickly with stack frames). Graydon decided early on that in order to be competitive with C++ we would need first-class stack allocation, and I agree.