[Bug libstdc++/41351] std::rotate on RAI does not conform to ISO complexity requirement

["potswa at mac dot com" <gcc-bugzilla at gcc dot gnu dot org>]

------- Comment #41 from potswa at mac dot com  2009-10-30 19:07 -------
Created an attachment (id=18934)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=18934&action=view)
table of benchmarks comparing various algorithms and parameters

As the Euclidean ring division algorithm sweeps the memory range at least once
per ring, you can see from this table that the present RAI implementation
performs very poorly for small k greater than one.

The final row, "fwd +copy", is a new proposal which adds the std::copy calls to
the existing forward iterator algo. It remains compatible with bidirectional
iterators and, from this data, looks pretty good. Its moderately bad showing in
the final column I don't yet understand.

The special cases for left and right by one should use std::move and
std::move_backward, respectively, I guess. I'm not sure what state of testing I
left things at before, but let's look at the performance numbers first.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=41351