Strategy to sharing data across an object tree without using static members

Question

I am in a situation where I need to share data across many instances of a polymorphic object tree, but then again, I need the shared data to be "per-tree" so using static class members in the base class is no really an option.

I don't want to "overburden" each instance with extra member pointers to the shared data, so my current approach (considering I use trees) is to have the shared data as members of the tree root node, and each access to shared data goes through a chain of indirections depending on the depth of the particular node through which "tree global" data is accessed.

Since there are scenarios where shared data will be very frequently (millions per second... at least that's what is intended) accessed, I wonder if there is some design pattern that can help me avoid the indirections to reach to the root node while still not introducing extra bloat to the footprint of objects.

While it is possible to "cache" the root node pointer as a local for say a tight loop that accesses shared data, there are many scenarios where functionality will cascade along tree nodes and even switch trees in the process, so caching the root node pointer is applicable only in a narrow context.

• note the mention of static members does not limit the scope of the implementation to C++, I added the C tag as well because at this point I am open to any ideas.

Answer 1

All methods to interact with a tree node take as their first parameter a pointer-to-root.

A flyweight wrapper class can hide this implementation detail, where you access the tree nodes through an opaque class with a real tree node pointer plus a poimter to root in it. If you ask for a child, it returns another flyweight.

Now your tree lacks the extra pointer, but the interface class has the extra pointer.

If your tree nodes are immutable (logically) you can even copy their state to reduce indirection costs.

template<class Data>
struct internal_tree {
  Data d;
  std::unique_ptr<internal_tree> left;
  std::unique_ptr<internal_tree> right;
};

template<class Data>
struct flyweight_tree {
private:
  internal_tree* internal = nullptr;
  internal_tree* root = internal;
  flyweight_tree(internal_tree* t, internal_tree* r):internal(t),root(r) {}
public:
  flyweight_tree() {}
  flyweight_tree(internal_tree* r):internal(r) {}
  flyweight_tree left() const { return { internal->left.get(), root }; }
  flyweight_tree right() const { return { internal->right.get(), root }; }
};

now our actual internal_tree data structure does not store a pointer-to-root. Code that uses it accesses it through a flyweight_tree, which stores the pointer-to-root, but that pointer-to-root is only stored at the point of access, never long-term stored.

If you want a parent, you could even implement it as a flyweight, where the flyweight_tree stores a std::vector of pointers-to-parent (instead of root). This saves another pile of memory in your tree nodes (no pointer-to-parent, yet everyone using it can get parent, because they use it through the flyweight_tree).

We could either implement most of the work in the internal_tree, where it takes as arguments the information that flyweight_tree stores, or we could implement most of the tree logic in flyweight_tree and leave internal_tree as a compact "long-term storage" structure.

Answer 2

The possibilities I can think of are :

• If your number of roots is limited, instead store an offset (for instance in a uint8_t) to a static array that has your roots. For instance if you only have 5-10 roots, no need to store a whopping 64 bits per node.
• Why not run each "tree" in its own process (at the OS level) ? This way each root can be stored as static data and accessed globally.
• If you can bound the number of nodes, maybe you could use a special allocator: allocate your root first at the beginning of a given memory boundary, for instance 0x0010000, 0x0020000, etc... and then retrieve the address of the root with a simple substraction / bit shift for each node ? But you have to be able to ensure that you can allocate all your nodes within the memory area of each tree.