避免已知类型数组中的 vtable 指针开销

问题描述 投票：0回答：1

这会很长，但请耐心等待。

假设我正在编写一个处理动物的程序

struct animal {
    virtual ~animal() {
    }

    virtual std::string get_noise() const = 0;
};

struct dog : public animal {
    std::string get_noise() const override {
        return "Woof";
    }
};

struct cat : public animal {
    std::string get_noise() const override {
        return "Meow";
    }
};


animal
基类很有用，因为现在我们可以编写适用于任何类型的
animal
的函数。

void make_noise(const animal& target) {
    std::cout << target.get_noise() << std::endl;
}

我们还可以制作一个工厂函数，在给定类型时返回正确的动物。

std::unique_ptr<animal> make_animal(const std::string& type) {
    if (type == "dog") {
        return std::unique_ptr<animal>(new dog);
    } else {
        return std::unique_ptr<animal>(new cat);
    }
}

让我们实例化一些动物来检查一切是否按预期工作。

dog puppy;
make_noise(puppy);

std::unique_ptr<animal> kitty = make_animal("cat");
make_noise(*kitty);

好极了。我喜欢猫。事实上，我需要一个包含 100 亿个数组的数组。

std::vector<cat> cats(10000000000);
make_noise(cats[0]);

但是哦不！我们的程序现在抛出异常。由于 vtable 指针，

cat
类的大小为 8 个字节，存储 100 亿只小猫将需要 80 GB 的内存。伤心！

但我不会放弃，有解决办法！让我们从两个派生类中删除

animal
基类开始。

struct dog {
    std::string get_noise() const {
        return "Woof";
    }
};

struct cat {
    std::string get_noise() const {
        return "Meow";
    }
};

现在的挑战是，我们如何实现

make_noise
和
make_animal
功能？我们可以编写一个通用的 
make_noise
函数，但它的参数类型在编译时并不总是已知的。我们需要一些类型来表示一个动态的动物实例，但由于通过继承实现的多态性被证明是不好的，我们必须即兴发挥。

从 Rust 中的胖指针中获取灵感，让我们手动实现一个 vtable！

struct animal_vtable {
    std::string (*get_noise)(const void*);
};

template<class T>
static std::string get_noise(const void* ptr) {
    return static_cast<const T*>(ptr)->get_noise();
}

struct animal {
    const void* value;
    const animal_vtable* vtable;

    template<class T>
    animal(const T& value) {
        static animal_vtable vtable = {
            ::get_noise<T>,
        };

        this->value = &value;
        this->vtable = &vtable;
    }

    std::string get_noise() const {
        return vtable->get_noise(value);
    }
};

让我们暂时忽略这现在只适用于

const
动物，而且我们需要另一个与
animal
基本相同的类，除了使用非常量动物指针，如果我们想让它为那些动物工作以及。

至少现在我们可以再次实现我们的

make_noise
功能。

void make_noise(animal target) {
    std::cout << target.get_noise() << std::endl;
}

这看起来还不错，现在它适用于只有 10 GB 内存的 100 亿只猫。

dog puppy;
make_noise(puppy);

std::vector<cat> cats(10000000000);
make_noise(cats[0]);

但是我们还有另一个问题，实现

make_animal
。我们不能简单地返回一个 
std::unique_ptr<animal>
，因为 
animal::value
指针不会被正确销毁。我们必须向我们的 vtable 添加一个析构函数，并且还有另一个与
animal
基本相同的类，除了从我们的 vtable 调用析构函数的析构函数。

此时代码变得笨拙。我对自定义“胖”指针与标准库类型（如 

std::unique_ptr
）的工作效果不满意。使用手动 vtables，感觉就像我们又在用 C 编程了。

所以最后，对于我的问题，有没有更好的方法？我不介意编写一些样板模板元编程魔术，如果这有助于保持我的其余代码干净的话。

C++ 据说是一种您“不用为不用的东西付费”的语言，但我不得不为在我的 

cats
数组中存储 vtable 100 亿次而付费，即使我知道编译时 vtable 将始终是猫的 vtable，否则有可能将我的代码变成一团乱麻。

谢谢你们坚持到最后

我要睡觉了

c++ templates polymorphism vtable
1个回答
0
投票

由于 vtable 指针，cat 类的大小为 8 个字节，存储 100 亿只小猫将需要 80 GB 的内存。 ... 所以最后，对于我的问题，有没有更好的方法？我不介意编写一些样板模板元编程魔术，如果这有助于保持我的其余代码干净的话。

