@@ -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
434457ContentDefinedChunker::ContentDefinedChunker (const LevelInfo& level_info,
0 commit comments