如何利用多态性实现数据本地化

Question

（标题可能"不太理想"。）

假设有这样的代码：

class Foo {/*stuff*/};
class Bar1 : Foo {/*stuff*/};
class Bar2 : Foo {/*stuff*/};
std::vector<Foo*> foos;
// Populate 'foos' with Foo, Bar1 and Bar2 objects
// Iterate through foos
for(Foo* foo : foos) foo->doSomething();

基本上，foos是具有Foo对象指针的向量。但是，通过该向量循环可能会导致缓存未命中。理论上的补救措施是存储实际对象而不是指针，但这在C++中是不允许的（没有数组的多态性）。

也就是说：当需要大量多态对象时，如何提高数据的局部性（并最大限度地减少缓存未命中）？

我对此很感兴趣，因为每个人都告诉我缓存命中/未命中在性能关键型软件中非常重要，因此应该避免像上面给出的代码示例中那样使用指针。然而，这本质上意味着抛弃多态性。

Answer 1

我认为通常情况下，为了使用多态性，您必须牺牲性能，但在这种情况下，也许您可以维护Bar1和Bar2的单独向量。您可以将它们视为Bar1和Bar2的"池"。

然后用指向Bar1和Bar2池中对象的指针填充Foo对象指针的矢量：

template<typename Bar>
void populateFoos(std::vector<Foo*>& foos, std::vector<Bar>& bars) {
    for (auto& bar : bars)
        foos.emplace_back(&bar);
}
std::vector<Bar1> bar1s;
std::vector<Bar2> bar2s;
std::vector<Foo*> foos;
// Populate Bar1s
bar1s.emplace_back();
bar1s.emplace_back();
// Populate Bar2s
bar2s.emplace_back();
// Populate 'foos' with Bar1 and Bar2 objects
populateFoos(foos, bar1s);
populateFoos(foos, bar2s);
// Iterate through foos
for(auto foo : foos) 
    foo->doSomething(); 

现场演示

您需要小心，不要通过重新分配Bar1和Bar2池来使Foo对象指针无效。