alamb opened a new issue, #24727: URL: https://github.com/apache/datafusion/issues/24727
## Is your feature request related to a problem or challenge? DataFusion generates a large amount of machine code when compiled, which has a few negative effects: 1. **WASM size**: compiled WASM is large (10MB+), slowing page load times (See https://github.com/apache/datafusion/issues/16554) 2. **Build time**: more generated code means more work for LLVM and the linker, so compile times (and thus CI and local iteration) suffer. See https://github.com/apache/datafusion/issues/13814 3. **Binary size**: artifact size (aka binary code) directly affects cold start times, and memory footprint in projects like serverless functions and edge deployments A significant contributor to code size is **unnecessary monomorphization**, a fancy name for generic functions that get instantiated once per type, but the copies are mostly the same. Common patterns include: 1. **Generics that only call trait methods**: functions like `fn foo<P: ExecutionPlan + ?Sized>(plan: &P)` that never use `P` except through the trait. These compile to N identical copies where a single `&dyn` version would do. 2. **Per-primitive-type instantiation where only the byte width matters**: kernels generic over `ArrowPrimitiveType` that only move, compare-for-equality, or hash native values behave identically for all same-width types (e.g. `Int32`, `UInt32`, `Date32`, `Time32` are all 4-byte bit patterns) and can dispatch on width at runtime instead of instantiating 30+ copies. 3. **Large default trait method bodies**: default methods on widely-implemented traits (e.g. `ScalarUDFImpl`, with 100+ implementations in `datafusion-functions` alone) are monomorphized per implementing type, duplicating the default body each time. An example of pattern 1 is [`check_default_invariants`](https://github.com/apache/datafusion/blob/66a901f68ddf7ce9c114ee6cb27b3801d4c334e3/datafusion/physical-plan/src/execution_plan.rs#L1642-L1656), which is compiled once for each of the 38 `ExecutionPlan` implementations (~44,000 lines of LLVM IR) even though every copy is identical: ```rust pub fn check_default_invariants<P: ExecutionPlan + ?Sized>( plan: &P, check: InvariantLevel, ) -> Result<(), DataFusionError> { let children_len = plan.children().len(); check_len!(plan, maintains_input_order, children_len); check_len!(plan, required_input_ordering, children_len); check_len!(plan, benefits_from_input_partitioning, children_len); ... } ``` An example of pattern 2 is [`hash_array_primitive`](https://github.com/apache/datafusion/blob/66a901f68ddf7ce9c114ee6cb27b3801d4c334e3/datafusion/common/src/hash_utils.rs#L306-L333), which is instantiated for all 32 primitive types in every crate that calls `create_hashes` (~12,000 lines of LLVM IR per crate). It only reads native values as bit patterns and hashes them, so the copies for `Int32`, `UInt32`, `Date32`, and `Time32` are byte-identical machine code: ```rust // condensed; the real function also handles nulls and rehashing fn hash_array_primitive<T>( array: &PrimitiveArray<T>, random_state: &impl HashState, hashes_buffer: &mut [u64], rehash: bool, ) where T: ArrowPrimitiveType<Native: HashValue>, { for (hash, &value) in hashes_buffer.iter_mut().zip(array.values().iter()) { *hash = value.hash_one(random_state); } ... } ``` ## Early hints / inspiration @geoffreyclaude and I have been working to keep the size of the IN LIST implementations down as part of https://github.com/apache/datafusion/issues/19241 (he came up with using just bytewidth for FixedSizeBinary in https://github.com/apache/datafusion/pull/24102) and here is an example that reduces code size: https://github.com/apache/datafusion/pull/24687 (removed 67% of the module's generated code with no measurable runtime cost) and I think we have figured out a general recipe to find and remove this in the codebase: 1. Find candidates with `cargo llvm-lines --release -p <crate> --lib` (rank generic functions by total IR lines × instantiation count) 2. Rewrite the candidate to dispatch at runtime (e.g. per batch, not per row), keeping monomorphized inner loops only where the generated code actually differs 3. Verify with `cargo llvm-lines` before/after and the relevant criterion benchmarks (a size win must not cost measurable performance) ## Describe the solution you'd like A collection of tickets applying the recipe above to the largest offenders. ## How to measure improvements Every PR / issue in this epic should report before/after numbers using both of the measurements below, taken once at the merge-base with `main` and once on the branch (see example on "Code size" heading of https://github.com/apache/datafusion/pull/24687). ### 1. Generated code: `cargo llvm-lines` Counts pre-optimization LLVM IR lines per monomorphized function. Deterministic, and attributes code to specific functions, so it shows exactly which instantiations were removed: ```bash cargo install cargo-llvm-lines # Run on main and on your branch: cargo llvm-lines --release -p <crate> --lib > /tmp/llvm-lines-{main,branch}.txt # Crate-wide totals (lines and copies): head -3 /tmp/llvm-lines-main.txt # Total for the module you changed: awk '/<module_name>/ {gsub(/[(),%]/,"",$1); sum+=$1; n++} END {print sum, "IR lines across", n, "functions"}' /tmp/llvm-lines-main.txt ``` Report: module IR lines, module instantiation count, and crate totals, before and after. ### 2. Final binary size: release build Measures what users actually ship. ```bash # Gold standard: datafusion-cli (slow: fat LTO takes ~30+ minutes) cargo build --release --bin datafusion-cli ls -l target/release/datafusion-cli # Faster per-crate proxy: any bench binary that links the changed crate cargo bench --no-run -p <crate> --bench <bench_target> ls -l target/release/deps/<bench_target>-* ``` Build at the merge-base and on the branch, compare byte sizes. Note that typically the binary delta will be much smaller than the IR delta as LLVM and the linker deduplicate and dead-code-eliminate aggressively. ## Ideas Here are some ideas (from an AI tool) <details><summary>Candidate list (click to expand)</summary> Initial candidates identified by an `llvm-lines` survey of seven crates (rough IR line totals; final binary impact is smaller but proportional — the PoC measured ~3.3 bytes of binary per IR line): - [ ] `udaf_default_*` display/schema-name helpers in `datafusion/expr/src/udaf.rs`: generic over `<F: AggregateUDFImpl + ?Sized>` but only call trait methods; ~145K IR lines across 29 UDAF impls (pattern 1) - [ ] `check_default_invariants` / `check_dynamic_expression_invariants` in `datafusion-physical-plan`: ~69K IR lines across 38 `ExecutionPlan` impls (pattern 1) - [ ] `IN` list primitive filters (`BranchlessFilter<T>`, `PrimitiveHashSetFilter<T>`, `BitmapFilter<T>`): ~130K IR lines across 27 instantiations; equality-only → width dispatch (pattern 2) - [ ] `hash_array_primitive` in `datafusion-common`: ~12K IR lines × 32 instantiations *per consuming crate*, ~70K workspace-wide (pattern 2) - [ ] `first_last` primitive accumulators in `datafusion-functions-aggregate`: ~55K IR lines across 25 instantiations (pattern 2) - [ ] GROUP BY primitive group values (`PrimitiveGroupValueBuilder<T, NULLABLE>`, `GroupValuesPrimitive<T>`): ~75K IR lines (pattern 2; the `const NULLABLE: bool` parameter doubles every instantiation) - [ ] TopK aggregate `PrimitiveHashTable<T>`: ~22K IR lines across 32 instantiations (pattern 2) - [ ] `functions-nested` per-primitive kernels (`array_sort`, `array_min`/`array_max`, `array_has`): ~120K IR lines; the `OffsetSizeTrait` dimension doubles many of these (pattern 2) - [ ] CASE literal lookup table `PrimitiveIndexMap<T>`: ~25K IR lines across 32 instantiations (pattern 2) - [ ] Sort-merge primitive cursor streams (`SortPreservingMergeStream` specializations): ~27K IR lines (pattern 2) - [ ] `ScalarUDFImpl` default method bodies (`return_field_from_args`, `schema_name`, `output_ordering`): ~75K IR lines across 119 impls in `datafusion-functions`, repeated in every crate defining UDFs (pattern 3) - [ ] https://github.com/apache/datafusion/issues/24658 </details> ## Important caveats - **Avoid making the code more complicated.** The goal is less generated code, not cleverer source code. Most of these changes will probably reduce code. - **Float semantics**: `f16`/`f32`/`f64` have distinct equality/hash semantics (`NaN`, `±0.0`), so width-based merging applies to integer-semantics types only; floats likely have to keep their own instantiations - **Every change must be benchmarked.** The rule from the PoC: a size reduction is acceptable only if the relevant criterion benchmarks show no regression beyond noise. ## Describe alternatives you've considered Do nothing ## Additional context - https://github.com/apache/datafusion/issues/16554 - https://github.com/apache/datafusion/issues/13815 - https://github.com/apache/datafusion/issues/13814 - https://github.com/apache/datafusion/pull/24102 - https://github.com/apache/datafusion/pull/24687 -- 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]
