4 ms·

None of the things you mention is necessary. In fact, we're adding user-mode threads (based on delimited continuations) to the JVM without doing any of them. Re

by pron 7y ago

None of the things you mention is necessary. In fact, we're adding user-mode threads (based on delimited continuations) to the JVM without doing any of them. Remember that every subroutine must already be compiled into a state machine or you wouldn't be able to return to it. I.e., every subroutine is already compiled in just the right way to be suspended already. The reason some languages run into problems are: 1. They may not have access to the representation the subroutines store their state, as it may be platform dependent (e.g. if you're targeting LLVM you may not have access to that representation). 2. They may not track their pointers, and so find it hard to move chunks of stack around if they have internal pointers into the stack. 3. They may want to enable some specific optimizations in the special (and rare, especially when IO is involved) case of a monomorphic calls to shallow coroutines. This requires that the representation of the subroutine's state be available as a high-level node for the compiler to change.

AaronFriel 7y ago
The JVM doesn't ever lose access to the bytecode, but Rust compiles down to machine code. The garbage collector and heap-oriented memory allocation without borrowing means you don't have nearly as much "stack" to worry about, and copying references is always OK. For a statically compiled language that produces machine code and prefers stack allocation and has strict constraints on copying references, it is not so easy.
- pron 7y ago
  Bytecode is irrelevant, but yeah, as I wrote, internal pointers into the stack do make moving stacks around difficult.
  - AaronFriel 7y ago
    It isn't irrelevant for point #2 above yours, which is that the JVM could rewrite and run/JIT two versions of every function. The JVM monomorphizes plenty already, does it not?
    - pron 7y ago
      It could compile two versions of every function on demand, but there's no need to (although it could be an implementation choice). AFAIK, every compiler in the world already compiles functions into state machines that are suitable for delimited continuations. What would the other version be for?
      - naasking 7y ago
        I'm not convinced they are suitable as-is in all compilers. Continuation capture can only be done at safe points similar to GC. The compiler and runtime need tight integration, which isn't a property of every compiler in the world. LLVM took a long time to integrate intrinsics to handle GC, for example.
        pron 7y ago
        "Physical" (i.e. non-inlined) subroutine calls are normally such safepoints (although I probably exaggerated when I said "every compiler in the world"). They need to be because a subroutine is a continuation. Upon return, it must be able to restore its state, otherwise it wouldn't be a subroutine. If you're doing any IO, there must such be such a physical call (and a safepoint) precisely where you need it -- at or before the actual IO.
        comex 7y ago
        It depends what you mean by "continuation capture". If you just want to suspend some code, subroutine calls will do – but so will any other instruction, as long as you save the values of all registers. That's what the kernel does, after all. Using the subroutine call boundary lets you save a bit of work by saving only the callee-save registers, but it doesn't make that much difference. The problem is that you still need a stack, which prevents coroutines from being lightweight enough. If you want to move the stack, like Go does... then just like with a GC, you need to track which registers and which stack offsets contain pointers at a given point in the program. That does require some sort of safepoint, which could be a subroutine call. But that's all irrelevant from Rust's perspective, because Rust's low-level pointer model is fundamentally incompatible with moving the stack. In Go, pointers into the stack are themselves only stored on the stack and in registers – never on the heap – so the runtime can easily find them all and adjust them. If you could store pointers into the stack onto the heap, it might still be possible to adjust them, albeit at higher cost, if you had a GC-managed heap where the runtime knows where all the pointers are. But Rust doesn't even have that. Tracking all the pointers in the heap is impossible for multiple reasons: - Rust programs don't have to use any particular runtime-provided heap; they can ask the OS for memory directly and store pointers there. - Pointers aren't necessarily stored in an easy-to-maintain way: e.g. Rust supports tagged unions, where the interpretation of one word in memory as either a pointer or integer depends on the value of another word. Oh, and Rust lets you convert pointers to integers (useful for hashing purposes), so moving pointers behind a program's back would have visible side effects in any case. So moving the stack is out. That leaves two possibilities: - Segmented stacks; - Calculating the required stack space statically. LLVM can generate code with segmented stack support [1], and Rust used to enable that option. It's not that bad, but it does require every function to begin by checking whether there's enough space left for its stack, and call a runtime function (__morestack) if not. That adds a measurable overhead to function calls. It also requires using a custom thread-local storage slot to track the current stack base, which means you can only call the function on threads where the runtime set up that slot, not any random C thread. That's a problem if you're writing a library meant to be used by C code, which evolved into a major use case for Rust. For these reasons, Rust nixed segmented stack support sometime before 1.0. Re-enabling it is one hypothetical reason why you might want two versions of each function. As for calculating the required stack space statically, that wouldn't require an alternate code generation mode. But as you were discussing in another subthread, the design of most compiler pipelines makes it very difficult to expose that information to the frontend. Even if that weren't a problem, merely making it theoretically possible to statically calculate stack usage requires imposing severe limits on the program. You can't make dynamic calls where you don't know the callee, and you can't use recursion at all (because then you might need infinite space). And if only a subset of code is async-compatible... then you end up with the equivalent of colored functions anyway. So even if LLVM's pipeline could be wrangled into doing what's necessary, it would only be a small improvement over the higher-level async/await implementation that Rust currently has. (As an alternative, you might be able to create a sort of hybrid mode where only dynamic and recursive calls use segmented stacks, but that would still require an alternate code generation mode.) The nail in the coffin is that Rust also targets WebAssembly, where you can't do any of the nice low-level things that you can on real machines. This has also been a blocker for guaranteed tail call elimination. I hate it. [1] https://llvm.org/docs/SegmentedStacks.html https://llvm.org/docs/SegmentedStacks.html
  - Rusky 7y ago
    Reusing the stack frame layout for a continuation state block is a really neat approach! Internal pointers into the stack aren't really the reason Rust can't take this approach either, though, unfortunately. Async frames are "pinned" once they start running anyway so the ecosystem is designed around not needing to move them. Async callee frames are, in a sense, contained in their caller's frames- this makes async recursion tricky, but in exchange each static call graph uses a single allocation. The real issue is basically naasking's #1- not that Rust loses its IR or that it's platform dependent, but that LLVM simply doesn't have the infrastructure to work with stack frames directly. A sufficiently motivated+funded team could add it but Rust doesn't have that luxury. In fact, this is also the reason that C++20 coroutines individually heap-allocate their frames. No compiler had the infrastructure or was able to put in the work in time. There are also some thorny problems around phase ordering here- stack frame layout typically isn't determined until very very late (to enable optimizations) but program-accessible types in both C++ and Rust need to know their sizes very very early. Java can sidestep this by being slightly higher level.
    - pron 7y ago
      Java sidesteps this because we generate concrete machine instructions and have control over the low-level platform-specific representation. In other words, because our backend is lower level, not higher level. But yeah, if you don't have access to the low level representation -- like Rust and Kotlin -- you don't really have a choice except to wait for your backend to give you that access. Sometimes waiting is a good approach, though. I'm not even sure you need control over the stack representation; it's sufficient to know what it is, which you could maybe do even on top of LLVM (but I don't know LLVM well enough to say for sure).
      - Rusky 7y ago
        Yeah, exactly. I believe you're correct that you just need to know what the stack looks like, not really change it much if at all. Any tweaks you may need to make are probably already available for things like split stacks or green threads. The problem is that LLVM doesn't even let you see the stack layout until very late, and then only as debug info. You could probably hack something on top but it would probably wind up looking a lot like C++20, with a lot of extra allocation, or like Rust, with all the stack frame layout optimization duplicated into the frontend.
naasking 7y ago
Delimited continuations are a more restricted form of my #3. The captured stack is smaller, but still much larger than what's strictly necessary, and in the pathological case, I still think it can be up to the full stack size. Unless you have some approach I haven't heard of, in which case, please provide a link!
- pron 7y ago
  Delimited continuations (I'm talking about one-shot, or non-reentrant continuations, AKA "stackful" coroutines) don't require more memory than async/await, as they capture the exact same state. That's the approach we're taking in Java, but I don't think it's particularly novel.
  - naasking 7y ago
    One shot delimited continuations capture strictly more state than a simple async/await implementation. The latter only captures bindings that are referenced after resumption, thus naturally implementing a sort of liveness analysis that discards unnecessary state. You could of course do the same thing during regular compilation, but it's not strictly necessary, and the interaction with GC means this state could potentially live much longer. That said, the extra object headers from heap-allocated activations will make up some of the difference.
    - pron 7y ago
      This liveness analysis isn't strictly necessary for async/await, either. You can do it in both cases or in none. In any event, it is not a matter of storing more stack, but of the level of optimization in the stack representation. Interaction with a GC brings its own complications as well as opportunities.
      - naasking 7y ago
        You're right that it's not strictly necessary, but as I said, it falls out naturally from computing the required continuations. This optimization doesn't necessarily happen naturally when compiling direct code, depending on your intermediate IR of course, ie. say, if your IR is already continuation-based. It'll be interesting to see how this plays out on the JVM though.
pcwalton 7y ago
We have that implemented in Rust too. It's a user-mode thread implementation called mioco. It's not used very much because the performance tends to be worse than 1:1 threads. This is a lesson that we all learned during the NPTL/NGPT era [1] and have subsequently forgotten and will have to relearn. [1]: https://akkadia.org/drepper/nptl-design.pdf https://akkadia.org/drepper/nptl-design.pdf
- pron 7y ago
  So it's better to bet on something whose lesson is yet to be learned? :) Anyway, I don't think anyone has forgotten those lessons, but they're not very relevant to modern managed runtimes. (also mioco seems to be single-threaded)
  - pcwalton 7y ago
    > So it's better to bet on something whose lesson is yet to be learned? :) Async I/O isn't anything new, and it's stood the test of time. Nginx isn't some new experimental technology. > Anyway, I don't think anyone has forgotten those lessons, but they're not very relevant to modern managed runtimes. (also mioco seems to be single-threaded) They're still very relevant. Linux can spawn hundreds of thousands of kernel threads. Anyway, we used to have an multithreaded M:N runtime in Rust, but it was removed because the performance was worse than 1:1 in practice. M:N was moved out of the standard library into the mioco library. Now it's unmaintained, because nobody actually wants M:N threads in Rust—an interesting outcome to be sure!
    - pron 7y ago
      > Async I/O isn't anything new, and it's stood the test of time. What do you mean? User-mode threads also use async I/O. They do just what async/await does, only without the syntax. I mean that async/await hasn't stood the test of time just yet. > Linux can spawn hundreds of thousands of kernel threads. Yeah, not very active ones, though. And their stacks are never really uncommitted. And the scheduler is badly optimized for many of the very uses you want in a server. On the other hand, you can spawn many millions of active fibers, schedule them how you like, and play with their state and its representation in many interesting ways (like moving a running fiber from one machine to another). > Now it's unmaintained, because nobody actually wants M:N threads in Rust—an interesting outcome to be sure! Just to make sure, when people say "M:N threads" they can mean a lot of very different things. In Java, they'll behave like async/await, only without the syntactic constructs. Stacks and stack frames are moved, can shrink and grow, can have various representations etc., and the scheduling is entirely pluggable. You can schedule the continuations manually, or in a scheduler of your choice, shared, or not, with ordinary tasks.

by pron 7y ago

AaronFriel 7y ago

The JVM doesn't ever lose access to the bytecode, but Rust compiles down to machine code. The garbage collector and heap-oriented memory allocation without borrowing means you don't have nearly as much "stack" to worry about, and copying references is always OK. For a statically compiled language that produces machine code and prefers stack allocation and has strict constraints on copying references, it is not so easy.

pron 7y ago
Bytecode is irrelevant, but yeah, as I wrote, internal pointers into the stack do make moving stacks around difficult.
- AaronFriel 7y ago
  It isn't irrelevant for point #2 above yours, which is that the JVM could rewrite and run/JIT two versions of every function. The JVM monomorphizes plenty already, does it not?
  - pron 7y ago
    It could compile two versions of every function on demand, but there's no need to (although it could be an implementation choice). AFAIK, every compiler in the world already compiles functions into state machines that are suitable for delimited continuations. What would the other version be for?
    - naasking 7y ago
      I'm not convinced they are suitable as-is in all compilers. Continuation capture can only be done at safe points similar to GC. The compiler and runtime need tight integration, which isn't a property of every compiler in the world. LLVM took a long time to integrate intrinsics to handle GC, for example.
      - pron 7y ago
        "Physical" (i.e. non-inlined) subroutine calls are normally such safepoints (although I probably exaggerated when I said "every compiler in the world"). They need to be because a subroutine is a continuation. Upon return, it must be able to restore its state, otherwise it wouldn't be a subroutine. If you're doing any IO, there must such be such a physical call (and a safepoint) precisely where you need it -- at or before the actual IO.
        comex 7y ago
        It depends what you mean by "continuation capture". If you just want to suspend some code, subroutine calls will do – but so will any other instruction, as long as you save the values of all registers. That's what the kernel does, after all. Using the subroutine call boundary lets you save a bit of work by saving only the callee-save registers, but it doesn't make that much difference. The problem is that you still need a stack, which prevents coroutines from being lightweight enough. If you want to move the stack, like Go does... then just like with a GC, you need to track which registers and which stack offsets contain pointers at a given point in the program. That does require some sort of safepoint, which could be a subroutine call. But that's all irrelevant from Rust's perspective, because Rust's low-level pointer model is fundamentally incompatible with moving the stack. In Go, pointers into the stack are themselves only stored on the stack and in registers – never on the heap – so the runtime can easily find them all and adjust them. If you could store pointers into the stack onto the heap, it might still be possible to adjust them, albeit at higher cost, if you had a GC-managed heap where the runtime knows where all the pointers are. But Rust doesn't even have that. Tracking all the pointers in the heap is impossible for multiple reasons: - Rust programs don't have to use any particular runtime-provided heap; they can ask the OS for memory directly and store pointers there. - Pointers aren't necessarily stored in an easy-to-maintain way: e.g. Rust supports tagged unions, where the interpretation of one word in memory as either a pointer or integer depends on the value of another word. Oh, and Rust lets you convert pointers to integers (useful for hashing purposes), so moving pointers behind a program's back would have visible side effects in any case. So moving the stack is out. That leaves two possibilities: - Segmented stacks; - Calculating the required stack space statically. LLVM can generate code with segmented stack support [1], and Rust used to enable that option. It's not that bad, but it does require every function to begin by checking whether there's enough space left for its stack, and call a runtime function (__morestack) if not. That adds a measurable overhead to function calls. It also requires using a custom thread-local storage slot to track the current stack base, which means you can only call the function on threads where the runtime set up that slot, not any random C thread. That's a problem if you're writing a library meant to be used by C code, which evolved into a major use case for Rust. For these reasons, Rust nixed segmented stack support sometime before 1.0. Re-enabling it is one hypothetical reason why you might want two versions of each function. As for calculating the required stack space statically, that wouldn't require an alternate code generation mode. But as you were discussing in another subthread, the design of most compiler pipelines makes it very difficult to expose that information to the frontend. Even if that weren't a problem, merely making it theoretically possible to statically calculate stack usage requires imposing severe limits on the program. You can't make dynamic calls where you don't know the callee, and you can't use recursion at all (because then you might need infinite space). And if only a subset of code is async-compatible... then you end up with the equivalent of colored functions anyway. So even if LLVM's pipeline could be wrangled into doing what's necessary, it would only be a small improvement over the higher-level async/await implementation that Rust currently has. (As an alternative, you might be able to create a sort of hybrid mode where only dynamic and recursive calls use segmented stacks, but that would still require an alternate code generation mode.) The nail in the coffin is that Rust also targets WebAssembly, where you can't do any of the nice low-level things that you can on real machines. This has also been a blocker for guaranteed tail call elimination. I hate it. [1] https://llvm.org/docs/SegmentedStacks.html https://llvm.org/docs/SegmentedStacks.html
- Rusky 7y ago
  Reusing the stack frame layout for a continuation state block is a really neat approach! Internal pointers into the stack aren't really the reason Rust can't take this approach either, though, unfortunately. Async frames are "pinned" once they start running anyway so the ecosystem is designed around not needing to move them. Async callee frames are, in a sense, contained in their caller's frames- this makes async recursion tricky, but in exchange each static call graph uses a single allocation. The real issue is basically naasking's #1- not that Rust loses its IR or that it's platform dependent, but that LLVM simply doesn't have the infrastructure to work with stack frames directly. A sufficiently motivated+funded team could add it but Rust doesn't have that luxury. In fact, this is also the reason that C++20 coroutines individually heap-allocate their frames. No compiler had the infrastructure or was able to put in the work in time. There are also some thorny problems around phase ordering here- stack frame layout typically isn't determined until very very late (to enable optimizations) but program-accessible types in both C++ and Rust need to know their sizes very very early. Java can sidestep this by being slightly higher level.
  - pron 7y ago
    Java sidesteps this because we generate concrete machine instructions and have control over the low-level platform-specific representation. In other words, because our backend is lower level, not higher level. But yeah, if you don't have access to the low level representation -- like Rust and Kotlin -- you don't really have a choice except to wait for your backend to give you that access. Sometimes waiting is a good approach, though. I'm not even sure you need control over the stack representation; it's sufficient to know what it is, which you could maybe do even on top of LLVM (but I don't know LLVM well enough to say for sure).
    - Rusky 7y ago
      Yeah, exactly. I believe you're correct that you just need to know what the stack looks like, not really change it much if at all. Any tweaks you may need to make are probably already available for things like split stacks or green threads. The problem is that LLVM doesn't even let you see the stack layout until very late, and then only as debug info. You could probably hack something on top but it would probably wind up looking a lot like C++20, with a lot of extra allocation, or like Rust, with all the stack frame layout optimization duplicated into the frontend.

naasking 7y ago

Delimited continuations are a more restricted form of my #3. The captured stack is smaller, but still much larger than what's strictly necessary, and in the pathological case, I still think it can be up to the full stack size. Unless you have some approach I haven't heard of, in which case, please provide a link!

pron 7y ago
Delimited continuations (I'm talking about one-shot, or non-reentrant continuations, AKA "stackful" coroutines) don't require more memory than async/await, as they capture the exact same state. That's the approach we're taking in Java, but I don't think it's particularly novel.
- naasking 7y ago
  One shot delimited continuations capture strictly more state than a simple async/await implementation. The latter only captures bindings that are referenced after resumption, thus naturally implementing a sort of liveness analysis that discards unnecessary state. You could of course do the same thing during regular compilation, but it's not strictly necessary, and the interaction with GC means this state could potentially live much longer. That said, the extra object headers from heap-allocated activations will make up some of the difference.
  - pron 7y ago
    This liveness analysis isn't strictly necessary for async/await, either. You can do it in both cases or in none. In any event, it is not a matter of storing more stack, but of the level of optimization in the stack representation. Interaction with a GC brings its own complications as well as opportunities.
    - naasking 7y ago
      You're right that it's not strictly necessary, but as I said, it falls out naturally from computing the required continuations. This optimization doesn't necessarily happen naturally when compiling direct code, depending on your intermediate IR of course, ie. say, if your IR is already continuation-based. It'll be interesting to see how this plays out on the JVM though.

pcwalton 7y ago

We have that implemented in Rust too. It's a user-mode thread implementation called mioco. It's not used very much because the performance tends to be worse than 1:1 threads. This is a lesson that we all learned during the NPTL/NGPT era [1] and have subsequently forgotten and will have to relearn. [1]: https://akkadia.org/drepper/nptl-design.pdf https://akkadia.org/drepper/nptl-design.pdf

pron 7y ago
So it's better to bet on something whose lesson is yet to be learned? :) Anyway, I don't think anyone has forgotten those lessons, but they're not very relevant to modern managed runtimes. (also mioco seems to be single-threaded)
- pcwalton 7y ago
  > So it's better to bet on something whose lesson is yet to be learned? :) Async I/O isn't anything new, and it's stood the test of time. Nginx isn't some new experimental technology. > Anyway, I don't think anyone has forgotten those lessons, but they're not very relevant to modern managed runtimes. (also mioco seems to be single-threaded) They're still very relevant. Linux can spawn hundreds of thousands of kernel threads. Anyway, we used to have an multithreaded M:N runtime in Rust, but it was removed because the performance was worse than 1:1 in practice. M:N was moved out of the standard library into the mioco library. Now it's unmaintained, because nobody actually wants M:N threads in Rust—an interesting outcome to be sure!
  - pron 7y ago
    > Async I/O isn't anything new, and it's stood the test of time. What do you mean? User-mode threads also use async I/O. They do just what async/await does, only without the syntax. I mean that async/await hasn't stood the test of time just yet. > Linux can spawn hundreds of thousands of kernel threads. Yeah, not very active ones, though. And their stacks are never really uncommitted. And the scheduler is badly optimized for many of the very uses you want in a server. On the other hand, you can spawn many millions of active fibers, schedule them how you like, and play with their state and its representation in many interesting ways (like moving a running fiber from one machine to another). > Now it's unmaintained, because nobody actually wants M:N threads in Rust—an interesting outcome to be sure! Just to make sure, when people say "M:N threads" they can mean a lot of very different things. In Java, they'll behave like async/await, only without the syntactic constructs. Stacks and stack frames are moved, can shrink and grow, can have various representations etc., and the scheduling is entirely pluggable. You can schedule the continuations manually, or in a scheduler of your choice, shared, or not, with ordinary tasks.