Yup. See https://journal.stuffwithstuff.com/2015/02/01/what-color-is-... for a pretty good explanation of the async/await problem.

I know Rust is all about zero-cost abstractions, "but at what cost" beyond just runtime cost? I appreciate their principled approach to mechanical sympathy and interop with the C abstract machine, but I'm just not enthused about this particular tradeoff.

An alternative design would have kept await, but supported async not as a function-modifier, but as an expression modifier. Unfortunately, as the async compiler transform is a static property of a function, this would break separate compilation. That said, I have to wonder if the continuously maturing specialization machinery in Rustc could have been used to address this. IIUC, they already have generic code that is compiled as an AST and specialized to machine code upon use, then memoized for future use. They could specialize functions by their async usage and whether or not any higher-order arguments are themselves async. It might balloon worst-case compilation time by ~2X for async/non-async uses (more for HOF), but that's probably better than ballooning user-written code by 2X.

Async adds a runtime requirement, so Rust cannot just take the same approach as Go. You only have a scheduler if you instantiate one. And having a runtime or not has nothing to do with the C abstract machine, but with precise control on what the code does.

For instance, Go does not give you the option to handle this yourself: you cannot write a library for implementing goroutines or a scheduler, since it's embed in every program. That's why it's called runtime. In Rust, every bit of async implementation (futures, schedulers, etc) is a library, with some language support for easing type inference and declarations. This should already tell you why they took this approach.

Regarding async/await and function colors (from the article you posted), I would much rather prefer Rust to use an effect system for implementing this. However, since effects are still much into research and there is no major language which is pushing on this direction (maybe OCaml in a few years?) it seems like a long shot for now.

Go is even more different. Rust async has explicit yields with await, but Go does it implicitly at various key locations. This is actually pretty surprising to many folks, it was in the past and maybe still is possible to deadlock Go with a certain incantation of tight looping.

Another difference with Rust is that async functions are stackless. Go has to contend with having a non-conventional stack and interoperability with C code (and sometimes syscalls, vDSO, etc.) that expects a relatively large stack requires pivoting.

I do wish Rust could solve this problem, but the two approaches are very different indeed. I think it’s a fact of life that accidental blocking will exist in Rust, approaches that prevent it are complicated and indeed have runtime costs.

> [...] Go does it implicitly at various key locations. This is actually pretty surprising to many folks, it was in the past and maybe still is possible to deadlock Go with a certain incantation of tight looping.

This is being worked on here: https://github.com/golang/go/issues/24543

Is there any documentation on the latest status on this, how far along they've come and what technical solutions they're considering / have settled on?

The proposal is marked accepted, and commits are being made to reference it, so I suppose the design doc and that issue are most likely the source of truth.

Fascinating. This would make Goroutines one giant leap closer to being thread-like. It feels weird how much of the OS scheduler is being “duplicated” but you can’t really argue much with the results.

> so Rust cannot just take the same approach as Go

I did not suggest that it do so. In fact, I suggested an approach that wouldn't fit for Go!

In Go, you've got pretty strict modular compilation. Because of this, specialization -- which is pervasive in Rust -- is virtually absent in Go. Rust's rich generics system demands robust specialization machinery. This machinery, which handles instantiation of explicit generics, can be repurposed to handle automatic instantiation of implicit generics. In this case, I'm suggesting that a function could be compiled as either synchronous or asynchronous as determined by the use-site.

> In Rust, every bit of async implementation (futures, schedulers, etc) is a library

Nothing about my suggestion precludes this.

Exactly! Most code doesn't care whether it's sync or async, the compiler should decide which specialization to use when the program is built. The only places where you usually care is either 1: the very top of the program (some event loop handler called near main) or 2: the very bottom, when you're implementing an IO library. The specialization is decided by what you do at the very top; that decision propagates down the call chain, specializing everything in the middle that doesn't care; until it gets to a function in your IO library where it chooses between the pre-defined sync or pre-defined async implementations.

So you have a synchronous http server and you decide you want to make it async? Ok, no problem, switch to an async-enabled request handler in main, and boom everything that you wrote is recompiled into a state machine a la async, and at the very bottom where it actually calls the library to write out to the socket it, the library knows what the context is and can choose the async-enabled implementation.

I'm glossing over some important details and restrictions that might make this more complicated in practice, but I think it should at least be possible for functions to opt-in to 'async-specializability' to avoid having to rewrite the world for async.

> An alternative design would have kept await, but supported async not as a function-modifier, but as an expression modifier.

