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

From: Leandro Melo (ltcmelo_at_[hidden])
Date: 2006-09-30 14:42:02

Hi.
First of all, I'd like to apologize because I've not carried out my
tests correctly.
I had some optimization configurations not set correctly. So, this
invalidates all tests I made. So, please ignore everything I said
about my results.
Anyway, if anyone has a comment about the topic it's still welcome.
I'm gonna have to redo all tests. And I'm pretty sure that I'm gonna
have better results for Boost. But I still have some surprises, I'll
come back to this subject later on the list.
Thank you again and sorry for the inconvinience.

On 9/30/06, Leandro Melo <ltcmelo_at_[hidden]> wrote:
> 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
>

-- 
Leandro Terra C. Melo