libstdc++
partition.h
Go to the documentation of this file.
1 // -*- C++ -*-
2 
3 // Copyright (C) 2007, 2008, 2009, 2010 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/partition.h
26  * @brief Parallel implementation of std::partition(),
27  * std::nth_element(), and std::partial_sort().
28  * This file is a GNU parallel extension to the Standard C++ Library.
29  */
30 
31 // Written by Johannes Singler and Felix Putze.
32 
33 #ifndef _GLIBCXX_PARALLEL_PARTITION_H
34 #define _GLIBCXX_PARALLEL_PARTITION_H 1
35 
37 #include <parallel/sort.h>
38 #include <parallel/random_number.h>
39 #include <bits/stl_algo.h>
40 #include <parallel/parallel.h>
41 
42 /** @brief Decide whether to declare certain variables volatile. */
43 #define _GLIBCXX_VOLATILE volatile
44 
45 namespace __gnu_parallel
46 {
47  /** @brief Parallel implementation of std::partition.
48  * @param __begin Begin iterator of input sequence to split.
49  * @param __end End iterator of input sequence to split.
50  * @param __pred Partition predicate, possibly including some kind
51  * of pivot.
52  * @param __num_threads Maximum number of threads to use for this task.
53  * @return Number of elements not fulfilling the predicate. */
54  template<typename _RAIter, typename _Predicate>
55  typename std::iterator_traits<_RAIter>::difference_type
56  __parallel_partition(_RAIter __begin, _RAIter __end,
57  _Predicate __pred, _ThreadIndex __num_threads)
58  {
59  typedef std::iterator_traits<_RAIter> _TraitsType;
60  typedef typename _TraitsType::value_type _ValueType;
61  typedef typename _TraitsType::difference_type _DifferenceType;
62 
63  _DifferenceType __n = __end - __begin;
64 
65  _GLIBCXX_CALL(__n)
66 
67  const _Settings& __s = _Settings::get();
68 
69  // shared
70  _GLIBCXX_VOLATILE _DifferenceType __left = 0, __right = __n - 1,
71  __dist = __n,
72  __leftover_left, __leftover_right,
73  __leftnew, __rightnew;
74 
75  // just 0 or 1, but int to allow atomic operations
76  int* __reserved_left = 0, * __reserved_right = 0;
77 
78  _DifferenceType __chunk_size = __s.partition_chunk_size;
79 
80  //at least two chunks per thread
81  if (__dist >= 2 * __num_threads * __chunk_size)
82 # pragma omp parallel num_threads(__num_threads)
83  {
84 # pragma omp single
85  {
86  __num_threads = omp_get_num_threads();
87  __reserved_left = new int[__num_threads];
88  __reserved_right = new int[__num_threads];
89 
90  if (__s.partition_chunk_share > 0.0)
91  __chunk_size = std::max<_DifferenceType>
92  (__s.partition_chunk_size, (double)__n
93  * __s.partition_chunk_share / (double)__num_threads);
94  else
95  __chunk_size = __s.partition_chunk_size;
96  }
97 
98  while (__dist >= 2 * __num_threads * __chunk_size)
99  {
100 # pragma omp single
101  {
102  _DifferenceType __num_chunks = __dist / __chunk_size;
103 
104  for (_ThreadIndex __r = 0; __r < __num_threads; ++__r)
105  {
106  __reserved_left [__r] = 0; // false
107  __reserved_right[__r] = 0; // false
108  }
109  __leftover_left = 0;
110  __leftover_right = 0;
111  } //implicit barrier
112 
113  // Private.
114  _DifferenceType __thread_left, __thread_left_border,
115  __thread_right, __thread_right_border;
116 
117  __thread_left = __left + 1;
118  // Just to satisfy the condition below.
119  __thread_left_border = __thread_left - 1;
120 
121  __thread_right = __n - 1;
122  // Just to satisfy the condition below.
123  __thread_right_border = __thread_right + 1;
124 
125  bool __iam_finished = false;
126  while (!__iam_finished)
127  {
128  if (__thread_left > __thread_left_border)
129  {
130  _DifferenceType __former_dist =
131  __fetch_and_add(&__dist, -__chunk_size);
132  if (__former_dist < __chunk_size)
133  {
134  __fetch_and_add(&__dist, __chunk_size);
135  __iam_finished = true;
136  break;
137  }
138  else
139  {
140  __thread_left =
141  __fetch_and_add(&__left, __chunk_size);
142  __thread_left_border =
143  __thread_left + (__chunk_size - 1);
144  }
145  }
146 
147  if (__thread_right < __thread_right_border)
148  {
149  _DifferenceType __former_dist =
150  __fetch_and_add(&__dist, -__chunk_size);
151  if (__former_dist < __chunk_size)
152  {
153  __fetch_and_add(&__dist, __chunk_size);
154  __iam_finished = true;
155  break;
156  }
157  else
158  {
159  __thread_right =
160  __fetch_and_add(&__right, -__chunk_size);
161  __thread_right_border =
162  __thread_right - (__chunk_size - 1);
163  }
164  }
165 
166  // Swap as usual.
167  while (__thread_left < __thread_right)
168  {
169  while (__pred(__begin[__thread_left])
170  && __thread_left <= __thread_left_border)
171  ++__thread_left;
172  while (!__pred(__begin[__thread_right])
173  && __thread_right >= __thread_right_border)
174  --__thread_right;
175 
176  if (__thread_left > __thread_left_border
177  || __thread_right < __thread_right_border)
178  // Fetch new chunk(__s).
179  break;
180 
181  std::iter_swap(__begin + __thread_left,
182  __begin + __thread_right);
183  ++__thread_left;
184  --__thread_right;
185  }
186  }
187 
188  // Now swap the leftover chunks to the right places.
189  if (__thread_left <= __thread_left_border)
190 # pragma omp atomic
191  ++__leftover_left;
192  if (__thread_right >= __thread_right_border)
193 # pragma omp atomic
194  ++__leftover_right;
195 
196 # pragma omp barrier
197 
198  _DifferenceType
199  __leftold = __left,
200  __leftnew = __left - __leftover_left * __chunk_size,
201  __rightold = __right,
202  __rightnew = __right + __leftover_right * __chunk_size;
203 
204  // <=> __thread_left_border + (__chunk_size - 1) >= __leftnew
205  if (__thread_left <= __thread_left_border
206  && __thread_left_border >= __leftnew)
207  {
208  // Chunk already in place, reserve spot.
209  __reserved_left[(__left - (__thread_left_border + 1))
210  / __chunk_size] = 1;
211  }
212 
213  // <=> __thread_right_border - (__chunk_size - 1) <= __rightnew
214  if (__thread_right >= __thread_right_border
215  && __thread_right_border <= __rightnew)
216  {
217  // Chunk already in place, reserve spot.
218  __reserved_right[((__thread_right_border - 1) - __right)
219  / __chunk_size] = 1;
220  }
221 
222 # pragma omp barrier
223 
224  if (__thread_left <= __thread_left_border
225  && __thread_left_border < __leftnew)
226  {
227  // Find spot and swap.
228  _DifferenceType __swapstart = -1;
229  for (int __r = 0; __r < __leftover_left; ++__r)
230  if (__reserved_left[__r] == 0
231  && __compare_and_swap(&(__reserved_left[__r]), 0, 1))
232  {
233  __swapstart = __leftold - (__r + 1) * __chunk_size;
234  break;
235  }
236 
237 #if _GLIBCXX_ASSERTIONS
238  _GLIBCXX_PARALLEL_ASSERT(__swapstart != -1);
239 #endif
240 
241  std::swap_ranges(__begin + __thread_left_border
242  - (__chunk_size - 1),
243  __begin + __thread_left_border + 1,
244  __begin + __swapstart);
245  }
246 
247  if (__thread_right >= __thread_right_border
248  && __thread_right_border > __rightnew)
249  {
250  // Find spot and swap
251  _DifferenceType __swapstart = -1;
252  for (int __r = 0; __r < __leftover_right; ++__r)
253  if (__reserved_right[__r] == 0
254  && __compare_and_swap(&(__reserved_right[__r]), 0, 1))
255  {
256  __swapstart = __rightold + __r * __chunk_size + 1;
257  break;
258  }
259 
260 #if _GLIBCXX_ASSERTIONS
261  _GLIBCXX_PARALLEL_ASSERT(__swapstart != -1);
262 #endif
263 
264  std::swap_ranges(__begin + __thread_right_border,
265  __begin + __thread_right_border
266  + __chunk_size, __begin + __swapstart);
267  }
268 #if _GLIBCXX_ASSERTIONS
269 # pragma omp barrier
270 
271 # pragma omp single
272  {
273  for (_DifferenceType __r = 0; __r < __leftover_left; ++__r)
274  _GLIBCXX_PARALLEL_ASSERT(__reserved_left[__r] == 1);
275  for (_DifferenceType __r = 0; __r < __leftover_right; ++__r)
276  _GLIBCXX_PARALLEL_ASSERT(__reserved_right[__r] == 1);
277  }
278 #endif
279 
280  __left = __leftnew;
281  __right = __rightnew;
282  __dist = __right - __left + 1;
283  }
284 
285 # pragma omp flush(__left, __right)
286  } // end "recursion" //parallel
287 
288  _DifferenceType __final_left = __left, __final_right = __right;
289 
290  while (__final_left < __final_right)
291  {
292  // Go right until key is geq than pivot.
293  while (__pred(__begin[__final_left])
294  && __final_left < __final_right)
295  ++__final_left;
296 
297  // Go left until key is less than pivot.
298  while (!__pred(__begin[__final_right])
299  && __final_left < __final_right)
300  --__final_right;
301 
302  if (__final_left == __final_right)
303  break;
304  std::iter_swap(__begin + __final_left, __begin + __final_right);
305  ++__final_left;
306  --__final_right;
307  }
308 
309  // All elements on the left side are < piv, all elements on the
310  // right are >= piv
311  delete[] __reserved_left;
312  delete[] __reserved_right;
313 
314  // Element "between" __final_left and __final_right might not have
315  // been regarded yet
316  if (__final_left < __n && !__pred(__begin[__final_left]))
317  // Really swapped.
318  return __final_left;
319  else
320  return __final_left + 1;
321  }
322 
323  /**
324  * @brief Parallel implementation of std::nth_element().
325  * @param __begin Begin iterator of input sequence.
326  * @param __nth _Iterator of element that must be in position afterwards.
327  * @param __end End iterator of input sequence.
328  * @param __comp Comparator.
329  */
330  template<typename _RAIter, typename _Compare>
331  void
332  __parallel_nth_element(_RAIter __begin, _RAIter __nth,
333  _RAIter __end, _Compare __comp)
334  {
335  typedef std::iterator_traits<_RAIter> _TraitsType;
336  typedef typename _TraitsType::value_type _ValueType;
337  typedef typename _TraitsType::difference_type _DifferenceType;
338 
339  _GLIBCXX_CALL(__end - __begin)
340 
341  _RAIter __split;
342  _RandomNumber __rng;
343 
344  const _Settings& __s = _Settings::get();
345  _DifferenceType __minimum_length = std::max<_DifferenceType>(2,
347 
348  // Break if input range to small.
349  while (static_cast<_SequenceIndex>(__end - __begin) >= __minimum_length)
350  {
351  _DifferenceType __n = __end - __begin;
352 
353  _RAIter __pivot_pos = __begin + __rng(__n);
354 
355  // Swap __pivot_pos value to end.
356  if (__pivot_pos != (__end - 1))
357  std::iter_swap(__pivot_pos, __end - 1);
358  __pivot_pos = __end - 1;
359 
360  // _Compare must have first_value_type, second_value_type,
361  // result_type
362  // _Compare ==
363  // __gnu_parallel::_Lexicographic<S, int,
364  // __gnu_parallel::_Less<S, S> >
365  // __pivot_pos == std::pair<S, int>*
367  __pred(__comp, *__pivot_pos);
368 
369  // Divide, leave pivot unchanged in last place.
370  _RAIter __split_pos1, __split_pos2;
371  __split_pos1 = __begin + __parallel_partition(__begin, __end - 1,
372  __pred,
373  __get_max_threads());
374 
375  // Left side: < __pivot_pos; __right side: >= __pivot_pos
376 
377  // Swap pivot back to middle.
378  if (__split_pos1 != __pivot_pos)
379  std::iter_swap(__split_pos1, __pivot_pos);
380  __pivot_pos = __split_pos1;
381 
382  // In case all elements are equal, __split_pos1 == 0
383  if ((__split_pos1 + 1 - __begin) < (__n >> 7)
384  || (__end - __split_pos1) < (__n >> 7))
385  {
386  // Very unequal split, one part smaller than one 128th
387  // elements not strictly larger than the pivot.
389  __binder1st<_Compare, _ValueType,
390  _ValueType, bool>, _ValueType>
391  __pred(__gnu_parallel::__binder1st<_Compare, _ValueType,
392  _ValueType, bool>(__comp, *__pivot_pos));
393 
394  // Find other end of pivot-equal range.
395  __split_pos2 = __gnu_sequential::partition(__split_pos1 + 1,
396  __end, __pred);
397  }
398  else
399  // Only skip the pivot.
400  __split_pos2 = __split_pos1 + 1;
401 
402  // Compare iterators.
403  if (__split_pos2 <= __nth)
404  __begin = __split_pos2;
405  else if (__nth < __split_pos1)
406  __end = __split_pos1;
407  else
408  break;
409  }
410 
411  // Only at most _Settings::partition_minimal_n __elements __left.
412  __gnu_sequential::nth_element(__begin, __nth, __end, __comp);
413  }
414 
415  /** @brief Parallel implementation of std::partial_sort().
416  * @param __begin Begin iterator of input sequence.
417  * @param __middle Sort until this position.
418  * @param __end End iterator of input sequence.
419  * @param __comp Comparator. */
420  template<typename _RAIter, typename _Compare>
421  void
422  __parallel_partial_sort(_RAIter __begin,
423  _RAIter __middle,
424  _RAIter __end, _Compare __comp)
425  {
426  __parallel_nth_element(__begin, __middle, __end, __comp);
427  std::sort(__begin, __middle, __comp);
428  }
429 
430 } //namespace __gnu_parallel
431 
432 #undef _GLIBCXX_VOLATILE
433 
434 #endif /* _GLIBCXX_PARALLEL_PARTITION_H */