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

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

[potswa at mac dot com]

According to C++03 and C++0x, std::rotate has "Complexity: At most last - first
swaps."

The random iterator implementation does not call std::swap at all, but rather
creates a temporary variable and uses the assignment operator to implement
swapping. std::swap often has different complexity than two assignments, so
this is non-conforming. Note that the standard requires that std::swap on any
container take constant time, but assignment will take linear time.

The temporary variable appears to be an optimization for native machine types:
rather than move each object to its final location with a swap operation, move
it with an assignment and avoid performing twice the necessary assignments.
This is a good goal, and perhaps it may be achieved using a special
temporary-variable template type which calls std::swap for all but some subset
of types.


-- 
           Summary: std::rotate on RAI does not conform to ISO complexity
                    requirement
           Product: gcc
           Version: 4.2.1
            Status: UNCONFIRMED
          Severity: major
          Priority: P3
         Component: libstdc++
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: potswa at mac dot com


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

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

[chris at bubblescope dot net]

------- Comment #1 from chris at bubblescope dot net  2009-09-14 07:24 -------
In C++0x, this problem will go away, because move constructors will be used,
which leads to the most efficient implementation for both large and small types
(assuming they implement a move constructor at least as efficient as swap).
However, the wording is misleading and I might see if it can be changed.

In C++03, being pedantic, I'm not sure if we have to call std::swap, although
as you say it would make things go faster for certain types. This wording is
used in some other places, for example stable_partition, which cannot be
implemented just with std::swap.

While you have bought up a obvious case of inefficiency, I would advise leaving
it as is, and compiling your code with -std=g++0x on a recent compiler. If you
are using standard containers, this should give you faster code, without any
changes at all. With your own code, it would require you defining the move
constructor and move assignment operators.


-- 

chris at bubblescope dot net changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |chris at bubblescope dot net


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

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

[paolo dot carlini at oracle dot com]

------- Comment #2 from paolo dot carlini at oracle dot com  2009-09-14 09:32 -------
Indeed, I agree with most of the points Chris is making, in particular I find
extremely important the point about stable_partition. I only want to add that
in principle in this specific case, dispatching to an overload using only swaps
(like the one for bidirectional iter) for any type != scalar for example would
be of course trivial. For sure there would be border cases in which we would
regress performance-wise. Do we have any idea what other implementations are
doing here? In particular stlport for example, which also inherited the
original HP/SGI three overloads.


-- 

paolo dot carlini at oracle dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |paolo dot carlini at oracle
                   |                            |dot com


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

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

[paolo dot carlini at oracle dot com]

------- Comment #3 from paolo dot carlini at oracle dot com  2009-09-14 10:49 -------
I'll double check but apparently both STLport and RogueWave are similar to
v3...


-- 


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

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

[potswa at mac dot com]

------- Comment #4 from potswa at mac dot com  2009-09-14 16:35 -------
I doubt that stable_partition can't be implemented with std::swap. If I
understand you the problem lies in the temporary_buffer, which is uninitialized
memory and hence un-swappable. One solution would be simply to initialize it.
Already value_type is seeing its constructor called repeatedly, might as well
use the default constructor rather than the copy constructor.

