Сеанс низкоуровневой оптимизации использования памяти в программах на языке С++ с полным разоблачением

«В вычислительной технике оптимизацией называется процесс модификации системы для улучшения её эффективности. Система может быть одиночной компьютерной программой, набором компьютеров или даже целой сетью, такой как Internet.

Несмотря на то, что слово „оптимизация“ использует тот же самый корень, что и слово „оптимальный“, процесс оптимизации весьма редко порождает оптимальную систему, поэтому всегда имеются уступки (tradeoffs).

Оптимизация должна проводиться с осторожностью. Тони Хоар впервые произнёс, и Дональд Кнут впоследствии часто повторял известное высказывание: „Преждевременная оптимизация — это корень всех бед“. Очень важно иметь для начала озвученный алгоритм и работающий прототип.»
© wiki

В этой статье мы попытаемся заставить наши алгоритмы работать быстрее, используя методики низкоуровневой оптимизации выделения памяти на С++. Нужно понимать, что все описанные в статье методики должны применятся с крайней осторожностью и в исключительных случаях, поскольку за внедрение любых элементов низкоуровневой оптимизации часто приходится платить гибкостью, переносимостью, понятностью или масштабируемостью приложений. Но если у вас как раз тот случай, когда отступать некуда, тогда — добро пожаловать.

1. Оптимизация «Конкретных Фабрик»

Я думаю, многие неоднократно сталкивались с классическим паттерном «Фабрика», или «Конкретная Фабрика», в терминологии GoF:

<code style="display:block!important;">struct IObject
{
     virtual ~IObject(){}
     virtual void DoIt()=0;
};
class CFactory
{
public:
void CreateSmth(int objType, std::auto_ptr<IObject> * pResult)
    {
        if (iValue<0)
        {
            pResult->reset(new CObject1);
        }
        else
        {
            pResult->reset(new CObject2);
        }
    }
};</code>

Паттерн исключительно хорош для избавления от бесконечных if’ов и switch’ей по всему коду, но имеет одну неприятную особенность, связанную с чрезмерным использованием динамической памяти, что иногда неприятно отражается на производительности С++ программ. Мы постараемся отучить его от этого, при определенных оговорках, естественно.

Посмотрим еще раз на процесс использования фабрики:

Для оптимизации описанного жизненного цикла продукции можно применить следующие утверждения:

1) Специальная форма оператора new — placement new позволяет создавать объекты в произвольном, «сыром» буфере. Например, так:

<code style="display:block!important;">char buffer[1024];
new(buffer)CObject(a,b,c);</code>

Очень полезная вещь, учитывая, что мы можем выделить буфер более эффективно, чем стандартная реализация new. Правда, использование placement new тоже вносит некоторые трудности в жизнь программиста:

a) Сырой буфер должен быть выровнен на границу, зависимую от платформы;
b) Деструктор созданного объекта должен быть вызван вручную.

2) Использование стека является удачной альтернативой хипу. Было бы намного более заманчиво использовать в качестве контейнера буфер на стеке, т.е. использовать

<code style="display:block!important;">MyWrapperAroundLocalBuffer<ObjectSize, IObject> product;</code>

вместо оригинального

<code style="display:block!important;">std::auto_ptr<IObject> product;</code>

Основная проблема создания контейнера на стеке заключается в том, что в стандартном С++ невозможно выделить на стеке объект произвольного размера (неизвестного на этапе компиляции).

3) Но, поскольку наша фабрика — конкретная (а не абстрактная), и мы знаем обо всех типах ее продукции, то мы определенно сможем узнать максимальный размер объекта-продукции на этапе компиляции. Например, используя списки типов:

<code style="display:block!important;">//--------------------------------
// typelist basics
//--------------------------------
template<class Head, class Tail>
struct Node
{
};
struct NullNode
{
};</code>

Мы можем написать рекурсивную compile-time функцию для вычисления максимального размера объекта, из числа типов, находящихся в списке:

<code style="display:block!important;">template <class List>
struct GetMaxSize
{
};
template <class Head, class Tail>
struct GetMaxSize<Node<Head, Tail> >
{
    static const size_t TailSize = GetMaxSize<Tail>::Result;
    static const size_t Result = (TailSize > sizeof(Head) ) ? TailSize : sizeof(Head);
};
template <>
struct GetMaxSize<NullNode>
{
    static const size_t Result = 0;
};</code>

