muparserSSE

Compiling mathematical expressions at runtime.

Introduction


muParserSSE is an mathematical expression parser able to compile a given mathematical expression into machine code for Intel processors at runtime. It will take an expression as well as variable definitions as its input and return the pointer to a just in time compiled function made up of fast SSE instructions. You can extend it with custom callback functions and operators. muParserSSE is based on asmjit a just in time compiler written by Petr Kobalicek and the original muParser project.

The original muParser works by translating a mathematical expression into an intermediate bytecode representing its reverse polish notation. Successive evaluations then interpret this bytecode instead of reparsing the whole expression. muParser does a pretty good job performace wise. According to my benchmarks its already the fastest C++ math parser library currently available. However claiming to have the fastest parser is relative and if you prefer an independant benchmark you will see all math parser bringing more or less the same performance. Until recently this was good enough for me but then i found an article on CodeProject describing the use of just in time code generation to create a Fast Polymorphic Math Parser. Together with the article the author provides a very simplistic parser. Rather spartanic in terms of features but good enough to prove the point that a just in time compiled expression could significantly outperform muParser.

So here is the problem: Eventually someone would create a parser library based on just in time compiled code and with a similar functionalty as muParser and claim it's outperforming it by a factor of 10 or above. muParser doesn't have to be the fastest parser available, it has to be stable, maintainable, reliable and portable. However it should not be significantly outperformed by any other math parser either (except its a fork of muParser). So basically i had to look into using just in time code generation for muParser myself. The other point i should mention is that i was looking for a project in which i could use assembly language and using a just in time compiler requires assambly language by definition. So the idea of writing muParserSSE the lightwight ultrafast version of muParser was born. I really wish i could have told you that i have a cool application requiring such a fast parser but in fact i don't, i wrote it for fun and for the purpose of learning assembly language. If you actually use it in a project please let me know.

Features


Since this is a fork of muParser its interface and features are pretty similar. However i had to remove some of muParsers more "esotheric" features in order to get the work done. A complete implementation just would have taken to much time and muParser has some features that are rarely used anyway. On the other side i added some operators in order to expose as much of the SSE instructions to the user as possible. The following table compares muParserSSE with the other parsers of the muParser family. A detailed description of the differences is listed below.

Parser Data types Precision User defined operators User defined functions Locale
support
Licence Performance
(Expr. per second)*
complex scalar  string  vector Binary Postfix Infix Strings as
parameters
Arbitrary number
of parameters
muparser partially(1) ok partially(2) fail double ok ok ok ok ok ok MIT ~ 10.000.000
muparserSSE fail ok fail fail float ok ok ok fail max. 5 ok MIT ~ 20.000.000 -
100.000.000
muparserX ok ok ok ok double ok ok ok ok ok fail LGPL V3 ~ 1.600.000

Table 1: Feature comparison with other derivatives of muParser. (* Average performance calculated using this set of expressions; (1) muparser comes with an implementation for complex numbers but this is rather limited and more of a hack; (2) muparser can define strings but only as constants.)

The current release contains a DLL and Project files for 32 bit Windows only. Since both asmjit and muParser are running on Linux too compiling the library under Linux should be possible but has'nt been tested. The same applies to 64 bit systems as well as Apples OSX. The following features are supported by muParserSSE:

The following features are present in the original muParser but were removed in order to speed up the development:

Predefined Constants

By default the parser supports the following mathematical constants:

Predefined Functions

By default muParserSSE supports the following functions:

Binary operators:

Unary operators:

The following lists the unary operators defined by muParserSSE. Unary operators can be either postfix operators or infix operators. Postfix operators can be used to easily distinguish value quantities, whilst infix operators are used to implement the sign operator:

Implementation details


