[Boost-commit] svn:boost r51399 - sandbox/interthreads/libs/interthreads/example

Subject: [Boost-commit] svn:boost r51399 - sandbox/interthreads/libs/interthreads/example
From: vicente.botet_at_[hidden]
Date: 2009-02-22 18:06:01

Author: viboes
Date: 2009-02-22 18:06:00 EST (Sun, 22 Feb 2009)
New Revision: 51399
URL: http://svn.boost.org/trac/boost/changeset/51399

Log:
0.4.1 : adding parallel-sort example

Text files modified: 
   sandbox/interthreads/libs/interthreads/example/parallel_sort.cpp |   231 ++++++++++++++++++++++++++++----------- 
   1 files changed, 163 insertions(+), 68 deletions(-)

Modified: sandbox/interthreads/libs/interthreads/example/parallel_sort.cpp
==============================================================================
--- sandbox/interthreads/libs/interthreads/example/parallel_sort.cpp	(original)
+++ sandbox/interthreads/libs/interthreads/example/parallel_sort.cpp	2009-02-22 18:06:00 EST (Sun, 22 Feb 2009)
@@ -13,6 +13,7 @@
 #include <algorithm>
 
 #include <boost/progress.hpp>
+#include <boost/thread/thread.hpp>
 #include <boost/bind.hpp>
 #include <boost/tp/pool.hpp>
 #include <boost/tp/unbounded_channel.hpp>
@@ -23,48 +24,45 @@
 #include <boost/range/begin.hpp>
 #include <boost/range/end.hpp>
 #include <boost/array.hpp>
+#include <boost/range/algorithm/equal.hpp>
+#include <boost/range/adaptor/sliced.hpp>
 
-template <typename Range, std::size_t Parts>
-class partition;
-
-#if 0
-template <typename Range>
-class partition<Range,2>
-{
-        boost::sub_range<Range> p0;
-        boost::sub_range<Range> p1;
-public:
-    partition(Range& range):
-        : p0(boost::begin(range), boost::begin(range)+(size/2))
-        , p1(boost::begin(range)+(size/2)+1, boost::end(range))
-    {}
-};
-
-#endif
+#include <assert.h>
 
+#define STAT
+#ifdef STAT
 template <typename Range, std::size_t Parts>
 class partition
 {
 public:
-    boost::array<boost::sub_range<Range>,Parts> parts;
+    boost::array<boost::sub_range<Range>,Parts> parts_;
     partition(boost::sub_range<Range>& range)
     {
         std::size_t size = boost::size(range);
-        parts[0]=boost::sub_range<Range>(boost::begin(range), boost::begin(range)+(size/Parts));
+        parts_[0]=boost::sub_range<Range>(boost::begin(range), boost::begin(range)+(size/Parts));
         for (std::size_t i=1; i< Parts-1; ++i) {
-            parts[i]=boost::sub_range<Range>(boost::begin(range)+i*(size/Parts)+1, boost::begin(range)+(i+1)*(size/Parts)+1);
+            parts_[i]=boost::sub_range<Range>(boost::begin(range)+i*(size/Parts), boost::begin(range)+(i+1)*(size/Parts));
         }
-        parts[Parts-1]=boost::sub_range<Range>(boost::begin(range)+(Parts-1)*(size/Parts)+1, boost::end(range));
+        parts_[Parts-1]=boost::sub_range<Range>(boost::begin(range)+(Parts-1)*(size/Parts), boost::end(range));
+    }
+    boost::sub_range<Range>& operator[](unsigned i) {
+        return parts_[i];
+    }
+};
+#else
+template <typename Range>
+class partition
+{
+    boost::sub_range<Range> range_;
+    std::size_t parts_;
+public:
+    partition(boost::sub_range<Range>& range, std::size_t parts) : range_(range), parts_() {}
+    boost::sub_range<Range> operator[](unsigned i) {
+        std::size_t size = boost::size(range_);
+        if (i==parts_ - 1)  return boost::sub_range<Range>(boost::begin(range_)+i*(size/parts_), boost::end(range_));
+        else              return boost::sub_range<Range>(boost::begin(range_)+i*(size/parts_), boost::begin(range_)+((i+1)*(size/parts_)));
     }
 };
-
-
-
-#define X_SORT
-#define COUT
-
-#ifdef COUT
-boost::mutex cout_sync;
 #endif
 typedef boost::tp::pool<
   boost::tp::unbounded_channel< boost::tp::fifo >
@@ -76,7 +74,6 @@
         typedef boost::tp::task< void > task_type;
 #endif
 
