作者 | benderzhao

一、方案

常見的內(nèi)存優(yōu)化方法有很多，針對不同的場景有不同的解決方案，下面按照由簡到繁的順序一一道來。

字段裁剪

顯而易見，把沒用的字段干掉，就可以省內(nèi)存。根據(jù)前文的內(nèi)存計算公式，哪怕只存了一個bool值，占用也是16字節(jié)。因此，首先考慮是去掉一些完全沒用的字段，其次是去掉一些默認(rèn)值的字段。

比如游戲里常見的物品，有id、數(shù)量、各種屬性等。如果出于方便或者可讀性，亦或者C++良好的編碼習(xí)慣，為每個字段都設(shè)置一個初始值，那么物品結(jié)構(gòu)就大概長這樣:

local item = {
    id = 123123,
    count = 1,
    property1 = 0,
    property2 = 0,
    property3 = "",
    property4 = false,
}

這種寫法property1到property4的默認(rèn)值占用了大量的內(nèi)存，單個item從2個Key-Value變?yōu)榱?個，內(nèi)存也膨脹了3倍。

比較節(jié)省內(nèi)存的做法是無默認(rèn)值，在使用時or下即可:

local property1 = item.property1 or 0

當(dāng)然，如果使用的地方特別多，比如有上萬處地方直接使用了item.property1，這種改動還是太大。這個后面會講到還有別的方法。

結(jié)構(gòu)調(diào)整

如果不熟悉Lua的實現(xiàn)，雀食會設(shè)計出一些常見于C++，但不友好于Lua內(nèi)存的結(jié)構(gòu)。

還是用物品舉例，假設(shè)一個玩家有1000個物品，每個物品有一些屬性。比較符合直覺的數(shù)據(jù)結(jié)構(gòu)是這樣:

local items = {
    [10001] = {count = 1, property1 = 1},
    [10002] = {count = 2, property2 = 4},
    [10003] = {count = 4, property4 = 10},
    ...
    [11000] = {count = 3, property1 = 2},
}

使用一個Table來存儲所有的物品，每個Key是物品id，Value是具體的屬性。

這種結(jié)構(gòu)淺顯易懂，但是有個問題，總共有1000+個Table，而Table不同于C++的struct，它是有很大的內(nèi)存開銷的，這種數(shù)據(jù)結(jié)構(gòu)占用的內(nèi)存會出乎意料的大，在這里光Table的占用就會有幾十KB。

考慮換成另一種結(jié)構(gòu):

local items = {
    count = {
        [10001] = 1,
        ...
        [11000] = 3,
    },
    property1 = {
        [10001] = 1
        ...
        [11000] = 2,
    }
 ...
}

這里把相同的字段放在一起，比如所有的count是一個Table，Key是物品id，Value是數(shù)量。這種結(jié)構(gòu)與前面的對比，Key-Value的數(shù)量是沒差別的，但是只有個位數(shù)的Table，對比前面的1000+，有幾個數(shù)量級的差距。

當(dāng)然，改動還是比較大的，但是如果對于這個結(jié)構(gòu)的訪問都收斂到物品模塊內(nèi)，對外只提供接口，那就還可以接受。

對于其他結(jié)構(gòu)也是一樣，主旨就是減少Table的使用。

提取公共表

前面字段裁剪提到，如果有一些默認(rèn)字段不好剔除，比如有上萬次使用的地方，挨個去加判斷肯定不現(xiàn)實，因此可以考慮提取元表來優(yōu)化。

還是用物品舉例，假設(shè)有1000個物品，每個物品有3個屬性，絕大部分情況下都是默認(rèn)值0。

local items = {
    [10001] = {count = 1, property1 = 0, property2 = 0, property3 = 0},
    [10002] = {count = 2, property1 = 0, property2 = 0, property3 = 0},
    [10003] = {count = 4, property1 = 0, property2 = 0, property3 = 0},
    ...
    [11000] = {count = 3, property1 = 1, property2 = 0, property3 = 0},
}

因為每個物品結(jié)構(gòu)的字段都是一樣，且大部分都是相同的值為0，因此我們提取一個元表base:

local base = {
    property1 = 0, property2 = 0, property3 = 0
}

然后將原始數(shù)據(jù)里與base內(nèi)容一樣的字段剔除掉，變?yōu)?

