2007-09-11 Johannes Singler <singler@ira.uka.de>

	    Leonor Frias Moya  <lfrias@lsi.upc.edu>
            Felix Putze  <kontakt@felix-putze.de>
            Marius Elvert  <marius.elvert@ira.uka.de>
	    Felix Bondarenko  <f.bondarenko@web.de>
	    Robert Geisberger  <robert.geisberger@stud.uni-karlsruhe.de>
	    Robin Dapp  <r.dapp@freenet.de>
  	    Benjamin Kosnik  <bkoz@redhat.com>

	Add parallel mode.
	* include/parallel: New.
	* include/parallel/iterator.h: New.
	* include/parallel/multiway_merge.h: New.
	* include/parallel/parallel.h: New.
	* include/parallel/algorithm
	* include/parallel/find_selectors.h: New.
	* include/parallel/losertree.h: New.
	* include/parallel/list_partition.h: New.
	* include/parallel/types.h: New.
	* include/parallel/for_each.h: New.
	* include/parallel/multiseq_selection.h: New.
	* include/parallel/workstealing.h: New.
	* include/parallel/base.h: New.
	* include/parallel/par_loop.h: New.
	* include/parallel/numeric
	* include/parallel/features.h: New.
	* include/parallel/quicksort.h: New.
	* include/parallel/algorithmfwd.h: New.
	* include/parallel/equally_split.h: New.
	* include/parallel/compiletime_settings.h: New.
	* include/parallel/for_each_selectors.h: New.
	* include/parallel/basic_iterator.h: New.
	* include/parallel/omp_loop_static.h: New.
	* include/parallel/random_shuffle.h: New.
	* include/parallel/balanced_quicksort.h: New.
	* include/parallel/set_operations.h: New.
	* include/parallel/tags.h: New.
	* include/parallel/merge.h: New.
	* include/parallel/tree.h: New.
	* include/parallel/settings.h: New.
	* include/parallel/unique_copy.h: New.
	* include/parallel/multiway_mergesort.h: New.
	* include/parallel/numericfwd.h: New.
	* include/parallel/search.h: New.
	* include/parallel/partition.h: New.
	* include/parallel/compatibility.h: New.
	* include/parallel/algobase.h: New.
	* include/parallel/find.h: New.
	* include/parallel/partial_sum.h: New.
	* include/parallel/algo.h: New.
	* include/parallel/omp_loop.h: New.
	* include/parallel/queue.h: New.
	* include/parallel/timing.h: New.
	* include/parallel/sort.h: New.
	* include/parallel/checkers.h: New.
	* include/parallel/random_number.h: New.
	* include/bits/algorithmfwd.h: New.

	* acinclude.m4 (GLIBCXX_ENABLE_PARALLEL): New.
	* configure.host: Add atomic_flags.
	* configure.ac: Export ATOMIC_FLAGS, call GLIBCXX_ENABLE_PARALLEL.
	* src/Makefile.am: Add parallel_list rules.
	* include/Makefile.am: Add parallel files.
	* testsuite/Makefile.am (check-parallel): Add.
	(check-performance-parallel): Add.
	* config.h.in: Regenerate.
	* configure: Same.
	* libsupc++/Makefile.in: Same.
	* testsuite/Makefile.in: Same.
	* Makefile.in: Same.
	* libmath/Makefile.in: Same.
	* include/Makefile.in: Same.
	* src/Makefile.in: Same.
	* po/Makefile.in: Same.
	
	* config/abi/pre/gnu.ver: Export parallel list bits.

	* docs/html/parallel_mode.html: New.
	* docs/html/documentation.html: Add link.
	* docs/doxygen/user.cfg.in: Adjust for new files and directory.
	* docs/doxygen/doxygroups.cc: Adjust namespace markup.

	* include/debug/set.h: Adjust for _GLIBCXX_STD_D or _P change.
	* include/debug/bitset: Same.
	* include/debug/multiset.h: Same.
	* include/debug/vector: Same.
	* include/debug/map.h: Same.
	* include/debug/deque: Same.
	* include/debug/list: Same.
	* include/debug/debug.h: Same.
	* include/debug/multimap.h: Same.
	* include/std/algorithm: Same.
	* include/std/numeric: Same.
	* include/std/bitset: Same.
	* include/std/string: Same.
	* include/ext/hash_map: Same.
	* include/ext/hash_set: Same.
	* include/bits/stl_list.h: Same.
	* include/bits/stl_map.h: Same.
	* include/bits/stl_algobase.h: Same.
	* include/bits/stl_set.h: Same.
	* include/bits/stl_multimap.h: Same.
	* include/bits/stl_vector.h: Same.
	* include/bits/stl_numeric.h: Same.
	* include/bits/stl_deque.h: Same.
	* include/bits/stl_multiset.h: Same.
	* include/bits/char_traits.h: Same.
	* include/bits/stl_algo.h: Same.
	* include/bits/c++config: Same.
	* include/bits/vector.tcc: Same.
	* include/bits/deque.tcc: Same.
	* include/bits/stl_bvector.h: Same.
	* include/bits/list.tcc: Same.
	* src/list.cc: Same.
	* src/parallel_list.cc: New.

	* testsuite/lib/libstdc++.exp (check_v3_target_parallel_mode): New.
	* testsuite/lib/dg-options.exp (dg-require-parallel-mode): New.
	* scripts/testsuite_flags.in (--cxxparallelflags): New.
	* scripts/check_performance: Adjust.
	* testsuite/25_algorithms/headers/parallel_algorithm.cc: New.
	* testsuite/25_algorithms/headers/algorithm_parallel_mode.cc: New.
	* testsuite/25_algorithms/headers/parallel_algorithm_mixed1.cc: New.
	* testsuite/25_algorithms/headers/parallel_algorithm_mixed2.cc: New.
	* testsuite/26_numerics/headers/numeric/parallel_numeric.cc: New.
	* testsuite/26_numerics/headers/numeric/numeric_parallel_mode.cc: New.
	* testsuite/26_numerics/headers/numeric/
	parallel_numeric_mixed1.cc: New.
	* testsuite/26_numerics/headers/numeric/
	parallel_numeric_mixed2.cc: New.
	


