Structured concurrency and Lua
gist.github.com
gist.github.com
I'm getting a little annoyed by the structured concurrency crowd ignoring the synchronous concurrency paradigm as a historical precedent. It has existed since the 1980s and as far as I can tell there is a huge overlap in concepts. The only major difference I'm seeing is the addition of scoped asynchronous concurrency on top of synchronous concurrency (meaning single-threaded concurrency). That's significant for sure, but also not so much that it's cool to ignore the existing previous work.
Here's Céu, a language from 2011 with scoped synchronous concurrency:
input int KEY;
par/or do
every 1s do
_printf("Hello World!\n");
end
with
await KEY;
end
And hey, since we're talking about Lua, maybe we can acknowledge LuaGravity, which has existed since 2009?
Don't get me wrong though, I'm glad structured concurrency is catching on and that new work is being done in this area.
[0] https://en.wikipedia.org/wiki/Synchronous_programming_langua...
That said, from what I’ve seen Trio-style “structured concurrency” is somewhat less strict than the synchronous model: nurseries being tangible objects implies (1) you can spawn a dynamically-specified amount of cooperative threads, as you can just tell the nursery to spawn things in a loop; (2) you are not limited to strict nesting, as an ancestor thread can pass you a nursery closer to the root if it wishes.
The result of the second point is that you can maintain a tree of responsibility for e.g. error propagation without having a stack discipline where a parent thread’s dynamic extent must encompass all of its children’s (though there must be an ancestor with such a property). Yes, that means you’re free to have a single catastrophically-crashing root nursery where everybody spawns whatever they want, but you’re also free not to (and in fact there’s a sort of capability discipline for that, to the extent that the host language encapsulates things).
http://ceu-lang.org/publications.html
From the references of those papers it should be easy to find others, right?
And yes, you're absolutely right that the synchronous model is more restrictive - most synchronous languages follow the GALS principle: "globally asynchronous, locally synchronous". One benefit of the synchronous model is that it can essentially be compiled to a finite state machine with a memory overhead of mere bytes per "trail" (the synchronous analogue of a thread - the code snipped above has one synchronous "main" trail that splits into two synchronous trails in the "par/or" section).
The focus on this makes sense historically, since many synchronous languages were originally designed to target hard real-time embedded systems, where available memory is small, computational tasks are usually not very heavy, and the "asynchronous" part is interacting with the real world.
But that also suggests that synchronous and asynchronous concurrency could complement each other with the right language design.
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.
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_g...
[2]: https://git.yzena.com/Yzena/Yc/src/branch/master/src/contain...
[3]: https://git.yzena.com/Yzena/Yc/src/branch/master/src/contain...
(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/. Who knows, there might be something interesting in there for you to steal)
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.
Edit: Maybe Erlang process trees are structured by default? It's been a while so I don't remember.
Even Python's Trio (which asserts that it is structured concurrency) uses await. But even Ada didn't use `await` (most languages didn't) and has had something very close to structured concurrency since 1983 (first published spec).
https://learn.adacore.com/courses/intro-to-ada/chapters/task...
One of the important parts of structured concurrency is that if you have something like this:
a
spawn(b)
spawn(c)
I was not-quite-intentionally using a broader notion of structured concurrency, including not only the initial concept (tie task hierarchy to code structure, propagate errors up the call + task stack), but also critical pieces that are built on top of that, notably cancel/timeout scopes [1]. I don't think these pieces had been assembled to form something powerful enough to make concurrency manageable, until about the time of Nathaniel J. Smith's articles and Python Trio.
I'm revising the text slightly, and adding a footnote:
> It achieves this in ways that seem subtle to us-- clearly so, since its utility didn't reach critical mass until around 2018†
> † While it's argued that the core concept of structured concurrency has existed in some libraries and languages prior to the recent boom, these lacked significant parts of the story for making concurrency manageable. One is powerful, ergonomic control of timeouts and cancellation-- itself dependent on structured concurrency. Another is striving for a program that follows structured concurrency as a whole, including direct and transient dependencies. Nathaniel J. Smith was first to piece this all together, with a set of articles, and corresponding Python Trio concurrency library.
Though I suspect this will welcome more controversy ;)
[1] https://vorpus.org/blog/timeouts-and-cancellation-for-humans...
To-be-closed variables were recently introduced in Lua 5.4. Lua runs a destructor method when these variables go out of scope, like the RAII pattern in c++.
Coroutines have been in Lua for quite a while now. They allow cooperative concurrency (as opposed to preemptive concurrency a-la threads). It works similar to async generators as found in Python, C#, etc, except that Lua coroutines are stackful. You can yield inside an inner function and it'll pause the whole call stack. In the article, the yield is inside the async_sleep function. When you call a function that yields, you don't need to explicitly mark that with an "await".
Coroutines give you an easy way to manage cancellation. Essentially, any yield back to the scheduler is an opportunity to inject a cancel into the task. The code run within the task doesn't need to do anything special (beyond not starving the scheduler).
I use Lua a lot, but the global interpreter lock or lua_lock/lua_unlock implementation detail is one I don't see people talk too much about.
It's particularly frustrating when you want to do something advanced, like pull in an FFI for Lua, but also implement GIL behavior.
I haven't ever seen someone implement this correctly. I think it should be easy in theory, but I haven't given it a go in a while.
The current state of things is, you can use LuaJIT and accept no thread safety, or use PUC-Rio Lua with a custom lua_open/lua_lock implementation and use the FFI library separately. I haven't actually seen anyone do the latter. So in the field, it's all an untested concept, I think.
Maybe someone out there is doing this today and not talking about it. But there's no open source solution. Lua Lanes doesn't address this concern, and stylistic adaptions of cooperative multitasking don't either.
I realize it's technically a different topic, but it's basically the same area of concern.
Except, well, I find there to be fewer practical use cases for cooperative multitasking versus preemptive.