Re: [boost] [range][iterator] contiguous iterators
From [boost-users]: Am 18.03.2013 16:06, schrieb Jeffrey Lee Hellrung, Jr.:
On Sat, Mar 16, 2013 at 7:42 AM, Stefan Strasser <strasser@uni-bremen.de is there any way to generically determine at compiletime whether an iterator or a boost range refers to contiguous memory?
is_contiguous<T *>::value == true is_contiguous<vector<T>::iterator>::value == true is_contiguous<std::list<T>::iterator>::value == false AFAIK, not presently, but this has been discussed quite a bit in several past threads on the Boost developers list.
Then I'd like to suggest this again to the maintainers of Boost.Iterator and Boost.Range. I'd also like to suggest another addition to Boost.Range: a RangeOutputIterator, i.e. an OutputIterator that doesn't only accept single values, but assignment of ranges: template<class RangeOutputIterator> ... (...RangeOutputIterator out){ *out=range; where range can be any Boost.Range. You can find an implementation of this concept here, in the form of an back insert iterator that can insert entire ranges into a vector: http://pastebin.com/9M5rPDh9 Using these two things together can make generic algorithms as efficient as is possible, e.g. if the container that is being written to is a vector and the value type is a POD, there's one call to std::memcpy. think e.g. about file or database operations like database.get(1024*1024,out); This is in my "namespace detail" right now and I'd be willing to help make it public and document it. Stefan
On 19-03-2013 11:03, Stefan Strasser wrote:
I'd also like to suggest another addition to Boost.Range: a RangeOutputIterator, i.e. an OutputIterator that doesn't only accept single values, but assignment of ranges:
template<class RangeOutputIterator> ... (...RangeOutputIterator out){ *out=range;
where range can be any Boost.Range. You can find an implementation of this concept here, in the form of an back insert iterator that can insert entire ranges into a vector: http://pastebin.com/9M5rPDh9
Using these two things together can make generic algorithms as efficient as is possible, e.g. if the container that is being written to is a vector and the value type is a POD, there's one call to std::memcpy. think e.g. about file or database operations like database.get(1024*1024,out);
This is in my "namespace detail" right now and I'd be willing to help make it public and document it.
Have you considered http://www.boost.org/doc/libs/1_53_0/libs/range/doc/html/range/reference/alg... ? E.g. using boost::push_back( my_container, my_range ) should be optimally efficient and more direct than using an output range. -Thorsten
Am 19.03.2013 01:08, schrieb Kyle Lutz:>> is_contiguous<T *>::value == true
is_contiguous<vector<T>::iterator>::value == true is_contiguous<std::list<T>::iterator>::value == false
I needed this functionality for Boost.Compute in order to determine if a region of memory could be copied directly to the GPU or if an intermediate std::vector was required. It works just like your example except I used the name is_contiguous_iterator instead.
The implementation is here: https://github.com/kylelutz/compute/blob/master/include/boost/compute/detail...
Good, then we just have to collaborate to get it into a public namespace. Is enable_if there to not require #include <vector>? Could you add one for boost::container::vector? Am 19.03.2013 11:29, schrieb Thorsten Ottosen:
I'd also like to suggest another addition to Boost.Range: a RangeOutputIterator, i.e. an OutputIterator that doesn't only accept single values, but assignment of ranges:
template<class RangeOutputIterator> ... (...RangeOutputIterator out){ *out=range;
Have you considered http://www.boost.org/doc/libs/1_53_0/libs/range/doc/html/range/reference/alg...
boost::push_back( my_container, my_range )
should be optimally efficient and more direct than using an output range.
No, and thanks, but "more direct" is "too direct" in this case. The algorithm should remain generic and not only be able to output into containers. going back to my example of database.get, you might wanna use it to load image data into a large container, or use it to load 4 byte into an integer.
On 19-03-2013 12:01, Stefan Strasser wrote:
Have you considered http://www.boost.org/doc/libs/1_53_0/libs/range/doc/html/range/reference/alg...
boost::push_back( my_container, my_range )
should be optimally efficient and more direct than using an output range.
No, and thanks, but "more direct" is "too direct" in this case. The algorithm should remain generic and not only be able to output into containers.
going back to my example of database.get, you might wanna use it to load image data into a large container,
No problem here.
or use it to load 4 byte into an integer.
Hm. How would that work? What concepts do you have in mind? Do yo want to interpret an int as a container of 4 bytes? -Thorsten
Am 19.03.2013 14:07, schrieb Thorsten Ottosen:
going back to my example of database.get, you might wanna use it to load image data into a large container,
No problem here.
right.
or use it to load 4 byte into an integer.
Hm. How would that work? What concepts do you have in mind? Do yo want to interpret an int as a container of 4 bytes?
no, not as part of what I'm proposing to be added to Boost.Range. it was an example only. the point is that there are many algorithms that you don't want to only be able to output into containers, as you've suggested using push_back, but into anything, using an OutputIterator. like copy(). but there are cases you can't use a regular OutputIterator for efficiency reasons, because the result has to be a bulk call to std::memcpy if that's possible, not iterating one by one. so instead of writing a generic function: template<class OutputIterator> //'char' value type void load(OutputIterator); you are forced to use template<class Container> void load(Container &); for performance reasons. which you don't want, see above. please see my original email for how I'm suggesting to solve this. even copy() could benefit from this, e.g.: copy(Range const &r,OutputIterator out){ copy(r,out,category of out); } copy(Range const &r,OutputIterator out,range_output_iterator_tag){ *out=r; } "out" can now copy the whole range at once, using vector.reserve(). or sputn() it into a file without buffering. or whetever else. (for that, it needs is_contiguous<>) Stefan
Am 19.03.2013 15:23, schrieb Stefan Strasser:
even copy() could benefit from this, e.g.:
copy(Range const &r,OutputIterator out){ copy(r,out,category of out); }
copy(Range const &r,OutputIterator out,range_output_iterator_tag){ *out=r; }
"out" can now copy the whole range at once, using vector.reserve(). or sputn() it into a file without buffering. or whetever else. (for that, it needs is_contiguous<>)
note that, although copy() doesnt, the algorithm might output multiple ranges, or a mix between ranges and values. so you can't just pass the input range to whatever you want to do. simple example: load(OutputIterator out){ char buffer[N]; do{ file.load(buffer,N); *out=buffer; }while(!file.eof()); }
On 19-03-2013 15:23, Stefan Strasser wrote:
Am 19.03.2013 14:07, schrieb Thorsten Ottosen:
going back to my example of database.get, you might wanna use it to load image data into a large container,
No problem here.
right.
or use it to load 4 byte into an integer.
Hm. How would that work? What concepts do you have in mind? Do yo want to interpret an int as a container of 4 bytes?
no, not as part of what I'm proposing to be added to Boost.Range. it was an example only.
the point is that there are many algorithms that you don't want to only be able to output into containers, as you've suggested using push_back, but into anything, using an OutputIterator. like copy().
but there are cases you can't use a regular OutputIterator for efficiency reasons, because the result has to be a bulk call to std::memcpy if that's possible, not iterating one by one.
so instead of writing a generic function: template<class OutputIterator> //'char' value type void load(OutputIterator);
you are forced to use
template<class Container> void load(Container &);
for performance reasons. which you don't want, see above. please see my original email for how I'm suggesting to solve this.
even copy() could benefit from this, e.g.:
copy(Range const &r,OutputIterator out){ copy(r,out,category of out); }
copy(Range const &r,OutputIterator out,range_output_iterator_tag){ *out=r; }
"out" can now copy the whole range at once, using vector.reserve(). or sputn() it into a file without buffering. or whetever else. (for that, it needs is_contiguous<>)
It appears to me that you can just do that by implementing a wrapper class that enables you to call boost::push_back. If its too contrieved to use push_back, we may add a function called write: template< class OutPutRange, class Rng > OutPutRange& write( OutPutRange& to, const Rng& from ) { to.write( from ); return to; } Anyway, I guess its possible to define an "output range", but it does not seem desirable stick it into the existing interface for output iterators, does it? -Thorsten
On 19-03-2013 16:18, Thorsten Ottosen wrote:
It appears to me that you can just do that by implementing a wrapper class that enables you to call boost::push_back. If its too contrieved to use push_back, we may add a function called write:
template< class OutPutRange, class Rng > OutPutRange& write( OutPutRange& to, const Rng& from ) { to.write( from ); return to; }
Thinking about it, I hate the name "output range" for something which is /not/ a range (that is, it does conform to the [begin(),end()) definition). Mayby the concept here is a "Sink" or "RangeSink", so its not confused with "Sink" from http://www.boost.org/doc/libs/1_53_0/libs/iostreams/doc/concepts/sink.html -Thorsten
Hi Thorsten, Am 19.03.2013 16:18, schrieb Thorsten Ottosen:
It appears to me that you can just do that by implementing a wrapper class that enables you to call boost::push_back. If its too contrieved to use push_back, we may add a function called write:
I fail to see the difference between a "wrapper class that enables you to [output data]" and an output iterator.
template< class OutPutRange, class Rng > OutPutRange& write( OutPutRange& to, const Rng& from ) { to.write( from ); return to; }
Anyway, I guess its possible to define an "output range", but it does not seem desirable stick it into the existing interface for output iterators, does it?
it's desirable because a "range output iterator" as I call it for now is a regular output iterator. it has the same semantics as an output iterator, with the addition that it can accept ranges. this means that it can be passed to any algorithm accepting an OutputIterator. only if you choose to optimize an algorithm for ranges you have to write any additional code, e.g. by tag dispatching (see previous email). if you don't like the interface for inserting ranges I use, '*out=range', maybe 'out << range' or even 'out.insert(range)' suits it more, but 'out' has to be a regular output iterator for the whole thing to make sense. if you have to write 2 algorithms again, one accepting an output iterator, and the other one accepting this "wrapper class that can write ranges", it misses the point. Stefan
participants (2)
-
Stefan Strasser -
Thorsten Ottosen