math expression evaluation - very fast - with objective-c

Question

i want to evaluate a math expression like y = 2(x * x) + 2.

But i need it in a loop, where the x changes maybe 100000 times.

I have written code to translate the expression in a parse tree.

Then i have a method to evaluate the parse tree.

- (double) evaluate:(TreeNode *)node variable:(double)x
{
    if ([node _operand] != 0) 
    {
        return [node _operand];
    }

    else if ([node _variable] != NULL) 
    {
        return x;
    }

    else if ([node _operator] != NULL) 
    {
        if ([[node _operator] isEqualToString: @"+"]) 
        {
            return ([self evaluate:[node left] variable:x] + [self evaluate:[node right] variable:x]);
        }
        else if ([[node _operator] isEqualToString: @"-"]) 
        {
            return ([self evaluate:[node left] variable:x] - [self evaluate:[node right] variable:x]);
        }
        else if ([[node _operator] isEqualToString: @"*"]) 
        {
            return ([self evaluate:[node left] variable:x] * [self evaluate:[node right] variable:x]);
        }
        else if ([[node _operator] isEqualToString: @"/"]) 
        {
            return ([self evaluate:[node left] variable:x] / [self evaluate:[node right] variable:x]);
        }
    }

    return 0;
}

Someone said: if i gotta go for speed, i could translate the expression into C code, compile and link it into a dll on-the-fly and load it (takes about a second). That, plus memoized versions of the math functions, could give me the best performance.

How can i achive that ? How can i compile the math expression into C code and compile and link it into a dll or so. And then load it on the fly to speed the loop up ?

Thanks a lot !

Chris

Answer 1

My advice: Do not write this code yourself. Having written code that does this, there are some things to be aware of:

Parsing mathematical expressions is not a trivial problem, if you're going to do it correctly and fully. You have to consider things like the associativity of each operator: what happens if you find more than one of the same operator in an expression? Which one do you evaluate first? How do you deal with operators whose precedence changes depending on their context? (for example, the negation operator) These are hard questions, and very few implementations get it right.

As was mentioned in a comment on the question, there are some things that can do this for you already:

1. NSPredicate. Pros: built-in, reasonably fast, decent precision. Cons: the exponent is parsed with incorrect associativity, not extensible, does not support implicit multiplication (i.e., 2(x*x)), does not parse the negation operator correctly.
2. GCMathParser. Pros: very fast, decent precision. Cons: not extensible, does not support implicit multiplication, does not parse the negation operator correctly.
3. DDMathParser. Pros: excellent precision, extensible, supports implicit multiplication. Cons: not quite as fast as the other two, due to the parsing engine and high precision math

Obviously, I recommend DDMathParser (I wrote it). In your case, you'd want to do something like this:

NSError *error = nil;
NSString *math = [DDExpression expressionFromString:@"2($x * $x) + 2" error:&error];

for (int x = 0; x < 100; ++x) {
  NSNumber *variable = [NSNumber numberWithInt:x];
  NSDictionary *sub = [NSDictionary dictionaryWithObject:variable forKey:@"x"];
  NSNumber *value = [math evaluateWithSubstitutions:sub evaluator:nil error:&error];
  NSLog(@"value: %@", value);
}

DDMathParser is available on GitHub: https://github.com/davedelong/DDMathParser . Please be mindful of its license (free for use with attribution).

However, if you're ok with sacrificing some precision (and a couple of cases of it being incorrect) in exchange for blazing fast speed, I'd recommend using GCMathParser.

Answer 2

If you were to performance analyze that code, you'd [very most likely almost 100% assuredly] find that string comparison is what is killing your performance.

An easy fix is to split parsing from evaluation. That is, parse the expression into an intermediate form (like what jills and Rudy allude to, but simpler) and then evaluate that intermediate form.

That is, you might create a "parse:" method that [recursively] walks your tree of nodes, parses each, and then sets a property to some # representing the operator.

typedef enum {
PlusOperator,
SinOperator,
..... etc ....
} OperatorID;

@property(nonatomic) OperatorID operatorID;

Then, your evaluate:variable:'s if/else would be replaced with a switch statement.

switch([node operatorID) {
case PlusOperator:
    ....
    break;
... etc ...

Hi, thanks a lot. But i already parsed the expression and have build a tree, which i evaluate with the method above. What i need is a faster evaluation in a loop.

Don't represent the parse tree as strings.

I.e. instead of _operator returning an NSString, make it return an int (or OperatorID, if using the above) then use a switch statement.

@property(nonatomic) OperatorID _operator;

Since you are already parsing the expression, this should be even easier / more straightforward to do.

Answer 3

i want to evaluate a math expression like y = 2(x * x) + 2. But i need it in a loop, where the x changes maybe 100000 times.

You should consider using the TinyExpr math expression evaluation library. It is written in C, and will do exactly what you want. If you would prefer to code it yourself, TinyExpr is only 500 lines of code, so it's probably the simplest complete example you'll find.

Here's how you would solve your problem with x constantly changing:

double x;
te_variable vars[] = {{"x", &x}};

te_expr *expr = te_compile("2*(x*x)+2", vars, 1, 0);

for (x = 0; x < 100000; ++x) {
    double y = te_eval(expr);
    printf("x=%f, y=%f\n", x, y);
}

Note that the expression is automatically reevaluated with the present value of x, even though the expression is only "compiled" once.

If you need to be even faster, you could always generate code at run-time and then invoke an actual compiler. However, the time it takes to run the compiler would likely dwarf the speed savings until you're well into billions of evaluations. The 100,000 evaluation number you gave in your question would likely be evaluated almost instantly by TinyExpr. It's pretty fast.

Answer 4

You could get an existing expression parser. Some of them can "compile" such expressions on the fly to some internal format that would make evaluating the expression faster, and then allow you to provide it with values for the variables. The "compilation" would be done before the loop and the substitution once every loop iteration.

I know such expression parsers/evaluators exist for Delphi, but I don't know any for C, sorry. I assume you can find them online, as C has a far larger worldwide code base than Delphi. Just google (or bing, etc.) for "expression parser" and then look if the ones you found can do such substitutions without having to reparse the expression.

Answer 5

You cannot generate and execute machine code on iOS, but you can still do better than walking a parse tree. From the parse tree, generate instructions for a fictitious stack machine (think Forth, x87 machine code, java bytecode, CLR bytecode). While generating, you can determine how much stack space (numbers) you need. Then interpret these instructions for each value of x. This is faster because the instructions are more compact and have better locality than the parse tree and because no C recursion is used.

EDIT: For example, the expression sqrt(x+1) is translated to four instructions: one to push the variable x onto the stack, one to push the constant 1, one to pop the two numbers and push the sum and one to replace the sum with its square root. Any parse tree can easily be translated to such a list of instructions using a recursive function. An instruction could be represented by a struct containing an enum for the type of the instruction and a number for push constant instructions. The "stack" is not the C stack but simply an array of numbers with an integer that indicates how many are currently in use (which starts off as 0 and will end at 1).

Answer 6

What's wrong with simply using OO design?

@implementation TreeNodeAdd

-(double)evaluateWithVariable:(double)x
{
  return [left evaluateWithVariable:x] + [right evaluateWithVariable:x];
}

@end

...

- (double) evaluate:(TreeNode *)node variable:(double)x
{
  return [node evaluateWithVariable:x];
}

The equivalent in C++ might be a little faster.