快速多态数学解析器

• 下载示例 - 21.87 KB

引言

本文提出了一个数学解析器的实现方案，该解析器使用多态方法来快速求值给定的表达式。尽管本文讨论了解析输入文本，但重点在于快速计算给定数学公式的方法。通过生成基本汇编指令级别的操作码，可以实现非常好的性能。所描述的库会解释数学公式，并在运行时发出机器码（使用标准的 8087 指令），以计算给定的表达式。这种方法结合了词法分析算法和操作码操作技术，这些技术广泛应用于编译器和虚拟机（如 .NET 或 Java 平台）。

进一步的测试表明，所提出的方法非常高效，其速度几乎与程序编译期间生成的数学代码一样快！它还比其他流行的数学解析器快 30 倍。

假设读者熟悉 C/C++ 编程和 x86 汇编语言的基础知识。

背景

编译器如何生成代码

让我们看看程序在系统内部是如何执行的，编译器是如何生成代码的，以及它们如何在计算机内存中操作。系统中的每个进程的执行通常需要四种类型的内存区域：

• 代码区 - 内存的这一部分包含机器码——CPU 执行的一系列指令。
• 数据段 - 此段包含程序中定义的静态数据和常量。
• 栈 - 栈负责存储程序执行数据和局部变量。
• 堆 - 可以动态分配的内存段（内存的这一部分由 malloc 或 new 运算符使用）。

程序使用数据段中的数据执行代码区的一系列指令。当程序以所谓的 *cdecl* 方式调用函数时，它会将所有定义的函数参数、返回点在代码区的指针压入栈，然后执行跳转到负责执行给定函数的代码。栈也是存储局部变量的地方——当需要时，会在栈顶保留适当大小的内存。

让我们分析一下编译器是如何为计算数学表达式 (x+1)*(x+2) 的简单函数生成代码的。

float testFun( float x )
{
    return ( x + 1.0f ) * ( x + 2.0f );
}

编译器为给定函数生成以下汇编指令：

;   float testFun( float x )
;   {   
PUSH        ebp  
MOV         ebp,esp 
;       return ( x + 1.0f ) * ( x + 2.0f );
FLD         dword ptr [ebp+8] 
FADD        qword ptr [__real@3ff0000000000000 (1D0D20h)] 
FLD         dword ptr [ebp+8] 
FADD        qword ptr [__real@4000000000000000 (1D0D18h)] 
FMULP       st(1),st 
;   }
POP         ebp  
RET

当调用函数时，调用者将参数列表和返回码指针压入栈顶。在本例中，函数只有一个参数（类型为 float），因此在函数执行时，栈顶（按顺序）是：

1. 4 字节浮点变量
2. 4 字节返回地址

在函数开始时，ebp 寄存器被压入栈（指令 PUSH ebp），然后，栈指针（esp 寄存器）被复制到 ebp（MOV ebp,esp）。在此操作后，ebp 指向栈上存储旧 ebp 值的位置，ebp+4 指向返回地址，ebp+8 指向函数的参数（类型为 float 的变量 x）。

下一部分代码使用数学协处理器的内部栈执行严格的数学计算（8087 指令）。该栈包含八个寄存器，符号为 ST(0), ST(1), ..., ST(6)。栈顶是 ST(0)。编译器解释数学公式 (x+1.0f)*(x+2.0f) 并生成依次执行计算的代码（使用上述栈）：

1. 将变量 x 加载到栈顶 - ST(0)（指令 FLD）
2. 将常量加到 ST(0) 并将结果存储在 ST(0) 中
3. 将变量 x 加载到栈顶 - ST(0) 变为 ST(1)，x 被加载到 ST(0)
4. 将常量加到 ST(0) 并将结果存储在 ST(0) 中
5. 将 ST(0) 与 ST(1) 相乘，弹出栈，并将结果存储在 ST(0) 中

经过这一系列操作后，ST(0)（浮点栈的顶部）包含给定数学公式的结果。随后，程序恢复 ebp 寄存器的原始值（POP ebp）并返回到调用者（RET）。输出结果通过数学栈的顶部——寄存器 ST(0)——传递给调用者。

创建快速数学解析器的基本思想是创建将生成另一个代码以计算给定数学公式的代码。生成的操作码应具有上述函数的结构。当程序需要使用数学解析器时，首先应执行数学公式的分析并生成操作码。此后，每次需要计算时，程序应执行生成的代码，得到所需的结果。这种方法的主要优点是计算过程非常快速且高效——它模拟了执行在程序编译期间生成的代码的数学计算。

