(Un-)Structured concurrency

Hi Team behind Verse, let’s have a constructive discussion on (un-)structured concurrency in verse.

I’m happy to see that Verse had decided to go that rout from day way since the language became publicly available. Props to everyone pushing this decision forward.

I would like to see the inspiration Verse went after, since it does not look like this kind of implementation follows the “cooperative” path.

As far as I can tell the cancellation mechanism in Verse’s concurrency model is eagerly enforced instead of being cooperative. At least there’s no explicit way to determine a cancellation within a structured task.

I still wonder there will be ways to do the following things:

  • explicit cancellation for spawned unstructured task
  • the ability to spawn and control structured tasks
  • detect if a task was explicitly cancelled (defer can work here and there, but I’m not sure it will scale to all use cases)
  • partial cancellation of specifically targeted structured child tasks

Yes I understand that we can use the special concurrency operations such as race, sync etc. to partly achieve those things, but sometimes it feels rather like a workaround than the intended behavior.

Feel free to correct me if I misunderstood the desired concurrency model Verse is trying to enforce here.

My personal structured concurrency expertise comes from Swift, which offers a cooperative cancellation when driving (un-)structured tasks.

1 Like

As you’ve noticed, we’re missing some functionality for unstructured concurrency (task and spawn) to be as powerful as the structured concurrency (sync, race, etc). So far we have been solely focused on the structured concurrency.

explicit cancellation for spawned unstructured task

With our cooperative coroutines, a task is almost always suspended when it is canceled. If you try to cancel a suspended task, it will be immediately canceled, and its defer blocks executed and unwound. As such, the semantics are that any call that suspends might also unwind cancellation.

Even so, it’s possible for a race subtask to cancel itself by calling a non-suspends function that, for example signals an event. Since that function doesn’t have the suspends effect, it cannot implicitly unwind an immediate cancellation.

This is a known bug right now: a self-canceling race subtask won’t actually cancel as you might expect, so please be careful not to rely closely on exactly how this currently behaves. To fix this, the cancellation must be asynchronous, or cooperative as you call it. We have a plan for how to do this, but not a timeline for the fix yet.

Allowing you to directly cancel a task is dependent on first defining sensible self-cancellation behavior in the structured case.

ability to spawn and control structured tasks

Can you elaborate on this? Verse doesn’t distinguish between structured and unstructured tasks: e.g. the main difference between spawn and branch is that branch creates a subtask that is implicitly canceled if the calling task is canceled. The spawned task might still be the root of a tree of structured tasks, it just doesn’t have a parent task itself.

detect if a task was explicitly cancelled

I’m not sure how we’d expose this exactly, given that anything that suspends might unwind cancellation instead of returning. It’s possible that we could refine cancellation to be an exception that could be handled explicitly, but that is dependent on adding exception handling to Verse, which isn’t something we have specific plans for.

partial cancellation of specifically targeted structured child tasks

The structured concurrency is designed in a way that doesn’t give you task values for the structured subtasks. This might be a case where using unstructured concurrency is the way to go.

Is there anything else you think is missing from unstructured concurrency in Verse?

4 Likes

Hi Andrew, thank you for elaborating on that many details here. Again I’m just comparing it to the structured concurrency model I’m experienced with, which does not imply that it has to be identical. If Verse has a slightly different direction in mind, that’s totally fine. I’m just trying to wrap my head around it as this a fairly advanced feature.

Let me bring up examples from Swift just to reference their behavior so we can compare a little better.

func nonAsyncFunc() {
  // - this function is not async
  // - it can initiate an async call, but that would require to 
  //   spawn an unstructured `Task`
  let task = Task { ... }

  // this function cannot await for `task` to complete
  // as it would require it to be able to suspend

  // trivial: `nonAsyncFunc` can be called from an async function 
}

Every root task starts always from some synchronous context and has to use a Task to enter the asynchronous domain. The execution within the scope of that unstructured Task however becomes structured.

func asyncFunc() async {
  anotherAsyncFunction()

  // - this function will spawn an unstructured task, but that 
  //   task is NOT a child task of the current structured task, 
  //   as it becomes detached
  // - Swift also differentiates between `Task {}` and 
  //   `Task.detached {}` where the former does inherit some
  //   execution context and the latter doesn't
  nonAsyncFunc()

  // - existing the scope of this function guarantees that all 
  //   "structured" child tasks have been completed or cancelled
  // - completion or failure can be viewed as the same, the child task
  //   returned either its value or a failure error
  // - errors in Swift are not exceptions, those are also values 
}