git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@128395 138bc75d-0d04-0410-961f-82ee72b054a4

2 files changed, 461 insertions, 2 deletions

diff --git a/libstdc++-v3/docs/html/documentation.html b/libstdc++-v3/docs/html/documentation.html
index f211165cca7..2881caff57d 100644
--- a/libstdc++-v3/docs/html/documentation.html
+++ b/libstdc++-v3/docs/html/documentation.html
@@ -222,13 +222,15 @@
    </ul>
    </li>
 
-   <li>Extensions to the Standard Library
+   <li>Extensions
    <ul>
+     <li><a href="ext/howto.html#4">Compile-time checks</a></li>
+     <li><a href="debug_mode.html">Debug mode</a></li>
+     <li><a href="parallel_mode.html">Parallel mode</a></li>
      <li><a href="ext/pb_ds/index.html">Policy Based Data Structures</a></li>
      <li><a href="ext/howto.html#1">Ropes and trees and hashes, oh my!</a></li>
      <li><a href="ext/howto.html#2">Added members and types</a></li>
      <li><a href="ext/mt_allocator.html"><code>__mt_alloc</code> </a></li>
-     <li><a href="ext/howto.html#4">Compile-time checks</a></li>
      <li><a href="ext/howto.html#5">LWG Issues</a></li>
      <li><a href="ext/../18_support/howto.html#6">Demangling</a></li>
    </ul>