local items = {
    [10001] = {count = 1},
    [10002] = {count = 2},
    [10003] = {count = 4},
    ...
    [11000] = {count = 3, property1 = 1,
}

再為每個物品設(shè)置元表，get不到的字段就去base里找。set則只在自己的Table里設(shè)置。所有物品共用一張元表。

顯而易見，通過共用base的默認(rèn)值，很多重復(fù)的Key-Value被優(yōu)化掉了，也就節(jié)省了內(nèi)存。

這種方法適合于結(jié)構(gòu)一致，且有大量相同值的情況。

內(nèi)存壓縮

假如結(jié)構(gòu)不一致，或者字段的值都各不相同，又該如何優(yōu)化呢？例如我們已經(jīng)把沒用的字段剔除了，現(xiàn)在物品結(jié)構(gòu)長這樣:

local items = {
    [10001] = {count = 1},
    [10002] = {count = 2},
    [10003] = {count = 4},
    ...
    [11000] = {count = 3, property1 = 1,
}

考慮前面的指導(dǎo)思想，就是減少Table的使用，因此我們可以考慮把Table序列化為字符串，例如變成:

local items = {
    [10001] = "count=1",
    [10002] = "count=2",
    [10003] = "count=4",
    ...
    [11000] = "count=3,property1=1",
}

這樣就少了一大堆的二級的Table。當(dāng)然，這種序列化格式還是比較占內(nèi)存，這里只是舉個例子方便理解。實際可以序列化為緊湊的二進(jìn)制形式。

改為字符串后，要是想訪問里面的count，怎么辦？還是設(shè)置元表，在使用的時候還原回Table即可。

而既然都序列化為二進(jìn)制字符串了，那干脆再調(diào)用下lz4壓縮下，犧牲一點點CPU換來更高的優(yōu)化效果。比如變?yōu)?

local items = {
    [10001] = "\01\FF",
    [10002] = "\01\FE",
    [10003] = "\01\1F",
    ...
    [11000] = "\01\3F\24",
}

到此為止了嗎？不，還可以進(jìn)一步優(yōu)化，考慮每個結(jié)構(gòu)其實都是長差不多的，比如都有count字段存放整數(shù)，那與其挨個結(jié)構(gòu)壓縮，不如聚合N個結(jié)構(gòu)一起壓縮，那樣的壓縮比更好。

假設(shè)N取10，將原來的id除10聚合，先變?yōu)榕R時結(jié)構(gòu):

local items = {
    [1000] = {
        [10001] = {count = 1},
        [10002] = {count = 2},
        ...
        [10009] = {count = 4},
 },
    [1001] = {...}
    ...
 [1100] = {...}
}

這樣10個一組，再分別對每一組序列化后壓縮，變?yōu)椋?/p>

local items = {
    [1000] = "\01\FF\12\22",
    [1001] = "\01\FE\12\22",
    ...
    [1100] = "\01\3F\24\12\22",
}

這樣可節(jié)省的內(nèi)存將會更多。訪問的方式也是一樣，當(dāng)訪問到某id時，除10找到對應(yīng)的組，解壓縮反序列化即可。

這種優(yōu)化方式對于一些冷數(shù)據(jù)的，尤為有效，因為大部分情況下都不會訪問它們。

下沉C++

在前面的優(yōu)化方法都嘗試之后，還想繼續(xù)優(yōu)化內(nèi)存，怎么辦？考慮一個問題，似乎C++很少因為定義幾個字段幾個Struct就內(nèi)存炸了的情況，究其原因，有以下幾點:

• C++的Struct或者Class無額外消耗，一個空Class幾乎不消耗內(nèi)存。而Lua的Table本質(zhì)是一個很復(fù)雜的HashTable與Vector結(jié)構(gòu)，即使是個空Table也消耗了一大坨內(nèi)存。
• C++的字段是緊密排列，一個int就是固定的4字節(jié)，無額外消耗。而Lua因為是弱類型的解釋語言，除了本身的數(shù)據(jù)存儲，還需要類型描述以及GC等信息，單個字段的消耗是16字節(jié)+，相比C++膨脹了數(shù)倍，雖然實際上Lua已經(jīng)實現(xiàn)的很精巧了。

那么，我們也仿照C++實現(xiàn)一套內(nèi)存布局，是不是就可以了？

比如某個Table結(jié)構(gòu)有a、b、c三個字段，都為int范圍的整數(shù)，那我們在C++中開辟一塊12字節(jié)的內(nèi)存來存放就行了，干掉Lua中的Table，把對a、b、c的讀寫操作都映射到C++里的這塊內(nèi)存上。

如何映射呢？當(dāng)然也是用元表了。也許你會說元表不也會占用空間？是會占用，所以我們要把所有類型相同的結(jié)構(gòu)共用一份元表，比如有1000個Item，只有一份元表。

