加快字串速度

Wiki

摘要

在 lua-l 上曾針對將字串從 C 傳遞到 Lua 的成本進行多次討論（例如 [1]），並暗示這會造成主要的額外負擔。本頁面試圖記載一項修改 Lua 的實驗，透過實作「預儲字串」來減少建立字串的額外負擔，即支援延遲 intern 的字串。本文說明一個範例 API，並提供用於驗證概念的 API 實作效能測試基準結果。

在有執行緒的環境中無法安全使用建議的 API，除非有嚴格的限制，而且這些限制可能難以保證。此外，效能測試基準結果並未顯示在常見用例中潛在有顯著的速度提升。

簡而言之，這更像是失敗的實驗而非建議，但報告失敗也很有用，以避免重蹈覆轍。

字串串接

基本上，Lua API 將字串匯入 Lua 時所遵循的流程為，使用 lua_pushlstring() 或作為建立新字串的原語的結果

1) 從字串中計算不超過 32 個字元的範本雜湊。

2) 使用雜湊，在全域的 intern 字串雜湊表中查詢字串。

3) 如果找到現有的字串，則使用該字串。

4) 否則，會配置一個新的 TString 物件，並將字串複製到其中。會使用步驟 1 中所計算的雜湊值將新物件插入 intern 表格。

這特別適用於可能已存在於 intern 表格中的短字串，例如全域變數名稱和其他表格鍵，因為這能避免不必要地配置或複製所提供的字串，儘管會產生將新字串與現有字串進行完整比對的成本。

如果字串不太可能已經存在於 intern 表格中，這也相當適用，因為雜湊查詢可能永遠不會比對鏈上任何現有字串的幾個字元以上，儘管會產生記憶體配置和複製的成本。

儘管如此，在某些用例中，這些額外負擔可能看似過度。有些人擔心 intern 的成本對從未使用作表格鍵的字串來說過高，而其他人則專注於步驟 4 中的複製，如果要逐步建構字串或由某些其他需要定長緩衝區的函式庫建立字串（例如 fread），這可能會是不必要的。

API 的演進

由於我是屬於第二組，我想知道是否可以找到一個方法來允許建立一個新的字串而不進行複製會是有用的。在表面上看來，這看起來很簡單：您只需要建立一個類似於字串（或是至少與字串一樣大小）的東西並提供起始位址；API 使用者接下來就能依照需要填入內容，然後透過儲存在內部將這個物件轉換為一個真正的字串。

這建議了一個簡潔的 API

   lua_newprestring(L, size);
   lua_tostring(L, index);
   /* Note that lua_tostring is a macro which expands
    * to lua_tolstring(L, index, NULL);
    */

現在，前字串是一個真正的 Lua 物件，因此理論上來說它可以從一個 C 函式中做為一個未儲存在內部的字串來傳回。由於它是透過在其上呼叫 `lua_tolstring` 轉換成一個真正的字串，而且由於 `lua_tostring` 是用於提取字串位址和長度的 API，因此為了使用前字串並不一定需要修改標準函式庫函式，儘管具備一個允許使用前字串而不用儲存在內部的 API 呼叫會很有用

   lua_rawtolstring(L, index, &len);

我可以劫持 `lua_topointer`，但 `lua_topointer` 不會傳回字串長度；此外，最好知道堆疊索引中的物件實際上是一個字串，而不仅仅是一個可能具有指標的任何東西。

我第一次嘗試使用 API 是撰寫一個 `file` 方法 `:buffers`，它是一個具有固定長度的類似於 `:lines` 的類比

   for b in f:buffers(2000) do
     -- #b is 2000 unless there are fewer than
     -- 2000 characters to read
   end

這表示 `:buffer` 的實作需要能夠知道前字串是否已被轉換爲字串，這需要另一個 API

   lua_rawtoprestring(L, index, &len);

透過使用 `lua_rawtoprestring` 和 `lua_newprestring`，:buffer 可以決定是要回收一個前字串還是建立一個新的，但由於現在看來難以證明的理由，我新增了另一個結合這兩個動作的 API；實作中語意上最複雜的 API 呼叫

   lua_toprestring(L, index, &len);

1) 如果它是一個前字串，就不會修改它；

2) 倘若它是一個字串，則建立一個具有相同長度的新的前字串（不會複製內容），然後用新的前字串替換堆疊位置「index」；

3) 倘若它是任何其他東西，則建立一個新的前字串，其長度為「&len」參數目前的指向值，然後用新的前字串替換堆疊位置「index」；

