[BGL] Boost poor performance (against LEDA)
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
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@gmail.com> 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
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.
Could you tell what improvements you have done? Regards. -- |\/\/| Seweryn Habdank-Wojewódzki `\/\/'
"Leandro Melo" <ltcmelo@gmail.com> writes:
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.
You should probably know that although graph construction should be fast with Boost, most of the attention to optimization went into the algorithms, and on making them as fast as possible on a wide variety of graph structures. -- Dave Abrahams Boost Consulting www.boost-consulting.com
Hi David. I understand that Boost's architecture (taking into account the template stuff, the fact all algorithms are implemented as functions and the layering of the algorithms implementations) favors a nice performance of the library. However, I can't get how algorithms can be implemented in a manner to be fast with a wide variety of graph structures. To make my point clear, I mean that a DFS is always a DFS, the algorithm is the same. So, how could one implement a 'optimized' DFS for a wide variety a graph structures. I might have not understood your post correctly. If this is the case, can you clearify this doubt. Thanks.
You should probably know that although graph construction should be fast with Boost, most of the attention to optimization went into the algorithms, and on making them as fast as possible on a wide variety of graph structures.
-- Leandro Terra C. Melo
"Leandro Melo" <ltcmelo@gmail.com> writes:
Hi David. I understand that Boost's architecture (taking into account the template stuff, the fact all algorithms are implemented as functions and the layering of the algorithms implementations) favors a nice performance of the library. However, I can't get how algorithms can be implemented in a manner to be fast with a wide variety of graph structures.
That's the magic of generic programming.
To make my point clear, I mean that a DFS is always a DFS, the algorithm is the same. So, how could one implement a 'optimized' DFS for a wide variety a graph structures.
You create abstractions ("concepts") that handle all the various structures without adding any performance penalty. For example, all of the algorithms use property maps to access properties associated with edges and vertices. That allows them to run fast whether the properties are stored internally or externally. I suggest reading the BGL book; it has a pretty good introduction to generic programming. -- Dave Abrahams Boost Consulting www.boost-consulting.com
Hi David. I think there's a misunderstanding here. I believe that I know many of the benefits of Generic Programming. But my poiny is that I don't agree that algorithms implemented generically can be considered to be faster just because of that. What I was trying to say is that. When you build a DFS algorithm for example (either generically or a very specialized version), the implementation has its lower bounds. And when I say that, I suppose I'm using a nice graph structure. Suppose I have a graph structure and I'm not able to provide an implementaiton of the Property Map interface that achieves constant time access. If I run Dijkstra algorithm with this structures, I will not get the best bound for the algorithm. In other words, in the case of Boost I believe that the fact algorithms are implement in a generic way contributes more to aspects related to 'flexibility'. Aspects related to 'performance' are intrinsically related to 'how' the algorithms are implemented (either in a generic or specialized version). On 10/2/06, David Abrahams <dave@boost-consulting.com> wrote:
"Leandro Melo" <ltcmelo@gmail.com> writes:
Hi David. I understand that Boost's architecture (taking into account the template stuff, the fact all algorithms are implemented as functions and the layering of the algorithms implementations) favors a nice performance of the library. However, I can't get how algorithms can be implemented in a manner to be fast with a wide variety of graph structures.
That's the magic of generic programming.
To make my point clear, I mean that a DFS is always a DFS, the algorithm is the same. So, how could one implement a 'optimized' DFS for a wide variety a graph structures.
You create abstractions ("concepts") that handle all the various structures without adding any performance penalty. For example, all of the algorithms use property maps to access properties associated with edges and vertices. That allows them to run fast whether the properties are stored internally or externally.
I suggest reading the BGL book; it has a pretty good introduction to generic programming.
-- Dave Abrahams Boost Consulting www.boost-consulting.com
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
-- Leandro Terra C. Melo
"Leandro Melo" <ltcmelo@gmail.com> writes:
On 10/2/06, David Abrahams <dave@boost-consulting.com> wrote:
"Leandro Melo" <ltcmelo@gmail.com> writes:
Hi David. I understand that Boost's architecture (taking into account the template stuff, the fact all algorithms are implemented as functions and the layering of the algorithms implementations) favors a nice performance of the library. However, I can't get how algorithms can be implemented in a manner to be fast with a wide variety of graph structures.
That's the magic of generic programming.
Hi David.
I think there's a misunderstanding here. I believe that I know many of the benefits of Generic Programming. But my poiny is that I don't agree that algorithms implemented generically can be considered to be faster just because of that.
I never claimed that. I said "fast with a wide variety of graph structures."
What I was trying to say is that. When you build a DFS algorithm for example (either generically or a very specialized version), the implementation has its lower bounds. And when I say that, I suppose I'm using a nice graph structure. Suppose I have a graph structure and I'm not able to provide an implementaiton of the Property Map interface that achieves constant time access. If I run Dijkstra algorithm with this structures, I will not get the best bound for the algorithm.
In other words, in the case of Boost I believe that the fact algorithms are implement in a generic way contributes more to aspects related to 'flexibility'.
The point is flexibility without loss of efficiency. Non-generic solutions would cost efficiency to, say, allow you to choose between two O(1) lookup structures such as a hashtable and an array.
Aspects related to 'performance' are intrinsically related to 'how' the algorithms are implemented (either in a generic or specialized version).
I don't understand the significance of the quotation marks above. -- Dave Abrahams Boost Consulting www.boost-consulting.com
Ok David, I get your point. On 10/2/06, David Abrahams <dave@boost-consulting.com> wrote:
"Leandro Melo" <ltcmelo@gmail.com> writes:
On 10/2/06, David Abrahams <dave@boost-consulting.com> wrote:
"Leandro Melo" <ltcmelo@gmail.com> writes:
Hi David. I understand that Boost's architecture (taking into account the template stuff, the fact all algorithms are implemented as functions and the layering of the algorithms implementations) favors a nice performance of the library. However, I can't get how algorithms can be implemented in a manner to be fast with a wide variety of graph structures.
That's the magic of generic programming.
Hi David.
I think there's a misunderstanding here. I believe that I know many of the benefits of Generic Programming. But my poiny is that I don't agree that algorithms implemented generically can be considered to be faster just because of that.
I never claimed that. I said "fast with a wide variety of graph structures."
What I was trying to say is that. When you build a DFS algorithm for example (either generically or a very specialized version), the implementation has its lower bounds. And when I say that, I suppose I'm using a nice graph structure. Suppose I have a graph structure and I'm not able to provide an implementaiton of the Property Map interface that achieves constant time access. If I run Dijkstra algorithm with this structures, I will not get the best bound for the algorithm.
In other words, in the case of Boost I believe that the fact algorithms are implement in a generic way contributes more to aspects related to 'flexibility'.
The point is flexibility without loss of efficiency. Non-generic solutions would cost efficiency to, say, allow you to choose between two O(1) lookup structures such as a hashtable and an array.
Aspects related to 'performance' are intrinsically related to 'how' the algorithms are implemented (either in a generic or specialized version).
I don't understand the significance of the quotation marks above.
-- Dave Abrahams Boost Consulting www.boost-consulting.com
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
-- Leandro Terra C. Melo
Leandro Melo schrieb:
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.
I'm very interested in the results. Next week I might start a student job for a planar separator project. Afaik ist currently uses LEDA, maybe I can persuade them to try Boost, too. (It consists of different algorithms and compares them, not only runtime, but many other things.)
Jens Müller wrote:
Leandro Melo schrieb:
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.
I'm very interested in the results.
Next week I might start a student job for a planar separator project. Afaik ist currently uses LEDA, maybe I can persuade them to try Boost, too.
(It consists of different algorithms and compares them, not only runtime, but many other things.)
Actually, one of our SOC students did some LEDA performance comparisons on a very limited scope for his new BGL algorithm. http://stephan.diederich.googlepages.com/soc2006222 But I seem to recall he had done some other performance comparisons previously... Jeff
participants (5)
-
David Abrahams -
Jeff Garland -
Jens Müller -
Leandro Melo -
Seweryn Habdank-Wojewódzki