re PR libstdc++/33893 ([parallel mode] Algorithms rely on omp_set_dynamic(false))

[thirdparty/gcc.git] / libstdc++-v3 / include / parallel / quicksort.h

diff --git a/libstdc++-v3/include/parallel/quicksort.h b/libstdc++-v3/include/parallel/quicksort.h
index a9ceab4a5555b13bb2ce8d2c56a6ea7812d29a98..4eb357818cfb71f467dcb60a690a102a9d35ba4f 100644 (file)
--- a/libstdc++-v3/include/parallel/quicksort.h
+++ b/libstdc++-v3/include/parallel/quicksort.h
@@ -53,11 +53,17 @@ namespace __gnu_parallel
    *  this part.
    */
   template<typename RandomAccessIterator, typename Comparator>
-  inline typename std::iterator_traits<RandomAccessIterator>::difference_type
-  parallel_sort_qs_divide(RandomAccessIterator begin, RandomAccessIterator end,
-                         Comparator comp,
-                         typename std::iterator_traits<RandomAccessIterator>::difference_type pivot_rank,
-                         typename std::iterator_traits<RandomAccessIterator>::difference_type num_samples, thread_index_t num_threads)
+  inline
+  typename std::iterator_traits<RandomAccessIterator>::difference_type
+  parallel_sort_qs_divide(
+      RandomAccessIterator begin,
+      RandomAccessIterator end,
+      Comparator comp,
+      typename std::iterator_traits<RandomAccessIterator>::difference_type
+          pivot_rank,
+      typename std::iterator_traits<RandomAccessIterator>::difference_type
+          num_samples,
+      thread_index_t num_threads)
   {
     typedef std::iterator_traits<RandomAccessIterator> traits_type;
     typedef typename traits_type::value_type value_type;
@@ -65,20 +71,24 @@ namespace __gnu_parallel
 
     difference_type n = end - begin;
     num_samples = std::min(num_samples, n);
-    value_type* samples = static_cast<value_type*>(__builtin_alloca(sizeof(value_type) * num_samples));
+
+    // Allocate uninitialized, to avoid default constructor.
+    value_type* samples = static_cast<value_type*>(
+        operator new(num_samples * sizeof(value_type)));
 
     for (difference_type s = 0; s < num_samples; s++)
       {
-       const unsigned long long index = static_cast<unsigned long long>(s) 
-                                        * n / num_samples;
-       samples[s] = begin[index];
+        const unsigned long long index = static_cast<unsigned long long>(s)
+                        * n / num_samples;
+        new(samples + s) value_type(begin[index]);
       }
 
     __gnu_sequential::sort(samples, samples + num_samples, comp);
 
     value_type& pivot = samples[pivot_rank * num_samples / n];
 
-    __gnu_parallel::binder2nd<Comparator, value_type, value_type, bool> pred(comp, pivot);
+    __gnu_parallel::binder2nd<Comparator, value_type, value_type, bool>
+        pred(comp, pivot);
     difference_type split = parallel_partition(begin, end, pred, num_threads);
 
     return split;
@@ -93,7 +103,10 @@ namespace __gnu_parallel
    */
   template<typename RandomAccessIterator, typename Comparator>
   inline void
-  parallel_sort_qs_conquer(RandomAccessIterator begin, RandomAccessIterator end, Comparator comp, int num_threads)
+  parallel_sort_qs_conquer(RandomAccessIterator begin,
+                           RandomAccessIterator end,
+                           Comparator comp,
+                           thread_index_t num_threads)
   {
     typedef std::iterator_traits<RandomAccessIterator> traits_type;
     typedef typename traits_type::value_type value_type;
@@ -101,8 +114,8 @@ namespace __gnu_parallel
 
     if (num_threads <= 1)
       {
-       __gnu_sequential::sort(begin, end, comp);
-       return;
+        __gnu_sequential::sort(begin, end, comp);
+        return;
       }
 
     difference_type n = end - begin, pivot_rank;
@@ -110,24 +123,27 @@ namespace __gnu_parallel
     if (n <= 1)
       return;
 
-    thread_index_t num_processors_left;
+    thread_index_t num_threads_left;
 
     if ((num_threads % 2) == 1)
-      num_processors_left = num_threads / 2 + 1;
+      num_threads_left = num_threads / 2 + 1;
     else
-      num_processors_left = num_threads / 2;
+      num_threads_left = num_threads / 2;
 
-    pivot_rank = n * num_processors_left / num_threads;
+    pivot_rank = n * num_threads_left / num_threads;
 
-    difference_type split = parallel_sort_qs_divide(begin, end, comp, pivot_rank,
-Settings::sort_qs_num_samples_preset, num_threads);
+    difference_type split = parallel_sort_qs_divide(
+        begin, end, comp, pivot_rank,
+        Settings::sort_qs_num_samples_preset, num_threads);
 
 #pragma omp parallel sections
     {
 #pragma omp section
-      parallel_sort_qs_conquer(begin, begin + split, comp, num_processors_left);
+      parallel_sort_qs_conquer(begin, begin + split,
+                               comp, num_threads_left);
 #pragma omp section
-      parallel_sort_qs_conquer(begin + split, end, comp, num_threads - num_processors_left);
+      parallel_sort_qs_conquer(begin + split, end,
+                               comp, num_threads - num_threads_left);
     }
   }
 
@@ -143,9 +159,12 @@ Settings::sort_qs_num_samples_preset, num_threads);
    */
   template<typename RandomAccessIterator, typename Comparator>
   inline void
-  parallel_sort_qs(RandomAccessIterator begin, RandomAccessIterator end,
-                  Comparator comp,
-                  typename std::iterator_traits<RandomAccessIterator>::difference_type n, int num_threads)
+  parallel_sort_qs(
+      RandomAccessIterator begin,
+      RandomAccessIterator end,
+      Comparator comp,
+      typename std::iterator_traits<RandomAccessIterator>::difference_type n,
+      int num_threads)
   {
     _GLIBCXX_CALL(n)
 
@@ -165,12 +184,9 @@ Settings::sort_qs_num_samples_preset, num_threads);
     // Hard to avoid.
     omp_set_num_threads(num_threads);
 
-    bool old_nested = (omp_get_nested() != 0);
-    omp_set_nested(true);
     parallel_sort_qs_conquer(begin, begin + n, comp, num_threads);
-    omp_set_nested(old_nested);
   }
 
-}      //namespace __gnu_parallel
+} //namespace __gnu_parallel
 
 #endif