4) 最後，不論上述執行了哪個，都傳回堆疊位置「index」中前字串的地址和長度

雖然這難以解釋，也可能難以理解，但用起來卻相當容易。譬如說，:buffers 的實作如下

static int io_readbuf (lua_State *L) {
  FILE *f = *(FILE **)lua_touserdata(L, lua_upvalueindex(1));
  if (f == NULL)
    luaL_error(L, "file is already closed");
  else {
    size_t nread;
    size_t toread = lua_tointeger(L, lua_upvalueindex(2));
    char *buf = lua_toprestring(L, lua_upvalueindex(3), &toread);
    nread = fread(buf, 1, toread, f);
    if (nread == toread)
      lua_pushvalue(L, lua_upvalueindex(3));
    else if (nread > 0)
      lua_pushlstring(L, buf, nread);
    else if (ferror(f))
      luaL_error(L, "%s", strerror(errno));
    else
      lua_pushnil(L);
  }
  return 1;
}

static int f_buffers (lua_State *L) {
  size_t bufsize;
  tofile(L);
  bufsize = luaL_optinteger(L, 2, LUAL_BUFFERSIZE);
  lua_settop(L, 1);
  lua_pushinteger(L, bufsize);
  lua_pushnil(L);
  lua_pushcclosure(L, io_readbuf, 3);
  return 1;
}

前字串只是一個初生的字串

此整個過程的一項要點是，前字串會明確地或在需要時就地轉換成字串。前字串沒有單獨的類型；在未呼叫上述感知前字串的 API 之一的情況下，它們看起來隨時都像是普通字串。現有的 C 模組和 Lua 程式無需以任何方式修改，就能考慮到前字串的存在，而倘若您想要一個 C 模組避免自動置入前字串內部，只需要將「lua_tolstring」替換成「lua_rawtolstring」即可。

由於前字串實際上是一個延遲置入內部的字串，因此在 Lua 環境中它必須表現得好像它是一個字串。這表示，必須將它置入內部，才能將它當成表格鍵來使用。（概念驗證的實作還會自動將前字串（== 的引數）置入內部。）

前字串置入內部成字串之後，就不能再變更。因此，修改已釋出到 Lua 環境中的前字串並非安全之舉。在讓任何 Lua 或 CFunction 看見前字串之前，您必須完成建立前字串的內容。

在非執行緒環境中這樣做沒問題，而上述的 :buffers 實作會這麼做；它會小心不要在未檢查前字串是否仍然是前字串的情況下修改它。但它無法在執行緒環境中安全地執行；:buffers 的重複執行函式未在「lua_lock」內部執行，而持有緩衝區參考的另一個處理程序可能在「fread」呼叫進行的同時對它進行字串化。

這很遺憾，因為我針對概念驗證實作執行的基準測試顯示，唯一顯著的加速方法是透過硬迴圈來回收前字串。在我看來，置入內部的負擔，甚至複製字串，都不足以證明實作的複雜性是合理的。

嘗試建立基準測試

我嘗試的第一個基準測試是讀寫檔案緩衝器，它使用的函式相當類似於上方所示的 :buffers。透過加入 :buffers 迭代器並把一些呼叫 lua_tolstring 改為 lua_rawtostring 來修改 iolib。然而，所有計時都由輸入/輸出系統呼叫所主導，因此除了證明在檔案輸入/輸出的正常使用中，所節省的效能甚至可能微不足道，結果並未具有決定性。

為了嘗試更精確地衡量可得的優點，我建立了一種偽檔案，它在環狀緩衝器中包含將近 16K 個隨機可列印字元。透過複製所要求的位元組數，以及隨著內部「檔案」位置前進，進行「讀取」環狀緩衝器，總是對環狀緩衝器大小（它是一個質數）進行模組運算。環狀緩衝器會定期重新加以隨機化；最終結果是給定「讀取」結果為現有字串的可能性極低。

使用上述 API，至少有四種可能的方式可以傳回字元緩衝器

1)「回收」：總是傳回同一 prestring，並載入新內容

2)「prestring」：每次都傳回新的 prestring，但不要將其內部化

3)「inplace」：透過先建立正確大小的 prestring，然後將資料讀入其中，最後將 prestring 轉換為字串的方式建立新的字串，在傳回前執行此動作。

