Skip to content

Commit b7bdb86

Browse files
authored
Merge branch 'main' into lexsort-small-limit-topk
2 parents c3fdb35 + 4b80f0e commit b7bdb86

36 files changed

Lines changed: 2959 additions & 1239 deletions

File tree

‎arrow-array/src/array/boolean_array.rs‎

Lines changed: 2 additions & 50 deletions
Original file line numberDiff line numberDiff line change
@@ -19,7 +19,6 @@ use crate::array::print_long_array;
1919
use crate::builder::BooleanBuilder;
2020
use crate::iterator::BooleanIter;
2121
use crate::{Array, ArrayAccessor, ArrayRef, Scalar};
22-
use arrow_buffer::bit_chunk_iterator::UnalignedBitChunk;
2322
use arrow_buffer::{BooleanBuffer, Buffer, MutableBuffer, NullBuffer, bit_util};
2423
use arrow_data::{ArrayData, ArrayDataBuilder};
2524
use arrow_schema::DataType;
@@ -157,16 +156,6 @@ impl BooleanArray {
157156
&self.values
158157
}
159158

160-
/// Block size for chunked fold operations in [`Self::has_true`] and [`Self::has_false`].
161-
/// Using `chunks_exact` with this size lets the compiler fully unroll the inner
162-
/// fold (no inner branch/loop), enabling short-circuit exits every N chunks.
163-
const CHUNK_FOLD_BLOCK_SIZE: usize = 16;
164-
165-
/// Returns an [`UnalignedBitChunk`] over this array's values.
166-
fn unaligned_bit_chunks(&self) -> UnalignedBitChunk<'_> {
167-
UnalignedBitChunk::new(self.values().values(), self.values().offset(), self.len())
168-
}
169-
170159
/// Returns the number of non null, true values within this array.
171160
/// If you only need to check if there is at least one true value, consider using `has_true()` which can short-circuit and be more efficient.
172161
pub fn true_count(&self) -> usize {
@@ -202,16 +191,7 @@ impl BooleanArray {
202191
let value_chunks = self.values().bit_chunks().iter_padded();
203192
null_chunks.zip(value_chunks).any(|(n, v)| (n & v) != 0)
204193
}
205-
None => {
206-
let bit_chunks = self.unaligned_bit_chunks();
207-
let chunks = bit_chunks.chunks();
208-
let mut exact = chunks.chunks_exact(Self::CHUNK_FOLD_BLOCK_SIZE);
209-
let found = bit_chunks.prefix().unwrap_or(0) != 0
210-
|| exact.any(|block| block.iter().fold(0u64, |acc, &c| acc | c) != 0);
211-
found
212-
|| exact.remainder().iter().any(|&c| c != 0)
213-
|| bit_chunks.suffix().unwrap_or(0) != 0
214-
}
194+
None => self.values().has_true(),
215195
}
216196
}
217197

@@ -228,35 +208,7 @@ impl BooleanArray {
228208
let value_chunks = self.values().bit_chunks().iter_padded();
229209
null_chunks.zip(value_chunks).any(|(n, v)| (n & !v) != 0)
230210
}
231-
None => {
232-
let bit_chunks = self.unaligned_bit_chunks();
233-
// UnalignedBitChunk zeros padding bits; fill them with 1s so
234-
// they don't appear as false values.
235-
let lead_mask = !((1u64 << bit_chunks.lead_padding()) - 1);
236-
let trail_mask = if bit_chunks.trailing_padding() == 0 {
237-
u64::MAX
238-
} else {
239-
(1u64 << (64 - bit_chunks.trailing_padding())) - 1
240-
};
241-
let (prefix_fill, suffix_fill) = match (bit_chunks.prefix(), bit_chunks.suffix()) {
242-
(Some(_), Some(_)) => (!lead_mask, !trail_mask),
243-
(Some(_), None) => (!lead_mask | !trail_mask, 0),
244-
(None, Some(_)) => (0, !trail_mask),
245-
(None, None) => (0, 0),
246-
};
247-
let chunks = bit_chunks.chunks();
248-
let mut exact = chunks.chunks_exact(Self::CHUNK_FOLD_BLOCK_SIZE);
249-
let found = bit_chunks
250-
.prefix()
251-
.is_some_and(|v| (v | prefix_fill) != u64::MAX)
252-
|| exact
253-
.any(|block| block.iter().fold(u64::MAX, |acc, &c| acc & c) != u64::MAX);
254-
found
255-
|| exact.remainder().iter().any(|&c| c != u64::MAX)
256-
|| bit_chunks
257-
.suffix()
258-
.is_some_and(|v| (v | suffix_fill) != u64::MAX)
259-
}
211+
None => self.values().has_false(),
260212
}
261213
}
262214