理論上來說，這種方式就可以達(dá)到接近C++的內(nèi)存使用，從而優(yōu)化Lua的內(nèi)存占用，順便還減輕了GC的壓力，因為Lua中已經(jīng)沒有復(fù)雜的Table結(jié)構(gòu)了。

將大象裝進(jìn)冰箱的思路有了，下面就講下具體的幾步。

結(jié)構(gòu)定義

首先第一步，是要先描述結(jié)構(gòu)的定義，可以采用自定義的格式，比如還是物品的例子，干脆直接用Lua描述它的格式:

local Item = {
    [id] = {size = 4},
    [count] = {size = 4},
    [property1] = {size = 4},
    ...
}

Item有3個字段，每個字段4字節(jié)?；蛘咭部梢允褂胘son、protobuf等格式，比如protobuf:

message Item {
    int32 id = 1;
    int32 count = 2;
    int32 property1 = 3;
    ...
}

考慮到生態(tài)，使用protobuf來描述最好。各種工具齊全，且大部分人都了解這個語法，無需再重新學(xué)習(xí)。

內(nèi)存布局

有了protobuf的定義后，接下來就是在內(nèi)存里把這些字段排列開來，也許你突然想到，既然都用了protobuf，那直接用它的反射庫不就好了？

(1) protobuf反射庫

protobuf的反射庫做的事情與我們要做的差不多，解析proto文件，生成一套描述信息Reflection，然后就可以根據(jù)Reflection初始化一塊內(nèi)存Message，并動態(tài)的讀寫其中的字段。

比如典型的接口：

最終的實現(xiàn)，也是將內(nèi)存地址強轉(zhuǎn)成類型指針，直接copy進(jìn)內(nèi)存，與我們的思路可以說一模一樣。

那看起來底層實現(xiàn)直接用protobuf就好了？然而，protobuf的反射庫除了太重，還有個最大的問題，是沒法支持熱更新。

(2) 反射需求

Lua天生就支持熱更新，因此，在將Lua內(nèi)存下沉到C++時，也必須考慮這個問題?？紤]之前的物品的Lua結(jié)構(gòu)：

local Item = {
    id = 123123,
    count = 1,
    property1 = 0
}

對應(yīng)的protobuf定義:

message Item {
    int32 id = 1;
    int32 count = 2;
    int32 property1 = 3;
}

最開始id寫在了分配的C++的內(nèi)存的偏移0，count寫在了偏移4，以此類推。

當(dāng)我們業(yè)務(wù)需要，假設(shè)需要增加一個字段time，出于可讀性考慮，我們加在了中間位置。Lua結(jié)構(gòu)變?yōu)?

message Item {
    int32 id = 1;
    int32 count = 2;
    int32 property1 = 3;
}

對應(yīng)的新的protobuf定義:

message Item {
    int32 id = 1;
    int32 count = 2;
    int32 time = 3;
    int32 property1 = 4;
}

這時候，再使用新的protobuf的偏移，去讀寫我們之前分配好的內(nèi)存，會明顯錯位了，比如現(xiàn)在property1的偏移是12，但是在舊的內(nèi)存布局里，偏移是8。

怎么辦？也許你已經(jīng)想到了，首先protobuf的定義不能亂來，應(yīng)該兼容舊版本，比如新增字段后，新的定義應(yīng)該為:

message Item {
    int32 id = 1;
    int32 count = 2;
    int32 time = 4; // 插在中間可以，tag必須兼容
    int32 property1 = 3;
}

其次，在內(nèi)存中永久維護(hù)一份message對應(yīng)的layout，當(dāng)加載新的protobuf定義后，根據(jù)tag修補layout的結(jié)構(gòu)。

在這個例子中，舊的layout是(id, 0), (count, 4), (property1, 8)，后面的數(shù)字是字段開始的偏移。

加載新定義之后，新的tag只會往后補充，layout變?yōu)?id, 0), (count, 4), (property1, 8), (time, 12)。

這樣，使用新的layout訪問舊內(nèi)存布局，是兼容沒問題的。

也許你會問，要是刪除字段怎么辦？豈不是會留有一個空洞？比如某天property1廢棄了，那layout變?yōu)榱?id, 0), (count, 4), (廢棄, 8), (time, 12)，有幾種辦法：新增的同類型字段可復(fù)用這個tag；等待重啟；當(dāng)看不見。

另外又因為熱更并不頻繁，所以這部分兼容的代碼，可以做在Lua里，實現(xiàn)更簡單，也不會造成性能的困擾。

(3) 小結(jié)

所以考慮熱更新需求和代碼復(fù)雜度，我們并不直接使用protobuf的反射庫，改為自己實現(xiàn)一套類似的內(nèi)存布局管理。

