Summary: As multi-core processors become more and more common amongst the
mainstream user, programmers must learn to adapt in order be able to take
advantage of such hardware by writing code which not only splits up execution
to one or two threads, but which has the ability to scale as more cores become
available. In particular, high-level facilities which ease the creation of
threads and handle synchronization implicitly in a way which eliminates the
possibility of deadlocks need to become available. Current threading libraries
such as Boost.Threads are fine for their purpose, but they are much too
low-level for the average user's needs. Algorithms which split up work to an
arbitrary number of threads can and should be just as easy to work with and
create as algorithms which run serially. As well, at a simpler level, the user
should be able to take almost any function from an existing code base and safely
make it execute asynchronously with respect to the call-site. My proposal,
Boost.Act, attempts to provide all of this functionality and more in an elegant
and easy-to-use manner.

As Herb Sutter put it, the free lunch is over:
http://www.gotw.ca/publications/concurrency-ddj.htm

Design: As was mentioned, algorithms which may split up their work amongst an
arbitrary number of threads can be just as easy to work with and create as
algorithms which run serially when given the proper tools. Boost.Act provides
such tools in the form of STL-style algorithms which can be adjusted via
policies to run either serially or in parallel. In addition to most STL
algorithms, Boost.Act also features a simplified for construct specifically
crafted to be able to calculate the number of iterations needed once algorithm
execution begins, making it easy to be implemented in a manner which creates a
predicable number of worker threads and splits up the work appropriately
dependent on the system.

