跳至主要内容

改進 V8 正則表達式

· 閱讀時間約 7 分鐘
Patrick Thier 和 Ana Peško，對正則表達式有獨到見解的正則表達式專家

在其默認配置中，V8 在正則表達式首次執行時將其編譯為本地代碼。作為我們對JIT-less V8工作的的一部分，我們引入了一個正則表達式解釋器。解釋正則表達式的優勢是使用更少的內存，但代價是性能下降。在這篇博客文章中，我們描述了如何在減少性能損失的同時利用解釋正則表達式的優勢。

正則表達式的分層提升策略​

我們希望對正則表達式採取‘兩者兼得’的策略。為了實現這一點，我們首先將所有正則表達式編譯為字節碼並進行解釋。這樣，我們可以節省大量的內存，而總體上（以及通過新的、更快的解釋器）性能損失是可以接受的。如果一個相同模式的正則表達式被再次使用，我們認為它是‘熱’的，因此將其重新編譯為本地代碼。在這一點上，我們將會以最快的速度執行。

在 V8 的正則表達式代碼中有許多不同的執行路徑，這取決於調用的方法是否是全域的或非全域的正則表達式，以及我們是否採用快速或緩慢的路徑。話雖如此，我們希望分層提升的決策儘可能集中。我們已經向 V8 的 RegExp 對象添加了一個 ticks 字段，該字段在運行時初始化為某個值。此值表示在提升到編譯器之前，正則表達式將被解釋的次數。每次解釋正則表達式時，我們將 ticks 字段減 1。在由CodeStubAssembler編寫的一個內建函數中，我們會在每次執行時檢查 ticks 標誌。當 ticks 降至 0 時，我們知道需要將正則表達式重新編譯為本地代碼，並跳轉到運行時執行此操作。

我們提到過，正則表達式可能會有不同的執行路徑。針對使用函數作為參數進行全域替換的情況，本地代碼和字節碼的實現方式是不同的。本地代碼會預期一個陣列來提前存儲所有匹配項，而字節碼一次匹配一個。因此，我們決定對這種使用情況始終提前切換到本地代碼。

加速正則表達式解釋器​

消除運行時開銷​

當執行正則表達式時，會調用由CodeStubAssembler編寫的一個內建函數。之前這個內建函數會檢查 JSRegExp 對象的代碼字段是否包含可以直接執行的 JIT 編譯的本地代碼，否則它會調用運行時方法以編譯（在 JIT-less 模式中為解釋）正則表達式。在 JIT-less 模式中，每次執行正則表達式都需要通過 V8 的運行時，這非常昂貴，因為在執行堆疊上需要在 JavaScript 和 C++ 代碼之間進行切換。

從 V8 v7.8 開始，每當正則表達式編譯器生成字節碼來解釋正則表達式時，除了生成的字節碼外，解釋器的跳板現在也會被存儲在 JSRegExp 對象的代碼字段中。通過這種方式，解釋器現在可以直接從內建函數調用，而無需通過運行時。

新的分派方法​

正則表達式解釋器之前使用的是基於簡單switch的分派方法。這種方法的主要缺點是 CPU 很難預測下一個要執行的字節碼，導致大量的分支錯誤預測，減慢了執行速度。

我們在 V8 v7.8 中將分派方法更改為線程代碼。該方法可以讓 CPU 的分支預測器根據正在執行的字節碼預測下一個字節碼的執行，從而減少錯誤預測。更具體地，我們使用了一個分派表（dispatch table），存儲每個字節碼 ID 和實現該字節碼的處理程序地址之間的映射。V8 的解釋器Ignition也使用了這種方法。然而，Ignition 和正則表達式解釋器之間的主要區別在於，Ignition 的字節碼處理程序是使用CodeStubAssembler編寫的，而整個正則表達式解釋器是使用 C++（使用計算goto——一個由 GNU 擴展並且由 clang 支持的特性）編寫的，這比 CSA 更易於閱讀和維護。對於那些不支持計算 goto 的編譯器，我們則退回到以前基於switch的分派方法。

字節碼偷看式優化​

在我們討論位元碼窺孔優化之前，我們先來看一個具有啟發性的範例。

const re = /[^_]*/;
const str = 'a0b*c_ef';
re.exec(str);
// → 相符 'a0b*c'

對於這個簡單的模式，正則表達式編譯器會為每個字元創建執行的 3 條位元碼。在高層次上，這些是：

  1. 加載當前字元。
  2. 檢查字元是否等於 '_'。
  3. 如果不是，則將當前位置在目標字串中前移，並 goto 1。

對於我們的目標字串，我們解釋了 17 條位元碼直到找到不匹配的字元。窺孔優化的想法是，我們用新優化的位元碼替換位元碼序列，該位元碼結合了多個位元碼的功能。在我們的範例中，我們甚至可以在新的位元碼中顯式處理由 goto 創建的隱性迴圈，因此單個位元碼處理所有匹配的字元，節省了 16 次調度。

儘管這個範例是編造的，但這裡描述的位元碼序列在真實網站中經常出現。我們分析了真實網站，並為經常遇到的位元碼序列創建了新的優化位元碼。

結果​

圖1：不同階段升級值的記憶體節省量

圖1 顯示了不同階段升級策略對 Facebook、Reddit、Twitter 和 Tumblr 瀏覽故事的記憶體影響。預設是 JIT 編譯代碼的大小，然後是我們最終使用的正則表達式代碼的大小（如果不升級的位元碼大小，如果升級的原生代碼大小），對於初始化為 1、10 和 100 的 ticks。最後，我們有如果解釋所有正則表達式的正則表達式代碼大小。我們使用這些結果和其他基準來決定啟用 ticks 初始化為 1 的階段升級策略，即我們解釋正則表達式一次，然後升級。

有了這個階段升級策略，我們在現實網站上減少了 V8 堆代碼大小 4 到 7%，以及 V8 有效大小 1 到 2%。

圖2：正則表達式性能比較

圖2 顯示了在 RexBench 基準套件中，本文描述的所有改進對正則表達式解釋器性能的影響1。作為參考，還顯示了 JIT 編譯正則表達式性能（原生）。

新的解釋器最多比舊的快 2 倍，平均快約 1.45 倍。對於大多數基準測試，我們甚至非常接近 JIT 編譯的正則表達式性能，Regex DNA 是唯一的例外。在這個基準中，解釋的正則表達式比 JIT 編譯的正則表達式慢得多的原因是使用了很長的目標字串（約 300,000 個字元）。即使我們將調度開銷降至最低，在超過 1,000 個字元的字串上，開銷仍會累加，導致執行速度減慢。由於解釋器在長字串上太慢，我們添加了一個啟發式方法，對這些字串積極地升級。

結論​

從 V8 v7.9（Chrome 79）開始，我們將正則表達式分階段編譯，而非急於編譯。因此，以前僅用於無 JIT 的 V8 的解釋器現在在任何地方都會使用。結果我們節省了記憶體。我們加快了解釋器的速度以使此可行。但這不是故事的終結——未來可以期待更多的改進。

我們想藉此機會感謝 V8 團隊在我們實習期間的支持。這是一段非常棒的經歷！

Footnotes​

  1. 此處顯示的結果還包括一項已在 V8 v7.8 版本說明 中描述的正則表達式改進。 ↩