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.
36 template <typename T>
37 class Histogram;
38 
39 /**
40  * An individual bin of histogram data.
41  */
42 template <typename T>
43 class HistogramBin {
44 public:
45 
46     /**
47      * Get a HistogramBin covering [s, e)
48      */
HistogramBin(T s, T e)49     HistogramBin(T s, T e) : _count(0), _start(s), _end(e) {}
50 
51     /**
52      * The starting value of this histogram bin (inclusive).
53      */
start() const54     T start() const { return _start; }
55 
56     /**
57      * The ending value of this histogram bin (exclusive).
58      */
end() const59     T end() const { return _end; }
60 
61     /**
62      * The count in this bin.
63      */
count() const64     size_t count() const { return _count.load(); }
65 
66 private:
67     friend class Histogram<T>;
68 
69     /**
70      * Increment this bin by the given amount.
71      */
incr(size_t amount)72     void incr(size_t amount) {
73         _count.fetch_add(amount);
74     }
75 
76     /**
77      * Set a specific value for this bin.
78      */
set(size_t val)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      */
accepts(T value)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  */
104 template <typename T>
105 class HistogramBinSampleAdder {
106 public:
HistogramBinSampleAdder()107     HistogramBinSampleAdder() {}
operator ()(size_t n, const HistogramBin<T> *b)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  */
115 template <typename T>
116 class GrowingWidthGenerator {
117 public:
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      */
GrowingWidthGenerator(T start, T width, double growth=1.0)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      */
operator ()()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 
140 private:
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  */
150 template <typename T>
151 class FixedInputGenerator {
152 public:
153 
154     /**
155      * Get a FixedInputGenerator with the given sequence of bin starts.
156      */
FixedInputGenerator(std::vector<T> &input)157     FixedInputGenerator(std::vector<T> &input)
158         : it(input.begin()), end(input.end()) {}
159 
operator ()()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     }
168 private:
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  */
176 template <typename T>
177 class ExponentialGenerator {
178 public:
179 
180     /**
181      * Get a FixedInputGenerator with the given sequence of bin starts.
182      */
ExponentialGenerator(uint64_t start, double power)183     ExponentialGenerator(uint64_t start, double power)
184         : _start(start), _power(power) {}
185 
operator ()()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     }
191 private:
192     uint64_t _start;
193     double   _power;
194 };
195 
196 /**
197  * Comparator for finding a histogram bin to hold a value.
198  */
199 template <typename T>
200 class BinCompare {
201 public:
202 
BinCompare()203     BinCompare() {}
204 
operator ()(T t, HistogramBin<T> *b)205     bool operator() (T t, HistogramBin<T> *b) {
206         return t < b->end();
207     }
208 };
209 
210 /**
211  * A Histogram.
212  */
213 template <typename T>
214 class Histogram {
215 public:
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>
Histogram(const G &generator, size_t n=30)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      */
Histogram(size_t n=30)233     Histogram(size_t n=30) : bins(n) {
234         ExponentialGenerator<T> generator(0, 2.0);
235         fill(generator);
236     }
237 
~Histogram()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      */
add(T amount, size_t count=1)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      */
getBin(T amount)258     const HistogramBin<T>* getBin(T amount) {
259         return findBin(amount);
260     }
261 
262     /**
263      * Set all bins to 0.
264      */
reset()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      */
total()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:
iterator(typename std::vector<HistogramBin<T>*>::iterator x)286         iterator(typename std::vector<HistogramBin<T>*>::iterator x) :p(x) {}
iterator(const iterator& mit)287         iterator(const iterator& mit) : p(mit.p) {}
operator ++()288         iterator& operator++() {++p;return *this;}
operator ++(int)289         iterator& operator++(int) {iterator tmp(*this); operator++(); return tmp;}
operator ==(const iterator& rhs)290         bool operator==(const iterator& rhs) {return p==rhs.p;}
operator !=(const iterator& rhs)291         bool operator!=(const iterator& rhs) {return p!=rhs.p;}
operator *()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      */
begin() const301     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      */
end() const308     iterator end() const {
309         return iterator(const_cast<Histogram<T>*>(this)->bins.end());
310     }
311 
312 private:
313 
314     template <typename G>
fill(G &generator)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.
verify()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 
findBin(T amount)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  */
380 class BlockTimer {
381 public:
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      */
BlockTimer(Histogram<hrtime_t> *d, const char *n=NULL, std::ostream *o=NULL)389     BlockTimer(Histogram<hrtime_t> *d, const char *n=NULL, std::ostream *o=NULL)
390         : dest(d), start(gethrtime()), name(n), out(o) {}
391 
~BlockTimer()392     ~BlockTimer() {
393         hrtime_t spent(gethrtime() - start);
394         dest->add(spent / 1000);
395         log(spent, name, out);
396     }
397 
log(hrtime_t spent, const char *name, std::ostream *o)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 
404 private:
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.
412 template <typename T>
operator <<(std::ostream &out, const HistogramBin<T> &b)413 std::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
419 template <typename T>
operator <<(std::ostream &out, const std::vector<HistogramBin<T>*> &b)420 std::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.
434 template <typename T>
operator <<(std::ostream &out, const Histogram<T> &b)435 std::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