Subject: [Boost-commit] svn:boost r51366 - sandbox/interthreads/libs/interthreads/example
From: vicente.botet_at_[hidden]
Date: 2009-02-21 12:54:54
Author: viboes
Date: 2009-02-21 12:54:54 EST (Sat, 21 Feb 2009)
New Revision: 51366
URL: http://svn.boost.org/trac/boost/changeset/51366
Log:
0.4.1 : adding parallel-sort example
Added:
sandbox/interthreads/libs/interthreads/example/parallel_sort.cpp (contents, props changed)
Added: sandbox/interthreads/libs/interthreads/example/parallel_sort.cpp
==============================================================================
--- (empty file)
+++ sandbox/interthreads/libs/interthreads/example/parallel_sort.cpp 2009-02-21 12:54:54 EST (Sat, 21 Feb 2009)
@@ -0,0 +1,244 @@
+//////////////////////////////////////////////////////////////////////////////
+//
+// (C) Copyright Vicente J. Botet Escriba 2008-2009.
+// Distributed under the Boost Software License, Version 1.0.
+// (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+//
+// See http://www.boost.org/libs/interthreads for documentation.
+//
+// Based on the shared.cpp example from the threadalert library of Roland Schwarz
+//////////////////////////////////////////////////////////////////////////////
+
+#include <iostream>
+#include <algorithm>
+
+#include <boost/progress.hpp>
+#include <boost/bind.hpp>
+#include <boost/tp/pool.hpp>
+#include <boost/tp/unbounded_channel.hpp>
+#include <boost/tp/fifo.hpp>
+#include <boost/range/algorithm/sort.hpp>
+#include <boost/range/algorithm/inplace_merge.hpp>
+#include <boost/range/sub_range.hpp>
+#include <boost/range/begin.hpp>
+#include <boost/range/end.hpp>
+#include <boost/array.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
+
+template <typename Range, std::size_t Parts>
+class partition
+{
+public:
+ 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));
+ 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[Parts-1]=boost::sub_range<Range>(boost::begin(range)+(Parts-1)*(size/Parts)+1, boost::end(range));
+ }
+};
+
+
+
+#define X_SORT
+#define COUT
+
+#ifdef COUT
+boost::mutex cout_sync;
+#endif
+typedef boost::tp::pool<
+ boost::tp::unbounded_channel< boost::tp::fifo >
+> pool_type;
+
+#ifdef TASK_POOL
+ typedef boost::tp::task< pool_type, void > task_type;
+#else
+ typedef boost::tp::task< void > task_type;
+#endif
+
+
+struct sort_fct {
+ template<class RandomAccessRange>
+ RandomAccessRange& operator()(RandomAccessRange& rng) {
+ return boost::sort(rng);
+ }
+};
+
+struct inplace_merge_fct {
+ template<class BidirectionalRange>
+ BidirectionalRange&
+ operator()( BidirectionalRange& rng,
+ typename boost::range_iterator<BidirectionalRange>::type middle ) {
+ return boost::inplace_merge(rng, middle);
+ }
+};
+
+class x_sort
+{
+private:
+ pool_type & pool_;
+ unsigned cutoff_;
+
+ template <typename Range>
+ void seq_( boost::sub_range<Range>& range)
+ {
+ sort_fct()(range);
+ }
+
+ template <typename Range>
+ void par_( boost::sub_range<Range>& range)
+ {
+ unsigned size = boost::size(range);
+ if ( size <= cutoff_) return seq_( range);
+ else
+ {
+ #if 1
+ #define BOOST_PARTS 2
+ partition<Range, BOOST_PARTS> parts(range);
+ //boost::array<task_type, BOOST_PARTS> tasks;
+ 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]))
+ ));
+ tasks[i] = tmp;
+
+ }
+ this->par_(parts.parts[BOOST_PARTS-1]);
+ for (unsigned i=0;i < BOOST_PARTS-1; ++i) {
+ tasks[i].wait();
+ };
+
+ #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));
+ // fork a new sub-action t1 in pool
+ task_type task(
+ pool_.submit(
+ boost::bind(
+ & x_sort::par_<Range>,
+ boost::ref( * this),
+ boost::ref(left))
+ )
+ );
+
+ this->par_(right);
+ task.wait();
+ #endif
+ inplace_merge_fct()(range, boost::begin(range)+(size/2));
+ }
+ }
+public:
+ x_sort( pool_type & pool, unsigned cutoff)
+ : pool_( pool), cutoff_( cutoff)
+ {}
+
+ 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;
+ }
+};
+
+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);
+}
+
+#define NN 500000
+
+
+int main() {
+ //pool_type ae(boost::tp::poolsize(2));
+ int values[NN];
+
+ for (unsigned i=NN-1; i>0; --i) values[i]=NN-i;
+ std::cout << "std::sort: reverse 0.." << NN << std::endl;
+ {
+ boost::progress_timer t; // start timing
+ std::sort(values, values+NN);
+ }
+
+ for (unsigned i=NN-1; i>0; --i) values[i]=NN-i;
+ std::cout << "boost::sort: reverse 0.."<<NN << std::endl;
+ {
+ boost::progress_timer t; // start timing
+ boost::sort(values);
+ }
+
+ // 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;
+ {
+ boost::progress_timer tmr; // start timing
+ parallel_sort(values, 4000);
+ }
+
+#endif
+
+ for (unsigned i=NN-1; i>0; --i) values[i]=NN-i;
+ std::cout << "parallel_sort 8000: reverse 0.."<<NN << std::endl;
+ {
+ boost::progress_timer tmr; // start timing
+ parallel_sort(values);
+ }
+
+ for (unsigned i=NN-1; i>0; --i) values[i]=NN-i;
+ std::cout << "parallel_sort 16000: reverse 0.."<<NN << std::endl;
+ {
+ boost::progress_timer tmr; // start timing
+ parallel_sort(values, 16000);
+ }
+
+#if 0
+ std::cout << "std::sort: 0.." << NN << std::endl;
+ {
+ boost::progress_timer t; // start timing
+ std::sort(values, values+NN);
+ }
+ std::cout << "boost::sort: 0.."<<NN << std::endl;
+ {
+ boost::progress_timer t; // start timing
+ boost::sort(values);
+ }
+ std::cout << "parallel_sort: 0.."<<NN << std::endl;
+ {
+ boost::progress_timer tmr; // start timing
+ parallel_sort(values);
+ }
+#endif
+
+ pool.shutdown();
+ return 0;
+}