likun666661 commented on PR #50372:
URL: https://github.com/apache/arrow/pull/50372#issuecomment-5010517751
Thank you again for the detailed review. I have completed a local follow-up
prototype and benchmark pass addressing the two remaining concerns: the
conservative
"do not fold" contract and large-expression performance evidence.
I have **not pushed these changes yet**. I would like to confirm the
narrowed design
with you before updating the PR.
## Proposed narrowed design
I split the implementation into two conservative layers:
1. **AST structural sharing**
- Canonicalize structurally identical fields, literals, and safe built-in
function
subtrees into a DAG.
- Use a structural key composed of node kind, function/field/literal
identity,
return type, and ordered child atom IDs.
- Preserve operand order. There is no commutative normalization.
2. **Same-basic-block Dex/LLVM value reuse**
- Reuse a decomposed `ValueValidityPair` only for a reusable canonical
AST node.
- Reuse a generated `LValue` only when the same `Dex` was generated in
the same
LLVM `BasicBlock`.
- Cache a generated value only when code generation ends in the block
where it
started.
I removed the Boolean/`if` algebraic transformations from the local version:
- no Boolean flattening or predicate deduplication;
- no `if(c, x, x) -> x`;
- no reuse across Boolean short-circuit blocks or `if` branches;
- no reuse across separately compiled output expressions.
This is intentionally a post-construction Gandiva pass. It canonicalizes an
AST after
the caller has already built it in `Projector::Make()` or `Filter::Make()`.
It reduces
decomposition, generated IR, LLVM optimization, and JIT work, but does not
claim to
remove caller-side `TreeExprBuilder` or SQL-to-Gandiva construction cost.
That is an
important difference from the Cloudberry article that initially motivated
this work.
## Safety contract
A function subtree is reusable only when:
```text
the function is a Gandiva built-in
and result nullability is not kResultNullInternal
and it does not need ExecutionContext
and it does not need a FunctionHolder
and it cannot return errors
and every child subtree is reusable
```
The built-in-only rule prevents a custom function registered with default
flags from
being treated as pure accidentally.
Functions such as `lower` and `upper` remain excluded in this initial
version. They are
deterministic at the SQL level, but Gandiva marks them `kNeedsContext`; their
implementations allocate output from the execution-context arena and may set
errors for
invalid UTF-8, invalid lengths, or allocation failures. I think those
functions need
explicit effect/CSE-safety metadata rather than relaxing the context
restriction
globally.
## Affected modules
| Module | Responsibility |
| --- | --- |
| `expr_cse.{h,cc}` | Structural keys, canonical AST nodes, shared safety
predicate |
| `function_registry.{h,cc}` | Distinguish built-ins from custom registered
functions |
| `projector.cc`, `filter.cc` | Fold before cache lookup, validation, and
code generation |
| `expr_decomposer.{h,cc}` | Cache safe decompositions by canonical node
identity |
| `llvm_generator.{h,cc}` | Reuse generated `LValue` only in the same basic
block |
| `engine.h`, `projector.cc` | Guard unoptimized IR using actual captured
engine state |
| CSE/projector/filter tests | Safety-contract, IR-shape, runtime, and cache
regressions |
| `micro_benchmarks.cc` | Fold, build, IR-size, and evaluation benchmarks |
## Module flow
```mermaid
flowchart LR
Caller["Gandiva caller"]
Entry["Projector::Make / Filter::Make"]
Folder["AST structural CSE"]
Registry["FunctionRegistry safety/provenance"]
Cache["Gandiva object cache"]
Decomposer["ExprDecomposer"]
Generator["LLVMGenerator::Visitor"]
BlockCache["Basic-block Dex cache"]
Engine["LLVM optimizer and JIT"]
Caller --> Entry
Entry --> Folder
Folder --> Registry
Entry --> Cache
Entry --> Decomposer
Decomposer --> Registry
Decomposer --> Generator
Generator --> BlockCache
Generator --> Engine
```
## Build sequence
```mermaid
sequenceDiagram
participant C as Caller
participant P as Projector or Filter
participant F as AST folder
participant R as FunctionRegistry
participant D as ExprDecomposer
participant G as LLVMGenerator
participant E as Engine
C->>P: Make(schema, expressions, config)
P->>F: FoldCommonSubexpressions
loop bottom-up AST traversal
F->>R: LookupSignature and IsBuiltIn
F->>F: intern safe structural node
end
F-->>P: folded AST DAG
P->>D: Decompose folded AST
D->>R: verify subtree reuse safety
D-->>G: shared ValueValidityPair/Dex graph
G->>G: reuse Dex value only in current BasicBlock
G->>E: FinalizeModule
E->>E: capture optional pre-optimization IR
E->>E: optimize and JIT
E-->>P: compiled code
P-->>C: Projector or Filter
```
## Focused safety tests
The local `FoldCommonSubexpressions()` test suite now directly covers:
- positive sharing within one expression and across input expression objects;
- `kResultNullInternal`;
- `NeedsContext()`;
- `NeedsFunctionHolder()`;
- `CanReturnErrors()`;
- a safe parent with an unsafe child;
- unknown functions;
- custom registered functions with default flags;
- opaque `InExpressionNode`;
- different literal values and types;
- operand order (`add(a,b)` versus `add(b,a)`);
- Boolean algebra not being applied;
- `if` algebra not being applied.
IR/runtime tests additionally verify:
- two repeated `add` calls become one in the same block;
- repeated values are not reused across `if` branches;
- `if(c, x, x)` still contains its condition, branch blocks, and phi;
- Boolean short-circuit CFG is preserved;
- the nested repeated-`between` pattern still emits three copies of each
comparison
because the copies occur in different Boolean blocks;
- filter cache behavior no longer relies on Boolean deduplication;
- cached and mutable-configuration unoptimized-IR error paths.
Local test results:
| Test binary | Result |
| --- | --- |
| `gandiva-internals-test` | 169 passed |
| `gandiva-projector-test` with `TZ=UTC` | 226 passed, 1 existing aarch64
skip |
| `gandiva-precompiled-test` | 132 passed |
| `git diff --check` | passed |
## Benchmark method
- Apple M4, Release build, LLVM 20.1.7;
- Google Benchmark, three repetitions, CPU-time mean;
- expression sizes 10, 100, and 1,000;
- three patterns: deep unique, balanced repeated safe, and balanced repeated
unsafe;
- measured fold-only, Projector/Filter build, unoptimized IR bytes, and
evaluation
separately;
- the disabled baseline bypassed only the AST folding calls, with identical
inputs and
LLVM settings;
- input AST construction was paused outside the timed build section.
## Results at size 1,000
| Pattern | Projector build, disabled -> enabled | Filter build, disabled ->
enabled | Projector unoptimized IR |
| --- | ---: | ---: | ---: |
| Deep unique | 178.7 -> 186.4 ms (+4.3%) | 50.4 -> 52.1 ms (+3.4%) |
116,902 -> 116,902 bytes |
| Repeated safe | 81.6 -> 21.4 ms (-73.8%) | 78.5 -> 22.0 ms (-72.0%) |
1,923,715 -> 5,963 bytes (-99.69%) |
| Repeated unsafe | 4,256.4 -> 4,356.6 ms (+2.4%) | 4,450.3 -> 4,487.1 ms
(+0.8%) | 2,350,279 -> 2,350,279 bytes |
Repeated-safe scaling:
| Size | Projector build | Filter build | IR reduction |
| ---: | ---: | ---: | ---: |
| 10 | 17.1 -> 18.2 ms (+6.5%) | 15.9 -> 16.0 ms (+0.5%) | -78.2% |
| 100 | 20.7 -> 17.7 ms (-14.5%) | 19.0 -> 16.6 ms (-12.6%) | -97.2% |
| 1,000 | 81.6 -> 21.4 ms (-73.8%) | 78.5 -> 22.0 ms (-72.0%) | -99.69% |
Evaluation at size 1,000:
| Pattern | Projector | Filter |
| --- | ---: | ---: |
| Deep unique | 254.44 -> 255.10 us (+0.3%) | 433.97 -> 434.44 us (+0.1%) |
| Repeated safe | 19.42 -> 17.24 us (-11.2%) | 20.68 -> 18.97 us (-8.2%) |
| Repeated unsafe | 525.48 -> 523.48 us (-0.4%) | 530.93 -> 527.66 us
(-0.6%) |
The strongest result is the reduction in compiler input and build time for
repeated
safe expressions. Unique expressions pay a small linear hash-consing cost,
while unsafe
expressions preserve their original IR.
Before I push the follow-up, I would appreciate feedback on these boundaries:
1. Is built-in-only reuse an acceptable initial safety contract?
2. Is same-basic-block Dex reuse sufficiently conservative for the first
version?
3. Should AST interning and execution-value reuse be represented as separate
concepts?
4. Would explicit function effect/CSE-safety metadata be the preferred way
to consider
arena-allocating deterministic functions such as `lower` and `upper`
later?
--
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]
