Как написать кеш дружественный полиморфный код на C ++?

Question

Я пишу кусок кода с высокими требованиями к производительности, где мне нужно обрабатывать большое количество объектов полиморфным способом. Допустим, у меня есть класс 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];

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

Answer 1

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

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

Answer 2

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

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(); 

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

Answer 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;
};

Answer 4

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