[Bug libstdc++/47433] New: libstdc++ parallel mode calls std::swap explicitely

[Bug libstdc++/47433] New: libstdc++ parallel mode calls std::swap explicitely

[manuel.holtgrewe@fu-berlin.de]

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

           Summary: libstdc++ parallel mode calls std::swap explicitely
           Product: gcc
           Version: unknown
            Status: UNCONFIRMED
          Severity: critical
          Priority: P3
         Component: libstdc++
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: manuel.holtgrewe@fu-berlin.de


The parallel libstdc++ calls std::swap explicitely. To my knowledge, this
disables the user to specify his own, possibly more efficient swap routine.
This is especially severe in parallel sorting and partitioning.

 libstdc++-v3-parallel-trunk $ ack 'std::swap'
balanced_quicksort.h
135:    std::swap(*__pivot_pos, *(__end - 1));
147:      std::swap(*(__begin + __split_pos), *__pivot_pos);
287:            std::swap(*__pivot_pos, *(__end - 1));
306:            std::swap(*__split_pos1, *__pivot_pos);

losertree.h
237:        std::swap(_M_losers[__pos]._M_sup, __sup);
238:        std::swap(_M_losers[__pos]._M_source, __source);
239:        std::swap(_M_losers[__pos]._M_key, __key);
333:        std::swap(_M_losers[__pos]._M_sup, __sup);
334:        std::swap(_M_losers[__pos]._M_source, __source);
335:        std::swap(_M_losers[__pos]._M_key, __key);
464:        std::swap(_M_losers[__pos]._M_sup, __sup);
465:        std::swap(_M_losers[__pos]._M_source, __source);
466:        std::swap(_M_losers[__pos]._M_keyp, __keyp);
541:        std::swap(_M_losers[__pos]._M_sup, __sup);
542:        std::swap(_M_losers[__pos]._M_source, __source);
543:        std::swap(_M_losers[__pos]._M_keyp, __keyp);
697:        std::swap(_M_losers[__pos]._M_source, __source);
698:        std::swap(_M_losers[__pos]._M_key, __key);
788:        std::swap(_M_losers[__pos]._M_source, __source);
789:        std::swap(_M_losers[__pos]._M_key, __key);
937:        std::swap(_M_losers[__pos]._M_source, __source);
938:        std::swap(_M_losers[__pos]._M_keyp, __keyp);
1027:        std::swap(_M_losers[__pos]._M_source, __source);
1028:        std::swap(_M_losers[__pos]._M_keyp, __keyp);

