[BGL] infinite loop in astar_search (there are no negative edge costs)
Hi all 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? -- Detlef Here are the facts: I condensed one of the malicious (undirected) graphs to <SNIP> V ar[181]; for( unsigned int i = 0; i < 181; ++i ) { ar[i] = add_vertex( VProp(i, 1.0), g ); } add_edge( ar[1], ar[18 ], EProp( 2.20 ), g ); add_edge( ar[0], ar[30 ], EProp( 1.58 ), g ); add_edge( ar[0], ar[66 ], EProp( 0.93 ), g ); add_edge( ar[66], ar[100 ], EProp( 2.72 ), g ); add_edge( ar[66], ar[101 ], EProp( 2.87 ), g ); add_edge( ar[30], ar[142 ], EProp( 4.88 ), g ); add_edge( ar[18], ar[142 ], EProp( 3.29 ), g ); </SNAP>. There are no other edges. A complete listing of the program is attached. My compiler version: # g++ -v Using built-in specs. Target: i586-suse-linux Configured with: ../configure --enable-threads=posix --prefix=/usr --with-local-prefix=/usr/local --infodir=/usr/share/info --mandir=/usr/share/man --libdir=/usr/lib --libexecdir=/usr/lib --enable-languages=c,c++,objc,f95,java,ada --disable-checking --with-gxx-include-dir=/usr/include/c++/4.0.2 --enable-java-awt=gtk --disable-libjava-multilib --with-slibdir=/lib --with-system-zlib --enable-shared --enable-__cxa_atexit --without-system-libunwind --host=i586-suse-linux Thread model: posix gcc version 4.0.2 20050901 (prerelease) (SUSE Linux) # g++ -O2 searchtest4.cpp && a.out 2>/dev/null discover: 0 examine: 0 edge_relaxed: 0 -- 30 discover: 30 edge_relaxed: 0 -- 66 discover: 66 examine: 66 edge_not_relaxed: 66 -- 0 edge_relaxed: 66 -- 100 discover: 100 edge_relaxed: 66 -- 101 discover: 101 examine: 30 edge_not_relaxed: 30 -- 0 edge_relaxed: 30 -- 142 discover: 142 CYCLE: examine: 100 CYCLE: edge_relaxed: 100 -- 66 CYCLE: black_target: 100 -- 66 CYCLE: examine: 66 CYCLE: edge_not_relaxed: 66 -- 0 CYCLE: edge_relaxed: 66 -- 100 CYCLE: black_target: 66 -- 100 CYCLE: edge_relaxed: 66 -- 101
From now on the lines marked CYCLE are repeated. --> infinite loop
# g++ -O0 searchtest4.cpp && a.out 2>/dev/null discover: 0 examine: 0 edge_relaxed: 0 -- 30 discover: 30 edge_relaxed: 0 -- 66 discover: 66 examine: 66 edge_not_relaxed: 66 -- 0 edge_relaxed: 66 -- 100 discover: 100 edge_relaxed: 66 -- 101 discover: 101 examine: 30 edge_not_relaxed: 30 -- 0 edge_relaxed: 30 -- 142 discover: 142 examine: 100 edge_not_relaxed: 100 -- 66 // from here on the two outputs differ examine: 101 edge_not_relaxed: 101 -- 66 examine: 142 edge_not_relaxed: 142 -- 30 edge_relaxed: 142 -- 18 discover: 18 examine: 18 edge_relaxed: 18 -- 1 discover: 1 edge_not_relaxed: 18 -- 142 examine: 1 found 1->18->142->30->0 --> success Here is the listing "searchtest4.cpp": ---------------------------------- #include <boost/graph/astar_search.hpp> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/graphviz.hpp> #include <iostream> using namespace std; using namespace boost; struct VProp { VProp() : m_distance(1.0) {} VProp( size_t invar_id, double heuristic ) : m_vertex_invariable_id( invar_id ), m_heuristic( heuristic ), m_distance( .0 ) {} size_t m_vertex_invariable_id; // my id that is not changed by rebuilding the index map double m_heuristic; // a really simple heuristic double m_distance; // altered by the algo: this id is the distance boost::default_color_type m_color; }; struct EProp { EProp() : m_weight( .0 ) {} EProp( double weight ) : m_weight( weight ) {} double m_weight; }; typedef boost::adjacency_list< boost::vecS, boost::vecS, boost::undirectedS, VProp, EProp > G; typedef G::vertex_descriptor V; typedef G::edge_descriptor E; struct found_goal {}; template< class Vertex, class Edge > class GoalVisitor : public boost::default_astar_visitor { public: GoalVisitor(Vertex goal) : m_goal(goal) {} template <class Graph> void examine_vertex(Vertex u, Graph& g) { cout << "examine: " << u << endl; if(u == m_goal) throw found_goal(); } template <class Graph> void discover_vertex(Vertex u, Graph& g) { cout << "discover: " << u << endl; } template <class Graph> void black_target(Edge u, Graph& g) { cout << "black_target: " << boost::source( u, g ) << " -- " << boost::target( u, g ) << endl; } template <class Graph> void edge_relaxed(Edge u, Graph& g) { cout << "edge_relaxed: " << boost::source( u, g ) << " -- " << boost::target( u, g ) << endl; } template <class Graph> void edge_not_relaxed(Edge u, Graph& g) { cout << "edge_not_relaxed: " << boost::source( u, g ) << " -- " << boost::target( u, g ) << endl; } private: Vertex m_goal; }; template< class Graph, class CostType > class DistanceHeuristic : public boost::astar_heuristic<Graph, CostType > { public: DistanceHeuristic( Graph & graph ) : m_graph(graph) {} template< class Vertex > CostType operator()( Vertex u) { return m_graph[u].m_heuristic; } private: Graph & m_graph; }; class EdgeWeightWriter { public: EdgeWeightWriter( G & graph ): m_graph( graph ) {} template< class OStream > void operator()( OStream& out, V v ) { // out << " [label= \"" << v <<"\"]"; } template< class OStream > void operator()( OStream& out, E v ) { out.precision( 30 ); out << " [label= \"" << m_graph[v].m_weight <<"\"]"; } private: G & m_graph; }; int main() { G g; V ar[181]; for( unsigned int i = 0; i < 181; ++i ) { ar[i] = add_vertex( VProp(i, 1.0), g ); } // add_edge( ar[1], ar[18 ], EProp( 2.20307469298885294506362697575 ), g ); // add_edge( ar[0], ar[30 ], EProp( 1.58945958901181461087048774061 ), g ); // add_edge( ar[0], ar[66 ], EProp( 0.937232823257896585644743936427 ), g ); // add_edge( ar[66], ar[100 ], EProp( 2.72761497732282665040770552878 ), g ); // add_edge( ar[66], ar[101 ], EProp( 2.87914914272965027919326530537 ), g ); // add_edge( ar[30], ar[142 ], EProp( 4.8843528076143511995610424492 ), g ); // add_edge( ar[18], ar[142 ], EProp( 3.29201592753501959265349796624 ), g ); add_edge( ar[1], ar[18 ], EProp( 2.20 ), g ); add_edge( ar[0], ar[30 ], EProp( 1.58 ), g ); add_edge( ar[0], ar[66 ], EProp( 0.93 ), g ); add_edge( ar[66], ar[100 ], EProp( 2.72 ), g ); add_edge( ar[66], ar[101 ], EProp( 2.87 ), g ); add_edge( ar[30], ar[142 ], EProp( 4.88 ), g ); add_edge( ar[18], ar[142 ], EProp( 3.29 ), g ); map< V, V > predecessor; associative_property_map< map< V, V > > predecessorMap( predecessor ); /** * solution to this: 1->18->142->30->0 */ try { astar_search(g, ar[0], DistanceHeuristic<G, double>( g ), predecessor_map( predecessorMap ). weight_map( get(&EProp::m_weight, g) ). color_map( get(&VProp::m_color, g) ). distance_map( get(&VProp::m_distance, g) ). visitor(GoalVisitor<V, E>( ar[1] ) ) ); } catch ( found_goal ) { cout << "found" << endl; for(V v = ar[1];; v = predecessor[v]) { cout << v; if(predecessor[v] == v) break; cout << "->"; } cout << endl; } boost::write_graphviz( std::cerr, g, EdgeWeightWriter( g ), EdgeWeightWriter( g ), default_writer() ); }
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
On Wednesday 08 February 2006 15:56, Doug Gregor wrote:
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
Thanks for the immediate fix. I tested the fixed astar_search.hpp and everything seems to work now. I already had faint intuition about decimal point precission, but discarded it due to my strong believe in the correctness without side-effects of how compilers address hardware. Attached you will find a cleaned up test case. I managed to reduce the graph even more without loosing its sensibility to the issue. Please feel free to put it in the BGL test suite. Thanks again for your help. Detlef
participants (2)
-
Detlef Mages -
Doug Gregor