kudu-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From t...@apache.org
Subject [4/5] kudu git commit: Optimize BinaryDictBlock to use dense_hash_map, smaller hot path
Date Thu, 23 Mar 2017 04:19:00 GMT
Optimize BinaryDictBlock to use dense_hash_map, smaller hot path

In profiling dictionary encoding, I found that std::_Hashtable was a
high CPU consumer, particularly due to its use of the 'div' instruction.

This switches to using the Google dense_hash_map hashtable
implementation instead, which avoids the div instruction and generally
is faster for lookups.

I benchmarked using:
  perf record -g ./build/latest/bin/cfile-test --gtest_filter=\*100MLow\*0

Unfortunately this benchmark spends much more CPU in generating the test
data than it does actually appending rows to the cfile, but I compared
before/after by counting how many samples had 'AddCodeWords' in the
stack. This was reduced by 26%.

Longer benchmarks at [1] indicated an end-to-end speedup of a write
workload by ~8%.

The new thirdparty dependency will also likely come in useful for other
hot hashmaps in the code.

[1] https://docs.google.com/document/d/1U1IXS1XD2erZyq8_qG81A1gZaCeHcq2i0unea_eEf5c/edit#heading=h.942lv84cuv4z

Change-Id: I25c61694a31a929db65d8e19cedbdece3457723c
Reviewed-on: http://gerrit.cloudera.org:8080/6433
Reviewed-by: David Ribeiro Alves <dralves@apache.org>
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/6ce51294
Tree: http://git-wip-us.apache.org/repos/asf/kudu/tree/6ce51294
Diff: http://git-wip-us.apache.org/repos/asf/kudu/diff/6ce51294

Branch: refs/heads/master
Commit: 6ce5129479b44ad05c8cc37f35f0c279bc2eff4d
Parents: 3679ead
Author: Todd Lipcon <todd@apache.org>
Authored: Tue Mar 14 20:00:58 2017 -0700
Committer: Todd Lipcon <todd@apache.org>
Committed: Wed Mar 22 07:23:05 2017 +0000

----------------------------------------------------------------------
 src/kudu/cfile/binary_dict_block.cc | 60 ++++++++++++++++++--------------
 src/kudu/cfile/binary_dict_block.h  | 10 ++++--
 thirdparty/build-definitions.sh     |  7 ++++
 thirdparty/build-thirdparty.sh      |  5 +++
 thirdparty/download-thirdparty.sh   |  4 +++
 thirdparty/vars.sh                  | 11 ++++++
 6 files changed, 67 insertions(+), 30 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/kudu/blob/6ce51294/src/kudu/cfile/binary_dict_block.cc
----------------------------------------------------------------------
diff --git a/src/kudu/cfile/binary_dict_block.cc b/src/kudu/cfile/binary_dict_block.cc
index be10158..247a74b 100644
--- a/src/kudu/cfile/binary_dict_block.cc
+++ b/src/kudu/cfile/binary_dict_block.cc
@@ -17,18 +17,20 @@
 
 #include "kudu/cfile/binary_dict_block.h"
 
-#include <glog/logging.h>
 #include <algorithm>
+#include <limits>
+
+#include <glog/logging.h>
 
+#include "kudu/cfile/bshuf_block.h"
 #include "kudu/cfile/cfile_reader.h"
 #include "kudu/cfile/cfile_util.h"
 #include "kudu/cfile/cfile_writer.h"
-#include "kudu/cfile/bshuf_block.h"
 #include "kudu/common/columnblock.h"
 #include "kudu/gutil/casts.h"
 #include "kudu/gutil/stringprintf.h"
-#include "kudu/util/coding.h"
 #include "kudu/util/coding-inl.h"
+#include "kudu/util/coding.h"
 #include "kudu/util/group_varint-inl.h"
 #include "kudu/util/hexdump.h"
 #include "kudu/util/memory/arena.h"
