xref: /6.6.0/platform/include/platform/histogram.h (revision 8c74fe5e)
1/* -*- Mode: C++; tab-width: 4; c-basic-offset: 4; indent-tabs-mode: nil -*- */
2/*
3 *     Copyright 2015 Couchbase, Inc
4 *
5 *   Licensed under the Apache License, Version 2.0 (the "License");
6 *   you may not use this file except in compliance with the License.
7 *   You may obtain a copy of the License at
8 *
9 *       http://www.apache.org/licenses/LICENSE-2.0
10 *
11 *   Unless required by applicable law or agreed to in writing, software
12 *   distributed under the License is distributed on an "AS IS" BASIS,
13 *   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 *   See the License for the specific language governing permissions and
15 *   limitations under the License.
16 */
17
18#pragma once
19
20#include <platform/visibility.h>
21#include <relaxed_atomic.h>
22
23#include <algorithm>
24#include <chrono>
25#include <cmath>
26#include <functional>
27#include <iostream>
28#include <memory>
29#include <numeric>
30#include <vector>
31
32// Custom microseconds duration used for measuring histogram stats.
33// Stats will never be negative, so an unsigned Rep is used.
34using UnsignedMicroseconds = std::chrono::duration<uint64_t, std::micro>;
35
36namespace cb {
37// std::chrono::durations are not supported by std::numeric_limits by default.
38// This struct acts as a traits class for durations. It should be specialised
39// for individual durations and implement a required subset of methods from
40// std::numeric_limits
41template <typename T>
42struct duration_limits {};
43
44template <>
45struct duration_limits<UnsignedMicroseconds> {
46    static UnsignedMicroseconds max() {
47        return UnsignedMicroseconds::max();
48    }
49    static UnsignedMicroseconds min() {
50        return UnsignedMicroseconds::min();
51    }
52};
53}
54
55// Forward declaration.
56template <typename T, template <class> class Limits>
57class Histogram;
58
59/**
60 * An individual bin of histogram data.
61 *
62 * @tparam T type of the histogram bin value.
63 * @tparam Limits traits class which provides min() and max() static
64 *         member functions which specify the min and max value of T.
65 */
66template <typename T, template <class> class Limits = std::numeric_limits>
67class HistogramBin {
68public:
69
70    /**
71     * Get a HistogramBin covering [s, e)
72     */
73    HistogramBin(T s, T e)
74        : _count(0),
75          _start(s),
76          _end(e) { }
77
78    HistogramBin(const HistogramBin& other) = delete;
79
80    /**
81     * The starting value of this histogram bin (inclusive).
82     */
83    T start() const { return _start; }
84
85    /**
86     * The ending value of this histogram bin (exclusive).
87     */
88    T end() const { return _end; }
89
90    /**
91     * The count in this bin.
92     */
93    size_t count() const { return _count.load(); }
94
95private:
96    friend class Histogram<T, Limits>;
97
98    /**
99     * Increment this bin by the given amount.
100     */
101    void incr(size_t amount) {
102        _count.fetch_add(amount);
103    }
104
105    /**
106     * Set a specific value for this bin.
107     */
108    void set(size_t val) {
109        _count.store(val);
110    }
111
112    /**
113     * Does this bin contain the given value?
114     *
115     * @param value a value that may be within this bin's boundaries
116     * @return true if this value is counted within this bin
117     */
118    bool accepts(T value) {
119        return value >= _start && (value < _end || value == Limits<T>::max());
120    }
121
122    cb::RelaxedAtomic<size_t> _count;
123    T _start;
124    T _end;
125};
126
127/**
128 * Helper function object to sum sample.
129 */
130template <typename T, template <class> class Limits>
131class HistogramBinSampleAdder {
132public:
133    HistogramBinSampleAdder() { }
134
135    size_t operator()(size_t n,
136                      const typename Histogram<T, Limits>::value_type& b) {
137        return n + b->count();
138    }
139};
140
141/**
142 * A bin generator that generates buckets of a width that may increase
143 * in size a fixed growth amount over iterations.
144 */
145template <typename T, template <class> class Limits = std::numeric_limits>
146class GrowingWidthGenerator {
147public:
148
149    /**
150     * Construct a growing width generator.
151     *
152     * @param start the starting point for this generator (inclusive)
153     * @param width the starting width for this generator
154     * @param growth how far the width should increase each time
155     */
156    GrowingWidthGenerator(T start, T width, double growth = 1.0)
157        : _growth(growth),
158          _start(start) {
159        // Dividing two durations returns a value of the underlying Rep.
160        _width = width / T(1);
161    }
162
163    /**
164     * Generate the next bin.
165     */
166    typename Histogram<T, Limits>::value_type operator()() {
167        auto rv = std::make_unique<typename Histogram<T, Limits>::bin_type>(
168                _start, _start + static_cast<T>(uint64_t(_width)));
169        _start += static_cast<T>(uint64_t(_width));
170        _width = _width * _growth;
171        return rv;
172    }
173
174private:
175    double _growth;
176    T _start;
177    double _width;
178};
179
180/**
181 * A bin generator that [n^i, n^(i+1)).
182 */
183template <typename T, template <class> class Limits = std::numeric_limits>
184class ExponentialGenerator {
185public:
186
187    /**
188     * Get a FixedInputGenerator with the given sequence of bin starts.
189     */
190    ExponentialGenerator(uint64_t start, double power)
191        : _start(start),
192          _power(power) { }
193
194    typename Histogram<T, Limits>::value_type operator()() {
195        T start = T(uint64_t(std::pow(_power, double(_start))));
196        T end = T(uint64_t(std::pow(_power, double(++_start))));
197        return std::make_unique<typename Histogram<T, Limits>::bin_type>(start,
198                                                                         end);
199    }
200
201private:
202    uint64_t _start;
203    double _power;
204};
205
206// UnsignedMicroseconds stream operator required for Histogram::verify()
207// so the type can be printed.
208inline std::ostream& operator<<(std::ostream& os,
209                                const UnsignedMicroseconds& ms) {
210    os << ms.count();
211    return os;
212}
213
214/**
215 * A Histogram.
216 */
217template <typename T, template <class> class Limits = std::numeric_limits>
218class Histogram {
219public:
220    using bin_type = HistogramBin<T, Limits>;
221    using value_type = std::unique_ptr<bin_type>;
222    using container_type = std::vector<value_type>;
223    using const_iterator = typename container_type::const_iterator;
224    using iterator = typename container_type::const_iterator;
225
226    /**
227     * Build a histogram.
228     *
229     * @param generator a generator for the bins within this bucket
230     * @param n how many bins this histogram should contain
231     */
232    template<typename G>
233    Histogram(const G& generator, size_t n = 30)
234        : bins(n) {
235        if (n < 1){
236            throw std::invalid_argument("Histogram must have at least 1 bin");
237        }
238        fill(generator);
239    }
240
241    /**
242     * Build a default histogram.
243     *
244     * @param n how many bins this histogram should contain.
245     */
246    Histogram(size_t n = 30)
247        : Histogram(ExponentialGenerator<T, Limits>(0, 2.0), n) {
248    }
249
250    //Deleted to avoid copying large objects
251    Histogram(const Histogram& other) = delete;
252
253    Histogram(Histogram&& other) = default;
254
255    Histogram& operator=(Histogram&& other) = default;
256
257    Histogram& operator=(const Histogram& other) = delete;
258
259    /**
260     * Add a value to this histogram.
261     *
262     * Note: defined non-inline to reduce the code bloat from recording
263     *       histogram values - the inline size of this method is non-trivial.
264     *       If you get want to add a new instantiation of this class; check
265     *       the explicit template definition in histogram.cc.
266     *
267     * @param amount the size of the thing being added
268     * @param count the quantity at this size being added
269     */
270    void add(T amount, size_t count = 1);
271
272    /**
273     * Get the bin servicing the given sized input.
274     */
275    const HistogramBin<T, Limits>* getBin(T amount) {
276        return findBin(amount)->get();
277    }
278
279    /**
280     * Set all bins to 0.
281     */
282    void reset();
283
284    /**
285     * Get the total number of samples counted.
286     *
287     * This is the sum of all counts in each bin.
288     */
289    size_t total();
290
291    /**
292     * Get an iterator from the beginning of a histogram bin.
293     */
294    const_iterator begin() const {
295        return bins.begin();
296    }
297
298    iterator begin() {
299        return bins.begin();
300    }
301
302    /**
303     * Get the iterator at the end of the histogram bin.
304     */
305    const_iterator end() const {
306        return bins.end();
307    }
308
309    iterator end() {
310        return bins.end();
311    }
312
313    size_t getMemFootPrint() const {
314        return sizeof(Histogram) + ((sizeof(bin_type) +
315                sizeof(value_type)) * bins.size());
316    }
317
318private:
319
320    template<typename G>
321    void fill(G& generator) {
322        std::generate(bins.begin(), bins.end(), generator);
323
324        // If there will not naturally be one, create a bin for the
325        // smallest possible value
326        if (bins.front()->start() > Limits<T>::min()) {
327            bins.insert(bins.begin(),
328                        std::make_unique<bin_type>(Limits<T>::min(),
329                                                   bins.front()->start()));
330        }
331
332        // Also create one reaching to the largest possible value
333        if (bins.back()->end() < Limits<T>::max()) {
334            bins.push_back(std::make_unique<bin_type>(bins.back()->end(),
335                                                      Limits<T>::max()));
336        }
337
338        verify();
339    }
340
341    // This validates that we're sorted and have no gaps or overlaps. Returns
342    // true if tests pass, else false.
343    bool verify();
344
345    /* Finds the bin containing the specified amount. Returns iterator to end
346     * () if not found
347     */
348    iterator findBin(T amount);
349
350    template <typename type, template <class> class limits>
351    friend std::ostream& operator<<(std::ostream& out,
352                                    const Histogram<type, limits>& b);
353
354    container_type bins;
355};
356
357/**
358 * Histogram of durations measured in microseconds.
359 *
360 * Typesafe; calling add() with any chrono::duration specialization (seconds,
361 * milliseconds etc) will perform any necessary conversion.
362 */
363using MicrosecondHistogram =
364        Histogram<UnsignedMicroseconds, cb::duration_limits>;
365
366/**
367 * Adapter class template to assist in recording the duration of an event into
368 * Histogram T that has an add method T::add(std::chrono::microseconds v);
369 * which don't have start() / stop() methods.
370 *
371 * This class will record the startTime when start() is called; then when end()
372 * is called it will calculate the duration and pass that to Histogram.
373 */
374 template<typename T>
375class MicrosecondStopwatch {
376public:
377    MicrosecondStopwatch(T& histogram)
378        : histogram(histogram) {
379    }
380
381    void start(std::chrono::steady_clock::time_point start_) {
382        startTime = start_;
383    }
384
385    void stop(std::chrono::steady_clock::time_point end) {
386        const auto spent = end - startTime;
387        histogram.add(std::chrono::duration_cast<std::chrono::microseconds>(spent));
388    }
389
390private:
391    T& histogram;
392    std::chrono::steady_clock::time_point startTime;
393};
394
395/**
396 * Times blocks automatically and records the values in a histogram.
397 *
398 * If THRESHOLD_MS is greater than zero, then any blocks taking longer than
399 * THRESHOLD_MS to execute will be reported to stderr.
400 * Note this requires that a name is specified for the BlockTimer.
401 */
402template<typename HISTOGRAM, uint64_t THRESHOLD_MS>
403class GenericBlockTimer {
404public:
405
406    /**
407     * Get a BlockTimer that will store its values in the given
408     * histogram.
409     *
410     * @param d the histogram that will hold the result.
411     *        If it is 'nullptr', the BlockTimer is disabled so that
412     *        both constructor and destructor will do nothing.
413     * @param n the name to give the histogram, used when logging slow block
414     *        execution to the log.
415     */
416    GenericBlockTimer(HISTOGRAM* d,
417                      const char* n = nullptr,
418                      std::ostream* o = nullptr)
419        : dest(d),
420          start((dest) ? std::chrono::steady_clock::now()
421                       : std::chrono::steady_clock::time_point()),
422          name(n),
423          out(o) {
424    }
425
426    ~GenericBlockTimer() {
427        if (dest) {
428            auto spent = std::chrono::steady_clock::now() - start;
429            dest->add(std::chrono::duration_cast<std::chrono::microseconds>(spent));
430            log(spent, name, out);
431        }
432    }
433
434    static void log(std::chrono::steady_clock::duration spent,
435                    const char* name,
436                    std::ostream* o) {
437        if (o && name) {
438            *o << name << "\t" << spent.count() << "\n";
439        }
440        if (THRESHOLD_MS > 0) {
441            const auto msec =
442                    std::make_unsigned<std::chrono::steady_clock::rep>::type(
443                            std::chrono::duration_cast<
444                                    std::chrono::milliseconds>(spent)
445                                    .count());
446            if (name != nullptr && msec > THRESHOLD_MS) {
447                std::cerr << "BlockTimer<" << name
448                          << "> Took too long: " << msec << "ms" << std::endl;
449            }
450        }
451    }
452
453private:
454    HISTOGRAM* dest;
455    std::chrono::steady_clock::time_point start;
456    const char* name;
457    std::ostream* out;
458};
459
460/* Convenience specialization which only records in a MicrosecondHistogram;
461 * doesn't log slow blocks.
462 */
463typedef GenericBlockTimer<MicrosecondHistogram, 0> BlockTimer;
464
465// How to print a bin.
466template <typename T, template <class> class Limits>
467std::ostream& operator<<(std::ostream& out, const HistogramBin<T, Limits>& b) {
468    out << "[" << b.start() << ", " << b.end() << ") = " << b.count();
469    return out;
470}
471
472// How to print a histogram.
473template <typename T, template <class> class Limits>
474std::ostream& operator<<(std::ostream& out, const Histogram<T, Limits>& b) {
475    out << "{Histogram: ";
476    bool needComma(false);
477    for (const auto& bin : b.bins) {
478        if (needComma) {
479            out << ", ";
480        }
481        out << (*bin);
482        needComma = true;
483    }
484    out << "}";
485    return out;
486}
487