Еще одна реализация обобщенных функторов на C++ - Изучение и анализ недостатков

ОГЛАВЛЕНИЕ

Изучение и анализ недостатков

В предыдущем разделе рассматривались требования обобщенных функторов, проблемы конструкции и возможные решения. Мы также добрались до реализации принципов, обычно используемых в существующих библиотеках. В данном разделе мы попытаемся изучить и проанализировать их недостатки и устранить их.

Один из недостатков, найденный в примерах предыдущего раздела, - необходимость выделения динамической памяти (кучи) для экземпляров FunctorImplи MemberFnImpl. Это расточительство – с точки зрения скорости и затрат памяти (так как все универсальные распределители выделяют память с некоторой величиной разбиения, тратя некоторый объем памяти). Исходя из этого, Локи создает оптимизированный специальный выделитель маленьких объектов для своего шаблона функтора. Реализация ускорения содержит прием, позволяющий отклонять выделение кучи для обобщенных функторов для функций-нечленов, но опускается до выделения кучи для обобщенных функторов в остальных случаях.

Как насчет отклонения выделения кучи во всех случаях? Возможное решение – встроить буфер некоторого фиксированного (но настраиваемого) размера в сам шаблон класса функтора и использовать его в качестве пула для выделения памяти. Данная идея использует то, что для всех видов вызываемых сущностей для хранения внутренних данных нужно лишь несколько байтов памяти. Для функтора для статической функции нужно хранить только указатель функции (4 байта в 32-битных системах). Для функтора для функции-члена требуются указатель на экземпляр целевого объекта и указатель на член для функции, которая будет вызываться. Первый снова занимает 4 байта, в то время как размер последнего может меняться от 4 до 20 байтов. Размер внутренних данных для произвольного функтора невозможно предсказать заранее, но из опыта известно, что функторы обычно сконструированы так, чтобы иметь лишь несколько членов-данных или вообще не иметь членов.

Данную идею можно выразить следующим образом:

template <class R, class TList, unsigned int size = 4 * sizeof(void*)> 
class Functor
{
...
struct Typeless {
char buffer_[size];
template <class T, class V> T* init(V const& v)
{ new(&buffer[0]) T(v); }
template <typename T> inline T const& get()
const { return *reinterpret_cast<T const*>(&buffer[0]); }
template <typename T> inline T& get()
{ return *reinterpret_cast<T*>(&buffer[0]); }
}
Typeless val_;
FunImplBase<R, TList> *pimpl_;
public:
...
// функтор для функций-нечленов и произвольных функторов
template <typename F> Functor(F const& fun)
{
pimpl_ = val_.init<FunctorImpl<F> >(fun);
}
...
};

Функторы, сконструированные вышеуказанным образом, тратят некоторый объем в случае минимально потребляющих память функторов для статических функций. Но, во-первых, при использовании выделения кучи некоторые растраты памяти появляются из-за гранулярности выделения памяти. И, во-вторых, выигрыш замечателен – все операции с функторами, участвующие в поддержке копирования по значению (ctors, dtor, operator=) выполняются с огромной скоростью. Данные операции интенсивно используются в важных применениях обобщенных функторов, основанных на сцеплении и связывании функторов.

Для остальной меньшей части случаев, когда sizeof(T) >size (размер), нужно обеспечить в Typeless::init() переключение на нормальный выделитель. Простейший способ сделать это следующий:

template <class R, class TList, 
               unsigned int size = 4 * sizeof(void*)>
class Functor
{
  ...
  struct Typeless {
    char buffer_[size];
    template <class T, class V> T* init(V const& v)
        { new(&buffer[0]) T(v); }
    template <typename T> inline T const& get() const
        { return *reinterpret_cast<T const*>(&buffer[0]); }
    template <typename T> inline T& get()
        { return *reinterpret_cast<T*>(&buffer[0]); }
  }
  template <typename T>
  struct ByValue
  {
    template <typename V> inline static T* init(Typeless& val,
                V const& v) { return val.template init<T>(v); }
    inline static T const& get(Typeless const& val)
                                { return val.get<T>(); }
    inline static T& get(Typeless& val)
                { return val.get<T>(); }
  };
  template <typename T>
  struct NewAlloc
  {
    template <typename V> inline static T* init(Typeless& val,
        V const& v) { return *val.template init<T*>(new T(v)); }
    inline static T const& get(Typeless const& val)
        { return *val.get<T const*>(); }
    inline static T& get(Typeless& val)
        { return *val.get<T*>(); }
  };
  template <typename T>
  struct SelectStored
  {
    typedef typename Select<
    sizeof(T)<=sizeof(Typeless),
    ByValue<T>,
    NewAlloc<T>
    >::Result Type;
    // меташаблон выбора возвращает
    // соответствующий тип в зависимости от его первого аргумента
  };
  struct Stored
  {
    template <typename T, typename V> inline T* init(V const& v)
             { return SelectStored<T>::Type::init(val_, v); }
    template <typename T> inline T const& get() const
             { return SelectStored<T>::Type::get(val_); }
    template <typename T> inline T& get()
             { return SelectStored<T>::Type::get(val_); }
    Typeless val_;
  };
  Stored val_;
  FunImplBase *pimpl_;
public:
  ...
  // функтор для функций-нечленов и произвольных функторов
  template <typename F> Functor(F const& fun)
  {
    pimpl_ = val_.init<FunctorImpl<F> >(fun);
  }
  ...
};

