diff options
Diffstat (limited to 'libstdc++-v3/include/parallel/find.h')
| -rw-r--r-- | libstdc++-v3/include/parallel/find.h | 458 |
1 files changed, 253 insertions, 205 deletions
diff --git a/libstdc++-v3/include/parallel/find.h b/libstdc++-v3/include/parallel/find.h index bc89fa570e5..2a5b22c629f 100644 --- a/libstdc++-v3/include/parallel/find.h +++ b/libstdc++-v3/include/parallel/find.h @@ -10,7 +10,7 @@ // This library is distributed in the hope that it will be useful, but // WITHOUT ANY WARRANTY; without even the implied warranty of -// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURstartE. See the GNU // General Public License for more details. // You should have received a copy of the GNU General Public License @@ -48,50 +48,66 @@ namespace __gnu_parallel { - /** - * @brief Parallel std::find, switch for different algorithms. - * @param begin1 Begin iterator of first sequence. - * @param end1 End iterator of first sequence. - * @param begin2 Begin iterator of second sequence. Must have same - * length as first sequence. - * @param pred Find predicate. - * @param selector Functionality (e. g. std::find_if (), std::equal(),...) - * @return Place of finding in both sequences. - */ - template<typename RandomAccessIterator1, typename RandomAccessIterator2, typename Pred, typename Selector> +/** + * @brief Parallel std::find, switch for different algorithms. + * @param begin1 Begin iterator of first sequence. + * @param end1 End iterator of first sequence. + * @param begin2 Begin iterator of second sequence. Must have same + * length as first sequence. + * @param pred Find predicate. + * @param selector Functionality (e. g. std::find_if (), std::equal(),...) + * @return Place of finding in both sequences. + */ +template< + typename RandomAccessIterator1, + typename RandomAccessIterator2, + typename Pred, + typename Selector> std::pair<RandomAccessIterator1, RandomAccessIterator2> find_template(RandomAccessIterator1 begin1, RandomAccessIterator1 end1, - RandomAccessIterator2 begin2, Pred pred, Selector selector) + RandomAccessIterator2 begin2, Pred pred, Selector selector) { switch (Settings::find_distribution) { case Settings::GROWING_BLOCKS: - return find_template(begin1, end1, begin2, pred, selector, growing_blocks_tag()); + return find_template(begin1, end1, begin2, pred, selector, + growing_blocks_tag()); case Settings::CONSTANT_SIZE_BLOCKS: - return find_template(begin1, end1, begin2, pred, selector, constant_size_blocks_tag()); + return find_template(begin1, end1, begin2, pred, selector, + constant_size_blocks_tag()); case Settings::EQUAL_SPLIT: - return find_template(begin1, end1, begin2, pred, selector, equal_split_tag()); + return find_template(begin1, end1, begin2, pred, selector, + equal_split_tag()); default: - _GLIBCXX_PARALLEL_ASSERT(false); - return std::make_pair(begin1, begin2); + _GLIBCXX_PARALLEL_ASSERT(false); + return std::make_pair(begin1, begin2); } } #if _GLIBCXX_FIND_EQUAL_SPLIT - /** - * @brief Parallel std::find, equal splitting variant. - * @param begin1 Begin iterator of first sequence. - * @param end1 End iterator of first sequence. - * @param begin2 Begin iterator of second sequence. Second sequence - * must have same length as first sequence. - * @param pred Find predicate. - * @param selector Functionality (e. g. std::find_if (), std::equal(),...) - * @return Place of finding in both sequences. - */ - template<typename RandomAccessIterator1, typename RandomAccessIterator2, typename Pred, typename Selector> +/** + * @brief Parallel std::find, equal splitting variant. + * @param begin1 Begin iterator of first sequence. + * @param end1 End iterator of first sequence. + * @param begin2 Begin iterator of second sequence. Second sequence + * must have same length as first sequence. + * @param pred Find predicate. + * @param selector Functionality (e. g. std::find_if (), std::equal(),...) + * @return Place of finding in both sequences. + */ +template< + typename RandomAccessIterator1, + typename RandomAccessIterator2, + typename Pred, + typename Selector> std::pair<RandomAccessIterator1, RandomAccessIterator2> - find_template(RandomAccessIterator1 begin1, RandomAccessIterator1 end1, RandomAccessIterator2 begin2, Pred pred, Selector selector, equal_split_tag) + find_template(RandomAccessIterator1 begin1, + RandomAccessIterator1 end1, + RandomAccessIterator2 begin2, + Pred pred, + Selector selector, + equal_split_tag) { _GLIBCXX_CALL(end1 - begin1) @@ -100,79 +116,89 @@ namespace __gnu_parallel typedef typename traits_type::value_type value_type; difference_type length = end1 - begin1; - difference_type result = length; + difference_type* borders; - const thread_index_t num_threads = get_max_threads(); omp_lock_t result_lock; omp_init_lock(&result_lock); - difference_type* borders = static_cast<difference_type*>(__builtin_alloca(sizeof(difference_type) * (num_threads + 1))); - - equally_split(length, num_threads, borders); - -#pragma omp parallel shared(result) num_threads(num_threads) - { - int iam = omp_get_thread_num(); - difference_type pos = borders[iam], limit = borders[iam + 1]; - - RandomAccessIterator1 i1 = begin1 + pos; - RandomAccessIterator2 i2 = begin2 + pos; - for (; pos < limit; pos++) - { -#pragma omp flush(result) - // Result has been set to something lower. - if (result < pos) - break; - - if (selector(i1, i2, pred)) - { - omp_set_lock(&result_lock); - if (result > pos) - result = pos; - omp_unset_lock(&result_lock); + thread_index_t num_threads = get_max_threads(); +# pragma omp parallel num_threads(num_threads) + { +# pragma omp single + { + num_threads = omp_get_num_threads(); + borders = new difference_type[num_threads + 1]; + equally_split(length, num_threads, borders); + } //single + + thread_index_t iam = omp_get_thread_num(); + difference_type start = borders[iam], stop = borders[iam + 1]; + + RandomAccessIterator1 i1 = begin1 + start; + RandomAccessIterator2 i2 = begin2 + start; + for (difference_type pos = start; pos < stop; ++pos) + { + #pragma omp flush(result) + // Result has been set to something lower. + if (result < pos) break; - } - i1++; - i2++; - } - } + + if (selector(i1, i2, pred)) + { + omp_set_lock(&result_lock); + if (pos < result) + result = pos; + omp_unset_lock(&result_lock); + break; + } + ++i1; + ++i2; + } + } //parallel omp_destroy_lock(&result_lock); - return std::pair<RandomAccessIterator1, RandomAccessIterator2>(begin1 + result, begin2 + result); + delete[] borders; + + return std::pair<RandomAccessIterator1, RandomAccessIterator2>( + begin1 + result, begin2 + result); } #endif #if _GLIBCXX_FIND_GROWING_BLOCKS - /** - * @brief Parallel std::find, growing block size variant. - * @param begin1 Begin iterator of first sequence. - * @param end1 End iterator of first sequence. - * @param begin2 Begin iterator of second sequence. Second sequence - * must have same length as first sequence. - * @param pred Find predicate. - * @param selector Functionality (e. g. std::find_if (), std::equal(),...) - * @return Place of finding in both sequences. - * @see __gnu_parallel::Settings::find_sequential_search_size - * @see __gnu_parallel::Settings::find_initial_block_size - * @see __gnu_parallel::Settings::find_maximum_block_size - * @see __gnu_parallel::Settings::find_increasing_factor - * - * There are two main differences between the growing blocks and - * the constant-size blocks variants. - * 1. For GB, the block size grows; for CSB, the block size is fixed. - - * 2. For GB, the blocks are allocated dynamically; - * for CSB, the blocks are allocated in a predetermined manner, - * namely spacial round-robin. - */ - template<typename RandomAccessIterator1, typename RandomAccessIterator2, typename Pred, typename Selector> +/** + * @brief Parallel std::find, growing block size variant. + * @param begin1 Begin iterator of first sequence. + * @param end1 End iterator of first sequence. + * @param begin2 Begin iterator of second sequence. Second sequence + * must have same length as first sequence. + * @param pred Find predicate. + * @param selector Functionality (e. g. std::find_if (), std::equal(),...) + * @return Place of finding in both sequences. + * @see __gnu_parallel::Settings::find_sequential_search_size + * @see __gnu_parallel::Settings::find_initial_block_size + * @see __gnu_parallel::Settings::find_maximum_block_size + * @see __gnu_parallel::Settings::find_increasing_factor + * + * There are two main differences between the growing blocks and + * the constant-size blocks variants. + * 1. For GB, the block size grows; for CSB, the block size is fixed. + + * 2. For GB, the blocks are allocated dynamically; + * for CSB, the blocks are allocated in a predetermined manner, + * namely spacial round-robin. + */ +template< + typename RandomAccessIterator1, + typename RandomAccessIterator2, + typename Pred, + typename Selector> std::pair<RandomAccessIterator1, RandomAccessIterator2> find_template(RandomAccessIterator1 begin1, RandomAccessIterator1 end1, - RandomAccessIterator2 begin2, Pred pred, Selector selector, - growing_blocks_tag) + RandomAccessIterator2 begin2, Pred pred, Selector selector, + growing_blocks_tag) { _GLIBCXX_CALL(end1 - begin1) @@ -182,101 +208,118 @@ namespace __gnu_parallel difference_type length = end1 - begin1; - difference_type sequential_search_size = std::min<difference_type>(length, Settings::find_sequential_search_size); + difference_type sequential_search_size = std::min<difference_type>( + length, Settings::find_sequential_search_size); // Try it sequentially first. std::pair<RandomAccessIterator1, RandomAccessIterator2> find_seq_result = - selector.sequential_algorithm(begin1, begin1 + sequential_search_size, begin2, pred); + selector.sequential_algorithm( + begin1, begin1 + sequential_search_size, begin2, pred); if (find_seq_result.first != (begin1 + sequential_search_size)) return find_seq_result; // Index of beginning of next free block (after sequential find). - difference_type next_block_pos = sequential_search_size; + difference_type next_block_start = sequential_search_size; difference_type result = length; - const thread_index_t num_threads = get_max_threads(); omp_lock_t result_lock; omp_init_lock(&result_lock); -#pragma omp parallel shared(result) num_threads(num_threads) - { - // Not within first k elements -> start parallel. - thread_index_t iam = omp_get_thread_num(); - - difference_type block_size = Settings::find_initial_block_size; - difference_type start = fetch_and_add<difference_type>(&next_block_pos, block_size); - - // Get new block, update pointer to next block. - difference_type stop = std::min<difference_type>(length, start + block_size); - - std::pair<RandomAccessIterator1, RandomAccessIterator2> local_result; - - while (start < length) - { -#pragma omp flush(result) - // Get new value of result. - if (result < start) - { - // No chance to find first element. - break; - } - - local_result = selector.sequential_algorithm(begin1 + start, begin1 + stop, begin2 + start, pred); - if (local_result.first != (begin1 + stop)) - { - omp_set_lock(&result_lock); - if ((local_result.first - begin1) < result) - { - result = local_result.first - begin1; - - // Result cannot be in future blocks, stop algorithm. - fetch_and_add<difference_type>(&next_block_pos, length); - } - omp_unset_lock(&result_lock); - } - - block_size = std::min<difference_type>(block_size * Settings::find_increasing_factor, Settings::find_maximum_block_size); - - // Get new block, update pointer to next block. - start = fetch_and_add<difference_type>(&next_block_pos, block_size); - stop = (length < (start + block_size)) ? length : (start + block_size); - } - } + thread_index_t num_threads = get_max_threads(); +# pragma omp parallel shared(result) num_threads(num_threads) + { +# pragma omp single + num_threads = omp_get_num_threads(); + + // Not within first k elements -> start parallel. + thread_index_t iam = omp_get_thread_num(); + + difference_type block_size = Settings::find_initial_block_size; + difference_type start = + fetch_and_add<difference_type>(&next_block_start, block_size); + + // Get new block, update pointer to next block. + difference_type stop = + std::min<difference_type>(length, start + block_size); + + std::pair<RandomAccessIterator1, RandomAccessIterator2> local_result; + + while (start < length) + { +# pragma omp flush(result) + // Get new value of result. + if (result < start) + { + // No chance to find first element. + break; + } + + local_result = selector.sequential_algorithm( + begin1 + start, begin1 + stop, begin2 + start, pred); + if (local_result.first != (begin1 + stop)) + { + omp_set_lock(&result_lock); + if ((local_result.first - begin1) < result) + { + result = local_result.first - begin1; + + // Result cannot be in future blocks, stop algorithm. + fetch_and_add<difference_type>(&next_block_start, length); + } + omp_unset_lock(&result_lock); + } + + block_size = std::min<difference_type>( + block_size * Settings::find_increasing_factor, + Settings::find_maximum_block_size); + + // Get new block, update pointer to next block. + start = + fetch_and_add<difference_type>(&next_block_start, block_size); + stop = (length < (start + block_size)) ? + length : (start + block_size); + } + } //parallel omp_destroy_lock(&result_lock); // Return iterator on found element. - return std::pair<RandomAccessIterator1, RandomAccessIterator2>(begin1 + result, begin2 + result); + return std::pair<RandomAccessIterator1, RandomAccessIterator2>( + begin1 + result, begin2 + result); } #endif #if _GLIBCXX_FIND_CONSTANT_SIZE_BLOCKS - /** - * @brief Parallel std::find, constant block size variant. - * @param begin1 Begin iterator of first sequence. - * @param end1 End iterator of first sequence. - * @param begin2 Begin iterator of second sequence. Second sequence - * must have same length as first sequence. - * @param pred Find predicate. - * @param selector Functionality (e. g. std::find_if (), std::equal(),...) - * @return Place of finding in both sequences. - * @see __gnu_parallel::Settings::find_sequential_search_size - * @see __gnu_parallel::Settings::find_block_size - * There are two main differences between the growing blocks and the - * constant-size blocks variants. - * 1. For GB, the block size grows; for CSB, the block size is fixed. - * 2. For GB, the blocks are allocated dynamically; for CSB, the - * blocks are allocated in a predetermined manner, namely spacial - * round-robin. - */ - template<typename RandomAccessIterator1, typename RandomAccessIterator2, typename Pred, typename Selector> +/** + * @brief Parallel std::find, constant block size variant. + * @param begin1 Begin iterator of first sequence. + * @param end1 End iterator of first sequence. + * @param begin2 Begin iterator of second sequence. Second sequence + * must have same length as first sequence. + * @param pred Find predicate. + * @param selector Functionality (e. g. std::find_if (), std::equal(),...) + * @return Place of finding in both sequences. + * @see __gnu_parallel::Settings::find_sequential_search_size + * @see __gnu_parallel::Settings::find_block_size + * There are two main differences between the growing blocks and the + * constant-size blocks variants. + * 1. For GB, the block size grows; for CSB, the block size is fixed. + * 2. For GB, the blocks are allocated dynamically; for CSB, the + * blocks are allocated in a predetermined manner, namely spacial + * round-robin. + */ +template< + typename RandomAccessIterator1, + typename RandomAccessIterator2, + typename Pred, + typename Selector> std::pair<RandomAccessIterator1, RandomAccessIterator2> find_template(RandomAccessIterator1 begin1, RandomAccessIterator1 end1, - RandomAccessIterator2 begin2, Pred pred, Selector selector, - constant_size_blocks_tag) + RandomAccessIterator2 begin2, Pred pred, Selector selector, + constant_size_blocks_tag) { _GLIBCXX_CALL(end1 - begin1) typedef std::iterator_traits<RandomAccessIterator1> traits_type; @@ -285,72 +328,77 @@ namespace __gnu_parallel difference_type length = end1 - begin1; - difference_type sequential_search_size = std::min<difference_type>(length, Settings::find_sequential_search_size); + difference_type sequential_search_size = std::min<difference_type>( + length, Settings::find_sequential_search_size); // Try it sequentially first. std::pair<RandomAccessIterator1, RandomAccessIterator2> find_seq_result = - selector.sequential_algorithm(begin1, begin1 + sequential_search_size, begin2, pred); + selector.sequential_algorithm(begin1, begin1 + sequential_search_size, + begin2, pred); if (find_seq_result.first != (begin1 + sequential_search_size)) return find_seq_result; difference_type result = length; - const thread_index_t num_threads = get_max_threads(); - omp_lock_t result_lock; omp_init_lock(&result_lock); // Not within first sequential_search_size elements -> start parallel. -#pragma omp parallel shared(result) num_threads(num_threads) - { - thread_index_t iam = omp_get_thread_num(); - difference_type block_size = Settings::find_initial_block_size; - - difference_type start, stop; - - // First element of thread's current iteration. - difference_type iteration_start = sequential_search_size; - - // Where to work (initialization). - start = iteration_start + iam * block_size; - stop = std::min<difference_type>(length, start + block_size); - - std::pair<RandomAccessIterator1, RandomAccessIterator2> local_result; - - while (start < length) - { - // Get new value of result. -#pragma omp flush(result) - // No chance to find first element. - if (result < start) - break; - - local_result = selector.sequential_algorithm(begin1 + start, begin1 + stop, begin2 + start, pred); - if (local_result.first != (begin1 + stop)) - { - omp_set_lock(&result_lock); - if ((local_result.first - begin1) < result) - result = local_result.first - begin1; - omp_unset_lock(&result_lock); - // Will not find better value in its interval. - break; - } - - iteration_start += num_threads * block_size; - - // Where to work. - start = iteration_start + iam * block_size; - stop = std::min<difference_type>(length, start + block_size); - } - } + + thread_index_t num_threads = get_max_threads(); +# pragma omp parallel shared(result) num_threads(num_threads) + { +# pragma omp single + num_threads = omp_get_num_threads(); + + thread_index_t iam = omp_get_thread_num(); + difference_type block_size = Settings::find_initial_block_size; + + // First element of thread's current iteration. + difference_type iteration_start = sequential_search_size; + + // Where to work (initialization). + difference_type start = iteration_start + iam * block_size; + difference_type stop = + std::min<difference_type>(length, start + block_size); + + std::pair<RandomAccessIterator1, RandomAccessIterator2> local_result; + + while (start < length) + { + // Get new value of result. +# pragma omp flush(result) + // No chance to find first element. + if (result < start) + break; + local_result = selector.sequential_algorithm( + begin1 + start, begin1 + stop, + begin2 + start, pred); + if (local_result.first != (begin1 + stop)) + { + omp_set_lock(&result_lock); + if ((local_result.first - begin1) < result) + result = local_result.first - begin1; + omp_unset_lock(&result_lock); + // Will not find better value in its interval. + break; + } + + iteration_start += num_threads * block_size; + + // Where to work. + start = iteration_start + iam * block_size; + stop = std::min<difference_type>(length, start + block_size); + } + } //parallel omp_destroy_lock(&result_lock); // Return iterator on found element. - return std::pair<RandomAccessIterator1, RandomAccessIterator2>(begin1 + result, begin2 + result); + return std::pair<RandomAccessIterator1, RandomAccessIterator2>( + begin1 + result, begin2 + result); } #endif } // end namespace #endif - |