Solving simple mathematical equation solving speed

[Lionel]

Hi all,

I have an equation that gets executing many thousands of times by an
algorithm. When I it is written in code the algorithm is quite fast.
However, I want the user to be able to define the equation themselves,
to solve it this way I use java expression parser (JEP).

For a test example, the algorithm using the hard coded version runs in
about 2 seconds, but using JEP, it takes in the order of 50 seconds! The
expression is only parsed once by JEP, but evaluated many times with
different values.

The expression I'm using looks like: A - (B / C) * D

Does anyone know if such a time difference is expected, and secondly, a
possible faster way of doing this?

Thanks

Lionel.

 

[Arne Vajhøj]

I have an equation that gets executing many thousands of times by an
algorithm. When I it is written in code the algorithm is quite fast.
However, I want the user to be able to define the equation themselves,
to solve it this way I use java expression parser (JEP).

For a test example, the algorithm using the hard coded version runs in
about 2 seconds, but using JEP, it takes in the order of 50 seconds! The
expression is only parsed once by JEP, but evaluated many times with
different values.

The expression I'm using looks like: A - (B / C) * D

Does anyone know if such a time difference is expected, and secondly, a
possible faster way of doing this?

Why not compile a Java class & method on the fly and load it ?

Arne

 

[Andrew Thompson]

I have an equation that gets executing many thousands of times by an
algorithm. When I it is written in code the algorithm is quite fast.
However, I want the user to be able to define the equation themselves,
to solve it this way I use java expression parser (JEP).

This one?

For a test example, the algorithm using the hard coded version runs in
about 2 seconds, but using JEP, it takes in the order of 50 seconds! The
expression is only parsed once by JEP, but evaluated many times with
different values.

The expression I'm using looks like: A - (B / C) * D

Does anyone know if such a time difference is expected, and secondly, a
possible faster way of doing this?

Use the JavaCompiler* to turn those mathematical
expressions into code within your own app.

*
<http://java.sun.com/javase/6/docs/api/javax/tools/JavaCompiler.html>

 

[Stefan Ram]

The expression I'm using looks like: A - (B / C) * D

The following example page shows how to evaluate expressions
with the compiler API.

http://www.purl.org/stefan_ram/pub/evaluating-expressions-with-java

(It uses disk-based compilation. There also is an option to
compile in memory, which is not shown on that page.)

 

[Roedy Green]

Does anyone know if such a time difference is expected, and secondly, a
possible faster way of doing this?

A clever parser would generate byte code. Then it potentially could
run just as fast as hand-coded if you let the JET JIT or Sun HotSpot
at it.

Most likely though it is generating a list of delegate calls, so you
have considerable overhead just stepping from operation to operation.

see http://mindprod.com/jgloss/onthefly.html

 

[Andrew Thompson]

On Jun 21, 1:00 pm, (Stefan Ram) wrote:
...

  (...There also is an option to
  compile in memory, which is not shown on that page.)

For 'in memory' compilation, see..
<http://forum.java.sun.com/thread.jspa?threadID=5305018>

(But in case anybody is wonderring. No, it
cannot be achieved within a sandbox, despite
getting the code directly from a text area.)

 

[John B. Matthews]

Use the JavaCompiler* to turn those mathematical
expressions into code within your own app.

*
<http://java.sun.com/javase/6/docs/api/javax/tools/JavaCompiler.html>

As Andrew & Stefan suggest, using the compiler will definitely be
faster, but version 1.6 is required. If JEP is too slow or you need
backward compatibility or your syntax is unique, writing your own
recursive descent parser isn't hard:

<http://home.woh.rr.com/jbmatthews/java/calc.html>

 

[Roedy Green]

