數據局部性 Data Locality

遊戲設計模式 Game Programming PatternsOptimization Patterns

意圖

合理組織數據，充分使用CPU的緩存來加速內存讀取。

動機

我們被欺騙了。 他們一直向我們展示CPU速度每年遞增的圖表，就好像摩爾定律不是觀察歷史的結果，而是某種定理。 無需吹灰之力，軟件憑藉着新硬件就可以奇蹟般地加速。

芯片確實越來越快（就算現在增長的速度放緩了），但硬件巨頭沒有提到某些事情。 是的，我們可以更快地處理數據，但不能更快地獲得數據。

一副展現了從1980年到2010年處理器和RAM速度的圖表。處理器速度增長的更快，而RAM的速度增長緩慢。

爲了讓你超高速的CPU颳起指令風暴， 它需要從內存獲取數據加載到寄存器。 如你所知，RAM沒有緊跟CPU的速度增長，差遠了。

藉助現代的硬件，要消耗上百個週期才能從RAM獲得一比特的數據。 如果大部分指令需要的數據都需要上百個週期去獲取， 那麼爲什麼我們的CPU沒有在99%的時間空轉着等待數據？

事實上，等待內存讀取確實會消耗很長時間，但是沒有那麼糟糕。 爲了解釋爲什麼，讓我們看一看這一長串類比……

數據倉庫

想象一下，你是小辦公室裏的會計。 你的任務是拿盒文件，然後做一些會計工作——把數據加起來什麼的。 你必須根據一堆只有會計能懂的晦澀邏輯，取出特定標記的文件盒並工作。

由於辛勤地工作，天生的悟性，還有進取心，你可以在一分鐘內處理一個文件盒。 但是這裏有一個小小的問題。所有這些文件盒都存儲在分離的倉庫中。 想要拿到一個文件盒，需要讓倉庫管理員帶給你。 他開着叉車在傳送帶周圍移動，直到找到你要的文件盒。

嚴格地說，這會消耗他一整天才能完成。 不像你，他下個月就不會被僱傭了。 這就意味着無論你有多快，一天只能拿到一個文件盒。 剩下的時間，你只能坐在那裏，質疑自己怎麼選了這個折磨靈魂的工作。

一天，一組工業設計師出現了。 他們的任務是提高操作的效率——比如讓傳送帶跑得更快。 在看着你工作幾天後，他們發現了幾件事情：

他們想出來一個巧妙的辦法。 無論何時你問倉庫要一個盒子，他都會帶給你一托盤的盒子。 他給你想要的盒子，以及它周圍的盒子。 他不知道你是不是想要這些（而且，根據工作條件，他根本不在乎）； 他只是儘可能地塞滿托盤，然後帶給你。

無視工作場地的安全，他直接將叉車開到你的辦公室，然後將托盤放在辦公室的角落。

當你需要新盒子，你需要做的第一件事就是看看它在不在辦公室角落的托盤裏。 如果在，很好！你只需要幾分鐘拿起它然後繼續計算數據。 如果一個托盤中有五十個盒子，而幸運的你需要所有盒子，你可以以五十倍的速度工作。

但是如果你需要的盒子不在托盤上，就需要新的一托盤的盒子。 由於你的辦公室裏只能放一托盤的盒子，你的倉庫朋友只能將舊的拿走，帶給你一托盤全新的盒子。

CPU的托盤

奇怪的是，這就是現代CPU運轉的方式。如果還不夠明顯，你是CPU。 你的桌子是CPU的寄存器，一盒文件就是寄存器能放下的數據。 倉庫是機器的RAM，那個煩人的倉庫管理員是從主存加載數據到寄存器的總線。

如果我在三十年前寫這一章，這個比喻就到此爲止了。 但是芯片越來越快，而RAM，好吧，“沒有跟上”，硬件工程師開始尋找解決方案。 他們想到的是CPU緩存技術。

現代的電腦在芯片內部有一小塊存儲器。 CPU從那上面取數據比從內存取數據快得多。 它很小，因爲需要放在芯片上，它很快，因爲使用的（靜態RAM，或稱SRAM）內存更貴。

這一小片內存被稱爲緩存（特別地，芯片上的被稱爲L1級緩存）， 在比喻中，它是由托盤扮演的。 無論何時芯片需要從RAM取一字節的數據，它自動將一整塊內存讀入然後將其放入緩存——通常是64到128字節。 這些一次性傳輸的字節被稱爲cache line。

