Re: [Boost-users] performance of dijkstra_shortest_paths

Subject: Re: [Boost-users] performance of dijkstra_shortest_paths
From: Bhaskara Marthi (bhaskara_at_[hidden])
Date: 2009-05-01 15:34:12

On Fri, May 1, 2009 at 11:34 AM, Thomas Klimpel <Thomas.Klimpel_at_[hidden]
> 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_at_[hidden]
> 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;
}