MCPcopy Create free account
hub / github.com/apache/arrow / ByteStreamSplitEncodeSimd

Function ByteStreamSplitEncodeSimd

cpp/src/arrow/util/byte_stream_split_internal.h:172–287  ·  view source on GitHub ↗

Source from the content-addressed store, hash-verified

170
171template <typename Arch, int kNumStreams>
172void ByteStreamSplitEncodeSimd(const uint8_t* raw_values, int width,
173 const int64_t num_values, uint8_t* output_buffer_raw) {
174 using simd_batch = xsimd::batch<int8_t, Arch>;
175 // For signed arithmetic
176 constexpr int kBatchSize = static_cast<int>(simd_batch::size);
177
178 static_assert(kBatchSize >= 16, "The smallest SIMD size is 128 bits");
179
180 if constexpr (kBatchSize > 16) {
181 if (num_values < kBatchSize) {
182 using Arch128 = xsimd::make_sized_batch_t<int8_t, 16>::arch_type;
183 return ByteStreamSplitEncodeSimd<Arch128, kNumStreams>(
184 raw_values, width, num_values, output_buffer_raw);
185 }
186 }
187
188 assert(width == kNumStreams);
189 static_assert(kNumStreams <= kBatchSize,
190 "The algorithm works when the number of streams is smaller than the SIMD "
191 "batch size.");
192 constexpr int kBlockSize = kBatchSize * kNumStreams;
193 static_assert(ReversePow2(kNumStreams) != 0,
194 "The algorithm works for a number of streams being a power of two.");
195
196 const int64_t size = num_values * kNumStreams;
197 const int64_t num_blocks = size / kBlockSize;
198 int8_t* output_buffer_streams[kNumStreams];
199 for (int i = 0; i < kNumStreams; ++i) {
200 output_buffer_streams[i] =
201 reinterpret_cast<int8_t*>(&output_buffer_raw[num_values * i]);
202 }
203
204 // First handle suffix.
205 const int64_t num_processed_elements = (num_blocks * kBlockSize) / kNumStreams;
206 for (int64_t i = num_processed_elements; i < num_values; ++i) {
207 for (int j = 0; j < kNumStreams; ++j) {
208 const uint8_t byte_in_value = raw_values[i * kNumStreams + j];
209 output_buffer_raw[j * num_values + i] = byte_in_value;
210 }
211 }
212
213 // Number of input values we can fit in a simd register
214 constexpr int kNumValuesInBatch = kBatchSize / kNumStreams;
215 static_assert(kNumValuesInBatch > 0);
216 // Number of bytes we'll bring together in the first byte-level part of the algorithm.
217 // Since we zip with the next batch, the number of values in a batch determines how many
218 // bytes end up together before we can use a larger type
219 constexpr int kNumBytes = 2 * kNumValuesInBatch;
220 // Number of steps in the first part of the algorithm with byte-level zipping
221 constexpr int kNumStepsByte = ReversePow2(kNumValuesInBatch) + 1;
222 // Number of steps in the first part of the algorithm with large data type zipping
223 constexpr int kNumStepsLarge = ReversePow2(static_cast<int>(kBatchSize) / kNumBytes);
224 // Total number of steps
225 constexpr int kNumSteps = kNumStepsByte + kNumStepsLarge;
226 static_assert(kNumSteps == ReversePow2(kBatchSize));
227
228 // Two step shuffling algorithm that starts with bytes and ends with a larger data type.
229 // An algorithm similar to the decoding one with log2(kBatchSize) + 1 stages is

Callers

nothing calls this directly

Calls 1

ReversePow2Function · 0.85

Tested by

no test coverage detected