Skip to content

Commit 3750d50

Browse files
Execute FoR iteratively (#10156)
Signed-off-by: Joseph Isaacs <[email protected]>
1 parent 900c1f2 commit 3750d50

5 files changed

Lines changed: 189 additions & 43 deletions

File tree

‎Cargo.lock‎

Lines changed: 1 addition & 0 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎encodings/fastlanes/Cargo.toml‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -34,6 +34,7 @@ vortex-session = { workspace = true }
3434

3535
[dev-dependencies]
3636
divan = { workspace = true }
37+
hegeltest = { workspace = true }
3738
itertools = { workspace = true }
3839
mimalloc = { workspace = true }
3940
rand = { workspace = true }

‎encodings/fastlanes/src/for/array/for_decompress.rs‎

Lines changed: 42 additions & 29 deletions
Original file line numberDiff line numberDiff line change
@@ -5,19 +5,20 @@ use std::iter;
55
use std::mem;
66
use std::mem::MaybeUninit;
77

8+
use fastlanes::BitPacking;
89
use fastlanes::FoR;
910
use itertools::Itertools;
1011
use num_traits::AsPrimitive;
1112
use num_traits::PrimInt;
1213
use num_traits::WrappingAdd;
1314
use vortex_array::ArrayView;
1415
use vortex_array::ExecutionCtx;
16+
use vortex_array::arrays::Primitive;
1517
use vortex_array::arrays::PrimitiveArray;
1618
use vortex_array::builders::PrimitiveBuilder;
1719
use vortex_array::builders::UninitRange;
1820
use vortex_array::dtype::NativePType;
1921
use vortex_array::dtype::PhysicalPType;
20-
use vortex_array::dtype::UnsignedPType;
2122
use vortex_array::match_each_integer_ptype;
2223
use vortex_array::match_each_unsigned_integer_ptype;
2324
use vortex_array::patches::Patches;
@@ -51,14 +52,11 @@ fn decompress_one_ref(
5152
ctx: &mut ExecutionCtx,
5253
) -> VortexResult<PrimitiveArray> {
5354
// Try to do fused unpack.
54-
if array.ptype().is_unsigned_int()
55-
&& let Some(bp) = array.encoded().as_opt::<BitPacked>()
56-
{
55+
if let Some(bp) = array.encoded().as_opt::<BitPacked>() {
5756
return fused_decompress(array, bp, ctx);
5857
}
5958

60-
// Otherwise execute array and add references.
61-
add_reference(array, reference, ctx)
59+
add_reference(array, reference)
6260
}
6361

6462
/// Unpack a BitPacked child and add the constant reference in one pass.
@@ -67,12 +65,14 @@ pub(crate) fn fused_decompress(
6765
bp: ArrayView<'_, BitPacked>,
6866
ctx: &mut ExecutionCtx,
6967
) -> VortexResult<PrimitiveArray> {
70-
match_each_unsigned_integer_ptype!(for_.ptype(), |T| {
68+
match_each_integer_ptype!(for_.ptype(), |T| {
7169
fused_decompress_typed::<T>(for_, bp, ctx)
7270
})
7371
}
7472

75-
fn fused_decompress_typed<T: PhysicalPType<Physical = T> + UnsignedPType + FoR + WrappingAdd>(
73+
fn fused_decompress_typed<
74+
T: PhysicalPType<Physical: FoR + BitPacking> + AsPrimitive<T::Physical> + WrappingAdd,
75+
>(
7676
for_: &FoRArray,
7777
bp: ArrayView<'_, BitPacked>,
7878
ctx: &mut ExecutionCtx,
@@ -88,23 +88,17 @@ fn fused_decompress_typed<T: PhysicalPType<Physical = T> + UnsignedPType + FoR +
8888
}
8989

9090
/// Decode `encoded`, then add `reference` to every value.
91-
fn add_reference(
92-
array: &FoRArray,
93-
reference: &Scalar,
94-
ctx: &mut ExecutionCtx,
95-
) -> VortexResult<PrimitiveArray> {
91+
fn add_reference(array: &FoRArray, reference: &Scalar) -> VortexResult<PrimitiveArray> {
9692
match_each_integer_ptype!(array.ptype(), |T| {
97-
add_reference_typed::<T>(array, reference, ctx)
93+
add_reference_typed::<T>(array, reference)
9894
})
9995
}
10096

10197
fn add_reference_typed<T: NativePType + WrappingAdd + PrimInt>(
10298
array: &FoRArray,
10399
reference: &Scalar,
104-
ctx: &mut ExecutionCtx,
105100
) -> VortexResult<PrimitiveArray> {
106-
// TODO(ngates): Do we need this to be into_encoded() somehow?
107-
let encoded = array.encoded().clone().execute::<PrimitiveArray>(ctx)?;
101+
let encoded = array.encoded().as_::<Primitive>().into_owned();
108102
let min = reference
109103
.as_primitive()
110104
.typed_value::<T>()
@@ -131,8 +125,7 @@ fn decompress_primitive<T: NativePType + WrappingAdd + PrimInt>(
131125
/// Decompress an array whose chunks have different references.
132126
fn decompress_many_refs(array: &FoRArray, ctx: &mut ExecutionCtx) -> VortexResult<PrimitiveArray> {
133127
// Try to do fused unpack. BitPacked chunks line up with FoR chunks when the offsets match.
134-
if array.ptype().is_unsigned_int()
135-
&& let Some(bp) = array.encoded().as_opt::<BitPacked>()
128+
if let Some(bp) = array.encoded().as_opt::<BitPacked>()
136129
&& bp.offset() == array.offset()
137130
{
138131
return fused_decompress_many_refs(array, bp, ctx);
@@ -150,12 +143,12 @@ fn add_references_typed<T: NativePType + WrappingAdd + PrimInt>(
150143
array: &FoRArray,
151144
ctx: &mut ExecutionCtx,
152145
) -> VortexResult<PrimitiveArray> {
153-
let encoded = array.encoded().clone().execute::<PrimitiveArray>(ctx)?;
146+
let encoded = array.encoded().as_::<Primitive>().into_owned();
154147
if encoded.is_empty() {
155148
return Ok(encoded);
156149
}
157150
let validity = encoded.validity()?;
158-
let references = array.references().clone().execute::<PrimitiveArray>(ctx)?;
151+
let references = array.references().as_::<Primitive>().into_owned();
159152
let references = references.as_slice::<T>();
160153

161154
// The first chunk may be partial when the array was sliced.
@@ -222,19 +215,19 @@ fn fused_decompress_many_refs(
222215
bp: ArrayView<'_, BitPacked>,
223216
ctx: &mut ExecutionCtx,
224217
) -> VortexResult<PrimitiveArray> {
225-
match_each_unsigned_integer_ptype!(for_.ptype(), |T| {
218+
match_each_integer_ptype!(for_.ptype(), |T| {
226219
fused_decompress_many_refs_typed::<T>(for_, bp, ctx)
227220
})
228221
}
229222

230223
fn fused_decompress_many_refs_typed<
231-
T: PhysicalPType<Physical = T> + UnsignedPType + FoR + WrappingAdd,
224+
T: PhysicalPType<Physical: FoR + BitPacking> + AsPrimitive<T::Physical> + WrappingAdd,
232225
>(
233226
for_: &FoRArray,
234227
bp: ArrayView<'_, BitPacked>,
235228
ctx: &mut ExecutionCtx,
236229
) -> VortexResult<PrimitiveArray> {
237-
let references = for_.references().clone().execute::<PrimitiveArray>(ctx)?;
230+
let references = for_.references().as_::<Primitive>().into_owned();
238231
let references = references.as_slice::<T>();
239232
fused_unpack(for_, bp, |chunk| references[chunk], ctx)
240233
}
@@ -243,7 +236,9 @@ fn fused_decompress_many_refs_typed<
243236
///
244237
/// `chunk_reference` maps the index of a chunk, counted from the first chunk of `bp`, to its
245238
/// reference.
246-
fn fused_unpack<T: PhysicalPType<Physical = T> + UnsignedPType + FoR + WrappingAdd>(
239+
fn fused_unpack<
240+
T: PhysicalPType<Physical: FoR + BitPacking> + AsPrimitive<T::Physical> + WrappingAdd,
241+
>(
247242
for_: &FoRArray,
248243
bp: ArrayView<'_, BitPacked>,
249244
chunk_reference: impl Fn(usize) -> T,
@@ -280,21 +275,27 @@ fn fused_unpack<T: PhysicalPType<Physical = T> + UnsignedPType + FoR + WrappingA
280275
///
281276
/// Full chunks unpack straight into `output`. A partial first or last chunk unpacks into a scratch
282277
/// chunk, and only its values in `output` are copied over.
283-
fn unpack_chunks<T: PhysicalPType<Physical = T> + UnsignedPType + FoR>(
278+
fn unpack_chunks<
279+
T: PhysicalPType<Physical: FoR + BitPacking> + AsPrimitive<T::Physical> + WrappingAdd,
280+
>(
284281
bp: ArrayView<'_, BitPacked>,
285282
chunk_reference: impl Fn(usize) -> T,
286283
output: &mut [MaybeUninit<T>],
287284
) -> VortexResult<()> {
288285
let offset = usize::from(bp.offset());
289286
let bit_width = bp.bit_width() as usize;
290-
let mut scratch = [const { MaybeUninit::<T>::uninit() }; FL_CHUNK_SIZE];
287+
// SAFETY: `T::Physical` is `T` with the same size and alignment, and the unpack is the same
288+
// wrapping addition in two's complement whichever signedness `T` has.
289+
let output =
290+
unsafe { mem::transmute::<&mut [MaybeUninit<T>], &mut [MaybeUninit<T::Physical>]>(output) };
291+
let mut scratch = [const { MaybeUninit::<T::Physical>::uninit() }; FL_CHUNK_SIZE];
291292
for_each_packed_chunk::<T, _>(
292-
bp.packed_slice::<T>(),
293+
bp.packed_slice::<T::Physical>(),
293294
bit_width,
294295
offset,
295296
bp.len(),
296297
|packed, range| {
297-
let reference = chunk_reference(range.start / FL_CHUNK_SIZE);
298+
let reference = chunk_reference(range.start / FL_CHUNK_SIZE).as_();
298299
// `range` counts from the start of the first chunk, and the output starts at `offset`.
299300
let skip = offset.saturating_sub(range.start);
300301
let dst = &mut output[range.start + skip - offset..range.end - offset];
@@ -414,4 +415,16 @@ mod tests {
414415
assert_arrays_eq!(decompressed, expect, &mut ctx);
415416
Ok(())
416417
}
418+
419+
#[test]
420+
fn test_decompress_fused_signed_patches() -> VortexResult<()> {
421+
let mut ctx = SESSION.create_execution_ctx();
422+
let expect = PrimitiveArray::from_iter((0i64..1024).map(|x| x % 7 - 1_000_000));
423+
let array = PrimitiveArray::from_iter((0i64..1024).map(|x| x % 7));
424+
let bp = BitPackedData::encode(&array.into_array(), 2, &mut ctx)?;
425+
let compressed = FoR::try_new(bp.clone().into_array(), (-1_000_000i64).into())?;
426+
let decompressed = fused_decompress(&compressed, bp.as_view(), &mut ctx)?;
427+
assert_arrays_eq!(decompressed, expect, &mut ctx);
428+
Ok(())
429+
}
417430
}

0 commit comments

Comments
 (0)