How is that different than an `async` block?

It's not. I didn't realize Rust had that, but the rest of my comment still applies: it would be nice if asynchrony was transparent to intermediate functions and compiled via specialization.

> Programming languages have the power to implement concurrency patterns that offer the same kind of performances, without the hassle.

Can you give one that reaches this goal? Go is often cited on that regard but it doesn't really fit your description since it trades performance for convinience (interactions with native libraries are really slow because of that) and still doesn't solve all problems since hot loops can block a whole OS thread, slowing down unrelated goroutines. (There's some work in progress to make the scheduler able to preempt tigh loops, though).

I think Project Loom would fit. It's a remarkably sane approach:

https://cr.openjdk.java.net/~rpressler/loom/Loom-Proposal.ht...

As a Java developer I'm really looking forward for Project Loom. I think it's a great approach that avoids the pitfalls of the two-colored functions approach.

However, Project Loom doesn't fit into the "zero cost abstraction" paradigm of rust. Project Loom requires quite a lot of support form the JVM runtime:

> The main technical mission in implementing continuations — and indeed, of this entire project — is adding to HotSpot the ability to capture, store and resume callstacks not as part of kernel threads. JNI stack frames will likely not be supported.

It also still require manual suspension so JIT compiled tight loops will likely still cause a problem.

I think that that makes it fairly similar to Rust's approach then... compiler support for suspension, and cooperative scheduling.

Clojure's pmap function (parallel map) is pretty cool: http://clojure.github.io/clojure/clojure.core-api.html#cloju...

There is rayon in rust land. This is a pretty different (simpler) thing.

Rayon uses iterators. Iterators are the dual of first order functions. Iterators are superior because they are more general. (You can implement pmap using iterators. You cannot implement iterators using pmap.)

Does Rayon use iterators, or just iterator-like combinators? I don’t think a for-loop would work with Rayon, would it?

You can also definitely implement iterators using first-order functions:

    const iterate = array => {
      const step = index => ({
        value: array[index],
        next: () => step(index + 1)
      });
      return step(0);
    }

    // add some combinators on top

First order functions can in fact implement anything if you’re willing to accept some bad syntax and speed — that’s the Church-Turing equivalence.

Hm. You're right. I hadn't used Rayon in so long I forgot it is indeed iterator-like combinators using an entry point called `par_iter`.

Python's greenthread implementations are quite good, monkey-patching all calls to work asynchronously with low mental overhead and automatic library comparability (except for libraries that call native code obviously).

Of course Python generally fails to offer "the same kind of performance" for anything limited by CPU or memory, so it technically doesn't fit the description either.

> since hot loops can block a whole OS thread

Asking as a beginner, what does the above mean?

Not sure what does hot loop means, and why does it block Os thread

Go creates the illusion of preemptive multithreading by having implicit safe-points for cooperative multithreading. Each IO operation is such a safe-point. If you write an infinite loop like `for {}` where there are no IO operations in loop body, it will block indefinitely. This will prevent the underlying OS thread from being available to other goroutines. The same thing can happen even if you do have IO operations in there, but the work being performed is dominated by CPU time instead of IO.

Note that this is being fixed in the next release: https://golang.org/issue/10958

That's cool it's finally coming, this issue is open since 2015! I wonder which performance impact this will have.

Maybe this is a dumb question, but what if a language with implicit safepoints lets you opt out with something like a nosafepoint block/pragma?

An “OS thread” is the most basic part of the program that can actually do things. When it is blocked, it can’t do anything.

OS threads can be expensive, so libraries try to only create a few OS threads.

A “hot loop” (usually, I think, called a “tight loop”) is a loop that does a lot of work for a relatively large amount of time all at once. Things like “looping through a list of every building an Manhattan and getting the average price over two decades.”

With some code like networking, you end up having to wait on other parts of the computer besides the CPU often, for things like uploads and downloads.

“Asynchronous programming” tried to make it easy to keep the CPU busy doing helpful things, even while some of it’s jobs are stuck waiting on uploads/downloads/whatever. This keeps the program efficient, because it can do a little bit of many tasks at once instead of having to complete each task entirely before moving on to the next.

The problem comes when you have a tight loop in a thread that is mostly expecting to be doing asynchronous work around I/O or networking. It is basically trying to juggle with one hand. The program can’t multitask as well, and you end up having to wait longer before it can start each piece of work you want.

Hot loops are often "expensive", or where your program is spending a lot of its time.

If you're doing a hot loop, which may be synchronous, you will block the event loop attached to that OS thread, because a hot loop is presumably not yielding control until it is done.

hmm, why is that a bad thing, if your entire thread is synchronous shouldn't it technically be blocking? Or is OS thread the main thread?

The problem is that the async model is a form of cooperative multithreading, so if one computation runs for a long time without returning to the main event loop, it can increase the latency for responses to other events. E.g., if one HTTP request takes a long time to process, and many of the worker-pool OS threads are handling such a request, response time goes up for all the other requests. OS-level concurrency is preemptive (timesliced), so one busy thread doesn't block other requests, but of course with much higher overhead in other ways. Best practice is usually to keep event handlers on event-loop threads short and push heavy computations to other OS-level worker threads.

ah, that make sense, I think another user point out that spawning n goroutine does not actually spawn n physical threads but rather queue n task to m thread in the pool, so if we exhaust m thread, n-m task will be blocked.

Thanks for the explanation

I wonder what is the point where each trade off make sense (ie. what is consider heavy computation vs light computation, it probably is related to OS thread allocation time)

> interactions with native libraries are really slow because of that

Can you explain a bit? What is the connection between concurrency implementation (which I am assuming you are talking about multiplexing multiple coroutines over the same OS thread) and say slowness in cgo? Having to save the stack? I don't get it.

FFI is slow because the main Go compiler uses a different calling convention than everything else. I couldn't tell you if or how that's related to its concurrency features.

Its an important optimization otherwise each go routine would use a lot of memory, but its not required. The stack allocation strategy has changed a couple times in main compiler, gccgo originally support it and CGo functions behave like normal go mod the stack.

> Can you give one that reaches this goal?

First-class continuations. They are an efficient building block for everything from calling asynchronous I/O routines without turning your code into callback spaghetti, to implementing coroutines and green threads. Goroutines are a special and poorly implemented case of continuations. Gambit-C has had preemptive green threads with priorities and mailboxes at less than 1KiB per thread memory overhead for over a decade now, all built on top of first-class continuations.

http://www.iro.umontreal.ca/~gambit/Gambit-inside-out.pdf

First-class continuations are too unrestricted to match the performance of Rust-style async/await.

If you take on a few limitations you can get there, but then those are exactly the things people complain about.

It is worse than that. First-class continuations add a small overhead for stack operations, and they always have more memory overhead than callbacks/async transformation into callbacks. But the comment I was replying was about Go, not Rust. For the small overhead that first-class continuations have, they provide a simple and efficient way to handle coroutines, generators, asynchronous I/O, and green threads.

Erlang probably comes closest?

Not an Erlang user, but my understanding is that the Erlang VM (BEAM) schedules on function calls. Which works fine for that use, since Erlang does looping with tail calls, but is not a solution for procedural languages.

Erlang vm is fully preemptive and schedules on something called a reduction. You can call an external function with EFI that can screw things up, but otherwise it's not necessarily on what you might consider a function call .

In practice, it's enough to preempt at potentially-recursive function entry and loop backedges. A thread which doesn't recurse or loop has to come to an end pretty quickly, at which point the scheduler will get a go.

There's no fundamental difference between inserting a yield before a tail call and inserting a yield before a continue statement or closing bracket of the for block, is there?

Fundamentally no, but it's a more difficult thing to do in practice at least. Unless you want to give up other optimizations like loop unrolling and other things like that since you end up losing the fact that the loop exists after some optimization passes.

BEAM (Erlang VM) provides pre-emptive scheduling

True for functions written in Erlang/Elixir, but not in NIF functions implemented in C.

Thanks to dirty schedulers that is not a big issue: https://medium.com/@jlouis666/erlang-dirty-scheduler-overhea...

Thanks for the link. It's a very deep and interesting technical post.

> If anything down the callstack is synchronous, it blocks everything.

If you use a work stealing executor tasks will get executed on another thread. Therefore the impact of accidentally blocking is lowered. Tokio implements such an executor

I haven't used tokio but in my Scala days the execution context was backed by a thread pool. One blocking call wouldn't kill you because it would just tie up one thread, but the thread pool would quickly get exhausted and lock up the application. Does tokio have the same problem?

There is a maximum number of threads and it's by default set to the # of cores (based on the docs for tokio-executor's ThreadPool and Builder). The docs also say that the # of threads starts at 0 and will increase, so one can do the Scala strategy of starting with large threadpools - one of my projects last year defaulted to 100-200 threads per pool to avoid just this problem.

