Concurrency model

[kyouko-taiga]

Val must offer composable concurrency primitives that can be used to build generic concurrent programs.

Usage example

This document is inspired the senders/receiver model proposed for C++.

public fun main() {
  // Creates a computation plan that consumes an integer and increments it.
  var n = 1
  let plan = fun[var n]() { n + 1 }

  // Schedules the plan for execution, creating a computation.
  var answer = spawn plan

  // Executes some code concurrently in this thread.
  print("The answer is ", terminator: "")

  // Attaches work to a running computation.
  &answer.map(fun(n) { n * 2 })

  // Blocks this thread until the computation terminates.
  n = answer.sync_wait()
  print(n)
}

In this example, plan denotes a computation plan and represents work that has not been scheduled for execution yet.
A computation plan is typically a lambda [E] () fx -> T, where T denotes the value that the computation produces.
The environment E of a computation plan must conform to Sinkable.
Once Val will support exceptions, fx may contain throws.

spawn plan consumes plan and schedules its execution, resulting in a computation answer.
A computation represents work that may be in either of two states:

• running: the computation is computing its result.
• done: the computation completed and its result can be consumed.

answer.map attaches additional work to a computation.
map accepts a closure that receives the result of the computation as an argument and describes how that value is transformed.

[Note: a computation Async<E, T, fx> is a monad for which the method map preserves the functor laws. map is not the monadic bind operator.]

answer.sync_wait() suspends the current thread, waiting for answer to terminate.
The result of the computation is consumed and used to (re)initialize n.

Detailed design

Computations

A computation is described by a type with the following API:

/// An asynchronous computation.
public type Async<Environment: Sinkable, Value, fx: effect> {

  /// The work executed by `self`.
  public private(set) var work: [Environment] () fx -> Value

  /// Detaches `self`, allowing execution to continue independently.
  ///
  /// - Note: A still running detached computation is automatically terminated if `main` exits.
  public fun detach() sink

}

extension Async where fx: throws {

  /// Requests `self` to cancel.
  public fun cancel() inout

}

[Note: Async.cancel requires exception support.]

Receivers

A receiver represents the continuation of a computation by "receiving" its value or handling errors or cancellation.
A receiver is a type that conforms to the following trait:

/// A type that describes a computation receiver.
public trait Receiver {

  /// The type of the value expected to be received.
  type Value

  /// The result of `self`.
  type Result

  /// Receives a computation.
  fun receive<E, fx: effect>(_ computation: sink Async<E, Value, fx>) throws -> Result

}

Standard receivers

The standard library provides a collection of general purpose receivers that can be used to compose computations.

SyncWait

SyncWait is a receiver that suspends the current thread and waits for a computation to terminate and consumes its value or errors.

public type SyncWait<Value> {

  public typealias Result = Value

  public fun receive<E, fx: effect>(_ computation: sink Async<E, Value, fx>) throws -> Result {
    // Note: naive implementation using a Java-like wait/notify approach.
    unsafe computation._wait()
    return unsafe computation._consume()
  }

}

extension Async {

  /// Suspends the current thread until `self` either produces a value or an error.
  public fun sync_wait() fx & sink -> Value {
    SyncWait().receive(self)
  }

}

Bind

Bind implements the monadic bind operator of a computation.

public type Bind<A, E: Sinkable, B, fx: effect> {

  public typealias Result = Async<E, B, fx>

  public var transform: [E] (A) fx -> Async<some Sinkable, B, fx>

  public fun receive<Ea, fxa: effect>(_ computation: sink Async<Ea, A, fxa>) fx & throws -> Result {
    &transform(computation.sync_wait())
  }

}

extension Async {

  public fun bind<Eb: Sinkable, B, fxb: effect>(_ transform: sink (Value) fx -> Async<Eb, B, fxb>) {
    Bind(transform: transform).receive(self)
  }

}

Alternatives considered

Treating computations as projections of their work

The current design requires the environment of a computation plan to conform to Sinkable, meaning that a plan cannot have let or inout captures.
Should that be possible, a computation should be a projection of its work, which makes it unsinkable and generally impedes on the ability to use linearity.

The spawn keyword

An earlier design used async to instead of spawn to create computations.
Discussions with practitioners from other communities suggest that the keyword async conveys a different meaning.
In many programming languages, async is a modifier indicating that a particular function is asynchronous and has a different semantics.

