Как реализовать объект кэша переменного размера, чтобы уменьшить выделение памяти в C ++?

Question

Перед выступлением люди отрывают мне голову: да, я сделал профилирование, прежде чем спросить:)

Я снова смотрю на мой контейнер одного типа , и хотя у меня есть решение, которое работает, производительность низкая, поскольку каждый тип кэшируемых элементов приводит к отдельному выделению на куча (что конечно дорого).

Основываясь на статическом анализе входных данных моей программы, я нашел способ узнать общий размер, необходимый для всех объектов, которые могут быть помещены в мой объект кэша, который обходит. По сути, у меня есть список объектов, которые могут быть созданы в данном объекте кэша, поэтому я знаю, какой размер того, что мне может понадобиться для кэширования, заранее, но не во время компиляции - только во время выполнения.

По сути, я хотел бы сделать то, что делает boost::make_shared - получает один блок памяти и создает биты shared_ptr, а также управляемый объект в том же блоке памяти.

Мне не нужно беспокоиться о сохранении поведения копирования, поскольку объект кэша не может быть скопирован и передан по указателю клиентами (обычно он хранится в чем-то вроде ptr_vector или std::auto_ptr).

Однако я не знаком с тем, как именно можно реализовать такой контейнер, а именно с тем, как следовать ограничениям на выравнивание и тому подобное.

В псевдокоде, что я хотел бы сделать:

//I know a lot of what's in here is not portable -- I need to run only on x86
//and x64 machines. Yes, this couple of classes looks hacky, but I'd rather
//have one hacky class than a whole programfull :)

class CacheRegistrar
{
    //Blah blah
public:
    //Figures out what objects will be in the cache, etc
    const std::vector<std::size_t>& GetRequiredObjectSizes() const;
    //Other stuff...
    template <typename T>
    void RegisterCacheObject();
    template <typename T>
    std::size_t GetObjectIndex() const;
    // etc.
};

class CacheObject;

std::auto_ptr<CacheObject> CacheObjectFactory(const CacheRegistrar& registrar)
{
    //Pretend this is in a CPP file and therefore CacheObject is defined...
    const std::vector<size_t>& sizes(registrar.GetRequiredObjectSizes());
    std::size_t sumOfCache = std::accumulate(sizes.begin(), sizes.end());
    sumOfCache += sizeof(CacheObject);
    boost::scoped_array<char> buffer(new char[] sumOfCache);
    CacheObject *obj = new (reinterpret_cast<void *>(buffer.get())) CacheObject;
    buffer.release(); //PSEUDOCODE (boost::scoped_array has no release member);
    return std::auto_ptr<CacheObject>(obj); //Nothrow
}

class CacheObject
{
    CacheRegistrar *registrar; //Set by my constructor
public:
    template<typename T>
    T& Get()
    {
        char * startOfCache = reinterpret_cast<char *>(this) + 
            sizeof(CacheObject);
        char * cacheItem = startOfCache + registrar->GetObjectIndex<T>();
        return *reinterpret_cast<T*>(cacheItem);
    }
};

Здесь звучит моя общая концепция? Есть ли лучший способ сделать это?

Answer 1

Но сначала прочитайте эту статью Андрея Александреску о том, что, по его мнению, он должен был написать в этой главе - способ построения куч, используя Слои кучи (по-настоящему вашими),Я использовал Heap Layers для построения Hoard , DieHard и DieHarder , а также пользовательских распределителей, используемых в нашей статье OOPLSA 2002, Пересмотр пользовательской памятиРаспределение , которое также следует прочитать, прежде чем приступать к созданию настраиваемого распределителя.

Answer 2

Посмотрите на распределитель мелких объектов Loki.

Быстрое поиск в Google, который не дал никаких прямых документов, ориентированных на человека.Есть документация, сгенерированная DOxygen, но не особенно поддающаяся уловлению.Тем не менее, проект и реализация документированы в «Современном C ++ Design» Андрея Александреску.

Если вы просто хотите эффективную переработку для объектов данного класса, тогда рассмотрите простой свободный список - возможно, свободный списоксырые куски хранения.

Cheers & hth.,

Answer 3

Ключевая проблема, которую я вижу, это возвращение

auto_ptr

для памяти, выделенной не по умолчанию. Вы можете решить эту проблему, определив подходящее перегруженное удаление, но лучше определить свою собственную функцию уничтожения как часть фабрики. Если вы сделаете это, вы также локализуете управление памятью в классе Cache, предоставляя вам больше свободы для повышения производительности, локальной для этого класса. Конечно, использование умного указателя для управления памятью - хорошая идея; что вам нужно сделать, это определить свой собственный распределитель и определить smart_ptr для его использования.

Для справки, другой подход к управлению пользовательским распределением - это определение нового пользовательского оператора. То есть Такого рода вещи:

struct Cache
{
    void* allocate(size_t size)
    {
        size_t blockSize = sizeof(size_t) + size;
        // Placeholder: do what ever appropriate to blocks of size 'blockSize'
        return malloc(blockSize);
    }
    void destroy(void* p)
    {
        size_t* block = reinterpret_cast<size_t*>(p);
        size_t blockSize = *block;
        // Placeholder: do what ever appropriate to blocks of size 'blockSize'
        free(p);
    }

};
Cache cache;


void* operator new (size_t size, Cache& cache )
{
    return cache.allocate(size);
}

struct CacheObject 
{
    void operator delete(void* p)
    {
        cache.destroy(p);
    }
};


CacheObject* co = new (cache) CacheObject;