快速字串修補程式
 |
||
|
快速字串修補程式 |
|
其概念源自於 Rici Lake 的創意（於 2005 年 5 月簡述於「Lua 字串作為『原子』」之郵件串中）。之後又在 irc #lua 中進一步討論和改善。我決定進行原型實作來測試這個概念的有效性。
此修補程式的目的是想取得有關 Lua 應用程式中快字串實用性的回饋。歡迎提供任何評論。特別需要針對使用大量（不同）小字串的實際應用程式進行效能評量比較。謝謝！
為避免誤解：此修補程式 *並非* 預計會併入 Lua 5.1 標準版本，而我也不建議在此時這麼做。是否此修補程式中的任何內容值得納入未來的 Lua 版本，我全權交由 Lua 作者判斷。
請將您的評論傳送至 Lua 郵件串，因為 Wiki 並不適合進行討論。
-- MikePall
授權聲明：我特此宣告，我對 Lua 核心所做的所有貢獻，應受與 Lua 核心相同的授權條款規範。
按一下以下載 修補程式本身 或 已套用修補程式的 Lua 5.1-work6 版本。
基線已包含多項修正：MSVC number2int 修正、*s 效能改善、移除未定義的 lua_checkpc 判斷。
Lua 會將所有物件儲存在 Lua 堆疊或 Lua 函式中的標籤值佔位中。這些佔位通常為 12 或 16 位元組長（視架構和 lua_Number 類型而異）。大小主要是因為需要儲存對齊良好的指標和 lua_Number。標籤本身是一個小整數，可輕鬆放入單一位元組中。因此我們有多達 11 或 15 個位元組的可用空間，可以妥善運用。
基本構想是將快速字串（例如，最多 11 或 15 位元組的短字串）直接儲存在標籤值佔位中，而非在堆積區中配置這些字串。
這表示快速字串在行為上更類似於數字，因為這些字串不需要配置、垃圾回收或釋放。這樣可大幅減少 VM 的負擔。
Lua API 和 Lua/C API 皆無更動。無須變更您在 Lua 或 C 模組中的任何內容（但請參閱「注意事項」下的說明中有關 Lua/C API 相符性的部分說明）。
高速字串在 Lua 核心之外表現和一般字串完全相同。你不需透過任何特殊條款來使用它們，而且在外部也看不出來有差別。
是，這表示 type() 會回傳「string」，而 lua_type() 會回傳 LUA_TSTRING，不論字串在內部如何儲存。你可以不受限制地使用所有 Lua 函式和所有 Lua/C API 函式。
當然，你的應用程式可能會變得更快、記憶體使用量也可能會更低。因此，你可能還是會注意到差別。但這差不多是這個修補程式的重點所在...
許多應用程式會大量使用短字串。眾所周知，一般應用程式所使用的字串長度分布，會有顯著偏向短字串的現象（例如名稱、標籤、識別代碼、自然語言文字等等）。而許多短字串的生命週期非常短（例如暫存資料，僅在區域範圍內使用）。
因此，短字串通常會造成記憶體管理（配置和釋放）、垃圾蒐集（標記和清除），以及管理共享字串雜湊表的龐大負擔。此外還有其他負擔，是因與其它受管理物件發生競爭而造成。
快速字串避免大部分這些負擔
共享字串表的兩個主要優點是字串相等性和表單查詢非常迅速。前者的需求是類型加上指標比對，後者可以重新使用預先運算的雜湊值（但需要與配置的字串一起儲存）。
如果操作方法正確，快速字串的相等性檢查一樣迅速：對標記數值槽進行大量比較速度很快，而標記數字的比對也可以最佳化（例如，透過取得快速字串長度）。快速字串雜湊處理可以使用對整個槽位進行快速的整體雜湊處理。任何剩下的雜湊負擔都可以透過避免在小型表單中產生雜湊值來減少（進行整體的線性比對會更快）。
很明顯地，選用合適的基準測試，幾乎都能證明一些東西。所以我省略一些目標基準測試，例如：lua -e 'for i in io.lines() do end' </usr/share/dict/words 或過度使用 string.gfind() 或 string.gsub()。
這些會顯示大幅變快 (取決於架構在 +60% 到 +200% 之間)，但可能不會執行典型的應用行為。
相反地，對於沒有廣泛使用短字串的標準基準測試，你不會看到任何差異 (例如，斐波那契數字或矩陣乘法)。
所以我已經從「偉大電腦語言比武」基準測試中選取明顯候選，並在不同的架構中比較它們
Benchmark | x86 x64 PPC32 PPC64 ------------+---------------------------------- hash | +38.2% +55.8% +40.9% +38.7% spellcheck | +23.6% +45.8% +17.7% +25.2% reversefile | +6.2% +22.7% +10.2% +13.6% wordfreq | +2.2% +8.3% +10.6% +8.6%嗯 ... 不錯吧？
但當然從實際應用中看到一些基準測試結果會更好。請分享你可能有的任何見解給郵件清單。謝謝！
目前不支援 16 位元系統，如果你嘗試，就會產生編譯器錯誤。這比較是測試和支援 16 位元 size_t 的問題 (注意，有些 16 位元系統使用 32 位元 size_t，但目前實作未針對此調整，且拒絕在所有 16 位元系統中編譯)。
快速字串實作的一項重要需求是不變更 Lua/C API。這樣可避免必須重新編寫任何 C 模組，並協助快速取得原型實作的回饋。
不過，快速字串與常規字串需要共存在 Lua 核心內，而且必須在幾乎所有地方接受不同的處理。但是，它們之間不應有任何明顯差異，而且應該是同樣處理的。這需要在內部和外部標記編號之間區分。
內部標記編號僅在 Lua 核心內可見，並儲存在所有標記值儲存槽 (堆疊和表格儲存槽) 和 GC 物件中。外部標記編號則僅在 Lua/C API 外可見，且所有 C 模組都會使用。
內部標籤數字定義於 lobject.h 中。所有名稱均以「TT」開頭（例如：TTNIL、TTBOOLEAN 等）。它們儲存在單個未簽署位元組中（TValue 結構中的 TT）。標籤數字分為 4 位元組的主要數字和 4 位元組的次要數字。主要數字保留基本物件類型，次要數字保留其他詳細資訊。次要數字目前僅用於布林值（用於保留 false (0) 或 true (1)）和快速字串（用於保留字串長度）。
在 Lua/C API 邊界上，所有內部標籤數字均對應至 lua.h 中定義的外部標籤數字。其名稱以「LUA_T」開頭（例如：LUA_TNIL、LUA_TBOOLEAN 等），且保留與標準 Lua 核心相同的含義。快速字串和一般字串都對應至相同的外部類型（LUA_TSTRING）。兩種呼叫的 API 皆可搭配兩種字串使用，撰寫完善的 C 模組絕不會發現有任何差異（但請見下方的「注意事項」）。
明智地配置內部標籤數字有助於加快許多常見檢查。例如，ttixstring() 可在一個操作中檢查兩種字串，且僅使用一個條件式。高效能敏感 l_isfalse() 巨集亦同。長度為上限的快速字串的標籤數字永遠為零（0x00），且也可作為 C 字串的終止符。這表示 lua_tolstring() 可以針對快速字串的堆疊槽位回傳一個指標。
由於現有 Lua/C API 提供的字串指標穩定性保證（請見下方），必須避免堆疊重新配置。對於原型實作，我決定使用固定的堆疊大小（請見 luaconf.h 中的 LUAI_FIXEDSTACK）。這當然不是長期的理想選擇，且有許多更好的解決方案：堆疊分塊、延遲堆疊複製／釋放或變更／擴充 Lua/C API 保證。不過，這不在此原型實作的範圍之內（很抱歉）。
除了內部類型系統所需的變更之外，所有建立或存取字串的位置都需要變更為可處理兩種變數。這是 ttixstring()、xsvalue() 和 xslen() 巨集以及 luaS_set* 函式和巨集的用途。物件複製已變更為複製整個標籤值槽位。也需要針對物件比較和雜湊表進行一些變更。在函式中轉儲／還原會在預先編譯的程式區塊中儲存外部類型值。
Lua 編譯器（llex.c、lparser.c、lcode.c）僅以 TString 指標的形式處理字串。為了避免進行大量修改且無任何明顯的效益，我們並未變更此設定。這表示編譯器在內部永遠使用一般字串（即使是簡短字串）。僅在將其用作函式原型常數時，才會將其轉換為標籤值（一般或快速字串）。用於偵錯資訊（例如變數名稱）的所有字串仍然是一般字串。這不會造成問題，因為偵錯 API 僅會回傳字串指標。
補丁看起來很長，因為有許多細微變更。但它對結果程式碼大小影響不大：它只新增約 1.8K 至 Lua 核心（在 x86 + gcc 3.3 上有預設設定）。
有一個可調整 (luaconf.h 中的 LUAI_FSTRINGWORDS) ，讓您可以在 32 位元系統上將快速的字串預設最大大小從 11 個字元變更為 15 個字元。請注意，64 位元系統總是使用 15 個字元為極限（這也是最大限制）。在設定這個值之前，請仔細閱讀 luaconf.h 中的說明。
這可能有助於您的字串有顯著的百分比落在 12..15 個字元範圍。但我未在自己的測試中發現任何顯而易見的效能提升。因此，我已選擇 pre 預設組態的較小堆疊/表格槽（保持 undefined 的 LUAI_FSTRINGWORDS）。
快速字串在從 Lua/C API 之外使用時，會像一般字串一樣表現。但是有幾個細微差異可能會影響程式，這個差異（可能不知不覺地）可能會利用標準的 Lua VM 的一些實作詳細資訊
1. lua_tostring()/lua_tolstring() 的規格說明：「由於 Lua 有垃圾回收，沒有保證 lua_tostring 所傳回的指標在相應的值從堆疊中移除後依然有效。」
以前，您有時可以破壞一般字串的堆疊槽並仍舊參照該指標（因為 GC 沒有馬上執行）。然而，這違背了 API 規定，而且可能會造成難以發現的錯誤。
由於快速字串傳回指標到堆疊槽本身，所以非相容的 C 模組 *絕對* 需要修正。
另外一個限制是，如果堆疊槽移動 (lua_insert())，快速字串指標可能會變得陳舊。但是，這非常罕見而且可以輕鬆避免。
2. Lua/C API 對於相同的字串，不保證字串 _指標_ 相等。
有些作者可能錯誤的假設，因為所有字串都是共用，所以對於相同的字串，總是傳回相同的指標。但通常並不是這樣。如果在 Lua 堆疊或表格之中沒有任何參照，字串可能會被解除配置並重新配置。
對於快速的字串，您可能會取得對於相同的字串，取得不同的指標，端看所指示的堆疊槽。而且，如果您碰巧重複使用相同的堆疊槽，您可能會取得對於不同的字串，取得相同的指標。
不論如何，Lua/C API 規格並未保證字串 _指標_ 相等。唯一可以適當地測試相等性的方法是使用 lua_equal() 或 lua_rawequal() API 函數。
對於字串指標相等性做出無效假設的 C 模組 *絕對* 會在快速字串補丁中中斷。
3. Lua/C API 明細並未明確說明 Lua 堆疊重新配置。在 Lua 堆疊重新配置（移動）時，從動態堆疊槽擷取的字串指標仍然維持穩定狀態，這是顯示存在的。
這是一個絕對必要的條件，因為幾乎任何 API 呼叫都可能會重新配置堆疊。在沒有此保證的情況下，一些 C 函式庫的呼叫（例如 string.gsub()）可能會中斷。
這便是原型實作中固定堆疊大小暫時解決方法的動機（請參閱「實作細節」中的上方）。
