This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[PATCH][libstdc++-v3 parallel mode] Speed up random_shuffle


This patch speeds up parallel random_shuffle for 1 thread
forced-parallel execution, and for small inputs in general.

timings before
10000    0.000635    0.000648    0.000645    0.000647    0.000647
0.000646    0.000646    0.000646    0.000647
1000000    0.086243    0.082482    0.030204    0.021635    0.015495
0.014524    0.017958    0.010846    0.008236

timings after
10000    0.000635    *0.000395*    *0.000300*    *0.000283*
*0.000170*    *0.000168*    *0.000167*    *0.000166*    *0.000121*
1000000    0.086378    *0.056726*    0.029879    0.021753    0.015436
 0.014460    0.017390    0.010898    0.008257



Tested x86_64-unknown-linux-gnu: No new regressions

Please approve for mainline.  gcc-4_4-branch also?

2010-03-30  Johannes Singler  <singler@kit.edu>

        * include/parallel/random_shuffle.h
        (__parallel_random_shuffle_drs) : Take as many threads as
        possible, i. e. favor parallelism over cache efficiency.
        Use own PRNG also for the 1 thread case.

Johannes


Index: include/parallel/random_shuffle.h
===================================================================
--- include/parallel/random_shuffle.h	(revision 157644)
+++ include/parallel/random_shuffle.h	(working copy)
@@ -322,10 +322,15 @@
 	}
 #endif
 
-      __num_threads = std::min<_BinIndex>(__num_threads, __num_bins);
+      __num_bins = __round_up_to_pow2(
+                        std::max<_BinIndex>(__num_threads, __num_bins));
 
       if (__num_threads <= 1)
-	return __sequential_random_shuffle(__begin, __end, __rng);
+      {
+        _RandomNumber __derived_rng(__rng(std::numeric_limits<uint32_t>::max()));
+	__sequential_random_shuffle(__begin, __end, __derived_rng);
+        return;
+      }
 
       _DRandomShufflingGlobalData<_RAIter> __sd(__begin);
       _DRSSorterPU<_RAIter, _RandomNumber >* __pus;

Index: include/parallel/random_shuffle.h
===================================================================
--- include/parallel/random_shuffle.h	(revision 157799)
+++ include/parallel/random_shuffle.h	(working copy)
@@ -316,10 +316,14 @@
       }
 #endif
 
-    num_threads = std::min<bin_index>(num_threads, num_bins);
+    num_bins = round_up_to_pow2(std::max<bin_index>(num_threads, num_bins));
 
     if (num_threads <= 1)
-      return sequential_random_shuffle(begin, end, rng);
+    {
+      random_number derived_rng(std::numeric_limits<uint32>::max());
+      sequential_random_shuffle(begin, end, derived_rng);
+      return;
+    }
 
     DRandomShufflingGlobalData<RandomAccessIterator> sd(begin);
     DRSSorterPU<RandomAccessIterator, random_number >* pus;


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]