Allocator (memory control) support for graphs and algorithms

[Becheler]

Stateful allocator support

Story

Three independent users, completely different domains, same root cause:

addy90 abandoned BGL after two years because he needed to load Germany's full OSM road network (~128 GB) using memory-mapped files via Boost.Interprocess. He discovered that adjacency_list has no allocator parameter: it uses hardcoded new for vertex storage and edge properties in detail/adjacency_list.hpp, and the container_gen machinery that maps selectors like vecS to actual containers has no allocator parameter either. He built his own allocator-aware graph from scratch.

megyhazy:

I've run into this naive allocator issue as well when dealing with large graphs.

pratzl confirmed he has working MMF-backed graphs using Boost.Interprocess, but that code lives in his private products.

jcelerier (OSSIA) comes from the opposite direction: small graphs, real-time audio threads with strict deadlines (2ms for transitive closure, 16ms for cycle detection). For him hidden allocations are not a scalability problem, they are a correctness problem: a malloc in the audio thread causes a glitch or a missed frame. He rewrote BGL algorithms by hand just to extract and control temporary allocations. His verdict:

"definitely the n°1 thing is having access to memory allocations / containers used. Everything else can be worked around or is a matter of ergonomics, but this is a core thing that cannot be worked around without rewriting."

There are two related but distinct problems here.

1. Graph data structures with no allocator parameter: you can't persist a graph to an MMF.
2. Algorithms with no allocator parameter: you can't control where BFS/DFS scratch memory (queues, stacks, priority queues) gets allocated.

The group can decide at the start which one to focus on. The data structure problem is harder and more impactful. The algorithm problem is more approachable in 45 minutes. Both are worth thinking about.

Dream solution

boost::graph::adjacency_list gains an Allocator template parameter (C++14-compatible, defaulted). A Boost.Interprocess-backed graph just works. No raw new anywhere in the implementation. BFS, DFS, and Dijkstra accept an optional allocator parameter for their internal scratch memory.

Starting point

addy90's full writeup in discussion #466
jcelerier's writeup in discussion #466
adjacency_list.hpp
detail/adjacency_list.hpp
Boost.Interprocess allocator docs

Intermediary objective (45 min)

It's a very challenging problem. Any lead, design idea, incomplete thoughts are welcome and valuable.

Option 1: Data structures. Design the missing interface. Write the new adjacency_list template signature with an Allocator parameter. Think about where a new allocator-aware adjacency_list should live to avoid breaking existing users. A modern boost::graph::adjacency_list<...> superseding the old boost::adjacency_list? Show what construction with a Boost.Interprocess allocator would look like at the call site. Note which internal new calls need replacing and with what.

Option 2: Algorithms. Write the proposed signature for allocator-aware BFS: breadth_first_search(g, source, queue, visitor, color_map, alloc). List which other algorithms have the same problem. Rewriting algorithms will be very painful: is there a happy path?

That is the design document a contributor needs before touching a single line of code.

[pratzl]

A common pattern in the std library is to have an allocator as the last parameter with a matching allocator template parameter. For example:
template<T, Alloc = std::allocator>
void do_something(T& value, Alloc alloc = Alloc());

A problem when dealing with graphs is that the type we want to allocate isn't available because it's internal and not exposed to the user, or that we want to use it for multiple types. In that case, we can use a common type instead, such as:
template<T, Alloc = std::allocator>
void do_something(T& value, Alloc alloc = Alloc());

In the implementation we can then cast the allocator to a new allocator, such as
using WVAlloc = typename std::allocator_traits::template rebind_alloc<weighted_vertex>;
using Queue = std::priority_queue<weighted_vertex, std::vector<weighted_vertex, WVAlloc>, decltype(qcompare)>;

WVAlloc can be used to allocate a Weighted Vertex.

The allocator can be applied to all the graph data structures (e.g. adjacency_list), and algorithms that allocate memory (e.g. for stack or queue).