Boost logo

Boost-Commit :

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;
 }


Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk