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

Subject: Re: [boost] [graph][heap][coroutine] interruptable dijkstra shortest path function
From: Oliver Kowalke (oliver.kowalke_at_[hidden])
Date: 2012-10-05 11:32:36

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?
preserving fpu state has a significant influence on performance too (at 
least for boost.coroutine I measure a significant influence).

stack-less coroutines (preprocessor trick with switch statement) will 
always be faster than stack-full coroutines (boost.coroutine) because 
stack-full coroutines have to preserver
the stack-frame and some registers and because it exchanges the stack 
and instruction pointer it kicks the CPU predictions (shadow stack 
pointer ...).