Back in the old days it was common to use assembly language for opimizing your code. One would take a time critical function and turn it into assembly code gaining somewhat around 30%-200% in speed. If you buy an assembly book they will still tell you this is the case nowadays. But the sad fact is that it has become very hard to write assembly code that is more efficient than what a modern compiler can generate when beeing run with all optimizations turned on and if you're not very familiar with the Intel processors optimization guide you will most likely not succeed in outperforming any modern C/C++ compiler with handcrafted assembly code. Today even the SSE instruction set is readily available from within C++ on any modern platform so why bother learning assembly anyway? On of the possible answers is that if you are writing an interpreter of any kind and if you would like to boost it's performance by using a just in time compiler you will most likely need assembly language. Compiled code is still an order of a magnitude faster than interpreted code even if its highly optimized code.

CPU's implementing SSE, the Streaming SIMD Extension provide a set of 8 registers useable for fast mathematical operations with floating point numbers. Their main purpose is to allow performing multiple operations at once by packing up to 4 numbers into the registers and operating simultaneousely with all 4 values. However the SSE instruction set also contains instructions for working with single floating point numbers. These instructions are prefixed with "ss" since they operate with single scalar values. This is the instruction subset predominantly used by muParserSSE (i.e. movss, divss, mulss, addss, subss, ...)

The reverse polish notation

In order to understand how muParserSSE works you first need to understand what a reverse polish notation is. Reverse Polish notation (or just RPN) is a mathematical notation wherein every operator follows all of its operands. Got that? Probably not so lets explain it with a bit more detail. The way a mathematical expression is normaly presented is called the infix notation. You probaly did'nt know that but believe me if you have ever attended a math lesson you have seen an expression in infix notation. Operators are written between the operands and you can use parentheses in order to define an evaluation order.

A simple Expression

In order to demonstrate how the evaluation works lets look at sample expressions. Out first sample is a simple expression without functions and with few binary operators:

a+((1+2)*b)-3

Expression 1: A simple mathematical expression. Operator items are colored blue, value items are colored in black.

Nothing special about that. Infix notation is a "human friendly" way to write an expression. Unfortunately to calculate it using a computer one needs a "computer friendly" way to write the expression and the reverse polish notation (or postfix notation) is just that. The RPN of our sample above looks like:

a 1 2 + b * + 3 -

Expression 1a: The reverse polish notation of expression 1.

Explaining how tor translate infix notation into postfix notation is beyond the scope of this article but if you are interested have a look at the Shunting-yard algorithm. For now just lets assume you already have the RPN of your expression. The expression is evaluated from left to right. Each value or variable is pushed to a stack. If an operator is found it is executed taking the two uppermost vaues from the stack as its arguments and pushing the result back to the stack. Lets assume our calculation stack is represented by an array called s and we parse the RPN from left to right. The following scheme then shows all operations needed to compute the final result of the expression given above:

a : s[0] = a
1 : s[1] = 1
2 : s[2] = 2
+ : s[1] = s[1] + s[2]
b : s[2] = b
* : s[1] = s[1] * s[2]
+ : s[0] = s[0] + s[1]
3 : s[1] = 3
- : s[0] = s[0] - s[1]

Image 1: Operations needed to calculate the reverse polish notation of equation 1.

The final result is located at s[0] ready for retrieval. A straightforward implementations would allocate an array for s and compute all the necessary steps pretty much like shown above. This is what muParser ist doing. So how can this be translated into assembly language for useage with asmjit?

It's gotta be fast so i intend to use the SSE instruction set. The SSE extension provides 8 additional registers on 32 bit machines. These are: xmm0, xmm1, .., xmm7. I could create an array much like s above and store the values there. Then i could load the values into the SSE registers from there, apply an operation (i.e. addition) and put the result back to my stack array. It would require only 2 SSE registers and a lot of data movement. All in all not very efficient! A better solution would be to use the SSE registers as much as possible. So why not use the registers directly as the calculation stack? There would be no memory allocations, no data movements. It would be very efficient. So lets look at pseudo assembly code usig SSE instructions for computing our sample expression:

