c++ - 如何用多态实现数据局部性？

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 对象指针的 vector 。但是，循环遍历此 vector 可能会导致缓存未命中。理论上的补救措施是存储实际对象而不是指针，但这在 C++ 中是不允许的(数组没有多态性)。

就是说:当需要大量多态对象时，如何改进数据局部性(并最大限度地减少缓存未命中)？

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

Answer 1

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

然后用指向您的Bar1 和Bar2 池中的对象的指针填充Foo 对象指针的 vector :

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

Live demo

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