-
 struct sort_fct {
     template<class RandomAccessRange>
     RandomAccessRange& operator()(RandomAccessRange& rng) {
@@ -100,41 +97,62 @@
   unsigned    cutoff_;
 
   template <typename Range>
+#ifdef STAT
   void seq_( boost::sub_range<Range>& range)
+#else
+  void seq_( boost::iterator_range<typename boost::range_iterator<Range>::type> range)
+#endif
   {
     sort_fct()(range);
   }
 
   template <typename Range>
+#ifdef STAT
   void par_( boost::sub_range<Range>& range)
+#else
+  void par_( boost::iterator_range<typename boost::range_iterator<Range>::type> range)
+#endif
   {
     unsigned size = boost::size(range);
-    if ( size <= cutoff_) return seq_( range);
+    //std::cout << "<<par_ " << size << std::endl;  
+    if ( size <= cutoff_) return seq_<Range>( range);
     else
     {
-        #if 1
+#if 1
         #define BOOST_PARTS 2
+#ifdef STAT
         partition<Range, BOOST_PARTS> parts(range);
-        //boost::array<task_type, BOOST_PARTS> tasks;
+#else
+//        partition<Range> parts(range, BOOST_PARTS);
+#endif
         task_type tasks[BOOST_PARTS];
         for (unsigned i=0;i < BOOST_PARTS-1; ++i) {
             task_type tmp(pool_.submit(
                 boost::bind(
                     & x_sort::par_<Range>,
                     boost::ref( * this),
-                    boost::ref(parts.parts[i]))
-            ));
+#ifdef STAT
+                    boost::ref(parts[i])
+#else
+                    boost::make_sliced_range(range, i*(size/BOOST_PARTS), ((i+1)*(size/BOOST_PARTS)))
+#endif
+            )));
             tasks[i] = tmp;
 
         }
-        this->par_(parts.parts[BOOST_PARTS-1]);
+#ifdef STAT
+        this->par_(parts[BOOST_PARTS-1]);
+#else
+        //this->par_(parts[BOOST_PARTS-1]);
+        this->par_<Range>(boost::make_sliced_range(range, (BOOST_PARTS-1)*(size/BOOST_PARTS), size));
+#endif
         for (unsigned i=0;i < BOOST_PARTS-1; ++i) {
             tasks[i].wait();
         };
         
-        #else
+#else
         boost::sub_range<Range> left(boost::begin(range), boost::begin(range)+(size/2));
-        boost::sub_range<Range> right(boost::begin(range)+(size/2)+1, boost::end(range));
+        boost::sub_range<Range> right(boost::begin(range)+(size/2), boost::end(range));
         // fork a new sub-action t1 in pool
         task_type task(
             pool_.submit(
@@ -145,10 +163,13 @@
             )
         );
 
-        this->par_(right);
+        this->par_<Range>(right);
         task.wait();
-        #endif
+#endif
+    //std::cout << "par_inplace_merge_fct " << size << ">>"<< std::endl;  
         inplace_merge_fct()(range, boost::begin(range)+(size/2));
+    //std::cout << "par_ " << size << ">>"<< std::endl;  
+        
     }
   }
 public:
@@ -157,71 +178,83 @@
   {}
 
   template <typename Range>
-  void execute( boost::sub_range<Range>& n)
-  {
-        //std::cout << "execute("<<boost::size(n)<<") >>" << std::endl;
-    par_( n);
-        //std::cout << "execute("<<boost::size(n)<<") >>" << std::endl;
+  void execute( Range& range) {
+#ifdef STAT
+    boost::sub_range<Range> rng(boost::begin(range), boost::end(range));
+#else
+    boost::iterator_range<typename boost::range_iterator<Range>::type> rng(range);
+#endif    
+    par_<Range>( rng);
   }
 };
 
 template <typename Range>
 void parallel_sort(Range& range, unsigned cutoff=10000) {
     pool_type pool( boost::tp::poolsize( 2) );
-    boost::sub_range<Range> rng(boost::begin(range), boost::end(range));
     x_sort fct( pool, cutoff);
-    fct.execute(rng);
+    fct.execute(range);
+    std::cout << "parallel_sort " << ">>"<< std::endl;  
 }
 