词法分析

编写数学解析器的基本问题是词法分析——它提供了给定表达式的结构，并说明了公式的解释方式。简单的数学表达式（带有运算符 +、-、*、/ 和括号）可以通过一组所谓的 *产生式* 来描述。

EXPR -> TERM + TERM
EXPR -> TERM - TERM
EXPR -> TERM
TERM -> FACT * FACT
TERM -> FACT / FACT
TERM -> FACT
FACT -> number
FACT -> x
FACT -> GROUP
GROUP -> ( EXPR )

这些操作描述了给定表达式的构建方式——一组输入字符（*非终结符*）如何被分解成更小的部分（*终结符*——如数字、数学运算符或符号）。

产生式 EXPR -> TERM + TERM 意味着非终结符 EXPR 可以分解为一系列非终结符 TERM、字符 '+' 和另一个非终结符 TERM。例如，非终结符 FACT 可以分解为数字、符号 x 或另一个非终结符 GROUP。

给定数学表达式的这些产生式定义了一个解析树（如下所示），它代表了输入字符串的语法结构。让我们看一下示例公式 (x+1)*(x+2)。此表达式可以从非终结符 EXPR 通过以下一系列转换推导出来：

EXPR -> TERM ->
     -> FACT ->
     -> FACT * FACT ->
     -> GROUP * GROUP ->
     -> ( EXPR ) * ( EXPR ) ->
     -> ( TERM + TERM ) * ( TERM + TERM ) ->
     -> ( FACT + FACT ) * ( FACT + FACT ) ->
     -> ( x + 1 ) * ( x + 2 )

在这些转换中的每一次都使用了（前面定义的）产生式。了解给定产生式在推导过程中如何使用，对于生成数学公式计算的机器指令非常有用。

实现

使用 Spirit 作为语法分析器

词法分析算法不是本文的重点——本文仅描述了解析数学公式所需的基本知识。语法分析可以由许多（免费提供的）库执行。在本文中，使用了 Boost 包中的 *Spirit* 库。

Spirit 是一个非常有用且易于使用的 C++ 工具，它利用了现代元编程方法。下面的代码定义了一个用于解释简单数学表达式的语法。

class MathGrammar : public grammar<MathGrammar>
{
public:
    template <typename ScannerT>
    struct definition
    {
        definition( MathGrammar const& self )
        {
            expr  = term >> *( ( '+' >> term )[ self._doAdd ] | 
                               ( '-' >> term )[ self._doSub ] )
                    ;
            term  = fact >> *( ( '*' >> fact )[ self._doMul ] | 
                               ( '/' >> fact )[ self._doDiv ] )
                    ;
            fact  = real_p[ self._doConst ] |
                    ch_p('x')[ self._doArg ] |
                    group
                    ;
            group = '(' >> expr >> ')'
                    ;
        }

        rule<ScannerT> expr, term, fact, group;
        rule<ScannerT> const& start() const { return expr; }
    };

protected:

private:
    AddFunctor _doAdd;
    SubFunctor _doSub;
    MulFunctor _doMul;
    DivFunctor _doDiv;
    ArgFunctor _doArg;
    ConstFunctor _doConst;
};

类 MathGrammar 派生自 grammar<MathGrammar> 泛型 Spirit 类。它使用四个非终结符（expr、term、fact 和 group）。在内部类 definition 的构造函数中，定义了语法的产生式。产生式是通过使用重载运算符开发的。

• >> 是一个合并非终结符和终结符的运算符。例如，a>>b 匹配表达式 *ab*。
• * 是 *Kleene 星号* 运算符——括号内符号的多次连接。例如，*(a>>b) 匹配表达式：*ab*、*abab*、*ababab* 等。
• | 是 OR 运算符。例如 ,(a|b) 匹配表达式 *a* 或 *b*。
• [] 这些括号包含函数对象，在使用了给定的产生式时会被调用。
• real_p 是代表常数——实数的终结符。
• ch_p('x') 是代表字符 *x* 的终结符。

所展示类的用法非常简单——在表达式解析过程中，当检测到给定的产生式时，就会调用定义的函数对象。分析始终是自底向上进行的——这意味着首先从解析树的底部调用产生式。

让我们使用下面的代码分析公式 (x+1)*(x+2)。

