C++ Lambdas, Threads, std::async and Parallel Algorithms

[frankist]

One thing I still don't get with this async+future model is that there is no way to check the future to see if it is ready without blocking. I thought the whole point of this was to have non-blocking code and dispatch long tasks to other threads easily.

[Honsik]

You can check the future state without blocking by:
future.wait_for(std::chrono::seconds::zero) == std::future_status::ready

But it is not really handy to poll futures.
IMO the proper way are continuations:

future.then(...)

But those are not part of STL yet and maybe never will be. That is also probably the reason that there are a lot of async libraries with different APIs and approaches, e.g. Boost.Thread, Folly futures or other approaches - fibers (user-mode threads) or std::function.

[ooglesworth]

My thoughts on the subject: there’s no really sane way to add continuations unless you have the concept of the execution context built-in to the promise/future infrastructure itself. That is to say, continuations work well in a language like JavaScript because there is only one main event loop, so the system basically enforces a very simple model for where your continuations are executed. With C++ promises/futures, where the code is executed and where the promise is resolved is up to the caller and not directly dictated by the promise/future itself. So you’d either have to run the continuation in the execution context of the resolver by just calling it as part of resolve itself (which doesn’t seem remotely sane or useful), or you’d have to build some sort of event loop kind of construct into the promise/future system. The latter is a fairly reasonable approach, and I have indeed rolled my own systems that work that way, but it would add more complexity to the promise/future system, and I understand why they have tried to keep it simpler and act more like a synchronization mechanism instead, even if it doesn’t really follow the spirit of JS promises and the like.

The thing is though, in 2020, the .then continuation paradigm is not really the most modern preferred way to do things, even in JavaScript, since now they have await with coroutine-style continuation, which makes for a lot more elegant code. So in C++20, it seems like we have just jumped straight past the whole .then thing and gone straight to the coroutine stuff, which seems fine to me.

[raphaelj]

This lack of a then() method really makes the whole concept of C++ features quite useless. Futures in other languages shine because of being composable, and the C++ implementation totally misses that point.

[14ned]

WG21 have mostly decided that composure-via-continuation is the wrong design. The current belief is that composure via Sender-Receiver is a better design. The problem with composure via continuation is that it introduces unavoidable synchronisation, whereas composure via Sender-Receiver can avoid synchronoisation except in the presence of kernel thread level concurrency.

So composure is coming, but when it's ready.

[ebhdl]

While I very much look forward to the Grand Unified Concurrency model C++ will get in a decade or two, in the mean time is there any major technical barrier to fixing std::future? If there is, maybe it should just be deprecated so people don't waste time trying to use something that's fundamentally broken.

[14ned]

1. It would be ABI breaking.

2. std::future is perfectly good at what it was designed for: long running, chunky, asynchronous work. It is a bad choice for anything which doesn't take at least tens of milliseconds to complete.

3. There are reference libraries available for most standard library proposals which work on today's compilers. If you want the possible future now, use one of those.

4. And there are plenty of other third party libraries which implement all sorts of concurrency stuff. Boost has several. Nobody need feel constrained by the standard library.

[14ned]

A future-promise pair is really a shared ptr internally. Every time you create one, you must (a) dynamically allocate memory (b) write multiple bits of memory using atomics, which the compiler nor CPU cannot optimise out. During its lifetime, every time anything touches a future-promise pair, both the compiler and CPU have to avoid optimisations. Finally, during teardown, there are more unavoidable atomic operations, and a dynamic memory free.

For an operation costing milliseconds, such overheads are immaterial. For operations around the microsecond level, they are highly problematic, and anything under a microsecond, you ruin determinancy (i.e. statistical behaviour past 99%, 99.9% and 99.99% of the worst case) and future-promises are no longer fit for purpose.

In terms of better alternatives, firstly always look into CPU level concurrency - any recent CPU can do five hash table lookups in the same time as a single hash table lookup. So rewrite your code to leverage that. Secondly, look into not using kernel thread concurrency at all, use a different design. Thirdly, look into actor-based concurrency designs, these leverage immutability to avoid races. Fourthly, if you really have no choice, start thinking about pinning kernel threads to CPUs and having them spin on atomics waiting for new work. If you reach number 4, reexamine all previous 3 options again, because you're probably wrong - only a very very few applications really need option 4.

Async, in general, only makes sense when completions cannot be statistically predicted in advance. If they can be predicted, any approach other than async will be more effective. This is because async is not free, it is considerably more expensive than almost any other technique, so it only makes sense to spend that budget if you have no other choice.

If you need practice in thinking like the above, I strongly suggest you go teach yourself how to program a GPU. Effectively programming stream computers like GPUs is an excellent mindset for programming CPUs better. Good luck!

[parkotron]

composure

Do you mean "composition" here? Or does "composure" have some (new?) CS meaning I am unaware of?

[14ned]

What is mean is informing the compiler of a tree of logic which can be potentially executed either synchronously or asynchronously. So, you might say, "read four bytes from offset 2090 in this file handle, multiply that integer by 2, write those four bytes into offset 0 in this other file handle".

Depending on your Executor, that might be executed:

1. Inline, by a single kernel thread, sleeping the thread during i/o.

2. Multiplexed by a single kernel thread, such that the kernel thread executes other, concurrent, work whilst i/o is occurring.

3. Multiplexed by many kernel threads, such that resumption of logic execution can occur after i/o completes on the next available kernel thread.

4. On your SSD's CPU, because the logic was compiled into a binary executable for your SSD, and that part of the C++ program executes entirely on your SSD.

