[Bug libstdc++/33489] New: parallel v3: sort assumes that the type of the objects to be sorted have a default constructor

[Bug libstdc++/33489] New: parallel v3: sort assumes that the type of the objects to be sorted have a default constructor

[bangerth at dealii dot org]

This program compiles in sequential mode but not in debug mode:
---------------------
#include <algorithm>
struct X { X(int); };
bool operator< (const X&, const X&);

void f () {
  X *p, *q;
  std::sort (p, q);
}
-------------------
The reason is that X does not have a default constructor. I don't think the 
standard prescribes that it should need one (as a matter of fact, the 
standard only talks in terms of iterators as arguments, not of the types they 
point to -- if they're pointers at all). However, the parallel mode requires 
a default constructor.

For reference, here's the error message:

4.3.0/parallel/multiway_mergesort.h: In function 'void
__gnu_parallel::parallel_sort_mwms(RandomAccessIterator, RandomAccessIterator,
Comparator, typename std::iterator_traits<_Iterator>::difference_type, int,
bool) [with RandomAccessIterator = X*, Comparator = std::less<X>]':
4.3.0/parallel/sort.h:88:   instantiated from 'void
__gnu_parallel::parallel_sort(RandomAccessIterator, RandomAccessIterator,
Comparator, bool) [with RandomAccessIterator = X*, Comparator = std::less<X>]'
4.3.0/parallel/algo.h:1300:   instantiated from 'void
std::__parallel::sort(_RAIter, _RAIter, _Compare) [with _RAIter = X*, _Compare
= std::less<X>]'
4.3.0/parallel/algo.h:1287:   instantiated from 'void
std::__parallel::sort(_RAIter, _RAIter) [with _RAIter = X*]'
x.cc:7:   instantiated from here
4.3.0/parallel/multiway_mergesort.h:369: error: no matching function for call
to 'X::X()'
x.cc:2: note: candidates are: X::X(int)
x.cc:2: note:                 X::X(const X&)
4.3.0/parallel/multiseq_selection.h: In function 'void
__gnu_parallel::multiseq_partition(RanSeqs, RanSeqs, RankType, RankIterator,
Comparator) [with RanSeqs = __gnu_cxx::__normal_iterator<std::pair<X*, X*>*,
std::__cxx1998::vector<std::pair<X*, X*>, std::allocator<std::pair<X*, X*> > >
>, RankType = int, RankIterator = __gnu_cxx::__normal_iterator<X**,
std::__cxx1998::vector<X*, std::allocator<X*> > >, Comparator = std::less<X>]':
4.3.0/parallel/multiway_mergesort.h:252:   instantiated from 'void
__gnu_parallel::parallel_sort_mwms_pu(__gnu_parallel::PMWMSSorterPU<RandomAccessIterator>*,
Comparator&) [with RandomAccessIterator = X*, Comparator = std::less<X>]'
4.3.0/parallel/multiway_mergesort.h:394:   instantiated from 'void
__gnu_parallel::parallel_sort_mwms(RandomAccessIterator, RandomAccessIterator,
Comparator, typename std::iterator_traits<_Iterator>::difference_type, int,
bool) [with RandomAccessIterator = X*, Comparator = std::less<X>]'
4.3.0/parallel/sort.h:88:   instantiated from 'void
__gnu_parallel::parallel_sort(RandomAccessIterator, RandomAccessIterator,
Comparator, bool) [with RandomAccessIterator = X*, Comparator = std::less<X>]'
4.3.0/parallel/algo.h:1300:   instantiated from 'void
std::__parallel::sort(_RAIter, _RAIter, _Compare) [with _RAIter = X*, _Compare
= std::less<X>]'
4.3.0/parallel/algo.h:1287:   instantiated from 'void
std::__parallel::sort(_RAIter, _RAIter) [with _RAIter = X*]'
x.cc:7:   instantiated from here
4.3.0/parallel/multiseq_selection.h:305: error: no matching function for call
to 'X::X()'
x.cc:2: note: candidates are: X::X(int)
x.cc:2: note:                 X::X(const X&)
4.3.0/parallel/multiseq_selection.h:305: error: no matching function for call
to 'X::X()'
x.cc:2: note: candidates are: X::X(int)
x.cc:2: note:                 X::X(const X&)

This sort of thing is repeated for several more pages.

W.


-- 
           Summary: parallel v3: sort assumes that the type of the objects
                    to be sorted have a default constructor
           Product: gcc
           Version: 4.3.0
            Status: UNCONFIRMED
          Keywords: rejects-valid
          Severity: normal
          Priority: P3
         Component: libstdc++
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: bangerth at dealii dot org


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

[Bug libstdc++/33489] parallel v3: sort assumes that the type of the objects to be sorted have a default constructor

[bkoz at gcc dot gnu dot org]

------- Comment #1 from bkoz at gcc dot gnu dot org  2007-09-19 17:07 -------

Wolfgang means "parallel mode" instead of debug mode.

This is confirmed.


-- 

bkoz at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|0                           |1
   Last reconfirmed|0000-00-00 00:00:00         |2007-09-19 17:07:42
               date|                            |


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

[Bug libstdc++/33489] parallel v3: sort assumes that the type of the objects to be sorted have a default constructor

[bkoz at gcc dot gnu dot org]

------- Comment #2 from bkoz at gcc dot gnu dot org  2007-09-21 03:24 -------

I'm working on a patch to test instantiability for 25/26 bits on types that are
not defaultconstructible.


-- 


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

[Bug libstdc++/33489] parallel v3: sort assumes that the type of the objects to be sorted have a default constructor

[bkoz at gcc dot gnu dot org]

------- Comment #3 from bkoz at gcc dot gnu dot org  2007-09-26 17:27 -------

OK. Now there are tests for all of algorithms for defaultconstructable. As per
20.1, this is not required for template arguments unless the standard
explicitly notes it.

http://gcc.gnu.org/ml/gcc-patches/2007-09/msg01921.html

>From this, we can see that the following parallel algorithms have issues with
this:

merge
nth_element
partial_sort
random_shuffle
set_difference
set_intersection
set_symmetric_difference
set_union
sort
stable_sort
partial_sum

-benjamin


-- 


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

[Bug libstdc++/33489] parallel v3: sort assumes that the type of the objects to be sorted have a default constructor

[bangerth at dealii dot org]

------- Comment #4 from bangerth at dealii dot org  2007-09-26 19:41 -------
(In reply to comment #3)
> OK. Now there are tests for all of algorithms for defaultconstructable. As per
> 20.1, this is not required for template arguments unless the standard
> explicitly notes it.

Yay, thanks for tackling this area!
W.


-- 


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

[Bug libstdc++/33489] parallel v3: not default constructable issues

[bkoz at gcc dot gnu dot org]

------- Comment #5 from bkoz at gcc dot gnu dot org  2007-10-06 15:31 -------
Created an attachment (id=14310)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=14310&action=view)
partial fix


-- 


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

[Bug libstdc++/33489] parallel v3: not default constructible issues

[bkoz at gcc dot gnu dot org]

------- Comment #6 from bkoz at gcc dot gnu dot org  2007-10-08 15:58 -------
Subject: Bug 33489

Author: bkoz
Date: Mon Oct  8 15:58:06 2007
New Revision: 129132

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=129132
Log:
2007-10-08  Benjamin Kosnik  <bkoz@redhat.com>

        PR libstdc++/33489      
        * include/parallel/multiseq_selection.h: Remove default constructed
        value_type.
        * include/parallel/partition.h: 
        * include/parallel/partial_sum.h: Format.


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


-- 


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

[Bug libstdc++/33489] parallel v3: not default constructible issues

[bkoz at gcc dot gnu dot org]

------- Comment #7 from bkoz at gcc dot gnu dot org  2007-10-09 20:48 -------
Subject: Bug 33489

Author: bkoz
Date: Tue Oct  9 20:48:38 2007
New Revision: 129179

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=129179
Log:
2007-10-09  Benjamin Kosnik  <bkoz@montsouris.artheist.org>

        PR libstdc++/33489 continued.           
        * include/parallel/features.h (_GLIBCXX_LOSER_TREE): Set to zero.
        (_GLIBCXX_LOSER_TREE_POINTER): Set to one.
        (_GLIBCXX_LOSER_TREE_UNGUARDED): Set to zero.
        (_GLIBCXX_LOSER_TREE_POINTER_UNGUARDED): Set to one.
        * include/parallel/multiway_merge.h (parallel_multiway_merge):
        Change array of value_type to array of value_type pointers.
        (multiway_merge_bubble): Same.
        (multiway_merge_loser_tree): Same.
        * include/parallel/merge.h (merge_advance_movc): Change to avoid
        default construction.
        * include/parallel/multiseq_selection.h (multiseq_partition):
        Replace value_type, bool pair with value_type*, null-initialized.
        * include/parallel/multiway_mergesort.h (parallel_sort_mwms):
        Don't use array form of operator new for value_types.
        (parallel_sort_mwms_pu): Same.
        * include/parallel/quicksort.h (parallel_sort_qs_divide): Don't
        use array form to construct pointer to value_type on stack,
        instead use __builtin_alloca.   
        * include/parallel/random_shuffle.h (sequential_random_shuffle): Same,
        but use operator new.
        (parallel_random_shuffle_drs_pu): Same.
        * include/parallel/partial_sum.h ( parallel_partial_sum_linear): Same.

        * include/parallel/losertree.h: Format.
        * include/parallel/settings.h: Format.

        * include/parallel/multiway_merge.h: Move traits to....
        * include/parallel/losertree.h: ... here.       


Modified:
    trunk/libstdc++-v3/ChangeLog
    trunk/libstdc++-v3/include/parallel/features.h
    trunk/libstdc++-v3/include/parallel/losertree.h
    trunk/libstdc++-v3/include/parallel/merge.h
    trunk/libstdc++-v3/include/parallel/multiseq_selection.h
    trunk/libstdc++-v3/include/parallel/multiway_merge.h
    trunk/libstdc++-v3/include/parallel/multiway_mergesort.h
    trunk/libstdc++-v3/include/parallel/partial_sum.h
    trunk/libstdc++-v3/include/parallel/quicksort.h
    trunk/libstdc++-v3/include/parallel/random_shuffle.h
    trunk/libstdc++-v3/include/parallel/settings.h


-- 


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

[Bug libstdc++/33489] parallel v3: not default constructible issues

[bkoz at gcc dot gnu dot org]

------- Comment #8 from bkoz at gcc dot gnu dot org  2007-10-09 20:50 -------

This should be all fixed now.

Wolfgang, please verify and fix if true.

-benjamin


-- 


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

[Bug libstdc++/33489] parallel v3: not default constructible issues

[bangerth at dealii dot org]

------- Comment #9 from bangerth at dealii dot org  2007-10-09 20:51 -------
(In reply to comment #8)
> Wolfgang, please verify and fix if true.

Already under way :-)

W.


-- 


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

[Bug libstdc++/33489] parallel v3: not default constructible issues

[bkoz at gcc dot gnu dot org]

------- Comment #10 from bkoz at gcc dot gnu dot org  2007-10-09 21:40 -------
Mine.


-- 

bkoz at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |bkoz at gcc dot gnu dot org
                   |dot org                     |
             Status|NEW                         |ASSIGNED
   Last reconfirmed|2007-09-19 17:07:42         |2007-10-09 21:40:25
               date|                            |


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

[Bug libstdc++/33489] parallel v3: not default constructible issues

[bkoz at gcc dot gnu dot org]

------- Comment #11 from bkoz at gcc dot gnu dot org  2007-10-18 16:06 -------

Wolfgang, I'm going to close this as fixed, ok? We are now checking
systematically for this issue as part of the 25_algo conformance testing. If
you find any more of these, please re-open. 

best,
benjamin


-- 

bkoz at gcc dot gnu dot org changed:

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


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

[Bug libstdc++/33489] parallel v3: not default constructible issues

[bangerth at dealii dot org]

------- Comment #12 from bangerth at dealii dot org  2007-10-18 18:46 -------
Yes, sorry. I meant to report of course that I believe that it works now.
Thanks for your work!
W.


-- 


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