lua是一款非常小巧的開源的腳本語言，5.1版本的的壓縮包僅208KB，代碼僅有17000多行。
使用標(biāo)準(zhǔn)c編寫的它可以很方便的嵌入到各個(gè)平臺(tái)系統(tǒng)中，深得游戲開發(fā)者的青睞。
你可以很方便的在github中查看它的源代碼：https://github.com/lua/lua

數(shù)據(jù)類型

lua的數(shù)據(jù)類型定義在lua.h中

// lua.h
#define LUA_TNONE (-1)          // 無類型
#define LUA_TNIL 0              // 空類型
#define LUA_TBOOLEAN 1          // 布爾
#define LUA_TLIGHTUSERDATA 2    // 指針 (void *)
#define LUA_TNUMBER 3           // 數(shù)字 (lua_Number)
#define LUA_TSTRING 4           // 字符串 (TString)
#define LUA_TTABLE 5            // 表 (Table)
#define LUA_TFUNCTION 6         // 函數(shù) (CClosure)
#define LUA_TUSERDATA 7         // 指針 (void *)
#define LUA_TTHREAD 8           // LUA虛擬機(jī) (lua_State)

我們可以看到LUA_TLIGHTUSERDATA和LUA_TUSERDATA都是void類型，但LUA_TLIGHTUSERDATA由lua外部使用者自行管理，不需要GC。

上述定義中，LUA_TTABLE及之后的類型均由GC進(jìn)行管理。

字符串

Lua的字符串與其他語言不同，在Lua虛擬機(jī)中有一個(gè)哈希數(shù)組變量，用來存儲(chǔ)所有字符串
同一個(gè)字符串只會(huì)有一份，一旦創(chuàng)建不可更改，Lua中使用的均是該字符串的引用

這個(gè)哈希數(shù)組存放在global_state.strt中

每當(dāng)使用一個(gè)字符串時(shí)，會(huì)進(jìn)行以下操作：

• 計(jì)算該字符串的哈希值
• 找到對(duì)應(yīng)的哈希桶，遍歷該哈希桶，如果找到同樣的字符串，則返回
• 否則，在該哈希桶中新插入該字符串
• 當(dāng)一個(gè)哈希桶中數(shù)量過多時(shí)，執(zhí)行一次重新哈希
• GC階段時(shí)會(huì)找到?jīng)]有使用的字符串進(jìn)行回收

使用技巧

我們知道每次設(shè)置字符串時(shí)，都會(huì)有一次哈希和查找操作，如果是新的字符串，還會(huì)新增到全局?jǐn)?shù)組中，所以我們應(yīng)該盡可能減少臨時(shí)字符串以及字符串連接操作

-- 低性能
local str = ""
for i = 1, 99999 do
    str = str .. "."
end
-- 高性能 大約提升10倍
local t = {}
for i = 1, 99999 do
    t[#t + 1] = "."
end
local str = table.concat(t, "")

Table

Lua的table是一個(gè)非常靈活的數(shù)據(jù)類型，它定義在lobject.h中，實(shí)現(xiàn)在ltable.c中。

typedef struct Table {
  CommonHeader;
  lu_byte flags;
  lu_byte lsizenode;  // 以2的lsizenode次方作為哈希表長(zhǎng)度
  unsigned int sizearray;  // 數(shù)組部分大小
  TValue *array;  // 數(shù)組部分
  Node *node; // 哈希表部分
  Node *lastfree;  // 指向最后一個(gè)閑置的鏈表空間
  struct Table *metatable; // 元表
  GCObject *gclist;
} Table;

Lua中的table分為數(shù)組和哈希表兩個(gè)部分

• 當(dāng)key為正整數(shù)時(shí)，在數(shù)組空間滿足時(shí)會(huì)優(yōu)先使用數(shù)組部分
• 哈希表部分則可以存放任意key和非nil的所有類型value

訪問流程

• 當(dāng)輸入key為正整數(shù)且小于等于數(shù)組部分大小時(shí)，嘗試在數(shù)組部分查找
• 否則計(jì)算哈希值，找到對(duì)應(yīng)哈希桶，遍歷該哈希桶直到找到該key

這里可以看出，如果key大于數(shù)組部分大小時(shí)，即使是正整數(shù)，也會(huì)存放在哈希表中

local t = {1}
t[1] = 0 -- 數(shù)組部分
t[100] = 0 -- 哈希表部分

Table空間動(dòng)態(tài)擴(kuò)展

• local t = {}數(shù)組部分和哈希部分沒有分配空間
• 在添加元素會(huì)優(yōu)先往哈希表部分添加
• 哈希表空間不足時(shí)執(zhí)行rehash和resize 操作，重新分配數(shù)組部分和哈希部分大小
• Lua申請(qǐng)內(nèi)存時(shí)以 2 的整數(shù)次冪邊界對(duì)齊

static void rehash (lua_State *L, Table *t, const TValue *ek)

table重新分配內(nèi)存有個(gè)原則：數(shù)組段的利用率不低于 50%

為此在rehash函數(shù)中調(diào)用了numusehash函數(shù)

目的：計(jì)算正整數(shù)key在(2^(i - 1), 2^i]之間的元素?cái)?shù)量，存放在num[i]中

static int numusehash (const Table *t, unsigned int *nums, unsigned int *pna)

舉個(gè)例子：

