Potential changes to the graph resource

Simulation Modeling Toolkit (SMTK) Design
1

Graph resource changes

We are considering 2 changes to the graph resource. They are not directly related, but since both would impact downstream users of graph resources, we are considering doing them at the same time or in quick succession:

  • Change the arc container classes to store weak pointers instead of using std::reference_wrapper.
  • Change the graph resource to hold shared pointers to its components in a boost::multimap instead of a std::set.

Problem statement and rationale

Arcs should hold weak pointers

The issue here is that without careful arc management, removing a component may leave arcs with dangling references to freed memory. Any operations which remove components from a resource may do so without removing arcs which point to the removed components and there is no efficient way to validate changes: although most arcs have an inverse relationship with a “partner” arc, this is not required and in this case it is not possible to efficiently remove arcs (because any component C with an arc class that can have the expunged component E as its destination must be visited to ensure it does not reference E – that could be many nodes for many arc types).

The overhead for weak pointers is

  • a small control structure and the use of atomic counter increments/decrements to update it.
  • the cost of updating code to call lock() and check validity before dereferencing.

This seems negligible compared to potentially expensive debugging.

  • Arcs alternative 0: keep std::reference_wrapper<T>.
  • Arcs alternative 1: switch to std::weak_pointer<T>.

0 voters

Nodes should be held in a multimap, not a set

Now that we have some experience with the graph resource, we have observed a need for fetching graph nodes by their type in addition to by their UUID. As the number of nodes in a resource becomes large (as expected in some existing and upcoming projects), iterating over all the nodes becomes expensive.

Instead of the resource holding std::set<std::shared_pointer<Component>>, we propose additional indexing of nodes by their (sub)class.

Alternative 1: Manual indexing

Besides the multi-index container, we also considered a (semi-)manually-maintained lookup for node type. This approach could keep the std::set and simply add a map from Component type-indices to sets of components of that type.

The resource could observe operations to keep this auxiliary map up-to-date, so this approach would not necessarily require any changes to existing subclasses of smtk::graph::Resource. However,

  1. This approach relies on operations properly reporting all changes, not just “top-level” changes.
  2. There would be no facility for additional indexes should the need arise.

Alternative 2a: Multi-index container

The simplest use of the multi-index container is to just replace the graph-resource’s current std::set with a boost::multi_index container. The container would be indexed on UUID and each node’s type-index (a hash of the type name).

Because node types do not change, developers would generally not need to make large changes to be compatible with the difference in the container type. However, this would require existing code using the graph resource’s node set directly to be updated to a new iteration style.

Alternative 2b: Parameterized multi-index container

If we are careful with the design, subclasses could be provided the ability to add indices relevant to their use cases. This would work by making the node storage a template parameter (and perhaps moving it out of the graph::ResourceBase class into graph::Resource) in addition to the TypeTraits parameter.

This approach could allow existing subclasses of graph::Resource to specify a std::set for the nodes and perhaps avoid any incompatible API changes. However, this would take some work to implement since the base graph resource would now need to handle different containers in the methods it provides.

  • Nodes alternative 0: no change.
  • Nodes alternative 1: add a map from type-info to nodes of that type (keeping the std::set of nodes).
  • Nodes alternative 2a: swich the std::set of nodes to boost::multi_index.
  • Nodes alternative 2b: swich the std::set of nodes to a template parameter (that subclasses could provide).

0 voters

2

Hi all! As an update, changes have now been made to the graph resource:

  1. The way arcs are implemented has been refactored. Endpoint nodes are held by raw pointer as experiments showed that weak pointers were too slow for the scales we already operate at. However, maintaining relationships is now much simpler as a single arc class/struct can (not must) provide access to traversal in both directions.

  2. Nodes are now stored using whatever the graph-traits NodeContainer type-alias specifies. If no type-alias is present, then smtk::graph::NodeSet is used. The graph resource accesses nodes through an API that allows multiple indexes to be updated.

You can see updated documentation on the changes here.

1 Like