22

Most of the groundwork for coroutines occurred in the 60s/70s and then stopped in favor of alternatives(e.g., threads)

Is there any substance to the renewed interest in coroutines that has been occurring in python and other languages?

2

4 Answers 4

30

Coroutines never left, they were just overshadowed by other things in the meanwhile. The recently increased interest in asynchronous programming and therefore coroutines is largely due to three factors: increased acceptance of functional programming techniques, toolsets with poor support for true parallelism (JavaScript! Python!), and most importantly: the different tradeoffs between threads and coroutines. For some use cases, coroutines are objectively better.

One of the biggest programming paradigms of the 80s, 90s and today is OOP. If we look at the history of OOP and specifically at the development of the Simula language, we see that classes evolved out of coroutines. Simula was intended for simulation of systems with discrete events. Each element of the system was a separate process that would execute in response to events for the duration of one simulation step, then yield to let other processes do their work. During development of Simula 67 the class concept was introduced. Now the persistent state of the coroutine is stored in the object members, and events are triggered by calling a method. For more details, consider reading the paper The development of the SIMULA languages by Nygaard & Dahl.

So in a funny twist we've been using coroutines all along, we were just calling them objects and event-driven programming.

With respect to parallelism, there are two kinds of languages: those that have a proper memory model, and those that don't. A memory model discusses things like “If I write to a variable and after that read from that variable in another thread, do I see the old value or the new value or perhaps an invalid value? What does ‘before’ and ‘after’ mean? Which operations are guaranteed to be atomic?”

Creating a good memory model is difficult, so this effort has simply never been done for most of these unspecified, implementation-defined dynamic open-source languages: Perl, JavaScript, Python, Ruby, PHP. Of course, all of those languages evolved far beyond the “scripting” they were originally built for. Well, some of these languages do have some kind of memory model document, but those are not sufficient. Instead, we have hacks:

  • Perl can be compiled with threading support, but each thread contains a separate clone of the complete interpreter state, making threads prohibitively expensive. As sole benefit, this shared-nothing approach avoids data races, and forces programmers to communicate only through queues/signals/IPC. Perl doesn't have a strong story for async processing.

  • JavaScript has always had rich support for functional programming, so programmers would manually encode continuations/callbacks in their programs where they needed asynchronous operations. For example, with Ajax requests or animation delays. Since the web is inherently async, there's a lot of async JavaScript code and managing all these callbacks is immensely painful. We therefore see many efforts to organize those callbacks better (Promises) or to eliminate them entirely.

  • Python has this unfortunate feature called the Global Interpreter Lock. Basically the Python memory model is “All effects appear sequentially because there is no parallelism. Only one thread will run Python code at a time.” So while Python does have threads, these are merely as powerful as coroutines.[1] Python can encode many coroutines via generator functions with yield. If used properly, this alone can avoid most of the callback hell known from JavaScript. The more recent async/await system from Python 3.5 makes asynchronous idioms more convenient in Python, and integrates an event loop.

    [1]: Technically these restrictions only apply to CPython, the Python reference implementation. Other implemen­tations like Jython do offer real threads that can execute in parallel, but have to go through great length to implement equivalent behaviour. Essentially: every variable or object member is a volatile variable so that all changes are atomic and are immediately seen in all threads. Of course, using volatile variables is far more expensive than using normal variables.

  • I don't know enough about Ruby and PHP to roast them properly.

To summarize: some of these languages have fundamental design decisions that make multithreading undesirable or impossible, leading to a stronger focus on alternatives like coroutines and on ways to make async programming more convenient.

Finally, let's talk about the differences between coroutines and threads:

Threads are basically like processes, except that multiple threads inside a process share a memory space. This means threads are by no means “light weight” in terms of memory. Threads are pre-emptively scheduled by the operating system. This means task switches have a high overhead, and may occur at inconvenient times. This overhead has two components: the cost of suspending the state of the thread, and the cost of switching between user mode (for the thread) and kernel mode (for the scheduler).

If a process schedules its own threads directly and cooperatively, the context switch to kernel mode is unnecessary, and switching tasks is comparably expensive to an indirect function call, as in: quite cheap. These light weight threads may be called green threads, fibers, or coroutines depending on various details. Notable users of green threads/fibers were early Java implementations, and more recently Goroutines in Golang. A conceptual advantage of coroutines is that their execution can be understood in terms of control flow explicitly passing back and forth between coroutines. However, these coroutines do not achieve true parallelism unless they are scheduled across multiple OS threads.

Where are cheap coroutines useful? Most software does not need a gazillion threads, so normal expensive threads are usually OK. However, async programming can sometimes simplify your code. To be used freely, this abstraction has to be sufficiently cheap.

