[Boost-users] [BGL] Boost poor performance (against LEDA)

From: Leandro Melo (ltcmelo_at_[hidden])
Date: 2006-09-30 13:49:58

Hi!
I'm making some performance tests (nothing too fancy) between LEDA and
Boost graphs. I'm not testing algorithms, but some basic adjacency
list operations (add_vertex, add_edge, remove_vertex and remove_edge).
I will not post the whole code I used here, but if anyone is
interested, I can send the files.

It's very surprising (taking into account the Boost claims to be a
high performance library) that LEDA did better in all tests I made.
Actually, in most tests LEDA was more than one order of magnitude
better than Boost. For example: I generated a random (self-loops and
parallel edges) directed graph with 10000 vertices and 20000 edges.
The generation time for LEDA was 0.025 seconds in average and the
generation time for Boost was 0.500 seconds in the average.

I know the template arguments I parameterized the adjacency list are
important. In this case I used the following definition (I also
switched the listS for vecS, but the results were pretty much the
same):

typedef adjacency_list<listS, listS, directedS> Graph;

I also tested remove_edge and remove_vertex operations with various
template parameters.
But in all situations LEDA did better than Boost. In some cases, LEDA
did much better (more that one oder of magnitude again).

The reason of this post is not to start some kind of arguments here
(LEDA X Bosst), but to try to clarify some questions. Naturally, I'd
be convenient if someone has already done such things I just did
(actually, this is what I'm looking for). Anyway, I'm trying to find
out:

- Has anyone come up with results similar to mine's. In other words,
if anyone has tested LEDA against Boost. Has LEDA done better (like in
my case)? If so, how better?

- Does anyone happen to know some reasons that make LEDA so efficient
(assuming my results are correct in a general way)? And it's not even
made using generic programming techniques (which provide some
optimizations at compile time).

- I made tests with versions 4.1 and 5.0 of LEDA. I believe that when
the GGCL ('old' Boost) was released, LEDA was in a version close to 4.
And even in LEDA's 4.1 version, the results were pretty much the same
(better than Boost). However, the Boost Graph Library book presents
Boost as a flexible and high performace library as 'better options'
than LEDA (among others like GTL and Stanford Graph). I agree with the
'flexible' part of the statement, but according to my results that
'high performance' part is not realistic.

One important thing to note is the following. As I mentioned, I did
switch some template parameters of the adjacency list (basically, the
edges and vertices container for both directed and undirected graphs).
However, the tests I'm working on are supposed to be tests for general
situations in which you might have remove_edges, remove_vertices and
even other operations. Thus, it'd be more realistic to use Boost's
adjacency list with template arguments that together represent the
'best' or a 'good' relationship between 'cost and benefit'. Because
I'm trying to simulate a situation in which I'd need all operations
with the same 'importance' (add_vertex, add_edge, remove_vertex,
remove_edge, etc).

Well, I'd appreciate if anyone could comment on this post. Thank you
for reading.
Bellow are the some of the functions I used (assume Graph is defined
and all_vertices and all_edges are vectors of defined vertex and edge
descriptors).

void generate_random_graph(Graph& g)
{
  for (int i = 0; i < num_v; i++)
    all_vertices[i] = add_vertex(g);
  for (int i = 0; i < num_e; i++)
  {
    vertex_desc s = all_vertices[rand() % num_v];
    vertex_desc t = all_vertices[rand() % num_v];
    all_edges[i] = add_edge(s, t, g).first;
  }
}

void remove_edges(Graph& g)
{
  //I didn't test the other version of remove_edge(s, t, g) because
LEDA doesn't have a similar one.
  for (int i = 0; i < 1000; i++)
  {
    edge_desc edge = all_edges[i];
    remove_edge(edge, g);
  }
}

void remove_vertices(Graph& g)
{
    for (int i = 0; i < 1000; i++)
    {
      vertex_desc vertex = vertices[i];
      clear_vertex(vertex, g);
      remove_vertex(vertex, g);
    }
}

-- 
Leandro Terra C. Melo