Patchwork [libstdc++-v3,parallel,mode] Enable user-defined swap

login
register
mail settings
Submitter Johannes Singler
Date Jan. 24, 2011, 5:07 p.m.
Message ID <4D3DB1E0.5010008@kit.edu>
Download mbox | patch
Permalink /patch/80218/
State New
Headers show

Comments

Johannes Singler - Jan. 24, 2011, 5:07 p.m.
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  <singler@kit.edu>

         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
Paolo Carlini - Jan. 24, 2011, 5:13 p.m.
Hi,
> 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?
Seem safe enough. But let's do it in a couple of weeks.

Thanks,
Paolo.
Benjamin Kosnik - Jan. 24, 2011, 6:12 p.m.
> Also commit to gcc-4_5-branch?

Ok.

-benjamin

Patch

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