Во фрагменте кода выше val_ используется только для хранения значения T или для хранения только указателя на только что выделенное значение. Замечание: выражение sizeof(T)<=sizeof(Typeless), используемое в меташаблоне Select (выбор), неполное и должно быть улучшено путем добавления расчетов выравнивания.

Обнаружен еще один недостаток. После ввода val_ указатель pimpl_ становится ненужным! Почти всегда известно, что он равен &val_ или встроен в сам val_. Если бы можно было сделать такой выбор, то pimpl_ можно было бы отбросить. Помните, что каждый экземпляр класса, содержащий виртуальные функции (собственные или унаследованные), хранит скрытый указатель на таблицу виртуальных методов, направляющую вызовы виртуальных функций по направлению к нужной функции нужного класса. Если бы можно было обращаться с ним напрямую и извлечь его из экземпляров FunctorImpl и MemberFnImpl в шаблон Functor, можно было бы сделать все нужные вызовы к правильным функциям FunctorImpl или MemberFnImpl и дополнительно сэкономить 4 байта! Конечно, это невозможно сделать, работая непосредственно с механизмом виртуальных функций C++. Однако можно сымитировать данный механизм.

Это известный и весьма мощный метод. В нашем случае его можно применить следующим образом:

template <class R, class TList, 
          unsigned int size = 4 * sizeof(void*)>
class Functor
{
  ...
  struct FunImplBase
  {
    struct VTable
    {
      R (*call_)(Functor const&,
                ...params evaluated from TList...);
      ...
    };
    // VTable vtbl_;
  };
  template <typename F>
  class FunctorImpl : public FunImplBase
  {
    F fun_;
  public:
    FunctorImpl(F const& fun) : fun_(fun) {}
    static R Call(Functor const& f,
              ...params evaluated from TList...)
    {
      FunctorImpl const& this_ =
         f.val_.template get<FunctorImpl const>();
      ... use this_ and params to make a call to fun_ ...
    }
    ...
  };
  template <class P, class MF>
  class MemberFnImpl : public FunImplBase
  {
    P pobj_;
    MF memfun_;
  public:
    MemberFnImpl(P const& pobj, MF memfun) :
                        pobj_(pobj), memfun_(fun) {}
    static R Call(Functor const& f,
                        ...params evaluated from TList...)
    {
      MemberFnImpl const& this_ =
         f.val_.template get<MemberFnImpl const>();
      ... use this_ and params to make ...
      ... a call to memfun_ of pobj_ ...
    }
    ...
  };
  ...
  Stored val_;
  typename FunImplBase::VTable* vptr_;
public:
  ...
  // функтор для функций-нечленов и произвольных функторов
  template <typename F> Functor(F const& fun)
  {
    FunImplBase* pimpl_ = val_.init<FunctorImpl<F> >(fun);
    // отбрасываем pimpl, в данной реализации он не нужен
    static typename FunImplBase::VTable vtbl =
    {
      &FunctorImpl::Call,
      ...
    };
    vptr_ = &vtbl;
  }
  R operator(...params evaluated from TList...)
  {
    return vptr_->call_(*this,
             ...params evaluated from TList...);
  }
  ...
};

Замечание: Это не простой перевод предыдущего примера с виртуальными функциями, а адаптированный перевод, например, указатель на FunImplBase отброшен и заменен указателем на таблицу функций, функция FunctorImpl::Call и т.д. принимает ссылку на экземпляр Functor в качестве первого аргумента (не указатель FunctorImpl, который мог бы быть в простом переводе). Результат выглядит приемлемым.
Сейчас перейдем к проблемам R2 и D2. Можно заметить, что при вызове FunctorImpl::Call и MemberFnImpl::Call из оператора operator() все его аргументы всегда приходится копировать. Так как это вызов через указатель функции (как и вызов виртуальной функции), компилятор не может применять никакие оптимизации. Что если объединить аргументы оператора operator() в кортеж и передать его в FunctorImpl::Call или MemberFnImpl::Call? Издержки копирования аргументов останутся такими же, но FunctorImpl и MemberFnImpl могут стать независимыми от количества аргументов оператора operator(). Это не показано в предыдущих листингах, но наряду с функциями Call, FunctorImplBase, FunctorImpl и MemberFnImpl также должны содержать функции для поддержки семантики значений. Поэтому их независимость от количества аргументов оператора operator()явно улучшает код:

