pjfanning opened a new pull request, #1321:
URL: https://github.com/apache/poi/pull/1321
Item 3 of the evaluator performance review.
## Before
Whether an operator with an area operand is evaluated element-wise depends
on whether its result ends up in an `ArrayMode` function (SUMPRODUCT, INDEX,
XLOOKUP …). `isConsumedByArrayModeFunction` (from #1299) answered that per
operation by walking the *remaining* tokens while tracking the result's stack
position — O(n) per operation with an area operand, O(n²) per formula in the
worst case (`SUM(A:A)+SUM(B:B)+…`) — and identified built-in functions with
`FunctionEval.getBasicFunction`, which **throws** `NotImplementedException` for
unimplemented functions; the walk caught it, so any formula containing such a
function paid a constructed exception per area operation per evaluation.
## After
`findArrayModeOperands(Ptg[])` does it for the whole formula in one pass:
replay the RPN structurally (a stack of producer indices), record the consumer
of every value and whether each function is `ArrayMode`, then propagate
`consumed[k] = arrayMode[consumer] || consumed[consumer]` in a backward sweep
(consumers always follow their operands in RPN). `evaluateFormula` computes it
lazily on the first operation that actually has an area operand — most formulas
never do — and reads one flag per operation after that.
Semantics are unchanged; the structural rules are the same as the walk's
(`tAttrSum` is `SUM`, other attribute/control/mem tokens are transparent,
`UnionPtg` consumes two). The one place that needed thought is external
("future"/UDF) functions: the walk read the function's name from the
`FunctionNameEval` already on the runtime stack; the pass resolves the name
token statically — `NamePtg` via `isFunctionName()`, `NameXPxg`/`NameXPtg` the
way `getLocalNameXEval` would, and only for this workbook (a name in another
workbook never yields a `FunctionNameEval`, so the walk said "no" there too).
No name formula is evaluated by the pass.
`FunctionEval.getBasicFunctionOrNull(int)` (`@since 6.0.0`) is the
non-throwing lookup; `getBasicFunction` is unchanged.
## Tests
`TestArrayModeOperands`: element-wise inside SUMPRODUCT/INDEX including
through an enclosing operator and through a non-array function
(`SUMPRODUCT(SUM(A1:A3*2),1)` = 12); row-reduction outside (`A1:A3*2` = A2*2,
`#VALUE!` on a row outside the area), and — the cases the per-token flags
matter for — an array function elsewhere in the formula not affecting operators
it does not consume (`A1:A3*2+SUMPRODUCT(B1:B3,C1:C3)`,
`SUMPRODUCT(A1:A3*2)+A1:A3*3`); XLOOKUP with `(A1:A3=2)*(B1:B3=20)` as lookup
array (the external-function path); and the raw per-token flag arrays for three
formulas. All of the behavioural assertions pass on trunk as well, so this is a
pure refactor for cost.
Locally green: `ss.formula.*` (both modules), `TestHSSFFormulaEvaluator*`,
`TestFormulaEvaluatorBugs`, `TestBugs`, `ss.usermodel.*`,
`TestXSSFFormulaEvaluator*`, `TestXSSFXLookupFunction`,
`TestFormulaEvaluatorOnXSSF`, `TestXSSFBugs` (pre-existing
`stackoverflow23114397` aside).
`changes.xml` left for you.
🤖 Generated with [Claude Code](https://claude.com/claude-code)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
