IMPALA-5222: don't call Bits::Log2*() functions Some of gutil's functions are fairly inefficient. We accidentally regressed this when switching to the new Bits::, and some of the BufferPool code that was in flight didn't switch over.
This commit switches to calling BitUtil::Log2*() everywhere and makes sure that those functions are all implemented in an efficient way. Change-Id: I46471590ae7cf5ccd3e44d5c31f0b06108a2a01c Reviewed-on: http://gerrit.cloudera.org:8080/6675 Reviewed-by: Henry Robinson <[email protected]> Tested-by: Impala Public Jenkins Project: http://git-wip-us.apache.org/repos/asf/incubator-impala/repo Commit: http://git-wip-us.apache.org/repos/asf/incubator-impala/commit/7fcf1ea4 Tree: http://git-wip-us.apache.org/repos/asf/incubator-impala/tree/7fcf1ea4 Diff: http://git-wip-us.apache.org/repos/asf/incubator-impala/diff/7fcf1ea4 Branch: refs/heads/master Commit: 7fcf1ea4c36e41c299e36078664522ef629bb5de Parents: 8bd854d Author: Tim Armstrong <[email protected]> Authored: Tue Apr 18 11:55:09 2017 -0700 Committer: Impala Public Jenkins <[email protected]> Committed: Fri Apr 21 21:03:43 2017 +0000 ---------------------------------------------------------------------- be/src/exec/parquet-column-readers.cc | 4 ++-- be/src/runtime/bufferpool/buffer-allocator.cc | 10 ++++----- be/src/runtime/bufferpool/buffer-pool.cc | 1 - be/src/runtime/disk-io-mgr.cc | 8 +++---- be/src/runtime/free-pool.h | 4 ++-- be/src/runtime/runtime-filter-bank.cc | 9 ++++---- be/src/runtime/tmp-file-mgr.cc | 5 ++--- be/src/util/bit-util-test.cc | 1 - be/src/util/bit-util.h | 25 +++++++++++++++++----- be/src/util/dict-encoding.h | 4 ++-- be/src/util/hdr-histogram.cc | 6 +++--- 11 files changed, 45 insertions(+), 32 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/incubator-impala/blob/7fcf1ea4/be/src/exec/parquet-column-readers.cc ---------------------------------------------------------------------- diff --git a/be/src/exec/parquet-column-readers.cc b/be/src/exec/parquet-column-readers.cc index ac74d72..f92de48 100644 --- a/be/src/exec/parquet-column-readers.cc +++ b/be/src/exec/parquet-column-readers.cc @@ -27,13 +27,13 @@ #include "exec/parquet-metadata-utils.h" #include "exec/parquet-scratch-tuple-batch.h" #include "exec/read-write-util.h" -#include "gutil/bits.h" #include "rpc/thrift-util.h" #include "runtime/collection-value-builder.h" #include "runtime/tuple-row.h" #include "runtime/tuple.h" #include "runtime/runtime-state.h" #include "runtime/mem-pool.h" +#include "util/bit-util.h" #include "util/codec.h" #include "util/debug-util.h" #include "util/dict-encoding.h" @@ -89,7 +89,7 @@ Status ParquetLevelDecoder::Init(const string& filename, if (num_bytes < 0) { return Status(TErrorCode::PARQUET_CORRUPT_RLE_BYTES, filename, num_bytes); } - int bit_width = Bits::Log2Ceiling64(max_level + 1); + int bit_width = BitUtil::Log2Ceiling64(max_level + 1); Reset(*data, num_bytes, bit_width); break; } http://git-wip-us.apache.org/repos/asf/incubator-impala/blob/7fcf1ea4/be/src/runtime/bufferpool/buffer-allocator.cc ---------------------------------------------------------------------- diff --git a/be/src/runtime/bufferpool/buffer-allocator.cc b/be/src/runtime/bufferpool/buffer-allocator.cc index e3c6e60..0fd88fd 100644 --- a/be/src/runtime/bufferpool/buffer-allocator.cc +++ b/be/src/runtime/bufferpool/buffer-allocator.cc @@ -22,8 +22,8 @@ #include <boost/bind.hpp> #include "common/atomic.h" -#include "gutil/bits.h" #include "runtime/bufferpool/system-allocator.h" +#include "util/bit-util.h" #include "util/cpu-info.h" #include "util/pretty-printer.h" #include "util/runtime-profile-counters.h" @@ -122,7 +122,7 @@ class BufferPool::FreeBufferArena : public CacheLineAligned { /// Return the lists of buffers for buffers of the given length. PerSizeLists* GetListsForSize(int64_t buffer_len) { DCHECK(BitUtil::IsPowerOf2(buffer_len)); - int idx = Bits::Log2Ceiling64(buffer_len) - parent_->log_min_buffer_len_; + int idx = BitUtil::Log2Ceiling64(buffer_len) - parent_->log_min_buffer_len_; DCHECK_LT(idx, NumBufferSizes()); return &buffer_sizes_[idx]; } @@ -142,7 +142,7 @@ int64_t BufferPool::BufferAllocator::CalcMaxBufferLen( int64_t min_buffer_len, int64_t system_bytes_limit) { // Find largest power of 2 smaller than 'system_bytes_limit'. int64_t upper_bound = system_bytes_limit == 0 ? 1L : 1L - << Bits::Log2Floor64(system_bytes_limit); + << BitUtil::Log2Floor64(system_bytes_limit); upper_bound = min(MAX_BUFFER_BYTES, upper_bound); return max(min_buffer_len, upper_bound); // Can't be < min_buffer_len. } @@ -153,8 +153,8 @@ BufferPool::BufferAllocator::BufferAllocator( system_allocator_(new SystemAllocator(min_buffer_len)), min_buffer_len_(min_buffer_len), max_buffer_len_(CalcMaxBufferLen(min_buffer_len, system_bytes_limit)), - log_min_buffer_len_(Bits::Log2Ceiling64(min_buffer_len_)), - log_max_buffer_len_(Bits::Log2Ceiling64(max_buffer_len_)), + log_min_buffer_len_(BitUtil::Log2Ceiling64(min_buffer_len_)), + log_max_buffer_len_(BitUtil::Log2Ceiling64(max_buffer_len_)), system_bytes_limit_(system_bytes_limit), system_bytes_remaining_(system_bytes_limit), per_core_arenas_(CpuInfo::GetMaxNumCores()), http://git-wip-us.apache.org/repos/asf/incubator-impala/blob/7fcf1ea4/be/src/runtime/bufferpool/buffer-pool.cc ---------------------------------------------------------------------- diff --git a/be/src/runtime/bufferpool/buffer-pool.cc b/be/src/runtime/bufferpool/buffer-pool.cc index a71a7c7..1d2f1d3 100644 --- a/be/src/runtime/bufferpool/buffer-pool.cc +++ b/be/src/runtime/bufferpool/buffer-pool.cc @@ -22,7 +22,6 @@ #include <boost/bind.hpp> #include "common/names.h" -#include "gutil/bits.h" #include "gutil/strings/substitute.h" #include "runtime/bufferpool/buffer-allocator.h" #include "util/bit-util.h" http://git-wip-us.apache.org/repos/asf/incubator-impala/blob/7fcf1ea4/be/src/runtime/disk-io-mgr.cc ---------------------------------------------------------------------- diff --git a/be/src/runtime/disk-io-mgr.cc b/be/src/runtime/disk-io-mgr.cc index b973a84..1f28b1a 100644 --- a/be/src/runtime/disk-io-mgr.cc +++ b/be/src/runtime/disk-io-mgr.cc @@ -20,8 +20,8 @@ #include <boost/algorithm/string.hpp> -#include "gutil/bits.h" #include "gutil/strings/substitute.h" +#include "util/bit-util.h" #include "util/hdfs-util.h" #include "util/time.h" @@ -304,7 +304,7 @@ DiskIoMgr::DiskIoMgr() : FileSystemUtil::MaxNumFileHandles()), &HdfsCachedFileHandle::Release) { int64_t max_buffer_size_scaled = BitUtil::Ceil(max_buffer_size_, min_buffer_size_); - free_buffers_.resize(Bits::Log2Ceiling64(max_buffer_size_scaled) + 1); + free_buffers_.resize(BitUtil::Log2Ceiling64(max_buffer_size_scaled) + 1); int num_local_disks = FLAGS_num_disks == 0 ? DiskInfo::num_disks() : FLAGS_num_disks; disk_queues_.resize(num_local_disks + REMOTE_NUM_DISKS); CheckSseSupport(); @@ -322,7 +322,7 @@ DiskIoMgr::DiskIoMgr(int num_local_disks, int threads_per_disk, int min_buffer_s file_handle_cache_(min(FLAGS_max_cached_file_handles, FileSystemUtil::MaxNumFileHandles()), &HdfsCachedFileHandle::Release) { int64_t max_buffer_size_scaled = BitUtil::Ceil(max_buffer_size_, min_buffer_size_); - free_buffers_.resize(Bits::Log2Ceiling64(max_buffer_size_scaled) + 1); + free_buffers_.resize(BitUtil::Log2Ceiling64(max_buffer_size_scaled) + 1); if (num_local_disks == 0) num_local_disks = DiskInfo::num_disks(); disk_queues_.resize(num_local_disks + REMOTE_NUM_DISKS); CheckSseSupport(); @@ -1223,7 +1223,7 @@ Status DiskIoMgr::WriteRangeHelper(FILE* file_handle, WriteRange* write_range) { int DiskIoMgr::free_buffers_idx(int64_t buffer_size) { int64_t buffer_size_scaled = BitUtil::Ceil(buffer_size, min_buffer_size_); - int idx = Bits::Log2Ceiling64(buffer_size_scaled); + int idx = BitUtil::Log2Ceiling64(buffer_size_scaled); DCHECK_GE(idx, 0); DCHECK_LT(idx, free_buffers_.size()); return idx; http://git-wip-us.apache.org/repos/asf/incubator-impala/blob/7fcf1ea4/be/src/runtime/free-pool.h ---------------------------------------------------------------------- diff --git a/be/src/runtime/free-pool.h b/be/src/runtime/free-pool.h index 98b1ebe..55774e8 100644 --- a/be/src/runtime/free-pool.h +++ b/be/src/runtime/free-pool.h @@ -23,9 +23,9 @@ #include <string.h> #include <string> #include <sstream> + #include "common/atomic.h" #include "common/logging.h" -#include "gutil/bits.h" #include "runtime/mem-pool.h" #include "util/bit-util.h" @@ -73,7 +73,7 @@ class FreePool { /// MemPool allocations are 8-byte aligned, so making allocations < 8 bytes /// doesn't save memory and eliminates opportunities to recycle allocations. size = std::max<int64_t>(8, size); - int free_list_idx = Bits::Log2Ceiling64(size); + int free_list_idx = BitUtil::Log2Ceiling64(size); DCHECK_LT(free_list_idx, NUM_LISTS); FreeListNode* allocation = lists_[free_list_idx].next; if (allocation == NULL) { http://git-wip-us.apache.org/repos/asf/incubator-impala/blob/7fcf1ea4/be/src/runtime/runtime-filter-bank.cc ---------------------------------------------------------------------- diff --git a/be/src/runtime/runtime-filter-bank.cc b/be/src/runtime/runtime-filter-bank.cc index 759b505..3e2dc6d 100644 --- a/be/src/runtime/runtime-filter-bank.cc +++ b/be/src/runtime/runtime-filter-bank.cc @@ -17,9 +17,7 @@ #include "runtime/runtime-filter-bank.h" -#include "common/names.h" #include "gen-cpp/ImpalaInternalService_types.h" -#include "gutil/bits.h" #include "gutil/strings/substitute.h" #include "runtime/client-cache.h" #include "runtime/exec-env.h" @@ -27,8 +25,11 @@ #include "runtime/mem-tracker.h" #include "runtime/runtime-filter.inline.h" #include "service/impala-server.h" +#include "util/bit-util.h" #include "util/bloom-filter.h" +#include "common/names.h" + using namespace impala; using namespace boost; using namespace strings; @@ -197,7 +198,7 @@ BloomFilter* RuntimeFilterBank::AllocateScratchBloomFilter(int32_t filter_id) { DCHECK(it != produced_filters_.end()) << "Filter ID " << filter_id << " not registered"; // Track required space - int64_t log_filter_size = Bits::Log2Ceiling64(it->second->filter_size()); + int64_t log_filter_size = BitUtil::Log2Ceiling64(it->second->filter_size()); int64_t required_space = BloomFilter::GetExpectedHeapSpaceUsed(log_filter_size); if (!filter_mem_tracker_->TryConsume(required_space)) return NULL; BloomFilter* bloom_filter = obj_pool_.Add(new BloomFilter(log_filter_size)); @@ -217,7 +218,7 @@ int64_t RuntimeFilterBank::GetFilterSizeForNdv(int64_t ndv) { bool RuntimeFilterBank::FpRateTooHigh(int64_t filter_size, int64_t observed_ndv) { double fpp = - BloomFilter::FalsePositiveProb(observed_ndv, Bits::Log2Ceiling64(filter_size)); + BloomFilter::FalsePositiveProb(observed_ndv, BitUtil::Log2Ceiling64(filter_size)); return fpp > FLAGS_max_filter_error_rate; } http://git-wip-us.apache.org/repos/asf/incubator-impala/blob/7fcf1ea4/be/src/runtime/tmp-file-mgr.cc ---------------------------------------------------------------------- diff --git a/be/src/runtime/tmp-file-mgr.cc b/be/src/runtime/tmp-file-mgr.cc index 37a05cf..293a898 100644 --- a/be/src/runtime/tmp-file-mgr.cc +++ b/be/src/runtime/tmp-file-mgr.cc @@ -26,7 +26,6 @@ #include <gutil/strings/join.h> #include <gutil/strings/substitute.h> -#include "gutil/bits.h" #include "runtime/runtime-state.h" #include "runtime/tmp-file-mgr-internal.h" #include "util/bit-util.h" @@ -299,7 +298,7 @@ Status TmpFileMgr::FileGroup::AllocateSpace( int64_t num_bytes, File** tmp_file, int64_t* file_offset) { lock_guard<SpinLock> lock(lock_); int64_t scratch_range_bytes = max<int64_t>(1L, BitUtil::RoundUpToPowerOfTwo(num_bytes)); - int free_ranges_idx = Bits::Log2Ceiling64(scratch_range_bytes); + int free_ranges_idx = BitUtil::Log2Ceiling64(scratch_range_bytes); if (!free_ranges_[free_ranges_idx].empty()) { *tmp_file = free_ranges_[free_ranges_idx].back().first; *file_offset = free_ranges_[free_ranges_idx].back().second; @@ -342,7 +341,7 @@ Status TmpFileMgr::FileGroup::AllocateSpace( void TmpFileMgr::FileGroup::RecycleFileRange(unique_ptr<WriteHandle> handle) { int64_t scratch_range_bytes = max<int64_t>(1L, BitUtil::RoundUpToPowerOfTwo(handle->len())); - int free_ranges_idx = Bits::Log2Ceiling64(scratch_range_bytes); + int free_ranges_idx = BitUtil::Log2Ceiling64(scratch_range_bytes); lock_guard<SpinLock> lock(lock_); free_ranges_[free_ranges_idx].emplace_back( handle->file_, handle->write_range_->offset()); http://git-wip-us.apache.org/repos/asf/incubator-impala/blob/7fcf1ea4/be/src/util/bit-util-test.cc ---------------------------------------------------------------------- diff --git a/be/src/util/bit-util-test.cc b/be/src/util/bit-util-test.cc index 948e5cf..2c40e569 100644 --- a/be/src/util/bit-util-test.cc +++ b/be/src/util/bit-util-test.cc @@ -23,7 +23,6 @@ #include <boost/utility.hpp> -#include "gutil/bits.h" #include "testutil/gtest-util.h" #include "util/bit-util.h" #include "util/cpu-info.h" http://git-wip-us.apache.org/repos/asf/incubator-impala/blob/7fcf1ea4/be/src/util/bit-util.h ---------------------------------------------------------------------- diff --git a/be/src/util/bit-util.h b/be/src/util/bit-util.h index 25a8c96..40a324c 100644 --- a/be/src/util/bit-util.h +++ b/be/src/util/bit-util.h @@ -287,9 +287,24 @@ class BitUtil { return __builtin_ctzll(v); } + // Wrap the gutil/ version for convenience. + static inline int Log2Floor(uint32_t n) { + return Bits::Log2Floor(n); + } + + // Wrap the gutil/ version for convenience. + static inline int Log2Floor64(uint64_t n) { + return Bits::Log2Floor64(n); + } + + // Wrap the gutil/ version for convenience. + static inline int Log2FloorNonZero64(uint64_t n) { + return Bits::Log2FloorNonZero64(n); + } + /// More efficient version of similar functions found in gutil/ static inline int Log2Ceiling(uint32 n) { - int floor = Bits::Log2Floor(n); + int floor = Log2Floor(n); // Check if zero or a power of two. This pattern is recognised by gcc and optimised // into branch-free code. if (0 == (n & (n - 1))) { @@ -299,8 +314,8 @@ class BitUtil { } } - static inline int Log2Ceiling64(uint64 n) { - int floor = Bits::Log2Floor64(n); + static inline int Log2Ceiling64(uint64_t n) { + int floor = Log2Floor64(n); // Check if zero or a power of two. This pattern is recognised by gcc and optimised // into branch-free code. if (0 == (n & (n - 1))) { @@ -310,8 +325,8 @@ class BitUtil { } } - static inline int Log2CeilingNonZero64(uint64 n) { - int floor = Bits::Log2FloorNonZero64(n); + static inline int Log2CeilingNonZero64(uint64_t n) { + int floor = Log2FloorNonZero64(n); // Check if zero or a power of two. This pattern is recognised by gcc and optimised // into branch-free code. if (0 == (n & (n - 1))) { http://git-wip-us.apache.org/repos/asf/incubator-impala/blob/7fcf1ea4/be/src/util/dict-encoding.h ---------------------------------------------------------------------- diff --git a/be/src/util/dict-encoding.h b/be/src/util/dict-encoding.h index e791d95..0b74468 100644 --- a/be/src/util/dict-encoding.h +++ b/be/src/util/dict-encoding.h @@ -22,11 +22,11 @@ #include <boost/unordered_map.hpp> -#include "gutil/bits.h" #include "gutil/strings/substitute.h" #include "exec/parquet-common.h" #include "runtime/mem-pool.h" #include "runtime/string-value.h" +#include "util/bit-util.h" #include "util/rle-encoding.h" namespace impala { @@ -73,7 +73,7 @@ class DictEncoderBase { int bit_width() const { if (UNLIKELY(num_entries() == 0)) return 0; if (UNLIKELY(num_entries() == 1)) return 1; - return Bits::Log2Ceiling64(num_entries()); + return BitUtil::Log2Ceiling64(num_entries()); } /// Writes out any buffered indices to buffer preceded by the bit width of this data. http://git-wip-us.apache.org/repos/asf/incubator-impala/blob/7fcf1ea4/be/src/util/hdr-histogram.cc ---------------------------------------------------------------------- diff --git a/be/src/util/hdr-histogram.cc b/be/src/util/hdr-histogram.cc index 25b8835..1427aac 100644 --- a/be/src/util/hdr-histogram.cc +++ b/be/src/util/hdr-histogram.cc @@ -22,9 +22,9 @@ #include <limits> #include <gutil/strings/substitute.h> #include <gutil/atomicops.h> -#include <gutil/bits.h> #include "common/status.h" +#include "util/bit-util.h" #include "common/names.h" @@ -113,7 +113,7 @@ void HdrHistogram::Init() { // Each sub-bucket is sized to have enough bits for the requested // 10^precision accuracy. int sub_bucket_count_magnitude = - Bits::Log2Ceiling(largest_value_with_single_unit_resolution); + BitUtil::Log2Ceiling(largest_value_with_single_unit_resolution); sub_bucket_half_count_magnitude_ = (sub_bucket_count_magnitude >= 1) ? sub_bucket_count_magnitude - 1 : 0; @@ -196,7 +196,7 @@ int HdrHistogram::BucketIndex(uint64_t value) const { // Here we are calculating the power-of-2 magnitude of the value with a // correction for precision in the first bucket. // Smallest power of 2 containing value. - int pow2ceiling = Bits::Log2Ceiling64(value | sub_bucket_mask_); + int pow2ceiling = BitUtil::Log2Ceiling64(value | sub_bucket_mask_); return pow2ceiling - (sub_bucket_half_count_magnitude_ + 1); }