同時protobuf的內(nèi)存生命周期管理也不是我們期望的，這個下面會講到。

內(nèi)存管理

熟悉Lua的人都知道，Lua把所有的短字符串都放到一個HashMap存起來，這樣內(nèi)存里只會存一份字符串的拷貝。比如:

local a = "test"
local b = "test"

a與b都指向了同樣的字符串地址，節(jié)省了內(nèi)存，而且這樣判斷a與b是否相等時，可以直接使用指針比較，而無需調(diào)用strcmp，也提高了性能。

而什么時候從hashmap刪掉呢？自然是沒有使用了，Lua通過GC來刪掉。比如:

local a = "test"
a = nil

其他需要GC的類型比如Table、UserData也是同理。

那既然我們把Lua內(nèi)存下沉到C++，Lua復(fù)雜的結(jié)構(gòu)如何保證既不會內(nèi)存泄露，又不會野指針呢？要知道，Lua的Table是可以隨便相互各種引用的。

是不是也要復(fù)刻這套GC呢？其實大可不必，我們使用最簡單的引用計數(shù)即可。

(1) 引用計數(shù)

引用計數(shù)眾所周知，引用+1，取消引用-1，為0表示沒人引用了，就釋放掉。比如std::shared_ptr就是干這個的。

但是引用計數(shù)有個問題是循環(huán)引用，比如:

local a = {}
local b = {}
a.b = b
b.a = a

這樣a與b相互引用，就沒機會減到0了。Lua為了避免這個問題，采用三色標(biāo)記法來一波一波的回收。

那為什么Lua內(nèi)存下沉到C++中，反倒可以使用引用計數(shù)，沒有循環(huán)引用的問題呢？

原因很簡單，我們使用了protobuf來描述結(jié)構(gòu)。直接不讓這么定義就行了，比如這種是不允許的:

message A {
  B b = 1;
}

message B {
  A a = 1;
}

實際上也幾乎不會有必須這樣寫的業(yè)務(wù)需求。大部分是分層的定義:

message A {
  Base b = 1;
}

message B {
  Base a = 1;
}

message Base {
  ...
}

當(dāng)去掉了循環(huán)的邊，所有的結(jié)構(gòu)都變成了一顆樹，只要使用引用計數(shù)管理即可，簡單又高效。

又因為Lua都是單線程的，所以使用一個單線程版本的shared_ptr即可，性能更佳。

(2) 復(fù)雜結(jié)構(gòu)

當(dāng)然，我們的結(jié)構(gòu)不可能總?cè)莍nt，必須要支持嵌套、repeated、map的定義，比如:

message Player {
  string name = 1;
  int32 score = 2;
  bool is_vip = 3;
  float experience = 4;
  repeated Item items = 5;
  Pet pet = 6;
  map<string, Friend> friends = 7;
}

在前面我們知道各個字段是按照偏移來存放在內(nèi)存里的，那這里的name、items、pet、friends成員應(yīng)該如何存？畢竟幾乎都是編譯期未知的大小。

那么很簡單，只存放指針即可，固定8字節(jié)。指針?biāo)饕骄唧w的實例上去，對應(yīng)的就是String、Array、Map。

(3) 字符串池子

如前所述，我們也仿照Lua，把所有C++里的字符串用一個hashmap管理起來。

雖然實際上不需要在C++中用到字符串的比對，因為訪問a.b時，Lua層已經(jīng)把b映射到某個偏移了，C++也就無需在用b再做字符串比較查找字段。

這種設(shè)計的主要目的還是減少內(nèi)存的占用，畢竟程序中還是存在大量的相同字符串的。

另外String雖然也使用了引用計數(shù)管理，但是在釋放時，需要從池子中刪掉，并且池子是不能增加計數(shù)的，不然永遠(yuǎn)到不了0，這里要用到weakptr了。

(4) Array實現(xiàn)

Array對應(yīng)的就是Lua中的數(shù)組，比如:

local array = {"a", "b", "c"}

也是protobuf里的repeated，對應(yīng)的定義:

repeated string array = 1;

雖然repeated看起來和普通的message區(qū)別很大，但是在C++里實現(xiàn)是差不多的。

message是在訪問a.b時，把b映射到某個偏移讀寫。

repeated則是在訪問a[1]時，把1也映射到某個偏移，邏輯更簡單了，乘以單個的元素大小即可。

不過這里需要注意的是，在設(shè)置元素時，要確保是符合protobuf的定義的，畢竟Lua是可以隨便寫，如果上面的例子:

array[1] = 2

把整數(shù)設(shè)置到了字符串?dāng)?shù)組中，C++層要能夠檢測并拋出異常出來。