Another solution would be to use the temporary_buffer for a parallel vector of
iterators, pointers, or indexes rather than values. Insert references to the
objects at desired locations in ascending order in [temp, temp+middle-first)
and descending order in (temp+last-first,temp+middle-first] (that is, the
sequences meet in the middle). Then use the buffer to reorder the sequence in
fewer than n std::swaps. (See reorder_destructive() in
http://stackoverflow.com/questions/838384/1267878#1267878). This buffer would
be smaller than in the present implementation except for tiny structures.


-- 


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

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

[chris at bubblescope dot net]

------- Comment #5 from chris at bubblescope dot net  2009-09-14 17:00 -------
You cannot assume the elements you are sorting have a default constructor. You
can however certainly use a separate array of indices, and then swap at the
end, so I withdraw that comment. However, this also only complicates the
problem, as it suggests we should also fix stable_partition.

A long time ago I tried improving the standard library to use whichever of swap
or copy was more efficent, and ended up effectively reinventing rvalue
references using template wrappers.

Given any patches would only be in a new version of gcc, as this is not a
regression, as we haw never done it "properly", would you be happy instead
using the c++0x support in those new compiler?


-- 


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

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

[potswa at mac dot com]

------- Comment #6 from potswa at mac dot com  2009-09-14 18:00 -------
If the alternative stable_partition is faster, maybe it should be used anyway.
For large blocks, virtual memory allocation time may dominate computation, so
it should certainly be faster sometimes.

Back to rotate, I was just answering another question on stackoverflow.com when
I noticed that rotate on a two-dimensional vector would be slow and memory
hungry. I don't actually use it.

I haven't checked out the rvalue reference stuff yet, and from what I see I
don't understand how stl_algo.h would be improved by it without specifying "&&"
anywhere, but I'll take your word for it. Is there another header I missed?

I do still believe that it would be best to let the complexity of a swap be
exactly the runtime of std::swap<value_type>, though. Given that there are
several ways to optimize this code, the standard appears to be recommending a
std::swap specialization as the preferred "helper function," and there does not
appear to be a defect in it.


-- 


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

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

[chris at bubblescope dot net]

------- Comment #7 from chris at bubblescope dot net  2009-09-14 18:11 -------
Only a svn copy of stl_algo.h has the rvalue reference stuff for
stable_partition. We use a number of macros, like _GLIBCXX_MOVE, to wrap
various parts of the algorithms, so they work in both c++03 and c++0x.

It is a requirement of c++0x that algorithms like rotate and stable_partition
work with move-only types, so the current implementations never copy at all. I
believe, without evidence, that these rotate / stable_partition implementations
will be as fast as maintaining a separate pointer list when sorting a range of
vector<int>s, for example. Of course a new implementation of any algorithm
which satisfies all the standard requirements, and is faster than the existing
ones in all cases it was used, would I'm sure be greatfully accepted, modulo
copyright assignments and the like.


Of course this does not help people right now, using C++03. Certainly it is bad
how long rotate takes, but similar problems have long existed, to a greater or
lesser extent, with many other algorithms including sort and stable_sort.


-- 


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

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

[potswa at mac dot com]

------- Comment #8 from potswa at mac dot com  2009-09-14 21:36 -------
Well, if fast is good, maybe you will consider this:

        const _Distance __d = __gcd(__n, __k), __r = __n / __d;

        for ( _Distance __i = 0; __i < __d; ++ __i ) {
                _ValueType __tmp = *__first;
                _RandomAccessIterator __p = __first + __l;

                for ( _Distance __j = 0; ; ) {
                        swap( __tmp, * __p );
                        if ( ++ __j >= __r ) break;
                        if ( __p >= __middle ) __p -= __n - __l;
                        else __p += __l;
                }
                ++ __first;
        }


It's a few times faster than the current implementation for the case of many
small rings, and seems to be within 1% otherwise for both large and small data
structures. (The way __tmp is used, it can always be optimized out.) There is a
small penalty which seems to go away if I manually unroll the inner loop, which
is annoying.

It's also much, much more elegant.


-- 


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

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

[paolo dot carlini at oracle dot com]

------- Comment #9 from paolo dot carlini at oracle dot com  2009-09-14 23:41 -------
David, thanks for your help, I think that in case something similar can be
tested to work fine with move-only types, we could certainly do the change,
it's small enough. In general, it would be nice if you could file a copyright
assignment, which would entitle you to contribute arbitrarily large changes (in
that case, I would of course ask you to properly test the change, submit it as
a patch vs current cvs head, etc.)


-- 


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

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

[potswa at mac dot com]

------- Comment #10 from potswa at mac dot com  2009-09-14 23:59 -------
I'll look into it. That's a long list to do and learn ;v) .

I think the general idea here is that the compiler is good at optimizing out
the useless moves generated by swap. It turns out that my code has less of a
straight line access pattern than the current impl, so I'd like to rewrite
first in any case. Can you point me to the test cases?


-- 


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

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

[paolo dot carlini at oracle dot com]

------- Comment #11 from paolo dot carlini at oracle dot com  2009-09-15 00:07 -------
David, it works like this: first you check out via svn a local copy of the
current GCC head. Then, you do your local changes to the code, the library in
this case, and you validate your changes by running 'make check' in the build
directory. Frankly, summarizing everything you need to know here, isn't a
trivial task: quite a bit of information for contributors is available from the
GCC web pages:

  http://gcc.gnu.org/svn.html
  http://gcc.gnu.org/contribute.html

