3 // Copyright (C) 2007-2024 Free Software Foundation, Inc.
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
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.
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.
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/>.
25 /** @file parallel/settings.h
26 * @brief Runtime settings and tuning parameters, heuristics to decide
27 * whether to use parallelized algorithms.
29 * This file is a GNU parallel extension to the Standard C++ Library.
31 * @section parallelization_decision Deciding whether to run an algorithm in parallel.
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.
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.
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
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,
53 * std::sort(__v.begin(), __v.end(), __gnu_parallel::sequential_tag());
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.
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.
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 .
75 * For some of the algorithms, there are even more tuning options,
76 * e. g. the ability to choose from multiple algorithm variants. See
80 // Written by Johannes Singler and Felix Putze.
82 #ifndef _GLIBCXX_PARALLEL_SETTINGS_H
83 #define _GLIBCXX_PARALLEL_SETTINGS_H 1
85 #include <parallel/types.h>
88 * @brief Determine at compile(?)-time if the parallel variant of an
89 * algorithm should be called.
90 * @param __c A condition that is convertible to bool that is overruled by
91 * __gnu_parallel::_Settings::algorithm_strategy. Usually a decision
92 * based on the input size.
94 #define _GLIBCXX_PARALLEL_CONDITION(__c) \
95 (__gnu_parallel::_Settings::get().algorithm_strategy \
96 != __gnu_parallel::force_sequential \
97 && ((__gnu_parallel::__get_max_threads() > 1 && (__c)) \
98 || __gnu_parallel::_Settings::get().algorithm_strategy \
99 == __gnu_parallel::force_parallel))
103 parallel_condition(bool __c)
106 const _Settings& __s = _Settings::get();
107 if (__s.algorithm_strategy != force_seqential)
109 if (__s.algorithm_strategy == force_parallel)
112 ret = __get_max_threads() > 1 && __c;
118 namespace __gnu_parallel
121 /// Run-time settings for the parallel mode including all tunable parameters.
124 _AlgorithmStrategy algorithm_strategy
;
126 _SortAlgorithm sort_algorithm
;
127 _PartialSumAlgorithm partial_sum_algorithm
;
128 _MultiwayMergeAlgorithm multiway_merge_algorithm
;
129 _FindAlgorithm find_algorithm
;
131 _SplittingAlgorithm sort_splitting
;
132 _SplittingAlgorithm merge_splitting
;
133 _SplittingAlgorithm multiway_merge_splitting
;
135 // Per-algorithm settings.
137 /// Minimal input size for accumulate.
138 _SequenceIndex accumulate_minimal_n
;
140 /// Minimal input size for adjacent_difference.
141 unsigned int adjacent_difference_minimal_n
;
143 /// Minimal input size for count and count_if.
144 _SequenceIndex count_minimal_n
;
146 /// Minimal input size for fill.
147 _SequenceIndex fill_minimal_n
;
149 /// Block size increase factor for find.
150 double find_increasing_factor
;
152 /// Initial block size for find.
153 _SequenceIndex find_initial_block_size
;
155 /// Maximal block size for find.
156 _SequenceIndex find_maximum_block_size
;
158 /// Start with looking for this many elements sequentially, for find.
159 _SequenceIndex find_sequential_search_size
;
161 /// Minimal input size for for_each.
162 _SequenceIndex for_each_minimal_n
;
164 /// Minimal input size for generate.
165 _SequenceIndex generate_minimal_n
;
167 /// Minimal input size for max_element.
168 _SequenceIndex max_element_minimal_n
;
170 /// Minimal input size for merge.
171 _SequenceIndex merge_minimal_n
;
173 /// Oversampling factor for merge.
174 unsigned int merge_oversampling
;
176 /// Minimal input size for min_element.
177 _SequenceIndex min_element_minimal_n
;
179 /// Minimal input size for multiway_merge.
180 _SequenceIndex multiway_merge_minimal_n
;
182 /// Oversampling factor for multiway_merge.
183 int multiway_merge_minimal_k
;
185 /// Oversampling factor for multiway_merge.
186 unsigned int multiway_merge_oversampling
;
188 /// Minimal input size for nth_element.
189 _SequenceIndex nth_element_minimal_n
;
191 /// Chunk size for partition.
192 _SequenceIndex partition_chunk_size
;
194 /// Chunk size for partition, relative to input size. If > 0.0,
195 /// this value overrides partition_chunk_size.
196 double partition_chunk_share
;
198 /// Minimal input size for partition.
199 _SequenceIndex partition_minimal_n
;
201 /// Minimal input size for partial_sort.
202 _SequenceIndex partial_sort_minimal_n
;
204 /// Ratio for partial_sum. Assume "sum and write result" to be
205 /// this factor slower than just "sum".
206 float partial_sum_dilation
;
208 /// Minimal input size for partial_sum.
209 unsigned int partial_sum_minimal_n
;
211 /// Minimal input size for random_shuffle.
212 unsigned int random_shuffle_minimal_n
;
214 /// Minimal input size for replace and replace_if.
215 _SequenceIndex replace_minimal_n
;
217 /// Minimal input size for set_difference.
218 _SequenceIndex set_difference_minimal_n
;
220 /// Minimal input size for set_intersection.
221 _SequenceIndex set_intersection_minimal_n
;
223 /// Minimal input size for set_symmetric_difference.
224 _SequenceIndex set_symmetric_difference_minimal_n
;
226 /// Minimal input size for set_union.
227 _SequenceIndex set_union_minimal_n
;
229 /// Minimal input size for parallel sorting.
230 _SequenceIndex sort_minimal_n
;
232 /// Oversampling factor for parallel std::sort (MWMS).
233 unsigned int sort_mwms_oversampling
;
235 /// Such many samples to take to find a good pivot (quicksort).
236 unsigned int sort_qs_num_samples_preset
;
238 /// Maximal subsequence __length to switch to unbalanced __base case.
239 /// Applies to std::sort with dynamically load-balanced quicksort.
240 _SequenceIndex sort_qsb_base_case_maximal_n
;
242 /// Minimal input size for parallel std::transform.
243 _SequenceIndex transform_minimal_n
;
245 /// Minimal input size for unique_copy.
246 _SequenceIndex unique_copy_minimal_n
;
248 _SequenceIndex workstealing_chunk_size
;
250 // Hardware dependent tuning parameters.
252 /// size of the L1 cache in bytes (underestimation).
253 unsigned long long L1_cache_size
;
255 /// size of the L2 cache in bytes (underestimation).
256 unsigned long long L2_cache_size
;
258 /// size of the Translation Lookaside Buffer (underestimation).
259 unsigned int TLB_size
;
261 /// Overestimation of cache line size. Used to avoid false
262 /// sharing, i.e. elements of different threads are at least this
264 unsigned int cache_line_size
;
268 /// The number of stolen ranges in load-balanced quicksort.
269 _SequenceIndex qsb_steals
;
271 /// Minimal input size for search and search_n.
272 _SequenceIndex search_minimal_n
;
274 /// Block size scale-down factor with respect to current position.
275 float find_scale_factor
;
277 /// Get the global settings.
278 _GLIBCXX_CONST
static const _Settings
&
281 /// Set the global settings.
283 set(_Settings
&) throw();
287 algorithm_strategy(heuristic
),
288 sort_algorithm(MWMS
),
289 partial_sum_algorithm(LINEAR
),
290 multiway_merge_algorithm(LOSER_TREE
),
291 find_algorithm(CONSTANT_SIZE_BLOCKS
),
292 sort_splitting(EXACT
),
293 merge_splitting(EXACT
),
294 multiway_merge_splitting(EXACT
),
295 accumulate_minimal_n(1000),
296 adjacent_difference_minimal_n(1000),
297 count_minimal_n(1000),
298 fill_minimal_n(1000),
299 find_increasing_factor(2.0),
300 find_initial_block_size(256),
301 find_maximum_block_size(8192),
302 find_sequential_search_size(256),
303 for_each_minimal_n(1000),
304 generate_minimal_n(1000),
305 max_element_minimal_n(1000),
306 merge_minimal_n(1000),
307 merge_oversampling(10),
308 min_element_minimal_n(1000),
309 multiway_merge_minimal_n(1000),
310 multiway_merge_minimal_k(2), multiway_merge_oversampling(10),
311 nth_element_minimal_n(1000),
312 partition_chunk_size(1000),
313 partition_chunk_share(0.0),
314 partition_minimal_n(1000),
315 partial_sort_minimal_n(1000),
316 partial_sum_dilation(1.0f
),
317 partial_sum_minimal_n(1000),
318 random_shuffle_minimal_n(1000),
319 replace_minimal_n(1000),
320 set_difference_minimal_n(1000),
321 set_intersection_minimal_n(1000),
322 set_symmetric_difference_minimal_n(1000),
323 set_union_minimal_n(1000),
324 sort_minimal_n(1000),
325 sort_mwms_oversampling(10),
326 sort_qs_num_samples_preset(100),
327 sort_qsb_base_case_maximal_n(100),
328 transform_minimal_n(1000),
329 unique_copy_minimal_n(10000),
330 workstealing_chunk_size(100),
331 L1_cache_size(16 << 10),
332 L2_cache_size(256 << 10),
336 search_minimal_n(1000),
337 find_scale_factor(0.01f
)
342 #endif /* _GLIBCXX_PARALLEL_SETTINGS_H */