一個cache line，被請求的一字節數據，以及臨近的其他字節被一起加載到緩存

如果你需要的下一字節數據就在這塊上， CPU從緩存中直接讀取，比從RAM中讀取快得多。 成功從緩存中找到數據被稱爲“緩存命中”。 如果不能從中獲得而得去主存裏取，這就是一次緩存不命中。

當緩存不命中時，CPU空轉——它不能執行下一條指令，因爲它沒有數據。 它坐在那裏，無聊地等待幾百個週期直到取到數據。 我們的任務是避免這一點。想象你在優化一塊性能攸關的遊戲代碼，長得像這樣：

for (int i = 0; i < NUM_THINGS; i++)
{
  sleepFor500Cycles();
  things[i].doStuff();
}

你會做的第一個改動是什麼？對了。 將那個無用的，代價巨大的函數調用拿出來。 這個調用等價於一次緩存不命中的代價。 每次跳到內存，都會延誤你的代碼。

等等，數據是性能？

當着手寫這一章時，我花費了一些時間製作一個類似遊戲的小程序，用於收集緩存使用的最好情況和最壞情況。 我想要緩存速度的基準，這樣可以得到緩存失效造成的性能浪費情況。

當看到一些工作的結果時，我驚到了。 我知道這是一個大問題，但眼見爲實。 兩個程序完成完全相同的計算，唯一的區別是它們會造成緩存不命中的數量。 較慢的程序比較快的程序慢五十倍。

這讓我大開眼界。我一直從代碼的角度考慮性能，而不是數據。 一個字節沒有快慢，它是靜態的。但是因爲緩存的存在，組織數據的方式直接影響了性能。

現在真正的挑戰是將這些打包成一章內可以講完的東西。 優化緩存使用是一個很大的話題。 我還沒有談到指令緩存呢。 記住，代碼也在內存上，而且在執行前需要加載到CPU上。 有些更熟悉這個主題的人可以就這個問題寫一整本書。

既然你已經在閱讀這本書了， 我有幾個基本技術來幫你考慮數據結構是如何影響性能的。

這可以歸結成很簡單的事情：芯片讀內存時總是獲得一整塊cache line。 你能從cache line讀到越多你要的東西，速度就越快。 所以目標是組織數據結構，讓要處理的數據緊緊相鄰。

換言之，如果你正處理Thing，然後Another然後Also，你需要它們這樣呆在內存裏：

Thing, Another, Also按順序緊密排列在內存中。

注意，不是Thing，Another，和Also的指針，而是一個接一個的真實數據，。 CPU讀到Thing，也會讀取Another和Also（取決於數據的大小和cache line的大小）。 當你開始下一個時，它們已經在緩存上了。芯片很高興，你也很高興。

模式

現代的CPU有緩存來加速內存讀取。 它可以更快地讀取最近訪問過的內存的毗鄰內存。 通過提高內存局部性來提高性能——保證數據以處理順序排列在連續內存上。

何時使用

就像大多數優化方案，使用數據局部性的第一準則是在遇到性能問題時使用。 不要將其應用在代碼庫不經常使用的角落上。 優化代碼不會讓你過得更輕鬆，因爲其結果往往更加複雜，更加缺乏靈活性。

就本模式而言，還得確認你的性能問題確實由緩存不命中引發。 如果代碼是因爲其他原因而緩慢，這個模式幫不上忙。

簡單的估算方案是手動添加指令，檢查代碼中兩點間消耗的時間，寄希望於精確的計時器。 爲了找到糟糕的緩存使用，你需要使用更加複雜的東西。 你想要知道有多少緩存不命中，又是在哪裏發生的。

幸運的是，有現成的工具做這些。 在數據結構上做大手術前，花一些時間瞭解這些工具是如何工作， 理解它們拋出的一大堆數據（令人驚訝地複雜）是很有意義的。

話雖這麼說，緩存不命中仍會影響遊戲的性能。 雖然不應該花費大量時間提前優化緩存的使用，但是在設計過程中仍要思考數據結構是不是對緩存友好。

記住

軟件體系結構的特點之一是抽象。 這本書的很多章節都在談論如何解耦代碼塊，這樣可以更容易地進行改變。 在面向對象的語言中，這幾乎總是意味着接口。

