1. 首页

手写 SQL 编译器 – 性能优化之缓存

1 引言

重回 “手写 SQL 编辑器” 系列。这次介绍如何利用缓存优化编译器执行性能。

可以利用 First 集Match 节点缓存 这两种方式优化。

本文会用到一些图做解释,下面介绍图形规则:

image

First 集优化,是指在初始化时,将整体文法的 First 集找到,因此在节点匹配时,如果 Token 不存在于 First 集中,可以快速跳过这个文法,在文法调用链很长,或者 “或” 的情况比较多时,可以少走一些弯路:

image

如图所示,只要构建好了 First 集,不论这个节点的路径有多长,都可以以最快速度判断节点是否不匹配。如果节点匹配,则继续深度遍历方式访问节点。

现在节点不匹配时性能已经最优,那下一步就是如何优化匹配时的性能,这时就用到 Match 节点缓存。

Match 节点缓存,指在运行时,缓存节点到其第一个终结符的过程。与 First 集相反,First 集可以快速跳过,而 Match 节点缓存可以快速找到终结符进行匹配,在非终结符很多时,效果比较好:

image

如图所示,当匹配到节点时,如果已经构建好了缓存,可以直接调到真正匹配 Token 的 Match 节点,从而节省了大量节点遍历时间。

这里需要注意的是,由于 Tree 节点存在分支可能性,因此缓存也包含将 “沿途” Chances 推入 Chances 池的职责。

2 精读

那么如何构建 First 集与 Match 节点缓存呢?通过两张图解释。

构建 First 集

image

如图所示,构建 First 集是个自下而上的过程,当访问到 MatchNode 节点时,就可以收集作为父节点的 First 集了!父集判断 First 集收集完毕的话,就会触发它的父节点 First 集收集判断,如此递归,最后完成 First 集收集的是最顶级节点。

构建 Match 节点缓存

image

如图所示,访问节点时,如果没有缓存,则会将这个节点添加到 Match 缓存查找队列,同时路途遇到 TreeNode,也会将下一个 Chance 添加到缓存查找队列。直到遇到了第一个 MatchNode 节点,则这个节点是 “Match 缓存查找队列” 所有节点的 Match 节点缓存,此时这些节点的缓存就可以生效了,指向这个 MatchNode,同时清空缓存查找队列,等待下一次查找。

3 总结

select a, b, c, d from e 这个语句做测试:

node 节点访问次数First 集优化First 集 + Match 节点缓存优化
784669652

从这个简单 Demo 来看,提效了 16% 左右。不过考虑到文法结构会影响到提效,对于层级更深的文法、能激活深层级文法的输入可以达到更好的效率提升。

4 更多讨论

讨论地址是:精读《手写 SQL 编译器 – 性能优化之缓存》 · Issue #110 · dt-fe/weekly

如果你想参与讨论,请点击这里,每周都有新的主题,周末或周一发布。前端周刊 – 帮你筛选靠谱的内容。

看完两件小事

如果你觉得这篇文章对你挺有启发,我想请你帮我两个小忙:

  1. 关注我们的 GitHub 博客,让我们成为长期关系
  2. 把这篇文章分享给你的朋友 / 交流群,让更多的人看到,一起进步,一起成长!
  3. 关注公众号 「画漫画的程序员」,公众号后台回复「资源」 免费领取我精心整理的前端进阶资源教程

JS中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。欢迎热爱技术的你一起加入交流与学习,JS中文网的使命是帮助开发者用代码改变世界

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Js中文网 · 前端进阶资源教程 」https://www.javascriptc.com

标题:手写 SQL 编译器 – 性能优化之缓存

链接:https://www.javascriptc.com/4825.html

« 这篇文章教会你把个人开发的jar包发布到maven中央仓库
微信小程序滑动切换导航 导航栏跟随滚动导航 顶部tab导航»
Flutter 中文教程资源

相关推荐

QR code