bshuf_block: some code cleanup * Some typo/grammar fixes/reformatting in comments. * Rename kMaxHeaderSize to kHeaderSize since the header is fixed-length. * Adds a private cell_ptr() function instead of error prone indexing with multiplication into the data_ buffer. * Remove an unnecessarily UINT32 specialization * Fix some C-style casts and unnecessary type punning in favor of memcpy() * Cleaned up padding code to use KUDU_ALIGN_UP
This also adds a TODO for a bug with GetLastKey: we are mistakenly indexing into data_[count - 1] instead of data_[(count - 1) * size_of_type] which causes incorrect results. The fix for this is in the following commit. Change-Id: I6857f8096319072eb09be097adea99c45735e0a6 Reviewed-on: http://gerrit.cloudera.org:8080/5193 Reviewed-by: Adar Dembo <[email protected]> Tested-by: Kudu Jenkins Project: http://git-wip-us.apache.org/repos/asf/kudu/repo Commit: http://git-wip-us.apache.org/repos/asf/kudu/commit/b43c6c6d Tree: http://git-wip-us.apache.org/repos/asf/kudu/tree/b43c6c6d Diff: http://git-wip-us.apache.org/repos/asf/kudu/diff/b43c6c6d Branch: refs/heads/master Commit: b43c6c6d6a8ff4c672b1818c0051158e93c9302e Parents: cc120da Author: Todd Lipcon <[email protected]> Authored: Tue Nov 22 16:38:07 2016 -0800 Committer: Todd Lipcon <[email protected]> Committed: Tue Nov 29 23:19:26 2016 +0000 ---------------------------------------------------------------------- src/kudu/cfile/bshuf_block.cc | 57 +++++++------------ src/kudu/cfile/bshuf_block.h | 110 +++++++++++++++++++++++-------------- 2 files changed, 88 insertions(+), 79 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/kudu/blob/b43c6c6d/src/kudu/cfile/bshuf_block.cc ---------------------------------------------------------------------- diff --git a/src/kudu/cfile/bshuf_block.cc b/src/kudu/cfile/bshuf_block.cc index e71c6cc..dec20bf 100644 --- a/src/kudu/cfile/bshuf_block.cc +++ b/src/kudu/cfile/bshuf_block.cc @@ -16,6 +16,11 @@ // under the License. #include "kudu/cfile/bshuf_block.h" +#include <algorithm> +#include <limits> + +#include "kudu/gutil/port.h" + namespace kudu { namespace cfile { @@ -45,33 +50,32 @@ void AbortWithBitShuffleError(int64_t val) { } // Template specialization for UINT32, which is used by dictionary encoding. -// It dynamically switch to block of UINT16 or UINT8 depending on the values +// It dynamically switches the element size to UINT16 or UINT8 depending on the values // in the current block. template<> Slice BShufBlockBuilder<UINT32>::Finish(rowid_t ordinal_pos) { uint32_t max_value = 0; for (int i = 0; i < count_; i++) { - uint32_t value = *reinterpret_cast<uint32_t*>(&data_[i * sizeof(uint32_t)]); - max_value = (max_value < value)? value : max_value; + max_value = std::max(max_value, *cell_ptr(i)); } // Shrink the block of UINT32 to block of UINT8 or UINT16 whenever possible and // set the header information accordingly, so that the decoder can recover the // encoded data. Slice ret; - if (max_value < 256) { + if (max_value <= std::numeric_limits<uint8_t>::max()) { for (int i = 0; i < count_; i++) { - uint32_t value = *reinterpret_cast<uint32_t*>(&data_[i * sizeof(uint32_t)]); - uint8_t converted_value = (uint8_t)(value); - *reinterpret_cast<uint8_t*>(&data_[i * sizeof(uint8_t)]) = converted_value; + uint32_t value = *cell_ptr(i); + uint8_t converted_value = static_cast<uint8_t>(value); + memcpy(&data_[i * sizeof(converted_value)], &converted_value, sizeof(converted_value)); } ret = Finish(ordinal_pos, sizeof(uint8_t)); InlineEncodeFixed32(ret.mutable_data() + 16, sizeof(uint8_t)); - } else if (max_value < 65536) { + } else if (max_value <= std::numeric_limits<uint16_t>::max()) { for (int i = 0; i < count_; i++) { - uint32_t value = *reinterpret_cast<uint32_t*>(&data_[i * sizeof(uint32_t)]); - uint16_t converted_value = (uint16_t)(value); - *reinterpret_cast<uint16_t*>(&data_[i * sizeof(uint16_t)]) = converted_value; + uint32_t value = *cell_ptr(i); + uint16_t converted_value = static_cast<uint16_t>(value); + memcpy(&data_[i * sizeof(converted_value)], &converted_value, sizeof(converted_value)); } ret = Finish(ordinal_pos, sizeof(uint16_t)); InlineEncodeFixed32(ret.mutable_data() + 16, sizeof(uint16_t)); @@ -82,27 +86,6 @@ Slice BShufBlockBuilder<UINT32>::Finish(rowid_t ordinal_pos) { return ret; } -// Template specialization for UINT32, dynamically decoded blocks of -// bitshuffled UINT16 OR UINT8 to UINT32. -template<> -Status BShufBlockDecoder<UINT32>::Expand() { - if (num_elems_ > 0) { - int64_t bytes; - decoded_.resize(num_elems_after_padding_ * size_of_elem_); - uint8_t* in = const_cast<uint8_t*>(&data_[kHeaderSize]); - - bytes = bitshuffle::decompress_lz4(in, decoded_.data(), num_elems_after_padding_, - size_of_elem_, 0); - if (PREDICT_FALSE(bytes < 0)) { - // Ideally, this should not happen. - AbortWithBitShuffleError(bytes); - return Status::RuntimeError("Unshuffle Process failed"); - } - } - - return Status::OK(); -} - // Template specialization for UINT32. template<> Status BShufBlockDecoder<UINT32>::SeekAtOrAfterValue(const void* value_void, bool* exact) { @@ -166,15 +149,13 @@ Status BShufBlockDecoder<UINT32>::CopyNextValuesToArray(size_t* n, uint8_t* arra // the expansion for size = 1 or size = 2. if (size_of_elem_ == 1) { for (int i = max_fetch - 1; i >= 0; i--) { - uint8_t value = *reinterpret_cast<uint8_t*>(&array[i * sizeof(uint8_t)]); - uint32_t convert_value = (uint32_t)(value); - *reinterpret_cast<uint32_t*>(&array[i * sizeof(uint32_t)]) = convert_value; + uint32_t value = array[i]; + memcpy(&array[i * sizeof(uint32_t)], &value, sizeof(value)); } } else if (size_of_elem_ == 2) { for (int i = max_fetch - 1; i >= 0; i--) { - uint16_t value = *reinterpret_cast<uint16_t*>(&array[i * sizeof(uint16_t)]); - uint32_t convert_value = (uint32_t)(value); - *reinterpret_cast<uint32_t*>(&array[i * sizeof(uint32_t)]) = convert_value; + uint32_t value = UNALIGNED_LOAD16(&array[i * sizeof(uint16_t)]); + memcpy(&array[i * sizeof(uint32_t)], &value, sizeof(value)); } } http://git-wip-us.apache.org/repos/asf/kudu/blob/b43c6c6d/src/kudu/cfile/bshuf_block.h ---------------------------------------------------------------------- diff --git a/src/kudu/cfile/bshuf_block.h b/src/kudu/cfile/bshuf_block.h index 22b207c..10caa32 100644 --- a/src/kudu/cfile/bshuf_block.h +++ b/src/kudu/cfile/bshuf_block.h @@ -31,6 +31,7 @@ #include "kudu/cfile/cfile_util.h" #include "kudu/common/columnblock.h" #include "kudu/gutil/strings/substitute.h" +#include "kudu/util/alignment.h" #include "kudu/util/coding.h" #include "kudu/util/coding-inl.h" #include "kudu/util/hexdump.h" @@ -45,18 +46,41 @@ void AbortWithBitShuffleError(int64_t val) ATTRIBUTE_NORETURN; // BshufBlockBuilder bitshuffles and compresses the bits of fixed // size type blocks with lz4. // -// Header includes: -// 1. ordinal of the first element within the block (uint32_t, little endian). -// 2. num of element within the block (uint32_t, little endian). -// 3. compressed_size, including the header size (uint32_t, little endian). -// 4. number of element after padding, padding is needed to meet the requirement -// by bitshuffle library that the number of element in the block must be -// multiple of 8. That means some psudo elements are appended at the end of the -// block if necessary (uint32_t, little endian). -// 5. the size of the elements in bytes, as actually encoded. In the case that all of the -// data in a block can fit into a smaller integer type, then we may choose to encode -// that smaller type to save CPU costs. This is currently done only for the UINT32 -// block type. (uint32_t, little endian). +// The block format is as follows: +// +// 1. Header: (20 bytes total) +// +// <first_ordinal> [32-bit] +// The ordinal offset of the first element in the block. +// +// <num_elements> [32-bit] +// The number of elements encoded in the block. +// +// <compressed_size> [32-bit] +// The post-compression size of the block, including this header. +// +// <padded_num_elements> [32-bit] +// Padding is needed to meet the requirements of the bitshuffle +// library such that the input/output is a multiple of 8. Some +// ignored elements are appended to the end of the block if necessary +// to meet this requirement. +// +// This header field is the post-padding element count. +// +// <elem_size_bytes> [32-bit] +// The size of the elements, in bytes, as actually encoded. In the +// case that all of the data in a block can fit into a smaller +// integer type, then we may choose to encode that smaller type +// to save CPU costs. +// +// This is currently only implemented in the UINT32 block type. +// +// NOTE: all on-disk ints are encoded little-endian +// +// 2. Element data +// +// The header is followed by the bitshuffle-compressed element data. +// template<DataType Type> class BShufBlockBuilder : public BlockBuilder { public: @@ -71,7 +95,7 @@ class BShufBlockBuilder : public BlockBuilder { data_.clear(); data_.reserve(options_->storage_attributes.cfile_block_size); buffer_.clear(); - buffer_.resize(kMaxHeaderSize); + buffer_.resize(kHeaderSize); } bool IsBlockFull(size_t limit) const OVERRIDE { @@ -100,7 +124,7 @@ class BShufBlockBuilder : public BlockBuilder { if (count_ == 0) { return Status::NotFound("no keys in data block"); } - memcpy(key, &data_[0], size_of_type); + memcpy(key, cell_ptr(0), size_of_type); return Status::OK(); } @@ -108,6 +132,8 @@ class BShufBlockBuilder : public BlockBuilder { if (count_ == 0) { return Status::NotFound("no keys in data block"); } + // TODO(todd): the following memcpy is incorrect. Will fix this in the + // next commit in this patch series. memcpy(key, &data_[count_ - 1], size_of_type); return Status::OK(); } @@ -117,36 +143,47 @@ class BShufBlockBuilder : public BlockBuilder { } private: + typedef typename TypeTraits<Type>::cpp_type CppType; + + const CppType* cell_ptr(int idx) const { + DCHECK_GE(idx, 0); + return reinterpret_cast<const CppType*>(&data_[idx * size_of_type]); + } + CppType* cell_ptr(int idx) { + DCHECK_GE(idx, 0); + return reinterpret_cast<CppType*>(&data_[idx * size_of_type]); + } + size_t EstimateEncodedSize() const { - int num = count_ + NumOfPaddingNeeded(); + int num = KUDU_ALIGN_UP(count_, 8); // The result of bshuf_compress_lz4_bound(num, size_of_type, 0) // is always bigger than the original size (num * size_of_type). // However, the compression ratio in most cases is larger than 1, // Therefore, using the original size may be more accurate and // cause less overhead. - return kMaxHeaderSize + num * size_of_type; - } - - uint32_t NumOfPaddingNeeded() const { - return (count_ % 8 == 0) ? 0 : 8 - (count_ % 8); + // + // TODO(todd): we could make this estimate more accurate by keeping + // track of the maximum bit-width of the inserted elements. + return kHeaderSize + num * size_of_type; } Slice Finish(rowid_t ordinal_pos, int final_size_of_type) { - data_.resize(kMaxHeaderSize + final_size_of_type * count_); + data_.resize(kHeaderSize + final_size_of_type * count_); // Do padding so that the input num of element is multiple of 8. - uint32_t num_of_padding = NumOfPaddingNeeded() * final_size_of_type; - for (int i = 0; i < num_of_padding; i++) { + int num_elems_after_padding = KUDU_ALIGN_UP(count_, 8); + int padding_elems = num_elems_after_padding - count_; + int padding_bytes = padding_elems * final_size_of_type; + for (int i = 0; i < padding_bytes; i++) { data_.push_back(0); } - int num_elems_after_padding = count_ + NumOfPaddingNeeded(); - buffer_.resize(kMaxHeaderSize + + buffer_.resize(kHeaderSize + bitshuffle::compress_lz4_bound(num_elems_after_padding, final_size_of_type, 0)); InlineEncodeFixed32(&buffer_[0], ordinal_pos); InlineEncodeFixed32(&buffer_[4], count_); - int64_t bytes = bitshuffle::compress_lz4(data_.data(), &buffer_[kMaxHeaderSize], + int64_t bytes = bitshuffle::compress_lz4(data_.data(), &buffer_[kHeaderSize], num_elems_after_padding, final_size_of_type, 0); if (PREDICT_FALSE(bytes < 0)) { // This means the bitshuffle function fails. @@ -156,15 +193,14 @@ class BShufBlockBuilder : public BlockBuilder { // since we have logged fatal in AbortWithBitShuffleError(). return Slice(); } - InlineEncodeFixed32(&buffer_[8], kMaxHeaderSize + bytes); + InlineEncodeFixed32(&buffer_[8], kHeaderSize + bytes); InlineEncodeFixed32(&buffer_[12], num_elems_after_padding); InlineEncodeFixed32(&buffer_[16], final_size_of_type); - return Slice(buffer_.data(), kMaxHeaderSize + bytes); + return Slice(buffer_.data(), kHeaderSize + bytes); } // Length of a header. - static const size_t kMaxHeaderSize = sizeof(uint32_t) * 5; - typedef typename TypeTraits<Type>::cpp_type CppType; + static const size_t kHeaderSize = sizeof(uint32_t) * 5; enum { size_of_type = TypeTraits<Type>::size }; @@ -207,7 +243,7 @@ class BShufBlockDecoder : public BlockDecoder { return Status::Corruption("Size Information unmatched"); } num_elems_after_padding_ = DecodeFixed32(&data_[12]); - if (num_elems_after_padding_ != num_elems_ + NumOfPaddingNeeded()) { + if (num_elems_after_padding_ != KUDU_ALIGN_UP(num_elems_, 8)) { return Status::Corruption("num of element information corrupted"); } size_of_elem_ = DecodeFixed32(&data_[16]); @@ -326,19 +362,13 @@ class BShufBlockDecoder : public BlockDecoder { return result; } - // Return the number of padding elements needed to ensure that the - // number of elements is a multiple of 8. - uint32_t NumOfPaddingNeeded() const { - return KUDU_ALIGN_UP(num_elems_, 8) - num_elems_; - } - Status Expand() { if (num_elems_ > 0) { int64_t bytes; - decoded_.resize(num_elems_after_padding_ * size_of_type); + decoded_.resize(num_elems_after_padding_ * size_of_elem_); uint8_t* in = const_cast<uint8_t*>(&data_[kHeaderSize]); bytes = bitshuffle::decompress_lz4(in, decoded_.data(), num_elems_after_padding_, - size_of_type, 0); + size_of_elem_, 0); if (PREDICT_FALSE(bytes < 0)) { // Ideally, this should not happen. AbortWithBitShuffleError(bytes); @@ -373,8 +403,6 @@ class BShufBlockDecoder : public BlockDecoder { }; template<> -Status BShufBlockDecoder<UINT32>::Expand(); -template<> Status BShufBlockDecoder<UINT32>::SeekAtOrAfterValue(const void* value_void, bool* exact); template<> Status BShufBlockDecoder<UINT32>::CopyNextValuesToArray(size_t* n, uint8_t* array);
