6 ms·

Are libmill and Go's approach the same? I.e. Holding concurrent state in multiple stack frames? What causes that to have degraded performance? Is this new appr

Are libmill and Go's approach the same? I.e. Holding concurrent state in multiple stack frames? What causes that to have degraded performance? Is this new approach different because instead of stack frames you just have dynamically allocated callback state?

pcwalton 10y ago
> Are libmill and Go's approach the same? I.e. Holding concurrent state in multiple stack frames? What causes that to have degraded performance? In the M:N approach you have to allocate stack space for each goroutine that you spawn. This requires that you either know the size of the stack up front (generally not possible without being conservative and requesting a large allocation) or that you start small and grow (resulting in a lot of memory traffic and pauses in the growth case, and much harder to do in C). By contrast, with the zero-cost futures approach we statically know exactly how much per-goroutine size we will ever need, and we can allocate precisely that amount. Furthermore, we only save the data that's absolutely needed across blocking calls. This results in much smaller per-connection state, and as a result it's quicker to allocate. It's the difference between static and dynamic control flow. Full M:N requires us to give up static knowledge of what a goroutine will do and try to do the best we can at runtime. With futures, we have a lot more static knowledge, and as a result we can optimize more aggressively.
- mindslight 10y ago
  > This requires that you either know the size of the stack up front ... generally not possible without being conservative Well, you are writing the compiler. Sure you'd be up against the halting problem, but relatively few functions are (non-tail) recursive. Perhaps the unwieldiness of a large stack is better attributed to the feature of unbounded recursion (and FFI into "uncharted territory") than the feature of green threads. I appreciate that Rust has already been down the road of lightweight threads. This statement just struck me as an assumption that deserved to be questioned.
  - pcwalton 10y ago
    It would require higher order control flow analysis like k-CFA, which would certainly fail to produce a bounded stack size on any nontrivial program. The futures library is the control flow analysis. Because it uses the type system instead of higher order control flow analysis, it actually achieves precision.
    - mindslight 10y ago
      I was thinking of a much lighter analysis, based on some optional restrictions. If a function: - is not recursive - does not call function pointers (ie trait objects) - allocates only fixed-sized objects on the stack - only calls functions with known stack requirements then its stack requirement should be known, no? It feels like with these requirements, one can still write many programs (threads, really). And if one goes beyond the restrictions, then they just pay the cost of having to guess a large stack size. Stack size analysis would be helpful for other applications as well, like embedded platforms.
      - pcwalton 10y ago
        No program beyond the most trivial will meet these requirements. The moment you call any function indirectly you lose.
        mindslight 10y ago
        Yes, but indirectly means "&Fn", but not "&F where F: Fn". And a whole program doesn't need to conform, only individual threads. Presumably the ones you want to make a lot of. (And if a little dynamicism was required, its expense could be paid for at the use, by creating a fresh necessary-sized stack at that point. But I'm probably opening up old split-stack wounds, sorry)
        jroesch 10y ago
        The problem with an optimization like this is that the current approach always gives you a guarantee on runtime cost. Heuristic based optimizations make performance harder to ensure, not to mention recovering performance when you fall outside the valid subset much more difficult. You can obviously provide another static analysis to warn you about violations, but this seems is more complex, and less flexible then the current approach.
Matthias247 10y ago
libmill only uses a single kernel thread so it's a little bit simpler here than Go, but otherwise they should be comparable. Regarding stack vs. dynamically allocated state (in a future) I'm not convinced what's better. Yes, the allocated stack most likely has an overhead. But at least the data will be stored there in linear fashion and accessing the state will be super cheap once the stack is loaded. In case of futures that hold dynamically allocated data the state might be spread over much more memory locations, so it might be slower to access. I however haven't any more scientific data on this. In my real-world applications I'm getting about the same performance from a Go based and a boost asio (uses no futures but dynamically allocated callback closures for storing state) networking application. However the programming style is completely different.
- saynsedit 10y ago
  With Rust zero cost futures, only one memory allocation is done for the entire chain of futures. It's not doing an allocation for every callback. This makes it comparable to using a stack. In an M:N solution, the stack is usually (but not always) allocated similarly (e.g. using malloc).

