CODEWITHSUNDEEP
c++performancefunctionmathdynamic
csgosmorf
csgosmorf

Reputation: 81

Dynamically construct user-defined math function for efficient calling in C++?

An example is something like Desmos (but as a desktop application). The function is given by the user as text, so it cannot be written at compile-time. Furthermore, the function may be reused thousands of times before it changes. However, a true example would be something where the function could change more frequently than desmos, and its values could be used more as well.

I see four methods for writing this code:

  1. Parse the user-defined function with a grammar every single time the function is called. (Slow with many function calls)
  2. Construct the syntax tree of the math expression so that the nodes contain function pointers to the appropriate math operations, allowing the program to skip parsing the text every single time the function is called. This should be faster than #1 for many function calls, but it still involves function pointers and a tree, which adds indirection and isn't as fast as if the functions were pre-compiled (and optimized).
  3. Use something like The Tiny C Compiler as the backend for dynamic code generation with libtcc to quickly compile the user's function after translating it into C code, and then use it in the main program. Since this compiler can compile something like 10,000 very simple programs on my machine per second, there should be next to no delay with parsing new functions. Furthermore, this compiler generates machine code for the function, so there are no pointers or trees involved, and optimization is done by TinyCC. This method is more daunting for an intermediate programmer like me.
  4. Write my own tiny compiler (not of C, but tailored specifically to my problem) to generate machine code almost instantly. This is probably 20x more work than #3, and doesn't do much in the way of future improvements (adding a summation operation generator would require me to write more assembly code for that).

Is there any easier, yet equally or more efficient method than #3, while staying in the realm of C++? I'm not experienced enough with lambdas and templates and the standard library to tell for sure if there isn't some abstract way to write this code easily and efficiently.

Even a method that is faster than #2 but slower than #3, and requires no dynamic code generation would be an improvement.

This is more of an intellectual curiosity than a real-world problem, which is why I am concerned so much with performance, and is why I wouldn't use someone else's math parsing library. It's also why I wouldn't consider using javascript or python interpreter which can interpret this kind of thing on-the-fly.

Upvotes: 0

Views: 278

Answers (2)

Paul Janssens
Paul Janssens

Reputation: 722

Actually, the generating machine code track isn't that difficult, the trick is to design the parser so the parse result observes the order of computation.

Then you basically concatenate machine code strings with semantics like "push a literal on the stack", "perform a binary operation on the two topmost elements of the stack and push the result on the stack" and "pop the result from the stack"

Upvotes: 1

g23
g23

Reputation: 676

I think something along the lines of your option 2 would be good. Except maybe to be a little easier would be to have an Expr class with a float Expr::eval(std::unordered_map<string,float> vars) method. Then implement subclasses like Var with a name, Add with left and right, Sub, Mult, Div, etc all the functions you want. When evaluating you just pass in the map with like {{"x",3},{"y",4}} or whatever and each Expr object would pass that down to any subexpressions and then do it's operation.

I would think this would be reasonably fast. How complicated of expressions do you think your user's would be putting in? Most expressions probably won't require more than 10-20 function calls.

It can also get a lot faster

If you're trying to make something that graphs functions (or similar) you could speed this up considerably if you made your operations able to work with vectors of values rather than single scalar values.

Assuming you wanted to graph something like x^3 - 6x^2 + 11x - 6 with 10,000 points, if you had your Expr objects only working on single values at a time, yeah this would be like ~10-15 function calls * 10,000 points = a lot jumping around! However, if your Expr objects could take arrays of values, like calling eval with {{"x",[1,2,3...10000]}} then this would only be ~10-15 function calls, total, into optimized C++. This could easily scale up to a larger number of points and still be very fast.

Upvotes: 1

Related Questions