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

[Johannes Singler]

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


-------------- next part --------------
A non-text attachment was scrubbed...
Name: random_shuffle_speedup.patch
Type: text/x-patch
Size: 828 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20100330/b55345cb/attachment.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: random_shuffle_speedup_4.4.patch
Type: text/x-patch
Size: 774 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20100330/b55345cb/attachment-0001.bin>