‎arrow-buffer/src/buffer/boolean.rs‎

Lines changed: 164 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -15,7 +15,7 @@
1515
// specific language governing permissions and limitations
1616
// under the License.
1717

18-
use crate::bit_chunk_iterator::BitChunks;
18+
use crate::bit_chunk_iterator::{BitChunks, UnalignedBitChunk};
1919
use crate::bit_iterator::{BitIndexIterator, BitIndexU32Iterator, BitIterator, BitSliceIterator};
2020
use crate::bit_util::read_u64;
2121
use crate::{
@@ -611,6 +611,11 @@ impl BooleanBuffer {
611611
self.into_iter()
612612
}
613613

614+
/// Returns an [`UnalignedBitChunk`] over this buffer's values.
615+
fn unaligned_bit_chunks(&self) -> UnalignedBitChunk<'_> {
616+
UnalignedBitChunk::new(self.values(), self.offset(), self.len())
617+
}
618+
614619
/// Returns an iterator over the set bit positions in this [`BooleanBuffer`]
615620
pub fn set_indices(&self) -> BitIndexIterator<'_> {
616621
BitIndexIterator::new(self.values(), self.bit_offset, self.bit_len)
@@ -625,6 +630,61 @@ impl BooleanBuffer {
625630
pub fn set_slices(&self) -> BitSliceIterator<'_> {
626631
BitSliceIterator::new(self.values(), self.bit_offset, self.bit_len)
627632
}
633+
634+
/// Block size for chunked fold operations in [`Self::has_true`] and [`Self::has_false`].
635+
/// Using `chunks_exact` with this size lets the compiler fully unroll the inner
636+
/// fold (no inner branch/loop), enabling short-circuit exits every N chunks.
637+
const CHUNK_FOLD_BLOCK_SIZE: usize = 16;
638+
639+
/// Returns whether there is at least one `true` value in this buffer.
640+
///
641+
/// This is more efficient than `count_set_bits() > 0` because it can short-circuit
642+
/// as soon as a `true` value is found, without counting all set bits.
643+
///
644+
/// Returns `false` for empty buffer.
645+
pub fn has_true(&self) -> bool {
646+
let bit_chunks = self.unaligned_bit_chunks();
647+
let chunks = bit_chunks.chunks();
648+
let mut exact = chunks.chunks_exact(Self::CHUNK_FOLD_BLOCK_SIZE);
649+
let found = bit_chunks.prefix().unwrap_or(0) != 0
650+
|| exact.any(|block| block.iter().fold(0u64, |acc, &c| acc | c) != 0);
651+
found || exact.remainder().iter().any(|&c| c != 0) || bit_chunks.suffix().unwrap_or(0) != 0
652+
}
653+
654+
/// Returns whether there is at least one `false` value in this buffer.
655+
///
656+
/// This is more efficient than `len() > count_set_bits()` because it can short-circuit
657+
/// as soon as a `false` value is found, without counting all set bits.
658+
///
659+
/// Returns `false` for empty buffer.
660+
pub fn has_false(&self) -> bool {
661+
let bit_chunks = self.unaligned_bit_chunks();
662+
// UnalignedBitChunk zeros padding bits; fill them with 1s so
663+
// they don't appear as false values.
664+
let lead_mask = !((1u64 << bit_chunks.lead_padding()) - 1);
665+
let trail_mask = if bit_chunks.trailing_padding() == 0 {
666+
u64::MAX
667+
} else {
668+
(1u64 << (64 - bit_chunks.trailing_padding())) - 1
669+
};
670+
let (prefix_fill, suffix_fill) = match (bit_chunks.prefix(), bit_chunks.suffix()) {
671+
(Some(_), Some(_)) => (!lead_mask, !trail_mask),
672+
(Some(_), None) => (!lead_mask | !trail_mask, 0),
673+
(None, Some(_)) => (0, !trail_mask),
674+
(None, None) => (0, 0),
675+
};
676+
let chunks = bit_chunks.chunks();
677+
let mut exact = chunks.chunks_exact(Self::CHUNK_FOLD_BLOCK_SIZE);
678+
let found = bit_chunks
679+
.prefix()
680+
.is_some_and(|v| (v | prefix_fill) != u64::MAX)
681+
|| exact.any(|block| block.iter().fold(u64::MAX, |acc, &c| acc & c) != u64::MAX);
682+
found
683+
|| exact.remainder().iter().any(|&c| c != u64::MAX)
684+
|| bit_chunks
685+
.suffix()
686+
.is_some_and(|v| (v | suffix_fill) != u64::MAX)
687+
}
628688
}
629689

