Investigation Of An Evaluation Performance Issue In ExprTk The following expression has been noted as being inefficient with regards to evaluation time when compared to its native implementation: 1 / (x * sqrt(2 * pi)) * e^(-0.5 * ((y - x) / x)^2) For this investigation we will assume the ExprTk evaluation engine as a blackbox and attempt to experiment with variations of the problematic expression against the blackbox. To setup the experiment we initially create a text file called 'test_expr.txt' and input the above denoted expression. Next we execute the exprtk_benchmark program as follows: ./exprtk_benchmark test_expr.txt 10000000 The above command will execute each expression found in the file 'test_expr.txt' 10000000 times. As output we get the following: ./exprtk_benchmark test_expr.txt 10000000 Expression 1 of 1 22.908 ns 229078999 ns (1447491.1374857433) '1/(x*sqrt(2*pi))*e^(-0.5*((y-x)/x)^2)' [*] Number Of Evals: 10000000 [*] Total Time: 0.229sec [*] Total Single Eval Time: 0.000ms The above output denotes the average time per evaluation and the total time for evaluating the expression ten million times. For our investigation we will concentrate only on the average evaluation time (eg: 22.908 ns) As a first step in the experiment we try to break the expression up into no more than two parts - The parts don't have to be of equal complexity, but rather as a means to bisect the expression so as to pinpoint the sub expression that that consumes the most computing time. One possible partition is as follows: 1. 1 / (x * sqrt(2 * pi)) 2. e^(-0.5 * ((y - x) / x)^2) We add the two new expressions to the 'test_expr.txt' file and execute the benchmark program. The following output is observed: ./exprtk_benchmark test_expr.txt 10000000 Expression 1 of 3 22.577 ns 225766000 ns (1447491.1374857433) '1/(x*sqrt(2*pi))*e^(-0.5*((y-x)/x)^2)' Expression 2 of 3 2.580 ns 25799000 ns (1577993.4335124078) '1 / (x * sqrt(2 * pi))' Expression 3 of 3 20.111 ns 201105999 ns (9225398.8246025164) 'e^(-0.5 * ((y - x) / x)^2)' [*] Number Of Evals: 30000000 [*] Total Time: 0.453sec [*] Total Single Eval Time: 0.000ms From the above numbers we can safely conclude that there isn't much that can be gained by fiddling with the first sub expression, its average run-time is nearly 3ns - which is quite close to what is normally required for a double type division and variable load into a register. Empirically the second sub-expression makes up the lion's share of evaluation time. We could partition the second sub-expression, however we note that the internal part of the expression (eg: '-0.5 * ((y-x) / x)^2') is a rather trivial expression, perhaps stripping the exponentiation operation (e^(....)) from the expression may provide an interesting result. So we place the exponentiation stripped form of the expression into the 'test_expr.txt' file and execute the benchmark program. The following output is observed: ./exprtk_benchmark test_expr.txt 10000000 Expression 1 of 4 22.643 ns 226427000 ns (1447491.1374857433) '1/(x*sqrt(2*pi))*e^(-0.5*((y-x)/x)^2)' Expression 2 of 4 2.603 ns 26026000 ns (1577993.4335124078) '1 / (x * sqrt(2 * pi))' Expression 3 of 4 20.410 ns 204095000 ns (9225398.8246025164) 'e^(-0.5 * ((y - x) / x)^2)' Expression 4 of 4 5.838 ns 58383000 ns (-810691.7790301639) '-0.5 * ((y - x) / x)^2' [*] Number Of Evals: 40000000 [*] Total Time: 0.515sec [*] Total Single Eval Time: 0.000ms From the above result, we conclude that the exponentiation operation consumes roughly 29% of time required to evaluate the third sub-expression. The problem here is that 'e' is a constant variable and as such when the exponentiation is compiled the operation is mapped to the 'pow' function. The pow function is a general purpose exponentiation function that takes two parameters x and y and returns x^y (assuming the result is in the Real domain). In our expression the base value or x is Euler's number or 'e'. For expressions that are in the form 'e^y' there's a specific more efficient function called 'exp'. The function exp takes only one value as an input parameter and returns 'e' to power of that value. Knowing the above we modify the second sub-expression and the original expression to use the exp function and update the 'test_expr.txt' file accordingly and rerun the benchmark: ./exprtk_benchmark test_expr.txt 10000000 Expression 1 of 6 22.663 ns 226632000 ns ( 1447491.1374857433) '1/(x*sqrt(2*pi))*e^(-0.5*((y-x)/x)^2)' Expression 2 of 6 2.588 ns 25883999 ns ( 1577993.4335124078) '1 / (x * sqrt(2 * pi))' Expression 3 of 6 20.272 ns 202722000 ns ( 9225398.8246025164) 'e^(-0.5 * ((y - x) / x)^2)' Expression 4 of 6 5.824 ns 58242999 ns ( -810691.7790301639) '-0.5 * ((y - x) / x)^2' Expression 5 of 6 13.522 ns 135219000 ns ( 9225398.8246025164) 'exp(-0.5 * ((y - x) / x)^2)' Expression 6 of 6 16.582 ns 165821000 ns ( 1447491.1374857433) '1/(x*sqrt(2*pi))*exp(-0.5*((y-x)/x)^2)' [*] Number Of Evals: 60000000 [*] Total Time: 0.815sec [*] Total Single Eval Time: 0.000ms In conclusion the above modification resulted in a 26% reduction in evaluation time. ExprTk does not implicitly perform this substitution optimisation as 'e' is not a reserved word and can be a user defined variable, vector, string or function name. Furthermore attempting to correctly ascertain if a const variable or literal is the transcendental 'e' is itself a rather onerous proposition. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Details: CPU: Intel(R) Core(TM) i7-7600U CPU @ 2.80GHz Compiler: g++ 13.1.0 Build: g++-13 -pedantic-errors -Wall -Wextra -Werror \ -O3 -march=native -DNDEBUG -o exprtk_benchmark exprtk_benchmark.cpp \ -L/usr/lib -lc++ -lm --- snip test_expr.txt snip --- 1/(x*sqrt(2*pi))*e^(-0.5*((y-x)/x)^2) 1 / (x * sqrt(2 * pi)) e^(-0.5 * ((y - x) / x)^2) -0.5 * ((y - x) / x)^2 exp(-0.5 * ((y - x) / x)^2) 1/(x*sqrt(2*pi))*exp(-0.5*((y-x)/x)^2) --- snip test_expr.txt snip ---