Filtering vertices and edges more efficiently

[fhamonic]

Hi all, I continue with the ideas I've had for my own graph library, one of which was designing a custom container for filtering vertices and edges.

A common operation in graph algorithms is to attach booleans to the graph vertices and edges that symbolizes either if a given vertex or edge has already been visited or if it must be skipped because we are considering a subgraph for example.

The typical way of doing this is with a std::vector or bool. This container has received much criticism since it is a specialization of std::vector for encoding each boolean as a single bit of memory of a 64bit word (usually), but it has a lot of advantages since it allows storing the same information with 8 times less memory usage (and has thus much more chances of staying in the CPU cache).

I think we can make use of the newly standardized functions like std::countr_zero for extending the functionality of std::vector<bool>. Indeed, if we want to iterate on all vertices that are associated to true, currently we need to iterate on the vertices and skip those for which filter[u] is false but if the vertices are consecutive integers we can use std::countr_zero to directly compute the next index corresponding to a 1 bit. On most CPUs std::countr_zero is only two instructions, that's a big saving !
This could look like this:

uint64_t word = ...;
int index = ...; // initially pointing to a bit that is at 1
...
++index;
index += std::countr_zero(word >> index); // add the offset to the next true bit
...

We then have to test if index exceeds 64, in which case we continue with the next 64bit word.

However, I wonder what the API should be for a container providing this functionality, I initially thought of a method true_indices that return a range of the indices that correspond to true bits...
What are your opinions/suggestions about that?

[pratzl]

While having a vector of bool is common, it's not used by all algorithms, so we avoid baking it into the data structures. If we need it, then we define it as needed for each algorithm when it's needed. We're also trying to be neutral to the graph data structures to allow easier integration with externally defined graphs that won't likely have that kind of feature defined for it (at least none that I've seen). The take-away is that I don't see that fitting into our design very well.

[fhamonic]

Hi,
I did not mean to bake a vector of bool into the graphs data structures but to replace the use of std::vector<bool> in some algorithms by a container that allows retrieving more efficiently the indices that are associated to true or false.
As I described it, the use of std::countr_zero can speed up the iteration on the indices associated to true bits by a factor 64 in the best case.
This would be of use in maximal_independent_set when we want to iterate on vertices that has not yet been removed or in a future connected_components where, after having discovered a connected component, we want to find a vertex that has not yet been discovered to start a new traversal from it.
I understand that adding a method to std::vector<bool> or adding a container extending std::vector<bool> is a pretty intrusive change, but I overall wanted to share the idea since std::countr_zero is in the standard now.

[pratzl]

Thanks for the clarification. I'd lost track of std::countr zero in C++20 and is a good reminder. I think I'm understanding now.

I can see how it would be useful for performance. If we attempt to make the graph interface dependent on it, it adds more time to get the library accepted, so I would prefer to have it as an internal feature that we could take advantage of.

I'll see if anyone else will comment on this, also. I'm meeting with the core group in a couple of weeks and can bring this up if no one else has responded. FWIW I'm more concerned about getting our API correct right now. Performance is also important, but it's less of a priority right now.

You asked what the API for that kind of container should be. I'd offer the challenge to you to come up with an API that's useful. Figure out how you want to use it, and that will drive your design.