diff --git a/libstdc++-v3/docs/html/parallel_mode.html b/libstdc++-v3/docs/html/parallel_mode.html
new file mode 100644
index 00000000000..74db8ca3771
--- /dev/null
+++ b/libstdc++-v3/docs/html/parallel_mode.html
@@ -0,0 +1,457 @@
+<?xml version="1.0" encoding="ISO-8859-1"?>
+<!DOCTYPE html
+          PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
+          "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
+
+<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
+<head>
+   <meta name="AUTHOR" content="bkoz@gcc.gnu.org (Benjamin Kosnik)" />
+   <meta name="KEYWORDS" content="c++, libstdc++, gdb, g++, debug" />
+   <meta name="DESCRIPTION" content="The libstdc++ parallel mode." />
+   <meta name="GENERATOR" content="emacs and ten fingers" />
+   <title>The libstdc++ parallel mode</title>
+<link rel="StyleSheet" href="lib3styles.css" type="text/css" />
+<link rel="Copyright" href="17_intro/license.html" type="text/html" />
+</head>
+<body>
+
+<h1 class="centered"><a name="top">The libstdc++ parallel mode</a></h1>
+
+<p class="fineprint"><em>
+   The latest version of this document is always available at
+   <a href="http://gcc.gnu.org/onlinedocs/libstdc++/parallel_mode.html">
+   http://gcc.gnu.org/onlinedocs/libstdc++/parallel_mode.html</a>.
+</em></p>
+
+<p><em>
+   To the <a href="http://gcc.gnu.org/libstdc++/">libstdc++-v3 homepage</a>.
+</em></p>
+
+<!-- ####################################################### -->
+<hr />
+<p> The libstdc++ parallel mode is an experimental parallel
+implementation of many algorithms the C++ Standard Library.
+</p>
+
+<p>
+Several of the standard algorithms, for instance
+<code>std::search</code>, are made parallel using OpenMP
+annotations. These parallel mode constructs and can be invoked by
+explicit source declaration or by compiling existing sources with a
+specific compiler flag.
+</p>
+
+<h3 class="left"><a name="parallel">The libstdc++ parallel mode</a></h3>
+
+<p>The libstdc++ parallel mode performs parallization of algorithms,
+function objects, classes, and functions in the C++ Standard.</p>
+
+<h4 class="left">Using the libstdc++ parallel mode</h4>
+
+<p>To use the libstdc++ parallel mode, compile your application with
+  the compiler flag <code>-D_GLIBCXX_PARALLEL -fopenmp</code>. This
+  will link in <code>libgomp</code>, the GNU OpenMP <a
+  href="http://gcc.gnu.org/onlinedocs/libgomp">implementation</a>,
+  whose presence is mandatory. In addition, hardware capable of atomic
+  operations is de rigueur. Actually activating these atomic
+  operations may require explicit compiler flags on some targets
+  (like sparc and x86), such as <code>-march=i686</code>,
+  <code>-march=native</code> or <code>-mcpu=v9</code>.
+</p>
+
+<p>Note that the <code>_GLIBCXX_PARALLEL</code> define may change the
+  sizes and behavior of standard class templates such as
+  <code>std::search</code>, and therefore one can only link code
+  compiled with parallel mode and code compiled without parallel mode
+  if no instantiation of a container is passed between the two
+  translation units. Parallel mode functionality has distinct linkage,
+  and cannot be confused with normal mode symbols.</p>
+
+
+<p>The following library components in the include
+<code>&lt;numeric&gt;</code> are included in the parallel mode:</p>
+<ul>
+  <li><code>std::accumulate</code></li>
+  <li><code>std::adjacent_difference</code></li>
+  <li><code>std::inner_product</code></li>
+  <li><code>std::partial_sum</code></li>
+</ul>
+
+<p>The following library components in the include
+<code>&lt;algorithm&gt;</code> are included in the parallel mode:</p>
+<ul>
+  <li><code>std::adjacent_find</code></li>
+  <li><code>std::count</code></li>
+  <li><code>std::count_if</code></li>
+  <li><code>std::equal</code></li>
+  <li><code>std::find</code></li>
+  <li><code>std::find_if</code></li>
+  <li><code>std::find_first_of</code></li>
+  <li><code>std::for_each</code></li>
+  <li><code>std::generate</code></li>
+  <li><code>std::generate_n</code></li>
+  <li><code>std::lexicographical_compare</code></li>
+  <li><code>std::mismatch</code></li>
+  <li><code>std::search</code></li>
+  <li><code>std::search_n</code></li>
+  <li><code>std::transform</code></li>
+  <li><code>std::replace</code></li>
+  <li><code>std::replace_if</code></li>
+  <li><code>std::max_element</code></li>
+  <li><code>std::merge</code></li>
+  <li><code>std::min_element</code></li>
+  <li><code>std::nth_element</code></li>
+  <li><code>std::partial_sort</code></li>
+  <li><code>std::partition</code></li>
+  <li><code>std::random_shuffle</code></li>
+  <li><code>std::set_union</code></li>
+  <li><code>std::set_intersection</code></li>
+  <li><code>std::set_symmetric_difference</code></li>
+  <li><code>std::set_difference</code></li>
+  <li><code>std::sort</code></li>
+  <li><code>std::stable_sort</code></li>
+  <li><code>std::unique_copy</code></li>
+</ul>
+
+
+<h4 class="left">Using the parallel algorithms without parallel mode</h4>
+
+<p>When it is not feasible to recompile your entire application, or
+  only specific algorithms need to be parallel-aware, individual
+  parallel algorithms can be made available explicitly. These
+  parallel algorithms are functionally equivalent to the standard
+  drop-in algorithms used in parallel mode, but they are available in
+  a separate namespace as GNU extensions and may be used in programs
+  compiled with either release mode or with parallel mode. The
+  following table provides the names and headers of the parallel
+  algorithms:
+</p>
+
+
+<table title="Parallel algorithms" border="1">
+  <tr>
+    <th>Algorithm</th>
+    <th>Header</th>
+    <th>Parallel algorithm</th>
+    <th>Parallel header</th>
+  </tr>
+  <tr>
+    <td>std::accumulate</td>
+    <td>&lt;numeric&gt;</td>
+    <td>__gnu_parallel::accumulate</td>
+    <td>&lt;parallel/numeric&gt;</td>
+  </tr>
+  <tr>
+    <td>std::adjacent_difference</td>
+    <td>&lt;numeric&gt;</td>
+    <td>__gnu_parallel::adjacent_difference</td>
+    <td>&lt;parallel/numeric&gt;</td>
+  </tr>
+  <tr>
+    <td>std::inner_product</td>
+    <td>&lt;numeric&gt;</td>
+    <td>__gnu_parallel::inner_product</td>
+    <td>&lt;parallel/numeric&gt;</td>
+  </tr>
+  <tr>
+    <td>std::partial_sum</td>
+    <td>&lt;numeric&gt;</td>
+    <td>__gnu_parallel::partial_sum</td>
+    <td>&lt;parallel/numeric&gt;</td>
+  </tr>
+  <tr>
+    <td>std::adjacent_find</td>
+    <td>&lt;algorithm&gt;</td>
+    <td>__gnu_parallel::adjacent_find</td>
+    <td>&lt;parallel/algorithm&gt;</td>
+  </tr>
+
+  <tr>
+    <td>std::count</td>
+    <td>&lt;algorithm&gt;</td>
+    <td>__gnu_parallel::count</td>
+    <td>&lt;parallel/algorithm&gt;</td>
+  </tr>
+
+  <tr>
+    <td>std::count_if</td>
+    <td>&lt;algorithm&gt;</td>
+    <td>__gnu_parallel::count_if</td>
+    <td>&lt;parallel/algorithm&gt;</td>
+  </tr>
+
+  <tr>
+    <td>std::equal</td>
+    <td>&lt;algorithm&gt;</td>
+    <td>__gnu_parallel::equal</td>
+    <td>&lt;parallel/algorithm&gt;</td>
+  </tr>
+
+  <tr>
+    <td>std::find</td>
+    <td>&lt;algorithm&gt;</td>
+    <td>__gnu_parallel::find</td>
+    <td>&lt;parallel/algorithm&gt;</td>
+  </tr>
+
+  <tr>
+    <td>std::find_if</td>
+    <td>&lt;algorithm&gt;</td>
+    <td>__gnu_parallel::find_if</td>
+    <td>&lt;parallel/algorithm&gt;</td>
+  </tr>
+
+  <tr>
+    <td>std::find_first_of</td>
+    <td>&lt;algorithm&gt;</td>
+    <td>__gnu_parallel::find_first_of</td>
+    <td>&lt;parallel/algorithm&gt;</td>
+  </tr>
+
+  <tr>
+    <td>std::for_each</td>
+    <td>&lt;algorithm&gt;</td>
+    <td>__gnu_parallel::for_each</td>
+    <td>&lt;parallel/algorithm&gt;</td>
+  </tr>
+
+  <tr>
+    <td>std::generate</td>
+    <td>&lt;algorithm&gt;</td>
+    <td>__gnu_parallel::generate</td>
+    <td>&lt;parallel/algorithm&gt;</td>
+  </tr>
+
+  <tr>
+    <td>std::generate_n</td>
+    <td>&lt;algorithm&gt;</td>
+    <td>__gnu_parallel::generate_n</td>
+    <td>&lt;parallel/algorithm&gt;</td>
+  </tr>
+
+  <tr>
+    <td>std::lexicographical_compare</td>
+    <td>&lt;algorithm&gt;</td>
+    <td>__gnu_parallel::lexicographical_compare</td>
+    <td>&lt;parallel/algorithm&gt;</td>
+  </tr>
+
+  <tr>
+    <td>std::mismatch</td>
+    <td>&lt;algorithm&gt;</td>
+    <td>__gnu_parallel::mismatch</td>
+    <td>&lt;parallel/algorithm&gt;</td>
+  </tr>
+
+  <tr>
+    <td>std::search</td>
+    <td>&lt;algorithm&gt;</td>
+    <td>__gnu_parallel::search</td>
+    <td>&lt;parallel/algorithm&gt;</td>
+  </tr>
+
+  <tr>
+    <td>std::search_n</td>
+    <td>&lt;algorithm&gt;</td>
+    <td>__gnu_parallel::search_n</td>
+    <td>&lt;parallel/algorithm&gt;</td>
+  </tr>
+
+  <tr>
+    <td>std::transform</td>
+    <td>&lt;algorithm&gt;</td>
+    <td>__gnu_parallel::transform</td>
+    <td>&lt;parallel/algorithm&gt;</td>
+  </tr>
+
+  <tr>
+    <td>std::replace</td>
+    <td>&lt;algorithm&gt;</td>
+    <td>__gnu_parallel::replace</td>
+    <td>&lt;parallel/algorithm&gt;</td>
+  </tr>
+
+  <tr>
+    <td>std::replace_if</td>
+    <td>&lt;algorithm&gt;</td>
+    <td>__gnu_parallel::replace_if</td>
+    <td>&lt;parallel/algorithm&gt;</td>
+  </tr>
+
+  <tr>
+    <td>std::max_element</td>
+    <td>&lt;algorithm&gt;</td>
+    <td>__gnu_parallel::max_element</td>
+    <td>&lt;parallel/algorithm&gt;</td>
+  </tr>
+
+  <tr>
+    <td>std::merge</td>
+    <td>&lt;algorithm&gt;</td>
+    <td>__gnu_parallel::merge</td>
+    <td>&lt;parallel/algorithm&gt;</td>
+  </tr>
+
+  <tr>
+    <td>std::min_element</td>
+    <td>&lt;algorithm&gt;</td>
+    <td>__gnu_parallel::min_element</td>
+    <td>&lt;parallel/algorithm&gt;</td>
+  </tr>
+
+  <tr>
+    <td>std::nth_element</td>
+    <td>&lt;algorithm&gt;</td>
+    <td>__gnu_parallel::nth_element</td>
+    <td>&lt;parallel/algorithm&gt;</td>
+  </tr>
+
+  <tr>
+    <td>std::partial_sort</td>
+    <td>&lt;algorithm&gt;</td>
+    <td>__gnu_parallel::partial_sort</td>
+    <td>&lt;parallel/algorithm&gt;</td>
+  </tr>
+
+  <tr>
+    <td>std::partition</td>
+    <td>&lt;algorithm&gt;</td>
+    <td>__gnu_parallel::partition</td>
+    <td>&lt;parallel/algorithm&gt;</td>
+  </tr>
+
+  <tr>
+    <td>std::random_shuffle</td>
+    <td>&lt;algorithm&gt;</td>
+    <td>__gnu_parallel::random_shuffle</td>
+    <td>&lt;parallel/algorithm&gt;</td>
+  </tr>
+
+  <tr>
+    <td>std::set_union</td>
+    <td>&lt;algorithm&gt;</td>
+    <td>__gnu_parallel::set_union</td>
+    <td>&lt;parallel/algorithm&gt;</td>
+  </tr>
+
+  <tr>
+    <td>std::set_intersection</td>
+    <td>&lt;algorithm&gt;</td>
+    <td>__gnu_parallel::set_intersection</td>
+    <td>&lt;parallel/algorithm&gt;</td>
+  </tr>
+
+  <tr>
+    <td>std::set_symmetric_difference</td>
+    <td>&lt;algorithm&gt;</td>
+    <td>__gnu_parallel::set_symmetric_difference</td>
+    <td>&lt;parallel/algorithm&gt;</td>
+  </tr>
+
+  <tr>
+    <td>std::set_difference</td>
+    <td>&lt;algorithm&gt;</td>
+    <td>__gnu_parallel::set_difference</td>
+    <td>&lt;parallel/algorithm&gt;</td>
+  </tr>
+
+  <tr>
+    <td>std::sort</td>
+    <td>&lt;algorithm&gt;</td>
+    <td>__gnu_parallel::sort</td>
+    <td>&lt;parallel/algorithm&gt;</td>
+  </tr>
+
+  <tr>
+    <td>std::stable_sort</td>
+    <td>&lt;algorithm&gt;</td>
+    <td>__gnu_parallel::stable_sort</td>
+    <td>&lt;parallel/algorithm&gt;</td>
+  </tr>
+
+  <tr>
+    <td>std::unique_copy</td>
+    <td>&lt;algorithm&gt;</td>
+    <td>__gnu_parallel::unique_copy</td>
+    <td>&lt;parallel/algorithm&gt;</td>
+  </tr>
+
+</table>
+
+
+<h4 class="left">Parallel mode semantics</h4>
+<p> Something about exception safety, interaction with threads,
+etc. Goal is to have the usual constraints of the STL with respect to
+exception safety and threads, but add in support for parallel
+computing.</p>
+
+<p> Something about compile-time settings and configuration, ie using
+<code>__gnu_parallel::Settings</code>. XXX Up in the air.</p>
+
+<h4 class="left">Interface basics and relevant namespaces</h4>
+
+<p> Two namespaces contain the parallel mode:
+<code>std::__parallel</code> and <code>__gnu_parallel</code>. 
+</p>
+
+<p> One namespace contain versions of code that are explicitly sequential:
+<code>__gnu_serial</code>.
+</p>
+
+<p> Parallel implementations of the sequential standard components are
+defined in <code>namespace std::__parallel</code>. For instance,
+<code>std::transform</code> from &lt;algorithm&gt; has a parallel
+counterpart in <code>std::__parallel::transform</code> from
+&lt;parallel/algorithm&gt;. In addition, these parallel
+implementatations are injected into <code>namespace
+__gnu_parallel</code> with using declarations. 
+</p>
+
+<p> Support and infrastructure is in <code>namespace __gnu_parallel</code>.
+</p>
+
+<p> More information, and an organized index of types and functions
+related to the parallel mode on a per-namespace basis, can be found in
+the generated source documentation.
+</p>
+
+<h4 class="left">Testing</h4>
+
+<p> Both the normal conformance and regression tests and the
+supplemental performance tests work.</p>
+
+<p> To run the conformance and regression tests with the parallel mode
+active,</p>
+<code>make check-parallel</code>
+
+<p>The log and summary files for conformance testing are in the
+<code>testsuite/parallel</code> directory.</p>
+
+<p> To run the performance tests  with the parallel mode active, </p>
+<code>make check-performance-parallel</code>
+
+<p>The result file for performance testing are in the
+<code>testsuite</code> directory, in the file
+<code>libstdc++_performance.sum</code>. In addition, the policy-based
+containers have their own visualizations, which have additional
+software dependencies than the usual bare-boned text file, and can be
+generated by using the <code>make doc-performance</code> rule in the
+testsuite's Makefile.</p>
+
+<p>Return <a href="#top">to the top of the page</a> or
+   <a href="http://gcc.gnu.org/libstdc++/">to the libstdc++ homepage</a>.
+</p>
+
+
+<!-- ####################################################### -->
+
+<hr />
+<p class="fineprint"><em>
+See <a href="17_intro/license.html">license.html</a> for copying conditions.
+Comments and suggestions are welcome, and may be sent to
+<a href="mailto:libstdc++@gcc.gnu.org">the libstdc++ mailing list</a>.
+</em></p>
+
+
+</body>
+</html>