Hi Boosters, Is it possible to use fusion to do a compile time matrix? The code below uses boost::tuple, but presumably fusion could do this stuff better? Things that might be useful include get column N, get cofactor<R,C> etc, etc. Might be an interesting example for fusion, but I don't know ... Its kind of fun anyway. regards Andy Little --------------------- #include <quan/out/time.hpp> #include <quan/out/reciprocal_time.hpp> #include <boost/tuple/tuple.hpp> template <int Rows, int Columns,typename TupleSequence> struct rc_matrix{ TupleSequence seq; // 0 based template <int Row, int Column> typename boost::tuples::element< Columns * Row + Column,TupleSequence >::type at() const { return seq.get<Columns * Row + Column>(); } rc_matrix( TupleSequence const & s): seq(s){} }; #include <iostream> int main() { typedef boost::tuples::tuple< double,quan::reciprocal_time::per_s, quan::time::s,double > matrix_elements; rc_matrix< 2,2, matrix_elements > mat(matrix_elements(2.,quan::reciprocal_time::per_s(3),quan::time::s(8),4.)); std::cout << mat.at<0,0>() << '\n'; std::cout << mat.at<0,1>() << '\n'; std::cout << mat.at<1,0>() << '\n'; std::cout << mat.at<1,1>() << '\n'; std::cout << mat.at<0,1>() * mat.at<1,0>() <<'\n'; }
"Andy Little" <andy@servocomm.freeserve.co.uk> writes:
Hi Boosters,
Is it possible to use fusion to do a compile time matrix?
Not directly, but there are at least two good ways to build one on top of fusion: 1. use a fusion vector of fusion vectors. 2. use a fusion vector augmented with a row length (assuming it's row-major). -- Dave Abrahams Boost Consulting www.boost-consulting.com
On 09/05/2006 08:36 AM, David Abrahams wrote:
"Andy Little" <andy@servocomm.freeserve.co.uk> writes:
Hi Boosters,
Is it possible to use fusion to do a compile time matrix?
Not directly, but there are at least two good ways to build one on top of fusion:
1. use a fusion vector of fusion vectors. 2. use a fusion vector augmented with a row length (assuming it's row-major).
The file array.cpp in vault/Template Metaprogramming has an array of types (can be any rank) which maybe useful to Andy. One problem is that there's no way (yet) to create a value from the array of types. The array of types is specified with a shape vector( mpl::vector_c<unsigned, T0, T1, ..., Tn> ) where n is the rank-1 of the array of types. The array<Shape,TypeArray> has a BOOST_CLASS_REQUIRE2(Shape,TypeArray) clause from the boost concepts library which assures the TypeArray has the shape specified by Shape (i.e. the vector_c<unsigned,...>). Andy, please let me know if you'd be interested in using this or what I'm planning on next. My next step is figuring how to generate the values (IOW, just like fusion::vector has values corresponding to mpl::vector [OK, actually they're template arguments to the fusion::vector, but maybe you get my idea], there would be fusion::array having values corresponding to array<Shape,TypeArray>).
On 09/10/2006 06:19 PM, Larry Evans wrote: [snip]
I'm planning on next. My next step is figuring how to generate the values (IOW, just like fusion::vector has values corresponding to mpl::vector [OK, actually they're template arguments to the fusion::vector, but maybe you get my idea], there would be fusion::array having values corresponding to array<Shape,TypeArray>). Done. Implemented using fusion::cons; hence, it's probably slower than fusion::vector.
On 09/10/2006 11:52 PM, Larry Evans wrote:
On 09/10/2006 06:19 PM, Larry Evans wrote: [snip]
I'm planning on next. My next step is figuring how to generate the values (IOW, just like fusion::vector has values corresponding to mpl::vector [OK, actually they're template arguments to the fusion::vector, but maybe you get my idea], there would be fusion::array having values corresponding to array<Shape,TypeArray>).
Done. Implemented using fusion::cons; hence, it's probably slower than fusion::vector. Latest version in boost/vault/Template Metaprogramming/array.cpp shows 2 alternative implementations.
1) array_impl_list This is the previous (and working) implementation. 2) array_impl_vec This uses fusion::vector to implement. Fails to compile. Would appreciate suggestions on what to do. TIA.
On 09/11/2006 06:10 PM, Larry Evans wrote: [snip]
Latest version in boost/vault/Template Metaprogramming/array.cpp shows 2 alternative implementations.
1) array_impl_list This is the previous (and working) implementation. 2) array_impl_vec This uses fusion::vector to implement. Fails to compile. Would appreciate suggestions on what to do.
Correction appears in array.zip. Now array_impl_vec works when cons_vec is used; however, when fusion::result_of::push_back is used, it doesn't. Compiler out included in the .zip. AFAICT, the mistake I'd made was not including ::type after if_<...> and other places.
"Larry Evans" <cppljevans@cox-internet.com> wrote in message news:ee26mm$bu7$1@sea.gmane.org...
On 09/05/2006 08:36 AM, David Abrahams wrote:
"Andy Little" <andy@servocomm.freeserve.co.uk> writes:
Hi Boosters,
Is it possible to use fusion to do a compile time matrix?
Not directly, but there are at least two good ways to build one on top of fusion:
1. use a fusion vector of fusion vectors. 2. use a fusion vector augmented with a row length (assuming it's row-major).
The file array.cpp in vault/Template Metaprogramming has an array of types (can be any rank) which maybe useful to Andy. One problem is that there's no way (yet) to create a value from the array of types.
The array of types is specified with a shape vector( mpl::vector_c<unsigned, T0, T1, ..., Tn> ) where n is the rank-1 of the array of types. The array<Shape,TypeArray> has a
BOOST_CLASS_REQUIRE2(Shape,TypeArray) clause from the boost concepts library which assures the TypeArray has the shape specified by Shape (i.e. the vector_c<unsigned,...>).
Andy, please let me know if you'd be interested in using this or what I'm planning on next.
FWIW I think that the combination of compile time programming, fusion and matrices has got a lot of potential. My own personal goal was to create a matrix capable of holding my quan physical quantity types, and in order to do that I have to use tuples rather than arrays, which is why fusion come in very handy. I wasnt (initially) too concerned about performance Now... the other aspect of matrix calcs is of course that they are never fast enough! From my experiments it seems to me that the fusion, compiletime programming combination can be very beneficial there too. I am not clear how beneficial as I don't really know what the current state of the art is. The final aspect of matrices (AFAICS, I am sure no expert) is that they can be big. Again from a very few experiments it seems to be quite possible to have a matrix, using fusion, where arbitrary elements are compile time entities. It is also possible of course at compile time to check ( for major example) if a particular compile time element is zero. If ( unlike the case for my physical quantity elements), you assume that each compile time element is standing in for a double, then it is presumably quite possible to sweep through the matrix resulting form a calc and eliminate any zero elements. Then when an element is not found in a processed matrix it must be a double with a zero value. For me howver that is some way down the road ;-) BTW the case of a compile time element with a zero value is particularly interesting, because it seems to allow the holy grail of actually regaining some compile time information. This is because N * 0 == ( of course 0), hence whenever any runtime value is multiplied by a compile time value of 0 then a compile time type representing 0 can be returned. This can have a beneficial 'domino' effect, thus eliminating many variables from a calc (think of how fusion computes the result_type of a calc). In cases where the compile time value is not 0 then the runtime type is returned: (In simplest case) static_value<0> operator* (static_value<0>, double) { return static_value<0>();} template <int N> double operator * (static_value<N>, double v) { return v * N;} Note also that the compiler will find it very easy to optimise the first away completely and one can also factor this in as almost a useful compile time tool( which actually fusion does a lot AFAICS)
My next step is figuring how to generate the values (IOW, just like fusion::vector has values corresponding to mpl::vector [OK, actually they're template arguments to the fusion::vector, but maybe you get my idea], there would be fusion::array having values corresponding to array<Shape,TypeArray>).
FWIW I think that a tuple is more interesting than an array, because of this property that it can hold both runtime and compile time entities. OTOH I guess that its all pretty new, so I should just say I dunno! regards Andy Little
"Andy Little" <andy@servocomm.freeserve.co.uk> wrote in message news:ee2u4r$s9b$1@sea.gmane.org...
"Larry Evans" <cppljevans@cox-internet.com> wrote in message news:ee26mm$bu7$1@sea.gmane.org...
On 09/05/2006 08:36 AM, David Abrahams wrote:
"Andy Little" <andy@servocomm.freeserve.co.uk> writes:
Hi Boosters,
Is it possible to use fusion to do a compile time matrix?
Not directly, but there are at least two good ways to build one on top of fusion:
1. use a fusion vector of fusion vectors. 2. use a fusion vector augmented with a row length (assuming it's row-major).
The file array.cpp in vault/Template Metaprogramming has an array of types (can be any rank) which maybe useful to Andy. One problem is that there's no way (yet) to create a value from the array of types.
The array of types is specified with a shape vector( mpl::vector_c<unsigned, T0, T1, ..., Tn> ) where n is the rank-1 of the array of types. The array<Shape,TypeArray> has a
BOOST_CLASS_REQUIRE2(Shape,TypeArray) clause from the boost concepts library which assures the TypeArray has the shape specified by Shape (i.e. the vector_c<unsigned,...>).
Andy, please let me know if you'd be interested in using this or what I'm planning on next.
FWIW I think that the combination of compile time programming, fusion and matrices has got a lot of potential. My own personal goal was to create a matrix capable of holding my quan physical quantity types, and in order to do that I have to use tuples rather than arrays, which is why fusion come in very handy. I wasnt (initially) too concerned about performance
Now... the other aspect of matrix calcs is of course that they are never fast enough! From my experiments it seems to me that the fusion, compiletime programming combination can be very beneficial there too. I am not clear how beneficial as I don't really know what the current state of the art is.
The final aspect of matrices (AFAICS, I am sure no expert) is that they can be big. Again from a very few experiments it seems to be quite possible to have a matrix, using fusion, where arbitrary elements are compile time entities. It is also possible of course at compile time to check ( for major example) if a particular compile time element is zero. If ( unlike the case for my physical quantity elements), you assume that each compile time element is standing in for a double, then it is presumably quite possible to sweep through the matrix resulting form a calc and eliminate any zero elements. Then when an element is not found in a processed matrix it must be a double with a zero value. For me howver that is some way down the road ;-)
BTW the case of a compile time element with a zero value is particularly interesting, because it seems to allow the holy grail of actually regaining some compile time information. This is because N * 0 == ( of course 0), hence whenever any runtime value is multiplied by a compile time value of 0 then a compile time type representing 0 can be returned. This can have a beneficial 'domino' effect, thus eliminating many variables from a calc (think of how fusion computes the result_type of a calc). In cases where the compile time value is not 0 then the runtime type is returned:
(In simplest case)
static_value<0> operator* (static_value<0>, double) { return static_value<0>();}
template <int N> double operator * (static_value<N>, double v) { return v * N;}
OH Yeah. Now static_value is quite difficult to assign to ;-) Actually this problem is very ease to solve. regards Andy Little
On 09/05/2006 08:36 AM, David Abrahams wrote:
"Andy Little" <andy@servocomm.freeserve.co.uk> writes:
Is it possible to use fusion to do a compile time matrix?
Not directly, but there are at least two good ways to build one on top of fusion:
1. use a fusion vector of fusion vectors. 2. use a fusion vector augmented with a row length (assuming it's row-major).
Andy, It suddenly dawned on me that 1 above seems a pretty simple solution. Is there some reason for not using 1?
"Larry Evans" <cppljevans@cox-internet.com> wrote in message news:eejch5$a8t$1@sea.gmane.org...
On 09/05/2006 08:36 AM, David Abrahams wrote:
"Andy Little" <andy@servocomm.freeserve.co.uk> writes:
Is it possible to use fusion to do a compile time matrix?
Not directly, but there are at least two good ways to build one on top of fusion:
1. use a fusion vector of fusion vectors. 2. use a fusion vector augmented with a row length (assuming it's row-major).
Andy,
It suddenly dawned on me that 1 above seems a pretty simple solution. Is there some reason for not using 1?
Well, Lets assume that you could use one infinitely long sequence. That is slightly simpler (IMO) because it would work exactly the same for any size matrix, iow each could have the same representation, which might be something like: matrix<rows, columns, sequence> which actually is what I am currently going for. I havent tried the alternative., but I suspect that the metaprogramming of it would be more complicated. Ultimately I suppose the interface should be separated from the implementation and it should work for both, however I'm certainly not planning something suitable for a boost review, just something where I can say 'look ma, it works!" if you get my drift :-), but in fact to get a row or a column you will probably need a fusion::View either way at some stage. If I can get to be able to produce a cofactor matrix and the inverse then I reckon I will have succeeded.; -) BTW, if you look at my inner_product.zip example in the Generic Programming section of the vault you will see why it is advantageous to be able to have arbitrary elements, even if they are just meant to stand in for doubles. Also BTW my other aim is following the book I bought called "Quaternions and Rotation sequences A primer with Applications to Orbits Aerospace and Virtual Reality", by Jack B. Kuipers. That might give a clue that my understanding of the subject isnt that advanced ;-) The ultimate aim being to make some sort of virtual reality using my Quan library. That's the dream anyway :-) regards Andy Little
On 09/17/2006 09:16 AM, Andy Little wrote:
"Larry Evans" <cppljevans@cox-internet.com> wrote in message news:eejch5$a8t$1@sea.gmane.org...
On 09/05/2006 08:36 AM, David Abrahams wrote: [snip]
1. use a fusion vector of fusion vectors. [snip] It suddenly dawned on me that 1 above seems a pretty simple solution. Is there some reason for not using 1?
Well, Lets assume that you could use one infinitely long sequence. That is slightly simpler (IMO) because it would work exactly the same for any size matrix, iow each could have the same representation, which might be something like:
matrix<rows, columns, sequence>
which actually is what I am currently going for.
I havent tried the alternative., but I suspect that the metaprogramming of it would be more complicated.
Ultimately I suppose the interface should be separated from the implementation and it should work for both, however I'm certainly not planning something Let's see if I understand. First, shorthand:
rank2_method means the fusion vector of fusion vector method. rank1_method means the existing method as illustrated in OP. One thing that would be more complicated with rank2_method vs. rank1_method is the initialization interface. IOW with the rank1_method there's this initialization interface: typedef tuples::tuple<T0_0,T0_1,T1_0,T1_1> rank1_type; rcmatrix<2,2,rank1_type> mat ( rank1_type ( val0_0 , val0_1 , val1_0 , val1_1 ) ); where rank1_type was matrix_elements in the OP. With rank2_method, the iterface would be: typedef fusion::vector<T0_0,T0_1> rank1_0_type; typedef fusion::vector<T1_0,T1_1> rank1_1_type; typedef fusion::vector<rank1_0_type,rank1_1_type> rank2_type; rcmatrix<2,2,rank2_type> mat ( rank2_type ( rank1_0_type ( val0_0 , val0_1 ) , rank1_1_type ( val1_0 , val1_1 ) ) ); So, the extra complexity the rank2_method is more typing; however, that buys you, IMO, clearer code. (WARNING: above code has not been compiled) Is there something I'm missing?
"Larry Evans" <cppljevans@cox-internet.com> wrote in message news:eejr8s$np1$1@sea.gmane.org...
Let's see if I understand. First, shorthand:
rank2_method means the fusion vector of fusion vector method. rank1_method means the existing method as illustrated in OP.
One thing that would be more complicated with rank2_method vs. rank1_method is the initialization interface. IOW with the rank1_method there's this initialization interface:
typedef tuples::tuple<T0_0,T0_1,T1_0,T1_1> rank1_type;
rcmatrix<2,2,rank1_type> mat ( rank1_type ( val0_0 , val0_1 , val1_0 , val1_1 ) );
Yeah but : rcmatrix<3,3,rank1_type> mat ( elements( val0_0, val0_1, val0_2, val1_0, val1_1, val1_2, val2_0, val2_1, val2_2 ) ); Thats how I lay it out any way. regards Andy Little
"Andy Little" <andy@servocomm.freeserve.co.uk> writes:
The code below uses boost::tuple, but presumably fusion could do this stuff better?
I should note that one of the main reasons fusion tuples (which are "vector-like") are better for random access than boost::tuple (which is "slist-like") is that, even taking into account the memoizing nature of template instantiation, the latter generates O(N^2) instantiations to access N elements of a tuple with at<>, whereas the former takes only O(N). Cheers, -- Dave Abrahams Boost Consulting www.boost-consulting.com
"David Abrahams" <dave@boost-consulting.com> wrote in message news:87irk2a0rd.fsf@pereiro.peloton...
"Andy Little" <andy@servocomm.freeserve.co.uk> writes:
The code below uses boost::tuple, but presumably fusion could do this stuff better?
I should note that one of the main reasons fusion tuples (which are "vector-like") are better for random access than boost::tuple (which is "slist-like") is that, even taking into account the memoizing nature of template instantiation, the latter generates O(N^2) instantiations to access N elements of a tuple with at<>, whereas the former takes only O(N).
Unfortunately I couldnt check out the relative compile time performance, as I ran out of elements in Boost.Tuple when I tried making a 4 x 4 matrix, else I would have stuck with it for the moment. ( I opted just to use one tuple) However maybe its a good move to try out Boost.Fusion. Although the docs said the move from tuple was as easy as changing from get to at, I found that there was a big change, because AFAICS Fusion uses references everywhere, and the compiler refused to assign anything, for reasons I am not clear on. Anyway after changing from result_of::at_c to result_of::value_at_c things seemed to go more smoothly. (That is using the Boost Review version of fusion). IOW I am succcessfully fused ! FWIW compiling a 2x2, 3x3, and 4x4 with some quan::quantities in, a multiply of each by itself and some output, takes about 22 seconds, on my AMD Atlhon 1.25Ghz system The trickiest part is working out an algorithm to do cofactors of the matrices (to get the inverse), but I may just hard code them, unless anyone has any suggestions ...? regards Andy Little
"Andy Little" <andy@servocomm.freeserve.co.uk> writes:
"David Abrahams" <dave@boost-consulting.com> wrote in message news:87irk2a0rd.fsf@pereiro.peloton...
"Andy Little" <andy@servocomm.freeserve.co.uk> writes:
The code below uses boost::tuple, but presumably fusion could do this stuff better?
I should note that one of the main reasons fusion tuples (which are "vector-like") are better for random access than boost::tuple (which is "slist-like") is that, even taking into account the memoizing nature of template instantiation, the latter generates O(N^2) instantiations to access N elements of a tuple with at<>, whereas the former takes only O(N).
Unfortunately I couldnt check out the relative compile time performance, as I ran out of elements in Boost.Tuple when I tried making a 4 x 4 matrix, else I would have stuck with it for the moment. ( I opted just to use one tuple)
Especially where Boost.Tuple (a cons-list implementation) is concerned, I don't see why one tuple would be better than 5.
However maybe its a good move to try out Boost.Fusion. Although the docs said the move from tuple was as easy as changing from get to at, I found that there was a big change, because AFAICS Fusion uses references everywhere,
Surely not everywhere. fusion::tuple<int,long> contains an int and a long, not references to int and long.
and the compiler refused to assign anything, for reasons I am not clear on. Anyway after changing from result_of::at_c to result_of::value_at_c things seemed to go more smoothly. (That is using the Boost Review version of fusion). IOW I am succcessfully fused ! FWIW compiling a 2x2, 3x3, and 4x4 with some quan::quantities in, a multiply of each by itself and some output, takes about 22 seconds, on my AMD Atlhon 1.25Ghz system The trickiest part is working out an algorithm to do cofactors of the matrices (to get the inverse), but I may just hard code them, unless anyone has any suggestions ...?
Yeah, use the fusion algorithms to express what you'd ordinarily do with looping if these were homogeneous vectors/matrices. -- Dave Abrahams Boost Consulting www.boost-consulting.com
"David Abrahams" <dave@boost-consulting.com> wrote in message news:87ejup8muh.fsf@pereiro.peloton...
"Andy Little" <andy@servocomm.freeserve.co.uk> writes:
"David Abrahams" <dave@boost-consulting.com> wrote in message news:87irk2a0rd.fsf@pereiro.peloton...
Unfortunately I couldnt check out the relative compile time performance, as I ran out of elements in Boost.Tuple when I tried making a 4 x 4 matrix, else I would have stuck with it for the moment. ( I opted just to use one tuple)
Especially where Boost.Tuple (a cons-list implementation) is concerned, I don't see why one tuple would be better than 5.
If you're talking about compile time, I don't know. If you are asking why use a single tuple, then it seems to be much more convenient (but I havent really thought that much about it, but it seems to be working OK so far). FWIW the matrix interface currently looks like so: typedef quan::rc_matrix< 2,2, boost::fusion::vector4< quan::current::mA, quan::current::mA, double,double > > current_matrix; current_matrix cmat( current_matrix::elements( quan::current::mA(30),quan::current::mA(5), -2,7 ) ); The rc_matrix is basically just a wrapper over a boost::fusion::vector, and I havent bothered to overload the matrix ctor for varying arguments, but rather left it to the fusion sequence to sort out. So far I have implememented addition of matrices among other rthings ( That is simply directly using the fusion transform algorithm). I had some old code which converts operator functions into function objects. Here FWIW is the main part of the add algorithm, which is pretty simple, once you get through the return type deduction: (relevent code is in <quan-trunk/quan/matrix/> for anyone interested. Headers using fusion are add_subtract.hpp and rc_matrix_def.hpp) template <int R, int C, typename SeqL,typename SeqR> typename quan::meta::binary_operation< quan::rc_matrix<R,C,SeqL>, quan::meta::plus, quan::rc_matrix<R,C,SeqR> >::type operator + ( quan::rc_matrix<R,C,SeqL> const & lhs, quan::rc_matrix<R,C,SeqR> const & rhs ) { typedef typename quan::meta::binary_operation< quan::rc_matrix<R,C,SeqL>, quan::meta::plus, quan::rc_matrix<R,C,SeqR> >::type result_type; result_type result( boost::fusion::as_vector( boost::fusion::transform(lhs.seq,rhs.seq,quan::operator_plus()) ) ); return result; } and here is a *= impl: template <int Rows, int Cols,typename Seq> template <typename Numeric> inline typename boost::enable_if< quan::meta::is_numeric<Numeric>, rc_matrix<Rows,Cols,Seq>& >::type rc_matrix<Rows,Cols,Seq>::operator *=(Numeric const & in) { boost::fusion::for_each( this->seq, detail::assignment_functor< quan::operator_times_equals, Numeric >(in) ); return *this; } So all in all I reckon Boost.Fusion is quite cool :-). Of course it is probably not as good performance wise, but I am not too concerned about performance and it is more interesting to do it this way..
However maybe its a good move to try out Boost.Fusion. Although the docs said the move from tuple was as easy as changing from get to at, I found that there was a big change, because AFAICS Fusion uses references everywhere,
Surely not everywhere. fusion::tuple<int,long> contains an int and a long, not references to int and long.
and the compiler refused to assign anything, for reasons I am not clear on. Anyway after changing from result_of::at_c to result_of::value_at_c things seemed to go more smoothly. (That is using the Boost Review version of fusion). IOW I am succcessfully fused ! FWIW compiling a 2x2, 3x3, and 4x4 with some quan::quantities in, a multiply of each by itself and some output, takes about 22 seconds, on my AMD Atlhon 1.25Ghz system The trickiest part is working out an algorithm to do cofactors of the matrices (to get the inverse), but I may just hard code them, unless anyone has any suggestions ...?
Yeah, use the fusion algorithms to express what you'd ordinarily do with looping if these were homogeneous vectors/matrices.
I guess I'll start with the easy stuff :-) regards Andy Little
"Andy Little" <andy@servocomm.freeserve.co.uk> wrote in message news:edn9qk$til$1@sea.gmane.org...
(relevent code is in <quan-trunk/quan/matrix/> for anyone interested. Headers using fusion are add_subtract.hpp and rc_matrix_def.hpp)
Sorry I meant its in the quan CVS : http://quan.cvs.sourceforge.net/quan/ regards Andy Little
"Andy Little" <andy@servocomm.freeserve.co.uk> writes:
So all in all I reckon Boost.Fusion is quite cool :-). Of course it is probably not as good performance wise,
I don't know why you say "of course." Just as STL iteration can be faster than a hand-coded loop, in MPL we did several things that can make it quite a bit faster to use the high-level abstractions than to do the naive hand-coded version. The same thing could be true of Fusion.
but I am not too concerned about performance and
A welcome change ;-)
it is more interesting to do it this way..
And more maintainable. And more understandable. And... :) -- Dave Abrahams Boost Consulting www.boost-consulting.com
"David Abrahams" <dave@boost-consulting.com> wrote in message news:873bb4eg6y.fsf@pereiro.peloton...
"Andy Little" <andy@servocomm.freeserve.co.uk> writes:
So all in all I reckon Boost.Fusion is quite cool :-). Of course it is probably not as good performance wise,
I don't know why you say "of course." Just as STL iteration can be faster than a hand-coded loop, in MPL we did several things that can make it quite a bit faster to use the high-level abstractions than to do the naive hand-coded version. The same thing could be true of Fusion.
Dunno, but there are two things, firstly references, aka pointers, and secondly iterators aka pointers. That said, the runtime performance issue is secondary. For someone like me I think it needs a whole lot of useage examples, so I can copy paste them. Anyway, for my 'Quan'tity matrices, its seems to hit the spot :-)
but I am not too concerned about performance and
A welcome change ;-)
Let's separate compile time performance from runtime performance.
it is more interesting to do it this way..
And more maintainable. And more understandable. And... :)
Boost.Fusion certainly has got something ... not quite sure what yet ;-) regards Andy Little
"Andy Little" <andy@servocomm.freeserve.co.uk> writes:
"David Abrahams" <dave@boost-consulting.com> wrote in message news:873bb4eg6y.fsf@pereiro.peloton...
"Andy Little" <andy@servocomm.freeserve.co.uk> writes:
So all in all I reckon Boost.Fusion is quite cool :-). Of course it is probably not as good performance wise,
I don't know why you say "of course." Just as STL iteration can be faster than a hand-coded loop, in MPL we did several things that can make it quite a bit faster to use the high-level abstractions than to do the naive hand-coded version. The same thing could be true of Fusion.
Dunno, but there are two things, firstly references, aka pointers,
What about them?
and secondly iterators aka pointers.
Fusion iterators are not pointers... at least, not in the usual sense. They might contain one pointer (to the whole tuple) that is never mutated during iteration. -- Dave Abrahams Boost Consulting www.boost-consulting.com
"David Abrahams" <dave@boost-consulting.com> wrote
"Andy Little" <andy@servocomm.freeserve.co.uk> writes:
"David Abrahams" <dave@boost-consulting.com> wrote in message news:873bb4eg6y.fsf@pereiro.peloton...
"Andy Little" <andy@servocomm.freeserve.co.uk> writes:
So all in all I reckon Boost.Fusion is quite cool :-). Of course it is probably not as good performance wise,
I don't know why you say "of course." Just as STL iteration can be faster than a hand-coded loop, in MPL we did several things that can make it quite a bit faster to use the high-level abstractions than to do the naive hand-coded version. The same thing could be true of Fusion.
Dunno, but there are two things, firstly references, aka pointers,
What about them?
and secondly iterators aka pointers.
Fusion iterators are not pointers... at least, not in the usual sense. They might contain one pointer (to the whole tuple) that is never mutated during iteration.
OK . I guess I was suffering from some conFusion about that. :-). regards Andy Little
"David Abrahams" <dave@boost-consulting.com> wrote in message news:873bb4eg6y.fsf@pereiro.peloton...
"Andy Little" <andy@servocomm.freeserve.co.uk> writes:
So all in all I reckon Boost.Fusion is quite cool :-). Of course it is probably not as good performance wise,
I don't know why you say "of course." Just as STL iteration can be faster than a hand-coded loop, in MPL we did several things that can make it quite a bit faster to use the high-level abstractions than to do the naive hand-coded version. The same thing could be true of Fusion.
Looking at the assembler output from my quan::fusion::dot_product function when optimised in VC8, it looks like the optimisation is near perfect FWIW. I love fusion ! regards Andy Little
Andy Little wrote:
"David Abrahams" <dave@boost-consulting.com> wrote in message news:873bb4eg6y.fsf@pereiro.peloton...
"Andy Little" <andy@servocomm.freeserve.co.uk> writes:
So all in all I reckon Boost.Fusion is quite cool :-). Of course it is probably not as good performance wise, I don't know why you say "of course." Just as STL iteration can be faster than a hand-coded loop, in MPL we did several things that can make it quite a bit faster to use the high-level abstractions than to do the naive hand-coded version. The same thing could be true of Fusion.
Looking at the assembler output from my quan::fusion::dot_product function when optimised in VC8, it looks like the optimisation is near perfect FWIW.
I love fusion !
:-) You must've missed this: Dan wrote me an email a while back. He says: "Interestingly using fusion::fold to do maths on boost::arrays, I'm finding that with vc8.0 fusion significantly outperforms the standard library equivalent code, presumably as it has more information available at compile time, and with inlining it effectively unrolls the entire loops." I asked Dan to add his tests to libs/fusion/example to showcase this favorable "phenomena" :-). Regards, -- Joel de Guzman http://www.boost-consulting.com http://spirit.sf.net
"Joel de Guzman" <joel@boost-consulting.com> wrote in message news:edtvh9$tcv$1@sea.gmane.org...
Andy Little wrote:
"David Abrahams" <dave@boost-consulting.com> wrote in message news:873bb4eg6y.fsf@pereiro.peloton...
"Andy Little" <andy@servocomm.freeserve.co.uk> writes:
So all in all I reckon Boost.Fusion is quite cool :-). Of course it is probably not as good performance wise, I don't know why you say "of course." Just as STL iteration can be faster than a hand-coded loop, in MPL we did several things that can make it quite a bit faster to use the high-level abstractions than to do the naive hand-coded version. The same thing could be true of Fusion.
Looking at the assembler output from my quan::fusion::dot_product function when optimised in VC8, it looks like the optimisation is near perfect FWIW.
I love fusion !
:-)
You must've missed this: Dan wrote me an email a while back. He says: "Interestingly using fusion::fold to do maths on boost::arrays, I'm finding that with vc8.0 fusion significantly outperforms the standard library equivalent code, presumably as it has more information available at compile time, and with inlining it effectively unrolls the entire loops."
I asked Dan to add his tests to libs/fusion/example to showcase this favorable "phenomena" :-).
I can't find that, but I am probably looking in the wrong place. Do you mean Boost CVS? BTW. By using a tuple rather than an array, then you can use representing zero and one. IOW zero<T> one<T> . hence: template <typename TL, typename TR> zero<typeof(TL() * TR() )> operator *( Tl , zero<TR>) { return zero<typeof(TL() * TR() )>(); } It should be relatively simple for the compiler to optimise such calcs away. Very useful for matrix calcs. (originally suggested by Geoffrey Irving). regards Andy Little
Andy Little wrote:
You must've missed this: Dan wrote me an email a while back. He says: "Interestingly using fusion::fold to do maths on boost::arrays, I'm finding that with vc8.0 fusion significantly outperforms the standard library equivalent code, presumably as it has more information available at compile time, and with inlining it effectively unrolls the entire loops."
I asked Dan to add his tests to libs/fusion/example to showcase this favorable "phenomena" :-).
I can't find that, but I am probably looking in the wrong place. Do you mean Boost CVS?
Sorry, you'll have to wait a bit more. Dan says he'll do it over the weekend.
BTW. By using a tuple rather than an array, then you can use representing zero and one. IOW zero<T> one<T> .
hence:
template <typename TL, typename TR> zero<typeof(TL() * TR() )> operator *( Tl , zero<TR>) { return zero<typeof(TL() * TR() )>(); } It should be relatively simple for the compiler to optimise such calcs away. Very useful for matrix calcs. (originally suggested by Geoffrey Irving).
Indeed. Also, with Fusion, you have the option to use purely constant sequences such as mpl::vector_c together with plain sequences, or even user defined sequences and adapted/converted structs/classes. Regards, -- Joel de Guzman http://www.boost-consulting.com http://spirit.sf.net
On Sat, Sep 09, 2006 at 06:27:40PM +0800, Joel de Guzman wrote:
Andy Little wrote:
You must've missed this: Dan wrote me an email a while back. He says: "Interestingly using fusion::fold to do maths on boost::arrays, I'm finding that with vc8.0 fusion significantly outperforms the standard library equivalent code, presumably as it has more information available at compile time, and with inlining it effectively unrolls the entire loops."
I asked Dan to add his tests to libs/fusion/example to showcase this favorable "phenomena" :-).
I can't find that, but I am probably looking in the wrong place. Do you mean Boost CVS?
Sorry, you'll have to wait a bit more. Dan says he'll do it over the weekend.
I think the main reason for this is that inlining a fusion loop means that the compiler has obeyed an explicit programmer suggestion (inline), whereas unrolling a constant size array loop is loop unrolling, which is impossible to suggest to the compiler (and typically requires higher -O levels, etc.). A while back when I implemented a vector type with constant size for loops, it slowed down the whole application by 30%. I'm very curious to see how much better fusion can do. Andy: is your fusion code in an easily accessible place where I could grab it and stick some of it into our vector class to test it in a (probably) larger example? The main issue is whether the compile will still choose to unroll everything if it sees a bunch of vector operations inside various complicated functions. Thanks, Geoffrey
"Geoffrey Irving" <irving@cs.stanford.edu> wrote in message news:20060909180645.GC20743@lie.Stanford.EDU...
On Sat, Sep 09, 2006 at 06:27:40PM +0800, Joel de Guzman wrote:
Andy Little wrote:
You must've missed this: Dan wrote me an email a while back. He says: "Interestingly using fusion::fold to do maths on boost::arrays, I'm finding that with vc8.0 fusion significantly outperforms the standard library equivalent code, presumably as it has more information available at compile time, and with inlining it effectively unrolls the entire loops."
I asked Dan to add his tests to libs/fusion/example to showcase this favorable "phenomena" :-).
I can't find that, but I am probably looking in the wrong place. Do you mean Boost CVS?
Sorry, you'll have to wait a bit more. Dan says he'll do it over the weekend.
I think the main reason for this is that inlining a fusion loop means that the compiler has obeyed an explicit programmer suggestion (inline), whereas unrolling a constant size array loop is loop unrolling, which is impossible to suggest to the compiler (and typically requires higher -O levels, etc.). A while back when I implemented a vector type with constant size for loops, it slowed down the whole application by 30%.
I'm very curious to see how much better fusion can do. Andy: is your fusion code in an easily accessible place where I could grab it and stick some of it into our vector class to test it in a (probably) larger example?
The code is in quan CVS. Heres the info page: http://sourceforge.net/cvs/?group_id=170593 The module name is quan-trunk Unfortunately there are quite a few dependencies on the rest of the Quan stuff. To use it direct you will need to download everything and point the compiler at the quan directory. The dot_product is implemented in <quan-trunk/quan/fusion/dot_product.hpp> OTOH You could however just download that header and replace the functors quan::operator_plus, quan::operator_plus_equals, and quan::operator_multiplies ( and swap_args) with your own versions which *should* remove the dependencies, but you will need to look at the <quan/fusion/swap_args.hpp> header to get the boost::reference_wrapper signatures for assignment There is an example use in <quan-matters/examples/fusion/dot_product.cpp>. regards Andy Little
"Joel de Guzman" <joel@boost-consulting.com> wrote in message news:edu4v2$beb$1@sea.gmane.org...
Andy Little wrote:
BTW. By using a tuple rather than an array, then you can use representing zero and one. IOW zero<T> one<T> .
hence:
template <typename TL, typename TR> zero<typeof(TL() * TR() )> operator *( Tl , zero<TR>) { return zero<typeof(TL() * TR() )>(); } It should be relatively simple for the compiler to optimise such calcs away. Very useful for matrix calcs. (originally suggested by Geoffrey Irving).
Indeed. Also, with Fusion, you have the option to use purely constant sequences such as mpl::vector_c together with plain sequences, or even user defined sequences and adapted/converted structs/classes.
Right. I started looking into this scheme for math ops. I opted for a zero and a one, but then I figured that one + one should go to two etc. In the end I opted for a static_value<StaticValue,RunTimeType> StaticValue could then be any of mpl::int_ etc, though for mpl int_ division is ( can be) lossy so at that point the division should turn the result into the RunTimeType. other possibilities for StaticValue are a compile time rational, maybe with a long long value_type. At any point where the compile time value will run out of steam then the type will be automatically converted to the RunTimeType. All in all... how to take a simple idea and make it very very complicated :-) regards Andy Little
"Andy Little" <andy@servocomm.freeserve.co.uk> wrote in message news:edv632$3ku$1@sea.gmane.org...
"Joel de Guzman" <joel@boost-consulting.com> wrote in message news:edu4v2$beb$1@sea.gmane.org...
Andy Little wrote:
BTW. By using a tuple rather than an array, then you can use representing zero and one. IOW zero<T> one<T> .
hence:
template <typename TL, typename TR> zero<typeof(TL() * TR() )> operator *( Tl , zero<TR>) { return zero<typeof(TL() * TR() )>(); } It should be relatively simple for the compiler to optimise such calcs away. Very useful for matrix calcs. (originally suggested by Geoffrey Irving).
Indeed. Also, with Fusion, you have the option to use purely constant sequences such as mpl::vector_c together with plain sequences, or even user defined sequences and adapted/converted structs/classes.
Right. I started looking into this scheme for math ops. I opted for a zero and a one, but then I figured that one + one should go to two etc.
In the end I opted for a static_value<StaticValue,RunTimeType>
StaticValue could then be any of mpl::int_ etc, though for mpl int_ division is ( can be) lossy so at that point the division should turn the result into the RunTimeType. other possibilities for StaticValue are a compile time rational, maybe with a long long value_type. At any point where the compile time value will run out of steam then the type will be automatically converted to the RunTimeType.
All in all... how to take a simple idea and make it very very complicated :-)
Oh Yeah, and plug in variadic templates, auto, and stick the kettle on while waiting for it to compile and you will probably not spend as much time worrying about sparse matrices. ;-) regards Andy Little
"Andy Little" <andy@servocomm.freeserve.co.uk> wrote in message news:edv632$3ku$1@sea.gmane.org...
"Joel de Guzman" <joel@boost-consulting.com> wrote
Indeed. Also, with Fusion, you have the option to use purely constant sequences such as mpl::vector_c together with plain sequences, or even user defined sequences and adapted/converted structs/classes.
Right. I started looking into this scheme for math ops. I opted for a zero and a one, but then I figured that one + one should go to two etc.
In the end I opted for a static_value<StaticValue,RunTimeType>
StaticValue could then be any of mpl::int_ etc, though for mpl int_ division is ( can be) lossy so at that point the division should turn the result into the RunTimeType. other possibilities for StaticValue are a compile time rational, maybe with a long long value_type. At any point where the compile time value will run out of steam then the type will be automatically converted to the RunTimeType.
All in all... how to take a simple idea and make it very very complicated :-)
static_value now implemented, though I changed the param order. runtime and static values should be able to be arbitarily mixed in same tuple. Also tested (after some mods) in the quan::fusion::dot_product functor <quan/fusion/dot_product.hpp> Example: http://tinyurl.com/gq3a4 http://sourceforge.net/projects/quan regards Andy Little
participants (5)
-
Andy Little -
David Abrahams -
Geoffrey Irving -
Joel de Guzman -
Larry Evans