tb = {1,2,3, 20}
num[0] = 1   -- 1在此范圍 2^0，范圍內(nèi)元素個(gè)數(shù)1個(gè)
num[1] = 1   -- 2在此范圍 2^1，范圍內(nèi)元素個(gè)數(shù)1個(gè)
num[2] = 1   -- 3在此范圍 2^2，范圍內(nèi)元素個(gè)數(shù)1個(gè)
num[3] = 0
num[4] = 0
num[5] = 1   -- 20在此范圍 2^5，范圍內(nèi)元素個(gè)數(shù)1個(gè)

而后rehash函數(shù)調(diào)用了computesizes

目的：判斷每個(gè)2次方位置num[i]的總元素個(gè)數(shù)都超過該范圍的50%

static unsigned int computesizes (unsigned int nums[], unsigned int *pna)

舉例例子：

-- 在之前的例子中我們已經(jīng)統(tǒng)計(jì)出了各二次冪分段的元素?cái)?shù)量
-- 接著我們判斷是否每個(gè)二次冪分段使用率超過50%
num[0]分段：元素個(gè)數(shù) 1 > 0.5 * 2^0 滿足利用率
num[1]分段：元素個(gè)數(shù) 1+1 = 2 > 0.5 * 2^1 滿足
num[2]分段：元素個(gè)數(shù) 1+1+1 = 3 > 0.5 * 2^2 滿足利用率
num[3]，num[4]分段無元素，跳過
num[5]分段：元素個(gè)數(shù) 1+1+1 = 3 < 0.5 * 2^5 不滿足，舍棄

最終數(shù)組部分分配的大小為2^2，也就是1，2，3均存在數(shù)組部分，20存放在哈希表部分

使用技巧

• 預(yù)分配策略

對(duì)于空表而言，前三個(gè)元素會(huì)執(zhí)行三次rehash操作，而100萬個(gè)元素僅執(zhí)行了20次(2^20 > 100萬)，對(duì)于已知元素大于3個(gè)的表來說，建議采用預(yù)分配策略

-- 低性能
local a = {}
for i = 1, 3 do
    a[i] = true
end

-- 高性能，大約提升一倍
local a= {1,1,1}
for i = 1, 3 do
    a[i] = true
end

• 盡量復(fù)用臨時(shí)table

Table表的取長(zhǎng)度操作

我們都知道lua可以使用#符號(hào)，來取table的長(zhǎng)度，但是其中有很多的限制
舉個(gè)例子，猜猜看下面這段代碼的輸出結(jié)果

print(#{1,2,nil,4,5,6,7,nil}) -- 輸出7
print(#{1,2,3,nil,5,6,7,nil}) -- 輸出3

為什么會(huì)出現(xiàn)這種結(jié)果呢，我們就要看看lua的取長(zhǎng)度函數(shù)了

lua_Unsigned luaH_getn (Table *t) {
  unsigned int j = t->sizearray;
  if (j > 0 && isempty(&t->array[j - 1])) {
    unsigned int i = 0;
    while (j - i > 1u) {  /* binary search */
      unsigned int m = (i + j) / 2;
      if (isempty(&t->array[m - 1])) j = m;
      else i = m;
    }
    return i;
  }
  else {  /* 'j' is zero or present in table */
    if (isdummy(t) || isempty(luaH_getint(t, l_castU2S(j + 1))))
      return j;  /* 'j + 1' is absent... */
    else  /* 'j + 1' is also present */
      return hash_search(t, j);
  }
}

取長(zhǎng)度一般經(jīng)過以下幾個(gè)步驟：

• 數(shù)組部分末位為空，二分法找空值

print(#{1,2,nil,4,5,6,7,nil}) -- 輸出7
數(shù)組大小為8，二分中值4，key=4存在的，會(huì)向右邊二分查找，返回長(zhǎng)度7

print(#{1,2,3,nil,5,6,7,nil}) -- 輸出3
數(shù)組大小為8，二分中值4，key=4不存在的，向左二分，返回長(zhǎng)度3

• 哈希部分為空，或者數(shù)組末位+1不存在，直接返回?cái)?shù)組部分大小

-- 哈希部分為空
print(#{nil,nil,nil,nil,nil,nil,nil,8}) -- 輸出8

-- 數(shù)組末位+1不存在
-- 數(shù)組大小4，哈希部分key=5不存在，所以直接返回4
local t = {nil, 2, 3, 4}
t[6] = 6 -- 若t[1]不為nil時(shí)，根據(jù)利用率大于50%原則，t[6]會(huì)被分到數(shù)組部分
print(#t) -- 輸出4

-- 另一個(gè)故事
local t = {1,2,3,4}
t[6] = 6
print(#t) -- 輸出6
-- 根據(jù)利用率大于50%原則，2^3次方區(qū)間總個(gè)數(shù)為5，滿足條件，t[6]會(huì)被分到數(shù)組部分

• 數(shù)組末位+1存在時(shí)，數(shù)組size翻倍找空值，再二分查找最大key
  這一部分的代碼是在hash_search函數(shù)中

local t = {nil, 2, 3, 4} -- 數(shù)組部分
t[5] = 5 -- 哈希部分
print(#t) -- 輸出5
-- key = 5存在時(shí)，數(shù)組大小=4，翻倍找空值，key = 8不存在，找到空值
則大小落在4-8之間，二分...
最終找到key = 5

原創(chuàng)文章，僅發(fā)布于我的簡(jiǎn)書與我的博客中，禁止轉(zhuǎn)載!