Boost Graph Library overhead

Question

In a for loop over ~21K variables (iNumVars ~21K), I have the following code snippet where both iNumVars and vars are integers, and vars is zero in most cases (which are ignored) and non-zero in others (for which there is additional processing):

for (i=1; i<=iNumVars; i++) {
    if (vars[i]) {
    ... additional processing ...

Out of the ~21K variables, there are 10 - 150 which are of interest. In another way to do this task I can use the Boost Graph Library and identify the ~21K variables as vertices in a graph (variable name G). Graph G is filtered to identify the 10 - 150 variables of interest, which can then be iterated over using:

auto vpair = vertices(filteredG);
for (auto iter=vpair.first; iter!=vpair.second; iter++) {
    ... the same additional processing as above ...

The for loop is called 10 million times. What I am finding is that iterating over the much smaller number of vertices is taking longer than iterating over all the variables and doing just the boolean compare. I'm not an expert in fast c++ coding, but does this make sense? Do the Boost Graph Library iterators really slow down the for loop?

One note is I didn't show how the graph G gets to the filtered version filteredG. However, this is done in any case for other reasons in the lines above either for loop, so there is no additional time penalty in having to do the filter_graph operation 10M times.

Thanks, jim

user_85371 · Answer

What I am finding is that iterating over the much smaller number of vertices is taking longer than iterating over all the variables and doing just the boolean compare. I'm not an expert in fast c++ coding, but does this make sense

Yes. Filtered Graph is a lazy adaptor. This has the benefit that you can have a dynamic filter (progressively filtering out more e.g.). The downside is the predicates are re-evaluated on the fly all the time.

Ideas

I'd consider copying the filtered subset to a separate graph to do the filtering once, up-front.

Alternatively you can

realize that vecS makes the vertex descriptor an ordinal index into a vector, which sort of removes any hope op optimizing for a subset (since the entire domain of the source graph still needs to be enumerated)
Have a look at subgraphs. These have a similar semantic (where the subgraph inherits all nodes in the parent graph) but you can still operate on the parent graph in isolation. This makes a different trade off in that descriptors need to be translated/projected between layers of the graph.

None of these solutions are really straightforward, so maybe you can simplify using your domain logic? Apparently you have an "oracle" that can tell you which vertices are "of interest". Why not put those in a set and iterate the set itself instead of the entire (filtered) graph?

Boost Graph Library overhead

1 Answers

Ideas