[Bug libstdc++/38875] New: parallel fill in the parallel version of libstdc++

[Bug libstdc++/38875] New: parallel fill in the parallel version of libstdc++

[wuerzner at gmail dot com]

Hi,

I recently started using the paralleled version of gcc's libstdc++. Now, I have
recognized that there is no parallel version of the fill algorithm (at least at
i486-linux-gnu).

The threshold variable __gnu_parallel::_Settings::fill_minimal_n
suggests that a parallel version of the fill algorithm is existing or at least
planned.
Among other things, fill is used for resizing vectors. But
std::vector.resize(n) is not executed in parallel. On first sight, a parallel
fill should not be hard to accomplish using openmp and would definitely be a
cool feature. But I am no stl expert and may be missing crucial
cross-dependencies.

Best regards,
Kay


-- 
           Summary: parallel fill in the parallel version of libstdc++
           Product: gcc
           Version: 4.4.0
            Status: UNCONFIRMED
          Severity: enhancement
          Priority: P3
         Component: libstdc++
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: wuerzner at gmail dot com
 GCC build triplet: i486-linux-gnu
  GCC host triplet: i486-linux-gnu
GCC target triplet: i486-linux-gnu


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

[Bug libstdc++/38875] parallel fill in the parallel version of libstdc++

[paolo dot carlini at oracle dot com]

------- Comment #1 from paolo dot carlini at oracle dot com  2009-01-16 15:46 -------
Thanks for your report. Johannes, can you have a look?


-- 


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

[Bug libstdc++/38875] parallel fill in the parallel version of libstdc++

[singler at gcc dot gnu dot org]

------- Comment #2 from singler at gcc dot gnu dot org  2009-01-16 15:51 -------
In some former (non-integrated) version of the code we had problems with fill
because it was so heavily used by other routines of the STL.  But this is not a
principal problem.  So I will try to integrate it as soon as possible.


-- 

singler at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |singler at gcc dot gnu dot
                   |dot org                     |org
             Status|UNCONFIRMED                 |ASSIGNED
     Ever Confirmed|0                           |1
   Last reconfirmed|0000-00-00 00:00:00         |2009-01-16 15:51:05
               date|                            |


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

[Bug libstdc++/38875] parallel fill and copy in the parallel version of libstdc++

[singler at gcc dot gnu dot org]

------- Comment #3 from singler at gcc dot gnu dot org  2009-03-23 11:00 -------
A parallelized std::copy was also suggested.


-- 

singler at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|parallel fill in the        |parallel fill and copy in
                   |parallel version of         |the parallel version of
                   |libstdc++                   |libstdc++


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

[Bug libstdc++/38875] parallel fill and copy in the parallel version of libstdc++

[wuerzner at gmail dot com]

------- Comment #4 from wuerzner at gmail dot com  2009-10-15 15:46 -------
Hi,

has there been any change on the std::fill policy, yet? If yes, in which
version did you integrate the parallel fill?

Many thanks,
Kay


-- 


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

[Bug libstdc++/38875] parallel fill and copy in the parallel version of libstdc++

[singler at gcc dot gnu dot org]

------- Comment #5 from singler at gcc dot gnu dot org  2009-10-20 07:37 -------
I'm investigating the problem.  In the meantime, you might want to "abuse"
std::for_each for this task.


-- 


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

[Bug libstdc++/38875] parallel fill and copy in the parallel version of libstdc++

[bkoz at gcc dot gnu dot org]

------- Comment #6 from bkoz at gcc dot gnu dot org  2009-11-05 02:15 -------
Created an attachment (id=18970)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=18970&action=view)
patch for parallel fill and fill_n


-- 


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

[Bug libstdc++/38875] parallel fill and copy in the parallel version of libstdc++

[bkoz at gcc dot gnu dot org]

------- Comment #7 from bkoz at gcc dot gnu dot org  2009-11-05 02:16 -------

Here's how parallel fill would look, based on Johannes patch.

-benjamin


-- 


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

[Bug libstdc++/38875] parallel fill and copy in the parallel version of libstdc++

[paolo dot carlini at oracle dot com]

------- Comment #8 from paolo dot carlini at oracle dot com  2009-11-05 02:33 -------
Cool. Now it would be nice to benchmark it a bit, somehow, a version of it with
the actual code not commented out, I mean ;)


-- 


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

[Bug libstdc++/38875] parallel fill and copy in the parallel version of libstdc++

[bkoz at gcc dot gnu dot org]

------- Comment #9 from bkoz at gcc dot gnu dot org  2009-11-05 02:52 -------

Yes, of course. Just providing the framework, since that was a bit tricky.

I should add all the steps here to the parallel mode docs to make this less
confusing for people trying to experiment.

best,
benjamin


-- 


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

[Bug libstdc++/38875] parallel fill and copy in the parallel version of libstdc++

[singler at gcc dot gnu dot org]

------- Comment #10 from singler at gcc dot gnu dot org  2009-11-19 15:32 -------
The new patch is functional.  However, for simple cases like setting integers,
I have no speedup (yet).


-- 


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

[Bug libstdc++/38875] parallel fill and copy in the parallel version of libstdc++

[singler at gcc dot gnu dot org]

------- Comment #11 from singler at gcc dot gnu dot org  2009-11-19 15:33 -------
Created an attachment (id=19053)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=19053&action=view)
Functional patch for parallel fill and fill_n.


-- 


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

[Bug libstdc++/38875] parallel fill and copy in the parallel version of libstdc++

[singler at gcc dot gnu dot org]

------- Comment #12 from singler at gcc dot gnu dot org  2009-11-19 15:35 -------
Remove old email address.


-- 

singler at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|singler at ira dot uka dot  |
                   |de                          |
             Status|ASSIGNED                    |WAITING


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

[Bug libstdc++/38875] parallel fill and copy in the parallel version of libstdc++

[wuerzner at gmail dot com]

------- Comment #13 from wuerzner at gmail dot com  2009-11-19 15:47 -------
If you have no speedup, do you recognize any loss of speed due to the
parallelization overhead (for small examples)?


-- 


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

[Bug libstdc++/38875] parallel fill and copy in the parallel version of libstdc++

[singler at gcc dot gnu dot org]

------- Comment #14 from singler at gcc dot gnu dot org  2009-11-20 09:53 -------
Created an attachment (id=19064)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=19064&action=view)
Functional patch for parallel fill and fill_n.


-- 

singler at gcc dot gnu dot org changed:

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


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

[Bug libstdc++/38875] parallel fill and copy in the parallel version of libstdc++

[singler at gcc dot gnu dot org]

------- Comment #15 from singler at gcc dot gnu dot org  2009-11-20 09:56 -------
There is slowdown, also for large inputs, for the most simple case, namely
filling constant integer values.  If assignment is more expensive, thing will
get better.  Please try with your application.


-- 

singler at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|WAITING                     |ASSIGNED
   Last reconfirmed|2009-01-16 15:51:05         |2009-11-20 09:56:12
               date|                            |


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

[Bug libstdc++/38875] parallel fill and copy in the parallel version of libstdc++

[paolo.carlini at oracle dot com]

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

--- Comment #16 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-04-06 22:25:44 UTC ---
Johannes, I lost a bit track of this enhancement PR: what do you think, now
that we are again in Stage 1 in mainline, are there chances we can resolve it
somehow? Is there something I can do to help?