994
lua 5.0的實現（翻譯)4,5
4、 表
Table是lua的主要——實際上，也是唯一的——數據結構。Table不僅在語言中，同時也在語言的實現中扮演著重要角色。Effort spent on a good implementation of tables is rewarded in the language,because tables are used for several internal tasks, with no qualms about performance。這有助於保持實現的小巧。相反的，任何其他數據結構的機製的缺乏也為table的高效實現帶來了很大壓力
Lua中的table是關聯數組，也就是可以用任何值做索引（除了nil），也可以持有任何值。另外，table是動態的，也就是說當加進數據的時候它們將增長（給迄今不存在的域賦值）而移除數據的時候將萎縮（給域賦nil值）。
不像大多數其他腳本語言，lua沒有數組類型。數組被表示為以整數做鍵的table。用table作為數組對於語言是有益的。主要的（益處）顯而易見：lua並不需要操縱表和數組的兩套不同的運算符。另外，程序員不用對兩種實現做出艱難選擇。在lua中實現稀疏數組是輕而易舉的。例如，在Perl裏麵，如果你嚐試去跑$a[1000000000]=1 這樣的程序，你能跑出個內存溢出！（you can run out of memory），因為它觸發了一個10億個元素的數組的創建（譯注，Perl的哲學是：去除不必要的限製）。而等價的lua程序 a={[1000000000]=1},（隻是）創建了有一個單獨的項的表（而已）。
直到lua 4.0，table都是作為hash表嚴格地實現：所有的pair都被顯式地保存。Lua5.0引入了一個新算法來優化作為數組的table：它將以整數為鍵的pair不再是存儲鍵而是優化成存儲值在真正的數組中。更精確地說，在lua 5.0中，table被實現為一個混合數據結構：它們包括一個hash部分和一個數組部分。圖2展示了一個有"x"→ 9.3, 1 → 100,2 → 200, 3 → 300對子的表的一種可能結構。注意到數組部分在右邊，並沒有存儲整數的key。這個劃分僅僅是在一個低的實現層次進行的，訪問table仍然是透明的，甚至在虛擬機內部（訪問table）也是如此。Table根據內容自動並且動態地對兩個部分進行適配：數組部分試圖從1到n的相應地存儲值，關聯非整數鍵或者整數鍵超過數組範圍的值被存儲在hash部分。
當一個table需要增長時，lua重新計算hash部分和數組部分的大小。任一部分都可能是空的。重新計算後的數組大小是至少是當前使用的數組部分從1到n的一半情況下的最大n值（原文：The computed size of the array part is the largest n such that at least half the slots between 1 and n are in use）（稀疏數組時避免浪費空間），並至少有一個（元素）處在n/2+1到n的槽中（當n被2整除時，避免n的這樣的數組大小）。計算完大小後，lua創建了“新”的部分並將“舊”的部分的元素重新插入到的“新”的部分。作為一個例子，假設a是一個空表；它的數組部分和hash部分的大小都是0。當我們執行a[1]=v時，這個表需要增長到足夠容納新的鍵。Lua將為新的數組部分的大小選擇n=1（帶有一個項1→v）。hash部分仍然保持為空。
這個混合的方案有兩個優點。首先，訪問以整數為鍵的值加快了，因為不再需要任何的散列行為。其次，也是最重要的，數組部分占用的內存大概是將數組部分存儲在hash部分時的一半，因為key在數組中是隱式的（譯注：也就是數組的下標）而在hash部分卻是顯式的。因而，當一個table被用作數組的時，它表現的就像一個數組，隻要整數鍵是密集。另外，不用為hash部分付出任何內存和時間上的懲罰，因為它（譯注：hash部分）甚至都不存在。相反的控製：如果table被用作關聯數組而非一個數組，數組部分可能就是空的。這些內存上的節省是比較重要的，因為lua程序經常創建一些小的table，例如table被用來實現對象（Object）（譯注，也就是用table來模仿對象，有點類似javascript中的json）。
Hash部分采用Brent's variation[3]的組合的鏈狀發散表。這些table的主要不變式是如果一個元素沒有在它的主要位置上（也就是hash值的原始位置），則衝突的元素在它自己的主要位置上。換句話說，僅當兩個元素有相同的主要位置（也就是在當時table大小情況下的hash值）時才有衝突的。沒有二級衝突。正因為那樣，這些table的加載因子可以是100%而沒有性能上的損失。這部分不是很明白，附上原文：
The hash part uses a mix of chained scatter table with Brent's variation [3].
A main invariant of these tables is that if an element is not in its main position
(i.e., the original position given by its hash value), then the colliding element
is in its own main position. In other words, there are collisions only when two
elements have the same main position (i.e., the same hash values for that table
size). There are no secondary collisions. Because of that, the load factor of these
tables can be 100% without performance penalties.
5、函數和閉包
當lua編譯一個函數的時候，它產生一個模型（prototype），包括了函數的虛擬機指令、常量值（數字，字符串字麵量等）和一些調試信息。運行的時候，無論何時lua執行一個function…end表達式，它都創建一個新的閉包。每個閉包都有一個引用指向相應的模型，一個引用指向環境（environment）（一張查找全局變量的表，譯注：指所謂環境就是這樣一張表），和一組用來訪問外部local變量的指向upvalue的引用。
詞法範圍以及first-class函數的組合導致一個關於（如何）訪問外部local變量的著名難題。考慮圖3中的例子。當add2被調用的時候，它的函數體（body）部分引用了外部local變量x (函數參數在lua裏是local變量，譯注：x就是所謂的自由變量，這裏形成了閉包)。盡管如此，當add2被調用時，生成add2的函數add已經返回。如果在棧中生成變量x，（x在棧的）其棧槽將不複存在。（譯注，此處的意思應該是說如果在棧保存變量x，那麼在調用add2的時候，add函數早已經返回，x也在add2調用前就不在棧裏頭了，這就是那個著名難題）。
大多數過程語言通過限製詞法範圍（例如python），不提供first-class函數（例如Pascal），或者都兩者都采用（例如c,譯注：也就是說c既不把函數當一等公民，也限製詞法範圍）來回避這個問題。函數式語言就沒有那些限製。圍繞著非純粹函數語言比如Scheme和ML的研究已經產生了大量的關於閉包的編譯技術的知識（參見[19, 1, 21]）。盡管如此，這些工作並沒有盡力去限製編譯器的複雜性。以優化的Scheme編譯器Bigloo的控製流分
析階段為例，（它的實現）比lua實現的10倍還大：Bigloo 2.6f的Cfa模塊源碼有106,350行 VS. 10,155行的lua5.0核心。正如第2部分已經解釋過的（原因），lua需要簡單。
Lua使用了一個稱為upvalue的結構來實現閉包。任何外部local變量的訪問都是通過一個upvalue間接進行的。Upvalue初始指向的是變量存活位置的棧槽（參見圖4的左半部分）。當變量（x）已經離開作用域（譯注，也就是這裏的add函數返回時），它就遷移到upvalue結構本身一個槽中（參見圖4的右半部分）。因為（對變量的）訪問是間接地通過upvalue結構中的一個指針進行的，因此這個遷移對於任何寫或者讀該變量的代碼都是透明的。不像它的內嵌函數（譯注：例子的add2，它是指外部函數add），聲明變量的函數訪問該變量就像訪問它的local變量一樣：直接到棧。
通過每個變量最多創建一個upvalue結構並且在必要的時候複用它們，可變狀態得以在閉包之間正確地共享。為了保證這一約束，lua維持一個鏈表，裏麵是一個棧裏（圖4中的pending vars列表）的所有open upvalue（所謂open upvalue，是指仍然指向棧的upvalue結構）。當lua創建一個新的閉包的時候，它遍曆所有的外部local變量。對於每個（外部local）變量，如果它在列表中找到一個open upvalue，那麼它就複用這個upvalue結構。否則，lua就創建一個新的upvalue並將它放入鏈表。注意到列表搜索隻是探測了少數幾個節點，因為列表最多包含一個被內嵌函數使用的local變量的項。當一個closed upvalue不再被任何閉包引用的時候，它最後將被當作垃圾並回收。
一個函數允許訪問一個不是它的直接外圍函數的外部local變量，隻要（這個local變量）是外部函數的（outer function）。在那種情況下，甚至在閉包被創建的時候，（外部local）變量可能就不在棧裏了。Lua使用扁平閉包（flat closures）解決這種情況[5]。通過扁平閉包，一個函數無論何時去訪問一個不屬於它的外圍函數的外部變量，這個變量都將進入外圍函數的閉包。從而當一個函數被實例化
文章轉自莊周夢蝶 ，原文發布時間
最後更新：2017-05-17 18:01:42