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 ...).