// Copyright (c) 2015 Baidu, Inc. // // Licensed under the Apache License, Version 2.0 (the "License"); // you may not use this file except in compliance with the License. // You may obtain a copy of the License at // // http://www.apache.org/licenses/LICENSE-2.0 // // Unless required by applicable law or agreed to in writing, software // distributed under the License is distributed on an "AS IS" BASIS, // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. // See the License for the specific language governing permissions and // limitations under the License. // Author: Zhangyi Chen (chenzhangyi01@baidu.com) // Date: 2015/09/15 15:14:32 #include "bvar/detail/percentile.h" #include "butil/logging.h" namespace bvar { namespace detail { inline uint32_t ones32(uint32_t x) { /* 32-bit recursive reduction using SWAR... * but first step is mapping 2-bit values * into sum of 2 1-bit values in sneaky way */ x -= ((x >> 1) & 0x55555555); x = (((x >> 2) & 0x33333333) + (x & 0x33333333)); x = (((x >> 4) + x) & 0x0f0f0f0f); x += (x >> 8); x += (x >> 16); return (x & 0x0000003f); } inline uint32_t log2(uint32_t x) { int y = (x & (x - 1)); y |= -y; y >>= 31; x |= (x >> 1); x |= (x >> 2); x |= (x >> 4); x |= (x >> 8); x |= (x >> 16); return(ones32(x) - 1 - y); } inline size_t get_interval_index(int64_t &x) { if (x <= 2) { return 0; } else if (x > std::numeric_limits<uint32_t>::max()) { x = std::numeric_limits<uint32_t>::max(); return 31; } else { return log2(x) - 1; } } class AddLatency { public: AddLatency(int64_t latency) : _latency(latency) {} void operator()(GlobalValue<Percentile::combiner_type>& global_value, ThreadLocalPercentileSamples& local_value) const { // Copy to latency since get_interval_index may change input. int64_t latency = _latency; const size_t index = get_interval_index(latency); PercentileInterval<ThreadLocalPercentileSamples::SAMPLE_SIZE>& interval = local_value.get_interval_at(index); if (interval.full()) { GlobalPercentileSamples* g = global_value.lock(); g->get_interval_at(index).merge(interval); g->_num_added += interval.added_count(); global_value.unlock(); local_value._num_added -= interval.added_count(); interval.clear(); } interval.add64(latency); ++local_value._num_added; } private: int64_t _latency; }; Percentile::Percentile() : _combiner(NULL), _sampler(NULL) { _combiner = new combiner_type; } Percentile::~Percentile() { // Have to destroy sampler first to avoid the race between destruction and // sampler if (_sampler != NULL) { _sampler->destroy(); _sampler = NULL; } delete _combiner; } Percentile::value_type Percentile::reset() { return _combiner->reset_all_agents(); } Percentile::value_type Percentile::get_value() const { return _combiner->combine_agents(); } Percentile &Percentile::operator<<(int64_t latency) { agent_type* agent = _combiner->get_or_create_tls_agent(); if (BAIDU_UNLIKELY(!agent)) { LOG(FATAL) << "Fail to create agent"; return *this; } if (latency < 0) { // we don't check overflow(of uint32) in percentile because the // overflowed value which is included in last range does not affect // overall distribution of other values too much. if (!_debug_name.empty()) { LOG(WARNING) << "Input=" << latency << " to `" << _debug_name << "' is negative, drop"; } else { LOG(WARNING) << "Input=" << latency << " to Percentile(" << (void*)this << ") is negative, drop"; } return *this; } agent->merge_global(AddLatency(latency)); return *this; } } // namespace detail } // namespace bvar