|
| 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 |
0 commit comments