630690
impl Not for &BooleanBuffer {
@@ -1245,4 +1305,107 @@ mod tests {
12451305
let buffer = BooleanBuffer::new_unset(100);
12461306
assert_eq!(buffer.clone().find_nth_set_bit_position(0, 1), 100);
12471307
}
1308+
1309+
#[test]
1310+
fn test_has_true_has_false_all_true() {
1311+
let arr = BooleanBuffer::from(vec![true, true, true]);
1312+
assert!(arr.has_true());
1313+
assert!(!arr.has_false());
1314+
}
1315+
1316+
#[test]
1317+
fn test_has_true_has_false_all_false() {
1318+
let arr = BooleanBuffer::from(vec![false, false, false]);
1319+
assert!(!arr.has_true());
1320+
assert!(arr.has_false());
1321+
}
1322+
1323+
#[test]
1324+
fn test_has_true_has_false_mixed() {
1325+
let arr = BooleanBuffer::from(vec![true, false, true]);
1326+
assert!(arr.has_true());
1327+
assert!(arr.has_false());
1328+
}
1329+
1330+
#[test]
1331+
fn test_has_true_has_false_empty() {
1332+
let arr = BooleanBuffer::from(Vec::<bool>::new());
1333+
assert!(!arr.has_true());
1334+
assert!(!arr.has_false());
1335+
}
1336+
1337+
#[test]
1338+
fn test_has_false_aligned_suffix_all_true() {
1339+
let arr = BooleanBuffer::from(vec![true; 129]);
1340+
assert!(arr.has_true());
1341+
assert!(!arr.has_false());
1342+
}
1343+
1344+
#[test]
1345+
fn test_has_false_non_aligned_all_true() {
1346+
// 65 elements: exercises the remainder path in has_false
1347+
let arr = BooleanBuffer::from(vec![true; 65]);
1348+
assert!(arr.has_true());
1349+
assert!(!arr.has_false());
1350+
}
1351+
1352+
#[test]
1353+
fn test_has_false_non_aligned_last_false() {
1354+
// 64 trues + 1 false: remainder path should find the false
1355+
let mut values = vec![true; 64];
1356+
values.push(false);
1357+
let arr = BooleanBuffer::from(values);
1358+
assert!(arr.has_true());
1359+
assert!(arr.has_false());
1360+
}
1361+
1362+
#[test]
1363+
fn test_has_false_exact_64_all_true() {
1364+
// Exactly 64 elements, no remainder
1365+
let arr = BooleanBuffer::from(vec![true; 64]);
1366+
assert!(arr.has_true());
1367+
assert!(!arr.has_false());
1368+
}
1369+
1370+
#[test]
1371+
fn test_has_true_has_false_unaligned_slices() {
1372+
let cases = [
1373+
(1, 129, true, false),
1374+
(3, 130, true, false),
1375+
(5, 65, true, false),
1376+
(7, 64, true, false),
1377+
];
1378+
1379+
let base = BooleanBuffer::from(vec![true; 300]);
1380+
1381+
for (offset, len, expected_has_true, expected_has_false) in cases {
1382+
let arr = base.slice(offset, len);
1383+
assert_eq!(
1384+
arr.has_true(),
1385+
expected_has_true,
1386+
"offset={offset} len={len}"
1387+
);
1388+
assert_eq!(
1389+
arr.has_false(),
1390+
expected_has_false,
1391+
"offset={offset} len={len}"
1392+
);
1393+
}
1394+
}
1395+
1396+
#[test]
1397+
fn test_has_true_has_false_exact_multiples_of_64() {
1398+
let cases = [
1399+
(64, true, false),
1400+
(128, true, false),
1401+
(192, true, false),
1402+
(256, true, false),
1403+
];
1404+
1405+
for (len, expected_has_true, expected_has_false) in cases {
1406+
let arr = BooleanBuffer::from(vec![true; len]);
1407+
assert_eq!(arr.has_true(), expected_has_true, "len={len}");
1408+
assert_eq!(arr.has_false(), expected_has_false, "len={len}");
1409+
}
1410+
}
12481411
}

