Skip to content

Commit a0c9a4b

Browse files
AntoinePrvpitrou
andauthored
GH-48277: [C++][Parquet] unpack with shuffle algorithm (#47994)
### Rationale for this change The current bit-unpacking algorithm (which is implemented as a C++ code generator script in Python) does not fully leverage SIMD operations: all loads and some bitshifts use scalar operations, leaving performance on the table. ### What changes are included in this PR? 1. Devise new bit-unpacking algorithms that fully leverage SIMD operations, for various parameter values of (packed bit width, destination integer width, SIMD register size). Different algorithms are necessary for different parameter values, because of straddling issues with some bit offsets. 2. Implement these new algorithms entirely in C++ using metaprogramming: the tables necessary for efficient SIMD swizzling and shifting are computed at compile-time using `constexpr` code (the exception is AVX-512 which is still using the legacy Python code generation script). 3. Implement low-level generic fallbacks for SIMD operations that are not available in all SIMD instruction sets, such as some flavor of bit-shifting. These fallbacks are also being contributed to xsimd, but have not been merged there yet. #### Benchmark results on a AVX2 CPU (AMD Zen 2) on Linux (Ubuntu 24.04): * Parquet decoding: * between 30% and 60% faster on DELTA_BINARY_PACKED integer decoding * up to 30% faster on RLE boolean decoding * Parquet reading: * around 60% faster on BIT_PACKED levels reading * up to 50% faster on RLE levels reading * up to 20% faster on reading or skipping OPTIONAL and REPEATED records ### Are these changes tested? Yes, by the current extensive bit-unpacking and Parquet decoding tests. ### Are there any user-facing changes? No * GitHub Issue: #48277 Lead-authored-by: Antoine Prouvost <[email protected]> Co-authored-by: AntoinePrv <[email protected]> Co-authored-by: Antoine Pitrou <[email protected]> Signed-off-by: Antoine Pitrou <[email protected]>
1 parent c9dfb3e commit a0c9a4b

24 files changed

Lines changed: 2033 additions & 40971 deletions

‎cpp/cmake_modules/SetupCxxFlags.cmake‎

Lines changed: 6 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -74,7 +74,12 @@ if(ARROW_CPU_FLAG STREQUAL "x86")
7474
if(CMAKE_SIZEOF_VOID_P EQUAL 8)
7575
# Check for AVX extensions on 64-bit systems only, as 32-bit support seems iffy
7676
list(JOIN ARROW_AVX2_FLAGS " " ARROW_AVX2_FLAGS_COMMAND_LINE)
77-
check_cxx_compiler_flag("${ARROW_AVX2_FLAGS_COMMAND_LINE}" CXX_SUPPORTS_AVX2)
77+
if(MINGW AND CMAKE_CXX_COMPILER_ID STREQUAL "GNU")
78+
# https://gcc.gnu.org/bugzilla/show_bug.cgi?id=54412
79+
message(STATUS "Disable AVX2 support on gcc / MINGW for now")
80+
else()
81+
check_cxx_compiler_flag("${ARROW_AVX2_FLAGS_COMMAND_LINE}" CXX_SUPPORTS_AVX2)
82+
endif()
7883
if(MINGW)
7984
# https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65782
8085
message(STATUS "Disable AVX512 support on MINGW for now")

‎cpp/src/arrow/util/bit_stream_utils_internal.h‎

Lines changed: 11 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -203,8 +203,9 @@ inline bool BitWriter::PutValue(uint64_t v, int num_bits) {
203203

204204
if (ARROW_PREDICT_FALSE(static_cast<int64_t>(byte_offset_) * 8 + bit_offset_ +
205205
num_bits >
206-
static_cast<int64_t>(max_bytes_) * 8))
206+
static_cast<int64_t>(max_bytes_) * 8)) {
207207
return false;
208+
}
208209

209210
buffered_values_ |= v << bit_offset_;
210211
bit_offset_ += num_bits;
@@ -273,14 +274,19 @@ inline int BitReader::GetBatch(int num_bits, T* v, int batch_size) {
273274
batch_size = static_cast<int>(remaining_bits / num_bits);
274275
}
275276

