Boost logo

Boost :

Subject: Re: [boost] [graph][heap][coroutine] interruptable dijkstra shortest path function
From: Alex Hagen-Zanker (ahh34_at_[hidden])
Date: 2012-10-05 12:26:30


On 05/10/2012 16:32, Oliver Kowalke wrote:
> Am 05.10.2012 14:07, schrieb Alex Hagen-Zanker:
>>> Have you seen
>>> http://cpp-next.com/archive/2012/09/portable-stackless-coroutines-in-one-header/
>>>
>>> ?
>>>
>>> This approach might be sufficiently lightweight that it would allow us
>>> to maintain one version of the algorithm with some macros.
>>>
>>
>> It is very nice indeed. I did not try it with the shortest path
>> algorithm, but instead a simple sum algorithm where yield is used to
>> get the running total.
>>
>> Using the stackless boost asio coroutine from the link you provided
>> is just as simple as using the proposed boost coroutine.
>>
>> Summing 10,000,000 times the number 2 while yielding intermediate
>> sums gave me the following results:
>>
>> sum plain : 20000000 time: 0.01
>> sum fragmented : 20000000 time: 0.232
>> sum boost coro : 20000000 time: 0.448
>> sum asio coro : 20000000 time: 0.034
>>
>> Without yielding intermediate results, I got the following:
>>
>> sum plain : 20000000 time: 0.008
>> sum fragmented : 20000000 time: 0.029
>> sum boost coro : 20000000 time: 0.027
>> sum asio coro : 20000000 time: 0.012
>>
>> I'd say it it definately worth investigating to use the boost asio
>> method as a means of creating algorithm objects. From this example it
>> appears that:
>>
>> 1. It is an efficient way of interrupting and resuming algorithms.
>> 2. It leaves the algorithms coded in a readable state, although it
>> seems that all local variables should become member variables.
>> 3. If you decide not to interrupt the algorithm, the additional cost
>> due to being part of an algorithm object is less than for the
>> alternatives.
>>
>> I am not working on this anymore, but please see the source for above
>> trial in the attachment.
>
> did you compile the code with optimization switched on?

Maximizing all optimization settings I get:

With yield:

sum plain : 20000000 time: 0.016
sum fragmented : 20000000 time: 0.047
sum boost coro : 20000000 time: 0.452
sum asio coro : 20000000 time: 0.031

Without yield:

sum plain : 20000000 time: 0.016
sum fragmented : 20000000 time: 0.031
sum boost coro : 20000000 time: 0.016
sum asio coro : 20000000 time: 0.015


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk