Boost graph: speeding up add_edge

Question

I have a boost graph application where I need to call the function add_edge( ) [documentation available here].

Profiling this application with KCachegrind reveals the following breakup of time spent:

As can be seen, the add_edge function call takes up roughly 21% of the time of the parent caller. Out of this 21%, 14.49% is simply some std::vector's reallocation.

The suggested way to prevent such vector reallocations seems to be to upfront reserve some amount of space. See for e.g., thread: How to prevent memory reallocation using std::vector

What is the equivalent way to do this reservation of some sufficient amount of space in boost graph?

The underlying graph object over which this repeated calls to add_edge are made is thus:

typedef adjacency_list<
    vecS, vecS, directedS,
    property<
    vertex_name_t, std::string,
    property<vertex_index_t, int,
    property<vertex_color_t, boost::default_color_type,
    property<vertex_distance_t, double,
    property<vertex_predecessor_t, Traits::edge_descriptor>
    > > > >,
    property<
    edge_index_t, int,
    property<edge_capacity_t, double,
    property<edge_weight_t, double,
    property<edge_residual_capacity_t, double,
    property<edge_reverse_t, Traits::edge_descriptor>
> > > > >
Graph;

Edited to add: Similar questions here and here.

Unfortunately for me, g.m_edges does NOT have function reserve.

Edited to add link to a minimal example (that is difficult to get to work fully) but compiles fine except for an undefined external reference that is not the main issue.

Close ? Why ? being able to reserve some std::vector 's space upfront which boost graph is built on seems like a valid question! — Tryer, Jun 07 '21 at 12:04
I'm not sure about the downvoter, but maybe they reckoned that it was not that useful to show how std::vector works in a profiler without the actual code that drives it. It was nice enough that you included proof of where your bottleneck is, but diving into the precisely allocation details of std::vector seems rather unhelpful (it has been like that for decades). I'll give this a more detailed look when weknow more about the use-case. — sehe, Jun 07 '21 at 12:37

score 1 · Answer 1 · answered Jun 07 '21 at 12:29

1

Unfortunately for me, g.m_edges does NOT have function reserve

But m_vertices does.

#include <boost/graph/adjacency_list.hpp>

int main() {
    boost::adjacency_list<> g;
    g.m_vertices.reserve(1024);
}

Also, since you're using vecS you could almost equivalently just construct with a pre-allocated number of vertices:

boost::adjacency_list<> g(1024);

The difference is, of course, that this doesn't just reserve space for, but resizes the graph to contain 1024 vertices.

answered Jun 07 '21 at 12:29

sehe

374,641
47
450
633

Actually, the number of vertices in my graph is fixed and is not the bottleneck. It is adding edges that seems to be the hotspot per KCachegrind. So, it is not clear that reserving space for the number of vertices will help. – Tryer Jun 07 '21 at 12:31
I added a minimal example that explains the issues in the OP. – Tryer Jun 07 '21 at 13:03
1

The nature of adjacency lists is that edges are stored with source vertices. You may be better able to micro-optimize when you control the full graph model, like I did here e.g. https://stackoverflow.com/questions/67232482/boost-fibonacci-heap-access-violation-during-pop/67238518#comment118864338_67238518 I'm a bit sad that all the improvements I made in [this answer](https://stackoverflow.com/a/67622091/85371). If I had a test bed that I could actually profile (`int xid(int fr,int to){return fr*NNODES+to;}` seems simple enough, but I have no edge configurations. – sehe Jun 07 '21 at 22:31
1

So, I made up some (BAD) random generations just to check that the bundled-properties approach doesn't perform a lot better - and it doesn't: https://godbolt.org/z/d8zj3hf15 performs roughly the same as https://godbolt.org/z/Pj5bnE1Tz. Maybe you can help out and make the self-contained tester more realistic so we have things to optimize? We might even experiment with a completely custom graph model. – sehe Jun 07 '21 at 22:40
1

thanks for your efforts.Let me see whether I can provide any test case using actual data from my application.BTW, you have certainly guided me over the years to modernize by C++. I have taken what I can chew -- my inputs are now json files and I use boost json reader and this has certainly improved my development/testing cycle. However, some of your suggestions such as the effort you put into your answer to make my code modern, I find it rather difficult to wrap my head around. Hence my seemingly stubborn code that I post on SO that is as you point out meant to compile in ancient 03 C++. – Tryer Jun 08 '21 at 03:00

Boost graph: speeding up add_edge

1 Answers1