Add TakeSlices for fixed-size-list take#8674
Closed
danking wants to merge 37 commits into
Closed
Conversation
Merging this PR will regress 1 benchmark
Warning Please fix the performance issues or acknowledge them on CodSpeed. Performance Changes
Tip Investigate this regression by commenting Comparing 
Footnotes
|
danking
force-pushed
the
codex/take-slices-fsl
branch
4 times, most recently
from
0908aec to
a039028
Compare
danking
force-pushed
the
codex/take-slices-fsl
branch
from
a039028 to
949cfcb
Compare
github-actions
Bot
removed
the
action/benchmark
Contributor
Author
This comment was marked as outdated.
This comment was marked as outdated.
Contributor
Polar Signals Profiling ResultsLatest Run
Previous Runs (4)
Powered by Polar Signals Cloud |
|
Codex Review: Didn't find any major issues. What shall we delve into next? Reviewed commit: ℹ️ About Codex in GitHubYour team has set up Codex to review pull requests in this repo. Reviews are triggered when you
If Codex has suggestions, it will comment; otherwise it will react with 👍. Codex can also answer questions or update the PR. Try commenting "@codex address that feedback". |
Contributor
Benchmarks: PolarSignals ProfilingVortex (geomean): 0.894x ✅ How to read Verdict and Engines
datafusion / vortex-file-compressed (0.894x ✅, 7↑ 0↓)
No file size changes detected. |
Contributor
Benchmarks: TPC-H SF=1 on NVMEVerdict: No clear signal (low confidence) How to read Verdict and Engines
datafusion / vortex-file-compressed (1.078x ➖, 0↑ 7↓)
datafusion / vortex-compact (1.075x ➖, 0↑ 4↓)
datafusion / parquet (1.076x ➖, 0↑ 8↓)
datafusion / arrow (1.124x ❌, 0↑ 16↓)
duckdb / vortex-file-compressed (1.074x ➖, 0↑ 3↓)
duckdb / vortex-compact (1.064x ➖, 0↑ 4↓)
duckdb / parquet (1.055x ➖, 0↑ 4↓)
duckdb / duckdb (1.060x ➖, 0↑ 2↓)
File Size Changes (10 files changed, -0.1% overall, 5↑ 5↓)
Totals:
|
Contributor
Benchmarks: FineWeb NVMeVerdict: No clear signal (low confidence) How to read Verdict and Engines
datafusion / vortex-file-compressed (0.996x ➖, 1↑ 0↓)
datafusion / vortex-compact (0.996x ➖, 1↑ 1↓)
datafusion / parquet (1.012x ➖, 0↑ 0↓)
duckdb / vortex-file-compressed (0.996x ➖, 1↑ 0↓)
duckdb / vortex-compact (1.030x ➖, 0↑ 0↓)
duckdb / parquet (0.960x ➖, 1↑ 0↓)
File Size Changes (1 files changed, +0.1% overall, 1↑ 0↓)
Totals:
|
Contributor
Benchmarks: Statistical and Population GeneticsVerdict: No clear signal (low confidence) How to read Verdict and Engines
duckdb / vortex-file-compressed (0.997x ➖, 0↑ 0↓)
duckdb / vortex-compact (1.025x ➖, 0↑ 0↓)
duckdb / parquet (0.956x ➖, 1↑ 0↓)
File Size Changes (2 files changed, -0.1% overall, 0↑ 2↓)
Totals:
|
Contributor
Benchmarks: TPC-DS SF=1 on NVMEVerdict: No clear signal (environment too noisy confidence) How to read Verdict and Engines
datafusion / vortex-file-compressed (0.965x ➖, 18↑ 1↓)
datafusion / vortex-compact (0.985x ➖, 11↑ 2↓)
datafusion / parquet (1.051x ➖, 12↑ 47↓)
duckdb / vortex-file-compressed (0.985x ➖, 8↑ 3↓)
duckdb / vortex-compact (0.895x ✅, 46↑ 0↓)
duckdb / parquet (1.022x ➖, 0↑ 8↓)
duckdb / duckdb (0.961x ➖, 5↑ 2↓)
File Size Changes (23 files changed, -0.1% overall, 13↑ 10↓)
Totals:
|
Contributor
Benchmarks: FineWeb S3Verdict: No clear signal (environment too noisy confidence) How to read Verdict and Engines
datafusion / vortex-file-compressed (1.089x ➖, 0↑ 2↓)
datafusion / vortex-compact (1.066x ➖, 0↑ 0↓)
datafusion / parquet (1.010x ➖, 0↑ 1↓)
duckdb / vortex-file-compressed (0.987x ➖, 0↑ 0↓)
duckdb / vortex-compact (0.892x ➖, 1↑ 0↓)
duckdb / parquet (0.984x ➖, 0↑ 0↓)
|
danking
force-pushed
the
codex/take-slices-fsl
branch
from
f80606e to
99d0126
Compare
Contributor
Benchmarks: Clickbench Sorted on NVMEVerdict: No clear signal (low confidence) How to read Verdict and Engines
datafusion / vortex-file-compressed (1.000x ➖, 1↑ 1↓)
datafusion / parquet (1.048x ➖, 0↑ 2↓)
duckdb / vortex-file-compressed (1.011x ➖, 1↑ 1↓)
duckdb / parquet (0.984x ➖, 0↑ 0↓)
duckdb / duckdb (0.988x ➖, 0↑ 0↓)
File Size Changes (201 files changed, -0.4% overall, 77↑ 124↓)
Totals:
|
Contributor
Benchmarks: TPC-H SF=10 on NVMEVerdict: No clear signal (low confidence) How to read Verdict and Engines
datafusion / vortex-file-compressed (1.054x ➖, 0↑ 1↓)
datafusion / vortex-compact (1.042x ➖, 0↑ 1↓)
datafusion / parquet (1.038x ➖, 0↑ 0↓)
datafusion / arrow (1.052x ➖, 1↑ 3↓)
duckdb / vortex-file-compressed (1.060x ➖, 0↑ 0↓)
duckdb / vortex-compact (1.038x ➖, 0↑ 0↓)
duckdb / parquet (1.008x ➖, 0↑ 0↓)
duckdb / duckdb (1.029x ➖, 0↑ 0↓)
File Size Changes (34 files changed, -0.0% overall, 15↑ 19↓)
Totals:
|
Contributor
Benchmarks: Random AccessVortex (geomean): 0.996x ➖ How to read Verdict and Engines
unknown / unknown (1.007x ➖, 1↑ 2↓)
|
Contributor
Benchmarks: Clickbench on NVMEVerdict: No clear signal (low confidence) How to read Verdict and Engines
datafusion / vortex-file-compressed (1.003x ➖, 2↑ 0↓)
datafusion / parquet (1.005x ➖, 1↑ 1↓)
duckdb / vortex-file-compressed (0.983x ➖, 3↑ 1↓)
duckdb / parquet (0.974x ➖, 0↑ 0↓)
duckdb / duckdb (0.982x ➖, 1↑ 0↓)
File Size Changes (201 files changed, -0.3% overall, 98↑ 103↓)
Totals:
|
Contributor
Benchmarks: TPC-H SF=1 on S3Verdict: No clear signal (environment too noisy confidence) How to read Verdict and Engines
datafusion / vortex-file-compressed (0.833x ➖, 3↑ 0↓)
datafusion / vortex-compact (0.927x ➖, 0↑ 0↓)
datafusion / parquet (0.934x ➖, 1↑ 0↓)
duckdb / vortex-file-compressed (0.886x ➖, 0↑ 0↓)
duckdb / vortex-compact (0.922x ➖, 0↑ 0↓)
duckdb / parquet (0.924x ➖, 0↑ 0↓)
|
Contributor
Benchmarks: Appian on NVMEVerdict: No clear signal (low confidence) How to read Verdict and Engines
datafusion / vortex-file-compressed (1.028x ➖, 0↑ 2↓)
datafusion / parquet (1.022x ➖, 0↑ 1↓)
duckdb / vortex-file-compressed (1.056x ➖, 0↑ 2↓)
duckdb / parquet (1.074x ➖, 0↑ 1↓)
duckdb / duckdb (1.038x ➖, 0↑ 0↓)
File Size Changes (6 files changed, -0.0% overall, 2↑ 4↓)
Totals:
|
Contributor
Benchmarks: TPC-H SF=10 on S3Verdict: No clear signal (environment too noisy confidence) How to read Verdict and Engines
datafusion / vortex-file-compressed (0.976x ➖, 1↑ 1↓)
datafusion / vortex-compact (0.914x ➖, 0↑ 0↓)
datafusion / parquet (0.934x ➖, 1↑ 1↓)
duckdb / vortex-file-compressed (0.979x ➖, 0↑ 0↓)
duckdb / vortex-compact (1.028x ➖, 0↑ 0↓)
duckdb / parquet (0.901x ➖, 0↑ 0↓)
|
Signed-off-by: Daniel King <dan@spiraldb.com>
Signed-off-by: Daniel King <dan@spiraldb.com>
Signed-off-by: Daniel King <dan@spiraldb.com>
Signed-off-by: Daniel King <dan@spiraldb.com>
Signed-off-by: Daniel King <dan@spiraldb.com>
Signed-off-by: Daniel King <dan@spiraldb.com>
Signed-off-by: Daniel King <dan@spiraldb.com>
Signed-off-by: Daniel King <dan@spiraldb.com>
Signed-off-by: Daniel King <dan@spiraldb.com>
Signed-off-by: Daniel King <dan@spiraldb.com>
Signed-off-by: Daniel King <dan@spiraldb.com>
Signed-off-by: Daniel King <dan@spiraldb.com>
Signed-off-by: Daniel King <dan@spiraldb.com>
Signed-off-by: Daniel King <dan@spiraldb.com>
Signed-off-by: Daniel King <dan@spiraldb.com>
Signed-off-by: Daniel King <dan@spiraldb.com>
Signed-off-by: Daniel King <dan@spiraldb.com>
Signed-off-by: Daniel King <dan@spiraldb.com>
Signed-off-by: Daniel King <dan@spiraldb.com>
Signed-off-by: Daniel King <dan@spiraldb.com>
Signed-off-by: Daniel King <dan@spiraldb.com>
Signed-off-by: Daniel King <dan@spiraldb.com>
Signed-off-by: Daniel King <dan@spiraldb.com>
Signed-off-by: Daniel King <dan@spiraldb.com>
Signed-off-by: Daniel King <dan@spiraldb.com>
Signed-off-by: Daniel King <dan@spiraldb.com>
danking
force-pushed
the
codex/take-slices-fsl
branch
from
f502b6a to
37634a3
Compare
Contributor
Author
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
3 participants
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
The key issue here is that
fixed_size_list.take(indices)explodes the indices into one index per list element. For a fixed-size list of length 4096, this means the number of take indices expands by three orders of magnitude. Moreover, the take kernel must either copy each index separately or reconstruct the fact that these are actually contiguous ranges so it can use range copies.This PR now models that operation directly as a gather of contiguous runs:
starts[i]andlengths[i]describe each child run, and the output is the concatenation ofvalues[starts[i]..starts[i] + lengths[i]]. The runs may overlap, repeat, and appear in any order; this is a gather of runs, not a normal slice.For
FixedSizeList<100, u8>, this:now becomes run selectors over the child elements:
instead of expanding to:
This also gives
ListView -> Listpacking a direct fast path:ListViewrebuild now uses original offsets as starts and normalized sizes as lengths, so it can gather the referenced element runs without building a flat per-element take index buffer or falling back to per-list builders.Structnow pushes those run selectors into each field, andVarBinViewnow executes run gathers by copying contiguous view ranges while reusing the original data buffers.This is a table of results for
FixedSizeList<N, f16>:per-index / take_slicesCodex:
Summary
TakeSlicesArrayfrom aVec<Range<usize>>constructor to selector arrays: non-nullable unsignedstartsandlengths.FixedSizeListtake through contiguous child runs viatake_slices, leaving child encodings responsible for optimization.TakeSlicesExecutekernel that copies each requested run directly from the primitive slice.StructTakeSlicesReduceso run gathers push down into each field, matching the existingtakeshape.VarBinViewTakeSlicesExecuteso run gathers copy view ranges directly and reuse backing data buffers.take_slicesto rebuild non-zero-copyListViewArraylayouts into packed, zero-copy-to-list layouts.take_fslbenchmarks andtake_slicescoverage for selector arrays, overlapping/repeated runs, empty runs, nestedTakeSlices, nullable validity, generic fallback, primitive execution, Struct pushdown, VarBinView view-buffer execution, and FSL take.Correctness and Coverage
TakeSlicesvalidates public construction selectors before creating the lazy array.TakeSlicesexecution repeatedly slices the child and appends each run; specialized children can bypass that path.ListViewrebuild zeroes null-list lengths before gathering elements, preserving packed offsets without copying invalid-row payloads.Structpreserves struct-level validity while applying the same run selectors to every unmasked field.VarBinViewpreserves validity and shares the original data-bufferArcwhile copying only selected views.Validation
cargo +nightly fmt --allcargo test -p vortex-array take_slicescargo test -p vortex-array fixed_size_list::tests::takecargo test -p vortex-array listviewcargo check -p vortex-array --all-targetscargo clippy --all-targets --all-featuresgit diff --check