| The Gaudi Framework v29r1 (5cd95fa2)

- Main Page
- Related Pages
- Modules
- Namespaces
- Classes
- Files

- File List
- File Members

mergesort.cpp
Go to the documentation of this file.
1
16 #include <algorithm>
17 #include <boost/smart_ptr.hpp>
18 #include <boost/thread/mutex.hpp>
19 #include <boost/threadpool.hpp>
20 #include <iostream>
21 #include <sstream>
22
23 using namespace std;
24 using namespace boost::threadpool;
25
26 //
27 // Helpers
28 boost::mutex m_io_monitor;
29
30 void print( string text )
31 {
32 boost::mutex::scoped_lock lock( m_io_monitor );
33 cout << text;
34 }
35
36 template <class T>
37 string to_string( const T& value )
38 {
39 ostringstream ost;
40 ost << value;
41 ost.flush();
42 return ost.str();
43 }
44
45 unsigned long get_ms_diff( boost::xtime& start, boost::xtime& end )
46 {
47 boost::xtime::xtime_sec_t start_ms = start.sec * 1000 + start.nsec / 1000000;
48 boost::xtime::xtime_sec_t end_ms = end.sec * 1000 + end.nsec / 1000000;
49 return static_cast<unsigned long>( end_ms - start_ms );
50 }
51
52 class image
53 {
54 public:
55 image() : m_content( 0 ) {}
56 image( int content ) : m_content( content ) {}
57
58 image( const image& src ) { m_content = src.m_content; }
59
60 bool operator<( const image& l ) const
61 {
62 { // simulate time needed for image comparision
63 boost::xtime xt;
64 boost::xtime_get( &xt, boost::TIME_UTC );
65 int duration = 1 + ( m_content % 4 );
66 xt.nsec += 250 * 1000 * duration;
67 boost::thread::sleep( xt );
68 print( "." );
69 }
70 return m_content < l.m_content;
71 }
72
73 protected:
74 int m_content; // represents image data in this example
75 };
76
77 template <class T>
78 class merge_job
79 {
80 public:
81 merge_job( boost::shared_array<T> data, unsigned int position, unsigned int length )
82 : m_data( data ), m_position( position ), m_length( length )
83 {
84 print( "merge job created : " + to_string( m_position ) + ", " + to_string( m_length ) + "\n" );
85 }
86
87 void run()
88 {
89 print( "merge job running : " + to_string( m_position ) + ", " + to_string( m_length ) + "\n" );
90
91 T* begin = m_data.get();
92 std::advance( begin, m_position );
93
94 T* mid = m_data.get();
95 std::advance( mid, m_position + m_length / 2 );
96
97 T* end = m_data.get();
98 std::advance( end, m_position + m_length );
99
100 std::inplace_merge( begin, mid, end );
101
102 print( "\nmerge job finished: " + to_string( m_position ) + ", " + to_string( m_length ) + "\n" );
103 }
104
105 protected:
106 boost::shared_array<T> m_data;
107 unsigned int m_position;
108 unsigned int m_length;
109 };
110
111 //
112 // A demonstration of the thread_pool class
113 int main( int argc, char* const argv[] )
114 {
115 print( "MAIN: construct thread pool\n" );
116
117 boost::xtime start;
118 boost::xtime_get( &start, boost::TIME_UTC );
119
120 int exponent = 7;
121 int data_len = 1 << exponent; // = pow(2, exponent)
122
123 print( "MAIN: sort array with " + to_string( data_len ) + " elements.\n" );
124
125 boost::shared_array<image> data( new image[data_len] );
126
127 // fill array with arbitrary values (not sorted ascendingly)
128 for ( int i = 0; i < data_len; i++ ) {
129 data[i] = image( ( data_len - i - 1 ) % 23 );
130 }
131
132 /***************************/
133 /* Standard implementation */
134 /***************************/
135
136 pool tp;
137 tp.size_controller().resize( 5 );
138
139 // merge data array
140 for ( int step = 1; step <= exponent; step++ ) {
141 print( "\nMAIN: merge step " + to_string( step ) + "\n" );
142
143 // divide array into partitions
144 int partition_size = 1 << step;
145 for ( int partition = 0; partition < data_len / partition_size; partition++ ) {
146 // sort partition
147 boost::shared_ptr<merge_job<image>> job(
148 new merge_job<image>( data, partition * partition_size, partition_size ) );
149 // tp->schedule(prio_task_func(5, boost::bind(&merge_job<image>::run, job)));
150 schedule( tp, boost::bind( &merge_job<image>::run, job ) );
151 // schedule(tp, job);
152 }
153 tp.wait(); // wait until all partitions are sorted
154 }
155
156 boost::xtime end;
157 boost::xtime_get( &end, boost::TIME_UTC );
158
159 print( "\nMAIN: duration " + to_string( get_ms_diff( start, end ) ) + " ms \n" );
160
161 print( "\nMAIN: check if array is sorted... \n" );
162
163 // check if array is sorted ascendingly
164 bool ascending = true;
165 for ( int i = 0; i < data_len - 1; i++ ) {
166 if ( data[i + 1] < data[i] ) {
167 ascending = false;
168 }
169 }
170
171 if ( ascending ) {
172 print( "\nMAIN: array is sorted\n" );
173 } else {
174 print( "\nMAIN: array is NOT sorted!\n" );
175 }
176
177 return 0;
178 }
image::image
image(const image &src)
Definition: mergesort.cpp:58
boost::threadpool::thread_pool::wait
void wait(size_t task_threshold=0) const
The current thread of execution is blocked until the sum of all active and pending tasks is equal or ...
Definition: pool.hpp:176
merge_job::run
void run()
Definition: mergesort.cpp:87
merge_job::m_position
unsigned int m_position
Definition: mergesort.cpp:107
merge_job::merge_job
merge_job(boost::shared_array< T > data, unsigned int position, unsigned int length)
Definition: mergesort.cpp:81
std::inplace_merge
T inplace_merge(T...args)
merge_job
Definition: mergesort.cpp:78
merge_job::m_length
unsigned int m_length
Definition: mergesort.cpp:108
image::image
image(int content)
Definition: mergesort.cpp:56
main
int main(int argc, char *const argv[])
Definition: mergesort.cpp:113
gaudirun.argv
list argv
Definition: gaudirun.py:235
std::advance
T advance(T...args)
get_ms_diff
unsigned long get_ms_diff(boost::xtime &start, boost::xtime &end)
Definition: mergesort.cpp:45
std::to_string
T to_string(T...args)
std
STL namespace.
image
Definition: mergesort.cpp:52
std::end
T end(T...args)
image::m_content
int m_content
Definition: mergesort.cpp:74
std::partition
T partition(T...args)
image::image
image()
Definition: mergesort.cpp:55
image::operator<
bool operator<(const image &l) const
Definition: mergesort.cpp:60
pool
Definition: PoolClasses.h:11
merge_job::m_data
boost::shared_array< T > m_data
Definition: mergesort.cpp:106
boost::threadpool::schedule
disable_if< is_void< typename result_of< Function() >::type >, future< typename result_of< Function() >::type >>::type schedule(Pool &pool, const Function &task)
Definition: future.hpp:111
std::ostringstream
STL class.
compareRootHistos.tp
tuple tp
Definition: compareRootHistos.py:417
std::lock
T lock(T...args)
IOTest.start
start
Definition: IOTest.py:99
std::ostringstream::str
T str(T...args)
boost::threadpool::thread_pool::size_controller
size_controller_type size_controller()
Gets the size controller which manages the number of threads in the pool.
Definition: pool.hpp:111
boost::threadpool
Definition: future.hpp:32
gaudirun.l
dictionary l
Definition: gaudirun.py:440
m_io_monitor
boost::mutex m_io_monitor
Definition: mergesort.cpp:28
plotBacklogPyRoot.argc
argc
Definition: plotBacklogPyRoot.py:138
std::ostringstream::flush
T flush(T...args)
std::begin
T begin(T...args)
print
void print(string text)
Definition: mergesort.cpp:30
std::cout
threadpool.hpp
Main include.