Drazen Dotlic is a Windows C++ software architect who lives in France. He can be contacted at http://drazen.dotlic.name.
Operations such as loading web pages, fetching data from databases, or crunching numbers are usually performed in the background, so as not to disturb the responsiveness of running applications. This is typically done by creating a separate thread. However, if you have many operations throughout the execution of your application, you should consider using asynchronous function calls. Asynchronous calls return immediately (usually giving back handle-like call identifiers), execute on a thread separate from all other threads, and deliver results to your callback function once they're done. The .NET Framework supports asynchronous programming via delegates—type-safe function wrappers.
Listing 1 illustrates an asynchronous delegate in C#. Every call consists of two phases—initiating the call and getting the result value. BeginInvoke initiates the call, immediately returning IAsyncResult. Its signature is identical to the signature of the target function, plus two more parameters. The first references the AsyncCallback delegate receiving the result value, and the second references the object with additional state information, also saved as IAsyncResult.AsyncState (both can be null). EndInvoke returns the result value, using IAsyncResult to identify the call. One delegate can be invoked several times, and the order of execution of these calls is not guaranteed to be the same as the invocation order.
Calls 1-3 block waiting for the result value, either by calling delegates EndInvoke and IAsyncResult.WaitOne(), or by looping on the IAsyncResult.IsCompleted flag. Call 4 provides ResultCallback to get the result value, and delegate itself as AsyncState. All calls execute on a thread from a thread pool separate from any of your threads, including a call to ResultCallback. It is up to you to ensure that your shared data is thread-safe. For calls 1-3, I could have opted to ignore the result completely, which is useful for fire-and-forget scenarios.
C++ Implementation
Instead of inventing a unique mechanism for asynchronous call support in C++, I decided to mimic .NET delegates. My goal was to have a portable, pure C++ solution with the syntax and behavior as close as possible to the .NET approach. It turns out this is not too difficult, thanks to Boost (http://www.boost.org/). My code depends on Boost 1.31, the version available at the time of this writing. Since there are no other dependencies, my implementation should be quite portable, and I've successfully tested it under GCC 3.3.1 and Microsoft Visual C++ 7.1. The complete source is available at http://www.cuj.com/code/.
At the outset, I decided not to sacrifice type safety just to adhere to .NET's approach. Consequently, my first departure was not to use (synchronous) delegates for result callbacks—good old-fashioned pointers to objects implementing an interface is good enough. (For a discussion of delegates with synchronous call semantics in C++, see [1].) Besides, I wanted to focus on the asynchronous aspects of delegates.
The second difference in my implementation is that the last parameter of BeginInvoke (AsyncState) ends up being used mainly to send the delegate itself to the result callback, but only so that you can access the result value. Therefore, I removed AsyncState and modified the result callback signature to accept the result value directly.
C++ Use
In Listing 2, which shows my C++ delegate class in action, a typedef resembles the .NET delegate declaration. Since you can't have pointers to member functions of an object in C++, delegate accepts the pointer to the object and a pointer to the member function of a class of that object. The rest of Listing 2 demonstrates the same features as Listing 1.
Figure 1 provides an overview of the participating objects. When delegate is invoked, an instance of one call is created using an internal factory. Delegate stores a call pointer in an asynchronous result and queues it in a work queue—a thread-safe container for calls. The thread pool pulls calls from the work queue one by one and invokes them on private threads. In turn, this invokes the function wrapped by the call. Meanwhile, the asynchronous result is returned from delegate and can be used to track the progress of execution or to wait for the result value.
Supporting Classes
Like the .NET approach, my implementation uses a separate thread pool for asynchronous execution; see the thread_pool class in Listing 3. In the constructor, based on a sole input parameter (threads), the number of threads is created and kept in boost::thread_group. A thread function for all these threads (thread_func) loops, getting items from a work_queue (which is where pending asynchronous calls are kept) and executes (invokes) them. To avoid a rogue function's exception thrown to crash a thread from the pool, all exceptions are caught and ignored. Normally, when there is no work, thread_func expects calling work_queue::dequeue_item to (efficiently) block. To tell pool threads to shutdown, fake asynchronous calls in the destructor of thread_pool are queued (as many last_call objects as there are threads executing), whose only purpose is to return false when invoked—a signal to stop processing. After that, I call boost::thread_group::join_all, which blocks until all threads of a group finish executing. The call queue is FIFO and the pool does not destruct until all previously scheduled calls are executed.
The call queue is implemented in the work_queue class (Listing 4), and demonstrates a simple form of the Monitor pattern (http:// www.boost.org/libs/thread/doc/bibliography.html). It is also a Singleton with only two public methods—one for adding and another for removing items from the queue (represented by std::list). To avoid unnecessary copying, only boost::shared_ptr pointers to calls in the list are kept, with a goal to allocate calls only once. boost::shared_ptr is a reference-counted smart pointer. It is safe to keep in containers, and similar to std::auto_ptr—it deletes owned objects once the reference count reaches zero. Both public methods of work_queue are made thread-safe by using (internal) boost::mutex wrapped with boost::mutex::scoped_lock, which releases the lock after execution leaves the scope. However, dequeue_item needs to block when there are no items in the queue. That's what boost::condition is used for—it is a thread primitive that accepts any lock (in this case, scoped_lock) and functor (not_empty, which returns true when the queue is not empty). When constructed, condition releases the lock it was given and waits (efficiently blocking the current thread) for the signal to continue. This signal should come from another thread in the form of a notify_one/notify_all member function—the former resumes execution of one waiting condition (blocking on some other thread), and the latter resumes all. In this case, notify_one is called from queue_item immediately after the new item (call) has been added, signaling that it can be dequeued. If there is no thread waiting on the condition, calling notify_one/notify_all does not have any effect. Functor protects from corner cases to ensure that the condition should continue. work_queue does not do any processing on its own—it is just a thread-safe container for pending asynchronous calls.
Both thread_pool and work_queue work with simple_call objects (Listing 5). This is a simplified representation of a pending call, stripped of any kind of concrete parameters or return value of the underlying call. Its members are mostly self explanatory—invoke executes the target function, is_completed is true after the execution, and wait_completion blocks until execution is completed. The last two members work together—clone is called to make a copy of any object that implements make_clone. This lets you clone objects derived from simple_call using only a clone (static) method—a technique identical to (and borrowed from) Loki Functor cloning [2]. None of the code up to now deals with delegates, and it is indeed possible to use thread_pool and work_queue to work with any other class that implements simple_call.
Delegate Implementation
An asynchronous delegate is essentially a generalized functor with delayed execution that optionally delivers a result value through a callback. Delivery of the result value is the duty of the dispatcher template derived from simple_call. Its only template parameter is the type of the return value. It declares a pure virtual method called result that returns the result value, and defines the method deliver_to that stores a pointer to the implementation of async_callback. If you want to get a result value through the callback, just derive from async_callback and implement its only method accept_result. Furthermore, the generalized functor aspect is implemented with the callable interface. The design is, again, strongly influenced by the Loki Functor. The target function signature, consisting of a return value and parameters, is modeled on a template with two type parameters—the return value type and the type list for parameter types (type lists manipulation uses boost::mpl, a powerful library that allows compile-time operations on a container of types as if it was an std::list of types). The template is then specialized for the number of parameters: 0, 1, 2... Each specialization has a (pure virtual) operator() with exactly the same parameters (and in the same order) as in the parameter type list. This is identical to the order and parameters of the target function. callable derives from dispatcher, templated by the (known at this point) return value type.
Delayed execution is handled by delegate_impl (Listing 6), templated by the delegate, the pointer to the object and the pointer to the member function of a class of the same object. It forwards a return value type and a parameter type list to callable (from which it derives), expecting these types to be inner typedefs of a delegate. The constructor expects a concrete pointer to the object and member functions of a class, storing them internally. Every operator() from all specializations of callable is implemented here, but this will not lead to a call bloat—only one "correct" member is instantiated, the one matching parameter type list. It is in operator() that everything fits together—parameter values, return value types, and member functions of an object are bound using boost::bind (similar to std::bind, only providing generalized binding with more than two parameters). boost::bind returns an unspecified class that behaves like a function with no parameters that, when called, forwards the call to an embedded (in this case) member function of an object with bound parameters. This is further wrapped in another generalized functor, boost::function (forwarder) with no parameters and a return type identical to target function result value type. This makes delayed calling both possible and simple. There are other (pure) virtual methods of inherited classes to implement, starting with simple_call:
- make_clone returns a copy with the same pointer to an object and member function of a class. This makes any delegate_impl-specific class a factory of itself.
- invoke calls through forwarder, stores a return value to internal _result and, using scoped_lock on internal mutex, blocks code in other threads until execution is finished. This function is called exclusively in the context of one of the threads in the thread pool, and declares the execution as finished by setting the internal Boolean flag (_done) to true. Then, internal condition _completed is signaled (using notify_all because you might wait for completion in more than one thread) and if a pointer to async_callback was provided, the return value is delivered through it.
- is_completed returns _done, signifying finished execution.
- wait_completion is using scoped_lock on the same internal mutex as invoke, making sure to block until execution is finished; if lock was acquired and _done is true, it returns immediately; otherwise, it blocks on _completed (which will be eventually signaled by invoke).
- result just returns the return value.
delegate_impl ultimately represents one call. Also, I make assumptions without which the code won't work correctly—invoke and wait_completion should execute on different threads, result should not be called until invoke has finished, and invoke should be called after operator() has been called. All of this is orchestrated in delegate, a class that is exposed to you.
All that is left is to implement the delegate. It is a template with two type parameters—a return value type and a type list for parameter types (Listing 7). Each parameter from the parameter type list is extracted using the metafunction at_v (essentially a compile-time if). For each position (1,2,3...), types p1, p2, and p3 are generated. I could have put return value type in the same list with parameters, but this way it resembles a function signature better. The constructor of delegate is templated by a pointer to an object (ptr_obj) and a member function of a class of that same object (mem_fun). It is this member function that is eventually called, and its signature must match what delegate's template parameters say. The only thing that happens here is that an instance of delegate_impl, called _impl_factory, is created. This object will produce other delegate_impl objects with the same ptr_obj and mem_fun as passed in the constructor. There are two reasons for this: Type information on ptr_obj and mem_fun is lost after the constructor is executed. Another reason for a factory is that the same delegate can be called multiple times, so for each of the calls we need to produce one instance of delegate_impl.
The only two public members of delegate are begin_invoke and end_invoke. Similar to delegate_impl, there is one begin_invoke for 0,1,2... parameters. Again, this might look like a code bloat, but because delegate is a template, only one (the "right") begin_invoke gets instantiated for each call (or if there is no match, you get a compilation error). Along with the parameters for a target function, begin_invoke optionally accepts a pointer to the object that implements the async_callback interface. Every begin_invoke does three things. First, a new delegate_impl is created (from now on referred to simply as a call), using the previously mentioned cloning technique with _impl_factory. If a pointer to the async_callback was provided, it is stored in the call using deliver_to. Result is further cast to callable so that operator() can be called, and binding is performed. A new item is queued up and stored internally in a list of calls and async_result, which wraps the newly created call, is returned. Mostly, async_result only delegates work to a wrapped call—is_completed forwards to delegate_ impl::is_completed and wait forwards to delegate_impl::wait_ completion. Also, async_result befriends delegate so that it can return a wrapped call through the private member get_call. It is in the end_invoke that everything fits together. The call is taken from async_result and checked if it is on the list of items generated from this delegate; if not, bad_async_result is thrown. If the call is owned, wait_completion is called and, when finished, the return value is provided through result. So, the delegate public interface, meant to be called from your threads, satisfies all assumptions about delegate_impl usage. On the other hand, invoke gets called only from thread pool threads, exactly as needed.
Improvements and Discussion
An unexpected result of my approach is that if some of the parameters for the target function are references, then the value, if changed in your target function, will not be changed through the referenced variable. Due to the forwarding problem (http://std.dkuug.dk/jtc1/ sc22/wg21/docs/papers/2002/n1385.htm), there is no perfect way to bind the arguments (that are references) correctly in all circumstances. Consequently, I let boost::bind do its default—make a copy of all arguments passed. If you want changes to parameters in the target function to persist, use a pointer.
Another complicated problem is catching exceptions thrown by target functions, and possibly forwarding them into the context of your threads by storing and delivering them to you along with the return value in accept_result. Thus, the thread pool ends up catching all exceptions, including access violations (null pointer usage, for example), but the alternative ("advanced") solution would obscure the point of the article too much.
You might also tweak thread_pool to increase/decrease the number of worker threads based on the number of pending calls/busy threads, but this also was left out for simplicity.
Finally, you might want to wrap calls to free functions, or even other functors, and not just the member function of an object. This would require changing delegate and delegate_impl a bit, but it should not be too complicated.
References
- [1] Smith, Daniel J. "Inside .NET's Delegates and Events Using C++," CUJ, September 2002.
- [2] http://sf.net/projects/loki-lib, from Modern C++ Design, by Andrei Alexandrescu, Addison-Wesley, 2001.
