Re: [boost] [graph][heap][coroutine] interruptable dijkstra shortest path function

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