После чего мы можем создать список из всех возможных типов продукции для фабрики CFactory:

<code style="display:block!important;">   typedef utils::Node<CObject1>, 
                 utils::Node<CObject2>, 
                      utils::NullNode
                     > 
                > ObjectList;
   static const size_t <strong>MaxObjectSize</strong> = utils::GetMaxSize<ObjectList>::Result;</code>

Как результат — теперь мы на 100% уверены, что любой произведенный объект наверняка поместится в буфере размера MaxObjectSize (если мы правильно написали список типов, конечно):

<code style="display:block!important;">   char buffer[ MaxObjectSize ];</code>

Этот буфер можно легко выделить в стеке.

4) Поскольку наш контейнер должен уметь хранить в себе объекты различных типов, мы вправе потребовать от них помощи в виде поддержки соответствующего интерфейса:

<code style="display:block!important;">struct IManageable
{
    virtual ~IManageable(){}
    virtual void DestroyObject(void * pObject)=0;
    virtual void CreateAndSwap(void * pObject, int iMaxSize)=0;
    virtual void CreateAndCopy(void * pObject, int iMaxSize)=0;
};</code>

Т.е. объект, который хочет жить в нашем контейнере, должен уметь:

a) удалять объекты своего типа по определенному адресу;

b) использовать технологию Create And Swap для передачи владения (опционально);

c) использовать технологию Create And Copy для создания копии объекта (опционально).

Структуру контейнера можно схематично представить следующим образом:

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

a) Указатель на IManageable для управления жизненным циклом объекта;

b) Указатель на пользовательский интерфейс IObject, методы которого, собственно, пользователь фабрики и хотел бы вызывать.

Поскольку достаточно трудоёмко добавлять для каждого класса продукции поддержку интерфейса IManageable, имеет смысл написать шаблон manageable, который будет делать это автоматически за нас:

<code style="display:block!important;">// manageable control flags (iFlags field)
const int allow_std_swap = 1; 
const int allow_copy     = 2;
const int allow_all      = 3;


// class manageable: wrapper, provides binary interface to manage object's life
template<class ImplType, int iFlags>
class manageable:public IManageable, public ImplType
{
    typedef manageable<ImplType, iFlags> ThisType;

    virtual void DestroyObject(void * pObject)
    {
        ((ThisType*)pObject)->~ThisType();
    }
    // CreateAndSwap
    template<int iFlags>
    void CreateAndSwapImpl(void * /*pObject*/, int /*iMaxSize*/)
    {
        throw std::runtime_error("Swap method is not supported");
    }

    template<>
    void CreateAndSwapImpl<allow_std_swap>(void * pObject, int /*iMaxSize*/)
    {
        ThisType * pNewObject = new(pObject)ThisType();
        pNewObject->swap(*this);
    }

    virtual void CreateAndSwap(void * pObject, int iMaxSize)
    {
        if (sizeof(ThisType)>iMaxSize)
            throw std::runtime_error("Object too large: swap method failed");
        CreateAndSwapImpl<iFlags & allow_std_swap>(pObject, iMaxSize);
    }

    // CreateAndCopy
    template<int iFlags>
    void CreateAndCopyImpl(void * /*pObject*/, int /*iMaxSize*/)
    {
        throw std::runtime_error("Copy method is not supported");
    }
    template<>
    void CreateAndCopyImpl<allow_copy>(void * pObject, int /*iMaxSize*/)
    {
        new(pObject)ThisType(*this);
    }

    virtual void CreateAndCopy(void * pObject, int iMaxSize)
    {
        if (sizeof(ThisType)>iMaxSize)
            throw std::runtime_error("Object too large: copy method failed");
        CreateAndCopyImpl<iFlags & allow_copy>(pObject, iMaxSize);
    }

public:
    manageable()
    {
    }
    template<class Type0>
    manageable(Type0 param0)
        : ImplType(param0)
    {
    }
};</code>

