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 13:12:21

Am 05.10.2012 18:05, schrieb Alex Hagen-Zanker:
> 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.
>>>
>>> ...
>>>
>>> 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.
>>>
>>
>> did you compile the code with optimization switched on?
>
> I used the default release setting of VS2010. It has 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 ...).
>
> Does that mean that you would recommend using the preprocessor trick 
> whenever its limitations can be worked around? Maybe it would make 
> sense to offer both solutions in your library, possibly using the same 
> interface?
>
it depends - as Giovanni already explained in another posting inline-asm 
could speed-up stack-full coroutines