Structured Concurrency(250bpm.com)

71 pointsby goranmoomin4 tahun yang lalu28 comments

https://250bpm.com/blog:71/

28 comments

ghoward4 tahun yang lalu

Just so you know, those of us who believe in structured concurrency often have slightly different meanings (which I believe will converge over time). My definition is at [0].

Beyond libdill, a rough version has now been implemented in C. (By me, sorry for shilling.)

An example of it in code is at [1].

Combine it with something I call a stackpool (basically a heap-allocated replacement for `alloca()`), and you can worry very little about managing memory manually, even in C.

In fact, both together can even serve the same purpose as Rust's borrow checker in C, if you are willing to write your code with a certain style.

Once I implement it as a first-class construct in a language (which I'm doing right now), it will look like this:

    threadset
    {
        // This starts a thread.
        go run_thread(arg1, arg2, etc);

        // The current thread does not leave
        // this block until all threads finish.
    }

I'm happy to answer questions.

[0]: https://gavinhoward.com/2019/12/structured-concurrency-defin...

[1]: https://git.yzena.com/Yzena/Yc/src/commit/30f4ae4e471cb5a500...

shoo4 tahun yang lalu

Are you aware of any case studies / examples of applying structured concurrency to a nontrivial codebase, which illustrates the benefits and drawbacks of the approach?

It'd be great to see before & after comparisons of taking a codebase written without structured concurrency, and porting it to use structured concurrency constructs, then seeing the differences in terms of runtime overhead, number of weird defects in one implementation but not in the other, lines of code spent, etc.

It'd also be interesting to know if all of the behaviour that was expressed in the original structureless concurrency code could be ported across to structured concurrency, or if it was still necessary to use structureless concurrency in a few places as the corresponding behaviour was not expressible.

Appreciate getting a good case study might be challenging --- I've been exposed to oldschool fortran numerical code written in a pre-structured-programming style with heavy use of global variables and gotos, trying to port that across to use structured constructs and local variables can be a large amount of effort.

ghoward4 tahun yang lalu

I do not know of any case studies or examples. However, my own code could be considered non-trivial because it's a full build system, or will be.

After writing only enough to get it bootstrapped, I'm now going through and redoing a lot to make it use all structured concurrency. Nevertheless, I don't think it's useful as an example, or rather, it won't be useful once the transformation is done.

> It'd also be interesting to know if all of the behaviour that was expressed in the original structureless concurrency code could be ported across to structured concurrency, or if it was still necessary to use structureless concurrency in a few places as the corresponding behaviour was not expressible.

I have a firm belief that the equivalence of structured and unstructured concurrency is exactly the same as the equivalence of structured and unstructured programming. It has been proven that you can express any possible unstructured program as a structured program. [0] (There is a bit of controversy over the original proof, but as far as I can tell, it has been proven as long as multi-level loop breaks/continues exist. See [1]. This is one reason why my language will have multi-level breaks/continues.)

I personally believe that such a proof exists for structured vs. unstructured concurrency and that it just needs to be found. Part of that belief is founded on [2], which does an excellent job of showing how the `go` statement is really a multi-branch `goto` statement. Perhaps I'll try to discover the proof and write it in a blog post.

(As a first dirty attempt, imagine all of the possible ways you could have more than one concurrent thread of execution. It should be simple to show how to turn every possible use of a `go`-like statement into an opening of a threadset that launches two tasks and waits on them before continuing. I'm not sure how any way of splitting a thread of execution into more than one thread of execution could not possibly be simulated with that. I could be wrong, though.)

Oh, and I just found out that Swift has structured concurrency! [3] This is great! And I think it is the first mainstream programming language with it. I think this is awesome because it means that structured concurrency is going mainstream. I hope it helps structured concurrency win against async/await, which I believe is a poor model.

So if you want a case study, I'd watch the Swift community; someone is going to rewrite their code using structured concurrency and write a blog post about it.

[0]: https://en.wikipedia.org/wiki/Structured_program_theorem

[1]: http://www.cs.cornell.edu/~kozen/Papers/BohmJacopini.pdf

[2]: https://vorpus.org/blog/notes-on-structured-concurrency-or-g...

[3]: https://github.com/apple/swift-evolution/blob/main/proposals...

zozbot2344 tahun yang lalu

I don't think this can be made to work. Concurrent systems are usually modeled using things like e.g. Petri nets that are not really "highly structured" by your definition. They may be more structured than a goto statement, but they aren't nearly as simple as the pure fork-join model that's often regarded as the typical case of "structured" concurrency.

Even the first diagram in OP has free interleaving of main() with quux() then foo() that's not well described by a "tree" of fork-join "tasks". (The second diagram is similarly complex in that foo() may want to transfer ownership of bar() to main(), in order to cleanly terminate and allow main() to proceed prior to waiting for bar().)

gavinhoward4 tahun yang lalu

You're probably right that my rough sketch for a proof wouldn't work.

That said, first of all, I don't think structured concurrency has to be a tree. I think it can be a DAG. See my comment at [0].

To solve the main(), quux(), foo() problem, just have main() open a threadset, spawn quux(), then call a function while the threadset is still open, and in that function, open another threadset that spawns foo().

The main(), foo(), bar() problem is a problem of cancellation. In that one, I believe that foo() should not return until bar() does. And if you need to cancel, use deadlines. That is why my code has cancellation built-in, with timers to implement deadlines. (Well, it's still alpha, but the rough shape of it is there.)

[0]: https://lobste.rs/s/8msejg/notes_on_structured_concurrency_g...

frankpf4 tahun yang lalu

Would you say that Java's Loom[1] matches your definition of structured concurrency?

[1]: https://www.javaadvent.com/2020/12/project-loom-and-structur...

gavinhoward4 tahun yang lalu

After reading that post, I'm pretty sure that Project Loom only fits my definition of structured concurrency if it's used solely with the try-with-resources construct.

However, if it is used that easy, then yes, absolutely, it fits my definition.

Using the Executor class as a threadset might also make it fit my definition, but I think my opinion of my definition has changed in the two years since I wrote it. I may have to revisit it because I think it may be useful to only consider concurrency that has the same block structure as structured programming does, whereas my current definition allows for passing a threadset around as a first-class value.

tl;dr: yes, it probably fits, but that might mean my definition need changing, except in the case of try-with-resources.

papercrane4 tahun yang lalu

The intent for the structured concurrency part of Loom is that you'd always use it with try-with-resources. The API is still developing so this link will break eventually, but the currently the basic API is in the StructuredTaskScope class.

https://download.java.net/java/early_access/loom/docs/api/jd...

CyberDildonics4 tahun yang lalu

In C++ this would just mean joining all the threads created in this block, which would be completely trivial. Is this really "structured concurrency" that warrants a Q and A?

ghoward4 tahun yang lalu

The Q&A is more for people that don't know about the concept of structured concurrency. Basically, people who have questions on TFA.

hinkley4 tahun yang lalu

This seems in some ways to be a special case of Communicating Sequential Processes.

In which case are we reinventing Erlang, badly (the new programmer's curse that is supplanting Lisp)?

ghoward4 tahun yang lalu

From what I understand, this would go further than Erlang, in that this can be a DAG of threads, not just a tree. I could be wrong, though; I'm not terribly familiar with Erlang anymore.

hinkley4 tahun yang lalu

Elixir is perpetually at the top of my TODO list, but I don't make it much past the videos (I had a plan involving rasPi clones, which ended up being a bridge too far).

I take your point about a tree versus a DAG. The supervisor tree is definitely a footgun of a sort and quite a few minutes of many videos is dedicated to ways to be successful with your supervisor tree. I suspect the tree was picked and stuck around so long in large part because it's the Simplest Thing That Could Work. But the BEAM has been tackling some headier topics of late. I'd be curious to see how much of this work could be grafted onto Erlang.

DAGs are great, but they do take a bit more vigilance. In a large project there is always the risk of adding a back link somewhere and upsetting the whole thing. The product I work on has one DAG, and in fact I just fixed a nasty memory leak in the cycle detector we added a couple years ago to surface these bugs a bit more gently.

Put another way: trees are statically stable, DAGS are dynamically stable. So it's down to whether what you accomplish with it is worth all of the effort. I predict if SC gets traction, that one of the videos will be about whether you actually need a DAG or whether your problem can be better represented as a tree. (Just because the feature exists, doesn't mean you need to use it on every project)

parksy4 tahun yang lalu

Is the basic concept of structured concurrency more about programming language design, or applicable to how a program is structured? I can do something like this in JS:

  async function doTasks(tasks = [])
    // Do some concurrent stuff:
    let results = await Promises.all(tasks.map((task) => new Promise((resolve, reject) => {
      workerpool.exec('mytask', [task])
        .then(function(result) {
            resolve(result)
        })
        .catch(function(err) {
            reject(err)
        })
    })))
    // Function pauses here until all tasks resolve.
    // do stuff with results
  }

The workerpool exists outside the scope of this function, is that kind of the crux of the distinction, or does it come down to how threads / workers are managed (by the language / first class constructs) that outlines the definition of structured concurrency?

The example above feels like a similar pattern to what I've seen in discussions of structured concurrency but as with most things I feel like there's an aha moment where I'll get what all the fuss is about.

cowboyd4 tahun yang lalu

I think the simplest expression of the idea of structured concurrency that I've come across is this: The scope of any concurrent process is the same as the lexical scope of the function that created it. This has profound implications.

Let's say, for example that I call `doTasks()` with 10 separate tasks. Before any of them can complete, one of them fails. What happens to the other 9? In your example, they are "leaked" because they will continue running, even though the scope that was awaiting their results in gone. Using a "worker pool" as in the example, it might go something like this:

  async function doTasks(tasks = []) {
    let workerpool = new WorkerPool();
    try {
      for (let task of tasks) {
        workerpool.exec("my task", task);
      }
      let results = await workerpool.all();
      // do stuff with results
    } finally {
      // no matter the outcome, nothing outlives this scope.
      await workerpool.destroy();
    }
  }

It should be noted that cancellation, i.e. the ability to "destroy" a concurrent task is a necessary primitive for structured concurrency. You can think of it as the equivalent of automatically releasing memory at the end of a lexical scope.

There is already an implementation of Structured Concurrency for JavasScript here https://frontside.com/effection

parksy4 tahun yang lalu

This helps complete the picture, thanks. In my current use-case I am batching up precomputing some expensive calculations in a genetic algorithm which all needs to be finished before I can run the competition. If one of the phenotypes throws an error Promises.all will catch it and my program will continue and I can handle the error, but as for my workers, yup they will leak - and I can't stop that using promises / async / await without leaking some internals of my workers with some shared semaphore or something, which is so 1990's. So yours this was a perfect example that helped bring it all together.

Funnily enough after this thread I did some digging around and came across effection as well, I'd never come across the term "structured concurrency" before but it feels like a natural next step on what I'm trying to accomplish, so I'll definitely be keen to see more development in this area and maybe some first class language constructs at some point.

Thanks for taking the time to give an example and explain the concept in relatable terms.

Matthias2474 tahun yang lalu

In my opinion it's mostly a pattern where you make sure that all sub-tasks are fully contained within child tasks and never outlive them. You can model that patten in most programming languages - e.g. as you do in JS.

However there can be environments which have structured concurrency baked in and thereby enforce the pattern. Kotlin coroutines are one example here.

parksy4 tahun yang lalu

So I guess my example resembles some form of structured concurrency but the threads are not encapsulated in the parent's closure. I still need to structure my promises and await / async logic to deal with the edge cases and make sure the program doesn't get stuck or leave threads hanging. That makes sense, thanks.

hinkley4 tahun yang lalu

So I glossed over this thread when I first saw it, and something drew me back.

My first thought when reading the description is that it reminds me of the 'with' semantics you see for resource management, where the API gives you an resource that lives for the lifetime of the closure, and then is destroyed or returned to a pool.

That's is a refinement of RAII, where the API may initialize the connection or may allocate an existing one to you that is no longer in use (serial acquisition).

This feels like a refinement of that for thread lifetimes, which are probably not a bad thing.

parksy4 tahun yang lalu

I think I'm getting the picture from this and other replies. To get close to a sense of structured concurrency I've had to lean on a plugin that handles worker threads (or would have to write one myself), and tie this in with async/await language features, and add some checks to handle thread lifetime and error states.

It would be really nice to have a first class language feature to wrap all this up, it sounds like that's what structured concurrency as a concept is aiming towards.

pizza4 tahun yang lalu

There's a proposal for a really nice form of structured concurrency in c++ https://ericniebler.com/2021/08/29/asynchronous-stacks-and-s...

muxator4 tahun yang lalu

I just wanted to mention that this is taken from the blog of Martin Sústrik, one of the original authors of ZeroMQ.

ibraheemdev4 tahun yang lalu

And possible related to the recent post of one of his projects, libmill: https://news.ycombinator.com/item?id=30699829, where libdill [0], "Structured Concurrency for C" was also mentioned.

[0]: http://libdill.org/

cowboyd4 tahun yang lalu

For those interested in exploring Structured Concurrency in JavaScript, there is https://frontside.com/effection

_ZeD_4 tahun yang lalu

Obligatory trio link https://trio.readthedocs.io/en/stable/

mns064 tahun yang lalu

Also worth being aware of AnyIO which implements structured concurrency on top of asyncio, and serves as an abstraction layer over trio/asyncio.

https://anyio.readthedocs.io/en/stable/

speps4 tahun yang lalu

(2016)

chrisbrandow4 tahun yang lalu

Glad you noted this. I was reading it thinking odd that it made no mention of Swift and it’s recent implementation.