pcwalton 10y ago

> Are libmill and Go's approach the same? I.e. Holding concurrent state in multiple stack frames? What causes that to have degraded performance? In the M:N approach you have to allocate stack space for each goroutine that you spawn. This requires that you either know the size of the stack up front (generally not possible without being conservative and requesting a large allocation) or that you start small and grow (resulting in a lot of memory traffic and pauses in the growth case, and much harder to do in C). By contrast, with the zero-cost futures approach we statically know exactly how much per-goroutine size we will ever need, and we can allocate precisely that amount. Furthermore, we only save the data that's absolutely needed across blocking calls. This results in much smaller per-connection state, and as a result it's quicker to allocate. It's the difference between static and dynamic control flow. Full M:N requires us to give up static knowledge of what a goroutine will do and try to do the best we can at runtime. With futures, we have a lot more static knowledge, and as a result we can optimize more aggressively.

mindslight 10y ago
> This requires that you either know the size of the stack up front ... generally not possible without being conservative Well, you are writing the compiler. Sure you'd be up against the halting problem, but relatively few functions are (non-tail) recursive. Perhaps the unwieldiness of a large stack is better attributed to the feature of unbounded recursion (and FFI into "uncharted territory") than the feature of green threads. I appreciate that Rust has already been down the road of lightweight threads. This statement just struck me as an assumption that deserved to be questioned.
- pcwalton 10y ago
  It would require higher order control flow analysis like k-CFA, which would certainly fail to produce a bounded stack size on any nontrivial program. The futures library is the control flow analysis. Because it uses the type system instead of higher order control flow analysis, it actually achieves precision.
  - mindslight 10y ago
    I was thinking of a much lighter analysis, based on some optional restrictions. If a function: - is not recursive - does not call function pointers (ie trait objects) - allocates only fixed-sized objects on the stack - only calls functions with known stack requirements then its stack requirement should be known, no? It feels like with these requirements, one can still write many programs (threads, really). And if one goes beyond the restrictions, then they just pay the cost of having to guess a large stack size. Stack size analysis would be helpful for other applications as well, like embedded platforms.
    - pcwalton 10y ago
      No program beyond the most trivial will meet these requirements. The moment you call any function indirectly you lose.
      - mindslight 10y ago
        Yes, but indirectly means "&Fn", but not "&F where F: Fn". And a whole program doesn't need to conform, only individual threads. Presumably the ones you want to make a lot of. (And if a little dynamicism was required, its expense could be paid for at the use, by creating a fresh necessary-sized stack at that point. But I'm probably opening up old split-stack wounds, sorry)
        jroesch 10y ago
        The problem with an optimization like this is that the current approach always gives you a guarantee on runtime cost. Heuristic based optimizations make performance harder to ensure, not to mention recovering performance when you fall outside the valid subset much more difficult. You can obviously provide another static analysis to warn you about violations, but this seems is more complex, and less flexible then the current approach.

Matthias247 10y ago

libmill only uses a single kernel thread so it's a little bit simpler here than Go, but otherwise they should be comparable. Regarding stack vs. dynamically allocated state (in a future) I'm not convinced what's better. Yes, the allocated stack most likely has an overhead. But at least the data will be stored there in linear fashion and accessing the state will be super cheap once the stack is loaded. In case of futures that hold dynamically allocated data the state might be spread over much more memory locations, so it might be slower to access. I however haven't any more scientific data on this. In my real-world applications I'm getting about the same performance from a Go based and a boost asio (uses no futures but dynamically allocated callback closures for storing state) networking application. However the programming style is completely different.

saynsedit 10y ago
With Rust zero cost futures, only one memory allocation is done for the entire chain of futures. It's not doing an allocation for every callback. This makes it comparable to using a stack. In an M:N solution, the stack is usually (but not always) allocated similarly (e.g. using malloc).