Equation parser efficiency

Question

I sunk about a month of full time into a native C++ equation parser. It works, except it is slow (between 30-100 times slower than a hard-coded equation). What can I change to make it faster?

I read everything I could find on efficient code. In broad strokes:

• The parser converts a string equation expression into a list of "operation" objects.
• An operation object has two function pointers: a "getSource" and a "evaluate".
• To evaluate an equation, all I do is a for loop on the operation list, calling each function in turn.

There isn't a single if / switch encountered when evaluating an equation - all conditionals are handled by the parser when it originally assigned the function pointers.

• I tried inlining all the functions to which the function pointers point - no improvement.
• Would switching from function pointers to functors help?
• How about removing the function pointer framework, and instead creating a full set of derived "operation" classes, each with its own virtual "getSource" and "evaluate" functions? (But doesn't this just move the function pointers into the vtable?)

I have a lot of code. Not sure what to distill / post. Ask for some aspect of it, and ye shall receive.

Answer 1

In your post you don't mention that you have profiled the code. This is the first thing I would do if I were in your shoes. It'll give you a good idea of where the time is spent and where to focus your optimization efforts.

Answer 2

It's hard to tell from your description if the slowness includes parsing, or it is just the interpretation time.

The parser, if you write it as recursive-descent (LL1) should be I/O bound. In other words, the reading of characters by the parser, and construction of your parse tree, should take a lot less time than it takes to simply read the file into a buffer.

The interpretation is another matter. The speed differential between interpreted and compiled code is usually 10-100 times slower, unless the basic operations themselves are lengthy. That said, you can still optimize it.

You could profile, but in such a simple case, you could also just single-step the program, in the debugger, at the level of individual instructions. That way, you are "walking in the computer's shoes" and it will be obvious what can be improved.

Whenever I'm doing what you're doing, that is, providing a language to the user, but I want the language to have fast execution, what I do is this: I translate the source language into a language I have a compiler for, and then compile it on-the-fly into a .dll (or .exe) and run that. It's very quick, and I don't need to write an interpreter or worry about how fast it is.