[Bug libstdc++/48559] New: parallel-mode vs C++0x

[Bug libstdc++/48559] New: parallel-mode vs C++0x

[paolo.carlini at oracle dot com]

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

           Summary: parallel-mode vs C++0x
           Product: gcc
           Version: 4.7.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: paolo.carlini@oracle.com


A number of parallel algorithms assumes CopyConstructible and/or
CopyAssignable, whereas in the new standard only MoveConstructible and/or
MoveAssignable are required (eminent case, std::sort). Indeed, at the moment we
have to run the following in normal-mode:

random_shuffle/moveable.cc:24:#undef _GLIBCXX_PARALLEL
nth_element/moveable.cc:27:#undef _GLIBCXX_PARALLEL
partial_sort/check_compare_by_value.cc:26:#undef _GLIBCXX_PARALLEL
partial_sort/moveable.cc:27:#undef _GLIBCXX_PARALLEL
partition/moveable.cc:27:#undef _GLIBCXX_PARALLEL
stable_sort/moveable2.cc:26:#undef _GLIBCXX_PARALLEL
stable_sort/check_compare_by_value.cc:26:#undef _GLIBCXX_PARALLEL
stable_sort/moveable.cc:26:#undef _GLIBCXX_PARALLEL
sort/check_compare_by_value.cc:26:#undef _GLIBCXX_PARALLEL
sort/moveable.cc:27:#undef _GLIBCXX_PARALLEL
for_each/1.cc:24:#undef _GLIBCXX_PARALLEL

(see also next_permutation/moveable.cc and prev_permutation/moveable.cc about
std::lexicographical_compare)

We have to fix this.

An option would be conditionalizing the parallel versions on
std::is_copy_constructible and/or std::is_copy_assignable being true. But those
traits are not available yet. We could conservatively use for now the trivial
version, which maybe is too conservative, however.

Much more elegant would be tweaking the algorithms themselves to not use
copies, just moves, as the serial versions do. I have no idea whether this is
feasible, for at least *some* of the algorithms...

[Bug libstdc++/48559] parallel-mode vs C++0x

[paolo.carlini at oracle dot com]

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

Paolo Carlini <paolo.carlini at oracle dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |singler at kit dot edu

--- Comment #1 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-04-11 18:30:42 UTC ---
Johannes, what do you think?

[Bug libstdc++/48559] parallel-mode vs C++0x

[singler at gcc dot gnu.org]

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

singler@gcc.gnu.org <singler at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2011.04.12 19:02:06
                 CC|                            |singler at gcc dot gnu.org
     Ever Confirmed|0                           |1

--- Comment #2 from singler at gcc dot gnu.org <singler at gcc dot gnu.org> 2011-04-12 19:02:06 UTC ---
We should try to tweak the algorithms to use just moves.  Since memory
bandwidth often limits parallel performance, it could even be particularly
efficient.

On the other hand, we sometimes need references to elements of the
random-access input sequence(s).  We could always use an iterator, but that
might be inefficient.  And we cannot take the lvalue reference or the address
of a dereferenced random access iterator, can we?  (Although this is
unfortunately done so far in multiseq_selection.h.)  Can we always take the
rvalue reference of a dereferenced random access iterator?

random_shuffle and partition will be the easiest cases, so we should start
there.

[Bug libstdc++/48559] parallel-mode vs C++0x

[redi at gcc dot gnu.org]

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

--- Comment #3 from Jonathan Wakely <redi at gcc dot gnu.org> 2011-04-12 19:20:29 UTC ---
(In reply to comment #2)
> On the other hand, we sometimes need references to elements of the
> random-access input sequence(s).  We could always use an iterator, but that
> might be inefficient.  And we cannot take the lvalue reference or the address
> of a dereferenced random access iterator, can we?

Yes you can for most iterators (not for move_iterator, but that's unusual)

>  (Although this is
> unfortunately done so far in multiseq_selection.h.)  Can we always take the
> rvalue reference of a dereferenced random access iterator?

No (you can for move_iterator).

For most iterators (especially random access iterators including pointers)
iterator_traits<It>::reference will be an lvalue reference.

[Bug libstdc++/48559] parallel-mode vs C++0x

[paolo.carlini at oracle dot com]

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

--- Comment #4 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-04-13 02:02:32 UTC ---
Johannes, all - 

if everything goes well, in a couple of days we'll have a very good
std::is_constructible in, contributed by Daniel, thus, it will be trivial,
std::is_copy_constructible. Do you know how far we can go in terms of
dispatching for parallel-mode with that trait alone? std::is_copy_assignable
will take a little more time, but if we aren't doing much assignments anyway in
the parallel code (or it can be quickly tweaked to do only copy constructions
instead of both copy assignments and copy constructions where it should do only
moves) then we can have a nice intermediate step, before calmly trying to
convert each parallel algorithm to not use moves at all.

Or we can just take the risk and surrogate for now std::is_copy_constructible
&& std::is_copy_assignable both being true with only the former being true for
dispatching, still better than the current situation, more C++0x conforming
code would compile in parallel-mode (and just fall-back to serial if the type
isn't CopyConstructible).

[Bug libstdc++/48559] parallel-mode vs C++0x

[paolo.carlini at oracle dot com]

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

--- Comment #5 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-04-17 23:17:00 UTC ---
Actually, the parallel-mode std::partition seems already ok, in any case I just
enabled its moveable.cc to actually run in parallel-mode.

[Bug libstdc++/48559] parallel-mode vs C++0x

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=48559

--- Comment #6 from Jonathan Wakely <redi at gcc dot gnu.org> ---
I'm inclined to close this as WONTFIX.

The new C++17 algorithms use modern C++ and are standardised. Rather than
maintain our non-standard extension, I'd prefer to deprecate our parallel mode
and tell people to use C++17 instead.