如果在每个对象中存储对象类型不切实际，另一种方法是将对象类型存储在指针中。

在 64 位地址空间中，您可以以指针编码对象类型的方式存储不同类型的对象。

比如说，您想要处理多达 16Mi 的 256 字节猫和多达 8Mi 的 512 字节狗 - 每个对象类型 4GiB。您 reserve 一个 8GiB 区域的虚拟地址空间，带有 

mmap
，并从该区域的前半部分分配猫，从第二部分分配狗。由于需求分页，页面框架（物理 RAM）仅分配给存储到该区域的页面。

指向对象的指针是区域基地址和偏移量的总和。每个对象类型 4GB，偏移量的高 32 位自然编码对象类型，

0
用于猫，
1
用于狗。

如果没有多态基类，指向对象的泛型指针在使用前必须向下转换。

这是工作草图：

#include <memory>
#include <new>
#include <iostream>
#include <cstdint>

#include <boost/interprocess/anonymous_shared_memory.hpp>
#include <boost/interprocess/mapped_region.hpp>

struct Animal {
    void destroy();
    std::string get_noise();
};

struct AnimalDeleter {
    void operator()(Animal* a) const;
};

template<class T>
using AnimalPtr = std::unique_ptr<T, AnimalDeleter>;

struct Cat : Animal {
    std::string get_noise() { return "Meow"; }
    ~Cat() { std::cout << "~Cat\n"; }
};

struct Dog : Animal {
    std::string get_noise() { return "Woof"; }
    ~Dog() { std::cout << "~Dog\n"; }
};

struct ObjectPool {
    static ObjectPool* instance;

    static constexpr auto OBJECT_POOL_SIZE = uintptr_t{1} << 32;
    static constexpr auto OBJECT_TYPES = 2;
    boost::interprocess::mapped_region mmap_region_;
    size_t allocated_[OBJECT_TYPES]{};

    ObjectPool() {
        if(instance)
            throw;
        instance = this;
        mmap_region_ = boost::interprocess::anonymous_shared_memory(OBJECT_TYPES * OBJECT_POOL_SIZE);
    }

    ~ObjectPool() {
        instance = 0;
    }

    template<class T>
    void destroy(T& t) {
        t.~T();
        // Maintain the pool.
    }

    template<class T>
    AnimalPtr<T> create(uintptr_t type) {
        auto type_region = reinterpret_cast<uintptr_t>(mmap_region_.get_address()) + OBJECT_POOL_SIZE * type;
        if(OBJECT_POOL_SIZE - allocated_[type] < sizeof(T))
            throw std::bad_alloc();
        T* p = reinterpret_cast<T*>(type_region + allocated_[type]);
        allocated_[type] += sizeof(T);
        return AnimalPtr<T>(new (p) T);
    }

    AnimalPtr<Cat> create_cat() { return create<Cat>(0); }
    AnimalPtr<Dog> create_dog() { return create<Dog>(1); }

    void destroy(Animal* a) { visit<void>(a, [this](auto& a2) { this->destroy(a2); }); }

    template<class R, class F>
    R visit(Animal* a, F&& f) const {
        auto offset = reinterpret_cast<uintptr_t>(a) - reinterpret_cast<uintptr_t>(mmap_region_.get_address());
        auto type = offset / OBJECT_POOL_SIZE;
        switch(type) {
        case 0: return f(*static_cast<Cat*>(a));
        case 1: return f(*static_cast<Dog*>(a));
        default: throw;
        }
    }
};

ObjectPool* ObjectPool::instance = 0;

inline void AnimalDeleter::operator()(Animal* a) const {
    if(a)
        ObjectPool::instance->destroy(a);
}

inline std::string Animal::get_noise() {
    return ObjectPool::instance->visit<std::string>(this, [](auto& a2) { return a2.get_noise(); });
}

int main() {
    ObjectPool pool;

    auto cat = pool.create_cat();
    std::cout << cat->get_noise() << '\n';
    AnimalPtr<Animal> cat2 = move(cat);
    std::cout << cat2->get_noise() << '\n';

    auto dog = pool.create_dog();
    std::cout << dog->get_noise() << '\n';
    AnimalPtr<Animal> dog2 = move(dog);
    std::cout << dog2->get_noise() << '\n';
}

输出：

Meow
Meow
Woof
Woof
~Dog
~Cat
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.