Archive for August, 2006|Monthly archive page

Futures again

To see how useful the previously described future is, I tried to retrofit some existing code. Here are some lines of test code before futures came in:

 1 obc::image orig(filename);
 2 obc::image img = obc::rgb2gray(orig);
 4 obc::show_image(img, "original");
 5 obc::show_image(obc::contrast_incr(img, 0.15), "contrast_incr");
 7 timespec timer_s, timer_e;
 8 clock_gettime(CLOCK_REALTIME, &timer_s);
10 CvSeq* lines = obc::hough_transform(img);
12 obc::image temp(img);
13 obc::image disp = obc::gray2rgb(temp);
14 obc::draw_hough_lines(disp, lines);
16 clock_gettime(CLOCK_REALTIME, &timer_e);
17 cout << "elapsed time = " << (time_diff(timer_s, timer_e) / 1000000.0) << endl;
19 obc::show_image(disp, "result");
21 cvReleaseMemStorage(&lines->storage);

The calculation of the Hough transform (line 10) takes a while so considering that each show_image() function needs user feedback which is quite slow it would make sense to trigger the calculation of the transform before the available images are shown. Thus line 5 in the code sample below contains the future that calculates asynchronously the Hough transform while we look at the images presented to us in the show_image() functions.

 1 obc::image orig(filename);
 2 obc::image img = obc::rgb2gray(orig);
 4 obc::image contr = obc::contrast_incr(img, 0.15);
 5 concur::future<CvSeq*> lines_f(bind(obc::hough_transform, img));
 7 obc::show_image(img, "original");
 8 obc::show_image(contr, "contrast_incr");
10 timespec timer_s, timer_e;
11 clock_gettime(CLOCK_REALTIME, &timer_s);
13 obc::image temp(img);
14 obc::image disp = obc::gray2rgb(temp);
15 obc::draw_hough_lines(disp, lines_f());
17 clock_gettime(CLOCK_REALTIME, &timer_e);
18 cout << "elapsed time = " << (time_diff(timer_s, timer_e) / 1000000.0) << endl;
20 obc::show_image(disp, "result");
22 cvReleaseMemStorage(&lines_f()->storage);

Now you may have recognized the little timing code and it comes as no surprise that the gains are significant. The old version takes about 2.8 seconds whereas the new one uses only 0.4 seconds for the covered code paths. A little reordering and renaming and voila – a nice result.


C++0x articles has some nice articles about what to expect from C++0x. Interesting read. I also noticed that Pete Becker wrote a book about the TR1 standard library additions. Just ordered my copy from Amazon. Luckily, even tough C++ standardization takes quite a long time, most of the proposed changes are available from Boost (where many of them were initially created) or they even found their way into mainstream compilers already.

C++ Futures

Recently I learnt about Alice, a dialect of Standard ML and thus a mostly functional language. What Alice adds to ML is excellent support for high-level concurrency primitives such as Futures.

A Future is a mechanism which can be used to provide values that will be resolved to another value asynchronously. Futures can also be called “promises” (see PromisePipelining). A method/function can return a future to its caller, and continue to compute the value that the future will resolve to in another thread of control […]” Wiki

Alice’s syntax for futures is especially pleasing. To give an example, an expression like ‘spawn exp;‘ would evaluate ‘exp’ asynchronously in a new thread and return immediately. Requesting the value of ‘exp’ results in implicit synchronization with the thread evaluating the result until completed. Later invocations return the result directly.

Alice is not the only language supporting futures. Even Java version 1.5 got a FutureTask although the usual restrictions of Java apply here too.

I could not find an implementation of a future for C++ maybe because multithreading is not standardized yet. However it is not difficult to implement one. I will use Boost.Threads as the underlying threading framework, but other libraries are just as good for this particular task.

Please note that the definition of futures does not specify if the computation of the given expression would start immediately or only when the result is requested the first time. I let the evaluation begin on future creation but an explicit start function could be added easily.

Now here is the complete future implementation (Did I mention than Vim‘s HTML export is really handy?):

 1 #ifndef FUTURE_HPP
 2 #define FUTURE_HPP
 4 #include <tr1/functional>
 5 #include <boost/bind.hpp>
 6 #include <boost/utility.hpp>
 7 #include <boost/thread/mutex.hpp>
 8 #include <boost/thread/thread.hpp>
10 using std::tr1::function;
11 using boost::thread;
12 using boost::mutex;
14 template<typename T>
15 class future : boost::noncopyable
16 {
17 public:
18         future(function<T ()> const & f);
19         T operator()();
21 private:
22         void run();
24         T v_;
25         function<T ()> f_;
26         thread t_;
27         mutex m_;
28         bool joined_;
29 };
31 template<typename T>
32 future<T>::future(function<T ()> const & f)
33 : v_(), f_(f), t_(boost::bind(&future<T>::run, this)), joined_(false) {}
35 template<typename T>
36 T future<T>::operator()()
37 {
38         mutex::scoped_lock lock(m_);
39         if (!joined_) {
40                 t_.join();
41                 joined_ = true;
42         }
43         return v_;
44 }
46 template<typename T>
47 void future<T>::run()
48 {
49         v_ = f_();
50 }
52 #endif // FUTURE_HPP

I think the code is reasonably clear. We take a tr1::function and immediately start a thread evaluating the function. Now it should be obvious that the expressive power of this future is not as high as Alice’s since we can only evaluate functions, member functions or functors (classes that overload operator()()) and not simple expressions like 2 + 3 but most non-trivial code is contained in functions anyway. If one of my favourite C++0x proposals makes it into the next standard revision we may even adapt the future to handle lambda expressions.

Now turning to the client side it is trivial to use the future for asynchronous evaluation. In the sample code below I simulate work with sleep(). Two functions (func1() and func2()) do heavy work and two other functions use these functions in futures. The first one (immediate_request()) requests the value of the future immediately and thus blocks until the future finishes evaluating the result. The second call returns the result then immediately. The function doing_work_itm() also creates a future but works hard before requesting the result which is already available by the time the work was done (timing issues aside).

 1 #include <iostream>
 2 #include <unistd.h>
 3 #include <boost/thread/thread.hpp>
 4 #include "future.hpp"
 6 using std::cout;
 7 using std::endl;
 8 using std::flush;
10 int func1() { sleep(15); return 42; }
11 int func2() { sleep(15); return 42; }
13 void immediate_request()
14 {
15         future<int> f1(func1);
16         cout << "Requesting result of f1 ..." << endl;
17         cout << "f1 = " << f1() << endl;
18 }
20 void doing_work_itm()
21 {
22         future<int> f2(func2);
23         cout << "Doing work ..." << endl;
24         sleep(15);
25         cout << "Requesting result of f2 ..." << endl;
26         cout << "f2 = " << f2() << endl;
27 }
29 int main()
30 {
31         boost::thread t1(immediate_request);
32         boost::thread t2(doing_work_itm);
33         t1.join();
34         t2.join();
35         return 0;
36 }

The nice thing about using futures is obviously the implicit data driven synchronization.