I think the question you're asking is, "are deadlocks possible?" and the answer to that seems like it would be yes. I would hope that Rust's memory model makes accidental memory sharing dependencies & deadlocks harder to cause, but you can always create 8 threads waiting on a mutex and a 9th that will release it, and have the 8 spinlock on the waiting part.

The "async-std" library, one of a few attempts to write async-aware primitive functions around blocking calls to the filesystem, mutexes, etc, implements async wrappers around mutex and others that should ensure that yield points are correctly inserted and the task goes back into the queues if it's blocked.

That seems to me the right solution - make sure all your blocking calls with a potential for deadlocking check "am I blocked?" first and if so, put themselves back onto the task queue instead of spinning.

Rust cannot guarantee the lack of deadlocks or overall thread-safety. It does guarantee no data races, though.

Yes, is there some way I could have been more precise about that in my comment?

It will certainly have it's limits. I don't know whether tokio spawns new threads if it detects all others are used up - likely not that this point of time. However work-stealing at least allows to mitigate the impact of some accidentally blocking code. E.g. if a syscall is made that takes longer than expected - or if a library holds a mutex for longer than necessary. It shouldn't be used as an excuse for simply blocking everywhere in an async task executor - but it will to reduce the impact, and give developers some time and wiggle room to improve the associated code.

