From patchwork Mon Jan 24 17:07:44 2011 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Johannes Singler X-Patchwork-Id: 80218 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) by ozlabs.org (Postfix) with SMTP id D571C1007D1 for ; Tue, 25 Jan 2011 04:08:03 +1100 (EST) Received: (qmail 17438 invoked by alias); 24 Jan 2011 17:08:00 -0000 Received: (qmail 17419 invoked by uid 22791); 24 Jan 2011 17:07:58 -0000 X-SWARE-Spam-Status: No, hits=-1.9 required=5.0 tests=AWL,BAYES_00 X-Spam-Check-By: sourceware.org Received: from iramx2.ira.uni-karlsruhe.de (HELO iramx2.ira.uni-karlsruhe.de) (141.3.10.81) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Mon, 24 Jan 2011 17:07:53 +0000 Received: from irams1.ira.uni-karlsruhe.de ([141.3.10.5]) by iramx2.ira.uni-karlsruhe.de with esmtps port 25 id 1PhPtI-0007dT-U7; Mon, 24 Jan 2011 18:07:51 +0100 Received: from i10pc67.iti.kit.edu ([141.3.24.67]) by irams1.ira.uni-karlsruhe.de with esmtps port 465 id 1PhPtI-0006V8-QL; Mon, 24 Jan 2011 18:07:44 +0100 Message-ID: <4D3DB1E0.5010008@kit.edu> Date: Mon, 24 Jan 2011 18:07:44 +0100 From: Johannes Singler User-Agent: Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv:1.9.2.9) Gecko/20100914 SUSE/3.1.4 Thunderbird/3.1.4 MIME-Version: 1.0 To: libstdc++ , gcc-patches@gcc.gnu.org Subject: [PATCH][libstdc++-v3 parallel mode] Enable user-defined swap X-ATIS-AV: ClamAV (irams1.ira.uni-karlsruhe.de) X-ATIS-AV: ClamAV (iramx2.ira.uni-karlsruhe.de) X-ATIS-AV: Kaspersky (iramx2.ira.uni-karlsruhe.de) X-ATIS-Timestamp: iramx2.ira.uni-karlsruhe.de 1295888871.142485000 X-IsSubscribed: yes Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org The following patch enables user-defined swap for parallel sorting and the like, which can improve performance. Tested x86_64-unknown-linux-gnu: No regressions Pre-approved for mainline. Also commit to gcc-4_5-branch? 2011-01-24 Johannes Singler PR libstdc++/47433 * include/parallel/losertree.h (_LoserTree<>::__delete_min_insert): Do not qualify swap with std:: for value type, but include a using directive instead. (_LoserTreeUnguarded<>::__delete_min_insert): Likewise. * include/parallel/balanced_quicksort.h (__qsb_divide): Use std::iter_swap instead of std::swap. (__qsb_local_sort_with_helping): Likewise. * include/parallel/partition.h (__parallel_partition): Likewise. (__parallel_nth_element): Likewise. Johannes Index: include/parallel/losertree.h =================================================================== --- include/parallel/losertree.h (revision 169160) +++ include/parallel/losertree.h (working copy) @@ -216,6 +216,7 @@ void __delete_min_insert(_Tp __key, bool __sup) { + using std::swap; #if _GLIBCXX_ASSERTIONS // no dummy sequence can ever be at the top! _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1); @@ -236,7 +237,7 @@ // The other one is smaller. std::swap(_M_losers[__pos]._M_sup, __sup); std::swap(_M_losers[__pos]._M_source, __source); - std::swap(_M_losers[__pos]._M_key, __key); + swap(_M_losers[__pos]._M_key, __key); } } @@ -316,6 +317,7 @@ void __delete_min_insert(_Tp __key, bool __sup) { + using std::swap; #if _GLIBCXX_ASSERTIONS // no dummy sequence can ever be at the top! _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1); @@ -332,7 +334,7 @@ // The other one is smaller. std::swap(_M_losers[__pos]._M_sup, __sup); std::swap(_M_losers[__pos]._M_source, __source); - std::swap(_M_losers[__pos]._M_key, __key); + swap(_M_losers[__pos]._M_key, __key); } } @@ -679,6 +681,7 @@ void __delete_min_insert(_Tp __key, bool) { + using std::swap; #if _GLIBCXX_ASSERTIONS // no dummy sequence can ever be at the top! _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1); @@ -695,7 +698,7 @@ { // The other one is smaller. std::swap(_M_losers[__pos]._M_source, __source); - std::swap(_M_losers[__pos]._M_key, __key); + swap(_M_losers[__pos]._M_key, __key); } } @@ -786,7 +789,7 @@ { // The other one is smaller. std::swap(_M_losers[__pos]._M_source, __source); - std::swap(_M_losers[__pos]._M_key, __key); + swap(_M_losers[__pos]._M_key, __key); } } Index: include/parallel/balanced_quicksort.h =================================================================== --- include/parallel/balanced_quicksort.h (revision 169160) +++ include/parallel/balanced_quicksort.h (working copy) @@ -132,7 +132,7 @@ // Swap pivot value to end. if (__pivot_pos != (__end - 1)) - std::swap(*__pivot_pos, *(__end - 1)); + std::iter_swap(__pivot_pos, __end - 1); __pivot_pos = __end - 1; __gnu_parallel::__binder2nd<_Compare, _ValueType, _ValueType, bool> @@ -144,7 +144,7 @@ __num_threads); // Swap back pivot to middle. - std::swap(*(__begin + __split_pos), *__pivot_pos); + std::iter_swap(__begin + __split_pos, __pivot_pos); __pivot_pos = __begin + __split_pos; #if _GLIBCXX_ASSERTIONS @@ -284,7 +284,7 @@ // Swap __pivot_pos value to end. if (__pivot_pos != (__end - 1)) - std::swap(*__pivot_pos, *(__end - 1)); + std::iter_swap(__pivot_pos, __end - 1); __pivot_pos = __end - 1; __gnu_parallel::__binder2nd @@ -303,7 +303,7 @@ #endif // Swap pivot back to middle. if (__split_pos1 != __pivot_pos) - std::swap(*__split_pos1, *__pivot_pos); + std::iter_swap(__split_pos1, __pivot_pos); __pivot_pos = __split_pos1; // In case all elements are equal, __split_pos1 == 0. Index: include/parallel/partition.h =================================================================== --- include/parallel/partition.h (revision 169160) +++ include/parallel/partition.h (working copy) @@ -178,8 +178,8 @@ // Fetch new chunk(__s). break; - std::swap(__begin[__thread_left], - __begin[__thread_right]); + std::iter_swap(__begin + __thread_left, + __begin + __thread_right); ++__thread_left; --__thread_right; } @@ -301,7 +301,7 @@ if (__final_left == __final_right) break; - std::swap(__begin[__final_left], __begin[__final_right]); + std::iter_swap(__begin + __final_left, __begin + __final_right); ++__final_left; --__final_right; } @@ -354,7 +354,7 @@ // Swap __pivot_pos value to end. if (__pivot_pos != (__end - 1)) - std::swap(*__pivot_pos, *(__end - 1)); + std::iter_swap(__pivot_pos, __end - 1); __pivot_pos = __end - 1; // _Compare must have first_value_type, second_value_type, @@ -376,7 +376,7 @@ // Swap pivot back to middle. if (__split_pos1 != __pivot_pos) - std::swap(*__split_pos1, *__pivot_pos); + std::iter_swap(__split_pos1, __pivot_pos); __pivot_pos = __split_pos1; // In case all elements are equal, __split_pos1 == 0