Monday, October 06, 2008

Asynchronous Fork/Join using Asio

As most Asio users will no doubt be aware, multiple threads can call io_service::run() to set up a pool of threads from which the completion handlers will be executed. This can be used in conjunction with io_service::post() to execute arbitrary tasks in the thread pool.

In some rare spare moments I have used this facility to dabble in parallel algorithms (mainly to do with sorting large data sets). However, I was not completely satisfied with its ease-of-use when it came to implementing the algorithms.

Recently I came across the new Fork/Join framework that's going to be included in Java 7. I was particularly struck by the simplicity of the coinvoke() function, and was inspired to implement something similar on top of Asio. Of course, what with Asio and my preferred mode of thinking, I wanted to implement an asynchronous version.

And the result...

I created a function template that may be used to initiate two or more tasks to run in parallel:

template <typename TaskCont0, ..., typename TaskContN,
typename Task0, ..., typename TaskN, Cont>
void coinvoke(asio::io_service& io_service,
Task0 task0, ..., TaskN taskN, Cont cont);

Each task must be a function object with a single argument, where the argument is the continuation function object for the task. The TaskContN template parameters explicitly specify the function signatures used for each of the task continuations. For example:

coinvoke<void(int), void(int)>(task0, task1, cont);

says that both tasks have a continuation with the signature void(int). The combining continuation has a signature that is the concatenation of all of the task continuations' arguments. In the above example, that's void(int, int).

The operation of coinvoke() works as follows (click image for full size view):

You can get the implementation here. Don't expect the source to be readable; it contains hairy uses of template metaprogramming and preprocessor magic.

Why continuations?

You might be wondering why each task passes its result to a continuation function rather than simply returning it. The answer to that is that a task need not be a single calcuation; it could instead be the start of a chain of asynchronous operations. This means that coinvoke() could be used to simplify management of parallel operations, such as writing data to multiple sockets, and not having the handler called until all operations have finished. I plan to explore those and other related ideas further in the near future, but for now let's just look at parallel algorithms.

Fibonacci revisited

The equivalent implementation of the Fibonacci example from the Java Fork/Join paper looks like:

void combine_fib(
int a, int b,
function<void(int)> h)
{
h(a + b);
}

void calc_fib(
asio::io_service& io_service,
int n,
function<void(int)> f)
{
if (n <= threshold)
{
f(seq_fib(n));
}
else
{
coinvoke<void(int), void(int)>(io_service,
bind(calc_fib, ref(io_service), n - 1, _1),
bind(calc_fib, ref(io_service), n - 2, _1),
bind(combine_fib, _1, _2, f));
}
}

Can I have C++0x lambdas now, please?

The need to define a separate combine_fib is not ideal, since a key part of the algorithm is off in another spot. Fortunately, C++0x's new monomorphic lambdas come to the rescue:

void calc_fib(
asio::io_service& io_service,
int n,
function<void(int)> f)
{
if (n <= threshold)
{
f(seq_fib(n));
}
else
{
coinvoke<void(int), void(int)>(io_service,
[&io_service, =n](function<void(int)> c)
{
calc_fib(io_service, n - 1, c),
},
[&io_service, =n](function<void(int)> c)
{
calc_fib(io_service, n - 2, c),
},
[=f](int a, int b)
{
f(a + b);
});
}
}

A useful example

Since that has to come close to being the most convoluted way of calculating a Fibonacci value, here is an example where coinvoke() is used for a parallel merge sort:

template <typename Iterator>
void merge(
Iterator begin,
Iterator middle,
Iterator end,
function<void()> f)
{
std::inplace_merge(begin, middle, end);
f();
}

template <typename Iterator>
void sort(
asio::io_service& io_service,
Iterator begin,
Iterator end,
function<void()> f)
{
std::size_t n = end - begin;
if (n <= 16384)
{
std::sort(begin, end);
io_service.post(f);
}
else
{
coinvoke<void(), void()>(io_service,

// First task sorts the initial half of the range.
bind(&sort<Iterator>,
ref(io_service),
begin, begin + n / 2, _1),

// Second task sorts the latter half of the range.
bind(&sort<Iterator>,
ref(io_service),
begin + n / 2, end, _1),

// Continuation function merges the two sorted ranges.
bind(&merge<Iterator>,
begin, begin + n / 2, end, f)

);
}
}

On my 8-core machine, this gives a little more than a threefold speedup in sorting large vectors.

21 comments:

Anonymous said...

awesome! - one question though, could there be an overload of coinvoke that takes an iterator range of tasks?

Anonymous said...

inspiring post!

have you compared the performance gain vs a thread pool or map-reduce model ?

It would be nice to have a map-reduce example using asio. I guess it would be much cleaner than the coinvoke code !

jose

Dean Berris said...

Nice post Chris,

It would be nice seeing the recently-accepted Phoenix library help out those stuck with compilers that don't support C++0x lambda's.

Just thinking aloud: what is the overhead of using an io_service instance to run arbitrary function handlers? I've been doing this to implement Active Objects, but until now I'm not entirely convinced that using an io_service instance per active object is a "lean" enough way of going about it.

I hope you can write about that issue, as well as how to be able to define a custom error/exception handler for function objects scheduled for execution in an io_service queue.

Keep up the great work!

Marat Abrarov said...