In any case, you can browse the svn from here http://gcc.gnu.org/viewcvs/trunk/


-- 


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

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

[potswa at mac dot com]

------- Comment #12 from potswa at mac dot com  2009-09-15 08:55 -------
Just for safekeeping, here's the body of the final code. It's much faster than
the current revision on my machine, 2.2 sec for 100 iterations rotating a 10
million int vector 5 places left or right, vs 10.5 sec currently. Also it
doesn't use a separate gcd function; the computation is built in.

        for ( ;; ) {
                 // preconditions: range in [p, p + n), stride = k
                if ( __k * 2 < __n ) {
                        _RandomAccessIterator __q = __p + __k;
                        for ( _Distance __i = 0; __i < __n - __k; ++ __i ) {
                                iter_swap( __p ++, __q ++ );
                        }
                        __n = __n % __k;
                        if ( __n == 0 ) return;
                        swap( __n, __k );
                        __k = __n - __k;
                } else {
                        __k = __n - __k;
                        _RandomAccessIterator __q = __p + __n;
                        __p = __q - __k;
                        for ( _Distance __i = 0; __i < __n - __k; ++ __i ) {
                                iter_swap( -- __p, -- __q );
                        }
                        __n = __n % __k;
                        if ( __n == 0 ) return;
                        swap( __n, __k );
                }
        }


-- 


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

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

[paolo dot carlini at oracle dot com]

------- Comment #14 from paolo dot carlini at oracle dot com  2009-09-15 09:59 -------
Created an attachment (id=18582)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=18582&action=view)
Draft, passes the testsuite


-- 


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

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

[paolo dot carlini at oracle dot com]

------- Comment #13 from paolo dot carlini at oracle dot com  2009-09-15 09:58 -------
Thanks. I'm attaching a slightly tweaked version of the patch, avoiding
postincrement of the iterators and reformatted according to our conventions,
which I successfully regtested. A minor issue I can see, in principle __k * 2
can overflow, _Distance is signed, we should rewrite the check slightly
differently to avoid that risk. Chris, what do you think?


-- 


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

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

[paolo dot carlini at oracle dot com]

------- Comment #15 from paolo dot carlini at oracle dot com  2009-09-15 10:16 -------
If I'm not mistaken, (__k < __n - __k) would be just fine.


-- 


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

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

[paolo dot carlini at oracle dot com]

------- Comment #16 from paolo dot carlini at oracle dot com  2009-09-15 14:16 -------
I'm also carrying out some experiments with builtin types, like int, and the
patched implementation indeed appears to perform well, usually beating by a
good amount the current implementation, easily 2x-3x for large k. Its Achille's
heel seems k == 1, whereas the current algorithm is faster, about 1.5-2.0 x.
These numbers are for an i7 920.


-- 


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

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

[potswa at mac dot com]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 875 bytes --]



------- Comment #17 from potswa at mac dot com  2009-09-15 14:33 -------
Hmm, on my Core2 my impl still beats the present one on many cases of shift by
1, but the margin is narrower.

Shift by 1 is the only case where the temporary can really help, and I
eliminated it completely. I suppose I should special-case it back in for k = ±
1.

Also, before a commit I'd like to see about installing this algo for the
forward and bidirectional cases. If it's not given n, it can compute it as a
side effect of a run through the first loop. Once n is found, the second,
backwards-iterating loop can be used with the bidirectional iterator and the
first, forwards loop can be used with a forward iterator. These will carry the
same optimal one-pass memory behavior and (n - gcd(n,k)) swap complexity to all
the overloads.


-- 


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

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

[paolo dot carlini at oracle dot com]

------- Comment #18 from paolo dot carlini at oracle dot com  2009-09-15 14:41 -------
Thanks David for your further ideas. I want to wait a bit other people, but I
don't know if specializing for k == 1 is worth the trouble, and the patch
becomes bigger. Really, if you are willing to help more, you should consider
sending an email to assignments@gnu.org and do the paperwork for the copyright
assignment. The only other option I can see for you, is collaborating behind
the scenes, with, say, Chris, but then your name cannot appear in the
ChangeLog, that would be a pity.


-- 


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

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

[chris at bubblescope dot net]

------- Comment #19 from chris at bubblescope dot net  2009-09-15 14:45 -------
I think this generally looks good. The testsuite could do with some
improvement, there are quite a lot of cases for this algorithm, and it's
probably worth testing they all work properly.

