Speeding up calculating parsed equations

[nkomli]

My goal is to allow users to enter in an equation that will be
calculated. In order to do this I’ve attached a parser to the program.
Unfortunately the equation has to be calculated millions of times. For
example

while(count !=limit)
{
Xnext= x+1;

x=xnext;
}

The parser is called to recalculate the equation every cycle which I
believe is the reason is why the program is as slow as Christmas. I
was wondering if there was any way to store the equation once it is
parsed to allow it to run at least close to the speeds it would of the
equation was hardcoded.



Here is the relevant part of the code in this example assume args and
args2 are x+1 and y+1.




int calculate()
{


double i;
stx::AnyScalar x, y, xnext, ynext, val, val2;


x = 0;
y = 0;

// parse expression into a parse tree
stx:arseTree pt;
stx:arseTree pt2;

// evaluate the expression with a very simple symbol table
stx::BasicSymbolTable bst;


for (i = 1; i <= obj.icount; i++)//calculate equation (x+1) icount
times
{


//set the parser to recognize x and y as their new values every cycle
bst.setVariable("x", x);
bst.setVariable("y", y);

//call parser to evaluate functions contained within strings args and
args2
try
{
pt = stx:arseExpression(args);
val = pt.evaluate(bst);

pt2 = stx:arseExpression(args2);
val2 = pt2.evaluate(bst);
}


catch (stx::UnknownSymbolException &e)//exception handling
{
std::cout << "UnknownSymbolException: " << e.what() << "\n";
return 0;
}
catch (stx::ExpressionParserException &e)
{
std::cout << "ExpressionParserException: " << e.what() << "\n";
return 0;
}



x = val;
y = val2;






cout<< x << endl; //print x

}






return 0;
}

 

[Kai-Uwe Bux]

My goal is to allow users to enter in an equation that will be
calculated. In order to do this I?ve attached a parser to the program.
Unfortunately the equation has to be calculated millions of times. For
example

while(count !=limit)
{
Xnext= x+1;

x=xnext;
}

The parser is called to recalculate the equation every cycle which I
believe is the reason is why the program is as slow as Christmas. I
was wondering if there was any way to store the equation once it is
parsed to allow it to run at least close to the speeds it would of the
equation was hardcoded.

Have the parser build an expression tree. E.g. (not run by a compiler):

struct node_base {

node_base * first_child;
node_base * next_sibling;

virtual
double evaluate ( void ) const;

};

struct add_node : public node_base {

virtual
double evaluate ( void ) const {
double result = 0;
node_base * summand = first_child;
while ( summand != 0 ) {
result += summand->evaluate();
summand = summand->next_sibling;
}
return ( result );
}

};

struct variable_node : public node_base {

double & the_ref;

virtual
double evaluate ( void ) const {
return ( the_var );
}

};


....


While you parse the expression, you build a tree like that. Note that the
nodes representing variables x, y, z, ... do not store values but
references. Thus, when you call

root->evaluate();

the expression will be evaluated with the values currently stored for x, y,
and z in those variables.


[snip]


Best

Kai-Uwe Bux

 

[Pascal J. Bourguignon]

Have the parser build an expression tree. E.g. (not run by a compiler):

Yep, but that's the problem the OP has, that it is not run by a compiler!

Actually, nkomli, you too are longing for Common Lisp, where you would
just write:

(let ((expression (progn (format *query-io* "Enter expression: ") (read *query-io*))))
(dotimes (i 100000)
(funcall (compile nil `(lambda () ,expression)))))

;; modulo some reservation about the security of letting the user
;; run random expressions, you may want to actually check that the
;; expression read contains only allowed operations.

Note that what you get in expression is the actual parse tree! Well,
perhaps you want the user to give their expressions in another syntax
than lisp, in which case you will have to add your own parser, but
this is not the question).


So now, let's apply Greenspun's Tenth Law, and try to implement
COMPILE in C++.

Happily, there are libraries that allow you to generate native binary
code at run-time!

For example: Lightning, or LLVM.
http://www.gnu.org/software/lightning/manual/lightning.html
http://llvm.org/


An alternative would be to use gcc and dynamically loaded libraries.

- write the text of a function in a temp file, returning your
expression, generated in C:

#include <math.h>
extern double dynfun(double x){
return(sin(x));
}

- call the compiler and linker to generate a .so:

/* pseudo code, of course you shouldn't use system(3) */
system("gcc -o dynfun.o dynfun.c");
system("gcc -fPIC -shared -Wl,-soname,libdynfun.so -o libdynfyn.so dynfun.o")
void* lib=dlopen("dynfun.so",flags);
double(*fun)(double);
fun=dlsym(lib,"dynfun");
double x=1.0d0;
for(int i=0;i<100000;i++){
x=fun(x);
}


It would be quicker to generate the code with Lightning and execute it
directly in RAM, than going to the file system and having gcc compile
it. On the other hand, gcc may be able to generate more optimized
code. Or you could just use Common Lisp and have both, built-in quick
and optimized run-time code generation.
And Common Lisp may be faster than C on numerical applications:
http://www.lrde.epita.fr/~didier/research/verna.06.imecs.pdf

 

[James Kanze]

Have the parser build an expression tree. E.g. (not run by a
compiler):

struct node_base {
node_base * first_child;
node_base * next_sibling;

virtual
double evaluate ( void ) const;
};

struct add_node : public node_base {
virtual
double evaluate ( void ) const {
double result = 0;
node_base * summand = first_child;
while ( summand != 0 ) {
result += summand->evaluate();
summand = summand->next_sibling;
}
return ( result );
}
};

struct variable_node : public node_base {
double & the_ref;
virtual
double evaluate ( void ) const {
return ( the_var );
}
};

...

While you parse the expression, you build a tree like that.
Note that the nodes representing variables x, y, z, ... do not
store values but references. Thus, when you call

the expression will be evaluated with the values currently
stored for x, y, and z in those variables.

This will definitely represent an improvement over reparsing the
text each time. But I suspect converting the tree to some sort
of bytecode, or even pure threaded code, will be even faster.
(One of the most readable explinations I've seen of how to
generate and execute byte code is for the hoc calculator in
Kernighan and Pike's "The Unix Programming Environment". If the
original poster wants to go this route, I'd strongly recommend
his reading it. Note too that "byte code" doesn't have to be
8 bit bytes; dispite the name, you can use just about any type
as the basis.)