1/* -*- Mode: C++; tab-width: 4; c-basic-offset: 4; indent-tabs-mode: nil -*- */
2/*
3 *     Copyright 2010 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#ifndef SRC_HISTO_H_
19#define SRC_HISTO_H_ 1
20
21#include "config.h"
22
23#include <algorithm>
24#include <cmath>
25#include <functional>
26#include <iterator>
27#include <limits>
28#include <numeric>
29#include <ostream>
30#include <vector>
31
32#include "atomic.h"
33#include "common.h"
34
35// Forward declaration.
36template <typename T>
37class Histogram;
38
39/**
40 * An individual bin of histogram data.
41 */
42template <typename T>
43class HistogramBin {
44public:
45
46    /**
47     * Get a HistogramBin covering [s, e)
48     */
49    HistogramBin(T s, T e) : _count(0), _start(s), _end(e) {}
50
51    /**
52     * The starting value of this histogram bin (inclusive).
53     */
54    T start() const { return _start; }
55
56    /**
57     * The ending value of this histogram bin (exclusive).
58     */
59    T end() const { return _end; }
60
61    /**
62     * The count in this bin.
63     */
64    size_t count() const { return _count.load(); }
65
66private:
67    friend class Histogram<T>;
68
69    /**
70     * Increment this bin by the given amount.
71     */
72    void incr(size_t amount) {
73        _count.fetch_add(amount);
74    }
75
76    /**
77     * Set a specific value for this bin.
78     */
79    void set(size_t val) {
80        _count.store(val);
81    }
82
83    /**
84     * Does this bin contain the given value?
85     *
86     * @param value a value that may be within this bin's boundaries
87     * @return true if this value is counted within this bin
88     */
89    bool accepts(T value) {
90        return value >= _start &&
91            (value < _end || value == std::numeric_limits<T>::max());
92    }
93
94    AtomicValue<size_t> _count;
95    T              _start;
96    T              _end;
97
98    DISALLOW_COPY_AND_ASSIGN(HistogramBin);
99};
100
101/**
102 * Helper function object to sum sample.
103 */
104template <typename T>
105class HistogramBinSampleAdder {
106public:
107    HistogramBinSampleAdder() {}
108    size_t operator() (size_t n, const HistogramBin<T> *b) { return n + b->count(); }
109};
110
111/**
112 * A bin generator that generates buckets of a width that may increase
113 * in size a fixed growth amount over iterations.
114 */
115template <typename T>
116class GrowingWidthGenerator {
117public:
118
119    /**
120     * Construct a growing width generator.
121     *
122     * @param start the starting point for this generator (inclusive)
123     * @param width the starting width for this generator
124     * @param growth how far the width should increase each time
125     */
126    GrowingWidthGenerator(T start, T width, double growth=1.0)
127        : _growth(growth), _start(start), _width(static_cast<double>(width)) {}
128
129    /**
130     * Generate the next bin.
131     */
132    HistogramBin<T>* operator () () {
133        HistogramBin<T>* rv = new HistogramBin<T>(_start,
134                                                  _start + static_cast<T>(_width));
135        _start += static_cast<T>(_width);
136        _width = _width * _growth;
137        return rv;
138    }
139
140private:
141    double _growth;
142    T      _start;
143    double _width;
144};
145
146/**
147 * A bin generator that generates buckets from a sequence of T where
148 * each bin is from [v[n], v[n+1]).
149 */
150template <typename T>
151class FixedInputGenerator {
152public:
153
154    /**
155     * Get a FixedInputGenerator with the given sequence of bin starts.
156     */
157    FixedInputGenerator(std::vector<T> &input)
158        : it(input.begin()), end(input.end()) {}
159
160    HistogramBin<T>* operator () () {
161        cb_assert(it != end);
162        T current = *it;
163        ++it;
164        cb_assert(it != end);
165        T next = *it;
166        return new HistogramBin<T>(current, next);
167    }
168private:
169    typename std::vector<T>::iterator it;
170    typename std::vector<T>::iterator end;
171};
172
173/**
174 * A bin generator that [n^i, n^(i+1)).
175 */
176template <typename T>
177class ExponentialGenerator {
178public:
179
180    /**
181     * Get a FixedInputGenerator with the given sequence of bin starts.
182     */
183    ExponentialGenerator(uint64_t start, double power)
184        : _start(start), _power(power) {}
185
186    HistogramBin<T>* operator () () {
187        T start = static_cast<T>(std::pow(_power, static_cast<double>(_start)));
188        T end = static_cast<T>(std::pow(_power, static_cast<double>(++_start)));
189        return new HistogramBin<T>(start, end);
190    }
191private:
192    uint64_t _start;
193    double   _power;
194};
195
196/**
197 * Comparator for finding a histogram bin to hold a value.
198 */
199template <typename T>
200class BinCompare {
201public:
202
203    BinCompare() {}
204
205    bool operator() (T t, HistogramBin<T> *b) {
206        return t < b->end();
207    }
208};
209
210/**
211 * A Histogram.
212 */
213template <typename T>
214class Histogram {
215public:
216
217    /**
218     * Build a histogram.
219     *
220     * @param generator a generator for the bins within this bucket
221     * @param n how many bins this histogram should contain
222     */
223    template <typename G>
224    Histogram(const G &generator, size_t n=30) : bins(n) {
225        fill(generator);
226    }
227
228    /**
229     * Build a default histogram.
230     *
231     * @param n how many bins this histogram should contain.
232     */
233    Histogram(size_t n=30) : bins(n) {
234        ExponentialGenerator<T> generator(0, 2.0);
235        fill(generator);
236    }
237
238    ~Histogram() {
239        for (typename std::vector<HistogramBin<T>*>::iterator it = bins.begin();
240             it != bins.end(); ++it) {
241            delete *it;
242        }
243    }
244
245    /**
246     * Add a value to this histogram.
247     *
248     * @param amount the size of the thing being added
249     * @param count the quantity at this size being added
250     */
251    void add(T amount, size_t count=1) {
252        findBin(amount)->incr(count);
253    }
254
255    /**
256     * Get the bin servicing the given sized input.
257     */
258    const HistogramBin<T>* getBin(T amount) {
259        return findBin(amount);
260    }
261
262    /**
263     * Set all bins to 0.
264     */
265    void reset() {
266        std::for_each(bins.begin(), bins.end(),
267                      std::bind2nd(std::mem_fun(&HistogramBin<T>::set), 0));
268    }
269
270    /**
271     * Get the total number of samples counted.
272     *
273     * This is the sum of all counts in each bin.
274     */
275    size_t total() {
276        HistogramBinSampleAdder<T> a;
277        return std::accumulate(begin(), end(), 0, a);
278    }
279
280    /**
281     * A HistogramBin iterator.
282     */
283    class iterator  : public std::iterator<std::forward_iterator_tag,
284                                           const Histogram<T>*> {
285    public:
286        iterator(typename std::vector<HistogramBin<T>*>::iterator x) :p(x) {}
287        iterator(const iterator& mit) : p(mit.p) {}
288        iterator& operator++() {++p;return *this;}
289        iterator& operator++(int) {iterator tmp(*this); operator++(); return tmp;}
290        bool operator==(const iterator& rhs) {return p==rhs.p;}
291        bool operator!=(const iterator& rhs) {return p!=rhs.p;}
292        const HistogramBin<T>* operator*() {return *p;}
293    private:
294        typename std::vector<HistogramBin<T>*>::iterator p;
295        friend class Histogram<T>;
296    };
297
298    /**
299     * Get an iterator from the beginning of a histogram bin.
300     */
301    iterator begin() const {
302        return iterator(const_cast<Histogram<T>*>(this)->bins.begin());
303    }
304
305    /**
306     * Get the iterator at the end of the histogram bin.
307     */
308    iterator end() const {
309        return iterator(const_cast<Histogram<T>*>(this)->bins.end());
310    }
311
312private:
313
314    template <typename G>
315    void fill(G &generator) {
316        std::generate(bins.begin(), bins.end(), generator);
317
318        // If there will not naturally be one, create a bin for the
319        // smallest possible value
320        if (bins.front()->start() > std::numeric_limits<T>::min()) {
321            bins.insert(bins.begin(),
322                        new HistogramBin<T>(std::numeric_limits<T>::min(),
323                                            bins.front()->start()));
324        }
325
326        // Also create one reaching to the largest possible value
327        if (bins.back()->end() < std::numeric_limits<T>::max()) {
328            bins.push_back(new HistogramBin<T>(bins.back()->end(),
329                                               std::numeric_limits<T>::max()));
330        }
331
332        verify();
333    }
334
335    // This validates that we're sorted and have no gaps or overlaps.
336    void verify() {
337        T prev = std::numeric_limits<T>::min();
338        typename std::vector<HistogramBin<T>*>::iterator it;
339        int pos(0);
340        for (it = bins.begin(); it != bins.end(); ++it) {
341            if ((*it)->start() != prev) {
342                std::cerr << "Expected " << (*it)->start() << " == " << prev
343                          << " at pos " << pos << std::endl;
344                abort();
345            }
346            cb_assert((*it)->start() == prev);
347            prev = (*it)->end();
348            ++pos;
349        }
350        cb_assert(prev == std::numeric_limits<T>::max());
351    }
352
353    HistogramBin<T> *findBin(T amount) {
354        HistogramBin<T> *rv(NULL);
355        if (amount == std::numeric_limits<T>::max()) {
356            rv = bins.back();
357        } else {
358            typename std::vector<HistogramBin<T>*>::iterator it;
359            BinCompare<T> binCompare;
360            it = std::upper_bound(bins.begin(), bins.end(), amount, binCompare);
361            cb_assert(it != bins.end());
362            cb_assert((*it)->accepts(amount));
363            rv = *it;
364        }
365        return rv;
366    }
367
368    template <typename Ttype>
369    friend std::ostream& operator<< (std::ostream& out,
370                                     const Histogram<Ttype> &b);
371
372    std::vector<HistogramBin<T>*> bins;
373
374    DISALLOW_COPY_AND_ASSIGN(Histogram);
375};
376
377/**
378 * Times blocks automatically and records the values in a histogram.
379 */
380class BlockTimer {
381public:
382
383    /**
384     * Get a BlockTimer that will store its values in the given
385     * histogram.
386     *
387     * @param d the histogram that will hold the result
388     */
389    BlockTimer(Histogram<hrtime_t> *d, const char *n=NULL, std::ostream *o=NULL)
390        : dest(d), start(gethrtime()), name(n), out(o) {}
391
392    ~BlockTimer() {
393        hrtime_t spent(gethrtime() - start);
394        dest->add(spent / 1000);
395        log(spent, name, out);
396    }
397
398    static inline void log(hrtime_t spent, const char *name, std::ostream *o) {
399        if (o && name) {
400            *o << name << "\t" << spent << "\n";
401        }
402    }
403
404private:
405    Histogram<hrtime_t> *dest;
406    hrtime_t             start;
407    const char          *name;
408    std::ostream        *out;
409};
410
411// How to print a bin.
412template <typename T>
413std::ostream& operator <<(std::ostream &out, const HistogramBin<T> &b) {
414    out << "[" << b.start() << ", " << b.end() << ") = " << b.count();
415    return out;
416}
417
418// How to print a vector histogram bin pointers
419template <typename T>
420std::ostream& operator <<(std::ostream &out, const std::vector<HistogramBin<T>*> &b) {
421    bool needComma(false);
422    for (typename std::vector<HistogramBin<T>*>::const_iterator it = b.begin();
423         it != b.end(); ++it) {
424        if (needComma) {
425            out << ", ";
426        }
427        out << **it;
428        needComma = true;
429    }
430    return out;
431}
432
433// How to print a histogram.
434template <typename T>
435std::ostream& operator <<(std::ostream &out, const Histogram<T> &b) {
436    out << "{Histogram: " << b.bins << "}";
437    return out;
438}
439
440#endif  // SRC_HISTO_H_
441