| The Gaudi Framework v27r1

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

- File List
- File Members

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