Hi, I need something like an abstraction layer for iterations over some range. Consider for example the following three statements, which all do the same, but the loop inside each for_each is different: // thrust is an STL-like interface for CUDA [1] thrust::device_vector< double > a1( 3 ); thrust::for_each( a1.begin() , a1.end() , op() ); std::vector< double > a2( 3 ); __gnu_parallel::for_each( a2.begin() , a2.end() , op() ); std::vector< double > a3( 3 ); std::for_each( a3.begin() , a3.end() , op() ); //maybe even fusion::vector< double , double , double > a4; fusion::for_each( a4 , op() ); Is there a way or some part of a boost-library which handles the above three statements in a unique manner? I want to write algorithms which are independent of the specific for_each implementation. Best regards, Karsten [1] http://code.google.com/p/thrust/
On 11/17/2010 8:22 AM, Karsten Ahnert wrote:
Hi,
I need something like an abstraction layer for iterations over some range. Consider for example the following three statements, which all do the same, but the loop inside each for_each is different:
// thrust is an STL-like interface for CUDA [1] thrust::device_vector< double> a1( 3 ); thrust::for_each( a1.begin() , a1.end() , op() );
std::vector< double> a2( 3 ); __gnu_parallel::for_each( a2.begin() , a2.end() , op() );
std::vector< double> a3( 3 ); std::for_each( a3.begin() , a3.end() , op() );
//maybe even fusion::vector< double , double , double> a4; fusion::for_each( a4 , op() );
Is there a way or some part of a boost-library which handles the above three statements in a unique manner? I want to write algorithms which are independent of the specific for_each implementation.
What do you mean by "handles"? Do you want to just package up the for_each function together with the sequence type you want to operate on, effectively reducing everything to a unary function accepting the op parameter? I don't know of such an abstraction in boost. There was a topic that was brought up by...I'm going to say Joel Falcou, but I may have that wrong...discussing segmented iterators and iteration in general (I would search "segmented iterators"). I believe his use case was enabling the use of simd instruction in the iteration, which required special treatment of the first few and last few elements of the range. One abstraction that makes this efficient is to push the iteration to the responsibility of the range or sequence you're operating on. This seems to be roughly what you might want to consider doing here (and is basically equivalent to packaging the for_each function up with the sequence, as I suggested above). - Jeff
What do you mean by "handles"? Do you want to just package up the for_each function together with the sequence type you want to operate on, effectively reducing everything to a unary function accepting the op parameter? I don't know of such an abstraction in boost.
Yes, exactly. This looks like a quite general concept for me and I was wondering if something has already been implemented. Maybe a small example is: struct std_algorithm { template< Op > static void for_each( std::vector< double > &vec , Op op ) { std::for_each( vec.begin() , vec.end() , op ); } }; struct thrust_algorithm { template< Op > static void for_each( thrust::device_vector< double > &vec , Op op ) { thrust::for_each( vec.begin() , vec.end() , op ); } }; // the complex algorithm we want to implement template< class Algorithm , class Sequence > void do_something( Sequence &seq ) { ... Algebra::for_each( seq , op() ); ... } // use youe code via // the standard version std::vector< double > vec1; do_something< std_algorithm >( vec1 ); // the thrust (CUDA) version thrust::device_vector< double > vec2; do_something< thrust_algorithm >( vec2 );
There was a topic that was brought up by...I'm going to say Joel Falcou, but I may have that wrong...discussing segmented iterators and iteration in general (I would search "segmented iterators"). I believe his use case was enabling the use of simd instruction in the iteration, which required special treatment of the first few and last few elements of the range. One abstraction that makes this efficient is to push the iteration to the responsibility of the range or sequence you're operating on. This seems to be roughly what you might want to consider doing here (and is basically equivalent to packaging the for_each function up with the sequence, as I suggested above).
I think you mean this one http://thread.gmane.org/gmane.comp.lib.boost.devel/209431 altough I am not sure I fully understand. Karsten
On 11/17/2010 11:55 AM, Karsten Ahnert wrote:
What do you mean by "handles"? Do you want to just package up the for_each function together with the sequence type you want to operate on, effectively reducing everything to a unary function accepting the op parameter? I don't know of such an abstraction in boost.
Yes, exactly. This looks like a quite general concept for me and I was wondering if something has already been implemented.
Not that I know of, at least not formally and with wide dissemination and adoption.
Maybe a small example is:
struct std_algorithm { template< Op> static void for_each( std::vector< double> &vec , Op op ) { std::for_each( vec.begin() , vec.end() , op ); } };
struct thrust_algorithm { template< Op> static void for_each( thrust::device_vector< double> &vec , Op op ) { thrust::for_each( vec.begin() , vec.end() , op ); } };
// the complex algorithm we want to implement template< class Algorithm , class Sequence> void do_something( Sequence&seq ) { ... Algebra::for_each( seq , op() );
^^^^^^^ Algorithm
... }
// use youe code via
// the standard version std::vector< double> vec1; do_something< std_algorithm>( vec1 );
// the thrust (CUDA) version thrust::device_vector< double> vec2; do_something< thrust_algorithm>( vec2 );
I was imagining something slightly different, where the for_each functions are more tightly coupled to the sequence types. In other words, std::vector and thrust::device_vector both have a for_each member function (or maybe a less intrusive for_each free function found, for example, via ADL): std::vector< double > vec1; vec1.for_each(op()); thrust::device_vector< double > vec2; vec2.for_each(op());
There was a topic that was brought up by...I'm going to say Joel Falcou, but I may have that wrong...discussing segmented iterators and iteration in general (I would search "segmented iterators"). I believe his use case was enabling the use of simd instruction in the iteration, which required special treatment of the first few and last few elements of the range. One abstraction that makes this efficient is to push the iteration to the responsibility of the range or sequence you're operating on. This seems to be roughly what you might want to consider doing here (and is basically equivalent to packaging the for_each function up with the sequence, as I suggested above).
I think you mean this one
Yes, that's it. Apologies to Mathias.
altough I am not sure I fully understand.
It's a different use case but with (I believe) a similar solution: ranges and sequences provide their own iteration mechanism. - Jeff
----- Original Message ----- From: "Jeffrey Lee Hellrung, Jr." <jhellrung@ucla.edu> To: <boost@lists.boost.org> Sent: Wednesday, November 17, 2010 9:58 PM Subject: Re: [boost] for_each abstraction
I was imagining something slightly different, where the for_each functions are more tightly coupled to the sequence types. In other words, std::vector and thrust::device_vector both have a for_each member function (or maybe a less intrusive for_each free function found, for example, via ADL):
std::vector< double > vec1; vec1.for_each(op()); thrust::device_vector< double > vec2; vec2.for_each(op());
Please, don't add algorithms in the containers. Vicente
On 11/17/2010 01:05 PM, vicente.botet wrote:
----- Original Message ----- From: "Jeffrey Lee Hellrung, Jr."<jhellrung@ucla.edu> To:<boost@lists.boost.org> Sent: Wednesday, November 17, 2010 9:58 PM Subject: Re: [boost] for_each abstraction
I was imagining something slightly different, where the for_each functions are more tightly coupled to the sequence types. In other words, std::vector and thrust::device_vector both have a for_each member function (or maybe a less intrusive for_each free function found, for example, via ADL):
std::vector< double> vec1; vec1.for_each(op()); thrust::device_vector< double> vec2; vec2.for_each(op());
Please, don't add algorithms in the containers.
Are you objecting to the syntax or to the entire idea of letting sequences opt in for tighter control of their iteration? I'm not 100% convinced it's a good idea, but I'm not convinced it's a bad idea either. It appears (to me, at least) to be one solution to the OP's question, and to Mathias/Joel's problem with "packing" range elements together to vectorize operations. It also could (speculation) make iterating over a type-erased range more efficient, compared to using type-erased iterators. - Jeff
On 17/11/10 22:18, Jeffrey Lee Hellrung, Jr. wrote:
Are you objecting to the syntax or to the entire idea of letting sequences opt in for tighter control of their iteration?
I'm not 100% convinced it's a good idea, but I'm not convinced it's a bad idea either. It appears (to me, at least) to be one solution to the OP's question, and to Mathias/Joel's problem with "packing" range elements together to vectorize operations.
It also could (speculation) make iterating over a type-erased range more efficient, compared to using type-erased iterators.
Binding algorithm to container type lessen genericity of code.
On 11/17/2010 10:24 PM, joel falcou wrote:
On 17/11/10 22:18, Jeffrey Lee Hellrung, Jr. wrote:
Are you objecting to the syntax or to the entire idea of letting sequences opt in for tighter control of their iteration?
I'm not 100% convinced it's a good idea, but I'm not convinced it's a bad idea either. It appears (to me, at least) to be one solution to the OP's question, and to Mathias/Joel's problem with "packing" range elements together to vectorize operations.
It also could (speculation) make iterating over a type-erased range more efficient, compared to using type-erased iterators.
Binding algorithm to container type lessen genericity of code.
Sure, but there is no to change the way how elements in a range are iterated. In my example, the algorithm is entirely provided by for_each with the appropriate operation.
On 17/11/10 22:35, Karsten Ahnert wrote:
Sure, but there is no to change the way how elements in a range are iterated. In my example, the algorithm is entirely provided by for_each with the appropriate operation.
That's not the actual problem. Bindign such thing make codes cumbersome to use in generic context where you may or may not know if a T must sue for_each or T::for_each. The proper way to solve the original question while preserving genericity is to use tag dispatching and externally tagging each type supporting on for_each with a proper compile-time flag thanks to a proper meta-function then use it to select the implementation fo the global, free for_each function.
On 11/17/2010 10:42 PM, joel falcou wrote:
On 17/11/10 22:35, Karsten Ahnert wrote:
Sure, but there is no to change the way how elements in a range are iterated. In my example, the algorithm is entirely provided by for_each with the appropriate operation.
That's not the actual problem. Bindign such thing make codes cumbersome to use in generic context where you may or may not know if a T must sue for_each or T::for_each.
The proper way to solve the original question while preserving genericity is to use tag dispatching and externally tagging each type supporting on for_each with a proper compile-time flag thanks to a proper meta-function then use it to select the implementation fo the global, free for_each function.
I think I understand. Maybe this allows the analogy to boost.range which provides an extendable layer how sequences/containers can be used in the range algorithms. Here an extendable layer is needed which allows you to change the way how thinks are iterated in for_each ( or accumulate, transform,... ), but with the additional contraint that the iteration has to be choosen according to the sequence/container.
On 11/17/2010 10:24 PM, joel falcou wrote:
On 17/11/10 22:18, Jeffrey Lee Hellrung, Jr. wrote:
Are you objecting to the syntax or to the entire idea of letting sequences opt in for tighter control of their iteration?
I'm not 100% convinced it's a good idea, but I'm not convinced it's a bad idea either. It appears (to me, at least) to be one solution to the OP's question, and to Mathias/Joel's problem with "packing" range elements together to vectorize operations.
It also could (speculation) make iterating over a type-erased range more efficient, compared to using type-erased iterators.
Binding algorithm to container type lessen genericity of code.
Sure, but there is no to change the way how elements in a range are iterated. In my example, the algorithm is entirely provided by for_each with the appropriate operation.
On 11/17/2010 4:24 PM, joel falcou wrote:
Binding algorithm to container type lessen genericity of code.
... but is sometimes done in practice when the generic framework doesn't provide the concepts for optimal implementations; e.g. std::map::lower_bound. In the STL, that would be the case with for_each over segmented sequences. A better solution, however, would be to define a concept for segmented iterators and write a generic segmented for_each algorithm. -- Eric Niebler BoostPro Computing http://www.boostpro.com
On 11/17/2010 1:50 PM, Eric Niebler wrote:
On 11/17/2010 4:24 PM, joel falcou wrote:
Binding algorithm to container type lessen genericity of code.
... but is sometimes done in practice when the generic framework doesn't provide the concepts for optimal implementations; e.g. std::map::lower_bound. In the STL, that would be the case with for_each over segmented sequences. A better solution, however, would be to define a concept for segmented iterators and write a generic segmented for_each algorithm.
Right. I almost read this as you suggesting to use segmented iterators for the OP's problem, but I don't think that's what you're suggesting. The OP's original problem (as I understand it) was to provide a generic framework to use thrust::for_each when working with thrust::vector's, boost::fusion::for_each when working with Boost.Fusion sequences, and std::for_each when using any STL-compatible range (the default, basically). Indeed, seems like this would just extend the idea of differentiating whether to dispatch to a std::for_each or a segmented for_each. I only meant to suggest that one would have to somehow tie the sequence to a particular iteration mechanism (i.e., a for_each implementation). The use of member function notation was a poor choice which kicked up more dust than I thought :/ - Jeff
// the complex algorithm we want to implement template< class Algorithm , class Sequence> void do_something( Sequence&seq ) { ... Algebra::for_each( seq , op() );
^^^^^^^ Algorithm
... }
Yes right, thanks.
std::vector< double > vec1; vec1.for_each(op()); thrust::device_vector< double > vec2; vec2.for_each(op());
Yes, it might by possible to bind for_each to a specific container. But, it would also be nice to have an additional degree of freedom in the way how things are iterated. Think for example on something like template< class Seq1 , class Seq2 , class BinarayOp for_each( Seq1 &seq1 , Seq2 &seq2 , BinaryOp op ) { } which could be implemented directly by iteration of both sequences or by use zip_iterators.
participants (5)
-
Eric Niebler -
Jeffrey Lee Hellrung, Jr. -
joel falcou -
Karsten Ahnert -
vicente.botet