Как написать кеширующий полиморфный код на С++?

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

vector<A*> a(n);
for(int i = 0; i < n; i++)
  a[i] = new B();

но если n велико (в моем случае 10 ^ 6 или более), это потребует очень много вызовов для новых и, кроме того, n объектов потенциально может быть распространено по всей моей основной памяти, что приводит к очень плохой производительности кеша, Каким будет правильный способ справиться с этой ситуацией? Я думаю сделать что-то вроде следующего, чтобы иметь все объекты в смежной области памяти.

B* b = new B[n];
vector<A*> a(n);
for(int i = 0; i < n; i++)
  a[i] = b + i;

но одна проблема заключается в том, как освободить память, выделенную новым B [n], если b больше не доступно (но у нас все еще есть a). Я только что узнал, что попытка

delete[] a[0];

не очень хорошая идея...

Ответ 1

Вы можете использовать новое размещение для создания объекта в определенной ячейке памяти:

vector<A*> a(n);
for(int i = 0; i < n; i++)
  a[i] = new(storage + i*object_size) B();
  // and invoke the destructor manually to release the object (assuming A has a virtual destructor!)
  a[i]->~A();

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

Ответ 2

Если вы точно знаете, что это будут только объекты типа B, почему бы не использовать параллельный вектор:

vector<B> storage(n);
vector<A*> pointers(n);
for(int i = 0; i < n; i++)
   pointers[i] = &storage[i];

Ответ 3

Если вы хотите сохранить все свои объекты в непрерывной памяти и в то же время избегать использования косвенности (вектор указателей базового класса), вы можете использовать контейнер типа объединения, например. вектор boost::variant. Это, конечно, предполагает, что существует ограниченное и известное количество производных классов и что их размеры сопоставимы. Недостатком является то, что каждый элемент вектора занимает столько же памяти, сколько и самый большой производный класс, независимо от его фактического класса (а также предполагает, что ваши классы разумно дешево копировать). Преимущества заключаются в том, что у вас есть непрерывное гетерогенное хранение полиморфных объектов, безопасность типов и отсутствие косвенности при доступе к элементам. Ниже приведен базовый пример с boost::variant и тремя классами A, B, C, где оба B и C наследуются от A, и все они являются полиморфными (и, это может быть намного приятнее с некоторым покрытием сахара и/или чем-то более специализированным для вашей цели, а не boost::variant, который не подходит для этой цели):

#include <iostream>
#include <vector>
#include <boost/variant/variant.hpp>
#include <boost/variant/apply_visitor.hpp>

struct A {
  int v1;
  A(int aV1 = 0) : v1(aV1) { };
  virtual ~A() { };
  virtual void print() { std::cout << "A print " << v1 << std::endl; };
  struct get_ref {
    typedef A& result_type;
    template <class T>
    A& operator()(T& obj) const { return obj; };
  };
};

struct B : A {
  float f1;
  B(float aF1 = 0.0) : A(42), f1(aF1) { };
  ~B() { };
  virtual void print() { std::cout << "B print " << f1 << std::endl; };
};

struct C : A {
  double d1;
  C(double aD1 = 0.0) : A(42), d1(aD1) { };
  ~C() { };
  virtual void print() { std::cout << "C print " << d1 << std::endl; };
};

int main() {
  typedef boost::variant<A,B,C> value_type;
  typedef std::vector< value_type > vect_type;
  vect_type arr(15);
  int i=0;
  for(;i<5;++i) arr[i] = A(31);
  for(;i<10;++i) arr[i] = B(0.2);
  for(;i<15;++i) arr[i] = C(0.4);

  for(vect_type::iterator it = arr.begin(); it != arr.end(); ++it)
    boost::apply_visitor(A::get_ref(), *it).print();

  std::cout << "value_type has size of " << sizeof(value_type) << std::endl;
  std::cout << "compared to: sizeof(A)=" << sizeof(A) << " sizeof(B)=" << sizeof(B) << " sizeof(C)=" << sizeof(C) << std::endl;

  return 0;
};

Ответ 4

Вам просто нужно сохранить указатели, возвращенные из нового [], и удалить их позже. Другой вектор, например.