[PATCH][libstdc++-v3 parallel mode] Clean up loser tree and multiway_merge code

[Johannes Singler]

The following patch makes the parallel mode get rid of obsolete loser 
tree variants and cleans up the whole multiway_merge/multiway_merge_sort 
thing (the parallel stable sorter). Many decisions are shifted from 
runtime to compile-time (e. g. stability yes/no and splitting variant), 
which results in smaller executables and faster compilation. Large 
objects are now held as pointers in the loser tree, which can 
drastically improve execution speed.

I admit that the diff is complicated to read for multiway_merge.h and 
losertree.h because they are basically entirely rewritten.

Tested x86_64-unknown-linux-gnu: No regressions

Please approve for mainline.


This also fixes PR 35588. I could do a much easier separate fix for the 
4.3 branch, if desired.


2008-04-03  Johannes Singler  <singler@ira.uka.de>

         * include/parallel/multiway_merge.h:
           Moved decisions to compiletime instead of runtime.
         * include/parallel/losertree.h:
           Removed obsolete variants, added variant that uses pointers
           in the loser tree.
         * include/parallel/types.h:
           Remove obsolete settings options from enum.
         * include/parallel/features.h:
           Remove obsolete compile-time switches.
         * include/parallel/compiletime_settings.h:
           Remove obsolete variant that copies back *after* sorting.
         * include/parallel/tags.h:
           Add one new tag for compile-time switch.
         * include/parallel/merge.h:
           Adapt to changes in multiway_merge.h.
         * include/parallel/multiway_mergesort.h:
           Adapt to changes in multiway_merge.h.
           Factor out splitting variants.
           Remove obsolete variant that copies back *after* sorting.
         * include/parallel/sort.h:
           Adapt to changes in multiway_mergesort.h.

Johannes
-------------- next part --------------
A non-text attachment was scrubbed...
Name: multiway_merge_cleanup.patch
Type: text/x-patch
Size: 175436 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20080403/8ccdf25c/attachment.bin>