I unfortunately cam't execute the code at the moment so I apologise if this is
wrong, but it looks like the existing code works fine with
std::rotate(NULL,NULL,NULL), while yours will break. It's not even completely
clear if this should work, but as a QOI issue it would probably be nice if it
did. In general, checking all rotates of length 0 to 10ish would I think be a
nice check that your code works properly.


-- 


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

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

[paolo dot carlini at oracle dot com]

------- Comment #20 from paolo dot carlini at oracle dot com  2009-09-15 14:53 -------
Chris, please check my actual patch, the code inline above is just the main
body. Besides that, are you willing to contribute a new testcase for rotate, at
the moment David can't, it would be too much code, I'm afraid.


-- 

paolo dot carlini at oracle dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|0                           |1
   Last reconfirmed|0000-00-00 00:00:00         |2009-09-15 14:53:02
               date|                            |


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

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

[potswa at mac dot com]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 724 bytes --]



------- Comment #21 from potswa at mac dot com  2009-09-15 14:56 -------
Just to be clear that "working properly" in this context means "working faster"
;v) .

I just coded up a special case for k = ± 1 that uses std::copy, which should
map to memmove for std::vector::iterator. That should beat anything else.

When I posted the code I said "for safekeeping." I would like to officially
become a contributor :v) but this is taking a fair amount of time and
theoretically something could make me drop it… but I don't have a job right now
so that's unlikely.

Also, what happens with std::__gcd? We erase it, right, and leave any
surreptitious uses in the cold?


-- 


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

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

[paolo dot carlini at oracle dot com]

------- Comment #22 from paolo dot carlini at oracle dot com  2009-09-15 15:04 -------
__gcd isn't important for now, there is no reason to remove it. At some point
we can erase it and another small function which Chris left, but there is no
hurry to do that.

Otherwise, I'm seeing the same slow down for __k == __n - 1, I suppose this is
what you meant by __k = -1 (__k, as defined, can't really be negative as far as
I can see). Also, always remember that in any case we have to cope with
move-able only type.

Besides that, just let us know what you prefer to do: you can contribute a few
lines of code now, or we can wait for your assignment to be in place. To be
clear again: you can't contribute anything larger than, say 50 lines of code
without an assignment in place.


-- 


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

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

[potswa at mac dot com]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 978 bytes --]



------- Comment #23 from potswa at mac dot com  2009-09-15 15:29 -------
With the new special case, I get 3x faster than current for n = 100, k = 99.
Now it weighs in at 45 lines in my style, before conversion to official style,
and not coincidentally I don't really feel like posting it again :vP . I'll do
the legal stuff next.

Note that a significant speedup is available if std::copy is used for other
values of k than 1 and n-1. I just observed 4x over my algorithm and 7.5x over
the current one for n = 100 k = n-2… which seems disproportionate but behavior
is correct. (The advantage disappears for large n.) This strategy generally
requires constructing min( k, n-k ) temporaries. What's the policy on that kind
of optimization? The temporaries can only go on the stack, which makes things
hairy. Although "isolated cases" benefit, its most reasonable to only
special-case left and right shift by 1, right?


-- 


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

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

[paolo dot carlini at oracle dot com]

------- Comment #24 from paolo dot carlini at oracle dot com  2009-09-15 15:37 -------
My gut feeling is that left and right by one is the special case we only want
to treat separately, but we can always proceed incrementally, and add
optimizations when people really ask. Remember that code size also counts, as
general maintainability. There are trade-offs.

Anyway, good for the paperwork. Important: remember to keep the maintainers
(me, Benjamin, etc) up to date, because FSF doesn't automatically inform us
about the statuses. Hopefully, we can actually commit a substantive improvement
in time for 4.5.0


-- 


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

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

[potswa at mac dot com]

------- Comment #25 from potswa at mac dot com  2009-09-23 21:07 -------
Hello Donald,

A week has passed. Do the papers usually take this long?

        - thanks,
        D

On Sep 15, 2009, at 1:45 PM, assign@gnu.org via RT wrote:

Hello David,

Thank you for contributing to GNU software. We'll send you the appropriate
papers through the post. Please sign and return the original in the envelope
provided. Once the FSF has signed it, we will send you a digital copy in pdf
format for your records.


-- 


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

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

[chris at bubblescope dot net]

