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