在C++中，使用接口意味着通過指針或者引用訪問對象。 但是使用指針就意味在內存中跳躍，這就帶來了這章想要避免的緩存不命中。

爲了討好這個模式，你需要犧牲一些寶貴的抽象。 你越圍繞數據局部性設計程序，就越是在放棄繼承、接口和它們帶來的好處。 沒有銀彈，只有挑戰性的權衡。這就是樂趣所在！

示例代碼

如果你真的要一探數據局部性優化的深處，那麼你會發現有無數的方法去分割數據結構， 將其切爲CPU更好處理的小塊。 爲了熱熱身，我會先從一些最通用的分割方法開始。 我們會在遊戲引擎的特定部分介紹它們， 但是（像其他章節一樣）記住這些通用方法也能在其他部分使用。

連續數組

讓我們從處理一系列遊戲實體的遊戲循環開始。 實體使用了組件模式，被分解到不同的領域——AI，物理，渲染。 這裏是GmaeEntity類。

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() { /* 處理並修改狀態…… */ }

private:
  // 目標，情緒，等等……
};

class PhysicsComponent
{
public:
  void update() { /* 處理並修改狀態…… */ }

private:
  // 剛體，速度，質量，等等……
};

class RenderComponent
{
public:
  void render() { /* 處理並修改狀態…… */ }

private:
  // 網格，紋理，着色器，等等……
};

遊戲循環管理遊戲世界中一大堆實體的指針數組。每個遊戲循環，我們都要做如下事情：

  1. 爲每個實體更新他們的AI組件。
  2. 爲每個實體更新他們的物理組件。
  3. 爲每個實體更新他們的渲染組件。

很多遊戲引擎以這種方式實現：

while (!gameOver)
{
  // 處理AI
  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();
  }

  // 其他和時間有關的遊戲循環機制……
}

在你聽說CPU緩存之前，這些看上去完全無害。 但是現在，你得看到這裏有隱藏着的不對之處。 這不是在顛簸緩存，這是在四處亂晃然後猛烈地敲擊。看看它做了什麼：

  1. 遊戲實體的數組存儲的是指針，所以爲了獲取遊戲實體，我們得轉換指針。緩存不命中。
  2. 然後遊戲實體有組件的指針。又一次緩存不命中。
  3. 然後我們更新組件。
  4. 再然後我們退回第一步，爲遊戲中的每個實體做這件事。

令人害怕的是，我們不知道這些對象是如何在內存中佈局的。 我們完全任由內存管理器擺佈。 隨着實體的分配和釋放，堆的組織會更亂。

一堆雜亂的對象散佈在內存的各處，使用指針彼此相連。

如果我們的目標是在遊戲地址空間中四處亂轉，完成“256MB內存四晚廉價遊”，這也許是一個很好的決定。 但是我們的目標是讓遊戲跑得儘可能快，而在主存四處亂逛不是一個好辦法。 記得sleepFor500Cycles()函數嗎？上面的代碼效率和它也差不多了。

我們能做得更好。 第一個發現是，之所以跟着指針去尋找遊戲實體，是因爲可以立刻跟着另一個指針去獲得組件。 GameEntity本身沒有有意義的狀態和有用的方法。組件 纔是遊戲循環需要的。

衆多實體和組件不能像星星一樣散落在黑暗的天空中，我們得腳踏實地。 我們將每種組件存入巨大的數組：一個數組給AI組件，一個給物理，另一個給渲染。

就像這樣：

AIComponent* aiComponents =
    new AIComponent[MAX_ENTITIES];
PhysicsComponent* physicsComponents =
    new PhysicsComponent[MAX_ENTITIES];
RenderComponent* renderComponents =
    new RenderComponent[MAX_ENTITIES];

讓我強調一點，這些都是組件的數組，而不是指向組件的指針。數據都在那裏一個接着一個排列。 遊戲循環現在可以直接遍歷它們了。

while (!gameOver)
{
  // 處理AI
  for (int i = 0; i < numEntities; i++)
  {
    aiComponents[i].update();
  }

  // 更新物理
  for (int i = 0; i < numEntities; i++)
  {
    physicsComponents[i].update();
  }

  // 繪製屏幕
  for (int i = 0; i < numEntities; i++)
  {
    renderComponents[i].render();
  }

  // 其他和時間有關的遊戲循環機制……
}

我們消除了所有的指針追逐。不在內存中跳來跳去，而是直接在三個數組中做直線遍歷。