[dabrahams]

I'm not exactly sure what the opening example is supposed to demonstrate, but I don't like (and maybe those with more experience in this area can correct me) is that it seems to be an example of things we don't want to happen (often):

1. We are dynamically attaching statically known work to an already-running computation, which costs synchronization.
2. We are blocking the thread to wait for results.

[kyouko-taiga]

Ah, Lucian expressed the same concerns about dynamically attaching work 😅

The example tried to demonstrate that it should be possible to do that when needed, even if in that particular case it would have been best not to use that approach. If we must support that use case, then synchronization is necessary (although it doesn't have to block threads, we could use green threads instead).

If we can know the entire concurrent work plan statically, then we can most likely define a DSL over composition primitives. For example:

// Rolls a 6 sided dice and returns its result.
fun roll() -> Int { .random(in_range: 1 ... 6) }

public fun main() {
  // Throw two dices concurrently and sum their result.
  let sum = Async()
    .fork([roll(), roll()]) // schedule two concurrent computations
    .all()                  // wait for the two computations to terminate
    .map(fun(r) {
      r[0] + r[1]           // sum the results
    })
    .await()                // wait for the outer computation to terminate
  print(sum)
}

There might be ways to make that code look more imperative with a Swift-like reset builders feature, but at this point I would prefer designing a fluent API in this style.

We may also try to automatically wrap regular code in continuations behind the scenes when we see a spawn expression. But I think that's much more difficult and perhaps overkill.

[kyouko-taiga]

And to illustrate how a program may add work dynamically with this DSL-like approach, here's a silly example:

fun foo(_ n: sink Int) -> Int { /* something that takes long */ }
fun bar(_ n: sink Int) -> Int { /* something that takes long */ }

public fun main() {
  // Start a computation that just produces `42`.
  // Note: the computation *may* execute on a different thread.
  var computation = Async(42).start() 

  // Attach more work to the computation depending on user inputs.
  while true {
    match read_input() {
      0 { &computation.map(foo.copy()) }
      1 { &computation.map(bar.copy()) }
      _ { break }
    }
  }

  // Wait for the work to be done.
  print(computation.await())
}

[dabrahams]

I wish I could make gitbook-style/gdocs-style comments here! GitHub steadfastly refuses to create a system for commenting on documents. :-(

[dabrahams]

A computation is described by a type with the following API:

I assume the private(set) is not meant to be part of the API?

[kyouko-taiga]

The interface should be public let work: ...

I originally declared it a var because I thought we could do in-place mutations of the computation, but that's a useless detail it this point.

[dabrahams]

A receiver represents the continuation of a computation by "receiving" its value or handling errors or cancellation.

Presumably that means it represents a join or something that continues the computation asynchronously?

Receiver looks like it is just a function (receive). Does it need/deserve a trait?

[kyouko-taiga]

Good question.

Yes, receive is just a function, but using functions as generic APIs doesn't feel very idiomatic in Val. I'd like to be able to write this kind of functions:

extension Receiver {
  fun receive_all<V, T: Sequence where T.Element == Async<V>>(
    _ computations: T
  ) inout -> Array<Result> {
    computations.reduce(into: Array(), fun(rs, c) { &rs.append(&receive(c)) })
  }
}

[dabrahams]

Bind implements the monadic bind operator of a computation.

I hate monads :-) What does it do? I understand the description of SyncWait at least.

[kyouko-taiga]

It takes a computation Async<A> together with a function A -> Async<B> and returns a computation Async<B>.

You don't necessarily need to know that a computation is a monad, but that's valuable information for theory nerds to derive other properties. I wanted to settle the discussion from the get go, after seeing countless blog posts debating whether or not JS promises are monads (hint: they are not!)

[dabrahams]

You don't necessarily need to know that a computation is a monad,

I realize that. The problem is that you left out information I do need to know (what it does) in favor of the theory nerd info.

[ericniebler]

I see this is covered in the ensuing discussion, but you really want to be defining your generic async algorithms in terms of async operations that have not yet been scheduled for execution. Trying to juggle with running operations leads to problems in generic code. That means there is more than two states for an async operation: suspended. All async work starts suspended, transitions to running, and then to done.

Also, I see a channel for success (with a value), a proposed channel for errors (exceptions), but no dedicated channel for cancellation, and no way to request that a running operation stop early.

S/r doesn't have "detach" as a primitive. Detached computations break structured concurrency and put you back in a world where you can't reason about the lifetimes of objects owned or accessed by async operations.

EDIT: Rather than truly detached work, in s/r you spawn "detached" work in a nursery (called async_scope) that keeps a count of outstanding work. You can join the async scope, which only completes when all work spawned in it has completed. This gives you the convenience of detached work while keeping the ability to properly scope async lifetimes.

[kyouko-taiga]

Thanks for the feedback!

Lucian has already addressed some of your concerns in a better pitch that will supersedes this one, but I think I should answer a couple of comments anyway.

but you really want to be defining your generic async algorithms in terms of async operations that have not yet been scheduled for execution.

Yes, that is the primary goal and I believe most code should look that way. There are however situations where it might be beneficial to attach work to an existing computation, and I would like to be able to address these.

Imagine you have a system that gets user inputs in a loop. The user may want to start some work on a piece of data (say apply a filter on a large image). That work could start on the background while the user would be allowed to queue another operation to be applied directly on the result.

Also, I see a channel for success (with a value), a proposed channel for errors (exceptions), but no dedicated channel for cancellation

We plan on using exceptions for both errors and cancellation. Our rationale is that implementing cancellation typically requires a mechanism very close to what exceptions already do. With this approach, the handler would be responsible to determine whether the thrown error relates to cancellation or not.

and no way to request that a running operation stop early.

Yes, that was absent from my pitch. The idea we're having now is to pass an inout object to the function representing the computation's work that could be queried for a stop token.

put you back in a world where you can't reason about the lifetimes of objects owned or accessed by async operations.

Maybe detach does not have to be a primitive operation but I still think it might be a relevant feature. The problem of ownership can be solved in by making the computation responsible for the lifetime of its environment.

[ericniebler]

Also, I see a channel for success (with a value), a proposed channel for errors (exceptions), but no dedicated channel for cancellation

We plan on using exceptions for both errors and cancellation. Our rationale is that implementing cancellation typically requires a mechanism very close to what exceptions already do. With this approach, the handler would be responsible to determine whether the thrown error relates to cancellation or not.

I'd like to get @kirkshoop and Lisa Lippincott involved in this discussion, since this is squarely in their wheelhouse:

https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/p1677r2.pdf

"This paper is focused on explaining why errors are a bad way to represent a cancelled result."

IMO, it's well worth your time reading this paper before committing to using exceptions to represent cancellation in Val, especially if it's your intention to have the equivalent of catch(...) in Val.

[kirkshoop]

A function (Int) -> Int is not cancellable.

If it makes an io call (logging, loading configuration) and it is not cancelable and cannot throw then the only options left is to violate its post-conditions by silently returning an int that may result in corruption of the state of the app or it must crash the app.

I prefer cancellation.

[kyouko-taiga]

All of those representations are valid error representations in Val. It is the fact that error values allow multiple representations that makes generic cancellation as error handling impossible.

I don't follow. A long integer is not a valid error value in Val. An error type must conform to Error. You can make Int64 conform to Error, but that would be a poor, lazy choice.

Instead, a wrapper library should define a different error type for all of these cases. That is tedious work but it's done once. There's a finite number of possible errors. Then you can switch over the types I've shown already.

public typealias WinError: Error = (
    type InvalidFunction {}
  | type FileNotFound {}
  | ...
)

Alternatively you can wrap everything except what counts as a cancellation in a single WinError type that would contain a long int and switch over its value at runtime. But, looking at this, I suppose I would personally consider all cases of that winerror to be just errors and simply define:

// A Windows error.
type WinError: Error {
  // The code of the error.
  public let code: Int64
}

I prefer cancellation.

Well, I don't, but that might very well be a matter of taste.

Personally I prefer to trust the API and know for a fact that (Int) -> Int returns an Int, always, no matter what. If that function can't satisfy its postcondition, then it should crash or the author should make it throwable if they think it is worth trying to recover from its failures.

We're in agreement on the fact that it shouldn't silently return an int that might wreck havoc later on ;)

