如何用C++编写缓存友好的多态代码？

Question

我正在编写一段对性能有很高要求的代码,我需要以多态方式处理大量对象.假设我有一个A类和一个从A派生的B类.我现在可以创建一个B的向量:s像这样

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

但如果n很大(在我的情况下按10 ^ 6或更多的顺序),这将需要非常多的new调用,而且n个对象可能会遍布我的主内存,导致缓存性能非常差.处理这种情况的正确方法是什么？我正在考虑做类似以下的事情,让所有对象都在一个连续的内存区域.

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

但一个问题是如果b不再可用,如何释放由新B [n]分配的内存(但我们仍然有).我刚刚学会了尝试

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

您可以使用placement 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(); 

但是，如果不放弃连续存储，就无法解决“真正”的问题：如果释放一个对象，它将导致堆中出现漏洞，从而随着时间的推移导致高碎片。您只能跟踪释放的对象并重新使用存储。