方程解析器的效率

Question

我花了一个月的全职时间写了一个本地 C++ 方程解析器。它可以工作，但速度很慢（比硬编码方程式慢30-100倍）。我能做什么来提高速度？

我阅读了所有我能找到的有关高效代码的信息，大致上：

• 解析器将字符串方程表达式转换为“操作”对象列表。
• 操作对象具有两个函数指针：“getSource”和“evaluate”。
• 要求解方程，我只需在操作列表上进行for循环，依次调用每个函数即可。

在求解方程时不存在单个if/switch - 所有条件都由解析器处理，当它最初分配函数指针时。

• 我尝试内联所有函数指针指向的函数 - 没有改进。
• 转换为函数对象（functors）是否有帮助？
• 如何使用派生出的完整“操作”类集合，每个类都有自己的虚拟“getSource”和“evaluate”函数，替换函数指针框架？（但这不只是将函数指针移到vtable中吗？）

我有很多代码。 不确定该精简哪些/发布哪些。请就其中某些方面提问，我将回答。

- Marupio

---

据我所知，内联只是编译器的一个提示，而不是命令。也许可以尝试使用优化（-O3或其他）进行编译... - phimuemue

实际上，如果您通过指针动态调用函数，则无法将其内联，因为编译器不知道您实际上正在调用哪个函数（如果有）。 - Blindy

也许你应该考虑在运行时输出字节码。在Windows上，你可以指定一个可执行的内存位置。你可以输出与你的方程对应的一系列汇编指令。这通常会让你接近未优化的硬编码方程。 - Mike Bailey

感谢所有快速的回复，我对stackoverflow及其社区印象非常深刻。只有几件事情需要补充：我不担心解析时间。它存储了操作列表，因此每进行一百万次左右的评估就只需要解析一次。 - Marupio

Answer 1

在您的文章中，您没有提到您是否对代码进行了分析。如果我是您，这将是我首先要做的事情。它会让您了解时间花费在哪里以及应该集中优化的地方。

- NPE

---

我还没有对代码进行性能分析。谢谢建议。我知道瓶颈在于评估，而不是解析。 - Marupio

Answer 2

根据你的描述很难确定缓慢的时间包括解析，还是仅包括解释时间。

如果你把解析器写成递归下降(LL1)，它应该受到I/O限制。换句话说，解析器读取字符和构建解析树的时间远远少于仅仅将文件读入缓冲区所需的时间。

解释是另一回事。解释和编译代码之间的速度差通常是10-100倍，除非基本操作本身就很耗时。尽管如此，你仍然可以进行优化。

你可以使用分析工具，但在这种简单情况下，你也可以在调试器中单步执行程序，以每个指令为单位。这样，你就可以“跟着计算机的脚步走”，很容易发现可以改进的地方。

每当我像你这样为用户提供语言，但希望该语言能够快速执行时，我会这样做：我将源语言翻译成我已经有编译器的语言，然后即时编译成.dll（或.exe）并运行。这很快，而且我不需要写解释器或担心速度问题。

- Mike Dunlavey

---

除了分析性能，我会尝试像你建议的那样进行单步调试。但是我确实按照你提到的策略设计它 - 成为计算机的一部分 ;) - Marupio

@Marupio：另外，睡一觉，然后尝试即时编译的方法。你可以打印出程序文件，执行编译器和链接器以生成.dll文件，然后加载.dll并定位要调用的入口点。这一切大约需要一秒钟的时间。然后你就可以以最快的速度运行代码了。我已经做过这个操作太多次了，非常顺畅。 - Mike Dunlavey

我喜欢你的建议，现在我重新阅读并理解了它。我可以将代码输出到源文件，但不确定如何即时调用编译器。我会研究一下。这可能是下一个版本的事情。谢谢！ - Marupio

@Marupio：我刚刚将批处理文件写到了一个方便的目录中。然后就是一些关于创建进程并等待其完成的无聊内容。函数调用CreateProcess会给你一个句柄，而WaitForSingleObject则会等待该进程完成。然后加载dll使用的是LoadLibrary，获取调用点则是GetProcAddress。 - Mike Dunlavey

Answer 3

