l4/pkg/libstdc++-v3/contrib/libstdc++-v3-4.3.3/include/parallel/settings.h

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2007, 2008 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the terms
   7 // of the GNU General Public License as published by the Free Software
   8 // Foundation; either version 2, or (at your option) any later
   9 // version.
  10
  11 // This library is distributed in the hope that it will be useful, but
  12 // WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14 // General Public License for more details.
  15
  16 // You should have received a copy of the GNU General Public License
  17 // along with this library; see the file COPYING.  If not, write to
  18 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
  19 // MA 02111-1307, USA.
  20
  21 // As a special exception, you may use this file as part of a free
  22 // software library without restriction.  Specifically, if other files
  23 // instantiate templates or use macros or inline functions from this
  24 // file, or you compile this file and link it with other files to
  25 // produce an executable, this file does not by itself cause the
  26 // resulting executable to be covered by the GNU General Public
  27 // License.  This exception does not however invalidate any other
  28 // reasons why the executable file might be covered by the GNU General
  29 // Public License.
  30
  31 /** @file parallel/settings.h
  32  *  @brief Runtime settings and tuning parameters, heuristics to decide
  33  *  whether to use parallelized algorithms.
  34  *  This file is a GNU parallel extension to the Standard C++ Library.
  35  *
  36  *  @section parallelization_decision
  37  *  The decision whether to run an algorithm in parallel.
  38  *
  39  *  There are several ways the user can switch on and off the parallel
  40  *  execution of an algorithm, both at compile- and run-time.
  41  *
  42  *  Only sequential execution can be forced at compile-time.  This
  43  *  reduces code size and protects code parts that have
  44  *  non-thread-safe side effects.
  45  *
  46  *  Ultimately, forcing parallel execution at compile-time makes
  47  *  sense.  Often, the sequential algorithm implementation is used as
  48  *  a subroutine, so no reduction in code size can be achieved.  Also,
  49  *  the machine the program is run on might have only one processor
  50  *  core, so to avoid overhead, the algorithm is executed
  51  *  sequentially.
  52  *
  53  *  To force sequential execution of an algorithm ultimately at
  54  *  compile-time, the user must add the tag
  55  *  __gnu_parallel::sequential_tag() to the end of the parameter list,
  56  *  e. g.
  57  *
  58  *  \code
  59  *  std::sort(v.begin(), v.end(), __gnu_parallel::sequential_tag());
  60  *  \endcode
  61  *
  62  *  This is compatible with all overloaded algorithm variants.  No
  63  *  additional code will be instantiated, at all.  The same holds for
  64  *  most algorithm calls with iterators not providing random access.
  65  *
  66  *  If the algorithm call is not forced to be executed sequentially
  67  *  at compile-time, the decision is made at run-time.
  68  *  The global variable __gnu_parallel::_Settings::algorithm_strategy
  69  *  is checked. It is a tristate variable corresponding to:
  70  *
  71  *  a. force_sequential, meaning the sequential algorithm is executed.
  72  *  b. force_parallel, meaning the parallel algorithm is executed.
  73  *  c. heuristic
  74  *
  75  *  For heuristic, the parallel algorithm implementation is called
  76  *  only if the input size is sufficiently large.  For most
  77  *  algorithms, the input size is the (combined) length of the input
  78  *  sequence(s).  The threshold can be set by the user, individually
  79  *  for each algorithm.  The according variables are called
  80  *  __gnu_parallel::_Settings::[algorithm]_minimal_n .
  81  *
  82  *  For some of the algorithms, there are even more tuning options,
  83  *  e. g. the ability to choose from multiple algorithm variants.  See
  84  *  below for details.
  85  */
  86
  87 // Written by Johannes Singler and Felix Putze.
  88
  89 #ifndef _GLIBCXX_PARALLEL_SETTINGS_H
  90 #define _GLIBCXX_PARALLEL_SETTINGS_H 1
  91
  92 #include <parallel/types.h>
  93
  94 /**
  95   * @brief Determine at compile(?)-time if the parallel variant of an
  96   * algorithm should be called.
  97   * @param c A condition that is convertible to bool that is overruled by
  98   * __gnu_parallel::_Settings::algorithm_strategy. Usually a decision
  99   * based on the input size.
 100   */
 101 #define _GLIBCXX_PARALLEL_CONDITION(c) (__gnu_parallel::_Settings::get().algorithm_strategy != __gnu_parallel::force_sequential && ((__gnu_parallel::get_max_threads() > 1 && (c)) || __gnu_parallel::_Settings::get().algorithm_strategy == __gnu_parallel::force_parallel))
 102
 103 /*
 104 inline bool
 105 parallel_condition(bool c)
 106 {
 107   bool ret = false;
 108   const _Settings& s = _Settings::get();
 109   if (s.algorithm_strategy != force_seqential)
 110     {
 111       if (s.algorithm_strategy == force_parallel)
 112         ret = true;
 113       else
 114         ret = get_max_threads() > 1 && c;
 115     }
 116   return ret;
 117 }
 118 */
 119
 120 namespace __gnu_parallel
 121 {
 122   /// class _Settings
 123   /// Run-time settings for the parallel mode, including all tunable parameters.
 124   struct _Settings
 125   {
 126     _AlgorithmStrategy          algorithm_strategy;
 127
 128     _SortAlgorithm              sort_algorithm;
 129     _PartialSumAlgorithm        partial_sum_algorithm;
 130     _MultiwayMergeAlgorithm     multiway_merge_algorithm;
 131     _FindAlgorithm              find_algorithm;
 132
 133     _SplittingAlgorithm         sort_splitting;
 134     _SplittingAlgorithm         merge_splitting;
 135     _SplittingAlgorithm         multiway_merge_splitting;
 136
 137     // Per-algorithm settings.
 138
 139     /// Minimal input size for accumulate.
 140     sequence_index_t            accumulate_minimal_n;
 141
 142     /// Minimal input size for adjacent_difference.
 143     unsigned int                adjacent_difference_minimal_n;
 144
 145     /// Minimal input size for count and count_if.
 146     sequence_index_t            count_minimal_n;
 147
 148     /// Minimal input size for fill.
 149     sequence_index_t            fill_minimal_n;
 150
 151     /// Block size increase factor for find.
 152     double                      find_increasing_factor;
 153
 154     /// Initial block size for find.
 155     sequence_index_t            find_initial_block_size;
 156
 157     /// Maximal block size for find.
 158     sequence_index_t            find_maximum_block_size;
 159
 160     /// Start with looking for this many elements sequentially, for find.
 161     sequence_index_t            find_sequential_search_size;
 162
 163     /// Minimal input size for for_each.
 164     sequence_index_t            for_each_minimal_n;
 165
 166     /// Minimal input size for generate.
 167     sequence_index_t            generate_minimal_n;
 168
 169     /// Minimal input size for max_element.
 170     sequence_index_t            max_element_minimal_n;
 171
 172     /// Minimal input size for merge.
 173     sequence_index_t            merge_minimal_n;
 174
 175     /// Oversampling factor for merge.
 176     unsigned int                merge_oversampling;
 177
 178     /// Minimal input size for min_element.
 179     sequence_index_t            min_element_minimal_n;
 180
 181     /// Minimal input size for multiway_merge.
 182     sequence_index_t            multiway_merge_minimal_n;
 183
 184     /// Oversampling factor for multiway_merge.
 185     int                         multiway_merge_minimal_k;
 186
 187     /// Oversampling factor for multiway_merge.
 188     unsigned int                multiway_merge_oversampling;
 189
 190     /// Minimal input size for nth_element.
 191     sequence_index_t            nth_element_minimal_n;
 192
 193     /// Chunk size for partition.
 194     sequence_index_t            partition_chunk_size;
 195
 196     /// Chunk size for partition, relative to input size.  If > 0.0,
 197     /// this value overrides partition_chunk_size.
 198     double                      partition_chunk_share;
 199
 200     /// Minimal input size for partition.
 201     sequence_index_t            partition_minimal_n;
 202
 203     /// Minimal input size for partial_sort.
 204     sequence_index_t            partial_sort_minimal_n;
 205
 206     /// Ratio for partial_sum. Assume "sum and write result" to be
 207     /// this factor slower than just "sum".
 208     float                       partial_sum_dilation;
 209
 210     /// Minimal input size for partial_sum.
 211     unsigned int                partial_sum_minimal_n;
 212
 213     /// Minimal input size for random_shuffle.
 214     unsigned int                random_shuffle_minimal_n;
 215
 216     /// Minimal input size for replace and replace_if.
 217     sequence_index_t            replace_minimal_n;
 218
 219     /// Minimal input size for set_difference.
 220     sequence_index_t            set_difference_minimal_n;
 221
 222     /// Minimal input size for set_intersection.
 223     sequence_index_t            set_intersection_minimal_n;
 224
 225     /// Minimal input size for set_symmetric_difference.
 226     sequence_index_t            set_symmetric_difference_minimal_n;
 227
 228     /// Minimal input size for set_union.
 229     sequence_index_t            set_union_minimal_n;
 230
 231     /// Minimal input size for parallel sorting.
 232     sequence_index_t            sort_minimal_n;
 233
 234     /// Oversampling factor for parallel std::sort (MWMS).
 235     unsigned int                sort_mwms_oversampling;
 236
 237     /// Such many samples to take to find a good pivot (quicksort).
 238     unsigned int                sort_qs_num_samples_preset;
 239
 240     /// Maximal subsequence length to switch to unbalanced base case.
 241     /// Applies to std::sort with dynamically load-balanced quicksort.
 242     sequence_index_t            sort_qsb_base_case_maximal_n;
 243
 244     /// Minimal input size for parallel std::transform.
 245     sequence_index_t            transform_minimal_n;
 246
 247     /// Minimal input size for unique_copy.
 248     sequence_index_t            unique_copy_minimal_n;
 249
 250     sequence_index_t            workstealing_chunk_size;
 251
 252     // Hardware dependent tuning parameters.
 253
 254     /// Size of the L1 cache in bytes (underestimation).
 255     unsigned long long          L1_cache_size;
 256
 257     /// Size of the L2 cache in bytes (underestimation).
 258     unsigned long long          L2_cache_size;
 259
 260     /// Size of the Translation Lookaside Buffer (underestimation).
 261     unsigned int                TLB_size;
 262
 263     /// Overestimation of cache line size.  Used to avoid false
 264     /// sharing, i. e. elements of different threads are at least this
 265     /// amount apart.
 266     unsigned int                cache_line_size;
 267
 268     // Statistics.
 269
 270     /// The number of stolen ranges in load-balanced quicksort.
 271     sequence_index_t            qsb_steals;
 272
 273     /// Get the global settings.
 274     static const _Settings&
 275     get() throw();
 276
 277     /// Set the global settings.
 278     static void
 279     set(_Settings&) throw();
 280
 281     explicit
 282     _Settings() : algorithm_strategy(heuristic), sort_algorithm(MWMS), partial_sum_algorithm(LINEAR), multiway_merge_algorithm(LOSER_TREE), find_algorithm(CONSTANT_SIZE_BLOCKS), sort_splitting(EXACT), merge_splitting(EXACT), multiway_merge_splitting(EXACT), accumulate_minimal_n(1000), adjacent_difference_minimal_n(1000), count_minimal_n(1000), fill_minimal_n(1000), find_increasing_factor(2.0), find_initial_block_size(256), find_maximum_block_size(8192), find_sequential_search_size(256), for_each_minimal_n(1000), generate_minimal_n(1000), max_element_minimal_n(1000), merge_minimal_n(1000), merge_oversampling(10), min_element_minimal_n(1000), multiway_merge_minimal_n(1000), multiway_merge_minimal_k(2), multiway_merge_oversampling(10), nth_element_minimal_n(1000), partition_chunk_size(1000), partition_chunk_share(0.0), partition_minimal_n(1000), partial_sort_minimal_n(1000), partial_sum_dilation(1.0f), partial_sum_minimal_n(1000), random_shuffle_minimal_n(1000), replace_minimal_n(1000), set_difference_minimal_n(1000), set_intersection_minimal_n(1000), set_symmetric_difference_minimal_n(1000), set_union_minimal_n(1000), sort_minimal_n(1000), sort_mwms_oversampling(10), sort_qs_num_samples_preset(100), sort_qsb_base_case_maximal_n(100), transform_minimal_n(1000), unique_copy_minimal_n(10000), workstealing_chunk_size(100), L1_cache_size(16 << 10), L2_cache_size(256 << 10), TLB_size(128), cache_line_size(64), qsb_steals(0)
 283     { }
 284   };
 285 }
 286
 287 #endif /* _GLIBCXX_SETTINGS_H */