读书笔记|数据局部性

2016-12-05 本文已影响122人 bakaqian

前言

CPU的速度飞速增长，然而计算机对RAM访问速度的增长却很迟缓。CPU速度增长带来的优势有时并不能为我们的程序带来同样的速度提升。

处理器的速度提升，使得我们可以更快的处理数据，但是却不能让计算机更快的获取数据。为了让CPU进行运算，它需要从主存中取出数据，并放到寄存器中，但是RAM的存取速度远远慢于CPU的速度。这就导致CPU可能会花费惊人的时间来等待内存传输数据。

一个形象的比喻

书中的比喻非常棒，想了想，还是大概抄下来把。

设想你是一个小办公室里的会计。你的工作是采集一盒子的单子并对它们进行一些核查统计或其他的计算。
得益于努力工作、出色的才能以及进取心，你可以在（比如说）一分钟内完成一个盒子里的所有任务。当然，这里有个小问题。这些盒子都被分别存放于一栋楼里的某个地方。为了拿到这些盒子，你必须询问仓储人员来获取这些盒子。他去开来叉车并在过道之间寻找直至找到你想要的那个盒子。
他花了一整天的时间来取一个盒子。这意味着不论你办事效率有多高，你一天只能搞定一个盒子。而剩余的时间，你就只能坐在办公椅上思考自己怎么就干了这样一份伤神的工作。
某天，一群工业设计师出现了。他们的任务是提高工作效率，比如提高流水线效率之类的工作。在观察你工作了几天之后，他们注意到以下几点：

通常情况下，在你完成某个盒子里的任务之后，你所需要的下个盒子就放在仓储间中与这个盒子所在的同个架子上。
开着叉车来取个小盒子真是蠢哭了。
其实在你的办公室角落里有一些空闲的空间。
它们想到了一个聪明的办法。仓库管理员为你带来你要的盒子时，会将与它相邻的那些盒子也都一起带来。现在当你需要一个新盒子时，第一件要做的事情就是查看盒子是否在办公室的托盘上。如果在，那就太棒了！你只需要几秒的时间把它拿过来然后继续你的算数。

CPU的托盘

上面的过程与当今计算机CPU工作原理相似。你相当于CPU，你的桌面是寄存器，装单子的盒子是数据，仓库是机器的RAM，仓库管理员是读取数据的总线。

CPU内部的内存十分有限，这一小块内存被成为缓存，这相当于那个装满盒子的托盘。当CPU需要RAM中的数据时，他它会自动将一整块的连续的内存取出来并放到缓存中。

加入你需要使用的下一个数据就恰好在缓存中，那么CPU就能直接从缓存中获取数据，这是很快的。成功在缓存中找到数据被称为一次命中，反之则称为未命中。

当缓存未命中时，CPU就停止运转，直到取得数据，我们的任务就是尽量避免这个情况的发生。

代码的好坏当然会影响性能，但是，数据的影响同样非常大，你需要做的就是让缓存中可用的数据尽可能的多。在缓存中使用的数据越多，程序就跑得越快。

所以优化就变成了如何让要处理的数据在内存中两两相邻。如下图所示，如果你要按顺序处理A、B、C三件事，那么，A、B、C最好在内存中是这样布局的：

优化

去使用上述优化最重要的是要找到需要优化的地方。并不是所有代码都需要进行这样的优化，对那些并不会频繁执行的代码进行优化将会浪费你大量的时间，并使你的代码更加复杂难看。

当然，你还要确定程序的性能问题是否是由缓存未命中引起的，如果不是，还是暂时不要在这上面浪费时间了。

另外，需要注意的是，使用抽象化的结构、使用借口意味着要通过指针或引用来访问对象，这会导致访问的内存不是连续的，这就会导致缓存未命中的现象，是否要牺牲一些抽象化的工作来提高效率，需要进行权衡。

示例

在游戏中，使用组建模式，将不同的模块拆分：AI、物理、渲染等。以下是GameEntity类与其他组件类：

class GameEntity {
public:
    GameEntity(AIComponent* ai, PhysicsComponent* physics, RenderComponent* render): 
      ai_(ai), physics_(physics), render_(render) {}

    AIComponent* ai() { return ai_;}
    PhysicsComponent* physics() { return physics_;}
    RenderComponent* render() { return render_;}

private:
    AIComponent* ai_;
    PhysicsComponent* physics_;
    RenderComponent* return render_;
};

class AIComponent {
public:
    void update() {
        //do something
    }
//other members
};

class PhysicsComponent {
public:
    void update() {
        //do something
    }
//other members
};

class RenderComponent {
public:
    void update() {
        //do something
    }
//other members
};

当游戏更新时，我们要分别调用各组建的update函数进行更新：

while(!gameover){
    for (int i = 0;i < num; ++ i) {
        entities[i]->ai()->update();
    }
    for (int i = 0;i < num; ++ i) {
        entities[i]->physics()->update();
    }
    for (int i = 0;i < num; ++ i) {
        entities[i]->render()->update();
    }
}

上面的代码不仅引起缓存抖动，甚至还将它来回搅成一团浆糊：

数组存储着指向游戏实体的指针，因此对于数组中的每个元素而言，我们需要遍历这些指针——这就引发了缓存未命中。

游戏实体又维护着指向组件的指针，再一次缓存未命中。
接着我们更新组建。
现在我们回到步骤1，对游戏里的每个实体的每个组件都这么干。

上面的代码不断做着内存空间一日游的操作，这可不是一个好的现象。

为了让循环想要访问的实体都在连续的内存中，我们可以使用一个保存各类控件的大数组：

AIComponent* aiComponents = new AIComponent[MAX_ENTITIES];
PhysicsComponent* physicsComponent = new PhysicsComponent[MAX_ENTITIES];
RenderComponent* renderComponent = new RenderComponent[MAX_ENTITIES];

然后我们的遍历就是这样的：

while(!gameover) {
    for (int i = 0;i < num; ++ i) {
        aiComponents.update();
    }
    for (int i = 0;i < num; ++ i) {
        physicsComponent.update();
    }
    for (int i = 0;i < num; ++ i) {
        renderComponent.update();
    }
}

没有了指针来跳跃查找数据，而是直接对连续的数组进行遍历，一些小的改变就可以避免内存未命中，使CPU效率得到提升。

读书笔记|数据局部性

前言

一个形象的比喻

CPU的托盘

优化

示例

猜你喜欢

热点阅读