Skip to content

Commit 4f89097

Browse files
authored
GH-41301: [C++] Extract the kernel loops used for PrimitiveTakeExec and generalize to any fixed-width type (#41373)
### Rationale for this change I want to instantiate this primitive operation in other scenarios (e.g. the optimized version of `Take` that handles chunked arrays) and extend the sub-classes of `GatherCRTP` with different member functions that re-use the `WriteValue` function generically (any fixed-width type and even bit-wide booleans). When taking these improvements to `Filter` I will also re-use the "gather" concept and parameterize it by bitmaps/boolean-arrays instead of selection vectors (`indices`) like `take` does. So gather is not a "renaming of take" but rather a generalization of `take` and `filter` do in Arrow with different representations of what should be gathered from the `values` array. ### What changes are included in this PR? - Introduce the Gather class helper to delegate fixed-width memory gathering: both static and dynamically sized (size known at compile time or size known at runtime) - Specialized `Take` implementation for values/indices without nulls - Fold the Boolean, Primitives, and Fixed-Width Binary implementation of `Take` into a single one - Skip validity bitmap allocation when inputs (values and indices) have no nulls ### Are these changes tested? - Existing tests - New test assertions that check that `Take` guarantees null values are zeroed out * GitHub Issue: #41301 Authored-by: Felipe Oliveira Carvalho <[email protected]> Signed-off-by: Felipe Oliveira Carvalho <[email protected]>
1 parent 036fca0 commit 4f89097

5 files changed

Lines changed: 435 additions & 334 deletions

File tree

Lines changed: 306 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,306 @@
1+
// Licensed to the Apache Software Foundation (ASF) under one
2+
// or more contributor license agreements. See the NOTICE file
3+
// distributed with this work for additional information
4+
// regarding copyright ownership. The ASF licenses this file
5+
// to you under the Apache License, Version 2.0 (the
6+
// "License"); you may not use this file except in compliance
7+
// with the License. You may obtain a copy of the License at
8+
//
9+
// http://www.apache.org/licenses/LICENSE-2.0
10+
//
11+
// Unless required by applicable law or agreed to in writing,
12+
// software distributed under the License is distributed on an
13+
// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
14+
// KIND, either express or implied. See the License for the
15+
// specific language governing permissions and limitations
16+
// under the License.
17+
18+
#pragma once
19+
20+
#include <cassert>
21+
#include <cstddef>
22+
#include <cstdint>
23+
24+
#include "arrow/array/data.h"
25+
#include "arrow/util/bit_block_counter.h"
26+
#include "arrow/util/bit_run_reader.h"
27+
#include "arrow/util/bit_util.h"
28+
#include "arrow/util/bitmap_ops.h"
29+
#include "arrow/util/macros.h"
30+
31+
// Implementation helpers for kernels that need to load/gather fixed-width
32+
// data from multiple, arbitrary indices.
33+
//
34+
// https://en.wikipedia.org/wiki/Gather/scatter_(vector_addressing)
35+
36+
namespace arrow::internal {
37+
38+
// CRTP [1] base class for Gather that provides a gathering loop in terms of
39+
// Write*() methods that must be implemented by the derived class.
40+
//
41+
// [1] https://en.wikipedia.org/wiki/Curiously_recurring_template_pattern
42+
template <class GatherImpl>
43+
class GatherBaseCRTP {
44+
public:
45+
// Output offset is not supported by Gather and idx is supposed to have offset
46+
// pre-applied. idx_validity parameters on functions can use the offset they
47+
// carry to read the validity bitmap as bitmaps can't have pre-applied offsets
48+
// (they might not align to byte boundaries).
49+
50+
GatherBaseCRTP() = default;
51+
ARROW_DISALLOW_COPY_AND_ASSIGN(GatherBaseCRTP);
52+
ARROW_DEFAULT_MOVE_AND_ASSIGN(GatherBaseCRTP);
53+
54+
protected:
55+
ARROW_FORCE_INLINE int64_t ExecuteNoNulls(int64_t idx_length) {
56+
auto* self = static_cast<GatherImpl*>(this);
57+
for (int64_t position = 0; position < idx_length; position++) {
58+
self->WriteValue(position);
59+
}
60+
return idx_length;
61+
}
62+
63+
// See derived Gather classes below for the meaning of the parameters, pre and
64+
// post-conditions.
65+
//
66+
// src_validity is not necessarily the source of the values that are being
67+
// gathered (e.g. the source could be a nested fixed-size list array and the
68+
// values being gathered are from the innermost buffer), so the ArraySpan is
69+
// used solely to check for nulls in the source values and nothing else.
70+
//
71+
// idx_length is the number of elements in idx and consequently the number of
72+
// bits that might be written to out_is_valid. Member `Write*()` functions will be
73+
// called with positions from 0 to idx_length - 1.
74+
//
75+
// If `kOutputIsZeroInitialized` is true, then `WriteZero()` or `WriteZeroSegment()`
76+
// doesn't have to be called for resulting null positions. A position is
77+
// considered null if either the index or the source value is null at that
78+
// position.
79+
template <bool kOutputIsZeroInitialized, typename IndexCType>
80+
ARROW_FORCE_INLINE int64_t ExecuteWithNulls(const ArraySpan& src_validity,
81+
int64_t idx_length, const IndexCType* idx,
82+
const ArraySpan& idx_validity,
83+
uint8_t* out_is_valid) {
84+
auto* self = static_cast<GatherImpl*>(this);
85+
OptionalBitBlockCounter indices_bit_counter(idx_validity.buffers[0].data,
86+
idx_validity.offset, idx_length);
87+
int64_t position = 0;
88+
int64_t valid_count = 0;
89+
while (position < idx_length) {
90+
BitBlockCount block = indices_bit_counter.NextBlock();
91+
if (!src_validity.MayHaveNulls()) {
92+
// Source values are never null, so things are easier
93+
valid_count += block.popcount;
94+
if (block.popcount == block.length) {
95+
// Fastest path: neither source values nor index nulls
96+
bit_util::SetBitsTo(out_is_valid, position, block.length, true);
97+
for (int64_t i = 0; i < block.length; ++i) {
98+
self->WriteValue(position);
99+
++position;
100+
}
101+
} else if (block.popcount > 0) {
102+
// Slow path: some indices but not all are null
103+
for (int64_t i = 0; i < block.length; ++i) {
104+
ARROW_COMPILER_ASSUME(idx_validity.buffers[0].data != nullptr);
105+
if (idx_validity.IsValid(position)) {
106+
// index is not null
107+
bit_util::SetBit(out_is_valid, position);
108+
self->WriteValue(position);
109+
} else if constexpr (!kOutputIsZeroInitialized) {
110+
self->WriteZero(position);
111+
}
112+
++position;
113+
}
114+
} else {
115+
self->WriteZeroSegment(position, block.length);
116+
position += block.length;
117+
}
118+
} else {
119+
// Source values may be null, so we must do random access into src_validity
120+
if (block.popcount == block.length) {
121+
// Faster path: indices are not null but source values may be
122+
for (int64_t i = 0; i < block.length; ++i) {
123+
ARROW_COMPILER_ASSUME(src_validity.buffers[0].data != nullptr);
124+
if (src_validity.IsValid(idx[position])) {
125+
// value is not null
126+
self->WriteValue(position);
127+
bit_util::SetBit(out_is_valid, position);
128+
++valid_count;
129+
} else if constexpr (!kOutputIsZeroInitialized) {
130+
self->WriteZero(position);
131+
}
132+
++position;
133+
}
134+
} else if (block.popcount > 0) {
135+
// Slow path: some but not all indices are null. Since we are doing
136+
// random access in general we have to check the value nullness one by
137+
// one.
138+
for (int64_t i = 0; i < block.length; ++i) {
139+
ARROW_COMPILER_ASSUME(src_validity.buffers[0].data != nullptr);
140+
ARROW_COMPILER_ASSUME(idx_validity.buffers[0].data != nullptr);
141+
if (idx_validity.IsValid(position) && src_validity.IsValid(idx[position])) {
142+
// index is not null && value is not null
143+
self->WriteValue(position);
144+
bit_util::SetBit(out_is_valid, position);
145+
++valid_count;
146+
} else if constexpr (!kOutputIsZeroInitialized) {
147+
self->WriteZero(position);
148+
}
149+
++position;
150+
}
151+
} else {
152+
if constexpr (!kOutputIsZeroInitialized) {
153+
self->WriteZeroSegment(position, block.length);
154+
}
155+
position += block.length;
156+
}
157+
}
158+
}
159+
return valid_count;
160+
}
161+
};
162+
163+
// A gather primitive for primitive fixed-width types with a integral byte width. If
164+
// `kWithFactor` is true, the actual width is a runtime multiple of `kValueWidthInbits`
165+
// (this can be useful for fixed-size list inputs and other input types with unusual byte
166+
// widths that don't deserve value specialization).
167+
template <int kValueWidthInBits, typename IndexCType, bool kWithFactor>
168+
class Gather : public GatherBaseCRTP<Gather<kValueWidthInBits, IndexCType, kWithFactor>> {
169+
public:
170+
static_assert(kValueWidthInBits >= 0 && kValueWidthInBits % 8 == 0);
171+
static constexpr int kValueWidth = kValueWidthInBits / 8;
172+
173+
private:
174+
const int64_t src_length_; // number of elements of kValueWidth bytes in src_
175+
const uint8_t* src_;
176+
const int64_t idx_length_; // number IndexCType elements in idx_
177+
const IndexCType* idx_;
178+
uint8_t* out_;
179+
int64_t factor_;
180+
181+
public:
182+
void WriteValue(int64_t position) {
183+
if constexpr (kWithFactor) {
184+
const int64_t scaled_factor = kValueWidth * factor_;
185+
memcpy(out_ + position * scaled_factor, src_ + idx_[position] * scaled_factor,
186+
scaled_factor);
187+
} else {
188+
memcpy(out_ + position * kValueWidth, src_ + idx_[position] * kValueWidth,
189+
kValueWidth);
190+
}
191+
}
192+
193+
void WriteZero(int64_t position) {
194+
if constexpr (kWithFactor) {
195+
const int64_t scaled_factor = kValueWidth * factor_;
196+
memset(out_ + position * scaled_factor, 0, scaled_factor);
197+
} else {
198+
memset(out_ + position * kValueWidth, 0, kValueWidth);
199+
}
200+
}
201+
202+
void WriteZeroSegment(int64_t position, int64_t length) {
203+
if constexpr (kWithFactor) {
204+
const int64_t scaled_factor = kValueWidth * factor_;
205+
memset(out_ + position * scaled_factor, 0, length * scaled_factor);
206+
} else {
207+
memset(out_ + position * kValueWidth, 0, length * kValueWidth);
208+
}
209+
}
210+
211+
public:
212+
Gather(int64_t src_length, const uint8_t* src, int64_t zero_src_offset,
213+
int64_t idx_length, const IndexCType* idx, uint8_t* out, int64_t factor)
214+
: src_length_(src_length),
215+
src_(src),
216+
idx_length_(idx_length),
217+
idx_(idx),
218+
out_(out),
219+
factor_(factor) {
220+
assert(zero_src_offset == 0);
221+
assert(src && idx && out);
222+
assert((kWithFactor || factor == 1) &&
223+
"When kWithFactor is false, the factor is assumed to be 1 at compile time");
224+
}
225+
226+
ARROW_FORCE_INLINE int64_t Execute() { return this->ExecuteNoNulls(idx_length_); }
227+
228+
/// \pre If kOutputIsZeroInitialized, then this->out_ has to be zero initialized.
229+
/// \pre Bits in out_is_valid have to always be zero initialized.
230+
/// \post The bits for the valid elements (and only those) are set in out_is_valid.
231+
/// \post If !kOutputIsZeroInitialized, then positions in this->_out containing null
232+
/// elements have 0s written to them. This might be less efficient than
233+
/// zero-initializing first and calling this->Execute() afterwards.
234+
/// \return The number of valid elements in out.
235+
template <bool kOutputIsZeroInitialized = false>
236+
ARROW_FORCE_INLINE int64_t Execute(const ArraySpan& src_validity,
237+
const ArraySpan& idx_validity,
238+
uint8_t* out_is_valid) {
239+
assert(src_length_ == src_validity.length);
240+
assert(idx_length_ == idx_validity.length);
241+
assert(out_is_valid);
242+
return this->template ExecuteWithNulls<kOutputIsZeroInitialized>(
243+
src_validity, idx_length_, idx_, idx_validity, out_is_valid);
244+
}
245+
};
246+
247+
// A gather primitive for boolean inputs. Unlike its counterpart above,
248+
// this does not support passing a non-trivial factor parameter.
249+
template <typename IndexCType>
250+
class Gather</*kValueWidthInBits=*/1, IndexCType, /*kWithFactor=*/false>
251+
: public GatherBaseCRTP<Gather<1, IndexCType, false>> {
252+
private:
253+
const int64_t src_length_; // number of elements of bits bytes in src_ after offset
254+
const uint8_t* src_; // the boolean array data buffer in bits
255+
const int64_t src_offset_; // offset in bits
256+
const int64_t idx_length_; // number IndexCType elements in idx_
257+
const IndexCType* idx_;
258+
uint8_t* out_; // output boolean array data buffer in bits
259+
260+
public:
261+
Gather(int64_t src_length, const uint8_t* src, int64_t src_offset, int64_t idx_length,
262+
const IndexCType* idx, uint8_t* out, int64_t factor)
263+
: src_length_(src_length),
264+
src_(src),
265+
src_offset_(src_offset),
266+
idx_length_(idx_length),
267+
idx_(idx),
268+
out_(out) {
269+
assert(src && idx && out);
270+
assert(factor == 1 &&
271+
"factor != 1 is not supported when Gather is used to gather bits/booleans");
272+
}
273+
274+
void WriteValue(int64_t position) {
275+
bit_util::SetBitTo(out_, position,
276+
bit_util::GetBit(src_, src_offset_ + idx_[position]));
277+
}
278+
279+
void WriteZero(int64_t position) { bit_util::ClearBit(out_, position); }
280+
281+
void WriteZeroSegment(int64_t position, int64_t block_length) {
282+
bit_util::SetBitsTo(out_, position, block_length, false);
283+
}
284+
285+
ARROW_FORCE_INLINE int64_t Execute() { return this->ExecuteNoNulls(idx_length_); }
286+
287+
/// \pre If kOutputIsZeroInitialized, then this->out_ has to be zero initialized.
288+
/// \pre Bits in out_is_valid have to always be zero initialized.
289+
/// \post The bits for the valid elements (and only those) are set in out_is_valid.
290+
/// \post If !kOutputIsZeroInitialized, then positions in this->_out containing null
291+
/// elements have 0s written to them. This might be less efficient than
292+
/// zero-initializing first and calling this->Execute() afterwards.
293+
/// \return The number of valid elements in out.
294+
template <bool kOutputIsZeroInitialized = false>
295+
ARROW_FORCE_INLINE int64_t Execute(const ArraySpan& src_validity,
296+
const ArraySpan& idx_validity,
297+
uint8_t* out_is_valid) {
298+
assert(src_length_ == src_validity.length);
299+
assert(idx_length_ == idx_validity.length);
300+
assert(out_is_valid);
301+
return this->template ExecuteWithNulls<kOutputIsZeroInitialized>(
302+
src_validity, idx_length_, idx_, idx_validity, out_is_valid);
303+
}
304+
};
305+
306+
} // namespace arrow::internal

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

Lines changed: 2 additions & 66 deletions
Original file line numberDiff line numberDiff line change
@@ -547,39 +547,6 @@ struct VarBinarySelectionImpl : public Selection<VarBinarySelectionImpl<Type>, T
547547
}
548548
};
549549

