7 ms·

This looks like it's going to be a great language. Compiling to LLVM should mean that it does tall call optimization, which is great and also means that integra

This looks like it's going to be a great language. Compiling to LLVM should mean that it does tall call optimization, which is great and also means that integrating with C/C++ should be fairly easy. The only thing it's missing that I'd like to see is support for CPS conversion like streamlinejs does. Even if it supports growable stacks that start at 1KB, with thousands of threads CPS conversion is still more efficient. Having said that, seeing as they are writing browsers, not servers, I can see why it's not a priority to do this.

beagle3 15y ago
Can you explain how CPS solves the growable stack problem? I haven't heard of this before.
- ori_b 15y ago
  It essentially lets you turn your stack state into closures on the heap which are passed to tail recursive functions.
  - 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.
- DanWaterworth 15y ago
  The idea is that you have a small number of OS threads that have their own stacks and you cooperatively map all of the user-space greenlets onto these threads, but whilst the greenlets are waiting to run, instead of storing their continuation as their stack and registers, you store the state as a closure. There's an obvious trade-off between responsiveness and memory usage, but you can adjust this by changing the number of OS threads. So the stack frames aren't allocated on the heap.
  - beagle3 15y ago
    And where exactly are those closures allocated?
    - DanWaterworth 15y ago
      They would be allocated on the heap, so mapping a greenlet onto an OS thread is a fairly expensive operation. However, the greenlets are cooperatively rather than pre-emptively mapped, so this doesn't happen as frequently as you may imagine.
      - beagle3 15y ago
        > > > So the stack frames aren't allocated on the heap. > > So where exactly are the closures allocated ? > They would be allocated on the heap You're playing a weird game of semantics here. closures and stack frames are the same thing in this case. The fact that the "call stack" is implemented via a register called "the stack register" and uses a LIFO move-the-mark allocation scheme is an irrelevant implementation detail. Your assertion that CPS conversion is somehow more efficient than growable stacks is not supported by any of the arguments you presented.
        DanWaterworth 15y ago
        Closures and stack frames are definitely not the same thing. CPS conversion is used to create continuations; it's not necessary that the continuations are compiled naively using CPS.

beagle3 15y ago

Can you explain how CPS solves the growable stack problem? I haven't heard of this before.

ori_b 15y ago
It essentially lets you turn your stack state into closures on the heap which are passed to tail recursive functions.
- 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.
DanWaterworth 15y ago
The idea is that you have a small number of OS threads that have their own stacks and you cooperatively map all of the user-space greenlets onto these threads, but whilst the greenlets are waiting to run, instead of storing their continuation as their stack and registers, you store the state as a closure. There's an obvious trade-off between responsiveness and memory usage, but you can adjust this by changing the number of OS threads. So the stack frames aren't allocated on the heap.
- beagle3 15y ago
  And where exactly are those closures allocated?
  - DanWaterworth 15y ago
    They would be allocated on the heap, so mapping a greenlet onto an OS thread is a fairly expensive operation. However, the greenlets are cooperatively rather than pre-emptively mapped, so this doesn't happen as frequently as you may imagine.
    - beagle3 15y ago
      > > > So the stack frames aren't allocated on the heap. > > So where exactly are the closures allocated ? > They would be allocated on the heap You're playing a weird game of semantics here. closures and stack frames are the same thing in this case. The fact that the "call stack" is implemented via a register called "the stack register" and uses a LIFO move-the-mark allocation scheme is an irrelevant implementation detail. Your assertion that CPS conversion is somehow more efficient than growable stacks is not supported by any of the arguments you presented.
      - DanWaterworth 15y ago
        Closures and stack frames are definitely not the same thing. CPS conversion is used to create continuations; it's not necessary that the continuations are compiled naively using CPS.