// instance of grammar class
MathGrammar calc;

// perform string parsing
if ( false == parse( "(x+1)*(x+2)", calc ).full )
{
    // parse error handling
}

在 parse 过程执行期间，定义的函数对象按顺序调用：

1. x 参数（函数对象 ArgFunctor _doArg）
2. 1 常量（函数对象 ConstFunctor _doConst）
3. + 运算符（函数对象 AddFunctor _doAdd）
4. x 参数（函数对象 ArgFunctor _doArg）
5. 2 常量（函数对象 ConstFunctor _doConst）
6. + 运算符（函数对象 AddFunctor _doAdd）
7. * 运算符（函数对象 MulFunctor _doMul）

这个操作顺序可以直接用于生成计算给定公式的适当机器码。获得的表示法

x 1 + x 2 + *

是所谓的 *逆波兰表示法*（RPN）或 *后缀表示法*——运算符跟在操作数之后，不使用括号。RPN 的解释器通常是基于栈的，也就是说，操作数被压入栈，当执行操作时，其操作数被弹出栈，然后将其结果压回栈。

机器码的发出

本文介绍的数学解析器的思想基于程序运行时动态生成机器码。程序使用语法分析器解释用户输入的文本——输入公式被转换为更合适的后缀表示法，可以使用处理器的数学栈来计算。在此分析之后，程序生成机器码来执行数学表达式的求值过程。

如何在 Windows 中动态生成机器码？首先，程序必须使用 VirtualAlloc 函数分配一个具有读/写访问权限的新内存段（下面的代码分配了 1024 字节内存）。

#include <windows.h>

// allocate memory segment with read/write access
BYTE *codeMem = (BYTE*)::VirtualAlloc( NULL, 1024, 
                         MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE );
if ( NULL == codeMem )
{
    // error handling
}

这段内存将包含新生成函数的主体。发出的代码应具有以下结构：

1. PUSH ebp - 将基址寄存器 ebp 压栈。
2. MOV ebp,esp - 将当前栈指针 esp 放入基址寄存器 ebp。
3. 对函数参数进行一系列数学计算（参数位于地址 ebp+8 的栈上）。
4. POP ebp - 恢复保存的基址寄存器 ebp 值。
5. RET - 函数返回指令。

下表描述了当语法分析器检测到数学运算时应发出的指令的操作码：

汇编代码	机器码操作码	操作 (Operation)
PUSH ebp	0x55	将基址指针压入栈。
MOV ebp, esp	0x8B, 0xEC	将栈指针移至基址指针。
FLD dword ptr [ebp+8]	0xD9, 0x45, 0x08	将浮点参数（来自 ebp+8）加载到 ST(0)。
FLD [mem32]	0xD9, 0x05, xx, xx, xx, xx	将常量从给定地址加载到 ST(0)（最后四个字节是常量在内存中的地址）。
FADDP st(1), st(0)	0xDE, 0xC1	将 ST(1) 加到 ST(0)，将结果存储在 ST(1) 中，然后弹出 ST(0)。
FSUBP st(1), st(0)	0xDE, 0xE9	将 ST(0) 减去 ST(1)，将结果存储在 ST(1) 中，然后弹出 ST(0)。
FMULP st(1), st(0)	0xDE, 0xE9	将 ST(1) 乘以 ST(0)，将结果存储在 ST(1) 中，然后弹出 ST(0)。
FDIVP st(1), st(0)	0xDE, 0xE9	将 ST(1) 除以 ST(0)，将结果存储在 ST(1) 中，然后弹出 ST(0)。
POP ebp	0x5D	从栈中恢复基址指针。
RET	0xC3	函数返回。

所描述的指令（以 Fxxx 开头）操作处理器内部的数学栈，并且最多使用两个寄存器——ST(0) 和 ST(1)。通过使用它们，程序可以轻松计算每个简单的数学表达式。当然，这个数学运算列表可以扩展到更复杂的函数（如对数、三角函数、根、幂等），但本文仅关注机器码生成思想——为简单起见，只描述了简单的数学运算符。

指令 FLDS 负责将数学值加载到栈中，从内存加载。此操作将用于加载参数 x 或给定数学公式中的常量。后一种情况需要一个（内存中的）特殊表来存储数字值。