550-
struct FSBSelectionImpl : public Selection<FSBSelectionImpl, FixedSizeBinaryType> {
551-
using Base = Selection<FSBSelectionImpl, FixedSizeBinaryType>;
552-
LIFT_BASE_MEMBERS();
553-
554-
TypedBufferBuilder<uint8_t> data_builder;
555-
556-
FSBSelectionImpl(KernelContext* ctx, const ExecSpan& batch, int64_t output_length,
557-
ExecResult* out)
558-
: Base(ctx, batch, output_length, out), data_builder(ctx->memory_pool()) {}
559-
560-
template <typename Adapter>
561-
Status GenerateOutput() {
562-
FixedSizeBinaryArray typed_values(this->values.ToArrayData());
563-
int32_t value_size = typed_values.byte_width();
564-
565-
RETURN_NOT_OK(data_builder.Reserve(value_size * output_length));
566-
Adapter adapter(this);
567-
return adapter.Generate(
568-
[&](int64_t index) {
569-
auto val = typed_values.GetView(index);
570-
data_builder.UnsafeAppend(reinterpret_cast<const uint8_t*>(val.data()),
571-
value_size);
572-
return Status::OK();
573-
},
574-
[&]() {
575-
data_builder.UnsafeAppend(value_size, static_cast<uint8_t>(0x00));
576-
return Status::OK();
577-
});
578-
}
579-
580-
Status Finish() override { return data_builder.Finish(&out->buffers[1]); }
581-
};
582-
583550
template <typename Type>
584551
struct ListSelectionImpl : public Selection<ListSelectionImpl<Type>, Type> {
585552
using offset_type = typename Type::offset_type;
@@ -939,23 +906,6 @@ Status LargeVarBinaryTakeExec(KernelContext* ctx, const ExecSpan& batch,
939906
return TakeExec<VarBinarySelectionImpl<LargeBinaryType>>(ctx, batch, out);
940907
}
941908

942-
Status FSBTakeExec(KernelContext* ctx, const ExecSpan& batch, ExecResult* out) {
943-
const ArraySpan& values = batch[0].array;
944-
const auto byte_width = values.type->byte_width();
945-
// Use primitive Take implementation (presumably faster) for some byte widths
946-
switch (byte_width) {
947-
case 1:
948-
case 2:
949-
case 4:
950-
case 8:
951-
case 16:
952-
case 32:
953-
return PrimitiveTakeExec(ctx, batch, out);
954-
default:
955-
return TakeExec<FSBSelectionImpl>(ctx, batch, out);
956-
}
957-
}
958-
959909
Status ListTakeExec(KernelContext* ctx, const ExecSpan& batch, ExecResult* out) {
960910
return TakeExec<ListSelectionImpl<ListType>>(ctx, batch, out);
961911
}
@@ -968,26 +918,12 @@ Status FSLTakeExec(KernelContext* ctx, const ExecSpan& batch, ExecResult* out) {
968918
const ArraySpan& values = batch[0].array;
969919

970920
// If a FixedSizeList wraps a fixed-width type we can, in some cases, use
971-
// PrimitiveTakeExec for a fixed-size list array.
921+
// FixedWidthTakeExec for a fixed-size list array.
972922
if (util::IsFixedWidthLike(values,
973923
/*force_null_count=*/true,
974924
/*exclude_bool_and_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-
}
925+
return FixedWidthTakeExec(ctx, batch, out);
989926
}
990-
991927
return TakeExec<FSLSelectionImpl>(ctx, batch, out);
992928
}
993929

0 commit comments

Comments
 (0)