C++昂贵的指针跳转

看Modern C++: What You Need to Know提到一个观点：考虑程序性能时，请更多地使用array，而不是list。 也就是说，尽管避免指针的跳转，尽管选择连续内存存储。指针的频繁跳转是费时且昂贵的。其主要原因在于， 连续内存存储能充分利用cpu的prefetch功能，CPU约32K的L1缓存和约3M的L2缓存，可以使prefetch发挥令人惊叹的性能提升。

视频内容提到两个例子。

例子一

比如有一个游戏实体类，所有的实体都需要不断更新。原来的代码如下：

class GameEntity
{
    AllComponent *ai_;
    PhysicsComponent *physics_;
    RenderComponent *render_;
};

vector<GameEntity> entities;
for (auto& e:entities) {e.ai_->update();}
for (auto& e:entities) {e.physics_->update();}
for (auto& e:entities) {e.render_->update();}

将代码改写成如下，即原来的基本不变，只是ai_、physics_和render_三个成员所指向的对象变成了连续存储：

class GameEntity
{
    AllComponent *ai_;
    PhysicsComponent *physics_;
    RenderComponent *render_;
};

vector<GameEntity> entities;
vector<AllComponent> ai;
vector<PhysicsComponent> physics;
vector<RenderComponent> render;
for (auto& e:ai) {e.update();}
for (auto& e:physics) {e.update();}
for (auto& e:render) {e.update();}

改写后的代码比原代码据说快15倍之多。主要是原代码中->update的->太过耗时。

例子二

我们往一个序列的中间不断插入数值，那么应该使用vector还是list呢？或者需求是不断从一个序列中间删除数值，直到删空为止， 应该使用vector还是list呢？我们都知道，list使用的数据结构是双向链表，适合插入删除操作，但是找到中间位置却比较耗时。 而vector呢，正好相反，插入和删除比较昂贵。其实问题的关键就是，指针跳转和内存拷贝，哪个更昂贵些！

自己写的示例代码如下：

Task task;

vector<int> vint;
task.set_task_us("vint");
for (int i = 0; i < 100000; ++i) {
    vector<int>::iterator it = vint.begin();
    size_t s = vint.size() / 2;
    while (s--) ++it;
    vint.insert(it, i); 
}   

list<int> lint;
task.set_task_us("lint");
for (int i = 0; i < 100000; ++i) {
    list<int>::iterator it = lint.begin();
    size_t s = lint.size() / 2;
    while (s--) ++it;
    lint.insert(it, i); 
}   

task.set_task_us("verase");
while (!vint.empty()) {
    vector<int>::iterator it = vint.begin();
    size_t s = vint.size() / 2;
    while (s--) ++it;
    vint.erase(it);
}   

task.set_task_us("lerase");
while (!lint.empty()) {
    list<int>::iterator it = lint.begin();
    size_t s = lint.size() / 2;
    while (s--) ++it;
    lint.erase(it);
}   

task.set_task_us("end");

测试结果表明，使用vector无论在插入测试中，还是在删除测试中，都比使用list快100倍（均使用-O3编译优化）。这也是为嘛C++各种数据结构的默认容器选用的是vector。

总之，使用连续内存存储，能充分利用cpu的prefetch功能，避免昂贵的指针跳转。