Boost logo

Boost :

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


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