On Oct 6, 2009, at 8:40 AM, Andrew Sutton wrote:
I'm evaluating the Boost Graph Library for a project would like to present my manager with some benchmark numbers. The only ones I have been able to find are from the GGCL OOPSLA paper, and those are pretty out of date. Does anybody know of any modern work at benchmarking BGL performance?
I am looking at adjacency lists with sets in particular, but anything is better than nothing. I realize that I may just have to give big-O estimates in the end (because it is all dependent on the graph structure), but any estimates would help me for my initial evaluation.
It would be nice to have standing performance benchmarks for the BGL - and other libraries for that matter. Alas... My guess is that you might be able extrapolate (estimate?) current timings from the OOPSLA paper by accounting for modern hardware. There haven't been any drastic changes to the underlying implementations since then.
Sticking with big-O will probably give you the best general sense of performance.
However, you might consider that using sets will cause more dynamic allocations, which will affect your bottom line performance (but not by orders of magnitude).
What benchmarks would you like to see? I've implemented the SSCA (Scalable Synthetic Compact Applications) #2 benchmark from the Darpa high productivity initiative in Parallel BGL, making it work for sequential BGL should only require removing some of the non- applicable parallel code, and possibly changing the call to betweenness_centrality(). It's intended as a parallel benchmark and I don't think it's particularly complete, but it's one of the few graph benchmarks I know of. The SSCA #2 code is in libs/graph_parallel/test. -Nick