Repository navigation
Optimize arrays top down as execution reaches them, and retry a parent when its children change - #11090
Conversation
02fa232 to
d889c87
Compare
d889c87 to
6f69042
Compare
6f69042 to
0cf0f95
Compare
0cf0f95 to
1d684a8
Compare
Merging this PR will degrade performance by 17.68%1 warning
Warning Please fix the performance issues or acknowledge them on CodSpeed. Performance Changes
Tip Investigate this regression by commenting Comparing Footnotes
|
4db3b2a to
13495e7
Compare
## Summary Follow-up to #11110. Keep the remaining noisy cases out of automatic CodSpeed runs while preserving them for local benchmarks. The Python scalar exclusions in #11110 never took effect because the runner exports simulation as `instrumentation`, while the fixture checked for `simulation`. Use the plugin's resolved mode so these cases are actually skipped. ## Changes - Allow a trailing comma in `#[divan::bench(...)]` when the CPU-feature macro appends its options. The multiline bitpacked take definition covers this case in CI builds. - Share the resolved simulation check between the scalar and filter fixtures. Also skip the 2 integer one-shot filtered scans that still report system calls under simulation. - Keep AVX2 bitpacked take with 80 selections local after batching still produced a regression alert. Retain the 64-selection case and both AVX-512 cases in CI. - Keep AVX-512 nullable integer comparison local because its minimum changes by more than 10% while its median stays stable. - Keep the small random power-law boolean filter and the large correlated power-law boolean filter local under simulation. The former has repeated unexplained changes, and the latter repeatedly makes system calls that simulation cannot measure. <details> <summary>Evidence from recent PR reports</summary> Reviewed 40 CodSpeed report comments updated between November 2 at 19:28 UTC and November 3 at 19:28 UTC, including their comparison revisions and the affected measurement modes. | Case | Evidence | | --- | --- | | Python integer scalar scans | [#11154](#11154 (comment)) still reports the repeated scan's 10 system calls. [A develop run after #11110](https://github.com/vortex-data/vortex/actions/runs/41677647530/job/126062463160) executes both integer scalar cases instead of skipping them. The [runner exports the legacy `instrumentation` value](https://github.com/CodSpeedHQ/codspeed/blob/main/crates/runner-shared/src/measurement_mode.rs), which pytest-codspeed 5.0.3 normalizes to simulation. | | Python integer filtered scans | [#11130](#11130 (comment)) reports 30 system calls totaling 14.3 ms in `test_scan_filter[int]`. [#11138](#11138 (comment)) reports 30 calls totaling 16.3 ms in `test_scan_filter_to_arrow_array[int]`. | | AVX2 `threshold[80]` | [#11004](#11004 (comment)) compares `f7b5b1d864` with `e59b236d7b`: 2.183 to 2.531 µs, reported as a 13.75% regression. Both use 1000 samples of 16 iterations. The head median is 2.556 µs, so this is not just a single outlying minimum. The PR does not change the fastlanes code or benchmark. | | AVX-512 `lt_i64_nullable` | [#11168](#11168 (comment)) reports 7.342 to 8.217 µs. Several unrelated CUDA PRs report the opposite direction, including [#10872](#10872 (comment)), at 8.208 to 7.348 µs. Their head medians remain around 8.3 to 8.5 µs. | | Boolean `filter_powerlaw_by_random[10000]` | [#11167](#11167 (comment)) reports a 16.2% regression, [#11168](#11168 (comment)) a 23.56% improvement, and [#11169](#11169 (comment)) a 13.06% regression. The cause is unknown. | | Boolean `filter_powerlaw_by_correlated_runs[100000]` | [#10871](#10871 (comment)) and [#11165](#11165 (comment)) each report 2 system calls totaling about 44 µs. | The NEON chunked-take alerts on #11090 are on a PR that changes execution substantially, so those cases remain enabled. Other dictionary simulation alerts need more attribution before excluding them. </details> CI passes formatting, Python lint and script tests, Rust lint, default-feature and all-feature Rust builds, all 3 CPU walltime benchmark jobs, and Python benchmarks (36 passed, 4 intentionally skipped). The previously failed simulation shard also passes. Some remaining CI jobs and CodSpeed performance analysis are still pending. No local checks were run. The pre-commit and pre-push hooks were bypassed as requested. --------- Signed-off-by: Connor Tsui <[email protected]>
With a session, the optimizer now optimizes the children of a node that were never optimized before it tries the rules of the node, and it does the same for the nodes that each rewrite builds. Children already marked are left without visiting their subtrees. The optimizer marks every array it returns, and it remembers for one call the array it rewrote each shared node into. optimize_recursive is now the same as optimize_ctx. The session-less optimize still rewrites only the root and does not mark the result, so a later optimize with a session still tries its kernels. execute_until now optimizes the root before it starts, each child that execution focuses, the result of each Done step, and the array it returns. Single-step execution optimizes with the session instead of trying only the static reduce and parent-reduce rules. Signed-off-by: Robert Kruszewski <[email protected]>
trace_op! dropped its arguments when the trace harness was not compiled in. Thus a value that only a trace event reads, such as any_optimizations in the optimizer, was reported as unused in plain and CodSpeed builds of vortex-array. The macro now borrows its arguments in a branch that never runs, so they are type-checked but not evaluated. Signed-off-by: Robert Kruszewski <[email protected]>
Execution now optimizes each array that it reaches unless the array is already marked. Arrays that a reader decodes are marked, but benchmarks build their inputs with constructors. Thus the timed region also timed the optimizer, and CodSpeed reported about 400 regressions that production does not see. test_harness::mark_optimized optimizes an input during setup and panics if the optimizer rewrites it, so a benchmark cannot time a different array than the one it built. test_harness::mark_decoded marks each node without trying any rule, as decoding does. The cosine similarity benchmark uses it for an extension array over constant storage, which a file can hold but the optimizer folds into a constant. Lazy arrays that a benchmark builds inside the timed closure stay unmarked, because their optimization is part of the cost it measures. Signed-off-by: Robert Kruszewski <[email protected]>
execute_until now keeps one optimizer for the whole execution. Thus a shared node that one step rewrote is reused when a later step reaches it through another parent, and is not rewritten again. The optimizer keys its cache of rewritten shared nodes by ArrayByPtr, a key that compares arrays by identity. The key holds the array, so its address cannot be reused while the optimizer exists. Signed-off-by: Robert Kruszewski <[email protected]>
13495e7 to
60c1c8b
Compare
split_extreme and the widen_decimal benchmarks came in with the rebase on develop. They built their inputs with constructors and did not mark them, so the timed region also timed the optimizer. They now mark their inputs during setup, as the other benchmarks do. Signed-off-by: Robert Kruszewski <[email protected]>
The optimizer now tries the rules of a node before it optimizes the children of the node. Thus a rule that drops or replaces a child does not optimize the subtree of that child first. After the children are optimized, the optimizer tries the rules of the node again if a child changed. Thus a parent rule or kernel that is keyed on the final encoding of a child still applies, such as LIKE over a slice of an FSST array. When a rule rewrites a node, the optimizer still optimizes the nodes that the rule built before the next pass on the node. This stops two rules that are inverses of each other from rewriting a node back and forth. The trace snapshot of the stack parent kernel test now shows the parent optimized before its child. Signed-off-by: Robert Kruszewski <[email protected]>
Polar Signals Profiling ResultsLatest Run
Powered by Polar Signals Cloud |
Benchmarks: PolarSignals Profiling 📖Commits: PR datafusion / vortex-file-compressed / ns (1.052x ➖, 0↑ 2↓)
|
Benchmarks: FineWeb NVMe 📖Commits: PR How to read Verdict and Engines
datafusion / vortex-file-compressed / ns (0.972x ➖, 0↑ 0↓)
datafusion / parquet / ns (1.010x ➖, 0↑ 0↓)
duckdb / vortex-file-compressed / ns (1.004x ➖, 0↑ 0↓)
duckdb / parquet / ns (0.993x ➖, 0↑ 0↓)
|
Benchmarks: TPC-H SF=1 on NVME 📖Commits: PR How to read Verdict and Engines
datafusion / vortex-file-compressed / ns (1.016x ➖, 0↑ 1↓)
datafusion / parquet / ns (1.000x ➖, 0↑ 0↓)
duckdb / vortex-file-compressed / ns (1.006x ➖, 0↑ 0↓)
duckdb / parquet / ns (1.002x ➖, 0↑ 0↓)
|
Benchmarks: TPC-H SF=10 on NVME 📖Commits: PR How to read Verdict and Engines
datafusion / vortex-file-compressed / ns (0.998x ➖, 0↑ 0↓)
datafusion / parquet / ns (0.997x ➖, 0↑ 0↓)
duckdb / vortex-file-compressed / ns (1.004x ➖, 0↑ 0↓)
duckdb / parquet / ns (0.999x ➖, 0↑ 0↓)
|
Benchmarks: Clickbench on NVME 📖Commits: PR How to read Verdict and Engines
datafusion / vortex-file-compressed / ns (0.994x ➖, 0↑ 0↓)
datafusion / parquet / ns (0.990x ➖, 0↑ 0↓)
duckdb / vortex-file-compressed / ns (1.001x ➖, 0↑ 1↓)
duckdb / parquet / ns (0.990x ➖, 1↑ 0↓)
|
Benchmarks: TPC-DS SF=1 on NVME 📖Commits: PR How to read Verdict and Engines
datafusion / vortex-file-compressed / ns (1.003x ➖, 0↑ 0↓)
datafusion / parquet / ns (1.003x ➖, 0↑ 0↓)
duckdb / vortex-file-compressed / ns (1.002x ➖, 1↑ 0↓)
duckdb / parquet / ns (1.000x ➖, 0↑ 0↓)
|
Benchmarks: TPC-H SF=1 on S3 📖Commits: PR How to read Verdict and Engines
datafusion / vortex-file-compressed / ns (1.088x ➖, 1↑ 2↓)
datafusion / parquet / ns (1.029x ➖, 1↑ 0↓)
duckdb / vortex-file-compressed / ns (1.074x ➖, 0↑ 0↓)
duckdb / parquet / ns (1.012x ➖, 1↑ 0↓)
|
Benchmarks: TPC-DS SF=10 on NVME 📖Commits: PR How to read Verdict and Engines
datafusion / vortex-file-compressed / ns (1.004x ➖, 0↑ 0↓)
datafusion / parquet / ns (1.002x ➖, 0↑ 0↓)
duckdb / vortex-file-compressed / ns (1.003x ➖, 0↑ 0↓)
duckdb / parquet / ns (0.997x ➖, 1↑ 0↓)
|
`ArrayOptimizer::optimize` uses only the static rules of the encodings, so it misses the kernels that a session registers. This PR deprecates it, and array constructors no longer optimize the arrays they build. ## Changes - `optimize_ctx` and `optimize_recursive` take `&impl AsOptimizerKernels`, which is a `VortexSession` or an `ExecutionCtx` created from one. Existing `optimize_ctx(&session)` callers compile without changes. - Constructors such as `slice`, `filter`, `take`, `cast`, `fill_null`, `get_item` and `apply` return lazy arrays. Execution optimizes each node it reaches (#11090). Callers that read the encoding of an array directly now optimize it with their session first: scan tasks, plan v2 operators, the dict layout writer, the FFI scan and CUDA dispatch. - The default `append_to_builder` optimizes the array first. It then appends through the encoding the array reduces to, so a lazy slice of a constant appends as a constant. - Tests now call `optimize_ctx(&SESSION)` instead of `optimize()`. ## API Changes - `ArrayOptimizer::optimize` is deprecated. Use `optimize_ctx` with the session or an `ExecutionCtx`. - `ArrayOptimizer::optimize_ctx` and `optimize_recursive` are generic over `AsOptimizerKernels`. - `ArrayRef::slice`, `filter`, `take` and the `ArrayBuiltins` methods no longer return an optimized array. --------- Signed-off-by: Robert Kruszewski <[email protected]>
With a session, the optimizer now works bottom up, and execution optimizes each node that it reaches. This prepares for lazy constructors in #11091.
Changes
optimize_ctxoptimizes the children of a node that were never optimized before it tries the rules of the node. It does the same for the nodes that each rewrite builds. It does not visit marked subtrees, and it marks every array that it returns. Thus inverse rules, such asslice(get_item)andget_item(slice), cannot loop.optimize_recursiveis now the same asoptimize_ctx.optimizestill rewrites only the root and does not mark the result. Thus a lateroptimize_ctxstill tries the session kernels.execute_untiloptimizes the root before it starts, each child that execution focuses, the result of eachDonestep, and the array that it returns. Single-step execution optimizes with the session, instead of trying only the static reduce and parent-reduce rules.Chunked::reducedoes not reduce an empty variant array, becauseVarianthas no empty canonical form.