三個存儲不同種的組件的數組。每個數組都整整齊齊地排列着組件。

這將一股字節流直接泵到了CPU飢餓的肚子裏。 在我的測試中，這個改寫後的更新循環是之前性能的50倍。

有趣的是，我們並沒有在這裏放棄太多的封裝。 是的，遊戲循環直接更新遊戲組件而不是通過遊戲實體，但在此之前它已經確保了以正確的順序運行。 即使如此，每個組件的內部還是具有很好的封裝性。 它們的封裝性取決於自身的數據和方法。我們只是改變了使用它們的方法。

這也不意味着我們擺脫了GameEntity。它擁有它組件的指針這一狀態仍然得以保持。 它的組件指針現在只是指到了這個數組之中。 對遊戲的其他部分，如果你還是想傳遞一個“遊戲實體”，一切照舊。 重要的是性能攸關的遊戲循環部分迴避了這點，直接獲取數據。

打包數據

假設我們在做粒子系統。 根據上節的建議，將所有的粒子放在巨大的連續數組中。讓我們用管理類封裝它。

class Particle
{
public:
  void update() { /* 重力，等等…… */ }
  // 位置，速度，等等……
};

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

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

  int numParticles_;
  Particle particles_[MAX_PARTICLES];
};

系統中的基本更新方法看起來是這樣的：

void ParticleSystem::update()
{
  for (int i = 0; i < numParticles_; i++)
  {
    particles_[i].update();
  }
}

但實際上不需要同時更新所有的粒子。 粒子系統維護固定大小的對象池，但是粒子通常不是同時在屏幕上活躍。 最簡單的解決方案是這樣的：

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

我們給Particle一個標誌位來追蹤其是否在使用狀態。 在更新循環時，我們檢查每個粒子的這個標誌位。 這會將粒子其他部分的數據也加載到緩存中。 如果粒子沒有在使用，那麼跳過它去檢查下一個。 這時粒子加載到內存中的其他數據都是浪費。

活躍的粒子越少，要在內存中跳過的部分就越多。 越這樣做，在兩次活躍粒子有效更新之間發生的緩存不命中就越多。 如果數組很大又有很多不活躍的粒子，我們又在顛簸緩存了。

如果連續數組中的對象不是連續處理的，實際上這個辦法也沒有太多效果。 如果有太多不活躍的對象需要跳過，就又回到了問題的起點。

鑑於本節的標題，你大概可以猜出答案是什麼了。 我們不監測活躍與否的標籤，我們根據標籤排序粒子。 將所有活躍的粒子放在列表的前頭。 如果知道了這些粒子都是活躍的，就不必再檢查這些標識位了。

還可以很容易地追蹤有多少活躍的粒子。這樣，更新循環變成了這種美麗的東西：

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

現在沒有跳過任何數據。 加載入緩存的每一字節都是需要處理的粒子的一部分。

當然，我可沒說每幀都要對整個數組做快排。 這將抵消這裏的收益。我們想要的是保持數組的順序。

假設數組已經排好序了——開始時確實如此，因爲所有粒子都不活躍——它變成未排序的時候即是粒子被激活或者被反激活時。 我們可以很輕易地處理這兩種情況。 當一個粒子激活時，我們讓它佔據第一個不活躍粒子的位置， 將不活躍粒子移動到激活序列的尾端，完成一次交換：

void ParticleSystem::activateParticle(int index)
{
  // 不應該已被激活！
  assert(index >= numActive_);

  // 將它和第一個未激活的粒子交換
  Particle temp = particles_[numActive_];
  particles_[numActive_] = particles_[index];
  particles_[index] = temp;

  // 現在多了一個激活粒子
  numActive_++;
}

爲了反激活粒子，只需做相反的事情：

void ParticleSystem::deactivateParticle(int index)
{
  // 不應該已被激活！
  assert(index < numActive_);

  // 現在少了一個激活粒子
  numActive_--;

  // 將它和最後一個激活粒子交換
  Particle temp = particles_[numActive_];
  particles_[numActive_] = particles_[index];
  particles_[index] = temp;
}

很多程序員（包括我在內）已經對於在內存中移動數據過敏了。 將一堆數據移來移去的消耗感覺比發送指針要大得多。 但是如果你加上了解析指針的代價，有時候這種估算是錯誤的。 在有些情況下，如果能夠保證緩存命中，在內存中移動數據消耗更小。