------- Comment #26 from chris at bubblescope dot net  2009-10-04 21:50 -------
Just to follow up on an earlier comment, I've tested this patch with a new
improved std::rotate test (to be submitted shortly) which tests all rotations
and positions up to length 20, and it passes fine. Further, it also passes all
C++0x move-only tests, as it only uses iter_swap.


-- 


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

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

[paolo dot carlini at oracle dot com]

------- Comment #27 from paolo dot carlini at oracle dot com  2009-10-04 23:33 -------
Thanks Chris, looking forward to the test, we can first commit it first.


-- 


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

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

[potswa at mac dot com]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 250 bytes --]



------- Comment #28 from potswa at mac dot com  2009-10-05 05:01 -------
I'm still waiting for the IP assignment papers. This is kinda disappointing.
Hopefully I'll get a reply this time…


-- 


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

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

[paolo dot carlini at oracle dot com]

------- Comment #29 from paolo dot carlini at oracle dot com  2009-10-05 09:08 -------
Hi David. This delay is strange indeed, normally the first step doesn't take so
much time. I suggest sending a reminder to assignments@


-- 


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

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

[potswa at mac dot com]

------- Comment #30 from potswa at mac dot com  2009-10-07 19:57 -------
The FSF receptionist says that the lawyer seems to have taken an unannounced
vacation this week. It's now three weeks since I requested the forms (and since
he confirmed my request). What is the timeframe we're shooting for?

On an unrelated note, I checked out the bidirectional iterator implementation a
couple weeks ago and it seems to be completely extraneous. The forward iterator
implementation is very similar to my algorithm, and performs exactly (n -
gcd(n,k)) swaps with a linear memory access pattern. The bidirectional
implementation always performs (n) swaps and sweeps over the memory range
twice, which hurts performance.

So, I'd argue for deleting the bidirectional iterator function and letting the
forward iterator function handle it.


-- 


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

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

[paolo dot carlini at oracle dot com]

------- Comment #31 from paolo dot carlini at oracle dot com  2009-10-07 20:25 -------
4.5.0 still seems a realistic target to me. I would suggest you using the time
it takes for the paperwork to complete (unfortunately, it *always* takes a lot
of time) to figure out a *minimal*, completely trustworthy set of changes,
maybe not the best one, still a noticeable improvement. Further changes can be
prepared for future releases.


-- 


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

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

[potswa at mac dot com]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 1914 bytes --]



------- Comment #32 from potswa at mac dot com  2009-10-10 01:15 -------
I have little experience in this field, so you would probably be a better judge
of the best alternative to complete revision. My suggested code is a complete
rewrite, based on creating a new algorithm from first principles. There's no
going halfway… there's the version I posted, without special cases for
left/right by one, but that's not so much safer as merely inferior.

Now that I've reread the forward iterator version and realized that it's the
same as my algorithm, less my right-rotating case, countdown-style loops, and
std::copy calls, I can see that its performance is nearly as good. If you like,
you can benchmark it against the bidirectional and RAI cases.

If you like the gain from simply deleting the bidirectional and RAI functions,
you might check in that change. It is ironic that the highest performing (at
least for large n) algorithm is the one which never gets used (as forward
iterators are nonexistent among the STL classes).

As currently written, the RAI algorithm accesses memory in long strides which
are likely to thrash the cache and cause the worst possible memory bottleneck
for large and coprime k. The bidirectional algorithm accesses memory in linear
fashion, but reads and writes each location twice and furthermore performs up
to twice as many swaps as necessary.

The forward iterator algorithm touches memory locations mostly only once and
always sequentially, locations which are touched repeatedly are spatially local
and hence cached, and it always performs the minimum number of swaps. Of the
current code, it gets the most fundamentals correct.

My impression is that any new code is inherently "untrustworthy." I haven't
benchmarked this suggestion, but I'm not really keen to check it in myself ;v)
. Feel free if you guys like…


-- 


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

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

[potswa at mac dot com]

------- Comment #33 from potswa at mac dot com  2009-10-17 20:45 -------
I returned the copyright forms today, so now the wheels are turning :vD .


-- 


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

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

[paolo dot carlini at oracle dot com]

------- Comment #34 from paolo dot carlini at oracle dot com  2009-10-22 18:18 -------
Excellent. As soon as you get the papers back, let us know...


-- 


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

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

[potswa at mac dot com]

