I'm creating a cache system for an object (Mesh
) that is expensive to create. A Mesh
can be created using a small amount of information in a hashable key (MeshKey
). There are multiple methods of creating meshes, and the key must identify which method is being used and supply the parameters to the creation function. The client code must be able to add creation methods. The cache looks like this:
class MeshCache {
public:
Mesh get(const MeshKey& key) const {
return _cache.count(key) ? _cache.at(key) : _cache.try_emplace(key, _create(key)).first->second;
}
private:
Mesh _create(const MeshKey& key) const {
return ...;
}
mutable std::unordered_map<MeshKey, Mesh> _cache;
};
Essentially, the cache is handed a MeshKey
from which to identify and return a specific Mesh
. If it doesn't yet exist, create it and cache it. This means the key represents both the method that should be used to create the mesh and the parameters used to create it (for example, one key could represent a sphere mesh with a specific radius, another a box with three side lengths).
The big problem is MeshCache::_create
. If the set of creation methods were known, I could map an index to a generator function, or std::visit
a std::variant
of all the possible MeshKey
types. As the user must be able to add their own creation modes, I decided polymorphism was the way to go:
struct _MeshKey {
virtual size_t hash() const = 0;
virtual bool operator==(const _MeshKey& rhs) const = 0;
virtual Mesh create() const = 0;
virtual std::unique_ptr<_MeshKey> clone() const = 0;
};
class MeshKey {
public:
MeshKey(std::unique_ptr<_MeshKey>&& x): key(std::move(x)) {}
MeshKey(const MeshKey& other): key(other.key->clone()) {}
size_t hash() const {
return key->hash();
}
bool operator==(const MeshKey& rhs) const {
return *key == *rhs.key;
}
Mesh create() const {
return key->create();
}
private:
std::unique_ptr<_MeshKey> key;
};
namespace std {
template <> struct hash<MeshKey> {
size_t operator()(const MeshKey& x) const noexcept { return x.hash(); }
};
}
MeshCache::_create
could then simply return key.create()
.
This lets me create new types of keys like this:
struct SphereMeshKey: public _MeshKey {
SphereMeshKey(float radius): radius(radius) {}
float radius;
size_t hash() const override { return std::hash<float>()(radius); }
bool operator==(const _MeshKey& rhs) const override {
if (typeid(*this) != typeid(rhs)) {
return false;
}
auto obj = static_cast<const SphereMeshKey&>(rhs);
return radius == obj.radius;
}
Mesh create() const override {
return ...; // Generate sphere mesh
}
std::unique_ptr<_MeshKey> clone() const override {
return std::make_unique<SphereMeshKey>(radius);
}
};
Unfortunately, this resulted in some ugly coupling between the values in the key itself and the object creation -- if creating the object required the use of other objects, those must typically be passed into the derived key's constructor. My first several attempts at decoupling resulted in some unattractive use of RTTI and two sets of polymorphic classes (keys and generators) which had to be authored by the client and then registered with the cache object. This complicated the logic and was generally a messy solution.
The problems I see with this design are:
- Heavy coupling between the mesh generation code and the mesh identification (keying) code
- Relying on a polymorphic structure to do the job of a map key (which usually should behave like a POD) requires prototype pattern (
clone
function) and heap allocation (dynamically sized key) - While I imagine some use of RTTI will likely make its way into the final code, my use of
typeid
in the equality operator felt repetitive and likely to create bugs down the road
Is there a more elegant solution? I generally favor readability and maintainability over performance until profiling reveals issues.