a : movss xmm0, a
1 : movss xmm1, 1
2 : movss xmm2, 2
+ : addss xmm1, xmm2
b : movss xmm2, b
* : mulss xmm1, xmm2
+ : addss xmm0, xmm1
3 : movss xmm1, 3
- : subss xmm0, xmm1

Image 2: Pseudo assembly instructions for evaluating the reverse polish notation of equation 1.

This is pretty much a 1:1 translation of the pseudocode given above just with differing syntax. Keep in mind that this is only pseudo assembly code and some details were omitted in order to make it easier to understand. You can not feed this directly into a compiler (although it's close to what you could write using inline assembly)!
To explain it a bit: movss is an instruction moving a floating point value into an SSE register. The instructions addss, mulss and subss perform addition, multiplication and subtraction using the values in the given registers as their input and storing the result in the register used as the first argument. Once the calculation is done the final result would be located in the register xmm0 ready for retrieval. Lets have a look at how this would look like in memory. For the following animation we assume a=1 and b=2:

evaluation of expression 1

Animation 1: Schematic memory and register useage during evaluation of the expression a+((1+2)*b)-3. The entire calculation can be performed by exclusively by using SSE registers (xmm0..xmm2).

Creating this set of instructions on the fly from an RPN using asmjit is no big deal. Should it really be that easy? There are only 8 SSE registers given the approach outlined above will this be enough to deal with any expression? Lets look at another sample.

A slightly more complex Expression

The next expression is slightly more complex. This expression doesn't have functions either and still just uses basic binary operators only. It is using a lot of paranthesis though in order to enforce a certain evaluation order. First lets look at the expression

1+(2+(3+(4+(5+(6+(7+(8*a)))))))

Expression 2: A slightly more complex equation using lots of paranthesis.

and its RPN:

1 2 3 4 5 6 7 8 a * + + + + + +

Expression 2a: Reverse polish notation of expression 2.

Translating Expression 2a into pseudo assembly using the same approach as for expression 1 would yield the following code:

1 : movss xmm0, 1
2 : movss xmm1, 2
3 : movss xmm2, 3
4 : movss xmm3, 4
5 : movss xmm4, 5
6 : movss xmm5, 6
7 : movss xmm6, 7
8 : movss xmm7, 8
a : movss xmm8, a     ; we don't have a register xmm8!
* : mulss xmm7, xmm8  ; we don't have a register xmm8!
+ : addss xmm6, xmm7
+ : addss xmm5, xmm6
+ : addss xmm4, xmm5
+ : addss xmm3, xmm4
+ : addss xmm2, xmm3
+ : addss xmm1, xmm2
+ : addss xmm0, xmm1

Image 3: Pseudo assembly instructions for evaluating the reverse polish notation of expression 2. The register xmm8 does not exist. This expression can't be evaluated by exclusively using SSE registers!

Looks great except it does not work that way! There are only 8 SSE registers available but we would need 9 in order to evaluate this expression. So its obvious that given an arbitrarily complex expression there is no way to store all values in SSE registers. We have to find another solution!

How about this: The lowermost 6 registers (xmm0, xmm1, ..., xmm5) are used for directly storing values. They serve as the calculation stack. If a value needs to be stored at a higher position it's stored directly on the CPU stack. For instance if all 6 registers are occupied and another value needs to be pushed to the calculation stack 4 additional bytes are allocated on the CPU stack by decreasing ESP by 4 bytes and the value is stored at this location instead. The two remaining SSE registers (xmm6 and xmm7) are used for performing operations with values stored on the CPU stack.

evaluation of expression 2

Animation 2: Schematic memory and register useage during evaluation of the expression 1+(2+(3+(4+(5+(6+(7+(8*a))))))).

Animation 2 shows how even complex expressions can be evaluated using a combination of SSE register commands and stack allocations. Extending this mechanism to support function calls is relatively easy. This library supports only callbacks with the cdecl calling convention. Arguments are pushed to the stack from right to left and the calling function has to clean up the stack afterwards.

Function calls

A crucial part of every math expressions are functions. Implementing functions callbacks is not straightforward since essentially i'm dealing with assembly here but there is no standardized assembly language. 32 bit assembly is a different language than 64 bit assembly. (Not to speak of other processor families) The syntax is similar but register names differ and most importantly the AMD 64 bit extension is using a different calling convention than 32 bit. The calling convention determines how function paramters are submitted when calling functions. In order to support callback functions i have to make a decision which calling convention i'm going to support since muParserSSE has to implement the calling code in assembly and this code depends on the calling convention.

The parser interface


The following section gives an overview over the DLL interface exposed by muParserSSE. The interface of this library is very similar to the interface of the original muParser DLL.

Adding the library to your projects

In order to use the library you need to add the DLL named muParserSSE32.dll and the header file named "muParserSSE.h" to your project. Using the DLL is the only way to use this parser with MSVC6 or languages other than C++. The DLL has an interface that exports all of its functions as plain C style functions. The following files are required:

Include the header file in your project and add the lib file to the project resources. If you are using the Borland compiler, it may be necessary either to create a new lib from the DLL using implib or to convert the lib file. For more details on using DLLs, consult your compiler manual.

Parser initialization / deinitialization

Before using the parser its necessary to create a new instance handle. You can create as many different instance handles as you like. Internally each handle will reference a different parser object (a different expression). After using the parser you should release any parser handle created by mecInit() with a call to mecRelease(handle).

#include "muParserSSE.h"

// ...

mecParserHandle_t hParser;
hParser = mecCreate();  // Create a new handle

// ...

mecRelease(hParser);    //Release an existing parser handle

Setting the expression

Setting the expression when using the DLL requires a valid parser handle and a pointer to null terminated string containing the expression.

const char szExpr = "sin(3*pi)";
mecSetExpr(hParser, szLine);
See also: example.c.

Evaluating an expression

Unlike muParser, muParserSSE can't directly evaluate the expression. You have to compile the expression first. In order to compile the expression use the mecCompile function. It will return a pointer to the evaluation function. In order to evaluate the expression you must call this function.

mecEvalFun_t pFunEval = NULL;

// Compile the expression and get the pointer to the
// just in time compiled eval function
pFunEval = mecCompile(hParser);

// calculate the expression
float fVal = 0;
if (pFunEval!=NULL)
  fVal = pFunEval();
See also: example.c.
warning It is crucial to know that the just in time compiled functions remains valid only as long as you do not change the expression or any variables. If you release the parser handle it gets invalid too. Accessing an invalid evaluation function will unevitably lead to a crash in your software! Just don't mess with the parser handle after having compiled the function!

Defining parser variables

Custom variables can be defined either explicitly in the code by using the DefineVar function or implicitly by the parser. Implicit declaration will call a variable factory function provided by the user. The parser is never the owner of its variables. So you must take care of their destruction in case of dynamic allocations. The general idea is to bind every parser variable to a C++ variable. For this reason, you have to make sure the C++ variable stays valid as long as you hav a parser object depending on it. Only variables of type float can be used as parser variables.

Explicitly defining variables

Explicitly in this context means you have to do add the variables manually in your application code. So you must know in advance which variables you intend to use. If this is not the case, have a look at the section on Implicit creation of new variables. In order to define variables use the mecDefineVar function. The first parameter is a valid parser handle, the second the variable name, and the third a pointer to the associated C++ variable.

float fVal=0;
mecDefineVar(hParser, "a", &fVal);
See also: example.c.
warning Defining a variable will invalidate any existing compiled function so you need to recompile the function after defining new variables! It's important to understand that you should never use mecDefineVar for changing the value of an existing variable! Change the variable via the pointer submitted as the last parameter of mecDefineVar. The compiled function will access variables directly using their address!

Implicit creation of new variables

Implicit declaration of new variables is only possible by setting a factory function. Implicit creation means every time the parser finds an unknown token at a position where a variable could be located, it creates a new variable with that name automatically. The necessary factory function must be of type:

typedef mecFloat_t* (*mecFacFun_t)(const mecChar_t*, void*);

The following code is an example of a factory function. The example does not use dynamic allocation for the new variables although this would be possible too. But when using dynamic allocation, you must keep track of the variables allocated implicitly in order to free them later on.


// Factory function for creating new parser variables
// This could as well be a function performing database queries.

mecFloat_t* AddVariable(const mecChar_t* a_szName, void *pUserData)
{
  static mecFloat_t afValBuf[PARSER_MAXVARS];  // I don't want dynamic allocation here
  static int iVal = 0;                         // so i used this buffer

  printf("Generating new variable \"%s\" (slots left: %d)\n", a_szName, PARSER_MAXVARS-iVal);

  afValBuf[iVal] = 0;
  if (iVal>=PARSER_MAXVARS-1) 
  {
     printf("Variable buffer overflow.");
     return NULL;
  }

  return &afValBuf[iVal++];
}
See also: example.c.

In order to add a variable factory, use the mecSetVarFactory functions. Without a variable factory, each undefined variable will cause an undefined token error. Factory functions can be used to query the values of newly created variables directly from a database.

mecSetVarFactory(hParser, AddVariable);
See also: example.c.

Defining parser constants

Like variables constants have to be of type float. Originally muParser was using constants as a way to access their values faster in it's intermediate bytecode. In muParserSSE there is no performance gain from using constants but the function remains for practical purposes. The names of user defined constants may contain only the following characters: 0-9, a-z, A-Z, _, and they may not start with a number. Violating this rule will raise a parser error.

// Define value constants _pi
mecDefineConst(hParser, "_pi", (float)PARSER_CONST_PI);  
See also: example.c.

Defining parser functions

The parser allows using custom callback functions with up to 5 parameters. In order to define a parser callback function, you need to specify its name, a pointer to your static callback function, and an optional flag indicating if the function is volatile. Volatile functions are functions that should not be optimized since they may return different values even when fed with the same input (such as the rnd function). The static callback functions must be either one of the following types:

// function types for calculation
typedef mecFloat_t (*mecFun0_t)(); 
typedef mecFloat_t (*mecFun1_t)(mecFloat_t); 
typedef mecFloat_t (*mecFun2_t)(mecFloat_t, mecFloat_t); 
typedef mecFloat_t (*mecFun3_t)(mecFloat_t, mecFloat_t, mecFloat_t); 
typedef mecFloat_t (*mecFun4_t)(mecFloat_t, mecFloat_t, mecFloat_t, mecFloat_t); 
typedef mecFloat_t (*mecFun5_t)(mecFloat_t, mecFloat_t, mecFloat_t, mecFloat_t, mecFloat_t); 

The callback functions must be bound to the parser by using either one of the following functions:

// Add an function with a fixed number of arguments
mecDefineFun1(hParser, "fun1", pCallback1, false);             
mecDefineFun2(hParser, "fun2", pCallback2, false);             
mecDefineFun3(hParser, "fun3", pCallback3, false);             
mecDefineFun4(hParser, "fun4", pCallback4, false);             
mecDefineFun5(hParser, "fun5", pCallback5, false);             
See also: example.c.

Defining parser operators

The parser is extensible with different kinds of operators: prefix operators, infix operators and binary operators.

Unary operators

Both postfix and infix operators take callback functions of type mecFun1_t like the following:

float MyCallback(float fVal) 
{
  return fVal/1000.0; 
}

For defining postfix operators and infix operators, you need a valid parser instance handle, an identifier string, and an optional third parameter marking the operator as volatile (non optimizable). In order to bind your callbacks to the parser use the mecDefineInfixOprt and mecDefinePostfixOprt functions:

// Define an infix operator
mecDefineInfixOprt(hParser, "!", MyCallback);

// Define a postfix operators
mecDefinePostfixOprt(hParser, "M", MyCallback);
See also:example.c.

Binary operators

This parser has 13 built-in binary operators. Sometimes it might be necessary to have additional custom binary operators. Examples are shl or shr, the "shift left" and "shift right" operators for integer numbers. In order to add user defined operators, you need to assign a name, a callback function of type mecFun2_t, a priority for each new binary operator. You are not allowed to overload! Let's consider the following callback function which should be assigned to a binary operator:

float MyAddFun(float v1, float v2) 
{
  return v1+v2; 
}

For the definition of binary operators, you need at least six parameters:

  1. A valid parser handle
  2. A string used as the operator identifier
  3. A pointer to a callback function
  4. An integer value determining the operator priority
  5. The operator associativity which can be either one of the following constants:
    • mecOPRT_ASCT_LEFT
    • mecOPRT_ASCT_RIGHT
  6. An integer flag; If this flag is 1 the operator is assumed to be volatile.

Having defined a proper operator callback function, you can add the binary operator with the following code:

mecDefineOprt(hParser, "add", MyAddFun, 0, mecOPRT_ASCT_LEFT, 0);
See also:example.c.

The Priority value must be greater or equal than zero (lowest possible priority). It controls the operator precedence in the expression. For instance, if you want to calculate the expression 1+2*3^4 in a mathematically correct sense, you have to make sure that addition has a lower priority than multiplication which in turn has a lower priority than the power operator. When adding custom binary operators the most likely cases are that you assign an operator with either a very low priority of 0 (like and, or, xor) or a high priority that is larger than 6 (the priority of the power operator ^). By assigning priority values already used by built-in operators, you might introduce unwanted side effects. To avoid this and make the order of calculation clear, you must use brackets in these cases. Otherwise, the order will be determined by the expression parsing direction which is from left to right.

Example A: Priority of shl equals priority of an addition; the order of the execution is from left to right.

1 + 2 shl 1 => (1 + 2) shl 1
2 shl 1 + 1 => (s shl 1) + 1

Example B: Priority of shl is higher than the that of addition; shl is executed first.

1 + 2 shl 1 => 1 + (2 shl 1)
2 shl 1 + 1 => (2 shl 1) + 1

Querying parser variables

Keeping track of all variables can be a difficult task. For simplification, the parser allows the user to query the variables defined in the parser. There are two different sets of variables that can be accessed:

Since the usage of the necessary commands is similar, the following example shows querying the parser variables only:

void ListExprVar(mecParserHandle_t a_hParser)
{
  mecInt_t iNumVar = mecGetVarNum(a_hParser),
           i = 0;

  if (iNumVar==0)
  {
    printf("Expression dos not contain variables\n");
    return;
  }

  printf("\nExpression variables:\n");
  printf("---------------------\n");
  printf("Expression: %s\n", mecGetExpr(a_hParser) );
  printf("Number: %d\n", iNumVar);
  
  for (i=0; i<iNumVar; ++i)
  {
    const mecChar_t* szName = 0;
    mecFloat_t* pVar = 0;

    mecGetVar(a_hParser, i, &szName, &pVar);
    printf("Name: %s   Address: [0x%x]\n", szName, (long long)pVar);
  }
}
See also: example.c.

For querying the variables used in the expression, exchange mecGetVarNum(...) with mecGetExprVarNum(...) and mecGetVar(...) with mecGetExprVar(...). Due to the use of a temporary internal static buffer for storing the variable name in the DLL version, this DLL-function is not thread safe.

Querying parser constants

Querying parser constants is similar to querying variables and expression variables. Due to the use of a temporary internal static buffer for storing the variable name in the DLL version, this DLL-function is not thread safe. The following sample shows how to query parser constants:

void ListConst(mecParserHandle_t a_hParser)
{
  mecInt_t iNumVar = mecGetConstNum(a_hParser),
          i = 0;

  if (iNumVar==0)
  {
    printf("No constants defined\n");
    return;
  }

  printf("\nParser constants:\n");
  printf("---------------------\n");
  printf("Number: %d", iNumVar);

  for (i=0; i<iNumVar; ++i)
  {
    const mecChar_t* szName = 0;
    mecFloat_t fVal = 0;

    mecGetConst(a_hParser, i, &szName, &fVal);
    printf("  %s = %f\n", szName, fVal);
  }
}
See also: example.c.

Removing variables or constants

Removing variables and constants can be done all at once using mecClearVar and mecClearConst. Additionally, variables can be removed by name using mecRemoveVar. Since the parser never owns the variables, you must take care of their release yourself if they were dynamically allocated. If you need to browse all the variables for that purpose, have a look at the chapter explaining how to query parser variables.

// Remove all constants
mecClearConst(hParser);

// remove all variables
mecClearVar(hParser);

// remove a single variable by name
mecRemoveVar(hParser, "a");

Error handling

In order to detect errors you can set an error handler as a callback function. The program will then automaticlly jump into the error handler in case of any problems. Once an error is detected you can use the following functions in order to get detailed information:

The following table lists the parser error codes. The first column contains the constant used for the error, the second column lists the numeric value assigned to this constant and the third column contains the error description.

See also: example.c.
Constant Value Description
mecERR_UNEXPECTED_OPERATOR 0 Unexpected binary operator found
mecERR_UNASSIGNABLE_TOKEN 1 Token can't be identified
mecERR_UNEXPECTED_EOF 2 Unexpected end of formula (example: "2+sin(")
mecERR_UNEXPECTED_COMMA 3 An unexpected comma has been found (example: "1,23")
mecERR_UNEXPECTED_ARG 4 An unexpected argument has been found
mecERR_UNEXPECTED_VAL 5 An unexpected value token has been found
mecERR_UNEXPECTED_VAR 6 An unexpected variable token has been found
mecERR_UNEXPECTED_PARENS 7 Unexpected parenthesis, opening or closing
unused 8 - 10 unused
mecERR_MISSING_PARENS 11 Missing parens. (example: "3*sin(3")
mecERR_UNEXPECTED_FUN 12 Unexpected function found (example: "sin(8)cos(9)")
unused 13 unused
mecERR_TOO_MANY_PARAMS 14 Too many function parameters
mecERR_TOO_FEW_PARAMS 15 Too few function parameters (example: "ite(1<2,2)")
unused 16 - 17 unused
mecERR_INVALID_NAME 18 Invalid function, variable or constant name.
mecERR_BUILTIN_OVERLOAD 19 Trying to overload built-in operator
mecERR_INVALID_FUN_PTR 20 Invalid callback function pointer
mecERR_INVALID_VAR_PTR 21 Invalid variable pointer
mecERR_NAME_CONFLICT 22 Name conflict
mecERR_OPT_PRI 23 Invalid operator priority
mecERR_DOMAIN_ERROR 24 Catch division by zero, sqrt(-1), log(0) (currently unused)
mecERR_DIV_BY_ZERO 25 Division by zero (currently unused)
mecERR_GENERIC 26 Generic error
mecERR_INTERNAL_ERROR 27 Internal error of any kind.

Since dynamic libraries with functions exported in C-style can't throw exceptions, the DLL version provides the user with a callback mechanism to raise errors. Simply add a callback function that does the handling of errors. Additionally, you can query the error flag with mupError(). By calling this function, you will automatically reset the error flag!

// Callback function for errors
void OnError(mecParserHandle_t hParser)
{
  printf("\nError:\n");
  printf("------\n");
  printf("Message:  \"%s\"\n", mecGetErrorMsg(hParser));
  printf("Token:    \"%s\"\n", mecGetErrorToken(hParser));
  printf("Position: %d\n", mecGetErrorPos(hParser));
  printf("Errc:     %d\n", mecGetErrorCode(hParser));
}

// ...


// Set a callback for error handling
mecSetErrorHandler(OnError);


// If the next function raises an error the
// error handler is automatically called.
mecCompile(hParser);

// Before continuing you should test the error flag.
if (!mecError(hParser))
  printf("%f\n", fVal);
See also: example.c.

Example code

The following snippet shows a the minimal code necessary to set up muParserSSE. The application defines a parser variable named "x" and then calculates the expression "1+sin(x)".

#include "muParserSSE.h"

void OnError(mecParserHandle_t hParser)
{
  printf("\nError:\n");
  printf("------\n");
  printf("Message:  \"%s\"\n", mecGetErrorMsg(hParser));
  printf("Token:    \"%s\"\n", mecGetErrorToken(hParser));
  printf("Position: %d\n", mecGetErrorPos(hParser));
  printf("Errc:     %d\n", mecGetErrorCode(hParser));
}

int main(int argc, char* argv[])
{
  mecParserHandle_t hParser = mecCreate();
  mecEvalFun_t pFunEval = NULL;

  mecSetErrorHandler(hParser, OnError);
  
  // Define parser variables and bind them to C++ variables
  float x = 1;
  mecDefineVar(hParser, "x", &x);

  // Set the expression
  mecSetExpr(hParser, "1+sin(x)");

  // Compile the expression and get the pointer to the
  // just in time compiled eval function
  pFunEval = mecCompile(hParser);
  if (pFunEval==NULL)
    return -1;

  // Finally calculate the expression
  fVal = pFunEval();
  printf("Result: %2.2f\n", fVal);
  return 0;
}

Benchmarks


The whole point of creating muParserSSE was to improve evaluation performance. But making precise estimates over the gain in performance from muParserSSE is not easy. The performance can be an order of a magnitude better when the expression does'nt contain functions. It can be faster by factor 2 to 5 when functions are used and in some cases there is no benefit at all. There is still room for improvement in muParserSSE so i won't claim it's generating the fastest possible machine code. However its significantly faster than math parsers based on interpretation rather than compilation and it's not slower than MathPresso the only other free math parser using a just in time compiler. The following parsers were used in the benchmark:

Interpreter

Compiler

In order to conduct the benchmarks I set up a small application containing all of the math parsers with their source code. This was done in order to guarantee all use the same optimized compiler settings such as:

The results are shown in the following two diagrams, please note that the logarithmic scaling is used on the y-axis:

Diagram 1: Performance of different open source math parser for a set of random expressions without functions.

Diagram 2: Performance for a set of random expressions with functions.

Remaining issues


Unfortunately as most software this library is not perfect! There is still room for improvement. Here is a list of topics i would like to see fixed in the future:

License


This library is distributed as freeware. You are free to use it for both non-commercial and commercial use. It is released under MIT Licence. If you use the library, I consider it appropriate to give me credit at some place. This can either be the About dialog of your application or the documentation of your software.

muParserSSE - A math expression compiler
Copyright (c) 2010 Ingo Berg

Permission is hereby granted, free of charge, to any person obtaining a copy of 
this software and associated documentation files (the "Software"), to deal in the 
Software without restriction, including without limitation the rights to use, 
copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the 
Software, and to permit persons to whom the Software is furnished to do so, subject 
to the following conditions:

The above copyright notice and this permission notice shall be included in all 
copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, 
INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A 
PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT 
HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 
OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE 
SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

Credits


Special thanks to Petr Kobalicek for writing the asmjit just in time compiler and making it available as open source. Writing muParserSSE wouldn't have been possible without asmjit!

History


V1.0 Initial Release (20100630)


Creative Commons License
Autor: Ingo Berg; Dieser Text und die dazugehörigen Mediendateien stehen, sofern nicht anderweitig angegeben, unter der Creative Commons Namensnennung 3.0 Deutschland Lizenz.