@@ -37,11 +39,15 @@ namespace kudu {
 namespace cfile {
 
 BinaryDictBlockBuilder::BinaryDictBlockBuilder(const WriterOptions* options)
-  : options_(options),
-    dict_block_(options_),
-    dictionary_strings_arena_(1024, 32*1024*1024),
-    mode_(kCodeWordMode) {
+    : options_(options),
+      dict_block_(options_),
+      dictionary_strings_arena_(1024, 32*1024*1024),
+      mode_(kCodeWordMode) {
   data_builder_.reset(new BShufBlockBuilder<UINT32>(options_));
+  // We use this invalid StringPiece for the "empty key". It's safe to build such
+  // a string and use it in equality comparisons.
+  dictionary_.set_empty_key(StringPiece(static_cast<const char*>(nullptr),
+                                        std::numeric_limits<int>::max()));
   Reset();
 }
 
@@ -91,42 +97,42 @@ int BinaryDictBlockBuilder::AddCodeWords(const uint8_t* vals, size_t count)
{
   DCHECK_GT(count, 0);
   size_t i;
 
+  const Slice* src = reinterpret_cast<const Slice*>(vals);
   if (data_builder_->Count() == 0) {
-    const Slice* first = reinterpret_cast<const Slice*>(vals);
-    first_key_.assign_copy(first->data(), first->size());
+    first_key_.assign_copy(src->data(), src->size());
   }
 
-  for (i = 0; i < count; i++) {
-    const Slice* src = reinterpret_cast<const Slice*>(vals);
+  for (i = 0; i < count; i++, src++) {
     const char* c_str = reinterpret_cast<const char*>(src->data());
     StringPiece current_item(c_str, src->size());
     uint32_t codeword;
 
-    if (!FindCopy(dictionary_, current_item, &codeword)) {
-      // The dictionary block is full
-      if (dict_block_.Add(vals, 1) == 0) {
-        break;
-      }
-      const uint8_t* s_ptr = dictionary_strings_arena_.AddSlice(*src);
-      if (s_ptr == nullptr) {
-        // Arena does not have enough space for string content
-        // Ideally, this should not happen.
-        LOG(ERROR) << "Arena of Dictionary Encoder does not have enough memory for
strings";
+    if (PREDICT_FALSE(!FindCopy(dictionary_, current_item, &codeword))) {
+      // Not already in dictionary, try to add it if there is space.
+      if (PREDICT_FALSE(!AddToDict(*src, &codeword))) {
         break;
       }
-      const char* s_content = reinterpret_cast<const char*>(s_ptr);
-      codeword = dict_block_.Count() - 1;
-      InsertOrDie(&dictionary_, StringPiece(s_content, src->size()), codeword);
     }
-    // The data block is full
-    if (data_builder_->Add(reinterpret_cast<const uint8_t*>(&codeword), 1) ==
0) {
+    if (PREDICT_FALSE(data_builder_->Add(reinterpret_cast<const uint8_t*>(&codeword),
1) == 0)) {
+      // The data block is full
       break;
     }
-    vals += sizeof(Slice);
   }
   return i;
 }
 
+bool BinaryDictBlockBuilder::AddToDict(Slice val, uint32_t* codeword) {
+  if (PREDICT_FALSE(dict_block_.Add(reinterpret_cast<const uint8_t*>(&val), 1)
== 0)) {
+    // The dictionary block is full
+    return false;
+  }
+  const uint8_t* s_ptr = CHECK_NOTNULL(dictionary_strings_arena_.AddSlice(val));
+  const char* s_content = reinterpret_cast<const char*>(s_ptr);
+  *codeword = dict_block_.Count() - 1;
+  InsertOrDie(&dictionary_, StringPiece(s_content, val.size()), *codeword);
+  return true;
+}
+
 int BinaryDictBlockBuilder::Add(const uint8_t* vals, size_t count) {
   if (mode_ == kCodeWordMode) {
     return AddCodeWords(vals, count);

http://git-wip-us.apache.org/repos/asf/kudu/blob/6ce51294/src/kudu/cfile/binary_dict_block.h
----------------------------------------------------------------------
diff --git a/src/kudu/cfile/binary_dict_block.h b/src/kudu/cfile/binary_dict_block.h
index c06a506..39c570e 100644
--- a/src/kudu/cfile/binary_dict_block.h
+++ b/src/kudu/cfile/binary_dict_block.h
@@ -37,13 +37,14 @@
 #define KUDU_CFILE_BINARY_DICT_BLOCK_H
 
 #include <string>
-#include <unordered_map>
 #include <vector>
 
+#include <sparsehash/dense_hash_map>
+
+#include "kudu/cfile/binary_plain_block.h"
 #include "kudu/cfile/block_encodings.h"
 #include "kudu/cfile/block_pointer.h"
 #include "kudu/cfile/cfile.pb.h"
-#include "kudu/cfile/binary_plain_block.h"
 #include "kudu/gutil/gscoped_ptr.h"
 #include "kudu/gutil/map-util.h"
 #include "kudu/gutil/strings/stringpiece.h"
@@ -91,6 +92,9 @@ class BinaryDictBlockBuilder final : public BlockBuilder {
  private:
   int AddCodeWords(const uint8_t* vals, size_t count);
 
+  ATTRIBUTE_COLD
+  bool AddToDict(Slice val, uint32_t* codeword);
+
   faststring buffer_;
   bool finished_;
   const WriterOptions* options_;
@@ -102,7 +106,7 @@ class BinaryDictBlockBuilder final : public BlockBuilder {
   // They should NOT be cleared in the Reset() method.
   BinaryPlainBlockBuilder dict_block_;
 
-  std::unordered_map<StringPiece, uint32_t, GoodFastHash<StringPiece> > dictionary_;
+  google::dense_hash_map<StringPiece, uint32_t, GoodFastHash<StringPiece> > dictionary_;
   // Memory to hold the actual content for strings in the dictionary_.
   //
   // The size of it should be bigger than the size limit for dictionary block

http://git-wip-us.apache.org/repos/asf/kudu/blob/6ce51294/thirdparty/build-definitions.sh
----------------------------------------------------------------------
diff --git a/thirdparty/build-definitions.sh b/thirdparty/build-definitions.sh
index 4626154..ab5d0bd 100644
--- a/thirdparty/build-definitions.sh
+++ b/thirdparty/build-definitions.sh
@@ -678,3 +678,10 @@ build_boost() {
   fi
   popd
 }
+
+build_sparsehash() {
+  # This library is header-only, so we just copy the headers
+  pushd $SPARSEHASH_SOURCE
+  rsync -av --delete sparsehash/ $PREFIX/include/sparsehash/
+  popd
+}

http://git-wip-us.apache.org/repos/asf/kudu/blob/6ce51294/thirdparty/build-thirdparty.sh
----------------------------------------------------------------------
diff --git a/thirdparty/build-thirdparty.sh b/thirdparty/build-thirdparty.sh
index fe36f5d..a94b496 100755
--- a/thirdparty/build-thirdparty.sh
+++ b/thirdparty/build-thirdparty.sh
@@ -92,6 +92,7 @@ else
       "nvml")         F_NVML=1 ;;
       "boost")        F_BOOST=1 ;;
       "breakpad")     F_BREAKPAD=1 ;;
+      "sparsehash")   F_SPARSEHASH=1 ;;
       *)              echo "Unknown module: $arg"; exit 1 ;;
     esac
   done
@@ -217,6 +218,10 @@ if [ -n "$F_COMMON" -o -n "$F_TRACE_VIEWER" ]; then
   build_trace_viewer
 fi
 
+if [ -n "$F_COMMON" -o -n "$F_SPARSEHASH" ]; then
+  build_sparsehash
+fi
+
 ### Build C dependencies without instrumentation
 
 PREFIX=$PREFIX_DEPS

http://git-wip-us.apache.org/repos/asf/kudu/blob/6ce51294/thirdparty/download-thirdparty.sh
----------------------------------------------------------------------
diff --git a/thirdparty/download-thirdparty.sh b/thirdparty/download-thirdparty.sh
index 77f1bb4..708ac52 100755
--- a/thirdparty/download-thirdparty.sh
+++ b/thirdparty/download-thirdparty.sh
@@ -305,5 +305,9 @@ if [ ! -d "$BREAKPAD_SOURCE" ]; then
   fetch_and_expand breakpad-${BREAKPAD_VERSION}.tar.gz
 fi
 
+if [ ! -d "$SPARSEHASH_SOURCE" ]; then
+  fetch_and_expand sparsehash-c11-${SPARSEHASH_VERSION}.tar.gz
+fi
+
 echo "---------------"
 echo "Thirdparty dependencies downloaded successfully"

http://git-wip-us.apache.org/repos/asf/kudu/blob/6ce51294/thirdparty/vars.sh
----------------------------------------------------------------------
diff --git a/thirdparty/vars.sh b/thirdparty/vars.sh
index 89a0dde..1ba9f30 100644
--- a/thirdparty/vars.sh
+++ b/thirdparty/vars.sh
@@ -175,3 +175,14 @@ OPENSSL_WORKAROUND_DIR="$TP_DIR/installed/openssl-el6-workaround"
 BREAKPAD_VERSION=f78d953511606348173911ae0b62572ebec1bbc4
 BREAKPAD_NAME=breakpad-$BREAKPAD_VERSION
 BREAKPAD_SOURCE=$TP_SOURCE_DIR/$BREAKPAD_NAME
+
+# Hash of the sparsehash-c11 git revision to use.
+# (from http://github.com/sparsehash/sparsehash-c11)
+#
+# To re-build this tarball use the following in the sparsehash-c11 repo:
+#  export NAME=sparsehash-c11-$(git rev-parse HEAD)
+#  git archive HEAD --prefix=$NAME/ -o /tmp/$NAME.tar.gz
+#  s3cmd put -P /tmp/$NAME.tar.gz s3://cloudera-thirdparty-libs/$NAME.tar.gz
+SPARSEHASH_VERSION=47a55825ca3b35eab1ca22b7ab82b9544e32a9af
+SPARSEHASH_NAME=sparsehash-c11-$SPARSEHASH_VERSION
+SPARSEHASH_SOURCE=$TP_SOURCE_DIR/$SPARSEHASH_NAME


Mime
View raw message