[dabrahams]

In conclusion, I posit that both errors and cancellation are not the "expected" result of an operation

I've found "expectedness" to be a fuzzy and useless distinction in discussions of error handling, and I strongly suspect the same applies to cancellation. IMO the well-defined bucket that both of these things fall into is “failure to satisfy postconditions.”

[dabrahams]

FWIW, reviewing these arguments, I find myself basically 100% in agreement with @kyouko-taiga , except that I can't tell if I'm missing something important because nobody really laid out the whole opposing argument in a way I can digest. I respect the authors of the paper (and @ericniebler who engaged them) too much to discard their concerns without truly understanding them. 🤷‍♂️

[kyouko-taiga]

I've opened a new thread to continue the discussion, as I feel it has slightly drifted away from the topic of concurrency.

Since error and cancellation handling is an important feature on its own, it might be good to come up with a satisfying design before we revisit it for the purpose of concurrency.

[dabrahams]

I wonder if cancellation deserves its own discussion thread?
I'm going to finish reading the referred paper after I write up something on safety for Kona.

[dabrahams]

Due respect to the authors (and I mean that), but I find the paper immensely frustrating. It says early on, “we cannot avoid the hard task of explaining why something like a cancelled_error exception or error_code is a poor representation of a cancelled result” but then it appears to do just that. It doesn't give me anything I can understand as an explanation, at least not without following the threads and histories of many other referenced proposals. I sense that there may be some implicit assumptions made by the authors that I don't agree with, like the idea that incorrectly stopping propagation of cancellation is somehow worse than incorrectly stopping propagation of an exception (?) but nowhere I can see are these assumptions laid out. I can't imagine that this takes 36 pages to explain. Can somebody lay out the argument in a single paragraph?