------- Comment #35 from potswa at mac dot com  2009-10-30 02:47 -------
I got PDF's of the completed forms. What now?


-- 


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

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

[paolo dot carlini at oracle dot com]

------- Comment #36 from paolo dot carlini at oracle dot com  2009-10-30 02:51 -------
First, send it to me and Benjamin (bkoz@redhat.com), because we want to be 100%
sure everything is ok. Then, start thinking about the fix ;) Really,
please-please, keep it minimal, we don't want for now the super-dupe algorithm,
we want something using only swaps and not regressing performance-wise wrt what
we have now. And clear, easy to understand. Additional testcases are always
welcome.


-- 


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

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

[potswa at mac dot com]

------- Comment #38 from potswa at mac dot com  2009-10-30 03:56 -------
Created an attachment (id=18932)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=18932&action=view)
C++ snippet containing example function template

improved algorithm with forward/backward and std::copy cases.

Excerpted from my test file. Not suitable for real use: at a glance, it's
missing the random_access_iterator_tag argument. I'm not in the programming
groove at the moment and can't proofread, polish, etc.


-- 


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

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

[potswa at mac dot com]

------- Comment #37 from potswa at mac dot com  2009-10-30 03:55 -------
It seems like the goals are changing. Is this due to an approaching deadline?

The "super" algorithm is the product of making every case faster. Removing any
part of it (i.e. calls to std::copy) will regress performance of something. I
don't think it's too complicated. I'm attaching my code so you can actually see
it; I don't think I've shared it yet.

See my post from October 10. The forward iterator implementation is already a
stripped-down version of my algorithm. If we want simplicity, we can excise the
reverse and RAI implementations and not add anything. If you're serious about
this, I can benchmark that.

But, it shouldn't be such a surprise that performance and minimalism are
exclusive. The existing RAI algo also has forward and backward cases.


-- 


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

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

[paolo dot carlini at oracle dot com]

------- Comment #39 from paolo dot carlini at oracle dot com  2009-10-30 04:20 -------
The goals are not changing, I told you already that we want minimal changes wrt
to the current code. We want safe and incremental improvements.

In general all the contributions must be in form of patches vs current
mainline, thus make sure to take all the necessary steps, fetch mainline via
svn, apply the patch to your local tree, regression test the actual code
changes + the new testcases (as extensive as possible). Then, when you are
satisfied, post to the mailing list - Bugzilla is not for patches. Thanks for
now.


-- 


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

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

[paolo dot carlini at oracle dot com]

------- Comment #40 from paolo dot carlini at oracle dot com  2009-10-30 16:30 -------
The last attached patch is also not ok wrt move-only types, the special case
for __k == 1 that is (trivially replacing copy -> _GLIBCXX_MOVE3 doesn't fix
it). Before going ahead this way, I would also like to see benchmark results
for __k close to 1 != 1, make sure that 2 is already fine performance-wise.


-- 


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

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

[potswa at mac dot com]

------- 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

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

[potswa at mac dot com]

------- Comment #42 from potswa at mac dot com  2009-10-30 19:14 -------
Sorry, "once per ring" doesn't guarantee more than one pass for k=2 and n odd,
or the test case I presented. Better to say there are k passes, although
performance should improve for n/k on the order of cache associativity. Details
not really important.


-- 


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

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

[paolo dot carlini at oracle dot com]

------- Comment #43 from paolo dot carlini at oracle dot com  2009-10-30 19:39 -------
Ok, thanks a lot for the benchmarks, I'll try to come to the numbers as soon as
possible. However, I suggest posting to the mailing list, to make sure all the
interested people follow the discussion. Also, as I tried to say already,
please don't use std::copy, doesn't work, regtesting fails for move-only types.
That's important also to not make bad judgements when comparing different
algorithms, some of course simply are not viable for move-only types.


-- 


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

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

[potswa at mac dot com]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 885 bytes --]



------- Comment #44 from potswa at mac dot com  2009-11-03 03:56 -------
When does _GLIBCXX_MOVE3 do the wrong thing? I can see only doing the k=1
optimization #ifdef __GXX_EXPERIMENTAL_CXX0X__ — after all, copying is the
misbehavior this bug is filed against in the first place! But std::move seems
reasonably kosher to me. It's as good as the current RAI implementation using
_GLIBCXX_MOVE, although not as compliant as always using std::swap.

