快速布尔表达式求值器

我有一个应用程序，其中包含一个3运算符（& |！）布尔表达式求值程序，包含变量和常量。一般来说，表达式不会太长（最多可能是50个词，但通常会少很多）。可以有很多表达方式 - 我预计上限约为一百万。目前我有一个用一个非常简单的评估器编写的解析器，只需递归遍历解析树。一个限制是它必须从C++中调用。表达式之间没有共享。我想调查这个速度。快速布尔表达式求值器

我看到了两条研究途径。

添加共享并存储指示表达式节点是否已被评估的状态。
提取常见子表达式。

另外我希望代码生成方法比解析树或类似结构上的解释方法更快。生成一些C++代码可能相当简单，但考虑到函数的长度，我不知道像GCC这样的编译器是否能够优化CSE。

我已经看到有几个库可用于表达式评估，但在我的工作环境中添加第三方库并不简单，再加上它们都与我的需求相比看起来非常复杂。

最后，我最近一直在看Antlr4，所以这可能适合我。在过去，我从事C代码生成工作，但是我没有使用LLVM之类的东西来进行优化和代码生成。

任何建议走哪条路？

来源

2017-05-25 Paul Floyd

尽管我想建议ANTLR4，但我担心它不会满足您的性能需求。尽管有一些常见的技巧可以提高其性能，但在运行时简单地跟踪一个ANTLR4解释器就会发现，除非当前的表达式求值器效率很低，否则很可能比ANTLR4更快，ANTLR4是一种工业应用引擎，旨在支持语法比你的复杂得多。当LALR（1）DFA shift-reduce引擎不支持我的语法时，我使用ANTLR，并以ANTLR4的额外解析能力作为回报而获得性能。

来源

2017-05-25 21:00:51 TomServo

解析和lex的运行时间不应该是一个问题。这是一个独立于评估的阶段，可能会有几天的运行时间。所以即使几个小时的解析lex阶段也不成问题。评估速度是关键。 –

啊我明白了。然后误解你的问题。 ANTLR中的评估可能非常有效。有一种称为Mu的语法，我用它作为运行时表达式解释器的基础。 [链接]（https://github.com/bkiers/Mu/tree/master/src/main/antlr4/mu）。 – TomServo

据我所知，你的问题更多的是关于更快的表达评估比它更快的表达式解析。所以我的回答将集中在前者。毕竟，解析不应该成为瓶颈，因为您的表达语言看起来很简单，足以为其实施手动调整的解析器。

因此，为了加速您的评估，您可以考虑使用LLVM对公式进行JIT执行。也就是说，根据公式F，您可以（相对）轻松生成相应的LLVM IR并直接对其进行评估。这SMT solver就是这样做的。 IR代码生成是在单个C++类here中实现的。请注意，您提到的布尔表达式是该解算器支持的SMT语言的子集。此外，您可以轻松调整LLVM优化器需要的积极性。

但是，IR生成和优化有其开销。因此，如果给定的公式不足以分摊初始费用，那么我会建议直接解释。你可以在这种情况下寻找机会找到结构相似性和常见的子表达。

来源

2017-05-26 10:59:17 Codoka

快速布尔表达式求值器

回答

相关问题