> Async I/O gives awesome performance, but further abstractions would make it easier and less risky to use. Designing everything around the fact that a program uses async I/O, including things that have nothing to do with I/O, is crazy.

Microsoft kind of tried to do this with the new APIs for UWP: pretty much everything is async, the blocking versions of APIs were all eliminated, so there was no way for the async-ness to "infect" otherwise synchronous code. It was actually a pretty nice way to program; it's a shame it never took off.

They're finally opening the APIs (already have, I think, to some extent) for use with normal desktop apps and "UWP" apps outside of the Store. You can even embed the new UI stuff inside of Forms and WPF apps via XAML islands.

They also lowered their portion of the revenue share considerably for Store apps, afaik.

The JavaScript world is pretty close to this. Not quite everything is async, but almost everything is async-first.

The javascript world was forced into this. Since it doesn't (or at least didn't) expose threads, everything had to be non-blocking. Otherwise programs would be non-responsive all the time.

They do, but only at the expense of interoperability. Any "green thread" solution breaks down once you have to invoke code written in something else while allowing it to call you back. Async futures, on the other hand, can map to any C ABI with callbacks.

So until there's some standardized form of seamless coroutines on OS level, that is sufficiently portable to be in wide use, we won't see widespread adoption of them outside of autarkic languages and ecosystems like Erlang or Go.

Targeting the browser via WASM, we don't even have syncronous I/O for many/most things - I've been looking forward to async/await as a means of reigning in some of the awkward APIs and callback hell.

I am waiting for a language to solve this with the type system and compiler. Give me the ability to mark a thread as async only and a clean (async) interface to communicate with a sync thread. If my async code tries to do anything sync, don't let it compile.

Whether a function is async-safe isn't black and white. A function that performs calculations may return instantly on a small dataset but block for "too long" on large parameters. On what is "too long" will vary widely depending on your application.

