libstdc++-v3/include/parallel/find.h

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2007, 2008, 2009, 2010, 2011 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 _RAIter1,
  56            typename _RAIter2,
  57            typename _Pred,
  58            typename _Selector>
  59     inline std::pair<_RAIter1, _RAIter2>
  60     __find_template(_RAIter1 __begin1, _RAIter1 __end1,
  61                     _RAIter2 __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,
  67                                  __selector, growing_blocks_tag());
  68         case CONSTANT_SIZE_BLOCKS:
  69           return __find_template(__begin1, __end1, __begin2, __pred,
  70                                  __selector, constant_size_blocks_tag());
  71         case EQUAL_SPLIT:
  72           return __find_template(__begin1, __end1, __begin2, __pred,
  73                                  __selector, 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 _RAIter1,
  93            typename _RAIter2,
  94            typename _Pred,
  95            typename _Selector>
  96     std::pair<_RAIter1, _RAIter2>
  97     __find_template(_RAIter1 __begin1, _RAIter1 __end1,
  98                     _RAIter2 __begin2, _Pred __pred,
  99                     _Selector __selector, equal_split_tag)
 100     {
 101       _GLIBCXX_CALL(__end1 - __begin1)
 102
 103       typedef std::iterator_traits<_RAIter1> _TraitsType;
 104       typedef typename _TraitsType::difference_type _DifferenceType;
 105       typedef typename _TraitsType::value_type _ValueType;
 106
 107       _DifferenceType __length = __end1 - __begin1;
 108       _DifferenceType __result = __length;
 109       _DifferenceType* __borders;
 110
 111       omp_lock_t __result_lock;
 112       omp_init_lock(&__result_lock);
 113
 114       _ThreadIndex __num_threads = __get_max_threads();
 115 #     pragma omp parallel num_threads(__num_threads)
 116       {
 117 #     pragma omp single
 118         {
 119           __num_threads = omp_get_num_threads();
 120           __borders = new _DifferenceType[__num_threads + 1];
 121           __equally_split(__length, __num_threads, __borders);
 122         } //single
 123
 124         _ThreadIndex __iam = omp_get_thread_num();
 125         _DifferenceType __start = __borders[__iam],
 126                          __stop = __borders[__iam + 1];
 127
 128         _RAIter1 __i1 = __begin1 + __start;
 129         _RAIter2 __i2 = __begin2 + __start;
 130         for (_DifferenceType __pos = __start; __pos < __stop; ++__pos)
 131           {
 132 #           pragma omp flush(__result)
 133             // Result has been set to something lower.
 134             if (__result < __pos)
 135               break;
 136
 137             if (__selector(__i1, __i2, __pred))
 138               {
 139                 omp_set_lock(&__result_lock);
 140                 if (__pos < __result)
 141                   __result = __pos;
 142                 omp_unset_lock(&__result_lock);
 143                 break;
 144               }
 145             ++__i1;
 146             ++__i2;
 147           }
 148       } //parallel
 149
 150       omp_destroy_lock(&__result_lock);
 151       delete[] __borders;
 152
 153       return std::pair<_RAIter1, _RAIter2>(__begin1 + __result,
 154                                            __begin2 + __result);
 155     }
 156
 157 #endif
 158
 159 #if _GLIBCXX_FIND_GROWING_BLOCKS
 160
 161   /**
 162    *  @brief Parallel std::find, growing block size variant.
 163    *  @param __begin1 Begin iterator of first sequence.
 164    *  @param __end1 End iterator of first sequence.
 165    *  @param __begin2 Begin iterator of second sequence. Second __sequence
 166    *  must have same length as first sequence.
 167    *  @param __pred Find predicate.
 168    *  @param __selector _Functionality (e. g. std::find_if(), std::equal(),...)
 169    *  @return Place of finding in both sequences.
 170    *  @see __gnu_parallel::_Settings::find_sequential_search_size
 171    *  @see __gnu_parallel::_Settings::find_scale_factor
 172    *
 173    *  There are two main differences between the growing blocks and
 174    *  the constant-size blocks variants.
 175    *  1. For GB, the block size grows; for CSB, the block size is fixed.
 176    *  2. For GB, the blocks are allocated dynamically;
 177    *     for CSB, the blocks are allocated in a predetermined manner,
 178    *     namely spacial round-robin.
 179    */
 180   template<typename _RAIter1,
 181            typename _RAIter2,
 182            typename _Pred,
 183            typename _Selector>
 184     std::pair<_RAIter1, _RAIter2>
 185     __find_template(_RAIter1 __begin1, _RAIter1 __end1,
 186                     _RAIter2 __begin2, _Pred __pred, _Selector __selector,
 187                     growing_blocks_tag)
 188     {
 189       _GLIBCXX_CALL(__end1 - __begin1)
 190
 191       typedef std::iterator_traits<_RAIter1> _TraitsType;
 192       typedef typename _TraitsType::difference_type _DifferenceType;
 193       typedef typename _TraitsType::value_type _ValueType;
 194
 195       const _Settings& __s = _Settings::get();
 196
 197       _DifferenceType __length = __end1 - __begin1;
 198
 199       _DifferenceType
 200         __sequential_search_size = std::min<_DifferenceType>
 201         (__length, __s.find_sequential_search_size);
 202
 203       // Try it sequentially first.
 204       std::pair<_RAIter1, _RAIter2>
 205         __find_seq_result = __selector._M_sequential_algorithm
 206         (__begin1, __begin1 + __sequential_search_size,
 207          __begin2, __pred);
 208
 209       if (__find_seq_result.first != (__begin1 + __sequential_search_size))
 210         return __find_seq_result;
 211
 212       // Index of beginning of next free block (after sequential find).
 213       _DifferenceType __next_block_start = __sequential_search_size;
 214       _DifferenceType __result = __length;
 215
 216       omp_lock_t __result_lock;
 217       omp_init_lock(&__result_lock);
 218
 219       const float __scale_factor = __s.find_scale_factor;
 220
 221       _ThreadIndex __num_threads = __get_max_threads();
 222 #     pragma omp parallel shared(__result) num_threads(__num_threads)
 223       {
 224 #       pragma omp single
 225         __num_threads = omp_get_num_threads();
 226
 227         // Not within first __k elements -> start parallel.
 228         _ThreadIndex __iam = omp_get_thread_num();
 229
 230         _DifferenceType __block_size =
 231           std::max<_DifferenceType>(1, __scale_factor * __next_block_start);
 232         _DifferenceType __start = __fetch_and_add<_DifferenceType>
 233           (&__next_block_start, __block_size);
 234
 235         // Get new block, update pointer to next block.
 236         _DifferenceType __stop =
 237           std::min<_DifferenceType>(__length, __start + __block_size);
 238
 239         std::pair<_RAIter1, _RAIter2> __local_result;
 240
 241         while (__start < __length)
 242           {
 243 #           pragma omp flush(__result)
 244             // Get new value of result.
 245             if (__result < __start)
 246               {
 247                 // No chance to find first element.
 248                 break;
 249               }
 250
 251             __local_result = __selector._M_sequential_algorithm
 252               (__begin1 + __start, __begin1 + __stop,
 253                __begin2 + __start, __pred);
 254
 255             if (__local_result.first != (__begin1 + __stop))
 256               {
 257                 omp_set_lock(&__result_lock);
 258                 if ((__local_result.first - __begin1) < __result)
 259                   {
 260                     __result = __local_result.first - __begin1;
 261
 262                     // Result cannot be in future blocks, stop algorithm.
 263                     __fetch_and_add<_DifferenceType>(&__next_block_start,
 264                                                      __length);
 265                   }
 266                 omp_unset_lock(&__result_lock);
 267               }
 268
 269             _DifferenceType __block_size =
 270              std::max<_DifferenceType>(1, __scale_factor * __next_block_start);
 271
 272             // Get new block, update pointer to next block.
 273             __start = __fetch_and_add<_DifferenceType>(&__next_block_start,
 274                                                        __block_size);
 275             __stop =
 276               std::min<_DifferenceType>(__length, __start + __block_size);
 277           }
 278       } //parallel
 279
 280       omp_destroy_lock(&__result_lock);
 281
 282       // Return iterator on found element.
 283       return
 284         std::pair<_RAIter1, _RAIter2>(__begin1 + __result,
 285                                       __begin2 + __result);
 286     }
 287
 288 #endif
 289
 290 #if _GLIBCXX_FIND_CONSTANT_SIZE_BLOCKS
 291
 292   /**
 293    *   @brief Parallel std::find, constant block size variant.
 294    *  @param __begin1 Begin iterator of first sequence.
 295    *  @param __end1 End iterator of first sequence.
 296    *  @param __begin2 Begin iterator of second sequence. Second __sequence
 297    *  must have same length as first sequence.
 298    *  @param __pred Find predicate.
 299    *  @param __selector _Functionality (e. g. std::find_if(), std::equal(),...)
 300    *  @return Place of finding in both sequences.
 301    *  @see __gnu_parallel::_Settings::find_sequential_search_size
 302    *  @see __gnu_parallel::_Settings::find_block_size
 303    *  There are two main differences between the growing blocks and the
 304    *  constant-size blocks variants.
 305    *  1. For GB, the block size grows; for CSB, the block size is fixed.
 306    *  2. For GB, the blocks are allocated dynamically; for CSB, the
 307    *  blocks are allocated in a predetermined manner, namely spacial
 308    *  round-robin.
 309    */
 310   template<typename _RAIter1,
 311            typename _RAIter2,
 312            typename _Pred,
 313            typename _Selector>
 314     std::pair<_RAIter1, _RAIter2>
 315     __find_template(_RAIter1 __begin1, _RAIter1 __end1,
 316                   _RAIter2 __begin2, _Pred __pred, _Selector __selector,
 317                   constant_size_blocks_tag)
 318     {
 319       _GLIBCXX_CALL(__end1 - __begin1)
 320       typedef std::iterator_traits<_RAIter1> _TraitsType;
 321       typedef typename _TraitsType::difference_type _DifferenceType;
 322       typedef typename _TraitsType::value_type _ValueType;
 323
 324       const _Settings& __s = _Settings::get();
 325
 326       _DifferenceType __length = __end1 - __begin1;
 327
 328       _DifferenceType __sequential_search_size = std::min<_DifferenceType>
 329         (__length, __s.find_sequential_search_size);
 330
 331       // Try it sequentially first.
 332       std::pair<_RAIter1, _RAIter2>
 333         __find_seq_result = __selector._M_sequential_algorithm
 334         (__begin1, __begin1 + __sequential_search_size, __begin2, __pred);
 335
 336       if (__find_seq_result.first != (__begin1 + __sequential_search_size))
 337         return __find_seq_result;
 338
 339       _DifferenceType __result = __length;
 340       omp_lock_t __result_lock;
 341       omp_init_lock(&__result_lock);
 342
 343       // Not within first __sequential_search_size elements -> start parallel.
 344
 345       _ThreadIndex __num_threads = __get_max_threads();
 346 #     pragma omp parallel shared(__result) num_threads(__num_threads)
 347       {
 348 #       pragma omp single
 349         __num_threads = omp_get_num_threads();
 350
 351         _ThreadIndex __iam = omp_get_thread_num();
 352         _DifferenceType __block_size = __s.find_initial_block_size;
 353
 354         // First element of thread's current iteration.
 355         _DifferenceType __iteration_start = __sequential_search_size;
 356
 357         // Where to work (initialization).
 358         _DifferenceType __start = __iteration_start + __iam * __block_size;
 359         _DifferenceType __stop = std::min<_DifferenceType>(__length,
 360                                                            __start
 361                                                            + __block_size);
 362
 363         std::pair<_RAIter1, _RAIter2> __local_result;
 364
 365         while (__start < __length)
 366           {
 367             // Get new value of result.
 368 #           pragma omp flush(__result)
 369             // No chance to find first element.
 370             if (__result < __start)
 371               break;
 372
 373             __local_result = __selector._M_sequential_algorithm
 374               (__begin1 + __start, __begin1 + __stop,
 375                __begin2 + __start, __pred);
 376
 377             if (__local_result.first != (__begin1 + __stop))
 378               {
 379                 omp_set_lock(&__result_lock);
 380                 if ((__local_result.first - __begin1) < __result)
 381                   __result = __local_result.first - __begin1;
 382                 omp_unset_lock(&__result_lock);
 383                 // Will not find better value in its interval.
 384                 break;
 385               }
 386
 387             __iteration_start += __num_threads * __block_size;
 388
 389             // Where to work.
 390             __start = __iteration_start + __iam * __block_size;
 391             __stop = std::min<_DifferenceType>(__length,
 392                                                __start + __block_size);
 393           }
 394       } //parallel
 395
 396       omp_destroy_lock(&__result_lock);
 397
 398       // Return iterator on found element.
 399       return std::pair<_RAIter1, _RAIter2>(__begin1 + __result,
 400                                            __begin2 + __result);
 401     }
 402 #endif
 403 } // end namespace
 404
 405 #endif /* _GLIBCXX_PARALLEL_FIND_H */