Skip to content

Commit 9749d7d

Browse files
authored
GH-39798: [C++] Optimize Take for fixed-size types including nested fixed-size lists (#41297)
### Rationale for this change Introduce utilities for dealing with fixed-width types (including fixed-size lists of fixed-width types) generically. And use it for initial optimizations of `Take` and `Filter`. ### What changes are included in this PR? - [x] Introduce utilities for dealing with fixed-width types generically - [x] Use faster `Take` kernel on small power-of-2 byte widths of fixed-width types - [x] from `FSLTakeExec` (including FSLs of FSBs) - [x] from `FSBTakeExec` (done before this PR) - [x] ~Take on any fixed-width type~ (as a separate issue #41301) - [x] Use faster `Filter` kernel on both primitive and fixed-width types of any length - [x] from `FSLFilterExec` (including FSLs of FSBs) - [x] from `FSBFilterExec` (done before this PR) ### Are these changes tested? By existing and new tests. ### Are there any user-facing changes? Some functions added to the `arrow::util` namespace and documented inline. * GitHub Issue: #39798 Authored-by: Felipe Oliveira Carvalho <[email protected]> Signed-off-by: Felipe Oliveira Carvalho <[email protected]>
1 parent 71e38fc commit 9749d7d

11 files changed

Lines changed: 1171 additions & 72 deletions

‎cpp/src/arrow/CMakeLists.txt‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -501,6 +501,7 @@ set(ARROW_UTIL_SRCS
501501
util/decimal.cc
502502
util/delimiting.cc
503503
util/dict_util.cc
504+
util/fixed_width_internal.cc
504505
util/float16.cc
505506
util/formatting.cc
506507
util/future.cc

‎cpp/src/arrow/compute/kernels/vector_selection_filter_internal.cc‎

Lines changed: 17 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -40,6 +40,7 @@
4040
#include "arrow/util/bit_run_reader.h"
4141
#include "arrow/util/bit_util.h"
4242
#include "arrow/util/bitmap_ops.h"
43+
#include "arrow/util/fixed_width_internal.h"
4344

4445
namespace arrow {
4546

@@ -158,9 +159,11 @@ class PrimitiveFilterImpl {
158159
PrimitiveFilterImpl(const ArraySpan& values, const ArraySpan& filter,
159160
FilterOptions::NullSelectionBehavior null_selection,
160161
ArrayData* out_arr)
161-
: byte_width_(values.type->byte_width()),
162+
: byte_width_(util::FixedWidthInBytes(*values.type)),
162163
values_is_valid_(values.buffers[0].data),
163-
values_data_(values.buffers[1].data),
164+
// No offset applied for boolean because it's a bitmap
165+
values_data_(kIsBoolean ? values.buffers[1].data
166+
: util::OffsetPointerOfFixedWidthValues(values)),
164167
values_null_count_(values.null_count),
165168
values_offset_(values.offset),
166169
values_length_(values.length),
@@ -169,17 +172,13 @@ class PrimitiveFilterImpl {
169172
if constexpr (kByteWidth >= 0 && !kIsBoolean) {
170173
DCHECK_EQ(kByteWidth, byte_width_);
171174
}
172-
if constexpr (!kIsBoolean) {
173-
// No offset applied for boolean because it's a bitmap
174-
values_data_ += values.offset * byte_width();
175-
}
176175

176+
DCHECK_EQ(out_arr->offset, 0);
177177
if (out_arr->buffers[0] != nullptr) {
178178
// May be unallocated if neither filter nor values contain nulls
179179
out_is_valid_ = out_arr->buffers[0]->mutable_data();
180180
}
181-
out_data_ = out_arr->buffers[1]->mutable_data();
182-
DCHECK_EQ(out_arr->offset, 0);
181+
out_data_ = util::MutableFixedWidthValuesPointer(out_arr);
183182
out_length_ = out_arr->length;
184183
out_position_ = 0;
185184
}
@@ -416,7 +415,7 @@ class PrimitiveFilterImpl {
416415
out_position_ += length;
417416
}
418417

419-
constexpr int32_t byte_width() const {
418+
constexpr int64_t byte_width() const {
420419
if constexpr (kByteWidth >= 0) {
421420
return kByteWidth;
422421
} else {
@@ -425,7 +424,7 @@ class PrimitiveFilterImpl {
425424
}
426425

427426
private:
428-
int32_t byte_width_;
427+
int64_t byte_width_;
429428
const uint8_t* values_is_valid_;
430429
const uint8_t* values_data_;
431430
int64_t values_null_count_;
@@ -439,6 +438,8 @@ class PrimitiveFilterImpl {
439438
int64_t out_position_;
440439
};
441440

441+
} // namespace
442+
442443
Status PrimitiveFilterExec(KernelContext* ctx, const ExecSpan& batch, ExecResult* out) {
443444
const ArraySpan& values = batch[0].array;
444445
const ArraySpan& filter = batch[1].array;
@@ -468,9 +469,10 @@ Status PrimitiveFilterExec(KernelContext* ctx, const ExecSpan& batch, ExecResult
468469
// validity bitmap.
469470
const bool allocate_validity = values.null_count != 0 || !filter_null_count_is_zero;
470471

471-
const int bit_width = values.type->bit_width();
472-
RETURN_NOT_OK(PreallocatePrimitiveArrayData(ctx, output_length, bit_width,
473-
allocate_validity, out_arr));
472+
DCHECK(util::IsFixedWidthLike(values, /*force_null_count=*/false));
473+
const int64_t bit_width = util::FixedWidthInBits(*values.type);
474+
RETURN_NOT_OK(util::internal::PreallocateFixedWidthArrayData(
475+
ctx, output_length, /*source=*/values, allocate_validity, out_arr));
474476

475477
switch (bit_width) {
476478
case 1:
@@ -505,6 +507,8 @@ Status PrimitiveFilterExec(KernelContext* ctx, const ExecSpan& batch, ExecResult
505507
return Status::OK();
506508
}
507509

510+
namespace {
511+
508512
// ----------------------------------------------------------------------
509513
// Optimized filter for base binary types (32-bit and 64-bit)
510514

‎cpp/src/arrow/compute/kernels/vector_selection_internal.cc‎

Lines changed: 38 additions & 18 deletions
Original file line numberDiff line numberDiff line change
@@ -37,6 +37,7 @@
3737
#include "arrow/util/bit_block_counter.h"
3838
#include "arrow/util/bit_run_reader.h"
3939
#include "arrow/util/bit_util.h"
40+
#include "arrow/util/fixed_width_internal.h"
4041
#include "arrow/util/int_util.h"
4142
#include "arrow/util/logging.h"
4243
#include "arrow/util/ree_util.h"
@@ -65,24 +66,6 @@ void RegisterSelectionFunction(const std::string& name, FunctionDoc doc,
6566
DCHECK_OK(registry->AddFunction(std::move(func)));
6667
}
6768

68-
Status PreallocatePrimitiveArrayData(KernelContext* ctx, int64_t length, int bit_width,
69-
bool allocate_validity, ArrayData* out) {
70-
// Preallocate memory
71-
out->length = length;
72-
out->buffers.resize(2);
73-
74-
if (allocate_validity) {
75-
ARROW_ASSIGN_OR_RAISE(out->buffers[0], ctx->AllocateBitmap(length));
76-
}
77-
if (bit_width == 1) {
78-
ARROW_ASSIGN_OR_RAISE(out->buffers[1], ctx->AllocateBitmap(length));
79-
} else {
80-
ARROW_ASSIGN_OR_RAISE(out->buffers[1],
81-
ctx->Allocate(bit_util::BytesForBits(length * bit_width)));
82-
}
83-
return Status::OK();
84-
}
85-
8669
namespace {
8770

8871
/// \brief Iterate over a REE filter, emitting ranges of a plain values array that
@@ -909,6 +892,20 @@ Status LargeListFilterExec(KernelContext* ctx, const ExecSpan& batch, ExecResult
909892
}
910893

911894
Status FSLFilterExec(KernelContext* ctx, const ExecSpan& batch, ExecResult* out) {
895+
const ArraySpan& values = batch[0].array;
896+
897+
// If a FixedSizeList wraps a fixed-width type we can, in some cases, use
898+
// PrimitiveFilterExec for a fixed-size list array.
899+
if (util::IsFixedWidthLike(values,
900+
/*force_null_count=*/true,
901+
/*exclude_dictionary=*/true)) {
902+
const auto byte_width = util::FixedWidthInBytes(*values.type);
903+
// 0 is a valid byte width for FixedSizeList, but PrimitiveFilterExec
904+
// might not handle it correctly.
905+
if (byte_width > 0) {
906+
return PrimitiveFilterExec(ctx, batch, out);
907+
}
908+
}
912909
return FilterExec<FSLSelectionImpl>(ctx, batch, out);
913910
}
914911

@@ -968,6 +965,29 @@ Status LargeListTakeExec(KernelContext* ctx, const ExecSpan& batch, ExecResult*
968965
}
969966

970967
Status FSLTakeExec(KernelContext* ctx, const ExecSpan& batch, ExecResult* out) {
968+
const ArraySpan& values = batch[0].array;
969+
970+
// If a FixedSizeList wraps a fixed-width type we can, in some cases, use
971+
// PrimitiveTakeExec for a fixed-size list array.
972+
if (util::IsFixedWidthLike(values,
973+
/*force_null_count=*/true,
974+
/*exclude_dictionary=*/true)) {
975+
const auto byte_width = util::FixedWidthInBytes(*values.type);
976+
// Additionally, PrimitiveTakeExec is only implemented for specific byte widths.
977+
// TODO(GH-41301): Extend PrimitiveTakeExec for any fixed-width type.
978+
switch (byte_width) {
979+
case 1:
980+
case 2:
981+
case 4:
982+
case 8:
983+
case 16:
984+
case 32:
985+
return PrimitiveTakeExec(ctx, batch, out);
986+
default:
987+
break; // fallback to TakeExec<FSBSelectionImpl>
988+
}
989+
}
990+
971991
return TakeExec<FSLSelectionImpl>(ctx, batch, out);
972992
}
973993

‎cpp/src/arrow/compute/kernels/vector_selection_internal.h‎

Lines changed: 1 addition & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -45,12 +45,6 @@ void RegisterSelectionFunction(const std::string& name, FunctionDoc doc,
4545
const FunctionOptions* default_options,
4646
FunctionRegistry* registry);
4747

48-
/// \brief Allocate an ArrayData for a primitive array with a given length and bit width
49-
///
50-
/// \param[in] bit_width 1 or a multiple of 8
51-
Status PreallocatePrimitiveArrayData(KernelContext* ctx, int64_t length, int bit_width,
52-
bool allocate_validity, ArrayData* out);
53-
5448
/// \brief Callback type for VisitPlainxREEFilterOutputSegments.
5549
///
5650
/// position is the logical position in the values array relative to its offset.
@@ -70,6 +64,7 @@ void VisitPlainxREEFilterOutputSegments(
7064
FilterOptions::NullSelectionBehavior null_selection,
7165
const EmitREEFilterSegment& emit_segment);
7266

67+
Status PrimitiveFilterExec(KernelContext*, const ExecSpan&, ExecResult*);
7368
Status ListFilterExec(KernelContext*, const ExecSpan&, ExecResult*);
7469
Status LargeListFilterExec(KernelContext*, const ExecSpan&, ExecResult*);
7570
Status FSLFilterExec(KernelContext*, const ExecSpan&, ExecResult*);

‎cpp/src/arrow/compute/kernels/vector_selection_take_internal.cc‎

Lines changed: 23 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -37,6 +37,7 @@
3737
#include "arrow/util/bit_block_counter.h"
3838
#include "arrow/util/bit_run_reader.h"
3939
#include "arrow/util/bit_util.h"
40+
#include "arrow/util/fixed_width_internal.h"
4041
#include "arrow/util/int_util.h"
4142
#include "arrow/util/ree_util.h"
4243

@@ -323,7 +324,7 @@ namespace {
323324
using TakeState = OptionsWrapper<TakeOptions>;
324325

325326
// ----------------------------------------------------------------------
326-
// Implement optimized take for primitive types from boolean to 1/2/4/8-byte
327+
// Implement optimized take for primitive types from boolean to 1/2/4/8/16/32-byte
327328
// C-type based types. Use common implementation for every byte width and only
328329
// generate code for unsigned integer indices, since after boundschecking to
329330
// check for negative numbers in the indices we can safely reinterpret_cast
@@ -333,33 +334,36 @@ using TakeState = OptionsWrapper<TakeOptions>;
333334
/// use the logical Arrow type but rather the physical C type. This way we
334335
/// only generate one take function for each byte width.
335336
///
336-
/// This function assumes that the indices have been boundschecked.
337+
/// Also note that this function can also handle fixed-size-list arrays if
338+
/// they fit the criteria described in fixed_width_internal.h, so use the
339+
/// function defined in that file to access values and destination pointers
340+
/// and DO NOT ASSUME `values.type()` is a primitive type.
341+
///
342+
/// \pre the indices have been boundschecked
337343
template <typename IndexCType, typename ValueWidthConstant>
338344
struct PrimitiveTakeImpl {
339345
static constexpr int kValueWidth = ValueWidthConstant::value;
340346

341347
static void Exec(const ArraySpan& values, const ArraySpan& indices,
342348
ArrayData* out_arr) {
343-
DCHECK_EQ(values.type->byte_width(), kValueWidth);
344-
const auto* values_data =
345-
values.GetValues<uint8_t>(1, 0) + kValueWidth * values.offset;
349+
DCHECK_EQ(util::FixedWidthInBytes(*values.type), kValueWidth);
350+
const auto* values_data = util::OffsetPointerOfFixedWidthValues(values);
346351
const uint8_t* values_is_valid = values.buffers[0].data;
347352
auto values_offset = values.offset;
348353

349354
const auto* indices_data = indices.GetValues<IndexCType>(1);
350355
const uint8_t* indices_is_valid = indices.buffers[0].data;
351356
auto indices_offset = indices.offset;
352357

353-
auto out = out_arr->GetMutableValues<uint8_t>(1, 0) + kValueWidth * out_arr->offset;
358+
DCHECK_EQ(out_arr->offset, 0);
359+
auto* out = util::MutableFixedWidthValuesPointer(out_arr);
354360
auto out_is_valid = out_arr->buffers[0]->mutable_data();
355-
auto out_offset = out_arr->offset;
356-
DCHECK_EQ(out_offset, 0);
357361

358362
// If either the values or indices have nulls, we preemptively zero out the
359363
// out validity bitmap so that we don't have to use ClearBit in each
360364
// iteration for nulls.
361365
if (values.null_count != 0 || indices.null_count != 0) {
362-
bit_util::SetBitsTo(out_is_valid, out_offset, indices.length, false);
366+
bit_util::SetBitsTo(out_is_valid, 0, indices.length, false);
363367
}
364368

365369
auto WriteValue = [&](int64_t position) {
@@ -386,7 +390,7 @@ struct PrimitiveTakeImpl {
386390
valid_count += block.popcount;
387391
if (block.popcount == block.length) {
388392
// Fastest path: neither values nor index nulls
389-
bit_util::SetBitsTo(out_is_valid, out_offset + position, block.length, true);
393+
bit_util::SetBitsTo(out_is_valid, position, block.length, true);
390394
for (int64_t i = 0; i < block.length; ++i) {
391395
WriteValue(position);
392396
++position;
@@ -396,7 +400,7 @@ struct PrimitiveTakeImpl {
396400
for (int64_t i = 0; i < block.length; ++i) {
397401
if (bit_util::GetBit(indices_is_valid, indices_offset + position)) {
398402
// index is not null
399-
bit_util::SetBit(out_is_valid, out_offset + position);
403+
bit_util::SetBit(out_is_valid, position);
400404
WriteValue(position);
401405
} else {
402406
WriteZero(position);
@@ -416,7 +420,7 @@ struct PrimitiveTakeImpl {
416420
values_offset + indices_data[position])) {
417421
// value is not null
418422
WriteValue(position);
419-
bit_util::SetBit(out_is_valid, out_offset + position);
423+
bit_util::SetBit(out_is_valid, position);
420424
++valid_count;
421425
} else {
422426
WriteZero(position);
@@ -433,7 +437,7 @@ struct PrimitiveTakeImpl {
433437
values_offset + indices_data[position])) {
434438
// index is not null && value is not null
435439
WriteValue(position);
436-
bit_util::SetBit(out_is_valid, out_offset + position);
440+
bit_util::SetBit(out_is_valid, position);
437441
++valid_count;
438442
} else {
439443
WriteZero(position);
@@ -584,14 +588,17 @@ Status PrimitiveTakeExec(KernelContext* ctx, const ExecSpan& batch, ExecResult*
584588

585589
ArrayData* out_arr = out->array_data().get();
586590

587-
const int bit_width = values.type->bit_width();
591+
DCHECK(util::IsFixedWidthLike(values, /*force_null_count=*/false,
592+
/*exclude_dictionary=*/true));
593+
const int64_t bit_width = util::FixedWidthInBits(*values.type);
588594

589595
// TODO: When neither values nor indices contain nulls, we can skip
590596
// allocating the validity bitmap altogether and save time and space. A
591597
// streamlined PrimitiveTakeImpl would need to be written that skips all
592598
// interactions with the output validity bitmap, though.
593-
RETURN_NOT_OK(PreallocatePrimitiveArrayData(ctx, indices.length, bit_width,
594-
/*allocate_validity=*/true, out_arr));
599+
RETURN_NOT_OK(util::internal::PreallocateFixedWidthArrayData(
600+
ctx, indices.length, /*source=*/values,
601+
/*allocate_validity=*/true, out_arr));
595602
switch (bit_width) {
596603
case 1:
597604
TakeIndexDispatch<BooleanTakeImpl>(values, indices, out_arr);

0 commit comments

Comments
 (0)