settings.h 12 KB

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