第一件事是：确定出问题的具体原因。是解析还是评估上存在瓶颈？valgrind在这方面提供了一些有用的工具。

如果是解析问题，boost::spirit可能会有所帮助。如果是评估问题，请记住虚函数的评估速度可能会很慢。我个人在使用递归boost::variant时取得了不错的经验。

- thiton

---

我不太关心解析时间。这是在前期完成的。我使用评估的频率比解析高一百万倍。 - Marupio

Answer 4

你知道吗，构建一个表达式递归下降解析器真的很容易，因为表达式的LL(1)文法只有几个规则。然后解析就变成了线性操作，其他所有事情都可以在表达式树上工作（在解析过程中）；你可以从较低节点收集数据并将其传递给更高的节点进行汇总。

这将完全避免函数/类指针在运行时确定调用路径，而是依靠经过验证的递归性（或者如果愿意，你也可以构建迭代的LL解析器）。

- Blindy

Answer 5

看起来你正在使用一个相当复杂的数据结构（据我理解，是带有指针等的语法树）。因此，通过指针解引用进行遍历在内存方面不是非常高效（大量随机访问），可能会显著减慢速度。正如Mike Dunlavey所建议的那样，你可以使用另一种语言或嵌入编译器（例如LLVM）在运行时编译整个表达式。据我所知，Microsoft .Net提供了这个功能（动态编译）Reflection.Emit和Linq.Expression trees。

- wendazhou

---

这正是我所担心的。实际上，为了处理函数指针，我的equationReader在我的operation对象中调用了一个“callFunctionPointer”函数，该函数又调用了equationReader中的函数。我本来要解决这个愚蠢的问题，但想到也许整个结构需要改变。至于运行时编译，这已经存在于项目中，但是，1.我已经太深入了-不想放弃解析器，2.我希望用户输入类似Excel的方程，而不是源代码。 - Marupio

@Marupio 嗯，我不知道你的源代码长什么样子，但是从基本的C++（指针、引用和函数，没有疯狂的模板元编程）移植到C#相当简单。然后，您可以使用解析器从用户输入生成抽象语法树（AST）。然后，从这个AST生成代码，并使用.Net JIT即时编译。 - wendazhou

Answer 6

这是我建议暂时不要进行性能分析的少有时刻之一。我立即猜测你使用的基本结构才是问题的真正源头。在你相当确定基本结构合理之前，对代码进行性能分析很少有价值，而且大多数情况下只是找出哪些部分可以改进基本结构。当你真正需要做的是抛弃大部分现有内容并从头开始时，它就不那么有用了。

我建议将输入转换为逆波兰表达式。要执行此操作，您唯一需要的数据结构是堆栈。基本上，当您到达一个操作数时，您将其推入堆栈。当您遇到运算符时，它会对堆栈顶部的项目进行操作。当您完成评估格式良好的表达式时，您应该在堆栈上恰好有一个项目，即表达式的值。

几乎唯一比这更有效的方法是像 Mike Dunlavey 建议的那样，只需生成源代码并通过“真正”的编译器运行。然而，这是一个相当“笨重”的解决方案。如果你确实需要最大速度，那么显然这是最好的解决方案--但如果你只想改进现在正在做的事情，将其转换为逆波兰式表示法并解释执行通常会为少量代码提供相当不错的速度提升。

- Jerry Coffin

---

我应该想到逆波兰式。不过，我认为我的效率损失来自于动态尝试找到正确的操作来执行——这也是逆波兰式的问题。如果逆波兰式说“3 4 +”，那么最有效的方法是如何执行addition()，其中有60个可能的函数/运算符？你提到了@Mike Dunlavey的回答，所以我重新阅读了它，并意识到我没有完全理解他的意思。听起来很沉重，但我想我可以尝试一下。 - Marupio

通常情况下，您希望将一系列连续的值分配给您使用的运算符，而不是使用可读性较强的符号。 switch语句通常至少与替代方案一样快。数组/向量指向函数/函数对象的指针 看起来会更快，但在我的测试中，通常比switch慢。 - Jerry Coffin

就@Mike的想法而言，它似乎非常简单：不要解释表达式，只需将其放入C（或其他）框架中，将其编译为DLL / SO，然后动态加载结果到您的程序中。 - Jerry Coffin