网格对象缓存

Question

我正在为一个对象(Mesh)创建一个缓存系统，创建起来非常昂贵。Mesh可以使用哈斯可键(MeshKey)中的少量信息创建。创建网格有多种方法，关键必须识别正在使用的方法，并将参数提供给创建函数。客户端代码必须能够添加创建方法。缓存如下所示：

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;
};

从本质上说，缓存是一个MeshKey，从中识别和返回一个特定的Mesh。如果它还不存在，那么创建它并缓存它。这意味着键既代表了创建网格的方法，也代表了用于创建网格的参数(例如，一个键可以表示具有特定半径的球面网格，另一个表示具有三个边长的框)。

最大的问题是MeshCache::_create。如果知道一组创建方法，我可以将索引映射到生成器函数，或者将std::visit映射为所有可能的MeshKey类型的std::variant。由于用户必须能够添加自己的创建模式，所以我决定使用多态性：

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可以简单地返回key.create()。

这使我可以创建新类型的键，如下所示：

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);
    }
};

不幸的是，这导致了键本身中的值与对象创建之间的一些丑陋的耦合--如果创建对象需要使用其他对象，这些对象通常必须传递到派生键的构造函数中。我最初的几次解耦尝试导致了RTTI和两组多态类(键和生成器)的一些不吸引人的使用，这些类必须由客户端编写，然后在缓存对象中注册。这使得逻辑变得复杂，而且通常是一个混乱的解决方案。

我在这个设计中看到的问题是：

• 网格生成码与网格识别(键控)码之间的严重耦合
• 依赖于多态结构来完成映射键的工作(这通常应该像动态键一样)，需要原型模式(clone函数)和堆分配(动态大小的键)。
• 虽然我想象一些RTTI的使用可能会进入最终的代码，但我在相等操作符中使用typeid感觉是重复的，很可能会在以后产生错误。

有没有更优雅的解决方案？与性能相比，我通常更倾向于可读性和可维护性，直到分析发现问题为止。

Answer 1

与性能相比，我通常更倾向于可读性和可维护性，直到分析发现问题为止。

这是一种很好的心态。我认为代码中缺乏优雅的原因是类有太多或没有正确的职责。例如，MeshKey看起来像一个基类，但实际上它是一个针对具体键对象的std::unique_ptr的包装器，而_MeshKey是实际的基。派生类也不必担心与不同的派生类型进行比较。使每个类尽可能简单。

您探索了使用std::variant和使用多态性，但是您忽略了另一种可能性:只需在键类型上模板化缓存本身。这简化了缓存，因为它只需要处理一种特定类型。考虑：

class MeshCache {
public:
    template <typename Key>
    static const Mesh& get(const Key& key) {
        auto& cache = _cache<Key>;

        if (auto it = cache.find(key); it != cache.end()) {
            return it->second;
        } else {
            return cache.try_emplace(key, key.create()).first->second;
        }
    }

private:
    template <typename Key>
    inline static std::unordered_map<Key, Mesh> _cache;
};

现在，您不再需要派生类或std::unique_ptrs。因此，SphereMeshKey变成：

struct SphereMeshKey {
    float radius;
    Mesh create() const {
        return ...;
    }
};

使用缓存的代码如下所示：

auto& earthMesh = MeshCache::get(SphereMeshKey{6.371e6});

真正的魔力在于用于声明inline的_cache关键字:它将确保为您使用的每个类型的Key实例化一个_cache<Key>，如果多个翻译单元导致同一个_cache<Key>被实例化，链接器将将它们合并为一个。

上面的代码还有另外两个优化：get()返回一个对Mesh的引用，而不是一个副本，它还使用find()而不是count()+at()，后者将搜索映射两次而不是一次。

Answer 2

网格获取( const & key) const{返回_cache.count(键)？_cache.at(键)：_cache.try_emplace(键，_create(键))。

有些事情：

• count在地图中查找键，然后at再进行第二次查找。
• 我们应该添加一些错误处理，以防try_emplace失败--即使是一个assert也可以。
• 我不认为有什么好的理由来掩盖get()可能改变缓存的事实。函数不应该是const，_cache成员变量不应该是mutable。
• 我们真的应该按值返回一个Mesh (即复制它)，而不是返回一个const&甚至一个指针吗？

struct _MeshKey {
...

class MeshKey {
...

struct SphereMeshKey: public _MeshKey {
...

嗯。我把它称为MeshGenerator而不是MeshKey，因为我认为这是它的主要目的。似乎用户总是必须将适当的MeshKey (或MeshGenerator)传递给get()函数.因此，我不确定是否有理由将整个生成器对象存储在缓存中。我们可能需要一个简单的std::unordered_map<std::size_t, Mesh>代替。

我认为缺少的是确保生成器类对结果的std::size_t哈希值有贡献，如下所示：

struct MeshGenerator {
    virtual ~MeshGenerator() { } // note: important!
    virtual std::size_t hash() const = 0;
    virtual Mesh create() const = 0;
};

struct SphereMeshGenerator : MeshGenerator {
    
    SphereMeshGenerator(float radius): _radius(radius) { }
    
    std::size_t hash() const override {
        
        using std::literals;
        auto const hashGenerator = std::hash<std::string_view>()("sphere"sv);
        auto const hashRadius = std::hash<float>()(_radius);
        
        return combineHashes(hashGenerator, hashRadius);
    }
    
    ...
    
};

其中combineHashes()是这样的：

inline std::size_t combineHashes(std::size_t a, std::size_t b) {
    return a ^ (b + 0x9e3779b9 + (a << 6) + (a >> 2)); // note: algorithm pilfered from boost hash_combine
}

因此，为了使用它，我们会做一些如下的事情：

    auto cache = MeshCache();
    auto const generator = SphereMeshGenerator(1.f);
    auto const mesh = cache.get(generator);

get()可能是：

    Mesh const& get(MeshGenerator const& gen) {
        
        auto const key = gen.hash();
        
        if (auto const entry = _cache.find(key); entry != _cache.end())
            return entry->second;
        
        auto mesh = gen.create();
        
        auto [entry, inserted] = _cache.insert({ key, std::move(mesh) });
        assert(inserted);
        
        return entry->second;
    }

注意，这里可能不需要继承，除非您需要在同一个容器中存储不同的MeshGenerator类型。否则，我们可以将get()改为模板函数。

(如果我们真的想要的话，我们甚至可以将密钥和生成器函数拆分为单独的std::size_t和std::function<Mesh(void)>参数)。

(或者照星宿星的话去做。我不知道那是件事。)