4 ms·

I am part of the structured concurrency crowd, and I agree with you. We (royal we) ignore it too much. I personally like some of the ideas, and I'm implementi

I am part of the structured concurrency crowd, and I agree with you. We (royal we) ignore it too much. I personally like some of the ideas, and I'm implementing those ideas in my structured concurrency language.

vanderZwan 4y ago
Hey I remember you, you wrote that thoughtful post on why you think Zig has function colors. Looking forward to see what you come up with, you clearly are putting a lot of thought into the subject!
- gavinhoward 4y ago
  Thank you! I'm glad someone liked that post. Yes, I've put a lot of thought in, and I'd like to hear your feedback. If you don't want to provide any, please don't waste your time reading the rest of this comment. The basic extension I would make to structured concurrency is explained in my comment at [1], but I'll make this comment self-contained. My design is predicated on the fact that the coolest thing about Rust is the borrow checker; it's a fantastic idea that eliminates many sources of bugs. But it's expensive, and structured concurrency can almost give it to us for "free." My design changes structured concurrency enough to give code a borrow checker for "free" or at least low cost at compile time and low cost at runtime. The change is this: change API's to "push" execution "down" the stack. (In this context, I'm thinking of the typical execution stack that grows downward in memory.) For example, say there's an API that creates an object A that your code wants to use. Usual code may just return A, and in that case, escape analysis would probably set A's lifetime to the lifetime of the caller, and this works. But in more complex cases, that may not be possible. However, if the API that creates A takes a function B to call with A instead, then A's lifetime could be tied directly to the function that created it, and the creator function can call B with a borrow of A. This is completely safe because B is guaranteed to return before A's lifetime ends. And if the language has some way to have closures, then B could be a closure with data or pointers to data higher in the stack, thus allowing code to access any data anywhere in the stack while running B with access to object A. This is still safe because B will definitely return before that other data goes out of scope. This is how pushing execution down the stack can easily ensure that lifetimes are automatically followed without needing a borrow checker. Honestly, I would suggest to the Rust people that they should adopt this style of programming; it would immensely useful in Rust. Anyway, then you add structured concurrency, which itself ties the lifetime of threads to the execution stack. This fact makes it easy to generalize the idea above to work with multiple threads. With structured concurrency, you can spawn a thread, and you know that any data higher on the stack than the threadset/nursery will always exist while that thread is live, no borrow checking necessary. So to extend my example, maybe the API creates multiple A objects and runs B on multiple threads, each one with a different instance of A. Even if B is a closure, with pointers to data higher in the stack, this is completely safe (assuming no mutation) because that data has a longer lifetime than all of the threads. As for mutation, I think Rust has the right idea with its Send/Sync model. To generalize mutation across threads, I would use something similar. For the possibility of mutation in the same thread, I would just add a layer of indirection; for example, I have strings, which are immutable, and string builders, which are mutable, but hidden behind an opaque pointer so that mutation is safe in single-thread code. Adding Send/Sync to this model will make mutability safe across threads too. That takes care of most cases, but there is still one case. Perhaps a thread creates data, and other threads want to use it. We have already taken care of the case where those other threads are descendants of the creator thread, but what if there is a thread C that wants to use that data that is not a descendant of the creator thread? Easy: create a thread that is a descendant of both the creator thread and thread C and push its execution down the stack like above. There would be an API to do this; thread C would basically send a request to the creator thread with a closure/function D and block waiting for the creator thread to say that D is done executing. The creator thread would create a new descendant thread E to run D. Once D was done, E would be joined, and the creator thread would send a message to thread C, which would then pick up execution where it left off. Of course, since the lifetime of thread E is smaller than the lifetime of both the creator thread and thread C, it is safe to use D, even though D might have references to data in both thread C and the creator thread. This would extend structured concurrency; instead of a thread tree, it would be a thread directed acyclic graph. All of this obviously requires RAII, but to make things work even better, forbid self-referential data structures (use a parent data structure that owns all items and have the items just refer to other items with indices or borrowed references, like in my implementation of linked lists [2] [3]). This ensures that reference cycles don't happen and eliminates that possible complexity. Also, it may be necessary to restrict thread spawning to the outermost scope of a threadset, just to ensure lifetimes are safe. If that's too onerous a restriction, then some lifetime analysis/borrow checker would be necessary, but I think it would be simpler than Rust's. However, this is not a free lunch; there are a few costs to this: 1. Extra memory for the extra thread stacks. This can be somewhat mitigated with compiler support for calculating the max stack size of each thread, but it can't be completely mitigated. 2. Extra memory for the extra thread data in the kernel. This cannot be mitigated. 3. Extra CPU time to start and stop extra threads. This cannot be mitigated, though there might be some performance improvements to be had on spawning threads. Nevertheless, there is still expensive context-switching that has to happen. 4. A paradigm shift about the same size as the one to adopt structured programming once `goto` was considered harmful. Of those four costs, I think number 4 is the biggest problem. The software industry is much larger, by several orders of magnitude, than it was when the structured programming shift took place, so there is greater momentum to overcome. And it would require rewriting a lot of libraries, or writing new ones. (This is one reason I am creating a new language: a new language has no technical debt in its standard library and can get the design right from the outset.) This is not a trivial cost, and it will only be done gradually, if at all. It will only happen if the industry decides that this is a good idea. The CPU cost is the other one that concerns me, but I think this could be mitigated a lot by having a system call to spawn several threads at once. The other mitigation would be to use thread pools: spawn threads when necessary, but when they finish, keep them around in a paused state and reuse them as much as possible. There would need to be a way to properly dispose of them in low-memory situations, but I think this could be done. And maybe it won't matter much if people only spawn threads to do heavy work, which would amortize the cost of spawning the threads. As for the memory costs, I think minimizing stacks for each thread is not going to matter much; stacks are already tiny compared to available memory. I don't think the extra kernel memory is going to be a problem either; it's a fixed cost and smaller than the cost of a thread stack. Anyway, that's my design so far. What do you think? [1]: https://lobste.rs/s/8msejg/notes_on_structured_concurrency_go#c_wkxbvb https://lobste.rs/s/8msejg/notes_on_structured_concurrency_g... [2]: https://git.yzena.com/Yzena/Yc/src/branch/master/src/container/list.h https://git.yzena.com/Yzena/Yc/src/branch/master/src/contain... [3]: https://git.yzena.com/Yzena/Yc/src/branch/master/src/container/list.c https://git.yzena.com/Yzena/Yc/src/branch/master/src/contain...
  - vanderZwan 4y ago
    One-sentence answer: sounds sensible, I think I'd need to play with it to get a good feeling for how it holds up in practice. (btw, since one of the comments of [1] mentions Erlang, have you seen Pony? It's actor based but has a lot of interesting recent compsci theory behind it: https://www.ponylang.io/discover/ https://www.ponylang.io/discover/. Who knows, there might be something interesting in there for you to steal)
    - ghoward 4y ago
      Thank you, and I agree; it needs to be played with. I've actually got a public "Show HN" scheduled for November 1, but it won't have any of the concurrency stuff then. (I don't have much time to work on it.) I hope concurrency won't be far behind. But the concurrency MVP is implemented in C, and the compiler/interpreter already uses it. It's promising. I've seen Pony before, but I haven't taken a deep look. I will now, thank you.

vanderZwan 4y ago

Hey I remember you, you wrote that thoughtful post on why you think Zig has function colors. Looking forward to see what you come up with, you clearly are putting a lot of thought into the subject!

gavinhoward 4y ago
Thank you! I'm glad someone liked that post. Yes, I've put a lot of thought in, and I'd like to hear your feedback. If you don't want to provide any, please don't waste your time reading the rest of this comment. The basic extension I would make to structured concurrency is explained in my comment at [1], but I'll make this comment self-contained. My design is predicated on the fact that the coolest thing about Rust is the borrow checker; it's a fantastic idea that eliminates many sources of bugs. But it's expensive, and structured concurrency can almost give it to us for "free." My design changes structured concurrency enough to give code a borrow checker for "free" or at least low cost at compile time and low cost at runtime. The change is this: change API's to "push" execution "down" the stack. (In this context, I'm thinking of the typical execution stack that grows downward in memory.) For example, say there's an API that creates an object A that your code wants to use. Usual code may just return A, and in that case, escape analysis would probably set A's lifetime to the lifetime of the caller, and this works. But in more complex cases, that may not be possible. However, if the API that creates A takes a function B to call with A instead, then A's lifetime could be tied directly to the function that created it, and the creator function can call B with a borrow of A. This is completely safe because B is guaranteed to return before A's lifetime ends. And if the language has some way to have closures, then B could be a closure with data or pointers to data higher in the stack, thus allowing code to access any data anywhere in the stack while running B with access to object A. This is still safe because B will definitely return before that other data goes out of scope. This is how pushing execution down the stack can easily ensure that lifetimes are automatically followed without needing a borrow checker. Honestly, I would suggest to the Rust people that they should adopt this style of programming; it would immensely useful in Rust. Anyway, then you add structured concurrency, which itself ties the lifetime of threads to the execution stack. This fact makes it easy to generalize the idea above to work with multiple threads. With structured concurrency, you can spawn a thread, and you know that any data higher on the stack than the threadset/nursery will always exist while that thread is live, no borrow checking necessary. So to extend my example, maybe the API creates multiple A objects and runs B on multiple threads, each one with a different instance of A. Even if B is a closure, with pointers to data higher in the stack, this is completely safe (assuming no mutation) because that data has a longer lifetime than all of the threads. As for mutation, I think Rust has the right idea with its Send/Sync model. To generalize mutation across threads, I would use something similar. For the possibility of mutation in the same thread, I would just add a layer of indirection; for example, I have strings, which are immutable, and string builders, which are mutable, but hidden behind an opaque pointer so that mutation is safe in single-thread code. Adding Send/Sync to this model will make mutability safe across threads too. That takes care of most cases, but there is still one case. Perhaps a thread creates data, and other threads want to use it. We have already taken care of the case where those other threads are descendants of the creator thread, but what if there is a thread C that wants to use that data that is not a descendant of the creator thread? Easy: create a thread that is a descendant of both the creator thread and thread C and push its execution down the stack like above. There would be an API to do this; thread C would basically send a request to the creator thread with a closure/function D and block waiting for the creator thread to say that D is done executing. The creator thread would create a new descendant thread E to run D. Once D was done, E would be joined, and the creator thread would send a message to thread C, which would then pick up execution where it left off. Of course, since the lifetime of thread E is smaller than the lifetime of both the creator thread and thread C, it is safe to use D, even though D might have references to data in both thread C and the creator thread. This would extend structured concurrency; instead of a thread tree, it would be a thread directed acyclic graph. All of this obviously requires RAII, but to make things work even better, forbid self-referential data structures (use a parent data structure that owns all items and have the items just refer to other items with indices or borrowed references, like in my implementation of linked lists [2] [3]). This ensures that reference cycles don't happen and eliminates that possible complexity. Also, it may be necessary to restrict thread spawning to the outermost scope of a threadset, just to ensure lifetimes are safe. If that's too onerous a restriction, then some lifetime analysis/borrow checker would be necessary, but I think it would be simpler than Rust's. However, this is not a free lunch; there are a few costs to this: 1. Extra memory for the extra thread stacks. This can be somewhat mitigated with compiler support for calculating the max stack size of each thread, but it can't be completely mitigated. 2. Extra memory for the extra thread data in the kernel. This cannot be mitigated. 3. Extra CPU time to start and stop extra threads. This cannot be mitigated, though there might be some performance improvements to be had on spawning threads. Nevertheless, there is still expensive context-switching that has to happen. 4. A paradigm shift about the same size as the one to adopt structured programming once `goto` was considered harmful. Of those four costs, I think number 4 is the biggest problem. The software industry is much larger, by several orders of magnitude, than it was when the structured programming shift took place, so there is greater momentum to overcome. And it would require rewriting a lot of libraries, or writing new ones. (This is one reason I am creating a new language: a new language has no technical debt in its standard library and can get the design right from the outset.) This is not a trivial cost, and it will only be done gradually, if at all. It will only happen if the industry decides that this is a good idea. The CPU cost is the other one that concerns me, but I think this could be mitigated a lot by having a system call to spawn several threads at once. The other mitigation would be to use thread pools: spawn threads when necessary, but when they finish, keep them around in a paused state and reuse them as much as possible. There would need to be a way to properly dispose of them in low-memory situations, but I think this could be done. And maybe it won't matter much if people only spawn threads to do heavy work, which would amortize the cost of spawning the threads. As for the memory costs, I think minimizing stacks for each thread is not going to matter much; stacks are already tiny compared to available memory. I don't think the extra kernel memory is going to be a problem either; it's a fixed cost and smaller than the cost of a thread stack. Anyway, that's my design so far. What do you think? [1]: https://lobste.rs/s/8msejg/notes_on_structured_concurrency_go#c_wkxbvb https://lobste.rs/s/8msejg/notes_on_structured_concurrency_g... [2]: https://git.yzena.com/Yzena/Yc/src/branch/master/src/container/list.h https://git.yzena.com/Yzena/Yc/src/branch/master/src/contain... [3]: https://git.yzena.com/Yzena/Yc/src/branch/master/src/container/list.c https://git.yzena.com/Yzena/Yc/src/branch/master/src/contain...
- vanderZwan 4y ago
  One-sentence answer: sounds sensible, I think I'd need to play with it to get a good feeling for how it holds up in practice. (btw, since one of the comments of [1] mentions Erlang, have you seen Pony? It's actor based but has a lot of interesting recent compsci theory behind it: https://www.ponylang.io/discover/ https://www.ponylang.io/discover/. Who knows, there might be something interesting in there for you to steal)
  - ghoward 4y ago
    Thank you, and I agree; it needs to be played with. I've actually got a public "Show HN" scheduled for November 1, but it won't have any of the concurrency stuff then. (I don't have much time to work on it.) I hope concurrency won't be far behind. But the concurrency MVP is implemented in C, and the compiler/interpreter already uses it. It's promising. I've seen Pony before, but I haven't taken a deep look. I will now, thank you.