On Fri, May 1, 2009 at 11:34 AM, Thomas Klimpel <Thomas.Klimpel@synopsys.com> 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;
}