I apologize for always saying "copy" and not "move." I did include a disclaimer
on that code, that it's not really intended for use. Really I was just using
std::copy as an alias for memmove for performance testing. I haven't been able
to test any C++0x code at all because I'm having trouble building GCC on OS X.

Once I can test C++0x code, I'll post to the mailing list…


-- 


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

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

[paolo dot carlini at oracle dot com]

------- Comment #45 from paolo dot carlini at oracle dot com  2009-11-03 12:37 -------
Created an attachment (id=18954)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=18954&action=view)
Second draft, regtests fine

Ok, this version works, I fixed it to use _GLIBCXX_MOVE3 in one case and
_GLIBCXX_MOVE_BACKWARD3 in the other. My benchmarks are fine for simple types,
like ints, I think we should just go ahead, close the PR, and maybe think about
a more general solution optimized for k small, not just 1. But there is no
hurry, definitely. In my opinion, for 4.5.0 it's more urgent to audit the
library vs std::swap, ie, the stable_partition case, but really David, if we
come to that make sure to be all set about building / testing mainline, etc.


-- 


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

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

[paolo dot carlini at oracle dot com]

-- 

paolo dot carlini at oracle dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|paolo dot carlini at oracle |
                   |dot com                     |
         AssignedTo|unassigned at gcc dot gnu   |paolo dot carlini at oracle
                   |dot org                     |dot com
             Status|NEW                         |ASSIGNED


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

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

[paolo dot carlini at oracle dot com]

------- Comment #46 from paolo dot carlini at oracle dot com  2009-11-03 15:33 -------
Created an attachment (id=18956)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=18956&action=view)
Third draft, also regtests fine

This version restricts the copies to "simple" types (per your initial idea,
here scalar types, similarly to std::fill, but more general types could be also
added) and sets up some general infrastructure for optimizing k > 1 too. Maybe
you like it better, I don't think we want to go much more beyond this, for
4.5.0.


-- 


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

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

[potswa at mac dot com]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 1220 bytes --]



------- Comment #47 from potswa at mac dot com  2009-11-03 17:21 -------
What is the function of the helper class? I suppose the user could get improved
performance by specializing __is_scalar<MyClass>, but that could have
unintended consequences (resulting from the class not being scalar), not to
mention that the user is then modifying nonstandard internals. Furthermore, we
care more about whether it's POD than scalar.

Why not adapt or add a general interface to the test used by __copy_move* in
stl_algo.h?

      const bool __simple = (__is_pod(_ValueTypeI)
                             && __is_pointer<_II>::__value
                             && __is_pointer<_OI>::__value
                             && __are_same<_ValueTypeI, _ValueTypeO>::__value);

This seems to capture the requirements of memmove… although using copy/move
instead of swap should also be faster for large PODs in eg linked lists.

Anyway, __is_pod being reasonably sufficient for compliant behavior wrt
"complexity of a swap" being known, couldn't we just take patch_draft_2 and
substitute in

              if ( __is_pod(_ValueType) && __k == 1)

I favor this alternative.


-- 


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

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

[paolo dot carlini at oracle dot com]

------- Comment #48 from paolo dot carlini at oracle dot com  2009-11-03 17:32 -------
In general, the user certainly cannot specialize anything, this is internal
stuff, with __ in front. Also, I'm not in favor of general podness, because a
pod can be large, any size, see the example of fill, we want the temporary to
fit in a register or something similar. About k, we aren't doing so well for k
small, I think we should prepare for k > 1, but if you think it's impossible
any time soon, I'm also ok with simplifying things to k == 1 and __is_scalar.


-- 


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

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

[paolo dot carlini at oracle dot com]

------- Comment #49 from paolo dot carlini at oracle dot com  2009-11-03 17:36 -------
By the way, it's really silly to have code used only for copy-able types (like
scalars or pods) and having to use the *_MOVE* macros only for compilation
sake, in such cases it's normally much cleaner to have the thing inside a
template instantiated on demand.


-- 


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

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

[potswa at mac dot com]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 990 bytes --]



------- Comment #50 from potswa at mac dot com  2009-11-03 17:53 -------
The current RAI algo uses a temporary regardless of size or class. We could put
in a "&& sizeof(_ValueType) < __MAX_TEMP_SIZE" or something… but stack overflow
from a single temporary doesn't seem to have been concern in the past.