And then there is the web. As mentioned above, the web is inherently asynchronous. Network requests simply take a long time. Many web servers maintain a thread pool full of worker threads. However, most of their time these threads will be idling because they are waiting for some resource, be it waiting an I/O event when loading a file from disk, waiting until the client has acknowledged part of the response, or waiting until a database query completes. NodeJS has demonstrated phenomenally that a consequent event-based and asynchronous server design works extremely well. Obviously JavaScript is far from the only language used for web applications, so there's also a big incentive for other languages (noticeable in Python and C#) to make asynchronous web programming easier.

6
  • I'd recommend sourcing your fourth to last paragraph to avoid risk to plagiarism, it is nearly exactly the same as another source I've read. Additionally, while having orders of magnitude smaller overhead than threads, coroutines performance cannot be simplified to " an indirect function call". See Boosts details on coroutine implementaitons here, and here.
    – Krupip
    Commented Jul 7, 2017 at 13:50
  • 1
    @snb Regarding your suggested edit: the GIL may be a CPython implementation detail, but the fundamental problem is that the Python language does not have an explicit memory model that specifies parallel mutation of data. The GIL is a hack to sidestep these issues. But Python implementations with true parallelism must go through great lengths to provide equivalent semantics, e.g. as discussed in the Jython book. Basically: every variable or object field must be an expensive volatile variable.
    – amon
    Commented Jul 8, 2017 at 10:09
  • 3
    @snb Regarding plagiarism: Plagiarism is falsely presenting ideas as your own, especially in an academic context. It is a serious allegation, but I'm sure you didn't mean it like that. The “Threads are basically like processes” paragraph merely reiterates well-known facts as is taught in any lecture or text book about operating systems. Since there are only so many ways to concisely phrase these facts, I'm not surprised the paragraph sounds familiar to you.
    – amon
    Commented Jul 8, 2017 at 10:21
  • I didn't change the meaning to imply that Python did have a memory model. Also the use of volatile does not on its own decrease performance volatile simply means the compiler can't optimize the variable in a way it can assume the variable will be unchanged with out explicit operations in the current context. In the Jython world this might actually matter, since its going to be using VM JIT compilation, but in the CPython world you don't worry about JIT optimization, your volatile variables would exist in the interpreter runtime space, where no optimizations could be made.
    – Krupip
    Commented Jul 8, 2017 at 16:51
  • Did you mean: threads are "light weight" in terms of memory because they share data? The only thing they don't share is the stack, which can be set to as little as 16K in linux. Not too heavy. (see: pthread_attr_setstacksize) Commented Jan 9, 2020 at 17:00
7

Early systems used coroutines to provide concurrency primarily because they are the simplest way of doing it. Threads require a fair amount of support from the operating system (you can implement them at a user level, but you will need some way of arranging for the system to periodically interrupt your process) and are harder to implement even when you do have the support.

Threads started taking over later on because, by the 70s or 80s all serious operating systems supported them (and, by the 90s, even Windows!), and they're more general. And they're easier to use. Suddenly everyone thought threads were the next big thing.

By the late 90s cracks were beginning to appear, and during the early 2000s it became apparent that there were serious problems with threads:

  1. they consume a lot of resources
  2. context switches take a lot of time, relatively speaking, and are often unnecessary
  3. they destroy locality of reference
  4. writing correct code that coordinates multiple resources that may need exclusive access is unexpectedly difficult

Over time, the number of tasks programs typically need to perform at any time hase been growing rapidly, increasing the problems caused by (1) and (2) above. The disparity between processor speed and memory access times has been increasing, exacerbating problem (3). And the complexity of programs in terms of how many and what different kinds of resources they require has been growing, increasing the relevance of problem (4).

But by losing a little generality, and putting a little extra onus on the programmer to think about how their processes can operate together, coroutines can solve all of these problems.

  1. Coroutines require little more resource wise than a handful of pages for stack, much less than most implementations of threads.
  2. Coroutines only switch context at programmer-defined points, which hopefully means only when it is necessary. They also don't usually need to preserve as much context information (eg register values) as threads do, meaning each switch is usually faster as well as needing fewer of them.
  3. Common coroutines patterns including producer/consumer type operations hand data off between routines in a way that actively increases locality. Furthermore, context switches typically only occur between units of work not within them, ie at a time when locality is usually minimized anyway.
  4. Resource locking is less likely to be necessary when routines know that they can't be arbitrarily interrupted in the middle of an operation, allowing simpler implementations to work correctly.
7

Coroutines used to be useful because operating systems did not perform pre-emptive scheduling. Once they started providing pre-emptive scheduling, it was longer necessary to give up control periodically in your program.

As multi-core processors become more prevalent, coroutines are used to achieve task parallelism and/or keep a system's utiliztion high (when one thread of execution must wait on a resource, another can start running in its place).

NodeJS is a special case, where coroutines are used get parallel access to IO. That is, multiple threads are used to service IO requests, but a single thread is used to execute the javascript code. The purpose of executing a users code in a signle thread is to avoid the need to use mutexes. This falls under the category of trying to keep the system's utilization high as mentioned above.

