# 数据局部性

“通过合理组织数据利用CPU的缓存机制来加快内存访问速度。”

CPU的速度飞速增长，但RAM访问速度却增长迟缓，从1980年，开始芯片速度每年都会起飞，而RAM速度被CPU远远甩在后面。

对刚访问数据的邻近数据进行访问的术语叫做访问局部性（locality of reference）。

当代计算机在其芯片内部的内存十分有限。CPU从芯片中读取数据的速度要快于它从主存中读取数据的速度。芯片内存很小，以便嵌入在芯片上，而且由于它使用了更快的内存类型（静态RAM或称“SRAM”），所以更加昂贵。

当代计算机有多级缓存，也就是你所听到的那些“L1”、“L2”、“L3”等。它们的大小按照其等级递增，但速度却随等级递减。

这一小块内存被称为缓存（特别一提的是，芯片上的那块内存便是L1缓存），任何时候当芯片需要RAM中的数据时，它会自动将一整块连续的内存（通常在64到128字节之间）取出来并置入缓存中。

假如你需要的下一个数据恰巧在这个块中，那么CPU直接从缓存中读取数据，要比命中RAM快多了。成功地在缓存中找到数据被称为一次命中。假如它没有找到数据而需要访问主存，则称之为未命中

## 连续的数组

```cpp
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* render_;
};

class AIComponent
{
public:
　void update() }
　{
　// Work with and modify state... 

private:
　// Goals, mood, etc. ...


};

class PhysicsComponent
{
public:
　void update()　}
　{
　// Work with and modify state... 

private:
　// Rigid body, velocity, mass, etc. ...


};

class RenderComponent
{
public:
　void render()
　{
　　// Work with and modify state... 
　}

private:
　// Mesh, textures, shaders, etc. ...
};
```

许多游戏实体将这样进行实现：

```cpp
while (!gameOver)
{
　for (int i = 0; i < numEntities; i++)
　{
　　entities[i]->ai()->update();
　}

　for (int i = 0; i < numEntities; i++)
　{
　　entities[i]->physics()->update();
　}

　for (int i = 0; i < numEntities; i++)
　{
　　entities[i]->render()->render();
　}

　// Other game loop machinery for timing...

}
```

这样的内存布局就不太好，可以优化

```cpp
AIComponent* aiComponents =
　　new AIComponent[MAX_ENTITIES];
PhysicsComponent* physicsComponents =
　　new PhysicsComponent[MAX_ENTITIES];
RenderComponent* renderComponents =
　　new RenderComponent[MAX_ENTITIES];
while (!gameOver)
{
　// Process AI.
　for (int i = 0; i < numEntities; i++)
　{
　　aiComponents[i].update();
　}

　// Update physics.
　for (int i = 0; i < numEntities; i++)
　{
　　physicsComponents[i].update();
　}

　// Draw to screen.
　for (int i = 0; i < numEntities; i++)
　{
　　renderComponents[i].render();
　}

　// Other game loop machinery for timing...

}
```

## 包装数据

假设在做一个粒子系统，将所有粒子置入一个大的连续数组中

```cpp
class Particle
{
public:
　void update() { /* Gravity, etc. ... */ }
　// Position, velocity, etc. ...
};

class ParticleSystem
{
public:
　ParticleSystem()
　: numParticles_(0)
　{}

　void update();
private:
　static const int MAX_PARTICLES = 100000;

　int numParticles_;
　Particle particles_[MAX_PARTICLES];
};
```

同时例子系统的一个简单的更新方法

```cpp
for (int i = 0; i < numParticles_; i++)
{
　if (particles_[i].isActive())
　{
　　particles_[i].update();
　}
}
```

更好的办法是可以时刻跟踪被激活粒子的数目

```cpp
for (int i = 0; i < numActive_; i++)
{
　particles[i].update();
}
```

快速的更改数组数据

激活目标粒子，与第一个未激活的进行数组元素交换

```cpp
void ParticleSystem::activateParticle(int index)
{
　// Shouldn't already be active!

　assert(index >= numActive_);

　// Swap it with the first inactive particle right

　// after the active ones.

　Particle temp = particles_[numActive_];
　particles_[numActive_] = particles_[index];
　particles_[index] = temp;

　numActive_++;
}
```

反激活粒子只需以相反的方式处理

```cpp
void ParticleSystem::deactivateParticle(int index)
{
　// Shouldn't already be inactive!

　assert(index < numActive_);
　numActive_--;

　// Swap it with the last active particle right

　// before the inactive ones.

　Particle temp = particles_[numActive_];
　particles_[numActive_] = particles_[index];
　particles_[index] = temp;
}
```

这样比起，操作大量数组内存，进行平移要好的不止一点半点。

## 冷热分解

内存是连续的，将经常修改的字段放在连续的位置，将不经常修改的放在连续的一起。

```cpp
class AIComponent
{
public:
  // Methods...

private:
　Animation* animation_;
　double energy_;
　Vector goalPos_;

　LootDrop* loot_;
};

class LootDrop
{
　friend class AIComponent;
　LootType drop_;
　int minDrops_;
　int maxDrops_;
　double chanceOfDrop_;
};
```