Re: [Boost-users] [BGL] infinite loop in astar_search (there are no negative edge costs)

From: Doug Gregor (dgregor_at_[hidden])
Date: 2006-02-08 09:56:16

On Feb 8, 2006, at 5:13 AM, Detlef Mages wrote:
> I am using astar_search from the BGL and have sometimes hangs due to an
> infinite loop (no, I do not use negative costs or negative heuristic 
> values).
>
> Now here is the strange problem: when compiling the attached (see 
> below) test
> program with compiler optimization enabled it runs into an infinite 
> loop.
> Without optimization a solution is found.
>
> I need help, because I do not know what I should do next. Is this a 
> compiler
> bug? Is there something boost can do (workaround)? Is there a known 
> issue
> (could not find anything) with the relax function?

We ran into a similar problem with Dijkstra's algorithm in the Parallel 
BGL, with the same strange symptoms. Once we saw that the problem occur 
on Intel x86 hardware but not our PowerPC-based Macs, we figured out 
what was going wrong. The floating point unit in x86 machines has 80 
bits of precision, whereas values of type "double" have 64 bits of 
precision. When relaxing occurs, it's possible that the A* search finds 
a new path that is just barely better than the old path, so the edge is 
relaxed. However, the "just barely" better requires more than 64 bits 
of precision to describe, so when the new distance is written back into 
memory the new distance is effectively the same as the old distance... 
so we end up looping, finding a better distance each time but having 
that better distance truncated back to the old value. This only occurs 
when optimizations are enabled because the optimizations are needed to 
turn all of the code in "relax" into efficient FPU operations, and it 
only happens on x86 because nobody else (that I know of) has more 
precision in the FPU than in memory. One fix is to force the compiler 
to write the relaxed distance value back into memory (to round it), 
then compare against the old distance (already rounded); if the values 
aren't equal we can continue.

Thanks for the test case. I was able to duplicate the problem on x86 
Linux with GCC and I've committed a fix to Boost CVS. The updated 
astar_search.hpp is also attached. May we have your permission to put 
this test case under the Boost Software License (all versions) and 
include it in the BGL test suite?

        Doug