[dabrahams]

(And maybe that would be a good place to start the new thread)

[niekbouman]

I am familiar with Seastar ( https://github.com/scylladb/seastar/ ), a C++ async framework for linux focused on getting good performance on multicore systems. It might be worth to also take inspiration from their thread-per-core approach to async programming. Also, the Seastar devs use pragmatic solutions to the typical challenges you have in the async world, like error handling and cancellation.

Seastar's design was motivated by the observation that when using "classical" multi-threaded programming (with mutexes & locks for thread safety), contention will kill good utilization of large multicore machines. Hence, it has a "one thread per cpu core"-model, and uses the convention to not share things between cores, except via explicit (async) message passing, which essentially brings you back to having multiple instantiations of the single-threaded programming model, which completely removes the need for locks/mutexes. As such, it has e.g. its own re-implementation of shared_ptr that does not have locks or atomics. Also it has its own NUMA-aware per-core memory allocator. Also has async networking (+dpdk) and async storage APIs (DMA reads/writes).
In the Rust world, glommio (and monoio) try to mimic Seastar's design.

Seastar's way of doing things is quite opinionated, hence might not be a good fit for every async-programming task. On the other hand,
it could be worthwhile to try and keep Val's concurrency design generic enough so that it would remain possible to implement a thread-per-core framework (without unnecessary locks, etc) like Seastar in Val.

[Brian-M-J]

I have 3 things I'd like to ask:

1. On the roadmap, it's mentioned that Hylo is leaning towards stackful coroutines. On this page and in this talk, it's mentioned that Hylo's concurrency model is based on senders/computations. In the stdlib, the name for a handle to async work is Future.

   In e.g. p2300, these 3 things are treated distinctly. I'm a bit confused as to where exactly the lines that differentiate them are, and where Hylo falls on those lines.

On avoiding function colouring:

2. It's mentioned on the roadmap that stackless coroutines don't necessarily lead to function colouring. This is extremely interesting and I'd like to know more. In Mojo (which is another language I'm interested in), the current decision is to go with stackless coroutines. I'd like to avoid things like Rust's async-std crate from happening to Mojo. I'm planning on giving a presentation of my own at the next community meeting and I'd like to bring this up.

   Could one also leverage senders/computations to avoid function colouring as mentioned here by @sean-parent?

   [...] make future destruction blocking (same as senders) to better support structured concurrency without function coloring.

   I'm worried about potentially introducing unnecessary blocking waits with such an approach.

3. How would one interoperate with legacy code that is coloured and uses a fire-and-forget style in a language that avoids function colouring? Mojo has to interoperate with Python, and WASI Preview 3 will introduce a future type.

Edit: The talk is pretty long, so I might have to split it into two parts. If you don't have time for a full explanation by the next community meeting (1st July), I can bring up function colouring in the second part (15th July).

[Brian-M-J]

This isn't really the best forum to investigate what's possible for Mojo, is it? I don't understand why Mojo keeps coming up here; it's a different language with its own set of goals and constraints.

