From 22a2af9556ba56f66109830ee63b0ee7544ecc74 Mon Sep 17 00:00:00 2001 From: Johannes Singler Date: Tue, 8 Jun 2010 16:50:05 +0000 Subject: [PATCH] 2010-06-08 Johannes Singler * include/parallel/find.h (__find_template(.., growing_blocks_tag)): Make block size proportional to current position. * include/parallel/settings.h (_Settings): Introduce new tuning parameter find_scale_factor to the end of the struct, defaults to 0.01f. From-SVN: r160439 --- libstdc++-v3/ChangeLog | 9 +++++++++ libstdc++-v3/include/parallel/find.h | 18 +++++++++--------- libstdc++-v3/include/parallel/settings.h | 6 +++++- 3 files changed, 23 insertions(+), 10 deletions(-) diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index 3ebfd13bac37..aa2e5bda671c 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,12 @@ +2010-06-08 Johannes Singler + + * include/parallel/find.h + (__find_template(.., growing_blocks_tag)): Make block size + proportional to current position. + * include/parallel/settings.h (_Settings): Introduce new tuning + parameter find_scale_factor to the end of the struct, defaults to + 0.01f. + 2010-06-08 Johannes Singler * include/parallel/partial_sum.h diff --git a/libstdc++-v3/include/parallel/find.h b/libstdc++-v3/include/parallel/find.h index b4e581488ae3..eb37d8aace18 100644 --- a/libstdc++-v3/include/parallel/find.h +++ b/libstdc++-v3/include/parallel/find.h @@ -168,9 +168,7 @@ namespace __gnu_parallel * @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 + * @see __gnu_parallel::_Settings::find_scale_factor * * There are two main differences between the growing blocks and * the constant-size blocks variants. @@ -218,6 +216,8 @@ namespace __gnu_parallel omp_lock_t __result_lock; omp_init_lock(&__result_lock); + const float __scale_factor = __s.find_scale_factor; + _ThreadIndex __num_threads = __get_max_threads(); # pragma omp parallel shared(__result) num_threads(__num_threads) { @@ -227,7 +227,8 @@ namespace __gnu_parallel // Not within first __k elements -> start parallel. _ThreadIndex __iam = omp_get_thread_num(); - _DifferenceType __block_size = __s.find_initial_block_size; + _DifferenceType __block_size = + std::max<_DifferenceType>(1, __scale_factor * __next_block_start); _DifferenceType __start = __fetch_and_add<_DifferenceType> (&__next_block_start, __block_size); @@ -265,15 +266,14 @@ namespace __gnu_parallel omp_unset_lock(&__result_lock); } - __block_size = std::min<_DifferenceType> - (__block_size * __s.find_increasing_factor, - __s.find_maximum_block_size); + _DifferenceType __block_size = + std::max<_DifferenceType>(1, __scale_factor * __next_block_start); // Get new block, update pointer to next block. __start = __fetch_and_add<_DifferenceType>(&__next_block_start, __block_size); - __stop = (__length < (__start + __block_size) - ? __length : (__start + __block_size)); + __stop = + std::min<_DifferenceType>(__length, __start + __block_size); } } //parallel diff --git a/libstdc++-v3/include/parallel/settings.h b/libstdc++-v3/include/parallel/settings.h index 3b326ff8e474..5d00b0269444 100644 --- a/libstdc++-v3/include/parallel/settings.h +++ b/libstdc++-v3/include/parallel/settings.h @@ -272,6 +272,9 @@ namespace __gnu_parallel /// Minimal input size for search and search_n. _SequenceIndex search_minimal_n; + /// Block size scale-down factor with respect to current position. + float find_scale_factor; + /// Get the global settings. _GLIBCXX_CONST static const _Settings& get() throw(); @@ -331,7 +334,8 @@ namespace __gnu_parallel TLB_size(128), cache_line_size(64), qsb_steals(0), - search_minimal_n(1000) + search_minimal_n(1000), + find_scale_factor(0.01f) { } }; } -- 2.43.5