[boost] [Fusion] port to c++0x

Subject: [boost] [Fusion] port to c++0x
From: Christopher Schmidt (mr.chr.schmidt_at_[hidden])
Date: 2009-09-22 18:40:56

I participated in Google's 'Summer of Code' for Boost this year. My 
project was to port Boost.Fusion to c++0x.
The program is over now and I would like to give you a short report on 
my work and put my code up for comments.

In a nutshell, there is rvalue support, native variadic templates are 
used if possible and the public classes and (meta-) functions are 
guarded by a set of static asserts that detect most invalid (template) 
arguments.
I also added certain new functionality to provide an easier, faster and 
more intuitive programming interface.
My implementation is pretty much backwards compatible and all test cases 
pass on gcc 3.4/4.4 and vc 9.

Here is a short overview of the most striking changes besides the 
implementation of raw c++0x support.

I removed the deque container and the extension-classes.
The deque container is undocumented and, in my opinion, does not go well 
with the other container due to its intrinsic extension mechanism. There 
also should not be a performance gain compared to a regular 
fusion::joint_view in combination with two fusion::vector.
The extension classes are pretty much Boost.Proto specific. At the 
moment they seem to be out of place, especially as they are 
undocumented, unmaintained and not even part of the regular file 
structure. I would like to see them either fully documented (with the 
underlying concept of segmented sequences) or in the detail namespace of 
Boost.Proto.

I added support for associative iterators. An associative forward 
sequence shall provide an iterator type which implements the extension 
backend of the intrinsic (meta-)functions 
fusion::result_of::value_of_data, fusion::deref_data and 
fusion::result_of::key_of. This has the advantage that all view classes, 
even fusion::iterator_range, are able to adapt the underlying sequence's 
associative-ness. fusion::transform_view, as a special case, got an 
additional template parameter. This parameter specifies whether the view 
should model either the forward concept only or the associative and the 
forward concept.
This design breaks consistency with Boost.MPL. Unfortunately these 
changes are crucial and I would rather risk this break with Boost.MPL 
than missing that important feature. Using the old implementation, there 
is no way to avoid explicitly converting from a view back to an 
associative sequence to preserve the associative-ness. This leads to a 
nasty runtime overhead due to evaluation of every element of the view 
and copy-/move-constructing it.

Besides, other changes include:
-If the compiler supports rvalue references, all fusion container have a 
template constructor (taking either const lvalue or 'templated' rvalue 
references).
-If the compiler supports variadic templates, fusion::cons, fusion::pair 
and fusion::single_view have a variadic template constructor (taking 
either const lvalue or 'templated' rvalue references) that allows 
emplace construction.
-The view classes adapt the full category of their underlying sequences. 
As mentioned above, the associative-ness is preserved, but also, if 
possible, the random-access or bidirectional trait.
-The result_of::-metafunctions accept r- and lvalue references 
arguments. If an argument is not reference-qualified, it will be 
considered to be an lvalue reference. All existing extension 
implementations must be changed to adapt this new behaviour.
-The algorithm functions now also take (and correctly forward) non-const 
reference arguments.
-Fusion iterators (with reference compatible sequence types and a very 
same index) and views (with reference compatible sequence types) have a 
working operator= that correctly reassigns the underlying sequence 
references.
-Fusion now also adapts MPL iterators. If, and only if, the 
<boost/fusion/adapted/mpl.hpp>-header is included, mpl sequences and 
iterators are recognized as fusion sequences and iterators.
-There are new headers to adapt std::(tr1::)array or std::(tr1::)tuple.

The overall compile-time performance of my code is satisfying. Compiling 
a compilation unit that includes all possible fusion headers takes on 
gcc 4.4 slightly more time than the official fusion implementation. If 
native variadic templates are present, the compilation is a lot faster 
(usually up to 3 to 6 times), regardless of the value of 
FUSION_MAX_xxx_SIZE.
The compile-time performance of actual fusion code is mixed. The 
intrinsic container and iterator (meta-)functions compile a little bit 
slower compared to the official fusion implementation. This is due to 
explicit removal of the references on the arguments of all 
result_of::metafunctions and some additional abstraction layer. If the 
compiler support rvalue references, there has to be a rather ugly and 
slow type evaluation/transformation to avoid issues with rvalue 
references on non-array, non-class types (see /support/internal/ref.hpp 
and 8.5.3p5 of the current c++0x draft for more details).
On the other hand, I added several optimizations (such as result 
preevaluation), and, if variadic templates are present, the actual 
instantiation of fusion containers is a lot faster.
All in all, the compile-time performance is a little bit worse if c++0x 
features are not present. If c++0x features are present, the code should 
compile a little bit faster in most cases.
For example, the lambda example of the Boost.Proto documentation, which 
internally heavily relies on Boost.Fusion, takes on my machine 2.6 
seconds to compile with the 'old' fusion on gcc 4.4, 3 seconds with my 
port without -std=c++0x, and 2.1 seconds with c++0x features being present.
The overall performance might be even better once Boost.MPL adapts 
native variadic templates and the compiler supports template aliases.

There have been tons of other changes, mostly bugfixes, optimizations 
(in terms of compile time of course) and removals of redundancy. 
Whenever I had the choice, I tried to prefer clean, redundancy-free 
instead of heavily optimized code. The overall performance loss is not 
noticeable though, and most compile-time optimizations that go beyond 
the as-little-template-instantiations-as-possible paradigm are pretty 
much compiler dependent anyway.

There is still some work to do. I did not add c++0x-specific test cases 
and there are several parts of the documentation which need to be 
updated. By the way, are there any official guidelines for documenting 
c++03/c++0x-specific differences?
For now, I would like to hold off on implementing these changes until 
Boost.TypeTraits adapts c++0x. Right now I implemented missing or 
incorrectly behaving trait functions in the fusion::detail-namespace. I 
would rather like to use the official ones, at least in the 
documentation and in the test cases.
Besides that, I think my implementation is trunk-ready. If there are no 
objections, I would like to finish the outstanding work as soon as 
possible, and then merge my code with the trunk. Of course I will 
provide long-term support for the project. In fact, I would love to 
become an official fusion maintainer.

You can find the code in the boost sandbox (/sandbox/SOC/2009/fusion). 
If you test the code with a compiler that has decltype support, please 
use the HEAD of the trunk rather than the official 1.40 distribution 
package to compile your code.

Best regards
Christopher