partition.h
181:              std::swap(__begin[__thread_left],
241:          std::swap_ranges(__begin + __thread_left_border
264:          std::swap_ranges(__begin + __thread_right_border,
304:        std::swap(__begin[__final_left], __begin[__final_right]);
357:            std::swap(*__pivot_pos, *(__end - 1));
379:            std::swap(*__split_pos1, *__pivot_pos);

[Bug libstdc++/47433] libstdc++ parallel mode calls std::swap explicitely

[paolo.carlini at oracle dot com]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2011.01.24 12:12:09
                 CC|                            |paolo.carlini at oracle dot
                   |                            |com, singler at kit dot edu
     Ever Confirmed|0                           |1
           Severity|critical                    |normal

--- Comment #1 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-01-24 12:12:09 UTC ---
Johannes, do you have an opinion about this? Otherwise, I'll simply go ahead
and do the change.

[Bug libstdc++/47433] libstdc++ parallel mode calls std::swap explicitely

[paolo.carlini at oracle dot com]

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

--- Comment #2 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-01-24 12:52:30 UTC ---
Note: std::swap_ranges is fine, AFAICS.

[Bug libstdc++/47433] libstdc++ parallel mode calls std::swap explicitely

[manuel.holtgrewe@fu-berlin.de]

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

--- Comment #3 from Manuel Holtgrewe <manuel.holtgrewe@fu-berlin.de> 2011-01-24 12:56:16 UTC ---
I agree, that there are no obvious problems with std::swap_ranges.

Is anything specified in the standard in this direction?

[Bug libstdc++/47433] libstdc++ parallel mode calls std::swap explicitely

[paolo.carlini at oracle dot com]

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

--- Comment #4 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-01-24 13:10:43 UTC ---
I don't think it is. I can double check later.

Also, in losertree.h most uses involve built-in types (like bool or int) or
pointers, and those are also fine.

Beyond the issue discussed here, however, I'm not sure to understand the logic
behind the __delete_min_insert members taking _Tp by *value* instead of
constant ref. Johannes, are we sure we want those copies?

[Bug libstdc++/47433] libstdc++ parallel mode calls std::swap explicitely

[singler at kit dot edu]

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

--- Comment #5 from Johannes Singler <singler at kit dot edu> 2011-01-24 13:19:22 UTC ---
What are you proposing for a fix?  Omitting std::?  Using std::iter_swap where
appropriate, like stl_algo.h mostly does?  The latter would be more consistent.

Johannes

[Bug libstdc++/47433] libstdc++ parallel mode calls std::swap explicitely

[singler at kit dot edu]

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

--- Comment #6 from Johannes Singler <singler at kit dot edu> 2011-01-24 13:23:26 UTC ---
Taking __key as value type in (some variants of __delete_min_insert) makes
sense, since it is also used as a buffer for storing the current loser.  Having
a local variable that is initialized with the const ref would have the same
effect, would it not?

Johannes

[Bug libstdc++/47433] libstdc++ parallel mode calls std::swap explicitely

[paolo.carlini at oracle dot com]

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

--- Comment #7 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-01-24 13:28:28 UTC ---
For sure if we are swapping _Tps we have to omit the std::. In general, when we
are not swapping built-ins or pointers we have to omit the qualification or use
something else, like std::swap_ranges (which eventually calls unqualified swap
anyway). Please let me know which are your plans Johannes and let's resolve
this issue of 4.6.0, we don't have much time...

[Bug libstdc++/47433] libstdc++ parallel mode calls std::swap explicitely

[redi at gcc dot gnu.org]

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

--- Comment #8 from Jonathan Wakely <redi at gcc dot gnu.org> 2011-01-24 13:53:27 UTC ---
(In reply to comment #3)
> Is anything specified in the standard in this direction?

20.2.2 Swappable requirements               [swappable.requirements]

3  The context in which swap(t, u) and swap(u, t) are evaluated shall ensure
that a binary non-member function named “swap” is selected via overload
resolution (13.3) on a candidate set that includes:
— the two swap function templates defined in <utility> (20.3) and
— the lookup set produced by argument-dependent lookup (3.4.2).


The usual way to do that is:

  using std::swap;  // overloads in <utility> are candidates
  swap(t, u);       // overloads found by ADL are also candidates

[Bug libstdc++/47433] libstdc++ parallel mode calls std::swap explicitely

[singler at kit dot edu]

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

--- Comment #9 from Johannes Singler <singler at kit dot edu> 2011-01-24 13:55:33 UTC ---
I have made the attached minimal patch.  
Use std::iter_swap where possible, use swap for _Tp, and leave std::swap for
built-in types.  I will test and then submit the patch.

Johannes

[Bug libstdc++/47433] libstdc++ parallel mode calls std::swap explicitely

[singler at kit dot edu]

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

--- Comment #10 from Johannes Singler <singler at kit dot edu> 2011-01-24 13:57:16 UTC ---
Created attachment 23098
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=23098
Minimal patch avoid std::swap on template types.

[Bug libstdc++/47433] libstdc++ parallel mode calls std::swap explicitely

[paolo.carlini at oracle dot com]

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

--- Comment #11 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-01-24 14:11:05 UTC ---
Thanks Johannes. Jon is right (and indeed we are already using the pattern
elsewhere): when we are removing the std:: qualification from std::swap inside
a namespace != std, let's also add an using std::swap before. Maybe isn't
really necessary due to namespace association, but let's play safe. Patch
pre-approved.

[Bug libstdc++/47433] libstdc++ parallel mode calls std::swap explicitely

[singler at gcc dot gnu.org]

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

--- Comment #12 from singler at gcc dot gnu.org <singler at gcc dot gnu.org> 2011-01-24 17:07:40 UTC ---
Author: singler
Date: Mon Jan 24 17:07:35 2011
New Revision: 169171

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=169171
Log:
2011-01-24  Johannes Singler  <singler@kit.edu>

        PR libstdc++/47433
        * include/parallel/losertree.h
        (_LoserTree<>::__delete_min_insert):
        Do not qualify swap with std:: for value type, 
        but include a using directive instead.
        (_LoserTreeUnguarded<>::__delete_min_insert): Likewise.
        * include/parallel/balanced_quicksort.h (__qsb_divide):
        Use std::iter_swap instead of std::swap.
        (__qsb_local_sort_with_helping): Likewise.
        * include/parallel/partition.h (__parallel_partition): 
        Likewise. (__parallel_nth_element): Likewise.

Modified:
    trunk/libstdc++-v3/ChangeLog
    trunk/libstdc++-v3/include/parallel/balanced_quicksort.h
    trunk/libstdc++-v3/include/parallel/losertree.h
    trunk/libstdc++-v3/include/parallel/partition.h

[Bug libstdc++/47433] libstdc++ parallel mode calls std::swap explicitely

[singler at kit dot edu]

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

Johannes Singler <singler at kit dot edu> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|                            |FIXED

--- Comment #13 from Johannes Singler <singler at kit dot edu> 2011-01-24 17:10:05 UTC ---
Fixed in mainline.

[Bug libstdc++/47433] libstdc++ parallel mode calls std::swap explicitely

[singler at gcc dot gnu.org]

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

--- Comment #14 from singler at gcc dot gnu.org <singler at gcc dot gnu.org> 2011-02-11 10:11:46 UTC ---
Author: singler
Date: Fri Feb 11 10:11:41 2011
New Revision: 170047

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=170047
Log:
2011-02-11  Johannes Singler  <singler@kit.edu>

        PR libstdc++/47433
        * include/parallel/losertree.h
        (_LoserTreeUnguarded<>::__delete_min_insert):
        Add missing "using std::swap;", as for other variants.

Modified:
    trunk/libstdc++-v3/ChangeLog
    trunk/libstdc++-v3/include/parallel/losertree.h

[Bug libstdc++/47433] libstdc++ parallel mode calls std::swap explicitely

[singler at gcc dot gnu.org]

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

--- Comment #15 from singler at gcc dot gnu.org <singler at gcc dot gnu.org> 2011-02-25 14:04:48 UTC ---
Author: singler
Date: Fri Feb 25 14:04:40 2011
New Revision: 170494

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=170494
Log:
2011-02-25  Johannes Singler  <singler@kit.edu>

        PR libstdc++/47433
        * include/parallel/losertree.h
        (_LoserTree<>::__delete_min_insert):
        Do not qualify swap with std:: for value type,
        but include a using directive instead.
        (_LoserTreeUnguarded<>::__delete_min_insert): Likewise.
        * include/parallel/balanced_quicksort.h (__qsb_divide):
        Use std::iter_swap instead of std::swap.
        (__qsb_local_sort_with_helping): Likewise.
        * include/parallel/partition.h (__parallel_partition):
        Likewise. (__parallel_nth_element): Likewise.

Modified:
    branches/gcc-4_5-branch/libstdc++-v3/ChangeLog
    branches/gcc-4_5-branch/libstdc++-v3/include/parallel/balanced_quicksort.h
    branches/gcc-4_5-branch/libstdc++-v3/include/parallel/losertree.h
    branches/gcc-4_5-branch/libstdc++-v3/include/parallel/partition.h