I'm sorry. I just thought they were working with similar constraints (no hidden costs, no unreliable heuristics for optimization), so I thought this applied to Hylo as well.

[dabrahams]

There's certainly overlap, but for example, they mention interop with python as a basic requirement. That doesn't apply to hylo.
I don't mind that you mention Mojo here, but it would be a lot less confusing for me if we were talking in terms of hylo's goals and requirements.

[lucteo]

@Brian-M-J , @nmsmith : thank you for the discussion. Seems like a valuable discussion to me.

Besides what @dabrahams pointed out, I'd like to pick on some points:

You don't pay for it if you don't use it. Stackful coroutines typically aren't very good in this regard.

I disagree. If you are not doing any coroutine jumps, there is no performance penalty. All the code compiles exactly like non-async code.

The beauty of stackfull coroutines is that you can have your function compile like a regular function, and apply the same optimisations, even if you call one async function.

As mentioned there, concore2full doesn't have the best performance. That award goes to S&R.

This is because of two reasons:

• concore2full is not yet polished/optimised
• the example is meant to expose stressful parts for concore2full

My honest feeling is that, once the concore2full approach reaches desired maturity, most of the users won't notice any performance difference between the two.

[niekbouman]

@dabrahams Gotcha. I suspect there are also ways that one can compile to state machines beyond the "russian nesting doll" model that Rust (and I think C++) uses. Instead of putting state machines inside state machines, why not compile a function to a set of transitions between states, and an abstract description of the inputs and outputs that each transition requires. Then whenever a function calls another function, you take the union of their transitions. The data structure that stores the data associated with each state can be decided by the executor. i.e. the job of the executor is to give each transition the inputs it needs, as well as the output addresses that it should store the next state in. The transitions don't actually store any data themselves.

i.e. you can think of function composition as taking the union of two graphs, rather than nesting one graph inside another.

Of course, these are all shower thoughts, and there might be a reason why that approach doesn't make sense.

hi Nick ( @nmsmith )
You should watch Sean Parent's talk on 'chains', which he proposes as a simpler variant to C++26's "sender-receiver" model, where he seems to be doing things along the lines you describe:

https://www.youtube.com/watch?v=nQpXOx0D7I8

[nmsmith]

FWIW I'm no longer in favour of that whole "state machine" compilation strategy. It's orders of magnitude simpler to just have green threads and do a dumb memcpy on and off the OS stack whenever the green thread is suspended or resumed. (Or if your stack is ≥1 memory page, just do conventional stack switching.)

[niekbouman]

@lucteo, what about the (virtual) memory overhead of stackful coroutines, and stackcache pollution when switching?

[lucteo]

There are two main scenarios to be considered:
a) spawning with the purpose of executing more work concurrently
b) spawning with the purpose of implementing asynchrony (i.e., waiting on a network packet)

In the first case, the number of stacks to be used is roughly equivalent to the stacks for the threads that are in use in the global thread pool. The number of the coroutines stacks active cannot be larger than the number of threads that are executing them at the same time, and thus this generates an upper bound of the stack consumption.
(there is some extra stack needed for the machinery, but this can be reduced to be insignificant)
See https://www.youtube.com/watch?v=k6fI4asLJxo for a bit more explanation around the stack space.

In the second case, you need to keep the stack around for the time you are suspending. If the program has 12 active threads, each of them spawning computations and then suspend them (as they are waiting for some external event), then you need stack space for all the currently active coroutines and the suspended ones. Here we can't guarantee an upper bound to the stack consumption.

One way we can address this is to allow the users to specify the stack size when spawning a computation that may be suspended. Or, use part of the current stack. Another idea I was contemplating is to let the compiler figure out the stack consumption for a spawned computation, and allocate it in place.

Most of the asynchronous operations I can think of are somehow low-level, and thus, my hope is that we can easily encapsulate them, meaning that we can fine-tune the stack consumption. For cases like an HTTP server, where the asyncrhony is at the high-level, we can separate (with some help from the language/compiler) the computation that is suspended from its continuation, thus reducing the amount of stack that needs to be kept active for longer times.

The handling of the second case isn't ideal, but we can reach decent compromises.

[lucteo]

On the cache polution:

The cost of a thread context switch is typically an order of magnitude higher than the RAM read, which is one or two orders of magnitudes higher than reading from cache.

