libstdc++
settings.h
Go to the documentation of this file.
1 // -*- C++ -*-
2 
3 // Copyright (C) 2007-2025 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 3, 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 // Under Section 7 of GPL version 3, you are granted additional
17 // permissions described in the GCC Runtime Library Exception, version
18 // 3.1, as published by the Free Software Foundation.
19 
20 // You should have received a copy of the GNU General Public License and
21 // a copy of the GCC Runtime Library Exception along with this program;
22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 // <http://www.gnu.org/licenses/>.
24 
25 /** @file parallel/settings.h
26  * @brief Runtime settings and tuning parameters, heuristics to decide
27  * whether to use parallelized algorithms.
28  *
29  * This file is a GNU parallel extension to the Standard C++ Library.
30  *
31  * @section parallelization_decision Deciding whether to run an algorithm in parallel.
32  *
33  * There are several ways the user can switch on and off the parallel
34  * execution of an algorithm, both at compile- and run-time.
35  *
36  * Only sequential execution can be forced at compile-time. This
37  * reduces code size and protects code parts that have
38  * non-thread-safe side effects.
39  *
40  * Ultimately, forcing parallel execution at compile-time makes
41  * sense. Often, the sequential algorithm implementation is used as
42  * a subroutine, so no reduction in code size can be achieved. Also,
43  * the machine the program is run on might have only one processor
44  * core, so to avoid overhead, the algorithm is executed
45  * sequentially.
46  *
47  * To force sequential execution of an algorithm ultimately at
48  * compile-time, the user must add the tag
49 * gnu_parallel::sequential_tag() to the end of the parameter list,
50  * e. g.
51  *
52  * \code
53  * std::sort(__v.begin(), __v.end(), __gnu_parallel::sequential_tag());
54  * \endcode
55  *
56  * This is compatible with all overloaded algorithm variants. No
57  * additional code will be instantiated, at all. The same holds for
58  * most algorithm calls with iterators not providing random access.
59  *
60  * If the algorithm call is not forced to be executed sequentially
61  * at compile-time, the decision is made at run-time.
62  * The global variable __gnu_parallel::_Settings::algorithm_strategy
63  * is checked. It is a tristate variable corresponding to:
64  * - a. force_sequential, meaning the sequential algorithm is executed.
65  * - b. force_parallel, meaning the parallel algorithm is executed.
66  * - c. heuristic
67  *
68  * For heuristic, the parallel algorithm implementation is called
69  * only if the input size is sufficiently large. For most
70  * algorithms, the input size is the (combined) length of the input
71  * sequence(__s). The threshold can be set by the user, individually
72  * for each algorithm. The according variables are called
73  * gnu_parallel::_Settings::[algorithm]_minimal_n .
74  *
75  * For some of the algorithms, there are even more tuning options,
76  * e. g. the ability to choose from multiple algorithm variants. See
77  * below for details.
78  */
79 
80 // Written by Johannes Singler and Felix Putze.
81 
82 #ifndef _GLIBCXX_PARALLEL_SETTINGS_H
83 #define _GLIBCXX_PARALLEL_SETTINGS_H 1
84 
85 #include <parallel/types.h>
86 
87 #pragma GCC diagnostic push
88 #pragma GCC diagnostic ignored "-Wlong-long" // LL literal
89 
90 /**
91  * @brief Determine at compile(?)-time if the parallel variant of an
92  * algorithm should be called.
93  * @param __c A condition that is convertible to bool that is overruled by
94  * __gnu_parallel::_Settings::algorithm_strategy. Usually a decision
95  * based on the input size.
96  */
97 #define _GLIBCXX_PARALLEL_CONDITION(__c) \
98  (__gnu_parallel::_Settings::get().algorithm_strategy \
99  != __gnu_parallel::force_sequential \
100  && ((__gnu_parallel::__get_max_threads() > 1 && (__c)) \
101  || __gnu_parallel::_Settings::get().algorithm_strategy \
102  == __gnu_parallel::force_parallel))
103 
104 /*
105 inline bool
106 parallel_condition(bool __c)
107 {
108  bool ret = false;
109  const _Settings& __s = _Settings::get();
110  if (__s.algorithm_strategy != force_seqential)
111  {
112  if (__s.algorithm_strategy == force_parallel)
113  ret = true;
114  else
115  ret = __get_max_threads() > 1 && __c;
116  }
117  return ret;
118 }
119 */
120 
121 namespace __gnu_parallel
122 {
123  /// class _Settings
124  /// Run-time settings for the parallel mode including all tunable parameters.
125  struct _Settings
126  {
127  _AlgorithmStrategy algorithm_strategy;
128 
129  _SortAlgorithm sort_algorithm;
130  _PartialSumAlgorithm partial_sum_algorithm;
131  _MultiwayMergeAlgorithm multiway_merge_algorithm;
132  _FindAlgorithm find_algorithm;
133 
134  _SplittingAlgorithm sort_splitting;
135  _SplittingAlgorithm merge_splitting;
136  _SplittingAlgorithm multiway_merge_splitting;
137 
138  // Per-algorithm settings.
139 
140  /// Minimal input size for accumulate.
142 
143  /// Minimal input size for adjacent_difference.
145 
146  /// Minimal input size for count and count_if.
148 
149  /// Minimal input size for fill.
151 
152  /// Block size increase factor for find.
154 
155  /// Initial block size for find.
157 
158  /// Maximal block size for find.
160 
161  /// Start with looking for this many elements sequentially, for find.
163 
164  /// Minimal input size for for_each.
166 
167  /// Minimal input size for generate.
169 
170  /// Minimal input size for max_element.
172 
173  /// Minimal input size for merge.
175 
176  /// Oversampling factor for merge.
177  unsigned int merge_oversampling;
178 
179  /// Minimal input size for min_element.
181 
182  /// Minimal input size for multiway_merge.
184 
185  /// Oversampling factor for multiway_merge.
187 
188  /// Oversampling factor for multiway_merge.
190 
191  /// Minimal input size for nth_element.
193 
194  /// Chunk size for partition.
196 
197  /// Chunk size for partition, relative to input size. If > 0.0,
198  /// this value overrides partition_chunk_size.
200 
201  /// Minimal input size for partition.
203 
204  /// Minimal input size for partial_sort.
206 
207  /// Ratio for partial_sum. Assume "sum and write result" to be
208  /// this factor slower than just "sum".
210 
211  /// Minimal input size for partial_sum.
212  unsigned int partial_sum_minimal_n;
213 
214  /// Minimal input size for random_shuffle.
216 
217  /// Minimal input size for replace and replace_if.
219 
220  /// Minimal input size for set_difference.
222 
223  /// Minimal input size for set_intersection.
225 
226  /// Minimal input size for set_symmetric_difference.
228 
229  /// Minimal input size for set_union.
231 
232  /// Minimal input size for parallel sorting.
234 
235  /// Oversampling factor for parallel std::sort (MWMS).
237 
238  /// Such many samples to take to find a good pivot (quicksort).
240 
241  /// Maximal subsequence __length to switch to unbalanced __base case.
242  /// Applies to std::sort with dynamically load-balanced quicksort.
244 
245  /// Minimal input size for parallel std::transform.
247 
248  /// Minimal input size for unique_copy.
250 
251  _SequenceIndex workstealing_chunk_size;
252 
253  // Hardware dependent tuning parameters.
254 
255  /// size of the L1 cache in bytes (underestimation).
256  unsigned long long L1_cache_size;
257 
258  /// size of the L2 cache in bytes (underestimation).
259  unsigned long long L2_cache_size;
260 
261  /// size of the Translation Lookaside Buffer (underestimation).
262  unsigned int TLB_size;
263 
264  /// Overestimation of cache line size. Used to avoid false
265  /// sharing, i.e. elements of different threads are at least this
266  /// amount apart.
267  unsigned int cache_line_size;
268 
269  // Statistics.
270 
271  /// The number of stolen ranges in load-balanced quicksort.
273 
274  /// Minimal input size for search and search_n.
276 
277  /// Block size scale-down factor with respect to current position.
279 
280  /// Get the global settings.
281  _GLIBCXX_CONST static const _Settings&
282  get() throw();
283 
284  /// Set the global settings.
285  static void
286  set(_Settings&) throw();
287 
288  explicit
289  _Settings() :
290  algorithm_strategy(heuristic),
291  sort_algorithm(MWMS),
292  partial_sum_algorithm(LINEAR),
293  multiway_merge_algorithm(LOSER_TREE),
294  find_algorithm(CONSTANT_SIZE_BLOCKS),
295  sort_splitting(EXACT),
296  merge_splitting(EXACT),
297  multiway_merge_splitting(EXACT),
298  accumulate_minimal_n(1000),
300  count_minimal_n(1000),
301  fill_minimal_n(1000),
306  for_each_minimal_n(1000),
307  generate_minimal_n(1000),
308  max_element_minimal_n(1000),
309  merge_minimal_n(1000),
310  merge_oversampling(10),
311  min_element_minimal_n(1000),
314  nth_element_minimal_n(1000),
315  partition_chunk_size(1000),
317  partition_minimal_n(1000),
319  partial_sum_dilation(1.0f),
320  partial_sum_minimal_n(1000),
322  replace_minimal_n(1000),
326  set_union_minimal_n(1000),
327  sort_minimal_n(1000),
331  transform_minimal_n(1000),
332  unique_copy_minimal_n(10000),
333  workstealing_chunk_size(100),
334  L1_cache_size(16 << 10),
335  L2_cache_size(256 << 10),
336  TLB_size(128),
337  cache_line_size(64),
338  qsb_steals(0),
339  search_minimal_n(1000),
340  find_scale_factor(0.01f)
341  { }
342  };
343 }
344 
345 #pragma GCC diagnostic pop
346 
347 #endif /* _GLIBCXX_PARALLEL_SETTINGS_H */
Basic types and typedefs. This file is a GNU parallel extension to the Standard C++ Library.
GNU parallel code for public use.
_FindAlgorithm
Find algorithms:
Definition: types.h:107
uint64_t _SequenceIndex
Unsigned integer to index __elements. The total number of elements for each algorithm must fit into t...
Definition: types.h:117
_SortAlgorithm
Sorting algorithms:
Definition: types.h:77
_PartialSumAlgorithm
Partial sum algorithms: recursive, linear.
Definition: types.h:92
_MultiwayMergeAlgorithm
Merging algorithms:
Definition: types.h:86
_AlgorithmStrategy
Strategies for run-time algorithm selection:
Definition: types.h:68
_SplittingAlgorithm
Sorting/merging algorithms: sampling, __exact.
Definition: types.h:99
class _Settings Run-time settings for the parallel mode including all tunable parameters.
Definition: settings.h:126
_SequenceIndex search_minimal_n
Minimal input size for search and search_n.
Definition: settings.h:275
unsigned int sort_mwms_oversampling
Oversampling factor for parallel std::sort (MWMS).
Definition: settings.h:236
unsigned int merge_oversampling
Oversampling factor for merge.
Definition: settings.h:177
_SequenceIndex multiway_merge_minimal_n
Minimal input size for multiway_merge.
Definition: settings.h:183
_SequenceIndex sort_minimal_n
Minimal input size for parallel sorting.
Definition: settings.h:233
unsigned int cache_line_size
Overestimation of cache line size. Used to avoid false sharing, i.e. elements of different threads ar...
Definition: settings.h:267
_SequenceIndex for_each_minimal_n
Minimal input size for for_each.
Definition: settings.h:165
_SequenceIndex nth_element_minimal_n
Minimal input size for nth_element.
Definition: settings.h:192
_SequenceIndex set_intersection_minimal_n
Minimal input size for set_intersection.
Definition: settings.h:224
_SequenceIndex sort_qsb_base_case_maximal_n
Maximal subsequence __length to switch to unbalanced __base case. Applies to std::sort with dynamical...
Definition: settings.h:243
unsigned long long L1_cache_size
size of the L1 cache in bytes (underestimation).
Definition: settings.h:256
int multiway_merge_minimal_k
Oversampling factor for multiway_merge.
Definition: settings.h:186
_SequenceIndex replace_minimal_n
Minimal input size for replace and replace_if.
Definition: settings.h:218
_SequenceIndex find_initial_block_size
Initial block size for find.
Definition: settings.h:156
unsigned int adjacent_difference_minimal_n
Minimal input size for adjacent_difference.
Definition: settings.h:144
unsigned int TLB_size
size of the Translation Lookaside Buffer (underestimation).
Definition: settings.h:262
unsigned int random_shuffle_minimal_n
Minimal input size for random_shuffle.
Definition: settings.h:215
unsigned long long L2_cache_size
size of the L2 cache in bytes (underestimation).
Definition: settings.h:259
_SequenceIndex set_difference_minimal_n
Minimal input size for set_difference.
Definition: settings.h:221
unsigned int sort_qs_num_samples_preset
Such many samples to take to find a good pivot (quicksort).
Definition: settings.h:239
_SequenceIndex merge_minimal_n
Minimal input size for merge.
Definition: settings.h:174
_SequenceIndex find_maximum_block_size
Maximal block size for find.
Definition: settings.h:159
_SequenceIndex find_sequential_search_size
Start with looking for this many elements sequentially, for find.
Definition: settings.h:162
unsigned int partial_sum_minimal_n
Minimal input size for partial_sum.
Definition: settings.h:212
float partial_sum_dilation
Ratio for partial_sum. Assume "sum and write result" to be this factor slower than just "sum".
Definition: settings.h:209
_SequenceIndex partial_sort_minimal_n
Minimal input size for partial_sort.
Definition: settings.h:205
_SequenceIndex generate_minimal_n
Minimal input size for generate.
Definition: settings.h:168
double find_increasing_factor
Block size increase factor for find.
Definition: settings.h:153
unsigned int multiway_merge_oversampling
Oversampling factor for multiway_merge.
Definition: settings.h:189
_SequenceIndex min_element_minimal_n
Minimal input size for min_element.
Definition: settings.h:180
double partition_chunk_share
Chunk size for partition, relative to input size. If > 0.0, this value overrides partition_chunk_size...
Definition: settings.h:199
_SequenceIndex set_union_minimal_n
Minimal input size for set_union.
Definition: settings.h:230
static void set(_Settings &)
Set the global settings.
static const _Settings & get()
Get the global settings.
_SequenceIndex set_symmetric_difference_minimal_n
Minimal input size for set_symmetric_difference.
Definition: settings.h:227
_SequenceIndex accumulate_minimal_n
Minimal input size for accumulate.
Definition: settings.h:141
_SequenceIndex max_element_minimal_n
Minimal input size for max_element.
Definition: settings.h:171
float find_scale_factor
Block size scale-down factor with respect to current position.
Definition: settings.h:278
_SequenceIndex qsb_steals
The number of stolen ranges in load-balanced quicksort.
Definition: settings.h:272
_SequenceIndex partition_chunk_size
Chunk size for partition.
Definition: settings.h:195
_SequenceIndex count_minimal_n
Minimal input size for count and count_if.
Definition: settings.h:147
_SequenceIndex fill_minimal_n
Minimal input size for fill.
Definition: settings.h:150
_SequenceIndex partition_minimal_n
Minimal input size for partition.
Definition: settings.h:202
_SequenceIndex transform_minimal_n
Minimal input size for parallel std::transform.
Definition: settings.h:246
_SequenceIndex unique_copy_minimal_n
Minimal input size for unique_copy.
Definition: settings.h:249