-#define NN 500000
-
+#define NN 1000000
+int sorted[NN];
+int values1[NN];
+int values2[NN];
+int values3[NN];
+int values4[NN];
+int values5[NN];
+int values6[NN];
 
 int main() {
     //pool_type ae(boost::tp::poolsize(2));
-    int values[NN];
+    for (unsigned i=0; i<NN; ++i) sorted[i]=i;
 
-    for (unsigned i=NN-1; i>0; --i) values[i]=NN-i;
-    std::cout << "std::sort: reverse 0.." << NN << std::endl;
+    
+   
+    for (unsigned i=0; i<NN; ++i) values1[i]=NN-i-1;
     {
+    std::cout << "std::sort: reverse 0.." << NN << std::endl;
     boost::progress_timer t;  // start timing
-    std::sort(values, values+NN);
+    std::sort(boost::begin(values1), boost::end(values1));
     }
+    assert(boost::equal(values1, sorted));
     
-    for (unsigned i=NN-1; i>0; --i) values[i]=NN-i;
-    std::cout << "boost::sort: reverse 0.."<<NN << std::endl;
+    for (unsigned i=0; i<NN; ++i) values2[i]=NN-i-1;
     {
+    std::cout << "boost::sort: reverse 0.."<<NN << std::endl;
     boost::progress_timer t;  // start timing
-    boost::sort(values);
+    boost::sort(values2);
     }
+    assert(boost::equal(values2, sorted));
 
     // creates a threadpool with two worker-threads
     pool_type pool( boost::tp::poolsize( 2) );
 
-#if 0
-    for (unsigned i=NN-1; i>0; --i) values[i]=NN-i;
-    std::cout << "parallel_sort 4000:  reverse 0.."<<NN << std::endl;
+
+    for (unsigned i=0; i<NN; ++i) values3[i]=NN-i-1;
+    std::cout << "parallel_sort "<<NN/16<<":  reverse 0.."<<NN << std::endl;
     {
     boost::progress_timer tmr;  // start timing
-    parallel_sort(values, 4000);
+    parallel_sort(values3, NN/16);
     }
     
-#endif
+    //for (unsigned i=0; i<NN; ++i) std::cout << sorted[i] << " " <<values3[i] << std::endl;
+    assert(boost::equal(values3, sorted));
 
-    for (unsigned i=NN-1; i>0; --i) values[i]=NN-i;
+#if 0
+    for (unsigned i=0; i<NN; ++i) values3[i]=NN-i-1;
     std::cout << "parallel_sort 8000:  reverse 0.."<<NN << std::endl;
     {
     boost::progress_timer tmr;  // start timing
-    parallel_sort(values);
+    parallel_sort(values3);
     }
-
-    for (unsigned i=NN-1; i>0; --i) values[i]=NN-i;
-    std::cout << "parallel_sort 16000:  reverse 0.."<<NN << std::endl;
+    for (unsigned i=0; i<NN; ++i) values[i]=NN-i-1;
+    std::cout << "parallel_sort 4000:  reverse 0.."<<NN << std::endl;
     {
     boost::progress_timer tmr;  // start timing
-    parallel_sort(values, 16000);
+    parallel_sort(values, 4000);
     }
     
-#if 0
     std::cout << "std::sort: 0.." << NN << std::endl;
     {
     boost::progress_timer t;  // start timing
@@ -238,7 +271,69 @@
     parallel_sort(values);
     }
 #endif
+
+    for (unsigned i=0; i<NN; ++i) values4[i]=NN-i-1;
+    {
+    std::cout << "std::sort: reverse 0.." << NN << std::endl;
+    boost::progress_timer t;  // start timing
+    std::sort(boost::begin(values4), boost::end(values4));
+    }
+    assert(boost::equal(values4, sorted));
     
+    for (unsigned i=0; i<NN; ++i) values5[i]=NN-i-1;
+    std::cout << "parallel_sort "<<NN/16<<":  reverse 0.."<<NN << std::endl;
+    {
+    boost::progress_timer tmr;  // start timing
+    parallel_sort(values5, NN/16);
+    }
+    
+    //for (unsigned i=0; i<NN; ++i) std::cout << sorted[i] << " " <<values3[i] << std::endl;
+    assert(boost::equal(values5, sorted));
+
+    for (unsigned i=0; i<NN; ++i) values6[i]=NN-i-1;
+    std::cout << "parallel_sort "<<NN/16<<":  reverse 0.."<<NN << std::endl;
+    {
+    boost::progress_timer tmr;  // start timing
+    parallel_sort(values6, NN/16);
+    }
+    
+    //for (unsigned i=0; i<NN; ++i) std::cout << sorted[i] << " " <<values3[i] << std::endl;
+    assert(boost::equal(values6, sorted));
+
+    for (unsigned i=0; i<NN; ++i) values1[i]=NN-i-1;
+    std::cout << "parallel_sort "<<NN/16<<":  reverse 0.."<<NN << std::endl;
+    {
+    boost::progress_timer tmr;  // start timing
+    parallel_sort(values1, NN/16);
+    }
+    
+    //for (unsigned i=0; i<NN; ++i) std::cout << sorted[i] << " " <<values3[i] << std::endl;
+    assert(boost::equal(values1, sorted));
+    
+#if 0
+    for (unsigned i=0; i<NN; ++i) values[i]=NN-i-1;
+    {
+    std::cout << "boost::sort: reverse 0.."<<NN << std::endl;
+    boost::progress_timer t;  // start timing
+    boost::sort(values);
+    }
+    assert(boost::equal(values, sorted));
+    
+    for (unsigned i=0; i<NN; ++i) values[i]=NN-i-1;
+    std::cout << "parallel_sort "<<NN/32<<":  reverse 0.."<<NN << std::endl;
+    {
+    boost::progress_timer tmr;  // start timing
+    parallel_sort(values, NN/32);
+    }
+    
+    //for (unsigned i=0; i<NN; ++i) std::cout << sorted[i] << " " <<values[i] << std::endl;
+    assert(boost::equal(values, sorted));
+    //std::cout << "sleep"<<std::endl;
+#endif    
+
+    //boost::this_thread::sleep(boost::posix_time::milliseconds(5000));
+    std::cout << "shutdown"<< std::endl;
     pool.shutdown();
+    std::cout << "end"<< std::endl;
     return 0;
 }