[cpp-threads] Asynchronous Execution Issues (caching_async)

[Robison, Arch]

The experience with TBB strongly supports Herb's point: users need both. For the first few years of TBB, we offered only work stealing, and users kept asking us for true asynchrony too.  (Now TBB offers the latter via an approximation of std::thread).

A key lesson from Cilk is that it's not just about granularity.  The choice of schedule can profoundly affect the asymptotic space behavior of a program.  For example, Cilk-style scheduling often delivers space bounds linear in the number of processors, whereas the equivalent code using true asynchrony can have exponential space blowup.  (Think depth-first versus breadth-first.)
  
Worse, "both" is probably not enough.  Cilk-style scheduling is great for a certain class of problems, but there are other problems (e.g. stream processing) where FIFO-like scheduling makes more sense.  Beman Dawes suggestion of a more generic approach is worth investigating.

To make non-preemptive schedulers useful, users have to understand their limitations, particularly with respect to deadlock.  For example, it's overly simplistic to require that one caching_async() call never wait on another.  At a minimum, I want a function being executed by a cached_async() call to be able to execute another cached_async() call and wait on the result.  Invariably users want to do more complex work graphs.   

Thus I'm skeptical that caching_async can be both widely useful and avoid the hard issues of a thread pool. 

- Arch Robison (TBB architect)

 -----Original Message-----
From: cpp-threads-bounces at decadentplace.org.uk [mailto:cpp-threads-bounces at decadentplace.org.uk] On Behalf Of Herb Sutter
Sent: Tuesday, April 28, 2009 7:37 PM
To: C++ threads standardisation
Subject: Re: [cpp-threads] Asynchronous Execution Issues (caching_async)

Just to repeat my $0.02 that I've been saying since the Kona meeting:

1. It is highly desirable to have an async() that is not guaranteed to run on a different thread, for exactly the reasons Hans mentioned -- enabling the new breed of work-stealing implementations that have significantly better performance and will be widespread in the next small number of years (Intel TBB, Java Fork/Join, Cilk++, and three Microsoft products (PPL for C++, TPL and PLINQ for .NET).

2. But semantically you also want I understand why it's also desirable to have an async()

Without #1, we don't support efficient parallel computation (at least, no longer competitive with current industry practice). Without #2, you don't support asynchrony/concurrency such as getting work off a GUI thread to run in the background. #1 can't be used for concurrency, and #2 can't efficiently be used for parallelism. That's why you want both, and the user needs to be able to spell both.

Herb