-
Notifications
You must be signed in to change notification settings - Fork 1
Expression Optimization
arithmexp
performs several expression optimizations at the end of parsing stage to reduce computational wherever possible. To disable optimizations, replace Parser::createDefault()
with Parser::createUnoptimized()
. arithmexp
executes the following optimization techniques on an expression:
-
Constant folding — Constant sub-expressions are evaluated at the parsing stage rather than the evaluation stage. For example, the expression
2 * 3 * x
gets rewritten as6 * x
. -
Idempotence Folding — Multiple calls to idempotent functions are transformed by reducing the number of function calls. For example, the expression
round(round(x))
gets rewritten asround(x)
, and the expressionmin(min(x, y), z, min(w))
gets rewritten asmin(x, y, z, w)
. -
Operator Strength Reduction — Computation is reduced by incorporating various mathematical identities to solve sub-expressions at the parsing stage. For example, the expression
(x * y) ** 1
gets rewritten asx * y
, while the expression(x * 2) / (4 * x)
gets rewritten as a constant0.5
. -
Expression Reordering — Operators in commutative operations (addition and multiplication) are rearranged by shifting numeric literals towards the right and variables towards the left. This optimization helps other optimization techniques further optimize an expression. For example, the expression
2 * x * 4
gets rewritten asx * 2 * 4
, and later tox * 6
during constant folding.
Aside from the gain in performance, optimizations can help in detecting errors early. For example:
- the expression
x / (y - y)
fails during the parsing stage (rather than the evaluation stage) due to division by zero - the expression
x % (y ** 0 - z ** 0)
fails during the parsing stage due to modulo by zero
As the optimizer may rearrange the expression, the resulting expression may return a more or less precise value than the original (albeit being mathematically equivalent). For example, the parser may rearrange (39 * 126) / 47
as (39 / 47) * 126
, resulting in float(104.5531914893617)
instead of float(104.55319148936171)
(an error of 1e-14
) due to how floating-point operations are handled by programming languages.
Due to rearranging, arithmexp may appear more or less powerful than PHP itself in few cases. For example, the expression 2 ** 1025 / 2 ** 1024
evaluates to int(2)
, instead of float(NAN)
, because arithmexp evaluates the expression as 2 ** (1025 - 1024)
(due to strength reduction optimization) instead of (2 ** 1025) / (2 ** 1024)
as PHP does. Ofcourse, this rearrangement is only possible when the base value in the two exponentiation operations are known during parsing stage (i.e., the bases are constant). The expression x ** a / x ** b
is rearranged as x ** (a - b)
whereas the expression x ** a / y ** b
is not.
Try out arithmexp
on the demo site!
1.1. Installation
2.1. Constant
2.2. Function
2.3. Macro
2.4. Operator
2.5. Variable
2.6. Expression Optimization
2.7. Implementation Internals