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

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 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 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