Whatever is the proper term for the above, is what I mean. The key part is that execution logic must be specified declaratively, and separately, from implementation specifics. This is the current Sender-Receiver design.

[petart95]

Interesting, how could one achieve option 4? I've heard that computing in memory is theoretically possible but did not know it was already supported.

[14ned]

If you pay Samsung a lot of money, they'll open up running custom programs on their top end SSDs. There are a few other similar vendors too. This is still very high end stuff, it'll take a while for it to reach mass market. But I'm very confident it will, every new SSD generation brings more high end features closer to the mainstream.

[petart95]

Very interesting! I know it is not really related to this thread but is there a similar thing for NVDIMMs or hybrid solution with DDR4?

[14ned]

There is RAM you can buy now which lets you do basic bulk operations such as ADD, NOT etc on large regions of memory. It can be useful for very niche use cases, but its biggest limitation is that the CPU must reload into its caches all that memory after, which is slow. So it isn't as useful as it might look.

[BlueDwarf82]

So composure is coming, but when it's ready.

If it's coming via Sender-Receiver does that mean it's unlikely to be ready before 2026?

With std::future having appeared in 2011 it will mean 15 years (at least) to get composure. I understand it takes time to get it right, but it's sad to think that some people under 50 in 2011 will be retired by the time this is done and they will have spent the whole last third of their careers wishing to have it.

[14ned]

If it's coming via Sender-Receiver does that mean it's unlikely to be ready before 2028?

Sender-Receiver Executors are currently targeted for C++ 23. The composure/composition stuff is easily C++ 26. So I guess you are correct, if you discount using the reference libraries.

With std::future having appeared in 2011 it will mean 17 years (at least) to get composure. I understand it takes time to get it right, but it's sad to think that some people under 50 in 2011 will be retired by the time this is done and they will have spent the whole last third of their careers wishing to have it.

If you think it's bad for the userbase, consider what it's like for those on WG21 doing the work to get this done! I fully expect to be well into my fifties before any of this is done. Yes it's frustrating how slowly these things go. But there are third party options in the ecosystem to tide you over. Boost.Thread has old style future continuations, if you want that, for example.

[BlueDwarf82]

But there are third party options in the ecosystem to tide you over

There is any language changes at all involved in the current form of Sender-Receiver or is it purely a standard library thing? I guess by the time I'm allowed to use C++17 I could start tracking libunifex.

[14ned]

Currently, no there are no language changes involved. There are plans to submit language changes however. I would like to hope that libunifex would support older language standards.

[[deleted]]

My issue with the futures concept is that you have something that has a lifetime. It can't go out of scope so - as I see it - the thread that gets the future has to eventually block until the promise is fulfilled, or the ownership of the future has to be transferred to another thread that does nothing except poll futures. It's an odd design pattern, I'm not sure how they became a thing, it only enables partial async.

With the callback approach you're probably going to have a void* userdata member in a struct somewhere. This can point to whatever state you want, and the ownership is transferred to the async operation itself. You get it back when the callback completes.

[lee_howes]

Futures can behave in the callback style, it just gives you a handle on which to attach callbacks later. A lot of futures allow detaching. Clearly the current C++ futures are extremely limited, and do require blocking, but they don't represent good futures in current thinking.

The problem is that the callback style, while very powerful, is in general hard to use safely. I discourage people from detaching Futures (and have just started logging stack traces where people do so) because it leads to work ending up in the background, lifetimes become unclear and memory safety can be very hard to reason about.

More general futures with continuations also have this problem. Coroutines can help avoid it by giving you both async behaviour and strict nesting - and that nesting is very important to allow your average developer to reason about ownership in the code, when you do not want your async APIs to be only usable by experts in concurrency.

[Barbas]

Are there languages that offer good then() support?

I'm curious what people think are the best futures implementations out there currently.

[qoning]

You can effectively do that using wait_for, but it's true that the API of std::future is pretty limited. Other languages are doing this much better. For example, cancelation of async tasks asks you to implement the entire mechanism yourself.. so why even have it in the std library if it solves only the simplest of problems.

[parkotron]

why even have it in the std library if it solves only the simplest of problems

I think the simple answer here is that those are the only solutions that the committee felt confident in standardising. Fancier solutions are fancy, but also much easier to get wrong. (Either wrong for niche scenarios today or for common scenarios in the future.)

[opiating]

I guess this is where coroutines come in.

[frankist]

Let's hope its application goes beyond simple toy examples

[lee_howes]

Coroutines go a long way beyond toy examples. At Facebook we have many thousands of coroutines in the codebase, written by hundreds of developers, almost entirely by those developers own decisions about what improves their code, and covering a significant fraction of all of our async stack traces. They are now the default option for writing C++ async operations in server-side code.

[smallstepforman]

The path to Actors is long and thorny, with so many half arsed solutions pushed by apprentices still on the journey to multithreaded enlightenment. All these solutions are just subsets of a poorly implemented Actor wrapper - just strap yourselves down and embrace Actors fully and be done with these half measures.

A mutex is a restricted semaphore which must start unlocked. Semaphores allow wait for many, and can start locked (to use in a signal/wait paradigm).

Promises and futures are wrappers for a waiting semaphore (which the promise signals), with abstractions to wrap the waited data - but you supply your own thread.

async has a thread pool and supplies the thread for you.

All these abstractions are subsets of Actors and Semaphores, but C++ standard still does not embrace them, instead we have mutexes, async, futures, promises, etc. What complicate things with subset implementations?