On Fri, May 1, 2009 at 11:34 AM, Thomas Klimpel wrote: Bhaskara Marthi wrote: Try building in release mode? The debugging instrumentation in the BGL
can
kill performance. I'm compiling my source files with -O3 using gcc on ubuntu.
That should be sufficient, right? For release mode, NDEBUG must be defined. However, a superficial glance at
the sources doesn't reveal any debugging instrumentation depending on
NDEBUG. Andrew, is there any? Another question for Andrew: Why was the relaxed heap replaced with a 4-ary
heap? In my experience, a normal array based binary heap is a nightmare for
the cache, and I wonder whether the 4-ary heap will be much better in this
respect. However, I don't know whether the cache behavior of a relaxed heap
is much better. Regards,
Thomas
_______________________________________________
Boost-users mailing list
Boost-users@lists.boost.org
http://lists.boost.org/mailman/listinfo.cgi/boost-users I verified that I'm compiling with NDEBUG. Compiler flags are shown below:
/usr/bin/c++ -Dtopological_graph_EXPORTS -O3 -DNDEBUG -fPIC
-I/u/bhaskara/ros/ros-pkg/world_models/topological_map/include
-I/u/bhaskara/ros/ros-pkg/deprecated/deprecated_msgs/msg/cpp
-I/u/bhaskara/ros/ros/core/rosconsole/include -I/opt/ros/include/boost-1_37
-I/u/bhaskara/ros/ros-pkg/common/tinyxml/include
-I/u/bhaskara/ros/ros-pkg/motion_planning/sbpl/src
-I/u/bhaskara/ros/ros-pkg/motion_planning/navfn/include
-I/u/bhaskara/ros/ros-pkg/motion_planning/navfn/srv/cpp
-I/u/bhaskara/ros/ros-pkg/motion_planning/navfn/msg/cpp
-I/u/bhaskara/ros/ros-pkg/world_models/costmap_2d/include
-I/u/bhaskara/ros/ros-pkg/common/laser_scan/include
-I/u/bhaskara/ros/ros-pkg/common/laser_scan/msg/cpp
-I/u/bhaskara/ros/ros-pkg/common/filters/include
-I/u/bhaskara/ros/ros-pkg/common/loki/build/loki-0.1.7/include
-I/u/bhaskara/ros/ros-pkg/common/angles/include
-I/u/bhaskara/ros/ros-pkg/common/robot_srvs/srv/cpp
-I/u/bhaskara/ros/ros-pkg/common/tf/include
-I/u/bhaskara/ros/ros-pkg/common/tf/msg/cpp
-I/u/bhaskara/ros/ros-pkg/common/tf/srv/cpp
-I/u/bhaskara/ros/ros/core/roscpp/include
-I/u/bhaskara/ros/ros/3rdparty/xmlrpc++/src
-I/u/bhaskara/ros/ros-pkg/common/bullet/build/include
-I/u/bhaskara/ros/ros-pkg/common/bullet/swig
-I/u/bhaskara/ros/ros-pkg/visualization_core/visualization_msgs/msg/cpp
-I/u/bhaskara/ros/ros-pkg/common/robot_msgs/msg/cpp
-I/u/bhaskara/ros/ros/std_msgs/msg/cpp
-I/u/bhaskara/ros/ros/core/roslib/msg/cpp
-I/u/bhaskara/ros/ros/core/roslib/include
-I/u/bhaskara/ros/ros-pkg/3rdparty/eigen/build/eigen-2.0.0
-I/opt/ros/include -I/u/bhaskara/ros/ros/3rdparty/gtest/gtest/include
-I/u/bhaskara/ros/ros-pkg/world_models/topological_map/srv/cpp
-DROS_PACKAGE_NAME=\"topological_map\" -O3 -DBT_USE_DOUBLE_PRECISION
-DBT_EULER_DEFAULT_ZYX -DBT_USE_DOUBLE_PRECISION -DBT_EULER_DEFAULT_ZYX -W
-Wall -Wno-unused-parameter -fno-strict-aliasing -o
CMakeFiles/topological_graph.dir/src/grid_graph.o -c
/u/bhaskara/ros/ros-pkg/world_models/topological_map/src/grid_graph.cpp
I also tried using my own priority-queue based version shown below. On a
graph with about 10^4 nodes and degree 4, my version takes about .05
seconds, while dijkstra_shortest_path takes ten times as long.
- Bhaskara
struct QueueItem
{
QueueItem(const GridGraphVertex& v, const double d) : v(v), d(d) {}
GridGraphVertex v;
double d;
};
inline
bool operator< (const QueueItem& q1, const QueueItem& q2)
{
return q1.d > q2.d;
}
ReachableCostVector GridGraph::singleSourceCosts (const Cell2D& source,
const vector<Cell2D>& dests)
{
GridDistances distances;
GridGraphVertex start = cellVertex(source);
priority_queue<QueueItem> q;
q.push(QueueItem(start,0.0));
while (!q.empty()) {
double d=q.top().d;
GridGraphVertex v=q.top().v;
q.pop();
if (distances.find(v)==distances.end()) {
distances[v] = d;
GridGraphAdjacencyIterator iter, end;
for (tie(iter, end)=adjacent_vertices(v, graph_); iter!=end; iter++)
if (distances.find(*iter)==distances.end())
q.push(QueueItem(*iter,d+graph_[edge(v,*iter,graph_).first].cost));
}
}
ReachableCostVector costs;
for (vector<Cell2D>::const_iterator iter=dests.begin(); iter!=dests.end();
++iter) {
GridDistances::iterator pos = distances.find(cellVertex(*iter));
if (pos==distances.end())
costs.push_back(ReachableCost(false,-42.0));
else
costs.push_back(ReachableCost(true, pos->second));
}
return costs;
}