[boost] Re: cycle_iterator update

From: Neal D. Becker (ndbecker2_at_[hidden])
Date: 2004-04-14 10:44:46

David Abrahams wrote:

> "Neal D. Becker" <ndbecker2_at_[hidden]> 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.