You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{{ message }}
Repository navigation
Commit 61ff28d
Browse filesBrowse the repository at this point in the historyBrowse files
perf(fastlanes): answer BitPacked compare and between from the bit width, between through the fused kernel (#10559)
## Summary
- Tracking Issue: #10396
BitPacked knows its bit width W, so a packed value is in `[0, 2^W - 1]`
and anything else is a patch. A predicate that is monotone in the value
and agrees at both ends of that range is decided for every packed value
without unpacking, which is the fast path from #8013 (ty
@joseph-isaacs), here extended to between and to patches. Vortex builds
for baseline x86-64 by default, where the between path also paid for two
compares per value through `stream_predicate`.
## Changes
- New `packed_range.rs`: the range of packed values for a bit width, and
a constant result with the patched positions fixed up by a dynamic
predicate, so it stays one instance per type. Without patches or nulls
the result is a `ConstantArray` and nothing is unpacked.
- `compare`: ordering operators are decided when the constant lies
outside the packed range; `Eq`/`NotEq` only when it is outside the range
or W = 0.
- `between`: the same rule on both endpoints, otherwise through the
fused `unpack_cmp` kernel with the bounds made inclusive and clamped to
the packed range, so one unsigned compare of the offset per value
regardless of strictness.
- Tests for both against the decoded reference, including patches,
nulls, W = 0 and full width.
## Benchmarks
Zen 5 laptop, divan medians (minimum over 3 alternating rounds), ratio =
develop / branch. Kernel-only counts from `perf stat` as the difference
of `--sample-size 400` and `200`.
| bench | default | target-cpu=native |
|---|---|---|
| `fast_{eq,lt}_out_of_range`, 64K | 8.8 to 11.8x | 4.9 to 5.6x |
| `fast_{eq,lt}_out_of_range`, 1K | 1.09 to 1.14x | 0.97 to 1.01x |
| `new_bp_prim_test_between` i16/i32 | 2.0 to 6.2x | 1.3 to 3.3x |
| `new_bp_prim_test_between` i64 | 1.3 to 1.55x | 1.26 to 1.97x |
| `new_alp_prim_test_between` | 1.24 to 3.7x | 1.18 to 2.5x |
| `baseline_{eq,lt}`, `bitpack_compare_sweep` | 0.97 to 1.03x | 0.99 to
1.03x |
| `new_raw_prim_test_between` (unaffected) | 1.01 to 1.03x | 0.99 to
1.01x |
The out-of-range compares now cost the same ~500 ns at any length, which
is the fixed `execute` overhead. Kernel instructions drop 2.67x for
those and 3.84x for bitpacked between; the in-range compare executes the
same instruction count as develop.
---------
Signed-off-by: mightsleep <[email protected]>
Signed-off-by: Robert Kruszewski <[email protected]>
0 commit comments