[Boost-users] [Graph] Multithreading slowdown on dual core Pentium D

From: Brian Townley (thranil_at_[hidden])
Date: 2007-01-18 14:27:13

I am experiencing a problem with multithreading using the boost graph
library on a dual core Pentium D platform. If I attempt to calculate average
path length of a graph, I get at least a 2x slowdown using multiple threads
when using johnson_all_pairs_shortest_path. Calculating betweenness is even
worse (~7x) when I use  brandes_betweenness_centrality and
relative_betweenness_centrality.

In my test setup, I have no locks anywhere and no shared memory (the graphs
are loaded from a file for each iteration in the test). The graph has been
defined similar to the following (I can't get actual code on the list due to
restrictions from employer):

struct VertexProperties
{
       string name;
       string group;
       vector<string> properties;
};

struct EdgeProperties
{
      string name;
      double weight;
};

typedef boost::property<...> GraphProperty //a group of enums mapped to
doubles and ints

typedef boost::adjacency_list<listS, vecS, undirectedS, VertexProperties,
EdgeProperties, GraphProperty> BoostGraph;

All I have to do in my code to see the slowdown is to use a populated graph
with johnson_all_pairs_shortest_path in some iterative loop in both one and
multiple threads. A real kicker is that currently I can get around this
problem by spawning multiple processes to deal with the data load (so I have
an interim solution at least) and that gives me a performance improvement by
2x which I expect with dual core... However, I really want to know why this
isn't working in a multi-threaded environment.

 What could I be doing wrong? Is there some proprocessor #define that makes
the boost graph library more thread independent? Is there something wrong
with the way that I am declaring the graph? Any help is appreciated!

Thanks,
Thranil