数据加工DSL编译优化：公共子表达式删除-阿里云开发者社区

数据加工DSL编译优化：公共子表达式删除

2021-09-14 431

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 本次分享主要介绍面向数据加工DSL的一项编译优化：公共子表达式删除（common subexpression elimination）。SLS数据加工服务是什么？公共子表达式删除的初衷？公共子表达式删除是怎么实现的？有哪些实际价值？SLS数据加工服务是什么？日志服务提供可托管、可扩展、高可用的数据加工服务。数据加工服务可用于数据的规整、富化、流转、脱敏和过滤。数据加工DSL提供了30多种场景方案、

本次分享主要介绍面向数据加工DSL的一项编译优化：公共子表达式删除（common subexpression elimination）。SLS数据加工服务是什么？公共子表达式删除的初衷？公共子表达式删除是怎么实现的？有哪些实际价值？

SLS数据加工服务是什么？

日志服务提供可托管、可扩展、高可用的数据加工服务。数据加工服务可用于数据的规整、富化、流转、脱敏和过滤。

数据加工DSL提供了30多种场景方案、200多个内置函数、400多项GROK模式，内置函数包含转换、分发、分裂、复制、富化五大类，并且内置函数之间没有前后强依赖关系，可以自由编排，由此客户只需以函数调用的方式编写DSL即可实现复杂业务需求。

数据加工概述：https://help.aliyun.com/document_detail/125384.html

数据加工DSL简介：https://help.aliyun.com/document_detail/125439.html

数据加工DSL函数总览：https://help.aliyun.com/document_detail/159702.html

数据加工架构设计：https://topic.atatech.org/articles/208924

公共子表达式删除的初衷？

数据加工服务客户多，各个客户的业务需求较为复杂，DSL灵活性强，由此导致数据加工作业数量较多，且数据加工作业内容差异较大。由于数据加工采用了按量收费，优化门槛较高，客户性能优化积极性不高。客户往往只关心正确性的问题，而不会关心性能，出现了问题再去解决，后知后觉，客户体验较差。如果采用研发人员手动优化的方式提升数据加工作业的执行效率，工作量巨大，成本极高。由此，采用编译技术将“优化意识”自动化是一种较优的DSL优化解决方案。

重复的子函数操作在数据加工作业原始DSL中大量出现，如上图所示，比如v(“content”)和其包装函数json_select(v(“content”), “Content”),经过优化后会把这些公共子表达式抽出为临时变量，依次消除部分冗余函数计算。优化之后的DSL如下图所示。在原始content字段较大的情况下，经过上述公共子表达式优化性能会提升至少1倍。

公共子表达式删除是怎么实现的？

公共子表达式是一种经典的冗余删除编译技术，有没有一个相对权威的描述？Steven S.Muchnick在《高级编译器设计与实现》（编译原理的经典著作：鲸书，最好的编译优化参考书？）中是这样描述公共子表达式的：程序中一个表达式的一次出现是公共子表达式，如果存在着该表达式的另一次出现，在执行顺序上它的计算总是先于这个表达式的计算，并且在这两个计算之间该表达式的操作数没有发生改变。公共子表达式删除是一种转换，它删除公共子表达式的重复计算，并用保存的值来替代它们。

数据加工DSL较通用程序语言具有一定的特殊性。由于面向数据加工的DSL的基本计算单元是函数，因此面向数据加工的“公共子表达式删除”的基本单元也是函数。数据加工的数据流是自上而下垂直方向的，不包含复杂的循环跳转函数，由此函数的上下文作用域推导也极为简洁。数据加工作业包含一个隐式的变量：全局事件，这个事件流向也是垂直的，从数据加工作业的第一条语句一直执行到最后一条语句。通常程序语言的公共子表达式删除需要重复遍历多次抽象语法树，而面向数据加工DSL的公共子表达式删除只需遍历一次抽象语法树，减少了循环遍历的次数，从而加快了编译优化速度，时间复杂度较小。

公共字表达式删除主要包含如下步骤：

词法语法分析

首先，采用词法语法解析工具将数据加工作业的DSL解析并改写为语义一致且具有父子关系的AST（抽象语法树，Abstract Syntax Tree）。

然后，将跳转函数e_if()、e_if_else()、e_switch()需改写为条件判断形式的AST节点。由于函数e_split()表示基于某个字段的值分裂出多个事件。如果e_split()函数独立使用，则后面的所有语句均在分裂的具体事件的基础上执行，因此将e_split()改写为循环嵌套形式的AST节点。

由于条件判断和循环嵌套的出现，随之引入了多层作用域变量的问题，也就是同名变量会出现相互覆盖的情况。

公共子表达式定位

为了简化抽象语法静态分析逻辑，假设子节点对“当前事件”的影响范围同时会扩展到父节点。例如：条件判断语句具有两个分支，那么条件判断语句的影响范围为两个子分支的并集。

为了实现全局作用域感知功能，需要将字段名称及当前字段版本存储到字典“公共子表达式字典common_subexpression_dict”，此字典的键为字符串类型，值为列表类型。

为了定位字表达语义是否相同，需要生成表达式的唯一性标识符。采用深度优先的方式依次遍历AST的各个节点。当节点为事件处理类函数，则将影响（添加、更新和删除）的字段版本号version_id加1。在遍历节点的同时，采用附加输入字段版本号的序列化字符串作为当前作用域下表达式的“标识符expression_id”，此标识符能够同时区分表达式和作用域，当两者任何一个发生改变时，标识符expression_id都会发生改变，并将标识符expression_id和节点作为键值对存储到字典“公共子表达式字典common_subexpression_dict”。

注意：用于跳转作用域（if\switch）通常只有一个分支会被执行，因此，上文描述的作用域包含“字段作用域”和“跳转作用域”两部分。

公共变量替换

遍历“编译上下文compiler_context_map”，如果值中包含多个元素，则表示这几个元素可以采用“公共子表达式变量common_sub_expression_var”统一代替。为了保证变量名称的的唯一性common_sub_expression_var变量名称需添加后缀“{全局递增编号}_{行号}_{列号}”。

“公共子表达式变量common_sub_expression_var”声明的位置为同组公共子表达式的父抽象语法树节点，以此保证“公共子表达式变量common_sub_expression_var”的作用域的正确性。