Here is an update to cycle_iterator. This is based on the original design by Gennadiy Rozental. After fairly extensive performance testing I am getting good results (compared to my old implementation which was hand-written, not based on boost iterators), after adding operator[]. There are two versions, both give about the same performance in my tests. One version, which I prefer, modifies the underlying base iterator for operations such as increment. The other implementation never touches the base iterator, but modifies an integral offset value. Also included is a Ring container adaptor class, which adapts a container (e.g., std::vector) to a ring. Basic operations are there, but more can be added. Also a simple test program.
"Neal D. Becker" <ndbecker2@verizon.net> writes:
Here is an update to cycle_iterator. This is based on the original design by Gennadiy Rozental. After fairly extensive performance testing I am getting good results (compared to my old implementation which was hand-written, not based on boost iterators), after adding operator[].
... which got poor results? Just wondering. BTW, not to keep nitpicking but I object to the name cycle_facade. iterator_facade really is just a facade for iterators, but cycle_facade is a full-fledged iterator and should be called cycle_iterator. -- Dave Abrahams Boost Consulting http://www.boost-consulting.com
David Abrahams wrote:
"Neal D. Becker" <ndbecker2@verizon.net> writes:
Here is an update to cycle_iterator. This is based on the original design by Gennadiy Rozental. After fairly extensive performance testing I am getting good results (compared to my old implementation which was hand-written, not based on boost iterators), after adding operator[].
... which got poor results? Just wondering.
I got benchmarks about 1/2 speed of hand-written implementation for all versions of the cycle_iterator until I added operator[]. Testing was mainly using the Ring class. Not much of a benchmark, but here is what I used: ,----[ /home/nbecker/shannon/TestAloha/TestRing3.cc ] | #include "Ring3.H" | #include <numeric> | #include <iostream> | | int main() { | Ring<int> r1 (1000000); | std::fill (r1.begin(), r1.end(), 1); | | int sum = 0; | for (int test = 0; test < 200; test++) { | for (size_t i = 0; i < r1.size(); i += 2) | sum += r1[i]; | } | // return sum; | std::cout << sum << '\n'; | } `---- I wanted to see how much overhead was associated with indexing operations. Poor results were obtained when Ring class said: T& operator[] (int n) { return *(it+n); } I guess this has to construct a temp iterator, advance it , then dereference it. Now Ring says: T& operator[] (int n) { return it[n]; } and cycle_iterator #1 says: reference operator[] (int n) { return *reduce (base+n, b, e); } similarly, the 2nd implementation says: reference operator[] (int n) { return *(base + index()); } Both of these latter versions give similar results. I switched from iterator_adaptor to facade to see if performance changed noticeably. It didn't. But honestly, facade is easier for me to understand, so I prefer it. The use of CRTP is iterator_adaptor exceeds my brain's recursion limit. BTW, I have added some more stuff to Ring, as well as fixing the glaring error due to lack of copy constructor.
"Neal D. Becker" <ndbecker2@verizon.net> writes:
I got benchmarks about 1/2 speed of hand-written implementation for all versions of the cycle_iterator until I added operator[].
You mean you were testing the speed of your iterator's operator[]? That's not a very important test. operator[] is one of the least-used iterator operations. -- Dave Abrahams Boost Consulting http://www.boost-consulting.com
Here is an update to cycle_iterator. This is based on the original design by Gennadiy Rozental. After fairly extensive performance testing I am getting good results (compared to my old implementation which was hand-written, not based on boost iterators), after adding operator[].
Neal, one important issue I came across: Say I have a collection, and I want to iterate over all its elements. For some reason, I don't want to do it from first to last, but I want to start at the 7th element, iterate to the end, jump back to the beginning, continue, and finish at the 6th element. Sounds like a case for cycle_iterator, right? Here we go: vector<int> v(10); // Begins at 7th element: cycle_facade<...> b = make_cycle_facade(v.begin()+7, v.begin(), v.end()); // Ends one past the 6th element: cycle_facade<...> e = make_cycle_facade(v.begin()+7, v.begin(), v.end()); I guess you already see the problem: the loop for( cycle_facade<...> it = b; it != e; ++it ) // do something is exited immediately, since b and e here are considered _equal_ (which is not what we intended). My solution back then was to keep an internal counter which counts how often the iterator got "past the end". In the case above, b would have a counter of 0, whereas e got past the end once, i.e. the counter is 1. Hence, b and e are no longer equal. You might want to check out cyclic_iterator in boost/view from the CVS Sandbox (and yes, it also uses the new iterator_adaptors). I am aware that this might not be relevant in your case; yet, I'd like to hear your opinion on this "equality" problem. - Roland
Roland Richter wrote:
Here is an update to cycle_iterator. This is based on the original design by Gennadiy Rozental. After fairly extensive performance testing I am getting good results (compared to my old implementation which was hand-written, not based on boost iterators), after adding operator[].
Neal,
one important issue I came across:
Say I have a collection, and I want to iterate over all its elements. For some reason, I don't want to do it from first to last, but I want to start at the 7th element, iterate to the end, jump back to the beginning, continue, and finish at the 6th element. Sounds like a case for cycle_iterator, right? Here we go:
vector<int> v(10);
// Begins at 7th element: cycle_facade<...> b = make_cycle_facade(v.begin()+7, v.begin(), v.end());
// Ends one past the 6th element: cycle_facade<...> e = make_cycle_facade(v.begin()+7, v.begin(), v.end());
I guess you already see the problem: the loop
for( cycle_facade<...> it = b; it != e; ++it ) // do something
is exited immediately, since b and e here are considered _equal_ (which is not what we intended).
My solution back then was to keep an internal counter which counts how often the iterator got "past the end". In the case above, b would have a counter of 0, whereas e got past the end once, i.e. the counter is 1. Hence, b and e are no longer equal.
You might want to check out cyclic_iterator in boost/view from the CVS Sandbox (and yes, it also uses the new iterator_adaptors).
I am aware that this might not be relevant in your case; yet, I'd like to hear your opinion on this "equality" problem.
Very interesting stuff. I guess the problem I am addressing is a little different. If you want to cirularly iterate over an existing container, you're right, there is a problem of what to do with end(). My problem is slightly different - I am free to just allocate one extra element in the container. The constructor Ring(size_t n) will allocate a container of size n+1. Problem solved. Answer is you have no business asking to iterate over the whole container, you can only iterate over 1 less. Still I'm very interested in your approach, but I have some questions. 1) The constructors I used take 3 arguments, the begin, end, and current position. I don't see how this would work with only 2 arguments. If I do: make_iterator (v.begin()+2, v.end()) then this iterator will be associated with the incorrect size, right? 2) If I have a Ring class, it needs a copy constructor. This copies the underlying container, then needs to setup a new iterator. It is desirable to be able to: a) get the state of the old iterator b) construct a new iterator with this state If you look at my Ring and iterator, you see that iterator has a function "offset" that basically retrieves the original state information, and the 3 arg constructor allows setting the state. Do you think something similar is needed for you implementation?
Neal D. Becker wrote:
Still I'm very interested in your approach, but I have some questions.
1) The constructors I used take 3 arguments, the begin, end, and current position. I don't see how this would work with only 2 arguments. If I do:
make_iterator (v.begin()+2, v.end())
Write make_cyclic_iterator( v.begin(), v.end() ) + 2 instead. I decided that make_cyclic_iterator() constructs an iterator pointing to the beginning. Ok, not elegant, I might reconsider it.
2) If I have a Ring class, it needs a copy constructor. This copies the underlying container, then needs to setup a new iterator. It is desirable to be able to: a) get the state of the old iterator b) construct a new iterator with this state
If you look at my Ring and iterator, you see that iterator has a function "offset" that basically retrieves the original state information, and the 3 arg constructor allows setting the state. Do you think something similar is needed for you implementation?
Yep, a copy ctor or somehing is also missing. As soon as I find the time ... - Roland
I like your suggestion, Roland. Here is my adaptation (I will have to add credits and copyright later). It counts wraps as you suggest. I found it easier to implement and understand by basing it on an integral offset from a base. It all becomes pretty simple by calculating a "realposition" which is wraps*size+position. This is like a virtual index into an infinitely long sequence. For the constructor, you give a pair of iterators and an optional offset, which defaults to 0. I think this covers all uses. Since the realposition can easily exceed an int, I decided to make this a separate parameter "offset_t" which defaults to int. Included is the iterator, a Ring class based on it, and a small test.
Neal Becker wrote:
I like your suggestion, Roland. Here is my adaptation (I will have to add credits and copyright later).
It counts wraps as you suggest. I found it easier to implement and understand by basing it on an integral offset from a base. It all becomes pretty simple by calculating a "realposition" which is wraps*size+position. This is like a virtual index into an infinitely long sequence.
Definitely, this solution is elegant and better readable. Plus, it passes the test I use for cyclic_iterator (in the sandbox) after a minor modification: For unknown reason, MSVC chokes on typename std::iterator_traits<BaseIterator>::value_type twice ('iterator_category' : is not a member of 'operator``global amespace'''), but accepts typename boost::iterator_value<BaseIterator>::type I suggest to add your implementation to Boost.Iterator! Does this require a review, or mini review, if there is something like that? - Roland
Roland Richter <roland@flll.jku.at> writes:
Neal Becker wrote:
I like your suggestion, Roland. Here is my adaptation (I will have to add credits and copyright later). It counts wraps as you suggest. I found it easier to implement and understand by basing it on an integral offset from a base. It all becomes pretty simple by calculating a "realposition" which is wraps*size+position. This is like a virtual index into an infinitely long sequence.
Definitely, this solution is elegant and better readable. Plus, it passes the test I use for cyclic_iterator (in the sandbox) after a minor modification:
For unknown reason, MSVC chokes on
typename std::iterator_traits<BaseIterator>::value_type
twice ('iterator_category' : is not a member of 'operator``global amespace'''), but accepts
typename boost::iterator_value<BaseIterator>::type
Right. iterator_value uses boost::iterator_traits, which contains bajillions of workarounds for vc6/7 inadequacies.
I suggest to add your implementation to Boost.Iterator! Does this require a review, or mini review, if there is something like that?
A review would help, but isn't strictly neccessary. It requires at least some extra confidence on my part. If cycle_iterator is thoroughly tested, including concept checks, and the documentation is readable and complete, that will go a long way. I don't know the current status of these things... -- Dave Abrahams Boost Consulting http://www.boost-consulting.com
participants (4)
-
David Abrahams -
Neal Becker -
Neal D. Becker
-
Roland Richter