template <class TList> struct CallParms;

... частичные специализации для списков типов разной длины ...

template <typename P1, 
    typename P2> struct CallParms<TYPELIST_2(P1, P2)>
{
  typedef InstantiateH<tTYPELIST_2(P1, P2)> ParmsListType;
  static inline ParmsListType Make(P1 p1, P2 p2)
         { ... make ParmsListType tuple from p1 and p2 ... }
};
template <typename CallType, typename R,
                 class TList> struct FunctorCall;
//... частичные специализации для разных количеств
//    аргументов типов функций ...
template <typename CallType, typename R, P1, P2>
struct FunctorCall<CallType, R, TYPELIST_2(P1, P2)>
{
  typedef InstantiateH<tTYPELIST_2(P1, P2)> ParmsListType;
  template <class Fun> static inline
           R Call(Fun const& fun, ParmsListType& parms)
  {
    return fun(... parameters unpacked from parms ...);
  }
  template <class PObj> static inline R Call(PObj const& pobj,
                         CallType memfun, ParmsListType& parms)
  {
    return (
      (*pobj).*memfun)(... parameters unpacked from parms ...);
  }
};
...
template <class R, class TList,
      unsigned int size = 4 * sizeof(void*)>
class Functor
{
  ...
  typedef typename CallParms<TList>::
                         ParmsListType ParmsListType;
  struct FunImplBase
  {
    struct VTable
    {
      R (*call_)(Functor const&, ParmsListType parms);
      ...
    };
    // VTable vtbl_;
  };
  template <typename F>
  class FunctorImpl : public FunImplBase
  {
    F fun_;
  public:
    FunctorImpl(F const& fun) : fun_(fun) {}
    static R Call(Functor const& f, ParmsListType parms)
    {
      FunctorImpl const& this_ =
                  f.val_.template get<FunctorImpl const>();
      return FunctorCall<T, R, TList>::Call(this_.fun_,
                                                    parms);
    }
    ...
  };
  template <class P, class MF>
  class MemberFnImpl : public FunImplBase
  {
    P pobj_;
    MF memfun_;
  public:
    MemberFnImpl(P const& pobj, MF memfun) :
                              pobj_(pobj), memfun_(fun) {}
    static R Call(Functor const& f, ParmsListType parms)
    {
      MemberFnImpl const& this_ =
                   f.val_.template get<MemberFnImpl const>();
      return FunctorCall<T, R, TList>::Call(this_.pobj_,
                                       this_.memfun_, parms);
    }
    ...
  };
  ...
  Stored val_;
  typename FunImplBase::VTable* vptr_;
public:
  ...
  // функтор для функций-нечленов и произвольных функторов
  template <typename F> Functor(F const& fun)
  {
    FunImplBase* pimpl_ = val_.init<FunctorImpl<F> >(fun);
   // отбрасываем pimpl, в данной реализации он не нужен
    static typename FunImplBase::VTable vtbl =
    {
      &FunctorImpl::Call,
      ...
    };
    vptr_ = &vtbl;
  }
  ... evaluate Parm1 type from TList ...
  ... evaluate Parm2 type from TList ...
  ...
  inline R operator()() const
  {
    return vptr_->call_(*this, CallParms<TList>::Make());
  }
  inline R operator()(Parm1 p1) const
  {
    return vptr_->call_(*this, CallParms<TList>::Make(p1));
  }
  inline R operator()(Parm1 p1, Parm2 p2) const
  {
    return vptr_->call_(*this,
            CallParms<TList>::Make(p1, p2));
  }
  ...
};


Замечание: В листинге выше InstantiateH походит на шаблон GenScatterHierarchy<> в Локи, используемый здесь в качестве средства генерации кортежа.
Объединение аргументов оператора operator() в кортеж и их передача во внутренних вызовах может привести к дополнительным выгодам, выходящим за пределы самой реализации Functor. Например, можно добавить следующий перегруженный оператор operator():

template <class R, class TList, 
       unsigned int size = 4 * sizeof(void*)>
class Functor
{
  ... как указано выше...
  inline R operator()(ParmsListType& parms) const
  {
    return vptr_->call_(*this, parms);
  }
};

и использовать его для передачи ссылки parms по двум или более функторам. Это может упростить реализацию и даже повысить эффективность поддержки сцепления и связывания функторов. Можно даже создать именованные параметры в вызовах оператора operator() Functor – возможность, не поддерживаемая C++ для простых вызовов функций.

Заключение

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