But whether a function is not async-safe is pretty black and white (i.e. there's a lot of clearly unsafe code). Even a definition as simple as "performs blocking I/O" would be extremely helpful.

This is the value people get out of async only environments like node. Yes, you still have to worry about costly for loops but I don't have to worry about which database driver I'm using because they are all async. In a mixed paradigm language like rust I would really appreciate the compiler telling me I grabbed the wrong database driver.

What about long-running computations? They're not really async-safe (they will block the thread), but they don't perform any IO.

I think the suggestion is “clearly blocking io should be marked as such (with some marker like unsafe) and other functions can be marked “blocking” if the creator decides it is blocking.”

In the worst case a problem could still occur, but once found, the “problem” function can be marked appropriately. At the least that would start to solve the issue.

There are plenty of synchronous calls in node and js. Not everything is async https://nodejs.org/api/fs.html#fs_dir_readsync

And that's just io, most function calls are synchronous also

Aren't you effectively asking the compiler to solve the halting problem?

I think the best you could do would be heuristics - having inferred or user-supplied bounds on the complexity of functions, having rough ideas on how disk or network latency will affect the performance of functions, and bubbling that information up the call tree. It wouldn't be perfect, but it could be useful.

Compilers can "avoid" the halting problem if the underlying language is not turing complete/ can express function totality.

You can even express algorithmic complexity in a language.

But it's a bit more complex than that, really. You will have a harder time saying "this loop will block the event system for longer than I'd like".

Sorry, how is Rust not that language? You can use single threaded executors that only require Send and not Sync on data being executed on.

Nit: Singlethreaded executors also don't require "Send", since they don't move things between threads. That allows you too e.g. use non-atomically refcounted things (Rc<T>) on singlethreaded executors, which you can't use in the multithreaded versions.

Yes, you're quite correct, and I don't think a nit. That is much more accurate.

Does the compiler prevent me from calling a library that calls a library that performs a sync action?

What is a 'sync action'?

Async is fundamentally cooperative multitasking. There is no real difference between the 'blocking'-ness of iterating over a large for-loop and doing a blocking I/O action - the rest of your async tasks are blocked either way while another task is doing something.

While the behavior of a large for-loop and a blocking I/O action doesn't change the event loop, I'd still appreciate the compiler helping me identify the blocking I/O loop. I'll take whatever help I can get.

I think I can agree with you, but first I think we'd have to somehow define how to even approach this feature.

Eg, fundamentally I feel like you're making a distinction between blocking I/o and a "blocking" for loop. At the end of the day, they're the same in my view - one is just more likely to be costly.

So I think for this feature to be done right, we'd have to somehow be able to analyze the likelihood of an expensive operation - and the negative consequence that action might have on the rest of the workload. Eg, I would want the same hypothetical behavior and compile-time warnings/errors that a huge file-load might cause, with a huge loop.

Otherwise a simple function call which involves no I/O and looks innocent could have the same terrible behavior as some I/O call does.

Defining that, and informing the compiler seems obscenely difficult. To that degree, I think any interaction with any sort of heap-y thing like iterating over a Vec would have to error the compiler if used in a Future context.

_everything_ would have to be willing to yield. Not sure I like it. Interesting thought experiment though. I imagine some GC languages do exactly this.

I mean, what you're asking for is just profiling, but only of your async methods. I'm not familiar enough with the details to predict how async messes with profilers, so maybe it'd need support. But using a flamegraph profiler would show a big chunk of time in a function that only has small amounts of time spent deeper in the stack.

No, but if that library claims to be an async library, wouldn't that be a bug in the library?

Edit: I'm interpreting your use of sync here as "blocking" and not as Sync in Rust, meaning safe to share across threads. To be clear in my initial response I was talking about shared memory across threads, and may have misunderstood your original statement.

Yes. And I want the language to use types and compilers to eliminate that whole class of bugs.

I'm not sure this is really possible. Given that async programming is cooperative by nature, how do you tell the difference between a blocking IO task, and a really long running loop in a piece of code that is itself blocking others from executing because it's doing too much work?

The blocking IO might be something in Rust that a type could be created for to denote that they are not async, and therefor warn you in some way, but I think that one is easy to detect in testing.

> I think that one is easy to detect in testing

I have seen that not detected in testing too many times. With a work stealing execution context the code will still run fine unless under heavy load (which will exhaust the thread pool and lock the application).

“Non-blocking” code is basically just code that takes a short enough amount of time that we don’t care that it blocks the thread. It’s inherently a matter of judgement.

Static analysis should help with this. Basically it should identify every call site where I/O happens (and other syscalls), and then you have to check them that they are invoked with the right async/nonblocking dance.

This is basically a code audit problem.

Of course something like taint analysis could also work. Every such callsite should be counted as tainted unless it gets wrapped with something that's whitelisted (or uses the right marker type wrapper).

Even effects as types can't help much, because the basic interfere to the kernels (Linux, WinNT, etc.) are not typesafe, and as long as the language provides FFI/syscall interfaces you have to audit/trust the codebase/ecosystem.

There are two ways a language can help

1. A performant "i/o" layer in the standard library that allows a large number of concurrent activity (forget thread vs coroutine differences).

2. Ability of programmer to express concurrency. Ideally, this has nothing to do with "I/O". If I am doing two calculations and both can run simultaneously, I should be able to represent that. Similarly for wait/join.

Explicitly marking a thread as async-only will just force everyone else (who need sync and cannot track/return a promise/callback to their caller) write a wrapper around it for no reason.

The alternative is to write SansI/O code (https://sans-io.readthedocs.io/), so that your program don't have to think about that.

Besides, you don't have to put async/await everywhere: if your code is not performing IO, it completely ignore this concern.

The problem is that most of your code is mixing I/O and non I/O code, and people just don't think about it. E.G: a django website is not just a web server, but has also plenty of calls to the session store, the cache backend, the ORM, etc.

Now you could argue that the compiler/interpreter is supposed to hide the sync/async choice to the code user. Unfortunately, this hides where the concurrency happens, and things have dependencies on each others. Some are exclusive, some must follow each others, some can be parallel but must all finish together at some points, some access concurrent resources...

You must have control over all that, and for that to happen, you can either:

- have guard code around each place you expect concurrency. This is what we do with threads, and it sucks. Locking is hard, and you always miss some race condition because it can switch anywhere. - have implicit but official switch points and silos you must know by heart. This is what gevent does. It's great for small systems, not so much at scale. - have explicit switch points and silos: async/await, promises, go-routine. This is tedious to write, but the dangerous spots are very clear and it forces you to think about concurrency upfront.

The last one is the least worse system we managed to write.

> this is still explicit/userland asynchronous programming: If anything down the callstack is synchronous, it blocks everything. This requires every components of a program, including every dependency, to be specifically designed for this kind of concurency.

Welcome to the 1980s world of cooperative multitasking, but now with "multi-colored functions."

Or just use a preemptive scheduler (such as a regular OS scheduler). Or just be explicit, and take difficulties with being explicit as an indication that the data flow is maybe not very well designed.

I don't know, maybe there are valid applications for await (such as much frequented web servers, where you might want to have 10s of thousands of connections, that would be too expensive to model as regular threads, but still you just want to get some cheap persistence of state and it's not a big problem that the state is lost on server reboot). I can't say, I'm not in web dev.

But I bet it's much more common that await is simply a little overhyped and often one of the other options (real threads or explicit state data structures) is actually a better choice.

> Or just use a preemptive scheduler (such as a regular OS scheduler).

Well... I can't help but whenever I see the await stuff it reminds me of times where I had to do cooperative multitasking and was longing for OS and/or CPU support for something which is non-invasive to my algorithms. But then I'm not sure whether I'm the grumpy old man or it is just history repeating.

await allows to write concurrent (for IO) or parallel (for CPU) code like it was serial.

The issue it solves is programmer having trouble executing parallel code in their head, and when relationship became intricate (a computation graph) they just breakdown and write buggy software.

A scheduler is targeted at use cases. A preemptive scheduler optimize for latency and fairness and would apply for real-time (say live audio/video work or games) but for most other use cases you want to optimize for throughput.

With real thread you risk oversubscription or you risk not getting enough work hence the task abstractions and a runtime that multiplex and schedule all those tasks on OS threads. Explicit state data structure is the bane of multithreading, you want to avoid state, it creates contention point, requires synchronization primitives, is hard to test. The beauty of futures is that you create an implicit state machine without a state.

You don't need await for data (CPU) parallelism. You'd typically use something like https://github.com/rayon-rs/rayon or OpenMP instead.

OpenMP does not handle nested parallelism.

Compute-bound parallelism is not always data parallelism, for example a tree search algorithm would need to spawn/async on each tree nodes.

You can't "avoid state". State is essential to any computation.

The only question is, can you express some of the state-relations as serial code? If "relationships became intricate (a computation graph)", chances are, you shouldn't use serial code anymore, because that splits dependencies in a two-class society: those that are expressed using code and those that are expressed using dead data. It is usually preferable to specify everything as dead data if the relationships get complex, and to then code sort of a virtual machine that "executes" the data.

So it's in fact the simple cases that lend themselves to being expressed as serial code. I won't argue with that there are nice looking example usages. Problem is, as always, systems that help making the simple things easy often make the hard things impossible.

Haskell avoids state.

When I say state I meant "shared state" is the bane of multithreading. Amdahl's law show that if 95% of your code is parallel you limit your speedup to 20x even with thousands of cores, any shared state contribute to those 5%.

> Haskell avoids state.

That's a myth. You need state for computation. It's not a language issue. You need just as much state in Haskell as you need in other languages. In Haskell you just specify each little component as a function which takes as a parameter what is effectively global state.

Which, by the way, is usually a bad idea because it causes so much boilerplate. Plus, it makes it unclear how many instances of a given concept can actually exist in a running program.

Isn't this the most convenient setup though? I'm most familiar with async/await in UI programming and you most often have a main thread for synchronization. You want to assume that most of your main thread work is synchronous and non-yielding until you explicitly yield. Seems like it would be a lot harder to use main thread synchronization in the style your suggesting.

Maybe I just can't imagine it. Whats a good language that shows off the style you're suggesting?

>Whats a good language that shows off the style you're suggesting? javascript.

What you describe sounds like native UI work since forever before javascript. "Don't block the main thread" and all that.

Javascript is diferent in that it's a single-thread with an event loop. Synchronous functions execute until they end. Asynchronous functions are handled by the event loop which "loops" between the pool and runs each one for some time, then switches to other, concurrenly (think round robin). What happens when the runtime is running an asynchronous function and inside it reaches a synchronous one? it stops round-robin and executes this function until it ends.

What OP wants is a language like javascript but without having to write code distinguishing synchronous and asynchronous functions and instead having some other tool to tell the runtime when a function is synchronous or asynchronous without having to write it again.

Yes, I realize all this. My question is how you can have such a system and still keep UI thread synchronization without having the opposite problem of marking all your synchronous methods.

in a strict language? I don't think it's possible. Because if you take a better look you'll see that it's not enough to mark functions as sync or async since inside the functions each line of code can be considered a synchronous function in it's own.

What you want is something like Haskell that's lazy and its not about "executing statements" but rather "evaluting expressions".

Not the OP, but Go doesn't have this problem because all I/O is async under the hood, but it exposes a sync interface. This means the entire Go ecosystem is bought into a single concurrency model and runtime, which some find irksome, but it works pretty well most of the time. Of course, Go also lacks Rust's static safety features, but I think that's orthogonal to its concurrency approach.

We tried this in Rust and found it was slower than 1:1 threading.

What you tried wasn't "this", though. It was one particular implementation of lightweight threading that has to cope with Rust's peculiarities, special requirements and compilation targets. There is absolutely nothing essential about lightweight threads that prevents them from emitting essentially the same code as the stackless-coroutine approach. It's just that in Rust it might be very hard or even not worth it, given the language's target audience.

I don't understand what your objection is. It's a given that what I wrote applies to Rust. This is a thread about Rust. I didn't say that M:N threading is always slower than 1:1.

Besides, fibers don't emit essentially the same code as async code. One has a stack, and the other doesn't. That's a significant difference.

If the stack could be sufficiently small, it's not that different from heap allocated async state. But you probably needs segmented stacks, or at least separate stack async preemptible or non-async-preemptible code (has anyone tried making a system like this?)

It's isn't a given that M:N threading is slower than 1:1 threading even in Rust. A particular implementation you tried exhibited that behavior.

> One has a stack, and the other doesn't. That's a significant difference.

They both have some memory area to which they write state. Calling it "a stack" refers to the abstraction in the programmer's mind, not to how the memory is actually written/read. It is true that in order to support recursion, a thread might need to dynamically allocate memory, but so would async/await, except it'll make it more explicit.

> It's isn't a given that M:N threading is slower than 1:1 threading even in Rust. A particular implementation you tried exhibited that behavior.

I don't see any way around the problems of segmented stacks and FFI. There is no way to implement stack growth by reallocating stacks and rewriting pointers in Rust, even in theory. It would break too much code: there is a lot of unsafe (and even safe!) code out there that assumes that stack pointer addresses are stable. In fact, async/await in Rust had to introduce a new explicit pinning concept in order to solve this exact problem while remaining backwards compatible. And when calling the FFI, you have to switch to a big stack, which was an insurmountable performance problem. Rust code by its nature is FFI-heavy; it's part of the niche that Rust finds itself in.

You can make what are virtually zero-cost copies from what you call a "big stack" to a resizable stack with virtual memory tricks. You don't even need to copy the entire stack, but cleverly rewrite the return address stored on the stack to do this kind of "code-switching". But it does mean doing backend manipulations in a platform-dependent way. There are several good ways to do this, none of them particularly easy. What is perhaps impossible is allowing FFI code to block the lightweight thread, but async/await doesn't solve this, either.

> You can make what are virtually zero-cost copies from what you call a "big stack" to a resizable stack with virtual memory tricks. You don't even need to copy the entire stack, but cleverly rewrite the return address stored on the stack to do this kind of "code-switching".

We tried it. It was too slow.

OK. It really is hard when you're what you call "FFI-heavy" and don't like a significant runtime. So Rust has several * self-imposed* constraints (whether they're all essential for its target domains is a separate discussion, but some of those constraints certainly are) that makes this task particularly hard, but my point is that there is nothing fundamental to n:m threading that makes it slower than async/await, and async/await does fundamentally come at the significant cost of a particularly viral form of accidental complexity.

Fibers under the magnifying glass [1] might be a relevant paper here. Its conclusion, after surveying many different implementations, is that lightweight threads are slower than stack less coroutines.

[1]: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p136...

No, its conclusion is that fibers with certain properties in C/C++ are slower -- and particularly hard to implement correctly -- than stackless coroutines in C/C++. That's because of the particular characteristics of those languages. In fact, you'll note that the only negative thing he says about Go is that it incurs an overhead when interacting with non-Go code.

And that overhead is a deal-breaker in Rust.

Sure, but that overhead is also not essential, but a feature of Go's particular implementation. Fibers aren't one thing and there are many, many ways of implementing them. As I said before, implementing them for Rust well would have likely required changes to LLVM and Web Assembly, and even then it would be harder than async/await, perhaps to the point of being too hard to be worth it and probably against aspects of Rust's philosophy (I would say that that is the main difference between the two: achieving similar performance is much easier for the language implementors with async/await). But it's just not true that there is something essential about them that makes them slower. After all, you're running all of your code inside a particular implementation of threads.

> Sure, but that overhead is also not essential, but a feature of Go's particular implementation.

The only way to get around the FFI performance problem would be for all fibers to have big stacks. At that point you've thrown away their biggest selling points: high scalability and fast spawning.

> The only way to get around the FFI performance problem would be for all fibers to have big stacks.

I don't know all of Rust's specific constraints, but it is not the case in general. There are two levels for FFI support in this context, based on whether you want to allow FFI to block the lightweight thread (perhaps through an upcall), or not. Only if you want to allow that do you need "big stacks", but even then they can be "virtually big" but "physically small". If you don't, then all you need to do is to temporarily run FFI code on a "big stack", but you know that all the FFI frames are gone by the time you want to block. Depending on your FFI, if you don't allow the FFI code to hold pointers into you language's stack, you're all good.

> Depending on your FFI, if you don't allow the FFI code to hold pointers into you language's stack, you're all good.

Rust does this with virtually all FFI.

It's not that crazy. There's an async ecosystem of libraries, you opt in to using them, if you run a blocking method inside an executor then you obviously pay the cost for that. Granted most executors run on multiple threads so you'd only be blocking one thread.

Still, in practice it's just not that hard, use async methods if you're writing async code.

Is it a single threaded state machine?

> Async I/O gives awesome performance

No, it doesn't really. 'Async' is a strictly Python problem, due to the insanity of the GIL. Predictably, the Python solution to it is also insane.

Why you have to turn a sane language like Rust into an insane one by cargo-culting a solution to a non-problem is a mystery to me.

Oh well, good thing at least C++ hasn't dropped the ball.

It’s important to distinguish 3 categories of coroutine implementations: stackful, stackless-on-heap, stackless-as-struct. C++ is stackless-on-heap. Stackless-as-struct is essentially creating an anonymous type (ala lambda), used to save the data across suspension points. This is the approach taken by Rust for its async/await implementation. I believe there were declaration/definition and ABI concerns about this approach for C++:

> "While it is theoretically not an insurmountable challenge , it might be a major re-engineering effort to the front-end structure and experts on two compiler front ends (Clang, EDG) have indicated that this is not a practical approach."

So the short answer seems to be that due to technical debt on the part of existing C++ compilers and their "straight" pipeline, the front-end cannot anticipate the size necessary for some book-keeping information traditionally handled by the code-generator. I'll take Richard Smith's word on Clang.

You are mixing up a lot of stuff here.

- Asynchronous programming is completely orthogonal to Python

- If you don't need it, don't use it. Rust without asynchronous functions still looks and works like before

- By the way: welcome to C++20's coroutines

> - Asynchronous programming is completely orthogonal to Python

Theoretically, yes. In practice, people are just copying Python mistakes word-for-word, in an attempt to score the "coolness" factor that async garnered in the Python community. (Never mind that the "coolness" came from solving a problem that doesn't even exist in other languages...)

If you want to see what asynchronous programming would look like if it weren't copied from Python, look at the recent C++ proposal.

> - If you don't need it, don't use it. Rust without asynchronous functions still looks and works like before

The problem is that every Python library now comes in two versions, regular and 'async'. Even if you don't need or care about anything 'async'.

I guess splintering your code base into two incompatible flavors is just the pythonic way of doing things? Now that the 2 vs 3 insanity is finally dying down, they needed to start a fresh one?

Why is Rust trying hard to repeat these mistakes?

> - By the way: welcome to C++20's coroutines

That I already answered above.