4)「string」：目前的機制：將檔案讀入 prestring（儘管它可能只是一個預先配置的緩衝器），然後呼叫 lua_pushlstring 以一般的方式建立字串。

比較這四種策略所花的時間，可以揭示下列代價

1) 配置記憶體（「prestring」與「回收」之間的差異）

2) 內部處理（「inplace」與「prestring」之間的差異）；以及

3) 複製（「string」與「inplace」之間的差異）。

此基準測試是在執行 Xubuntu 的筆記型電腦上完成的，過程相當不科學（我試著在基準測試執行期間不使用機器，但是仍有許多程序正在運作中）。Lua 已編譯為 -O2 -DLUA_USE_APICHECK（雖然我不認為這會影響相對時序，但它應該要在沒有 LUA_USE_APICHECK 的情況下編譯；顯而易見，報告的執行時間比生產版本中應該執行的時間要慢。此機器在 64 位元環境中執行 AMD Turion。對於每個緩衝區大小，模擬檔案大小已設定為 1,000,000 個緩衝區，並使用 os.clock 來蒐集執行時間，因此結果可以當成每個緩衝區的 μs。每次測試執行 10 次，並選取摘要中最快的時間；結果總結於 檔案：wiki_insecure/users/rici/buftest.pdf。可以看出，串接時間約為每個字串的 200-250 奈秒，僅會針對極短字串明顯地感受到；複製時間最長只有總時間的 13%，而緩衝區則已測試為最大值。

概念驗證

此實作並未經過特別優化，且由於結果並不特別出色，因此我不太可能繼續開發它。如果您有興趣，我已放置其中一個修補程式在 檔案：wiki_insecure/users/rici/prestring.diff

關於此實作的某些注意事項

垃圾回收

每個可垃圾回收的物件都有 next 成員，Lua 使用它來執行垃圾回收的掃描階段。不是字串的物件會保存在單一連結串列中，其頭部位在全域狀態。然而，字串保存在字串串接表格中，而 next 成員用於連結雜湊鏈。（事實上，每個雜湊鏈的頭部都是垃圾回收根的一部分。）

一旦將 prestring 串接，就必須從已配置的物件連結串列移除，並連結到串接表格中相對應的雜湊鏈。我能想到執行的唯一方法就是將已配置的 prestring 串列雙向連結。後向指標會保存在 union 中，其中成員為 prestring 所不需要的 hash。在 32 位元架構中，這不會造成任何成本，但在 64 位元架構中，它會將字串開銷從 24 位元組增加到 32 位元組，因為 hash 是 int。或許更好的方式僅假設永遠不會有太多 prestring，並將它們保存在單一連結串列中，當 prestring 被串接時，只需要線性搜尋即可。

除此之外，我不認為有任何 GC 問題。像字串一樣，prestring 總是會在堆疊上建立，並且可以建立為白色，因為堆疊會自動標記。

鎖定

lua_lock 和 lua_unlock 巨集提供的鎖定機制設計為避免垃圾回收或表格調整大小干擾 API 呼叫或 VM 執行。即使在理論上，Lua 也不會嘗試防止競況情況出現的其他物件變異。

前綴字串引進一種變異的新形式：將可變物件（前綴字串）變更為不可變物件（字串）。如上所述，lua_lock 機制無法防止在變更前綴字串內容與將前綴字串變更為字串之間的競爭狀態。

其他事項

前綴字串的類型與字串相同（LUA_TSTRING），而且除了 hash 資訊符之外，記憶體配置也相同。已在物件標題增加一個旗標，用以區分前綴字串和字串。

當將前綴字串內部處理時，有可能會得到一個現有的字串為結果。在此狀況下，我們將得到兩個物件：一個前綴字串和一個舊字串。這可能會導致同一前綴字串被重複內部處理數次。為了降低這類狀況發生的可能性，由金鑰搜尋和等號運算子執行的自動內部處理都會將字串指標重新設定為舊字串；實作此項功能時需要將多個內部原型從 const 變更為 non-const，而且無法有效解決問題。

我想在 前綴字串內存放一個轉發指標（使用重載的回溯指標/hash），並於垃圾回收過程中重新撰寫字串指標，這樣或許會更好。（垃圾收集器無法重新撰寫 C 呼叫堆疊架構中的指標，但應能在其他地方重新撰寫這些指標。重新撰寫 C 呼叫堆疊架構中的指標可能會導致垃圾收集器在 C 函式使用指向 前綴字串 的指標時，將 前綴字串 釋放掉。）

——RiciLake