Skip to content

Commit 222220a

Browse files
authored
GH-51684: [C++][Parquet][FOLLOWUP] Speed up content-defined chunking with a local gear hash (#51692)
### Rationale for this change #51685 keeps one content-defined chunker per column for the whole file, so the file writer now creates the chunkers together. The chunker's hash loop stores its rolling hash state to memory for every hashed byte, because the values it reads through byte pointers may alias that state. That slows down the chunking, and with the chunkers next to each other, the threads writing neighbouring columns also contend for their cache lines. This PR is stacked on #51685, only the last commit is new. ### What changes are included in this PR? - The rolling hash and its chunking state move into a `GearHash` value. `GetChunks()` rolls a local copy of it and stores it back once, so the compiler keeps the state in registers. - `BM_WriteContentDefinedChunking` benchmarks writing 16 int32 columns of 1M rows with content-defined chunking, with and without threads. ### Are these changes tested? The existing CDC tests cover the chunking, the chunk boundaries don't change. Medians of `BM_WriteContentDefinedChunking` on an Apple M4 Max: | | main | #51685 | this PR | |---|---|---|---| | single-threaded | 49.6 ms | 49.6 ms | 36.9 ms | | multi-threaded | 10.5 ms | 15.4 ms | 9.1 ms | ### Are there any user-facing changes? No, writing with content-defined chunking gets faster. ### Was AI used for this PR? In accordance to the [AI generation guidelines](https://arrow.apache.org/docs/dev/developers/overview.html#ai-generated-code), please disclose below whether and how AI was used in this PR. Claude Code wrote the code, tests and description under human direction. **PR code and description written by:** - [ ] Human - [x] AI **Reviewed before submission by:** - [x] Human - [x] AI - [ ] Not reviewed * GitHub Issue: #51684
1 parent 9630caa commit 222220a

2 files changed

Lines changed: 119 additions & 54 deletions

File tree

‎cpp/src/parquet/arrow/reader_writer_benchmark.cc‎

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -273,6 +273,48 @@ BENCHMARK(BM_WriteBinaryColumn)
273273
->Args({50, kInfiniteUniqueValues})
274274
->Args({99, kInfiniteUniqueValues});
275275

276+
// Writes int32 columns with content-defined chunking into a single row group, with
277+
// use_threads the columns are chunked by different threads in parallel
278+
static void BM_WriteContentDefinedChunking(::benchmark::State& state) {
279+
const auto num_columns = static_cast<int>(state.range(0));
280+
const bool use_threads = state.range(1) != 0;
281+
constexpr int64_t kNumRows = 1024 * 1024;
282+
283+
::arrow::random::RandomArrayGenerator generator(/*seed=*/500);
284+
::arrow::FieldVector fields;
285+
::arrow::ArrayVector columns;
286+
for (int i = 0; i < num_columns; i++) {
287+
fields.push_back(::arrow::field("column" + std::to_string(i), ::arrow::int32(),
288+
/*nullable=*/false));
289+
columns.push_back(generator.Int32(kNumRows, /*min=*/0, /*max=*/1 << 30));
290+
}
291+
auto schema = ::arrow::schema(fields);
292+
auto batch = ::arrow::RecordBatch::Make(schema, kNumRows, columns);
293+
auto properties = WriterProperties::Builder()
294+
.enable_content_defined_chunking()
295+
->disable_dictionary()
296+
->build();
297+
auto arrow_properties =
298+
ArrowWriterProperties::Builder().set_use_threads(use_threads)->build();
299+
300+
for (auto _ : state) {
301+
auto output = CreateOutputStream();
302+
auto writer = arrow::FileWriter::Open(*schema, ::arrow::default_memory_pool(), output,
303+
properties, arrow_properties);
304+
EXIT_NOT_OK(writer.status());
305+
EXIT_NOT_OK((*writer)->WriteRecordBatch(*batch));
306+
EXIT_NOT_OK((*writer)->Close());
307+
}
308+
state.SetBytesProcessed(state.iterations() * num_columns * kNumRows *
309+
static_cast<int64_t>(sizeof(int32_t)));
310+
}
311+
312+
BENCHMARK(BM_WriteContentDefinedChunking)
313+
->ArgNames({"columns", "use_threads"})
314+
->Args({16, 0})
315+
->Args({16, 1})
316+
->UseRealTime();
317+
276318
template <typename T>
277319
struct Examples {
278320
static constexpr std::array<T, 2> values() { return {127, 128}; }

‎cpp/src/parquet/chunker_internal.cc‎

Lines changed: 77 additions & 54 deletions
Original file line numberDiff line numberDiff line change
@@ -113,14 +113,11 @@ uint64_t CalculateMask(int64_t min_chunk_size, int64_t max_chunk_size, int norm_
113113
}
114114
}
115115

116-
} // namespace
117-
118-
class ContentDefinedChunker::Impl {
116+
/// The gear hash of a column together with the state deciding the chunk boundaries
117+
class GearHash {
119118
public:
120-
Impl(const LevelInfo& level_info, int64_t min_chunk_size, int64_t max_chunk_size,
121-
int norm_level)
122-
: level_info_(level_info),
123-
min_chunk_size_(min_chunk_size),
119+
GearHash(int64_t min_chunk_size, int64_t max_chunk_size, int norm_level)
120+
: min_chunk_size_(min_chunk_size),
124121
max_chunk_size_(max_chunk_size),
125122
rolling_hash_mask_(CalculateMask(min_chunk_size, max_chunk_size, norm_level)) {}
126123

@@ -202,6 +199,40 @@ class ContentDefinedChunker::Impl {
202199
return false;
203200
}
204201

202+
private:
203+
// Minimum chunk size in bytes, the rolling hash will not be updated until this size is
204+
// reached for each chunk. Note that all data sent through the hash function is counted
205+
// towards the chunk size, including definition and repetition levels.
206+
int64_t min_chunk_size_;
207+
int64_t max_chunk_size_;
208+
// The mask to match the rolling hash against to determine if a new chunk should be
209+
// created. The mask is calculated based on min/max chunk size and the normalization
210+
// level.
211+
uint64_t rolling_hash_mask_;
212+
213+
// Whether the rolling hash has matched the mask since the last chunk creation. This
214+
// flag is set true by the Roll() function when the mask is matched and reset to false
215+
// by NeedNewChunk() method.
216+
bool has_matched_ = false;
217+
// The current run of the rolling hash, used to normalize the chunk size distribution
218+
// by requiring multiple consecutive matches to create a new chunk.
219+
int8_t nth_run_ = 0;
220+
// Current chunk size in bytes, reset to 0 when a new chunk is created.
221+
int64_t chunk_size_ = 0;
222+
// Rolling hash state, never reset only initialized once for the entire column.
223+
uint64_t rolling_hash_ = 0;
224+
};
225+
226+
} // namespace
227+
228+
class ContentDefinedChunker::Impl {
229+
public:
230+
Impl(const LevelInfo& level_info, int64_t min_chunk_size, int64_t max_chunk_size,
231+
int norm_level)
232+
: level_info_(level_info), gearhash_(min_chunk_size, max_chunk_size, norm_level) {}
233+
234+
uint64_t GetRollingHashMask() const { return gearhash_.GetRollingHashMask(); }
235+
205236
void ValidateChunks(const std::vector<Chunk>& chunks, int64_t num_levels) const {
206237
// chunks must be non-empty and monotonic increasing
207238
ARROW_DCHECK(!chunks.empty());
@@ -249,6 +280,9 @@ class ContentDefinedChunker::Impl {
249280
// requirements, we create a new chunk. See the `NeedNewChunk()` method for more
250281
// details.
251282
std::vector<Chunk> chunks;
283+
// Roll a local copy of the hash so the compiler can keep it in registers instead of
284+
// storing it to memory for every hashed byte
285+
GearHash gearhash = gearhash_;
252286
int64_t offset;
253287
int64_t prev_offset = 0;
254288
int64_t prev_value_offset = 0;
@@ -258,8 +292,8 @@ class ContentDefinedChunker::Impl {
258292
if (!has_rep_levels && !has_def_levels) {
259293
// fastest path for non-nested non-null data
260294
for (offset = 0; offset < num_levels; ++offset) {
261-
RollValue(offset);
262-
if (NeedNewChunk()) {
295+
RollValue(gearhash, offset);
296+
if (gearhash.NeedNewChunk()) {
263297
chunks.push_back({prev_offset, prev_offset, offset - prev_offset});
264298
prev_offset = offset;
265299
}
@@ -272,11 +306,11 @@ class ContentDefinedChunker::Impl {
272306
for (int64_t offset = 0; offset < num_levels; ++offset) {
273307
def_level = def_levels[offset];
274308

275-
Roll(&def_level);
309+
gearhash.Roll(&def_level);
276310
if (def_level == level_info_.def_level) {
277-
RollValue(offset);
311+
RollValue(gearhash, offset);
278312
}
279-
if (NeedNewChunk()) {
313+
if (gearhash.NeedNewChunk()) {
280314
chunks.push_back({prev_offset, prev_offset, offset - prev_offset});
281315
prev_offset = offset;
282316
}
@@ -293,13 +327,13 @@ class ContentDefinedChunker::Impl {
293327
def_level = def_levels[offset];
294328
rep_level = rep_levels[offset];
295329

296-
Roll(&def_level);
297-
Roll(&rep_level);
330+
gearhash.Roll(&def_level);
331+
gearhash.Roll(&rep_level);
298332
if (def_level == level_info_.def_level) {
299-
RollValue(value_offset);
333+
RollValue(gearhash, value_offset);
300334
}
301335

302-
if (rep_level == 0 && NeedNewChunk()) {
336+
if (rep_level == 0 && gearhash.NeedNewChunk()) {
303337
// if we are at a record boundary and need a new chunk, we create a new chunk
304338
auto levels_to_write = offset - prev_offset;
305339
if (levels_to_write > 0) {
@@ -314,6 +348,7 @@ class ContentDefinedChunker::Impl {
314348
}
315349
}
316350
}
351+
gearhash_ = gearhash;
317352

318353
// add the last chunk if we have any levels left
319354
if (prev_offset < num_levels) {
@@ -333,49 +368,55 @@ class ContentDefinedChunker::Impl {
333368
const uint8_t* raw_values =
334369
values.data()->GetValues<uint8_t>(/*i=*/1, /*absolute_offset=*/0) +
335370
values.offset() * kByteWidth;
336-
return Calculate(def_levels, rep_levels, num_levels, [&](int64_t i) {
337-
return Roll<kByteWidth>(&raw_values[i * kByteWidth]);
338-
});
371+
return Calculate(def_levels, rep_levels, num_levels,
372+
[&](GearHash& gearhash, int64_t i) {
373+
return gearhash.Roll<kByteWidth>(&raw_values[i * kByteWidth]);
374+
});
339375
}
340376

341377
template <typename ArrayType>
342378
std::vector<Chunk> CalculateBinaryLike(const int16_t* def_levels,
343379
const int16_t* rep_levels, int64_t num_levels,
344380
const ::arrow::Array& values) {
345381
const auto& array = checked_cast<const ArrayType&>(values);
346-
return Calculate(def_levels, rep_levels, num_levels, [&](int64_t i) {
347-
typename ArrayType::offset_type length;
348-
const uint8_t* value = array.GetValue(i, &length);
349-
Roll(value, length);
350-
});
382+
return Calculate(def_levels, rep_levels, num_levels,
383+
[&](GearHash& gearhash, int64_t i) {
384+
typename ArrayType::offset_type length;
385+
const uint8_t* value = array.GetValue(i, &length);
386+
gearhash.Roll(value, length);
387+
});
351388
}
352389

353390
std::vector<Chunk> CalculateBinaryView(const int16_t* def_levels,
354391
const int16_t* rep_levels, int64_t num_levels,
355392
const ::arrow::Array& values) {
356393
const auto& array = checked_cast<const ::arrow::BinaryViewArray&>(values);
357-
return Calculate(def_levels, rep_levels, num_levels, [&](int64_t i) {
358-
const std::string_view value = array.GetView(i);
359-
Roll(reinterpret_cast<const uint8_t*>(value.data()),
360-
static_cast<int64_t>(value.size()));
361-
});
394+
return Calculate(def_levels, rep_levels, num_levels,
395+
[&](GearHash& gearhash, int64_t i) {
396+
const std::string_view value = array.GetView(i);
397+
gearhash.Roll(reinterpret_cast<const uint8_t*>(value.data()),
398+
static_cast<int64_t>(value.size()));
399+
});
362400
}
363401

364402
std::vector<Chunk> GetChunks(const int16_t* def_levels, const int16_t* rep_levels,
365403
int64_t num_levels, const ::arrow::Array& values) {
366404
auto handle_type = [&](auto&& type) -> std::vector<Chunk> {
367405
using ArrowType = std::decay_t<decltype(type)>;
368406
if constexpr (ArrowType::type_id == ::arrow::Type::NA) {
369-
return Calculate(def_levels, rep_levels, num_levels, [](int64_t) {});
407+
return Calculate(def_levels, rep_levels, num_levels, [](GearHash&, int64_t) {});
370408
} else if constexpr (ArrowType::type_id == ::arrow::Type::BOOL) {
371409
const auto& array = static_cast<const ::arrow::BooleanArray&>(values);
372-
return Calculate(def_levels, rep_levels, num_levels,
373-
[&](int64_t i) { Roll(array.Value(i)); });
410+
return Calculate(
411+
def_levels, rep_levels, num_levels,
412+
[&](GearHash& gearhash, int64_t i) { gearhash.Roll(array.Value(i)); });
374413
} else if constexpr (ArrowType::type_id == ::arrow::Type::FIXED_SIZE_BINARY) {
375414
const auto& array = static_cast<const ::arrow::FixedSizeBinaryArray&>(values);
376415
const auto byte_width = array.byte_width();
377416
return Calculate(def_levels, rep_levels, num_levels,
378-
[&](int64_t i) { Roll(array.GetValue(i), byte_width); });
417+
[&](GearHash& gearhash, int64_t i) {
418+
gearhash.Roll(array.GetValue(i), byte_width);
419+
});
379420
} else if constexpr (ArrowType::type_id == ::arrow::Type::EXTENSION) {
380421
const auto& array = static_cast<const ::arrow::ExtensionArray&>(values);
381422
return GetChunks(def_levels, rep_levels, num_levels, *array.storage());
@@ -408,27 +449,9 @@ class ContentDefinedChunker::Impl {
408449
private:
409450
// The column's level information
410451
const internal::LevelInfo level_info_;
411-
// Minimum chunk size in bytes, the rolling hash will not be updated until this size is
412-
// reached for each chunk. Note that all data sent through the hash function is counted
413-
// towards the chunk size, including definition and repetition levels.
414-
const int64_t min_chunk_size_;
415-
const int64_t max_chunk_size_;
416-
// The mask to match the rolling hash against to determine if a new chunk should be
417-
// created. The mask is calculated based on min/max chunk size and the normalization
418-
// level.
419-
const uint64_t rolling_hash_mask_;
420-
421-
// Whether the rolling hash has matched the mask since the last chunk creation. This
422-
// flag is set true by the Roll() function when the mask is matched and reset to false
423-
// by NeedNewChunk() method.
424-
bool has_matched_ = false;
425-
// The current run of the rolling hash, used to normalize the chunk size distribution
426-
// by requiring multiple consecutive matches to create a new chunk.
427-
int8_t nth_run_ = 0;
428-
// Current chunk size in bytes, reset to 0 when a new chunk is created.
429-
int64_t chunk_size_ = 0;
430-
// Rolling hash state, never reset only initialized once for the entire column.
431-
uint64_t rolling_hash_ = 0;
452+
// The gear hash carried over between the calls, so the chunking continues across
453+
// the pages and the row groups
454+
GearHash gearhash_;
432455
};
433456

434457
ContentDefinedChunker::ContentDefinedChunker(const LevelInfo& level_info,

0 commit comments

Comments
 (0)