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 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 1000000 The above command will execute each expression found in the file 'test_expr.txt' 1000000 times. As output we get the following: ./exprtk_benchmark test_expr.txt 1000000 Expression 1 of 1 115.745 ns 115745438 ns (144749.1137301750) '1/(x*sqrt(2*pi))*e^(-0.5*((y-x)/x)^2)' [*] Number Of Evals: 1000000 [*] Total Time: 0.116sec [*] Total Single Eval Time: 0.000ms The above output denotes the average time per evaluation and the total time for evaluating the expression one million times. For our investigation we will concentrate only on the average evaluation time (eg: 115.745 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 1000000 Expression 1 of 3 115.226 ns 115225973 ns (144749.1137301750) '1/(x*sqrt(2*pi))*e^(-0.5*((y-x)/x)^2)' Expression 2 of 3 6.971 ns 6971151 ns (157799.3433528780) '1 / (x * sqrt(2 * pi))' Expression 3 of 3 109.611 ns 109610776 ns (922539.8825277411) 'e^(-0.5 * ((y - x) / x)^2)' [*] Number Of Evals: 3000000 [*] Total Time: 0.234sec [*] 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 7ns - 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 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 1000000 Expression 1 of 4 135.235 ns 135235355 ns (144749.1137301750) '1/(x*sqrt(2*pi))*e^(-0.5*((y-x)/x)^2)' Expression 2 of 4 7.084 ns 7083584 ns (157799.3433528780) '1 / (x * sqrt(2 * pi))' Expression 3 of 4 105.596 ns 105596366 ns (922539.8825277411) 'e^(-0.5 * ((y - x) / x)^2)' Expression 4 of 4 64.313 ns 64312578 ns (-81069.1779004620) '-0.5 * ((y - x) / x)^2' [*] Number Of Evals: 4000000 [*] Total Time: 0.314sec [*] Total Single Eval Time: 0.000ms From the above result, we conclude that the exponentiation operation consumes roughly 39% of time required to evaluate the second 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 1000000 Expression 1 of 6 132.121 ns 132121023 ns (144749.1137301750) '1/(x*sqrt(2*pi))*e^(-0.5*((y-x)/x)^2)' Expression 2 of 6 7.026 ns 7025524 ns (157799.3433528780) '1 / (x * sqrt(2 * pi))' Expression 3 of 6 114.102 ns 114101950 ns (922539.8825277411) 'e^(-0.5 * ((y - x) / x)^2)' Expression 4 of 6 69.165 ns 69165320 ns (-81069.1779004620) '-0.5 * ((y - x) / x)^2' Expression 5 of 6 97.226 ns 97225639 ns (922539.8825277411) 'exp(-0.5 * ((y - x) / x)^2)' Expression 6 of 6 102.544 ns 102544394 ns (144749.1137301750) '1/(x*sqrt(2*pi))*exp(-0.5*((y-x)/x)^2)' [*] Number Of Evals: 6000000 [*] Total Time: 0.539sec [*] Total Single Eval Time: 0.001ms In conclusion the above modification resulted in a 22% 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. --- 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 ---