You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@kudu.apache.org by to...@apache.org on 2017/03/23 04:19:00 UTC
[4/5] kudu git commit: Optimize BinaryDictBlock to use dense_hash_map,
smaller hot path
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 <dr...@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 <to...@apache.org>
Authored: Tue Mar 14 20:00:58 2017 -0700
Committer: Todd Lipcon <to...@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