While answering this code review question, I came up with a way to convert an equation given at runtime to a std::function<double(double)> that would evaluate that equation at a given point. Assuming the equation was already split into tokens and converted to postfix notation, this is done by evaluating those tokens like you would do in a normal implementation of a RPN calculator by maintaining a stack of intermediate results, but instead of just storing the values, the stack stores lambda expressions that can calculate those values. At the end of the evaluation, the stack should thus contain a single lambda expression that implements the desired equation. Here is a simplified version of the parser than only supports a few operations:
#include <cmath>
#include <functional>
#include <iostream>
#include <numbers>
#include <stack>
#include <string>
#include <string_view>
std::function<double(double)> build_function(const std::vector<std::string_view> &rpn_tokens) {
std::stack<std::function<double(double)>> subexpressions;
for (const auto &token: rpn_tokens) {
if (token.empty())
throw std::runtime_error("empty token");
if (token == "x") { // Variable
subexpressions.push([](double x){
return x;
});
} else if (isdigit(token[0])) { // Literal number
double value = std::stof(token.data());
subexpressions.push([=](double /* ignored */){
return value;
});
} else if (token == "sin") { // Example unary operator
if (subexpressions.size() < 1) {
throw std::runtime_error("invalid expression");
}
auto operand = subexpressions.top();
subexpressions.pop();
subexpressions.push([=](double x){
return std::sin(operand(x));
});
} else if (token == "+") { // Example binary operator
if (subexpressions.size() < 2) {
throw std::runtime_error("invalid expression");
}
auto right_operand = subexpressions.top();
subexpressions.pop();
auto left_operand = subexpressions.top();
subexpressions.pop();
subexpressions.push([=](double x){
return left_operand(x) + right_operand(x);
});
} else {
throw std::runtime_error("invalid token");
}
}
if (subexpressions.size() != 1) {
throw std::runtime_error("invalid expression");
}
return subexpressions.top();
}
int main() {
auto function = build_function({"1", "x", "2", "+", "sin", "+"}); // 1 + sin(2 + x)
for (double x = 0; x < 2 * std::numbers::pi; x += 0.1) {
std::cout << x << ' ' << function(x) << '\n';
}
}
I call this a poor man's JIT because while it looks like we get a function object that is seemingly created at runtime, it basically is a bunch of precompiled functions (one for each lambda body in the above code) strung together by the lambda captures. So there is quite a lot more overhead when calling the above function() than if one would write the following:
auto function = [](double x){
return 1 + sin(2 + x);
}
But it should still be much faster than parsing the bunch of tokens that make up the equation each time you want to evaluate it.
Some questions:
- Is there a better way to do this?
- Is this technique already implemented in some library?
- The argument to resulting function has to be passed down to most of the lambdas (the exception being the one returning literal numbers). Is there a better way to do this?
- How should one handle building a function that takes multiple arguments? Can we make
build_functiona template somehow that can return astd::functionwith a variable number of arguments?
Performance measurements on an AMD Ryzen 3900X, code compiled with GCC 10.2.1 with -O2, after a warm-up of 60 million invocations, averaged over another 60 million invocations of function():
- A simple lambda: 10 ns per evaluation
- The above code: 21 ns per evaluation
- Deduplicator's original answer: 77 ns per evaluation
- Adding
stack.reserve(): 39 ns per evaluation - Making
stackstatic: 26 ns per evaluation
- Adding
- Deduplicator's version using separate bytecode and data stacks: 19 ns per evaluation
- Hardcoding using a fixed small stack: 17 ns per evaluation
main(). Otherwise the compiler can just substitute the hell out of everything. \$\endgroup\$