I don't see how being register-size in particular is important. If we were
swapping the temporary every time, we would want it to fit in a reasonable
number of registers so the compiler could optimize out read-after-writes. But
the __tmp here is only written and read once. The larger it is, the more
acceleration.

Proposed performance is very good with k small > 1, compared to current. Using
memmove is simply even faster. It's not clear such rotate operations are
popular enough to warrant a framework for optimization, though.

If we assure it's a non-move type then I also favor reverting out the
_GLIBCXX_MOVE[3]().


-- 


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

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

[paolo dot carlini at oracle dot com]

------- Comment #51 from paolo dot carlini at oracle dot com  2009-11-03 17:56 -------
Ok, agreed, let's use PODness and restrict ourselves to k == 1. In future,
we'll see...


-- 


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

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

[paolo at gcc dot gnu dot org]

------- Comment #52 from paolo at gcc dot gnu dot org  2009-11-03 18:16 -------
Subject: Bug 41351

Author: paolo
Date: Tue Nov  3 18:16:34 2009
New Revision: 153860

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=153860
Log:
2009-11-03  David Krauss  <potswa@mac.com>
            Paolo Carlini  <paolo.carlini@oracle.com>

        PR libstdc++/41351
        * include/bits/stl_algo.h (__rotate(_RandomAccessIterator,
        _RandomAccessIterator, _RandomAccessIterator,
        random_access_iterator_tag)): Rewrite to use only std::swap in
        general and std::copy/std::copy_backward when safe.

Modified:
    trunk/libstdc++-v3/ChangeLog
    trunk/libstdc++-v3/include/bits/stl_algo.h


-- 


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

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

[paolo dot carlini at oracle dot com]

------- Comment #53 from paolo dot carlini at oracle dot com  2009-11-03 18:18 -------
Fixed for 4.5.0.


-- 

paolo dot carlini at oracle dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED
   Target Milestone|---                         |4.5.0


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

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

[potswa at mac dot com]

------- Comment #54 from potswa at mac dot com  2009-11-03 20:43 -------
Created an attachment (id=18959)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=18959&action=view)
A couple benchmarks for 32-bit mode and updated fwd+copy

Yikes. Just a second: yesterday I played around with the forward iterator
algorithm a little more, and discovered that the reason it benchmarked slower
in rotate_speed.txt was that I had changed it to use std::iter_swap instead of
std::swap. I don't know if 4.5.0 has whatever compilation issue caused the
difference (I'm still testing in 4.2.1), but the new benchmarks show it as
being the same speed as my rewrite in -m64 mode.

Previous data showing my algo being faster resulted from testing in -m32 mode.
Attached are updated benchmarks showing that the only significant advantage to
my rewrite is a 12% speedup in -m32 mode for the general case.

The advantage to an improved forward/bidirectional iterator version is that it
should also help sequences in containers besides std::vector. Also it would be
lower impact as the only code added would be the special cases calling
std::copy, and the separate bidirectional and RAI algos would go away
completely.


-- 

potswa at mac dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
  Attachment #18934|0                           |1
        is obsolete|                            |


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

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

[paolo dot carlini at oracle dot com]

------- Comment #55 from paolo dot carlini at oracle dot com  2009-11-03 20:51 -------
David, this issue is closed, nobody will pay further attention to it. And, more
generally, we are not going to change the other overloads of rotate in the
4.5.0 timeframe, is too risky. Thus, please, as already recommended, please
concentrate on the std::swap issue in the other algorithms, and post any
further prospective discussions to libstdc++@. Also, again, as already
recommended, please make sure to do all the tests vs current mainline. A lot
has changes the last years in the compiler too, not just the library. Thanks.


-- 


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

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

[potswa at mac dot com]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 262 bytes --]



------- Comment #56 from potswa at mac dot com  2009-11-03 21:01 -------
Okay… I'm doing my best, anyway. I'll be holding off on other contributions
until I get a compiler capable of testing my code.


-- 


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

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

[paolo dot carlini at oracle dot com]

------- Comment #57 from paolo dot carlini at oracle dot com  2009-11-03 21:36 -------
To be clear: I'm 100% sure you are doing your (current) best to help, and I
appreciate that. But at same time, we have to follow here some definite
policies and methodologies in the work. By the way, don't hesitate to contact
me privately for help about building issues, etc: you mentioned OSX, I seem to
remember, you should not have any problem building and testing for that very
common target.


-- 


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