Both spawn and await may have thread context switches, thus the costs of invalidating the cache seems rather small.
A thread context switch typically comes with cache invalidation, so the the caching costs may be completely absorbed.

That being said, the layout of the operations tries to maintain locality of the data.
The operations before the spawn, the operations between spawn and await, and the operations after await are all using the same stack. The operations executed after await are executed by the thread that finishes last; chances are both threads are somehow related to what comes after the await point.

The problematic case of having the secondary OS thread continuing after the await point is not that bad. Chances are that this thread was working on some result that is now read by the code after await, so the cache doesn't need to be completely thrown away.

[niekbouman]

Both spawn and await may have thread context switches, thus the costs of invalidating the cache seems rather small.
A thread context switch typically comes with cache invalidation, so the the caching costs may be completely absorbed.

What about avoiding thread context switching altogether by using a single-thread per CPU core model (and each thread 'pinned' to its core), i.e. running an event loop / scheduler on each core, and ensure that async tasks cannot switch threads during suspension points?

[dabrahams]

We are already doing that; if @lucteo says there can still be context switches it is because they aren't completely eliminated. I don't know if this is what he meant, but these points may cause a single thread to switch which task it is executing, which generally means the thread will be accessing a different part of memory.

[niekbouman]

We are already doing that;

Ah ok, thanks for clarifying that.
(Apologies for commenting in this thread without actually having much knowledge about Hylo's status quo...)

[dabrahams]

I don’t think we have any plans to copy stacks around, FWIW

[DmT021]

and do a dumb memcpy on and off the OS stack whenever the green thread is suspended or resumed

You'd need a memory model that forbids references to stack objects when a routine yields then?

Are stacks with sizes < 1 page really a concern?

[lucteo]

One possible approach of solving this issue in the proposed Hylo model is use escaping/detached tasks. For the example above, we would make spawning of C() to be escaping, and we would also make D() to be a new escaping task (from the point of view of A()). Something like:

A()
return spawn_escaping { C(); spawn { D() }.await() }

This means that, after the spawn point, the original flow control can continue executing, thus stack(A) will not be needed anymore.

On the positive side, this drastically reduces the memory consumption. We don't need to keep stack(A) around, and stack(C) can be very small. Thus, we only accumulate small portions of stack.

On the downside, this is not an automatic change, the user needs to do it. Moreover, because stack(A) is (potentially) gone, the user needs to pass information from A() to D() manually.

But, before advancing this model, I need to try it out, to get a feel of the ergonomics of the model.

[dabrahams]

Lucian, I don't think your reduction of the concurrent structure really captures the pattern. Maybe I'm missing something, but I'd write it like this:

spawn_detached( {
   while some_condition {
      x = something_that_does_io()
      do_something_with(x)
   }
})

That is, there's no await anywhere; the task isn't rejoined. It just keeps doing things that suspend it approximately forever.

[dabrahams]

@lucteo says:

If we are in a shared-memory environment, then we need to guarantee that when we restore a stack we restore it at the exactly same position. While a certain task was suspended, some other task may get pointers in the same address space.

Avoiding that problem is why I think a detachable task needs to require its arguments/captures to be Copyable. Whatever goes in or out needs to be copied to the task stack so that it can be referred to there instead of in its original location. It's my contention that whoever is spawning one of these long-running/usually-suspended tasks knows that it has those properties, and the cost of copying captures/arguments is in the noise in such applications.

Think for example of a parallel for-each block that operates on an array. How would we implement that efficiently? Do we need to copy the array into multiple memory spaces.

That application is not the kind of example in question; there's no reason for these tasks to be detachable.

One possible approach of solving this issue in the proposed Hylo model is use escaping/detached tasks.

I guess if a task escapes it has the same argument/capture copying requirement as one that is detached.

On the downside, this is not an automatic change, the user needs to do it.

? I don't have a problem with that at all, but at the same time I thought we actually had enough information from the type system that the user didn't need to use different syntax.

Moreover, because stack(A) is (potentially) gone, the user needs to pass information from A() to D() manually.

Listing copies of the data from A in the capture list of the spawned lambda should work I think.

[lucteo]

@dabrahams : I think my pseudo-code example is compatible with yours. I tried to avoid the loops, as they are not central to the problem.

Think for example of a parallel for-each block that operates on an array. How would we implement that efficiently? Do we need to copy the array into multiple memory spaces.

That application is not the kind of example in question; there's no reason for these tasks to be detachable.\

I was trying to give this example to make the point that we can't have disjoint memory spaces by default. Many applications require shared-memory.

I agree with you on the rest of the points.

[dabrahams]

I think my pseudo-code example is compatible with yours. I tried to avoid the loops, as they are not central to the problem.

I understand: if you launch enough io-performing jobs, even if they suspend only once, you can have the issue. But in fairness, an await isn't central either ;-)

[niekbouman]

[...] then you need stack space for all the currently active coroutines and the suspended ones. Here we can't guarantee an upper bound to the stack consumption.
One way we can address this is to allow the users to specify the stack size when spawning a computation that may be suspended.

This is an interesting part (link starts at 25min:22secs) of a talk by an engineer from Google about some new coroutine library,
but in this part he talks about the status quo of the "fibers" model in Google, where they use small 64kB stacks. Your remark about the application programmer controlling the stack size, made me think about this talk, the speaker essentially argues that with this model you are likely to run into stack overflow issues, especially when using third party libs, which are a pain to debug:

https://www.youtube.com/watch?v=k-A12dpMYHo&t=1519s

BTW when the speaker refers to "other talks", he might be talking about this one:
https://www.youtube.com/watch?v=KXuZi9aeGTw

[dabrahams]

That is a really good talk. He says Google fibers aren't what anybody else means by fibers, so unfortunately it doesn't have much light to shed on the stackful-vs-stackless question, which is what I was looking for. Still a useful talk for other reasons.

[dabrahams]

@nmsmith wrote:

IMO a better challenge for PL designers to spend their time on is coming up with easy-to-use concurrency models, i.e. task communication/synchronization structures. That's something no PL has ever done well.

If I understand what you mean by “structures,” I'm not sure there are many such structures that we know how to reason about. The only shared state I actually understand is monotonic (or cache-like, which is similar). Everything else, it seems, is subject to logical races.

[dabrahams]

@nmsmith I will certainly look. The abstract strongly implies it is the actor model plus a mechanism for atomically updating multiple actors. Is that not it?

[nmsmith]

@dabrahams The narrative of the paper is "we want to improve upon the actor model", so you'll see the authors make constant comparisons against actors. I expect the reason for this narrative is that actors are currently in vogue again, so they think this is the "state of the art" that they need to compare themselves against.

But no, I wouldn't consider the actual model that they have designed to be "actors plus [something]". It's completely different.

[dabrahams]

OK. BTW, I think we have a problem with stack (un)mounting, even if we require the types passed to tasks to be movable: If you have let binding (a.k.a. immutable reference) to something, you can't just move it; you'll need to copy it. So now it basically means things passed to tasks must be copyable, which isn't great.

[nmsmith]

I'm not that familiar with Hylo, so I'll leave it to you to decide whether unmounting is viable. Just remember what we're competing against: a suspended task should only consume as much stack memory as it is using. That could be as low as 100-200 bytes, not 4-16KiB. That's the only way to match the benefits of async. (Maybe that's not one of Hylo's goals, and that's ok.)

[dabrahams]

Don't worry, I'm quite well aware of the competitive target. The web server case wasn't something we thought about, but it's something I think we ought to be able to handle. I think we can easily deal with the little problem I mentioned by making detached tasks a different thing from the ones used for strongly/weakly-structured concurrency; they can impose a Copyable requirement on inputs (or merely sink their inputs I suppose). I don't think potentially-copying and moving input data when you launch these long-running tasks should be a problem; it only happens once after all.

[dabrahams]

The Conclusions section of the BoC dissertation contains this handy evaluation of its suitability for various use-cases:

9.1.1 Optimal BoC applications

I have shown that, BoC shines when we need to perform atomic operations over multiple resources, and
when we need to access multiple resources at once.
Examples of these two patterns are the bank account transfers which should not be interleaved with
other operations, and the boids program where an individual boid needs to read the state of all other boids
to compute its next step.

9.1.2 Effective BoC applications

I discussed that BoC is effective when we need to perform coordinated operations on resources, but the
operation does not need to atomically update multiple cowns. Many of the examples demonstrated in this
thesis can be solved as elegantly using BoC as they can be with actors and promises; this includes examples
santa, barrier synchronisation and dining philosophers.
We can sometimes improve on these situations by leveraging the ordering guarantees of BoC. This is
possible when we spawn behaviours that must happen in sequence, accessing the same cowns, and when
we know no interleaving behaviours can occur. Recall the fibonacci example from Section 7.2.3. In these
scenarios we can avoid a completion signal from one behaviour to the next, or a continuation that is passed
or nested within the behaviour (flattening the code which aids comprehension).
However, it is reasonable to say that this kind of programming requires adjustment; it is not typical to
program by relying on the implicit order of behaviours.

9.1.3 Suboptimal BoC applications

I demonstrated, in Section 7.2.7, that BoC does not fit with the goal of building an asynchronous data-
structure which must perform operations in a synchronous order. The example I presented was hand-over-
hand locking of a tree structure.
In these scenarios, the programmer must revise what they are trying to achieve and decide whether
parallelism or order are important.

[dabrahams]

@nmsmith on that basis, I think uses for this particular paradigm are somewhat niche. Unless you tell me there's a good reason to think it couldn't be implemented as a library I probably won't spend any more cycles on it right now.

[nmsmith]

Btw, the creator of the programming language "Vale" has written up a design for zero-cost green threads here. If it works, it could potentially be even more efficient than the "stack unmounting" approach that we were discussing.

[nmsmith]

Compute efficient, that is. (Because it doesn't require copying.) The memory consumption of the Vale approach would be higher, because it's relying upon a static/worse-case analysis of stack usage, whereas unmounting is capable of allocating just the right amount of memory at runtime.

[lucteo]

@nmsmith : thank you for the heads up.

The Vale model is fully compatible to what we are doing in Hylo, so I would expect us to be able to do something similar. I would expect the overall costs to be slightly higher than what the document wants us to believe, but I still think that the costs are reasonable. Also, the preamble needs to be applied to more than just virtual functions (recursive functions, functions that call outside the boundary of the module, etc. In general to every function that can't be (potentially) fully inlined.)

For the case with no suspended coroutines, this model may give us less stack consumption than if we would just have threads.
For the case with (many) suspended coroutines, the stack consumption can be kept under control.

[seadiem]

In order of nonsense - I wonder what would happen if we built in a buffer that we send to the GPU via Metal or Vulkan at the concept of MVS. In essence, this is the same Structured Concurrency, but only the number of tasks is measured not in units but in thousands

[lucteo]

From the user's point of view, tens of thousands of GPU cores are added to the 8 CPU cores. But the meaning is the same - the same barriers, the same atomics.

I'm not a GPU expert, but all my friends that are, tell me the opposite. At the low level, the way you would interact with the GPU is completely different than the way you interact with the CPU. However, we can provide algorithms on top that are specialized for different hardware that abstracts out these differences.

[seadiem]

The difference is not that big, in fact it is only that we have to allocate memory on the device (GPU) and copy data there from the host (CPU) and back. For example, CUDA makes this process almost seamless

    float h_in[N], h_out[N];
    for (int i = 0; i < N; i++) h_in[i] = (float)i;
    float *d_in, *d_out;
    cudaMalloc((void**)&d_in, size);
    cudaMalloc((void**)&d_out, size);
    cudaMemcpy(d_in, h_in, size, cudaMemcpyHostToDevice);
    int gridSize  = (N + blockSize - 1) / blockSize;
    mapKernel<<<gridSize, blockSize>>>(d_out, d_in, N);
    cudaMemcpy(h_out, d_out, size, cudaMemcpyDeviceToHost);

So I thought, since Hylo intends to make maximum interchangeability with C++, we can directly take the model on CUDA and experiment with it

[lucteo]

For CUDA, we also need to think about SIMD, avoiding conditionals, the differences between streaming processors/blocks/threads, different types of memory, etc.

[seadiem]

Well.. it seems to me that Structurrd Concurrency is a special case of a more general approach to running a grid of threads on the GPU

[lucteo]

I'm looking at this from a different direction. You want to have your application from top to bottom using structured concurrency. Then, at the bottom level you may use existing algorithms that are tailored to work well both on CPU and on GPU (and maybe, why not, on clusters of machines).

It's just like the fact that you are using HTTP, pure sockets, in-memory communication can be abstracted out if you look from a high enough perspective. All these communication methods can be thought of having the same effect of communicating between different nodes, but they vary significantly if you put them under the microscope.