277+
const ::arrow::internal::UnpackOptions opts{
278+
.batch_size = batch_size,
279+
.bit_width = num_bits,
280+
.bit_offset = bit_offset_,
281+
.max_read_bytes = max_bytes_ - byte_offset_,
282+
};
283+
276284
if constexpr (std::is_same_v<T, bool>) {
277-
::arrow::internal::unpack(buffer_ + byte_offset_, v, batch_size, num_bits,
278-
bit_offset_);
285+
::arrow::internal::unpack(buffer_ + byte_offset_, v, opts);
279286

280287
} else {
281288
::arrow::internal::unpack(buffer_ + byte_offset_,
282-
reinterpret_cast<std::make_unsigned_t<T>*>(v), batch_size,
283-
num_bits, bit_offset_);
289+
reinterpret_cast<std::make_unsigned_t<T>*>(v), opts);
284290
}
285291

286292
Advance(batch_size * num_bits);

‎cpp/src/arrow/util/bpacking.cc‎

Lines changed: 16 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -17,7 +17,6 @@
1717

1818
#include <array>
1919

20-
#include "arrow/util/bpacking_dispatch_internal.h"
2120
#include "arrow/util/bpacking_internal.h"
2221
#include "arrow/util/bpacking_scalar_internal.h"
2322
#include "arrow/util/bpacking_simd_internal.h"
@@ -29,19 +28,21 @@ namespace {
2928

3029
template <typename Uint>
3130
struct UnpackDynamicFunction {
32-
using FunctionType = decltype(&unpack_scalar<Uint>);
31+
using FunctionType = decltype(&bpacking::unpack_scalar<Uint>);
3332
using Implementation = std::pair<DispatchLevel, FunctionType>;
3433

3534
static constexpr auto implementations() {
3635
return std::array{
37-
// Current SIMD unpack algorithm works terribly on SSE4.2 due to lack of variable
38-
// rhsift and poor xsimd fallback.
39-
Implementation{DispatchLevel::NONE, &unpack_scalar<Uint>},
36+
#if defined(ARROW_HAVE_SSE4_2)
37+
Implementation{DispatchLevel::NONE, &bpacking::unpack_sse4_2<Uint>},
38+
#else
39+
Implementation{DispatchLevel::NONE, &bpacking::unpack_scalar<Uint>},
40+
#endif
4041
#if defined(ARROW_HAVE_RUNTIME_AVX2)
41-
Implementation{DispatchLevel::AVX2, &unpack_avx2<Uint>},
42+
Implementation{DispatchLevel::AVX2, &bpacking::unpack_avx2<Uint>},
4243
#endif
4344
#if defined(ARROW_HAVE_RUNTIME_AVX512)
44-
Implementation{DispatchLevel::AVX512, &unpack_avx512<Uint>},
45+
Implementation{DispatchLevel::AVX512, &bpacking::unpack_avx512<Uint>},
4546
#endif
4647
};
4748
}
@@ -50,19 +51,19 @@ struct UnpackDynamicFunction {
5051
} // namespace
5152

5253
template <typename Uint>
53-
void unpack(const uint8_t* in, Uint* out, int batch_size, int num_bits, int bit_offset) {
54+
void unpack(const uint8_t* in, Uint* out, const UnpackOptions& opts) {
5455
#if defined(ARROW_HAVE_NEON)
55-
return unpack_neon(in, out, batch_size, num_bits, bit_offset);
56+
return bpacking::unpack_neon(in, out, opts);
5657
#else
5758
static DynamicDispatch<UnpackDynamicFunction<Uint> > dispatch;
58-
return dispatch.func(in, out, batch_size, num_bits, bit_offset);
59+
return dispatch.func(in, out, opts);
5960
#endif
6061
}
6162

62-
template void unpack<bool>(const uint8_t*, bool*, int, int, int);
63-
template void unpack<uint8_t>(const uint8_t*, uint8_t*, int, int, int);
64-
template void unpack<uint16_t>(const uint8_t*, uint16_t*, int, int, int);
65-
template void unpack<uint32_t>(const uint8_t*, uint32_t*, int, int, int);
66-
template void unpack<uint64_t>(const uint8_t*, uint64_t*, int, int, int);
63+
template void unpack<bool>(const uint8_t*, bool*, const UnpackOptions&);
64+
template void unpack<uint8_t>(const uint8_t*, uint8_t*, const UnpackOptions&);
65+
template void unpack<uint16_t>(const uint8_t*, uint16_t*, const UnpackOptions&);
66+
template void unpack<uint32_t>(const uint8_t*, uint32_t*, const UnpackOptions&);
67+
template void unpack<uint64_t>(const uint8_t*, uint64_t*, const UnpackOptions&);
6768

6869
} // namespace arrow::internal

‎cpp/src/arrow/util/bpacking_benchmark.cc‎

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

18+
#include <memory>
1819
#include <stdexcept>
1920
#include <vector>
2021

@@ -33,7 +34,7 @@ namespace arrow::internal {
3334
namespace {
3435

3536
template <typename Int>
36-
using UnpackFunc = void (*)(const uint8_t*, Int*, int, int, int);
37+
using UnpackFunc = void (*)(const uint8_t*, Int*, const UnpackOptions&);
3738

3839
/// Get the number of bytes associate with a packing.
3940
constexpr int32_t GetNumBytes(int32_t num_values, int32_t bit_width) {
@@ -86,33 +87,62 @@ void BM_Unpack(benchmark::State& state, bool aligned, UnpackFunc<Int> unpack, bo
8687
const uint8_t* packed_ptr =
8788
GetNextAlignedByte(packed.data(), sizeof(Int)) + (aligned ? 0 : 1);
8889

89-
std::vector<Int> unpacked(num_values, 0);
90+
auto unpacked = std::make_unique<Int[]>(num_values);
91+
92+
const ::arrow::internal::UnpackOptions opts{
93+
.batch_size = num_values,
94+
.bit_width = bit_width,
95+
.bit_offset = 0,
96+
.max_read_bytes = -1,
97+
};
9098

9199
for (auto _ : state) {
92-
unpack(packed_ptr, unpacked.data(), num_values, bit_width, /* bit_offset = */ 0);
100+
unpack(packed_ptr, unpacked.get(), opts);
93101
benchmark::ClobberMemory();
94102
}
95103
state.SetItemsProcessed(num_values * state.iterations());
96104
}
97105

98-
constexpr int32_t kMinRange = 64;
99-
constexpr int32_t kMaxRange = 32768;
106+
// Currently, the minimum unpack SIMD kernel size is 32 and the RLE-bit-packing encoder
107+
// will not emit runs larger than 512 (though other implementation might), so we biased
108+
// the benchmarks towards a rather small scale.
109+
static const auto kNumValuesRange = benchmark::CreateRange(32, 512, 2);
110+
constexpr std::initializer_list<int64_t> kBitWidths8 = {1, 2, 8};
100111
constexpr std::initializer_list<int64_t> kBitWidths16 = {1, 2, 8, 13};
101112
constexpr std::initializer_list<int64_t> kBitWidths32 = {1, 2, 8, 20};
102113
constexpr std::initializer_list<int64_t> kBitWidths64 = {1, 2, 8, 20, 47};
114+
115+
static const std::vector<std::vector<int64_t>> kBitWidthsNumValuesBool = {
116+
{0, 1},
117+
kNumValuesRange,
118+
};
119+
static const std::vector<std::vector<int64_t>> kBitWidthsNumValues8 = {
120+
kBitWidths8,
121+
kNumValuesRange,
122+
};
103123
static const std::vector<std::vector<int64_t>> kBitWidthsNumValues16 = {
104124
kBitWidths16,
105-
benchmark::CreateRange(kMinRange, kMaxRange, /*multi=*/32),
125+
kNumValuesRange,
106126
};
107127
static const std::vector<std::vector<int64_t>> kBitWidthsNumValues32 = {
108128
kBitWidths32,
109-
benchmark::CreateRange(kMinRange, kMaxRange, /*multi=*/32),
129+
kNumValuesRange,
110130
};
111131
static const std::vector<std::vector<int64_t>> kBitWidthsNumValues64 = {
112132
kBitWidths64,
113-
benchmark::CreateRange(kMinRange, kMaxRange, /*multi=*/32),
133+
kNumValuesRange,
114134
};
115135

136+
/// Nudge for MSVC template inside BENCHMARK_CAPTURE macro.
137+
void BM_UnpackBool(benchmark::State& state, bool aligned, UnpackFunc<bool> unpack,
138+
bool skip = false, std::string skip_msg = "") {
139+
return BM_Unpack<bool>(state, aligned, unpack, skip, std::move(skip_msg));
140+
}
141+
/// Nudge for MSVC template inside BENCHMARK_CAPTURE macro.
142+
void BM_UnpackUint8(benchmark::State& state, bool aligned, UnpackFunc<uint8_t> unpack,
143+
bool skip = false, std::string skip_msg = "") {
144+
return BM_Unpack<uint8_t>(state, aligned, unpack, skip, std::move(skip_msg));
145+
}
116146
/// Nudge for MSVC template inside BENCHMARK_CAPTURE macro.
117147
void BM_UnpackUint16(benchmark::State& state, bool aligned, UnpackFunc<uint16_t> unpack,
118148
bool skip = false, std::string skip_msg = "") {
@@ -129,52 +159,111 @@ void BM_UnpackUint64(benchmark::State& state, bool aligned, UnpackFunc<uint64_t>
129159
return BM_Unpack<uint64_t>(state, aligned, unpack, skip, std::move(skip_msg));
130160
}
131161

132-
BENCHMARK_CAPTURE(BM_UnpackUint16, ScalarUnaligned, false, &unpack_scalar<uint16_t>)
162+
BENCHMARK_CAPTURE(BM_UnpackBool, ScalarUnaligned, false, &bpacking::unpack_scalar<bool>)
163+
->ArgsProduct(kBitWidthsNumValuesBool);
164+
BENCHMARK_CAPTURE(BM_UnpackUint8, ScalarUnaligned, false,
165+
&bpacking::unpack_scalar<uint8_t>)
166+
->ArgsProduct(kBitWidthsNumValues8);
167+
BENCHMARK_CAPTURE(BM_UnpackUint16, ScalarUnaligned, false,
168+
&bpacking::unpack_scalar<uint16_t>)
133169
->ArgsProduct(kBitWidthsNumValues16);
134-
BENCHMARK_CAPTURE(BM_UnpackUint32, ScalarUnaligned, false, &unpack_scalar<uint32_t>)
170+
BENCHMARK_CAPTURE(BM_UnpackUint32, ScalarUnaligned, false,
171+
&bpacking::unpack_scalar<uint32_t>)
135172
->ArgsProduct(kBitWidthsNumValues32);
136-
BENCHMARK_CAPTURE(BM_UnpackUint64, ScalarUnaligned, false, &unpack_scalar<uint64_t>)
173+
BENCHMARK_CAPTURE(BM_UnpackUint64, ScalarUnaligned, false,
174+
&bpacking::unpack_scalar<uint64_t>)
137175
->ArgsProduct(kBitWidthsNumValues64);
138176

177+
#if defined(ARROW_HAVE_SSE4_2)
178+
BENCHMARK_CAPTURE(BM_UnpackBool, Sse42Unaligned, false, &bpacking::unpack_sse4_2<bool>)
179+
->ArgsProduct(kBitWidthsNumValuesBool);
180+
BENCHMARK_CAPTURE(BM_UnpackUint8, Sse42Unaligned, false,
181+
&bpacking::unpack_sse4_2<uint8_t>)
182+
->ArgsProduct(kBitWidthsNumValues8);
183+
BENCHMARK_CAPTURE(BM_UnpackUint16, Sse42Unaligned, false,
184+
&bpacking::unpack_sse4_2<uint16_t>)
185+
->ArgsProduct(kBitWidthsNumValues16);
186+
BENCHMARK_CAPTURE(BM_UnpackUint32, Sse42Unaligned, false,
187+
&bpacking::unpack_sse4_2<uint32_t>)
188+
->ArgsProduct(kBitWidthsNumValues32);
189+
BENCHMARK_CAPTURE(BM_UnpackUint64, Sse42Unaligned, false,
190+
&bpacking::unpack_sse4_2<uint64_t>)
191+
->ArgsProduct(kBitWidthsNumValues64);
192+
#endif
193+
139194
#if defined(ARROW_HAVE_RUNTIME_AVX2)
140-
BENCHMARK_CAPTURE(BM_UnpackUint16, Avx2Unaligned, false, &unpack_avx2<uint16_t>,
195+
BENCHMARK_CAPTURE(BM_UnpackBool, Avx2Unaligned, false, &bpacking::unpack_avx2<bool>,
196+
!CpuInfo::GetInstance()->IsSupported(CpuInfo::AVX2),
197+
"Avx2 not available")
198+
->ArgsProduct(kBitWidthsNumValuesBool);
199+
BENCHMARK_CAPTURE(BM_UnpackUint8, Avx2Unaligned, false, &bpacking::unpack_avx2<uint8_t>,
200+
!CpuInfo::GetInstance()->IsSupported(CpuInfo::AVX2),
201+
"Avx2 not available")
202+
->ArgsProduct(kBitWidthsNumValues8);
203+
BENCHMARK_CAPTURE(BM_UnpackUint16, Avx2Unaligned, false, &bpacking::unpack_avx2<uint16_t>,
141204
!CpuInfo::GetInstance()->IsSupported(CpuInfo::AVX2),
142205
"Avx2 not available")
143206
->ArgsProduct(kBitWidthsNumValues16);
144-
BENCHMARK_CAPTURE(BM_UnpackUint32, Avx2Unaligned, false, &unpack_avx2<uint32_t>,
207+
BENCHMARK_CAPTURE(BM_UnpackUint32, Avx2Unaligned, false, &bpacking::unpack_avx2<uint32_t>,
145208
!CpuInfo::GetInstance()->IsSupported(CpuInfo::AVX2),
146209
"Avx2 not available")
147210
->ArgsProduct(kBitWidthsNumValues32);
148-
BENCHMARK_CAPTURE(BM_UnpackUint64, Avx2Unaligned, false, &unpack_avx2<uint64_t>,
211+
BENCHMARK_CAPTURE(BM_UnpackUint64, Avx2Unaligned, false, &bpacking::unpack_avx2<uint64_t>,
149212
!CpuInfo::GetInstance()->IsSupported(CpuInfo::AVX2),
150213
"Avx2 not available")
151214
->ArgsProduct(kBitWidthsNumValues64);
152215
#endif
153216

154217
#if defined(ARROW_HAVE_RUNTIME_AVX512)
155-
BENCHMARK_CAPTURE(BM_UnpackUint16, Avx512Unaligned, false, &unpack_avx512<uint16_t>,
218+
BENCHMARK_CAPTURE(BM_UnpackBool, Avx512Unaligned, false, &bpacking::unpack_avx512<bool>,
219+
!CpuInfo::GetInstance()->IsSupported(CpuInfo::AVX512),
220+
"Avx512 not available")
221+
->ArgsProduct(kBitWidthsNumValuesBool);
222+
BENCHMARK_CAPTURE(BM_UnpackUint8, Avx512Unaligned, false,
223+
&bpacking::unpack_avx512<uint8_t>,
224+
!CpuInfo::GetInstance()->IsSupported(CpuInfo::AVX512),
225+
"Avx512 not available")
226+
->ArgsProduct(kBitWidthsNumValues8);
227+
BENCHMARK_CAPTURE(BM_UnpackUint16, Avx512Unaligned, false,
228+
&bpacking::unpack_avx512<uint16_t>,
156229
!CpuInfo::GetInstance()->IsSupported(CpuInfo::AVX512),
157230
"Avx512 not available")
158231
->ArgsProduct(kBitWidthsNumValues16);
159-
BENCHMARK_CAPTURE(BM_UnpackUint32, Avx512Unaligned, false, &unpack_avx512<uint32_t>,
232+
BENCHMARK_CAPTURE(BM_UnpackUint32, Avx512Unaligned, false,
233+
&bpacking::unpack_avx512<uint32_t>,
160234
!CpuInfo::GetInstance()->IsSupported(CpuInfo::AVX512),
161235
"Avx512 not available")
162236
->ArgsProduct(kBitWidthsNumValues32);
163-
BENCHMARK_CAPTURE(BM_UnpackUint64, Avx512Unaligned, false, &unpack_avx512<uint64_t>,
237+
BENCHMARK_CAPTURE(BM_UnpackUint64, Avx512Unaligned, false,
238+
&bpacking::unpack_avx512<uint64_t>,
164239
!CpuInfo::GetInstance()->IsSupported(CpuInfo::AVX512),
165240
"Avx512 not available")
166241
->ArgsProduct(kBitWidthsNumValues64);
167242
#endif
168243

169244
#if defined(ARROW_HAVE_NEON)
170-
BENCHMARK_CAPTURE(BM_UnpackUint16, NeonUnaligned, false, &unpack_neon<uint16_t>)
245+
BENCHMARK_CAPTURE(BM_UnpackBool, NeonUnaligned, false, &bpacking::unpack_neon<bool>)
246+
->ArgsProduct(kBitWidthsNumValuesBool);
247+
BENCHMARK_CAPTURE(BM_UnpackUint8, NeonUnaligned, false, &bpacking::unpack_neon<uint8_t>)
248+
->ArgsProduct(kBitWidthsNumValues8);
249+
BENCHMARK_CAPTURE(BM_UnpackUint16, NeonUnaligned, false, &bpacking::unpack_neon<uint16_t>)
171250
->ArgsProduct(kBitWidthsNumValues16);
172-
BENCHMARK_CAPTURE(BM_UnpackUint32, NeonUnaligned, false, &unpack_neon<uint32_t>)
251+
BENCHMARK_CAPTURE(BM_UnpackUint32, NeonUnaligned, false, &bpacking::unpack_neon<uint32_t>)
173252
->ArgsProduct(kBitWidthsNumValues32);
174-
BENCHMARK_CAPTURE(BM_UnpackUint64, NeonUnaligned, false, &unpack_neon<uint64_t>)
253+
BENCHMARK_CAPTURE(BM_UnpackUint64, NeonUnaligned, false, &bpacking::unpack_neon<uint64_t>)
175254
->ArgsProduct(kBitWidthsNumValues64);
176255
#endif
177256

257+
BENCHMARK_CAPTURE(BM_UnpackBool, DynamicAligned, true, &unpack<bool>)
258+
->ArgsProduct(kBitWidthsNumValuesBool);
259+
BENCHMARK_CAPTURE(BM_UnpackBool, DynamicUnaligned, false, &unpack<bool>)
260+
->ArgsProduct(kBitWidthsNumValuesBool);
261+
262+
BENCHMARK_CAPTURE(BM_UnpackUint8, DynamicAligned, true, &unpack<uint8_t>)
263+
->ArgsProduct(kBitWidthsNumValues8);
264+
BENCHMARK_CAPTURE(BM_UnpackUint8, DynamicUnaligned, false, &unpack<uint8_t>)
265+
->ArgsProduct(kBitWidthsNumValues8);
266+
178267
BENCHMARK_CAPTURE(BM_UnpackUint16, DynamicAligned, true, &unpack<uint16_t>)
179268
->ArgsProduct(kBitWidthsNumValues16);
180269
BENCHMARK_CAPTURE(BM_UnpackUint16, DynamicUnaligned, false, &unpack<uint16_t>)

0 commit comments

Comments
 (0)