Alternatively, you could use ANTLR (http://www.antlr.og) to generate a
parser. In fact, the book "The Definitive ANTLR Reference" by Terrence
Parr has an example of a mathematical expression parser and even extends
it to compile to Java bytecode using Jasmin
(http://jasmin.sourceforge.net/). This approach will work without
requiring the Compiler API from Java 6.

or any of the other parser generators, see
http://mindprod.com/jgloss/parser.html

 

[Lionel]

Hi all,

I have an equation that gets executing many thousands of times by an
algorithm. When I it is written in code the algorithm is quite fast.
However, I want the user to be able to define the equation themselves,
to solve it this way I use java expression parser (JEP).

For a test example, the algorithm using the hard coded version runs in
about 2 seconds, but using JEP, it takes in the order of 50 seconds! The
expression is only parsed once by JEP, but evaluated many times with
different values.

The expression I'm using looks like: A - (B / C) * D

Does anyone know if such a time difference is expected, and secondly, a
possible faster way of doing this?

Thanks for the numerous responses. I'm stuck on Java 1.5 for now, so it
appears that rules out a couple of suggestions. I was trying to avoid
the parser generator just because it would mean more code for me to
maintain, but perhaps I will have to bite the bullet and go for it. In
fact I would probably go the recursive descent parser if I take this
line anyway.

I guess that parsing it myself means I need a model of an equation. I'm
sure this has been done to death, so does anyone know of an example
model out there?

Thanks

Lionel.

 

[Roedy Green]

. I was trying to avoid
the parser generator just because it would mean more code for me to
maintain, but perhaps I will have to bite the bullet and go for it. In
fact I would probably go the recursive descent parser if I take this
line anyway.

Don't be frightened. It is duck simple. You will probably find a
grammar already suitable for your equations. It will be a lot more
work to write your own parser.

Hint, if you write your own, read the Aho and Ulman Dragon book then
use recursion. I wrote a parser for Algol-68 declarations back in my
student day in PL/I. It is one of my great life achievements. No
other student was able to do it. I basked in the approval of the
Professor Peck, one of the designers of Algol 68.

 

[none]

Don't be frightened. It is duck simple. You will probably find a
grammar already suitable for your equations. It will be a lot more
work to write your own parser.

I'm not frightened. I've written numerous grammars, and some recursive
descent parsers. But I have to introduce another set of libraries to do
the parser generation from the grammars, so the recursive descent parser
is more self-contained. It is also a simple problem, so won't be very
complex.

Hint, if you write your own, read the Aho and Ulman Dragon book

Ah yes. I know the dragon book. I've got a newer book which I will refer
to. You're right, it will be worth looking at first.

I just don't want to have to re-invent the wheel. There should be
something out there to do it already that is nice and fast, hence the
reason for my original post. I have googled but not found anything
appropriate yet.

I know it won't take too long to write the recursive descent parser, so
I might end up taking that line.

Thanks

Lionel.

 

[John B. Matthews]

Hi all,

I have an equation that gets executing many thousands of times by an
algorithm. When I it is written in code the algorithm is quite fast.
However, I want the user to be able to define the equation themselves,
to solve it this way I use java expression parser (JEP).

For a test example, the algorithm using the hard coded version runs in
about 2 seconds, but using JEP, it takes in the order of 50 seconds! The
expression is only parsed once by JEP, but evaluated many times with
different values.

The expression I'm using looks like: A - (B / C) * D

Does anyone know if such a time difference is expected, and secondly, a
possible faster way of doing this?

Thanks for the numerous responses. I'm stuck on Java 1.5 for now, so it
appears that rules out a couple of suggestions. I was trying to avoid
the parser generator just because it would mean more code for me to
maintain, but perhaps I will have to bite the bullet and go for it. In
fact I would probably go the recursive descent parser if I take this
line anyway.[/QUOTE]

Using 1.6 to invoke the compiler is more reliable, but it's not terribly
hard to do under 1.5 with Runtime.getRuntime().exec(). There's an
excellent example in Frank Felfe's delightful fractal project; see the
IteratorManager.compileTemplate() method:

<http://sourceforge.net/projects/benojt/>
<http://benojt.svn.sourceforge.net/viewvc/benojt/trunk/benojt/src/net/ben
ojt/IteratorManager.java?view=markup>

The alternative using a parser generator is indeed a maintenance
problem. I believe a custom recursive descent parser can be optimized
more readily, assuming the grammar is suitable.

 

[Patricia Shanahan]

I'm not frightened. I've written numerous grammars, and some recursive
descent parsers. But I have to introduce another set of libraries to do
the parser generation from the grammars, so the recursive descent parser
is more self-contained. It is also a simple problem, so won't be very
complex.

....

I suggest making it an expression-to-Java-source translator, and then
feeding the Java code to javac, if necessary by exec.

The fast results for static code may depend on the JVM's ability to
compile and optimize the bytecode. Its optimization is likely to have
been tested and tuned primarily on bytecode as generated by javac,
rather than arbitrary bytecode. The easiest way to produce bytecode that
is stylistically similer to javac generated bytecode is to use javac to
generate it.

Patricia

 

[none]

...

I suggest making it an expression-to-Java-source translator, and then
feeding the Java code to javac, if necessary by exec.

The fast results for static code may depend on the JVM's ability to
compile and optimize the bytecode. Its optimization is likely to have
been tested and tuned primarily on bytecode as generated by javac,
rather than arbitrary bytecode. The easiest way to produce bytecode that
is stylistically similer to javac generated bytecode is to use javac to
generate it.

There is another requirement. The equations would need to be loaded
every time the application starts. Does this still make the above
suggestion valid?

I think I will see what the speed is without the compiling step, then,
if it is really necessary I will consider it.

Thanks

Lionel.

 

[none]

Hi all,

I have an equation that gets executing many thousands of times by an
algorithm. When I it is written in code the algorithm is quite fast.
However, I want the user to be able to define the equation themselves,
to solve it this way I use java expression parser (JEP).

For a test example, the algorithm using the hard coded version runs in
about 2 seconds, but using JEP, it takes in the order of 50 seconds! The
expression is only parsed once by JEP, but evaluated many times with
different values.

The expression I'm using looks like: A - (B / C) * D

Does anyone know if such a time difference is expected, and secondly, a
possible faster way of doing this?

Thanks for the numerous responses. I'm stuck on Java 1.5 for now, so it
appears that rules out a couple of suggestions. I was trying to avoid
the parser generator just because it would mean more code for me to
maintain, but perhaps I will have to bite the bullet and go for it. In
fact I would probably go the recursive descent parser if I take this
line anyway.

Using 1.6 to invoke the compiler is more reliable, but it's not terribly
hard to do under 1.5 with Runtime.getRuntime().exec(). There's an
excellent example in Frank Felfe's delightful fractal project; see the
IteratorManager.compileTemplate() method:

<http://sourceforge.net/projects/benojt/>
<http://benojt.svn.sourceforge.net/viewvc/benojt/trunk/benojt/src/net/ben
ojt/IteratorManager.java?view=markup>
Thanks.

The alternative using a parser generator is indeed a maintenance
problem. I believe a custom recursive descent parser can be optimized
more readily, assuming the grammar is suitable.[/QUOTE]

My thoughts exactly.

Cheers

Lionel.