Structured Concurrency

by pcr910303 • 4 years ago

71 28 4 years ago

ghoward6• 4 years ago

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...

shoo• 4 years ago

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.

ghoward6• 4 years ago

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...

frankpf• 4 years ago

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...

ghoward6• 4 years ago

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.

CyberDildonics• 4 years ago

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?

ghoward6• 4 years ago

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

hinkley3• 4 years ago

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)?

ghoward6• 4 years ago

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.

speps• 4 years ago

(2016)

chrisbrandow• 4 years ago

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

muxator• 4 years ago

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

ibraheemdev• 4 years ago

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/

_ZeD_• 4 years ago

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

mns06• 4 years ago

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/

pizza• 4 years ago

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

parksy4• 4 years ago

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.

Matthias247• 4 years ago

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• 4 years ago

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.

cowboyd2• 4 years ago

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• 4 years ago

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.

hinkley3• 4 years ago

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• 4 years ago

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.

cowboyd2• 4 years ago

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

Structured Concurrency

Related Stories