將粒子根據激活狀態保持排序——就不需要給每個粒子都添加激活標誌位了。 這可以由它在數組中的位置和numActive_計數器推斷而得。 這讓粒子對象更小，意味着在cache lines中能夠打包更多數據，能跑得更快。

但是並非萬事如意。 你可以從API看出，我們放棄了一定的面向對象思想。 Particle類不再控制其激活狀態了。 你不能在它上面調用activate()因爲它不知道自己的索引。 相反，任何想要激活粒子的代碼都需要接觸到粒子系統。

在這個例子中，將ParticleSystem和Particle這樣牢牢綁一起沒有問題。 我將它們視爲兩個物理類的的組合概念。 這意味着粒子只在特定的粒子系統中有意義。 在這種情況下，很可能是粒子系統在複製和銷燬粒子。

冷/熱 分割

這裏是最後一種取悅緩存的技術例子。 假設某些遊戲實體有AI控件。 其中包括一些狀態——現在正在播放的動畫，正在前往的方向，能量等級，等等——這些東西每幀都會發生變化。 就像這樣：

class AIComponent
{
public:
  void update() { /* ... */ }

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

但它也有一些罕見事件的狀態。 它存儲了一些數據，描述它遭到獵槍痛擊後會掉落什麼戰利品。 掉落數據在實體的整個生命週期只會使用一次，就在它結束的前一霎那：

class AIComponent
{
public:
  void update() { /* ... */ }

private:
  // 之前的字段……
  LootType drop_;
  int minDrops_;
  int maxDrops_;
  double chanceOfDrop_;
};

假設我們遵循前面的章節，那麼當我們更新AI組件時，就穿過了一序列打包好的連續數組。 那個數據包含所有掉落物的信息。 這讓每個組件都變得更大了，這就減少了我們能夠加載到cache line中的組件個數。 每幀的每個組件都會將戰利品數據加載到內存中去，即使我們根本不會去使用它。

這裏的解決方案被稱爲“冷/熱分割”。這個點子源於將數據結構劃分爲兩個分離的部分。 第一部分保存“熱”數據，那些每幀都要調用的數據。 剩下的片段被稱爲“冷”數據，在那裏存儲使用的次數較少的數據。

這裏的熱部分是AI組件的主體。 它是使用最多的部分，所以我們不希望解析指針去找到它。 冷組件可以被歸到一邊去，但是我們還是需要訪問它，因此我們在熱組件中包含一個指向它的指針，就像這樣：

class AIComponent
{
public:
  // 方法……
private:
  Animation* animation_;
  double energy_;
  Vector goalPos_;

  LootDrop* loot_;
};

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

現在我們每幀都要遍歷AI組件，加載到內存的數據只包含必需的數據（以及那個指向冷數據的指針）。

你可以看到事情是怎麼變得模棱兩可的。 在我的例子中，哪些是冷數據，哪些是熱數據是很明確的，但是在真實的遊戲中一般很少可以這麼明顯地分割。 如果你有一部分數據，實體在一種狀態下會經常使用，另一種狀態則不會，那該怎麼辦？ 如果實體只在特定關卡時使用一塊特定的數據，又該怎麼辦？

做這種優化有時就是在走鋼絲。 很容易陷入其中，消耗無盡的時間把數據挪來挪去看看性能如何。 需要通過實踐來掌握在哪裏付出努力。

設計決策

這章更接近於介紹一種思維定勢——將數據的組織模式作爲遊戲性能的關鍵部分。 實際上具體的設計空間是開放的。 你可以讓數據局部性影響整個架構，或者只在局部幾個核心數據結構上使用這個模式。

最需要關心的問題是在何時何地使用這個模式，但是這裏還有其他幾個問題需要回答。

你如何處理多態？

到了現在，我們避開了子類和虛方法。 我們假設有打包好的同類對象。 這種情況下，我們知道它們有同樣的大小。 但是多態和動態調用也是有用的工具。我們如何調和呢？

遊戲實體是如何定義的？

如果與組件模式串聯使用此模式， 你會獲得多個數組，包含組成遊戲實體的組件。 遊戲循環會在那裏直接遍歷它們，所以實體本身就不是那麼重要了， 但是在其他你想要與“實體”交互的代碼庫部分，一個概念上的實體還是很有用的。

這裏的問題是它該如何被表示？如何追蹤這些組件？

參見