精讀《手寫 SQL 編譯器 - 性能優化之緩存》

Arno 發布于2019-08-23 12:47 / 379人閱讀

摘要：引言重回手寫編輯器系列。現在節點不匹配時性能已經最優，那下一步就是如何優化匹配時的性能，這時就用到節點緩存。更多討論討論地址是精讀手寫編譯器性能優化之緩存如果你想參與討論，請點擊這里，每周都有新的主題，周末或周一發布。

1 引言

重回 “手寫 SQL 編輯器” 系列。這次介紹如何利用緩存優化編譯器執行性能。

可以利用 Frist 集 與 Match 節點緩存 這兩種方式優化。

本文會用到一些圖做解釋，下面介紹圖形規則：

First 集優化，是指在初始化時，將整體文法的 First 集找到，因此在節點匹配時，如果 Token 不存在于 First 集中，可以快速跳過這個文法，在文法調用鏈很長，或者 “或” 的情況比較多時，可以少走一些彎路：

如圖所示，只要構建好了 First 集，不論這個節點的路徑有多長，都可以以最快速度判斷節點是否不匹配。如果節點匹配，則繼續深度遍歷方式訪問節點。

現在節點不匹配時性能已經最優，那下一步就是如何優化匹配時的性能，這時就用到 Match 節點緩存。

Match 節點緩存，指在運行時，緩存節點到其第一個終結符的過程。與 First 集相反，First 集可以快速跳過，而 Match 節點緩存可以快速找到終結符進行匹配，在非終結符很多時，效果比較好：

如圖所示，當匹配到節點時，如果已經構建好了緩存，可以直接調到真正匹配 Token 的 Match 節點，從而節省了大量節點遍歷時間。

這里需要注意的是，由于 Tree 節點存在分支可能性，因此緩存也包含將 “沿途” Chances 推入 Chances 池的職責。

2 精讀

那么如何構建 First 集與 Match 節點緩存呢？通過兩張圖解釋。

構建 First 集

如圖所示，構建 First 集是個自下而上的過程，當訪問到 MatchNode 節點時，就可以收集作為父節點的 First 集了！父集判斷 First 集收集完畢的話，就會觸發它的父節點 First 集收集判斷，如此遞歸，最后完成 First 集收集的是最頂級節點。

構建 Match 節點緩存

如圖所示，訪問節點時，如果沒有緩存，則會將這個節點添加到 Match 緩存查找隊列，同時路途遇到 TreeNode，也會將下一個 Chance 添加到緩存查找隊列。直到遇到了第一個 MatchNode 節點，則這個節點是 “Match 緩存查找隊列” 所有節點的 Match 節點緩存，此時這些節點的緩存就可以生效了，指向這個 MatchNode，同時清空緩存查找隊列，等待下一次查找。

3 總結

拿 select a, b, c, d from e 這個語句做測試：

node 節點訪問次數	Frist 集優化	First 集 + Match 節點緩存優化
784	669	652

從這個簡單 Demo 來看，提效了 16% 左右。不過考慮到文法結構會影響到提效，對于層級更深的文法、能激活深層級文法的輸入可以達到更好的效率提升。

4 更多討論

討論地址是：精讀《手寫 SQL 編譯器 - 性能優化之緩存》 · Issue #110 · dt-fe/weekly

如果你想參與討論，請點擊這里，每周都有新的主題，周末或周一發布。前端精讀 - 幫你篩選靠譜的內容。

云數據庫MySQL cdn之高速緩存編譯器優化緩存優化性能優化

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/99009.html

精讀《手寫 SQL 編譯器 - 智能提示》

摘要：經過連續幾期的介紹，手寫編譯器系列進入了智能提示模塊，前幾期從詞法到文法語法，再到構造語法樹，錯誤提示等等，都是為智能提示做準備。 1 引言詞法、語法、語義分析概念都屬于編譯原理的前端領域，而這次的目的是做具備完善語法提示的 SQL 編輯器，只需用到編譯原理的前端部分。經過連續幾期的介紹，《手寫 SQL 編譯器》系列進入了智能提示模塊，前幾期從詞法到文法、語法，再到構造語法...

ztyzz 2019-08-23 14:15 評論0 收藏0
精讀《syntax-parser 源碼》

摘要：引言是一個版語法解析器生成器，具有分詞語法樹解析的能力。實現函數用鏈表設計函數是最佳的選擇，我們要模擬調用棧了。但光標所在的位置是期望輸入點，這個輸入點也應該參與語法樹的生成，而錯誤提示不包含光標，所以我們要執行兩次。 1. 引言 syntax-parser 是一個 JS 版語法解析器生成器，具有分詞、語法樹解析的能力。通過兩個例子介紹它的功能。第一個例子是創建一個詞法解析器 my...

yuanxin 2019-08-23 15:37 評論0 收藏0
精讀《手寫 SQL 編譯器 - 語法樹》

摘要：返回的語法樹作為結果被傳遞到文法中，其結果可能是。每個元素的子節點全部執行完畢，才會生成當前節點的語法樹。更多討論討論地址是精讀手寫編譯器語法樹如果你想參與討論，請點擊這里，每周都有新的主題，周末或周一發布。 1 引言重回手寫 SQL 編輯器系列。之前幾期介紹了詞法、文法、語法的解析，以及回溯功能的實現，這次介紹如何生成語法樹。基于《回溯》一文介紹的思路，我們利用 JS ...

Caicloud 2019-08-23 11:31 評論0 收藏0