Aside from parallel algorithms, Boost.Act also provides tools for executing
function objects asynchronously and for creating active types through pseudo
type qualification, not too dissimilar from existing cv-qualification. As a
reference, active types as proposed are similar in many ways to active types in
existing languages and as described by Herb Sutter in his PDC talk on
concurrency
( http://pluralsight.com/blogs/hsutter/archive/2005/10/25/15903.aspx ).

In brief, active types allow instantiations to create their own thread in which
they process a queue of all signaled functions performed on that instance. This
makes it easy for a programmer to create an object and signal operations upon it
without the call actually running in the call-site thread and still guarantees
them that the functions will all run serially with respect to the target object.
Because of this, active objects also have the benefit of easily being able to
take signals from multiple threads in a safe manner when using a thread-safe
function queue implementation.

Traditionally, active object implementations allow you to interact with the
results of function calls made upon the target object via futures which provide
you with a handle to the result. In order to access the result you force a wait
for the function to finish its execution. Boost.Act takes a unique approach in
this respect by using its own concept called an action which represents the call
being queued and allows indirect access to the result in its active qualified
form. Access to this resultant object does not force a wait, but rather lazily
creates a thread and a queue once operations upon it are signaled.
Alternatively, a wait may also be optionally forced which yields the inactive
qualified form.

Rationale: In order to conserve space in the proposal, the rationale for certain
design decisions is included with the documentation linked with the proposal or
you can get to the rationale directly by going to
http://members.gamedev.net/Rivorus/surge/html/surge_act/rationale.html

Note that in the documentation, the name Surge.Act is used as Surge is the
library collection name use for my personal projects. If the proposal were
accepted, the library would be changed to Boost.Act.

Implementation: As you may already be familiar with, an existing specification
exists for C and C++ which allows shared memory parallelism through the use of
compiler directives and libraries called OpenMP ( http://www.openmp.org ).
OpenMP is already implemented in most C++ compilers and most of those which do
not yet support it are planning to do so in the future. Because of this, OpenMP
makes for a great tool for the internal implementation of parallel algorithms.

As I mentioned in the Boost developers mailing list, I already have some of
Boost.Act implemented. Specifically, OpenMP parallel for loops are already in
place and working, as well as the policies necessary to switch between serial
and parallel execution. Actions and active types are also nearly fully
implemented for a test non-threaded policy and a version using a combination of
Boost.Threads and win32 threads is following closely behind.

Despite my efforts thus far, there is still quite a large amount to be done.
Remaining work includes creating a full set of parallelable STL algorithms,
creating a portable concurrent implementation of actions and active objects,
making a full set of active interfaces for fundamental C++ types, making
work-arounds for non-compliant compilers, easing the creation of instrinsic
functions of active qualified types, optimizing compile-times, making much more
complete documentation, and of course testing, testing, and more testing.

Obstacles: Many of the obstacles associated with this project are a part of
the design which I have already given much thought to and have described
fairly thouroughly in this proposal and in the coupled documentation.

Implementation obstacles that are currently foreseeable include coming up with a
way of allowing users to more easily create intrinsic functions of active
qualified types and making the implementation portable to non-compliant
compilers.

Some challenging implementation obstacles already past include the creation of a
custom preprocessor container type needed to simplify the creation of intrinsic
functions of active qualified types and the creation of a method which allows
optimal parameter passing which also allows for different behavior dependent on
policies being used.

Experience: I currently have about 5 years of C++ under my belt with 3 years of
extensive Boost usage. In particular, those libraries which I will be using for
Boost.Act include Boost.Threads, Boost.Preprocessor, Boost.MPL,
Boost.TypeTraits, enable_if, Boost.Lambda, Boost.Function, and Boost.Iterator to
name a few. Not only do I have experience working with Boost libraries, but I
use Boost coding guidelines in all of my personal projects so they are already
very familiar to me. I am also the coder of the preprocessor binary literal
utility.

Final Notes: Be sure to take a look at the documentation at
http://members.gamedev.net/Rivorus/surge/html/index.html . I'll change the
license at your request.

//////////
Comment from Dave Abrahams:
//////////
This is a great application. Matthew, you didn't say anything about your qualifications, although you obviously know what you're doing. I'm left with one question, however: what is your level of familiarity with the principles of generic programming, such as concepts, refinement and models, and with the techniques used to realize those principles in C++?

//////////
Update:
//////////

Thank you very much. My initial proposal met Google’s character limit exactly and I’m not sure if this update will go through or if it will be chopped off, so I am emailing it to you as well.

I consider myself to be very able to conceive of, develop, and work with projects based around generic programming. I have worked with Boost nearly every day for the past two or three years (the STL longer than that), so I not only understand the paradigm in theory, but I also have a lot of experience working intimately with it in practice.

While I did not state so explicitly in the rough documentation I put together, Boost.Act itself uses generic programming throughout the project, particularly in its algorithms, as you likely would imagine. One example which I already have implemented is existent behind-the-scenes in the “copy” and “for_each” parallelable algorithms which are used in the documentation I provided. Here, in order to easily take advantage of parallelism using parallel loops, random-access iterators are required and the function arguments should model the parallel-safe concept touched on in the documentation (a more formal description of the parallel-safe concept will be presented as the documentation becomes final). This is why I chose deques and vectors and inherit from parallel_safe in my examples. Behind the scenes, different implementations are used dependent on the iterator category of the arguments and whether the function being performed models the parallel-safe concept. I usually implement such behavior using enable_if and disable_if along with iterator traits, though I may switch over to using more traditional forms of tag-dispatch to account for compilers with broken SFINAE. In particular, I noticed in tests that MinGW has problems in some cases when “conflicting” static member function templates are created using enable_if and disable_if, which is the current method I use internally in one of my policies.

Aside from that, another example of my use of generic programming, which I will eventually go back and more formally describe in documentation, is the “actable” concept, which is modeled by active-qualified types and Boost.Act atomic types. Each actable type has associated traits including an active-unqualified value type and implies basic operations such as being able to copy the modeled object to its value type using a non-member form of the inactive_value function. As well, the actable concept is implicitly refined into additional concepts every time the active interface for a type is specialized. Each created concept has the additional constraints being that the functions declared in the active interface specialization must exist for the modeled object. This concept is used to join together different forms of active types together (such as those varying by act model) along with Boost.Act atomic types by a common model. This allows generic code to be written which easily works with active types instantiated with different policies as well as Boost.Act atomic types without problem, given that they all model the same refinement. As well, when creating types, users may optionally inherit from a base provided with the library using the CRTP to make their types directly support the associated actable concept refinement, allowing the active interface of the type to be usable without an active-qualified instantiation (much like how with a const-unqualified instance of a type you may still call const member functions and functions taking a const reference to an instance of the type).

In terms of my ability to implement the library in C++ as I have proposed, I am fully confident that I will be able to do so and meet Boost’s high standards. I own a personal copy of the standard and am more familiar with the nuances of C++ than many professionals I know, I have experience with several compilers and know where they vary in compliance, and I am aware of the facilities provided by Boost.Config to aid in portability. I know that you hesitated having Boost participate in Summer of Code as you questioned the abilities of students to produce a well-designed and well-implemented library which would be fitting for Boost, but I hope to prove to you that I can and will. I firmly believe that my design is sound and that I have the knowledge and experience with C++ to implement it in a portable and efficient manner. I love Boost and the C++ language in general and I am very enthusiastic about this project.