libstdc++
find.h
Go to the documentation of this file.
1 // -*- C++ -*-
2 
3 // Copyright (C) 2007, 2008, 2009 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/find.h
26  * @brief Parallel implementation base for std::find(), std::equal()
27  * and related functions.
28  * This file is a GNU parallel extension to the Standard C++ Library.
29  */
30 
31 // Written by Felix Putze and Johannes Singler.
32 
33 #ifndef _GLIBCXX_PARALLEL_FIND_H
34 #define _GLIBCXX_PARALLEL_FIND_H 1
35 
36 #include <bits/stl_algobase.h>
37 
38 #include <parallel/features.h>
39 #include <parallel/parallel.h>
40 #include <parallel/compatibility.h>
41 #include <parallel/equally_split.h>
42 
43 namespace __gnu_parallel
44 {
45 /**
46  * @brief Parallel std::find, switch for different algorithms.
47  * @param begin1 Begin iterator of first sequence.
48  * @param end1 End iterator of first sequence.
49  * @param begin2 Begin iterator of second sequence. Must have same
50  * length as first sequence.
51  * @param pred Find predicate.
52  * @param selector Functionality (e. g. std::find_if (), std::equal(),...)
53  * @return Place of finding in both sequences.
54  */
55 template<typename RandomAccessIterator1,
56  typename RandomAccessIterator2,
57  typename Pred,
58  typename Selector>
60  find_template(RandomAccessIterator1 begin1, RandomAccessIterator1 end1,
61  RandomAccessIterator2 begin2, Pred pred, Selector selector)
62  {
63  switch (_Settings::get().find_algorithm)
64  {
65  case GROWING_BLOCKS:
66  return find_template(begin1, end1, begin2, pred, selector,
68  case CONSTANT_SIZE_BLOCKS:
69  return find_template(begin1, end1, begin2, pred, selector,
71  case EQUAL_SPLIT:
72  return find_template(begin1, end1, begin2, pred, selector,
73  equal_split_tag());
74  default:
75  _GLIBCXX_PARALLEL_ASSERT(false);
76  return std::make_pair(begin1, begin2);
77  }
78  }
79 
80 #if _GLIBCXX_FIND_EQUAL_SPLIT
81 
82 /**
83  * @brief Parallel std::find, equal splitting variant.
84  * @param begin1 Begin iterator of first sequence.
85  * @param end1 End iterator of first sequence.
86  * @param begin2 Begin iterator of second sequence. Second sequence
87  * must have same length as first sequence.
88  * @param pred Find predicate.
89  * @param selector Functionality (e. g. std::find_if (), std::equal(),...)
90  * @return Place of finding in both sequences.
91  */
92 template<typename RandomAccessIterator1,
93  typename RandomAccessIterator2,
94  typename Pred,
95  typename Selector>
97  find_template(RandomAccessIterator1 begin1,
98  RandomAccessIterator1 end1,
99  RandomAccessIterator2 begin2,
100  Pred pred,
101  Selector selector,
102  equal_split_tag)
103  {
104  _GLIBCXX_CALL(end1 - begin1)
105 
106  typedef std::iterator_traits<RandomAccessIterator1> traits_type;
107  typedef typename traits_type::difference_type difference_type;
108  typedef typename traits_type::value_type value_type;
109 
110  difference_type length = end1 - begin1;
111  difference_type result = length;
112  difference_type* borders;
113 
114  omp_lock_t result_lock;
115  omp_init_lock(&result_lock);
116 
117  thread_index_t num_threads = get_max_threads();
118 # pragma omp parallel num_threads(num_threads)
119  {
120 # pragma omp single
121  {
122  num_threads = omp_get_num_threads();
123  borders = new difference_type[num_threads + 1];
124  equally_split(length, num_threads, borders);
125  } //single
126 
127  thread_index_t iam = omp_get_thread_num();
128  difference_type start = borders[iam], stop = borders[iam + 1];
129 
130  RandomAccessIterator1 i1 = begin1 + start;
131  RandomAccessIterator2 i2 = begin2 + start;
132  for (difference_type pos = start; pos < stop; ++pos)
133  {
134  #pragma omp flush(result)
135  // Result has been set to something lower.
136  if (result < pos)
137  break;
138 
139  if (selector(i1, i2, pred))
140  {
141  omp_set_lock(&result_lock);
142  if (pos < result)
143  result = pos;
144  omp_unset_lock(&result_lock);
145  break;
146  }
147  ++i1;
148  ++i2;
149  }
150  } //parallel
151 
152  omp_destroy_lock(&result_lock);
153  delete[] borders;
154 
155  return
157  begin2 + result);
158  }
159 
160 #endif
161 
162 #if _GLIBCXX_FIND_GROWING_BLOCKS
163 
164 /**
165  * @brief Parallel std::find, growing block size variant.
166  * @param begin1 Begin iterator of first sequence.
167  * @param end1 End iterator of first sequence.
168  * @param begin2 Begin iterator of second sequence. Second sequence
169  * must have same length as first sequence.
170  * @param pred Find predicate.
171  * @param selector Functionality (e. g. std::find_if (), std::equal(),...)
172  * @return Place of finding in both sequences.
173  * @see __gnu_parallel::_Settings::find_sequential_search_size
174  * @see __gnu_parallel::_Settings::find_initial_block_size
175  * @see __gnu_parallel::_Settings::find_maximum_block_size
176  * @see __gnu_parallel::_Settings::find_increasing_factor
177  *
178  * There are two main differences between the growing blocks and
179  * the constant-size blocks variants.
180  * 1. For GB, the block size grows; for CSB, the block size is fixed.
181 
182  * 2. For GB, the blocks are allocated dynamically;
183  * for CSB, the blocks are allocated in a predetermined manner,
184  * namely spacial round-robin.
185  */
186 template<typename RandomAccessIterator1,
187  typename RandomAccessIterator2,
188  typename Pred,
189  typename Selector>
191  find_template(RandomAccessIterator1 begin1, RandomAccessIterator1 end1,
192  RandomAccessIterator2 begin2, Pred pred, Selector selector,
193  growing_blocks_tag)
194  {
195  _GLIBCXX_CALL(end1 - begin1)
196 
197  typedef std::iterator_traits<RandomAccessIterator1> traits_type;
198  typedef typename traits_type::difference_type difference_type;
199  typedef typename traits_type::value_type value_type;
200 
201  const _Settings& __s = _Settings::get();
202 
203  difference_type length = end1 - begin1;
204 
205  difference_type sequential_search_size =
206  std::min<difference_type>(length, __s.find_sequential_search_size);
207 
208  // Try it sequentially first.
209  std::pair<RandomAccessIterator1, RandomAccessIterator2> find_seq_result =
210  selector.sequential_algorithm(
211  begin1, begin1 + sequential_search_size, begin2, pred);
212 
213  if (find_seq_result.first != (begin1 + sequential_search_size))
214  return find_seq_result;
215 
216  // Index of beginning of next free block (after sequential find).
217  difference_type next_block_start = sequential_search_size;
218  difference_type result = length;
219 
220  omp_lock_t result_lock;
221  omp_init_lock(&result_lock);
222 
223  thread_index_t num_threads = get_max_threads();
224 # pragma omp parallel shared(result) num_threads(num_threads)
225  {
226 # pragma omp single
227  num_threads = omp_get_num_threads();
228 
229  // Not within first k elements -> start parallel.
230  thread_index_t iam = omp_get_thread_num();
231 
232  difference_type block_size = __s.find_initial_block_size;
233  difference_type start =
234  fetch_and_add<difference_type>(&next_block_start, block_size);
235 
236  // Get new block, update pointer to next block.
237  difference_type stop =
238  std::min<difference_type>(length, start + block_size);
239 
241 
242  while (start < length)
243  {
244 # pragma omp flush(result)
245  // Get new value of result.
246  if (result < start)
247  {
248  // No chance to find first element.
249  break;
250  }
251 
252  local_result = selector.sequential_algorithm(
253  begin1 + start, begin1 + stop, begin2 + start, pred);
254  if (local_result.first != (begin1 + stop))
255  {
256  omp_set_lock(&result_lock);
257  if ((local_result.first - begin1) < result)
258  {
259  result = local_result.first - begin1;
260 
261  // Result cannot be in future blocks, stop algorithm.
262  fetch_and_add<difference_type>(&next_block_start, length);
263  }
264  omp_unset_lock(&result_lock);
265  }
266 
267  block_size =
268  std::min<difference_type>(block_size * __s.find_increasing_factor,
269  __s.find_maximum_block_size);
270 
271  // Get new block, update pointer to next block.
272  start =
273  fetch_and_add<difference_type>(&next_block_start, block_size);
274  stop = ((length < (start + block_size))
275  ? length : (start + block_size));
276  }
277  } //parallel
278 
279  omp_destroy_lock(&result_lock);
280 
281  // Return iterator on found element.
282  return
284  begin2 + result);
285  }
286 
287 #endif
288 
289 #if _GLIBCXX_FIND_CONSTANT_SIZE_BLOCKS
290 
291 /**
292  * @brief Parallel std::find, constant block size variant.
293  * @param begin1 Begin iterator of first sequence.
294  * @param end1 End iterator of first sequence.
295  * @param begin2 Begin iterator of second sequence. Second sequence
296  * must have same length as first sequence.
297  * @param pred Find predicate.
298  * @param selector Functionality (e. g. std::find_if (), std::equal(),...)
299  * @return Place of finding in both sequences.
300  * @see __gnu_parallel::_Settings::find_sequential_search_size
301  * @see __gnu_parallel::_Settings::find_block_size
302  * There are two main differences between the growing blocks and the
303  * constant-size blocks variants.
304  * 1. For GB, the block size grows; for CSB, the block size is fixed.
305  * 2. For GB, the blocks are allocated dynamically; for CSB, the
306  * blocks are allocated in a predetermined manner, namely spacial
307  * round-robin.
308  */
309 template<typename RandomAccessIterator1,
310  typename RandomAccessIterator2,
311  typename Pred,
312  typename Selector>
314  find_template(RandomAccessIterator1 begin1, RandomAccessIterator1 end1,
315  RandomAccessIterator2 begin2, Pred pred, Selector selector,
316  constant_size_blocks_tag)
317  {
318  _GLIBCXX_CALL(end1 - begin1)
319  typedef std::iterator_traits<RandomAccessIterator1> traits_type;
320  typedef typename traits_type::difference_type difference_type;
321  typedef typename traits_type::value_type value_type;
322 
323  const _Settings& __s = _Settings::get();
324 
325  difference_type length = end1 - begin1;
326 
327  difference_type sequential_search_size = std::min<difference_type>(
328  length, __s.find_sequential_search_size);
329 
330  // Try it sequentially first.
331  std::pair<RandomAccessIterator1, RandomAccessIterator2> find_seq_result =
332  selector.sequential_algorithm(begin1, begin1 + sequential_search_size,
333  begin2, pred);
334 
335  if (find_seq_result.first != (begin1 + sequential_search_size))
336  return find_seq_result;
337 
338  difference_type result = length;
339  omp_lock_t result_lock;
340  omp_init_lock(&result_lock);
341 
342  // Not within first sequential_search_size elements -> start parallel.
343 
344  thread_index_t num_threads = get_max_threads();
345 # pragma omp parallel shared(result) num_threads(num_threads)
346  {
347 # pragma omp single
348  num_threads = omp_get_num_threads();
349 
350  thread_index_t iam = omp_get_thread_num();
351  difference_type block_size = __s.find_initial_block_size;
352 
353  // First element of thread's current iteration.
354  difference_type iteration_start = sequential_search_size;
355 
356  // Where to work (initialization).
357  difference_type start = iteration_start + iam * block_size;
358  difference_type stop =
359  std::min<difference_type>(length, start + block_size);
360 
362 
363  while (start < length)
364  {
365  // Get new value of result.
366 # pragma omp flush(result)
367  // No chance to find first element.
368  if (result < start)
369  break;
370  local_result = selector.sequential_algorithm(
371  begin1 + start, begin1 + stop,
372  begin2 + start, pred);
373  if (local_result.first != (begin1 + stop))
374  {
375  omp_set_lock(&result_lock);
376  if ((local_result.first - begin1) < result)
377  result = local_result.first - begin1;
378  omp_unset_lock(&result_lock);
379  // Will not find better value in its interval.
380  break;
381  }
382 
383  iteration_start += num_threads * block_size;
384 
385  // Where to work.
386  start = iteration_start + iam * block_size;
387  stop = std::min<difference_type>(length, start + block_size);
388  }
389  } //parallel
390 
391  omp_destroy_lock(&result_lock);
392 
393  // Return iterator on found element.
394  return
396  begin2 + result);
397  }
398 #endif
399 } // end namespace
400 
401 #endif /* _GLIBCXX_PARALLEL_FIND_H */
#define _GLIBCXX_CALL(n)
Macro to produce log message when entering a function.
Selects the constant block size variant for std::find().
Definition: tags.h:184
Compatibility layer, mostly concerned with atomic operations. This file is a GNU parallel extension t...
Defines on whether to include algorithm variants.
Selects the equal splitting variant for std::find().
Definition: tags.h:188
ISO C++ entities toplevel namespace is std.
GNU parallel code for public use.
Selects the growing block size variant for std::find().
Definition: tags.h:180
pair holds two objects of arbitrary type.
Definition: stl_pair.h:67
static const _Settings & get()
Get the global settings.
const T & min(const T &a, const T &b)
Equivalent to std::min.
Definition: base.h:145
uint16 thread_index_t
Unsigned integer to index a thread number. The maximum thread number (for each processor) must fit in...
Definition: types.h:141
std::pair< RandomAccessIterator1, RandomAccessIterator2 > find_template(RandomAccessIterator1 begin1, RandomAccessIterator1 end1, RandomAccessIterator2 begin2, Pred pred, Selector selector)
Parallel std::find, switch for different algorithms.
Definition: find.h:60
End-user include file. Provides advanced settings and tuning options. This file is a GNU parallel ext...
OutputIterator equally_split(difference_type n, thread_index_t num_threads, OutputIterator s)
Function to split a sequence into parts of almost equal size.
Definition: equally_split.h:48