‎arrow-cast/src/cast/decimal.rs‎

Lines changed: 14 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -531,7 +531,7 @@ where
531531

532532
/// Parses given string to specified decimal native (i128/i256) based on given
533533
/// scale. Returns an `Err` if it cannot parse given string.
534-
pub(crate) fn parse_string_to_decimal_native<T: DecimalType>(
534+
pub fn parse_string_to_decimal_native<T: DecimalType>(
535535
value_str: &str,
536536
scale: usize,
537537
) -> Result<T::Native, ArrowError>
@@ -777,15 +777,15 @@ where
777777
if cast_options.safe {
778778
array
779779
.unary_opt::<_, D>(|v| {
780-
D::Native::from_f64((mul * v.as_()).round())
780+
single_float_to_decimal::<D>(v.as_(), mul)
781781
.filter(|v| D::is_valid_decimal_precision(*v, precision))
782782
})
783783
.with_precision_and_scale(precision, scale)
784784
.map(|a| Arc::new(a) as ArrayRef)
785785
} else {
786786
array
787787
.try_unary::<_, D, _>(|v| {
788-
D::Native::from_f64((mul * v.as_()).round())
788+
single_float_to_decimal::<D>(v.as_(), mul)
789789
.ok_or_else(|| {
790790
ArrowError::CastError(format!(
791791
"Cannot cast to {}({}, {}). Overflowing on {:?}",
@@ -802,6 +802,17 @@ where
802802
}
803803
}
804804

805+
/// Cast a single floating point value to a decimal native with the given multiple.
806+
/// Returns `None` if the value cannot be represented with the requested precision.
807+
#[inline(always)]
808+
pub fn single_float_to_decimal<D>(input: f64, mul: f64) -> Option<D::Native>
809+
where
810+
D: DecimalType + ArrowPrimitiveType,
811+
<D as ArrowPrimitiveType>::Native: DecimalCast,
812+
{
813+
D::Native::from_f64((mul * input).round())
814+
}
815+
805816
pub(crate) fn cast_decimal_to_integer<D, T>(
806817
array: &dyn Array,
807818
base: D::Native,

‎arrow-cast/src/cast/mod.rs‎

Lines changed: 20 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -72,9 +72,25 @@ use arrow_schema::*;
7272
use arrow_select::take::take;
7373
use num_traits::{NumCast, ToPrimitive, cast::AsPrimitive};
7474

75-
pub use decimal::{DecimalCast, rescale_decimal};
75+
pub use decimal::{
76+
DecimalCast, parse_string_to_decimal_native, rescale_decimal, single_float_to_decimal,
77+
};
7678
pub use string::cast_single_string_to_boolean_default;
7779

80+
/// Lossy conversion from decimal to float.
81+
///
82+
/// Conversion is lossy and follows standard floating point semantics. Values
83+
/// that exceed the representable range become `INFINITY` or `-INFINITY` without
84+
/// returning an error.
85+
#[inline(always)]
86+
pub fn single_decimal_to_float_lossy<D, F>(f: &F, x: D::Native, scale: i32) -> f64
87+
where
88+
D: DecimalType,
89+
F: Fn(D::Native) -> f64,
90+
{
91+
f(x) / 10_f64.powi(scale)
92+
}
93+
7894
/// CastOptions provides a way to override the default cast behaviors
7995
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
8096
pub struct CastOptions<'a> {
@@ -2314,10 +2330,11 @@ where
23142330
Int32 => cast_decimal_to_integer::<D, Int32Type>(array, base, *scale, cast_options),
23152331
Int64 => cast_decimal_to_integer::<D, Int64Type>(array, base, *scale, cast_options),
23162332
Float32 => cast_decimal_to_float::<D, Float32Type, _>(array, |x| {
2317-
(as_float(x) / 10_f64.powi(*scale as i32)) as f32
2333+
single_decimal_to_float_lossy::<D, F>(&as_float, x, <i32 as From<i8>>::from(*scale))
2334+
as f32
23182335
}),
23192336
Float64 => cast_decimal_to_float::<D, Float64Type, _>(array, |x| {
2320-
as_float(x) / 10_f64.powi(*scale as i32)
2337+
single_decimal_to_float_lossy::<D, F>(&as_float, x, <i32 as From<i8>>::from(*scale))
23212338
}),
23222339
Utf8View => value_to_string_view(array, cast_options),
23232340
Utf8 => value_to_string::<i32>(array, cast_options),

0 commit comments

Comments
 (0)