This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH][libstdc++-v3 parallel mode] Speed up random_shuffle
- From: Johannes Singler <singler at kit dot edu>
- To: libstdc++ <libstdc++ at gcc dot gnu dot org>, gcc-patches at gcc dot gnu dot org
- Date: Tue, 30 Mar 2010 14:17:32 +0200
- Subject: [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;