(5) Map實現(xiàn)

Map在Lua里雖然也是Table，但是是用來存放未知的KV的，典型的比如一個好友的集合:

local friends = {
    ["123123"] = {name = "張三"},
    ["123124"] = {name = "李四"},
}

對應(yīng)到protobuf的定義:

map<string, Friend> friends = 1;

這個Map就不能靠偏移來實現(xiàn)了，是放KV的也就只能用HashMap結(jié)構(gòu)。

而既然要節(jié)省內(nèi)存，那自然要用最精確的字段來存儲了，比如:

map<int32, int32> map1 = 1;
map<int64, int32> map2 = 2;
map<int32, int64> map1 = 3;
map<int64, int64> map1 = 4;

這有4種尺寸的KV排列組合，如果我們想簡單實現(xiàn)，定義個union，比如:

union Data {
    int32_t i32;
    int32_t i64;
    ...
};

然后用一個C++的std::unordered_map<Data, Data>來存放所有類型的KV。這種方式固然簡單，但是內(nèi)存明顯并沒有做到最優(yōu)。

怎么辦呢？似乎也沒什么好方法，羅列下所有的可能性，然后定一個指針union，像這樣:

union Map {
    std::unordered_map<int32_t, int32_t> * i32_32;
    std::unordered_map<int32_t, int64_t> * i32_64;
 ...
};

然后根據(jù)protobuf的定義，初始化對應(yīng)的類型，并按照那個類型來讀寫。

看起來很蠢，但是卻是最簡單有效的做法。也許你會說，有字節(jié)對齊，i32_32與i32_64占用的實際內(nèi)存會不會其實是一樣的？

是有這個可能，但是我們沒法假定std::unordered_map內(nèi)部實現(xiàn)的結(jié)構(gòu)定義，而且哪怕是一樣的，除了代碼多一點，CPU和內(nèi)存均無損失。

而代碼方面，可以借助template以及C++17的if constexpr，最大程度的減少冗余。

(6) 測試結(jié)果

廢了好大勁，終于正確無誤的把Lua內(nèi)存下沉到C++中，現(xiàn)在是檢驗優(yōu)化成果的時候了。

分成了普通結(jié)構(gòu)、Array、Map三種場景。

(7) 普通結(jié)構(gòu)

就是最普通簡單的結(jié)構(gòu)體，定義如下:

message SimpleStruct {
  int32 a = 1;
  int32 b = 2;
  int32 c = 3;
  ...
  int32 y = 25;
  int32 z = 26;
}

初始化了5000份數(shù)據(jù)，實測下沉C++后，內(nèi)存為Lua的1/3左右。

(8) Array

也采用了最簡單的數(shù)組類型，定義如下:

repeated int32 labels = 6;

插入1000w條數(shù)據(jù)后，C++內(nèi)存為Lua的1/4左右。

(9) Map

最后是Map類型，定義為:

map<int32, int32> params = 9;

插入1000w條數(shù)據(jù)后，C++的內(nèi)存居然和Lua差不多，甚至還稍大些。這就尷尬了。

(10) Map優(yōu)化

分析代碼，Map下沉之后，內(nèi)存不減反增。而我們只是封裝了一層std::unordered_map，所以問題必然出現(xiàn)在它與Lua的實現(xiàn)的不同上面。

根據(jù)資料，std::unordered_map采用的是拉鏈法，除了KV本身的存儲外，還有桶、鏈表等消耗，那是會多耗費些內(nèi)存。

再觀察Lua的實現(xiàn)，它其實用的是Coalesced hashing，這種實現(xiàn)雖然Set稍顯麻煩，但是Get卻很簡單，同時因為是一整塊內(nèi)存，內(nèi)存利用率更高。

既然std::unordered_map比不過它，那么我們自己實現(xiàn)一個類似的coalesced_map即可，同樣的算法，不過做了些變種，比如支持Delete。

將coalesced_map與std::unordered_map比較下性能，Set會稍慢點，Get是一致的，符合預(yù)期。實際上程序中也是讀多寫少，Lua這種策略沒錯。

(11) 優(yōu)化后測試

最后，重新跑一遍測試，C++內(nèi)存為Lua的1/2左右。不得不說，Lua實現(xiàn)真的很精巧。

總體來說，下沉方案效果還可以，但是還有繼續(xù)扣內(nèi)存的空間。

(12) 總結(jié)

Lua確實是嵌入式腳本語言一哥，開發(fā)效率高，運行效率也不差。

不過如果一不注意，就容易陷入CPU與內(nèi)存的陷阱中，大量使用時還是要多加注意。