kudu-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From t...@apache.org
Subject [3/5] kudu git commit: bshuf_block: some code cleanup
Date Wed, 30 Nov 2016 00:10:01 GMT
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 <adar@cloudera.com>
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 <todd@apache.org>
Authored: Tue Nov 22 16:38:07 2016 -0800
Committer: Todd Lipcon <todd@apache.org>
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);


Mime
View raw message