An unstructured Task in Swift can do many things:

  • we can check if it’s cancelled task.isCancelled
  • we can await it’s value await task.value
  • we can explicitly cancel it task.cancel()

However, task cancellation in Swift is ‘cooperative’ and not eager. That means that the task will not potentially immediate resume or gets thrown away. It will run until it can unwind if at all.

To check within a (un-)structured task if it’s cancelled or not Swift provides two static options.

Task<Int, Never> {
  // do some work

  // we can dually return early if we wanted
  if Task.isCancelled { return 42 }

  // do more work
  return someComputedResult
}

Task<Int, any Error> {
  // do some work

  // this option throws a cancellation error
  try Task.checkCancellation()

  // do more work
  return someComputedResult
}

The cancellation error again is just an empty struct.

struct CancellationError: Error, Sendable {}

As you might have noticed by now a task in Swift has a return value and a failure (error). It’s basically like Either<A, B>. It expresses that it might return either the value for success or failure.

I mentioned “it might” because it doesn’t have to if it does not want to. Even with cooperative cancellation this is still enforced. It’s up to the task on how it wants to handle the cancellation.

let task = Task {
  var iteration = 0
  while true {
    iteration = iteration &+ 1 // with overflow

    if Task.isCancelled {
      print("cancelled", iteration)
    } else {
      print(iteration)
    }
  }
}

task.cancel()

In the above example the task will never return or throw any error value. It will indefinitely loop, but it will eventually start printing cancelled when the task is known to be cancelled.

If on the other hand the cancellation in Swift was eager instead of cooperative, the task would be immediately killed and potentially require it to always be failable.

The beauty of having cooperative task cancellation is that it permits the implementation of gracefully shutdowns. The cancellation eventually propagates through all interconnected structured child tasks and they all decide on their own how they want to finish their execution if at all.

The similarity in verse is that unstructured tasks spawned within a structured task are not implicitly interconnected. Therefore such unstructured task can outlive the structured one. However any true structured child task is not allowed to outlive the parent. I’m not partially sure if branch enforces that behavior.

Right now Swift does have some ways to explicitly spawn structured child task through [Discarding]TaskGroup.

try await withThrowingTaskGroup(of: Void.self) { group in 
  group.addTask { try boom() }
  group.addTask { try boom() }
  group.addTask { try boom() }
  
  try await group.next() // re-throws whichever error happened first
} // since body threw, the group and remaining tasks are immediately cancelled 

All child tasks must finish in some way before withThrowingTaskGroup itself is allowed to be resumed.

Swift is still evolving in that area and functionality like withThrowingTaskGroup are the basic primitives for things like race, sync etc. in Verse.

If Verse has static members you could potentially also expose a form of task local cancellation checks.

Pseudo example:

MyAsyncFunc()<suspends>: int = {
  var Result: int = 0
  loop {
    if (task.IsCancelled()) {
      set Result = Result + 10 // bump + 10 on cancellation
      break
    }
    set Result += 1
  }
  return Result
}

If Verse also went the cooperative cancellation route then I could implement the cancellation gracefully and take as much time as needed to complete any critical computation I’d have already running instead of killing that process asap.

One last thing. The above Swift’s TaskGroup adds structured child tasks, but they currently cannot be explicitly cancelled. However this is just the status quo as the API surface for that hasn’t been implemented yet. There’s no technical reason why it cannot be done, it’s just not there yet.

Hey @AndrewScheidecker I’d love to hear your thoughts on my last message, but I also have more topics to talk about in the same context.


Why does Verse not have an explicit marker for suspension points such as an await keyword? While having async calls transparently integrated into the syntax is somewhat nice, it starts to give me personally some headache as soon as the async logic becomes much more complex and it’s important to maintain some state integrity. Therefore spotting suspension points by reading the logic is a good practice to undestand the phenomenon of reentrancy.

A few follow up questions are:

  • How does verse schedule tasks?
  • Are tasks truly concurrent / parallel or are we in a single threaded environment?
  • If there’s some true concurrency here, how is a class then thread safe?
  • How can I ensure that a property isn’t read while it’s being modified by another task?

In Swift example there’s now an answer to that through actors instead of unsafe classes where one would need to handle this manually.

I’m always unsure if two tasks that perform similar actions and modify the same stored properties aren’t truly racing in my map logic.

If on the other hand we’re in a single threaded environment:

  • How is the logic able to run so fast, that it does not potentially block other more important tasks from running for too long?
  • Are we possibly going to get true concurrency in the future?
2 Likes