在表达式解析过程中，程序会创建一个常量表，该表将在求值过程中使用。当语法分析器在公式中检测到一个常量（例如 (x+1) 中的 1）时——它会将其值写入表中，并发出 FLD [mem32] 操作码，该操作码带有指向内存中常量存储位置的指针。当生成的代码执行时，此指令将常量的值（从内存中读取）加载到栈顶。

在发出操作码后，程序应将分配的内存（由指针 codeMem 提供）的访问权限从*读/写*更改为*仅执行*。

// change access protection for memory segment to execute only
DWORD oldProtect;
BOOL res = ::VirtualProtect( codeMem, 1024, PAGE_EXECUTE, &oldProtect );
if ( FALSE == res )
{
    // error handling
}

在此操作后，任何试图写入此内存的进程都将崩溃。在 Windows 系统中，这种方法可以防止恶意代码注入。可以通过如下所示的简单代码执行发出的代码。

float ( *fun )( float );
fun = ( float ( __cdecl * )( float ) )codeMem;
fun( x );

当然，当不再需要生成的公式求值器时，应释放分配的内存。

if ( NULL != codeMem )
{
    // deallocate memory segment
    BOOL res = ::VirtualFree( codeMem , 0, MEM_RELEASE );
    if ( FALSE == res )
    {
        // error handling
    }
}

Using the Code

本文附带的项目包含了一个快速多态数学解析器的示例实现。该库基于以下类：

• MathFormula - 包含代码生成功能的类。它封装了带有要执行的操作码的内存段的处理。
• MathGrammar - 定义数学表达式语法的类。
• AddFunctor, SubFunctor, MulFunctor, DivFunctor, ArgFunctor, ConstFunctor - 用于处理数学语法产生式的函数对象集。

该库的使用非常简单：

#include "MathFormula.h"

// create MathFormula instance for given expression
MathFormula fun( "(x+1)*(x+2)" );

// perform evaluation of expression for given argument x
float result = fun( 2.0f );

MathFormula 对象的构造函数通过使用 MathGrammar 类执行输入字符串的语法分析。在表达式解释过程中，当满足给定的产生式规则时，会调用适当的函数对象。每个函数对象都会调用 MathFormula 对象中的发出方法——生成机器码。在初始分析后，可以使用重载的括号运算符来计算数学公式。

附带的项目可以在 *Visual Studio 2008* 中使用 *Boost* 库进行编译。有关构建过程的信息可以在 *ReadMe.txt* 文件中找到。

摘要

正如我们所见，使用动态生成的机器码实现数学表达式求值器非常简单。它是语法分析器（本文我们使用了 *Spirit* 库）、一些用于内存分配的 WinAPI 函数以及一些基本的汇编语言编程知识的结合。

所描述的数学解析器实现具有一个非常重要的优点——它的速度几乎与程序编译期间静态生成的代码一样快！下表显示了对表达式 (x+1)*(x+2)*(x+3)*(x+4)*(x+5)*(x+6)*(x+7)*(x+8)*(x+9)*(x+10)*(x+11)*(x+12)，不同类型解析器的平均数学公式求值时间。

数学解析器	执行时间 [ns]
C++	20.7 [ns]
MathParser	22.2 [ns]
muParser	700.69 [ns]
uCalc	762.36 [ns]
fParser	907.07 [ns]

所示的执行时间是 100,000,000 次执行的平均值，并且所有这些执行都在处理器 *AMD Turion X2 2.0 GHz* 上进行。

C++ 代表编译器在编译过程中生成的代码。我们的数学解析器（MathParser）的执行时间仅比 C++ 代码差 7%！相比之下，表中还包含了网上可用的数学解析器的执行时间——它们比 *MathParser* 慢至少 30-35 倍！

未来工作

本文仅描述了一个多态数学解析器的思想——当然，所提出的代码可以扩展到更高级的解决方案：

• 可以使用更复杂的数学函数；
• 程序可以使用一个以上的输入函数参数；
• 为了获得更好的性能，可以对生成的代码进行优化（例如：数学表达式简化）；
• 可以考虑使用 SIMD（单指令多数据）汇编指令，以便对整个值向量进行更快计算——使用 SSE 处理器的扩展。

从 JIT（*Just In Time*）编译器借用的动态生成代码技术，为非常快速地求值给定的数学表达式开辟了新的可能性。多态数学解析器可以应用于需要为用户提供的每个数学公式执行快速、大规模函数求值的系统。

历史

• 2009 年 11 月 30 日：文章创建
• 2009 年 12 月 03 日：小修改