Awesome.
It remains to get rid of boost::function. boost::function can add additional overhead related to memory allocation.
What about overall custom memory allocation support?
What about replacing boost::function? For example, it could be replaced with boost::function with custom allocator forwarding to asio custom memory allocation.
Support of custom memory allocation could provide an opportunity to compete (sometimes) with Intel TBB (with TBB's task class).
I am more inclined to think that, thanks to its versatility and generalizations, asio can become the basis for the fork/join library, which is then able to enter the Boost.

Jim Hurd said...

Great post, great library.

Does ASIO already implement work stealing? If not, is there any reason asio would not benefit from a work stealing scheduler?

James said...

Great job to share such a beneficial article. Cole Hauser Yellowstone Jacket The article is not only useful but also really creative.

JW Willy said...

Really helpful down to the ground, happy to read such a useful post. Trucker Jacket Cole Hauser Yellowstone I got a lot of information through it and I will surely keep it in my mind. Keep sharing.

Noah Oliver said...

Where else may anyone get that kind of info in such an ideal approach of writing? You are Excellent.Rip Wheeler Yellowstone Cotton Jacket

Ayesha Anees said...

These posts of Asynchronous Fork/Join using Asio, which are so reactive and authentic for all, but there are also very relevant and desiring new model car for sale in Karachi, available to getting in all over the Karachi, Pakistan reactively.

Joy Shore said...

Welcome back! Our custom writing portal never doubt the quality of our content. But if you do, a refund is guaranteed. To ensure 100% uniqueness of your review, experts examine the final copy using advanced tools. Top-quality is a must. A team of professional editors re-check your order before delivery.

Dijital Pazarlamacilar said...

SWOT Analizi
SWOT Analizi Nedir?
SWOT diyagramlarını veya matrislerini kullanan SWOT analizi, herhangi bir iş planlaması veya analizinin önemli bir parçasıdır.

SWOT, güçlü yönler, zayıf yönler, fırsatlar ve tehditler anlamına gelir. Güçlü ve zayıf yönler iç faktörlerdir ve fırsatlar ve tehditler dış faktörlerdir. Bir SWOT diyagramı, bu faktörlerin her birine odaklanarak bir projeyi veya ticari girişimi analiz eder. Tipik olarak, her alan için bir tane olmak üzere dört kutudan oluşur, ancak tam şekil tasarıma bağlı olarak değişebilir.

SWOT diyagramları, artıları ve eksileri görselleştirerek belirli bir girişime veya stratejiye başlayıp başlamamaya karar vermeye çalışırken özellikle yararlı olabilir. Bir projenin tüm olumlu ve olumsuz yanlarını açıkça ortaya koyan SWOT analizi, ilerleyip ilerlememeye karar vermeyi kolaylaştırır.

SWOT Analizi Nasıl Yapılır?
Hedefi belirleyin. Analiz etmek ve sayfanın en üstüne yerleştirmek için önemli bir proje veya stratejiye karar verin.
Bir ızgara oluşturun. Büyük bir kare çizin ve ardından onu dört küçük kareye bölün.
Her kutuyu etiketleyin. Sol üstteki kutuya "Güçlü Yönler", sağ üstteki kutuya "Zayıf Yönler", sol alttaki kutuya "Fırsatlar" ve sağ alttaki kutuya "Tehditler" kelimesini yazın. Bunlar başlıklardır, bu nedenle renk veya yazı tipi boyutu kullanılarak metnin geri kalanından ayırt edilmelidirler. SmartDraw, inşaatı hızlı ve kolay hale getirmek için tasarlanmış birkaç SWOT diyagramı şablonu sunar.
Güçlü ve zayıf yönleri ekleyin. Projeyi etkileyen faktörleri ilgili kutulara ekleyin. Bir SWOT analizinin bileşenleri niteliksel ve anekdotsal olabileceği gibi niceliksel ve deneysel nitelikte olabilir. Faktörler tipik olarak bir madde işareti biçiminde listelenir.
Sonuca varmak. Bitmiş SWOT diyagramını analiz edin. Olumlu sonuçların olumsuzlardan daha ağır basıp basmadığını not ettiğinizden emin olun. Eğer yaparlarsa, amacı gerçekleştirmek için iyi bir karar olabilir. Aksi takdirde, ayarlamalar yapılması gerekebilir, aksi takdirde plan basitçe terk edilmelidir.

Shirlee Minichiello said...

Executive-Education.id is really a supplier of personal teaching knowledge products and services where a person coach exclusively shows you 1 to 3 college students and coaching plus understanding pursuits ... go to https://privat-inggris.netlify.app/kursus-bahasa-inggris-penjaringan.html for further

바카라사이트닷컴 said...

Looking forward to 바카라사이트닷컴 reading more. Great article.Really looking forward to read more. Great.

Mike Hartgraves said...

Jabodetabek private tutoring services with teachers coming to the house. A lot more than many hundreds of active tutors you will need to teach various skills and lessons for the children to adults ... go to https://kursus-jerman.vercel.app/kursus-bahasa-jerman-pasar-minggu.html for further

Spirited Ryan Reynolds Jacket said...

You’re doing a remarkable process. Hold it up

49ers Gold Jacket said...

I never stop myself to mention some thing about it.

49ers Gold Jacket said...

Really enjoyed reading your blog

top gun jacket patches said...

In summary, Asynchronous Fork/Join using Asio is a powerful technique for writing efficient and scalable code. By breaking down tasks into smaller subtasks, using Asio to create a pool of worker threads, and combining the results using a Join operation, you can take advantage of modern hardware architectures and write highly efficient and scalable code that can leverage multiple cores and threads.

Finn Foley said...

Your expertise fosters development. Kill Em With Comedy Hoodie

Mhina said...

I am truly pleased to discover this website. Thanks a lot! www.personaltrainersherwoodpark.com

James Lavine said...

This post resonates with me so much. It's like you read my mind! Thanks for sharing your personal experiences; it makes the content much more relatable. Red Leather jackets