Шаблон параметризируется типом объекта и флагами, указывающими, какие методы нужно поддерживать. Например, если указать флаг allow_copy, компилятор будет требовать от объекта наличия конструктора копирования для реализации метода CreateAndCopy; аналогично, если указать флаг allow_swap, будет сгенерирована функция CreateAndSwap на основе метода объекта swap, который вам необходимо будет написать самому.

Итак, наша оптимизированная фабрика приобретет следующий вид:

<code style="display:block!important;">class CFastConcreteFactory
{
public:
    typedef utils::Node<utils::manageable<CObject1, utils::allow_copy>, 
                 utils::Node<utils::manageable<CObject2, utils::allow_copy>, 
                      utils::NullNode
                     > 
                > ObjectList;

    static const size_t MaxObjectSize = utils::GetMaxSize<ObjectList>::Result;
    typedef utils::CFastObject<MaxObjectSize, IObject> AnyObject;

    void CreateSmth(int iValue, AnyObject * pResult)
    {
        if (iValue<0)
        {
            pResult->CreateByCopy(utils::manageable<CObject1, utils::allow_copy>());
        }
        else
        {
            pResult->CreateByCopy(utils::manageable<CObject2, utils::allow_copy>());
        }
    }
};</code>

И использовать ее будет так же просто, как и обыкновенную:

<code style="display:block!important;">// usage sample
CFastConcreteFactory factory;
CFastConcreteFactory::AnyObject product;
factory.CreateSmth(-1, &product);
product->DoIt();
// copy sample
CFastConcreteFactory::AnyObject another_product;
product.Copy( &another_product );</code>

Но выполняться сие творение будет значительно быстрее (см. src\win32_fast_object_sample).

Весь исходный код, примеры, performance и unit tests вы можете найти в библиотеке MakeItFaster: src\make_it_faster\.

2. Оптимизация «Ареной»

Второй метод оптимизации, предлагаемый к рассмотрению, значительно проще, однако, область его применения несколько меньше, да и отстрелить им себе ногу значительно легче.

Представим себе, что у нас есть некоторый итерационный алгоритм, повторяющий некоторое действие N раз:

<code style="display:block!important;">int mega_algorithm(int N)
{
   int Count =0;
   for(int i =0 ; i<N; ++i)
   {  
      Count += DoSmth1( );
   }
   return Count;
}</code>

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

1) алгоритм не имеет побочных эффектов;

2) мы можем предсказать максимальный размер динамической памяти, выделяемой на итерацию (назовем его MaxHeapUsage).

В таком случае мы можем воспользоваться паттерном «Арена» для его оптимизации. Суть паттерна довольна проста. Для его реализации мы:

a) подменяем стандартные new/delete своими;

b) перед стартом алгоритма регистрируем некоторый буфер-арену pBuffer размером MaxHeapUsage, и устанавливаем индекс, указывающий на начало свободного места FreeIndex в 0;

c) в обработчиках new выделяем память непосредственно в буфере, сдвигая FreeIndex на величину аллокации. Возвращаем естественно ((char *) pBuffer + oldFreeIndex);

d) после каждой итерации алгоритма устанавливаем FreeIndex в 0, очищая таким образом всю память, которую итерация выделила для своих нужд;

e) после конца алгоритма дерегистрируем наш буфер-арену.

Очень просто и эффективно. Это довольно опасный паттерн, потому что в production code довольно сложно гарантировать условие (1) — но хорошо подходит для около-вычислительных задач (например, из области разработки игр).

При использовании STL контейнеров, конкретный экземпляр арены можно привязать к объекту контейнера так, что объявление и использование контейнера практически не будет отличаться от оригинала, например:

<code style="display:block!important;">    typedef utils::arena_custom_map<int,int, utils::CGrowingArena<1024> >::result Map1_type;
    Map1_type map1;

    for(int i = 0;i<iNumberOfElements;++i)
    {
       map1[i] = i+1;
    }</code>

В данном примере вся память для объекта map1 выделяется из расширяемого буфера CGrowingArena, выделенная память удалится в деструкторе при уничтожении объекта.

Весь исходный код, примеры, performance и unit tests вы можете найти в библиотеке MakeItFaster.

Архив с кодом можно скачать здесь: apriorit.com/...​wnloads/arena-factory.rar

Материал подготовили Виктор Милокум и компания ApriorIT.

Все про українське ІТ в телеграмі — підписуйтеся на канал DOU