8
  • 4
    But coroutines are not OS managed. OS does not know what a coroutine is, unlike C++ fibers Commented Jul 6, 2017 at 6:01
  • Many OSs have coroutines. Commented Jul 6, 2017 at 7:59
  • coroutines like python and Javascript ES6+ aren't multiprocess though? How do those achieve task parallelism?
    – Krupip
    Commented Jul 6, 2017 at 14:32
  • 1
    @Mael The recent "revival" of coroutines come from python and javascript, both of which do not achieve parallelism with their coroutines as I understand. That is to say that this answer is incorrect, as task parrallism is not the reason coroutines are "back" at all. Also Luas aren't multiprocess either? EDIT: I just realized you weren't talking about parallelism, but why did you reply to me in the first place? Reply to dlasalle, since clearly they are wrong about this.
    – Krupip
    Commented Jul 6, 2017 at 15:48
  • 3
    @dlasalle No they can't despite the fact that it says "running in parrallel" that doesn't mean any code is run physically at the same time. GIL would stop it and async does not spawn seperate processes required for multiprocessing in CPython (seperate GILs). Async works with yields on a single thread. When they say "parralel" they actually mean several functions yeilding to other functions work and interleving function execution. Python async processes can not be run in parallel because of impl. I now have three languages who don't do parralel coroutines, Lua, Javascript, and Python.
    – Krupip
    Commented Jul 6, 2017 at 15:58
5

Preface

I want to start of by stating stating a reason why coroutines aren't getting a resurgence, parallelism. In general modern coroutines are not a means to achieve task based parallelism, as modern implementations do not utilize multiprocessing functionality. The closest thing you get to that are things like fibres.

Modern Usage (why they are back)

Modern coroutines have come as a way to achieve lazy evaluation, something very useful in functional languages like haskell, where by instead of iterating over an entire set to perform an operation, you would be able to perform an operation only evaluation as much as needed (usefull for infinite sets of items or otherwise large sets with early termination and subsets).

With the use of the Yield keyword to create generators (which in themselves satisfy part of the lazy evaluation needs) in languages like Python and C#, coroutines, in the modern implementation were not only possible, but possible with out special syntax in the language itself (though python eventually added a few bits to help). Co-routines help with lazy evaulation with the idea of futures where if you don't need the value of a variable at that time, you can delay actually acquiring it until you explicitly ask for that value (allowing you to use the value and lazily evaluate it at a different time than instantiation).

Beyond lazy evaluation, though, especially in the websphere, these co routines help fix callback hell. Coroutines become useful in database access, online transaction, ui, etc, where processing time on the client machine itself isn't going to result in faster access of what you need. Threading could fullfill the same thing, but requires a lot more overhead in this sphere, and in contrast with coroutines, actually are usefull for task parallelism.

In short, as web development grows and functional paradigms merge more with imperative languages, coroutines have come as a solution to asynchronous problems and lazy evaluation. Coroutines come to problem spaces where multiprocess threading and threading in general are either unnecessary, inconvenient or not possible.

Modern Example

Coroutines in languages like Javascript, Lua, C# and Python all derive their implementations by individual functions giving up control of the main thread to other functions (nothing to do with operating system calls).

In this python example, we have a funny python function with something called await inside of it. This is basically a yield, which yields execution to the loop which then allows a different function to run (in this case, a different factorial function). Note that when it says "Parallel execution of tasks" that is a misnomer, it isn't actually executing in parallel, its interleaving function execution through the use of the await keyword (which keep in mind is just a special type of yield)

They allow single, non parallel, yields of control for concurrent processes which is not task parallel, in the sense that these tasks do not operate ever at the same time. Coroutines are not threads in modern language implementations. All these languages implementation of co routines are derived from these function yield calls (which you the programmer have to actually put in manually into your co routines).

EDIT: C++ Boost coroutine2 works the same way, and thier explanation should give a better visual of what I'm talking about with yeilds, see here. As you can see, there is no "special case" with the implementations, things like boost fibres are the exception to the rule, and even then require explicit synchronization.

EDIT2: since someone thought I was talking about c# task based system, I wasn't. I was talking about Unity's system and naive c# implementations

2
  • @T.Sar I never stated C# had any "natural" coroutines, neither does C++ (might change) neither did python (and it still had them), and all three have co routine implementations. But all C# implementations of coroutines (like those in unity) are based off of yield as I describe. Also your use of "hack" here is meaningless, I guess every program is a hack because it wasn't always defined in the language. I'm in no way mixing up C# "task based system" with anything, I didn't even mention it.
    – Krupip
    Commented Jul 6, 2017 at 17:07
  • I would suggest making your answer a bit more clearer. C# has both the concept of await instructions and a task-based parallelism system - using C# and those words while giving examples on python about how python isn't really truly parallel can cause a lot of hard confusion. Also, remove your first sentence - it's unneeded to directly attack other users in an answer like that.
    – T. Sar
    Commented Jul 6, 2017 at 17:11

Not the answer you're looking for? Browse other questions tagged or ask your own question.