SampleSet -> HistogramSamples (will be reused by SparseHistogram)

base/metrics/histogram.h

 // Copyright (c) 2012 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 // Histogram is an object that aggregates statistics, and can summarize them in
 // various forms, including ASCII graphical, HTML, and numerically (as a
 // vector of numbers corresponding to each of the aggregating buckets).
 
 // It supports calls to accumulate either time intervals (which are processed
 // as integral number of milliseconds), or arbitrary integral units.
@@ skipping 50 matching lines @@
 #include <map>
 #include <string>
 #include <vector>
 
 #include "base/atomicops.h"
 #include "base/base_export.h"
 #include "base/basictypes.h"
 #include "base/compiler_specific.h"
 #include "base/gtest_prod_util.h"
 #include "base/logging.h"
+#include "base/memory/scoped_ptr.h"
 #include "base/metrics/bucket_ranges.h"
 #include "base/metrics/histogram_base.h"
+#include "base/metrics/histogram_samples.h"
 #include "base/time.h"
 
 class Pickle;
 class PickleIterator;
 
 namespace base {
 
 class Lock;
 //------------------------------------------------------------------------------
 // Histograms are often put in areas where they are called many many times, and
@@ skipping 254 matching lines @@
             base::Histogram::kUmaTargetedHistogramFlag))
 
 //------------------------------------------------------------------------------
 
 class BooleanHistogram;
 class BucketRanges;
 class CustomHistogram;
 class Histogram;
 class LinearHistogram;
 
+class BASE_EXPORT_PRIVATE BucketHistogramSamples : public HistogramSamples {
+ public:
+  explicit BucketHistogramSamples(const BucketRanges* bucket_ranges);
+  virtual ~BucketHistogramSamples();
+
+  // Implements HistogramSamples:

[Ilya Sherman, 2012/08/29 08:48:16]

nit: This is typically written as "HistogramSamples implementation:" or just
"HistogramSamples:"

[kaiwang, 2012/08/29 22:42:16]

Done.

+  virtual void Accumulate(HistogramBase::Sample value,
+                          HistogramBase::Count count) OVERRIDE;
+  virtual HistogramBase::Count GetCount(
+      HistogramBase::Sample value) const OVERRIDE;
+  virtual HistogramBase::Count TotalCount() const OVERRIDE;
+  virtual scoped_ptr<SampleCountIterator> Iterator() const OVERRIDE;
+
+  // Get count of a specific bucket.
+  HistogramBase::Count GetCountFromBucketIndex(size_t bucket_index) const;
+
+ protected:
+  virtual bool AddSubtractImpl(SampleCountIterator* iter,
+                               bool is_add) OVERRIDE;
+
+  static size_t GetBucketIndex(HistogramBase::Sample value,
+                               const BucketRanges* bucket_ranges);

[Ilya Sherman, 2012/08/29 08:48:16]

nit: Why is this a static function rather than an instance method?  It looks
like you always pass |bucket_ranges_| as the second parameter.

[Ilya Sherman, 2012/08/29 08:48:16]

Can this be private?

[kaiwang, 2012/08/29 22:42:16]

Will change it to private.

For static/non-static, there's a coding best practice(inside and outside of
google) to define private functions that does not change object state all
static. Unfortunately I can not find the internal pages at hand.

The good thing about static is, it does not depends on the whole object (no this
pointer). So it's much easier for code reader to understand what is going on if
you pass the
members that affect this method. So basically static function has less
dependency then non-static functions.

Another reason is, making private functions static does not help encapsulation,
because external client can not call these functions. While many public
functions has to be non-static, because external client need them to change
object state.

I do find some design docs of another project mentioning this. It's the maps
frontend testing design doc:
https://www.corp.google.com/eng/designdocs/maps/testing.html#s13

[Ilya Sherman, 2012/08/29 23:41:27]

As discussed offline, Chromium code usually prefers free functions hidden in the
implementation file's anonymous namespace to private static functions.

Also, please keep in mind that this code review site is used by more than just
Googlers, so it is generally not appropriate to link to internal-only pages,
including documentation.  As much as possible, all relevant resources should be
made equally accessible to all Chromium developers.  (In this case it's not such
a big issue, since you explained the contents fairly clearly, and they are not
of a sensitive nature.  Just something to keep in mind.)

[kaiwang, 2012/08/30 03:13:22]

Sorry I forgot a reason to make it a non-static member: subclass can override it
in a more efficient way. E.g. LinearHistogram should be able to directly
calculate the index.
Changed it back to non-static.

+
+ private:
+  FRIEND_TEST_ALL_PREFIXES(HistogramTest, CorruptSampleCounts);
+
+  std::vector<HistogramBase::Count> counts_;
+
+  // Shares the same BucketRanges with Histogram object.
+  const BucketRanges* const bucket_ranges_;
+
+  DISALLOW_COPY_AND_ASSIGN(BucketHistogramSamples);
+};
+
+class BASE_EXPORT_PRIVATE BucketHistogramSamplesIterator
+    : public SampleCountIterator {
+ public:
+  BucketHistogramSamplesIterator(
+      const std::vector<HistogramBase::Count>* counts,
+      const BucketRanges* bucket_ranges);
+
+  // Implements SampleCountIterator.
+  virtual bool Done() OVERRIDE;
+  virtual void Next() OVERRIDE;
+  virtual void Get(HistogramBase::Sample* min,
+                   HistogramBase::Sample* max,
+                   HistogramBase::Count* count) OVERRIDE;
+ private:
+  void ForwardToNextNonemptyBucket();
+
+  const std::vector<HistogramBase::Count>* counts_;
+  const BucketRanges* bucket_ranges_;
+
+  int index_;
+  bool is_done_;
+};
+
 class BASE_EXPORT Histogram : public HistogramBase {
  public:
   // Initialize maximum number of buckets in histograms as 16,384.
   static const size_t kBucketCount_MAX;
 
   typedef std::vector<Count> Counts;
 
   // These enums are used to facilitate deserialization of renderer histograms
   // into the browser.
   enum ClassType {
@@ skipping 19 matching lines @@
 
     NEVER_EXCEEDED_VALUE = 0x10
   };
 
   struct DescriptionPair {
     Sample sample;
     const char* description;  // Null means end of a list of pairs.
   };
 
   //----------------------------------------------------------------------------
-  // Statistic values, developed over the life of the histogram.
-
-  class BASE_EXPORT SampleSet {
-   public:
-    explicit SampleSet(size_t size);
-    SampleSet();
-    ~SampleSet();
-
-    void Resize(size_t size);
-
-    // Accessor for histogram to make routine additions.
-    void Accumulate(Sample value, Count count, size_t index);
-
-    // Accessor methods.
-    size_t size() const { return counts_.size(); }
-    Count counts(size_t i) const { return counts_[i]; }
-    Count TotalCount() const;
-    int64 sum() const { return sum_; }
-    int64 redundant_count() const { return redundant_count_; }
-
-    // Arithmetic manipulation of corresponding elements of the set.
-    void Add(const SampleSet& other);
-    void Subtract(const SampleSet& other);
-
-    bool Serialize(Pickle* pickle) const;
-    bool Deserialize(PickleIterator* iter);
-
-   protected:
-    // Actual histogram data is stored in buckets, showing the count of values
-    // that fit into each bucket.
-    Counts counts_;
-
-    // Save simple stats locally.  Note that this MIGHT get done in base class
-    // without shared memory at some point.
-    int64 sum_;         // sum of samples.
-
-   private:
-    // Allow tests to corrupt our innards for testing purposes.
-    FRIEND_TEST_ALL_PREFIXES(HistogramTest, CorruptSampleCounts);
-
-    // To help identify memory corruption, we reduntantly save the number of
-    // samples we've accumulated into all of our buckets.  We can compare this
-    // count to the sum of the counts in all buckets, and detect problems.  Note
-    // that due to races in histogram accumulation (if a histogram is indeed
-    // updated on several threads simultaneously), the tallies might mismatch,
-    // and also the snapshotting code may asynchronously get a mismatch (though
-    // generally either race based mismatch cause is VERY rare).
-    int64 redundant_count_;
-  };
-
-  //----------------------------------------------------------------------------
   // For a valid histogram, input should follow these restrictions:
   // minimum > 0 (if a minimum below 1 is specified, it will implicitly be
   //              normalized up to 1)
   // maximum > minimum
   // buckets > 2 [minimum buckets needed: underflow, overflow and the range]
   // Additionally,
   // buckets <= (maximum - minimum + 2) - this is to ensure that we don't have
   // more buckets than the range of numbers; having more buckets than 1 per
   // value in the range would be nonsensical.
   static Histogram* FactoryGet(const std::string& name,
@@ skipping 19 matching lines @@
   virtual void Add(Sample value) OVERRIDE;
 
   // This method is an interface, used only by BooleanHistogram.
   virtual void AddBoolean(bool value);
 
   // Accept a TimeDelta to increment.
   void AddTime(TimeDelta time) {
     Add(static_cast<int>(time.InMilliseconds()));
   }
 
-  void AddSampleSet(const SampleSet& sample);
+  void AddSamples(const HistogramSamples& samples);
+  bool AddSamples(PickleIterator* iter);

[Ilya Sherman, 2012/08/29 08:48:16]

Optional nit: Perhaps |AddSamplesFromPickle()|?

[kaiwang, 2012/08/29 22:42:16]

Done.

 
   // This method is an interface, used only by LinearHistogram.
   virtual void SetRangeDescriptions(const DescriptionPair descriptions[]);
 
   // The following methods provide graphical histogram displays.
   virtual void WriteHTMLGraph(std::string* output) const OVERRIDE;
   virtual void WriteAscii(std::string* output) const OVERRIDE;
 
   // Convenience methods for serializing/deserializing the histograms.
   // Histograms from Renderer process are serialized and sent to the browser.
   // Browser process reconstructs the histogram from the pickled version
   // accumulates the browser-side shadow copy of histograms (that mirror
   // histograms created in the renderer).
 
   // Serialize the given snapshot of a Histogram into a String. Uses
   // Pickle class to flatten the object.
   static std::string SerializeHistogramInfo(const Histogram& histogram,
-                                            const SampleSet& snapshot);
+                                            const HistogramSamples& snapshot);
 
   // The following method accepts a list of pickled histograms and
   // builds a histogram and updates shadow copy of histogram data in the
   // browser process.
   static bool DeserializeHistogramInfo(const std::string& histogram_info);
 
+  // This constant if for FindCorruption. Since snapshots of histograms are
+  // taken asynchronously relative to sampling, and out counting code currently
+  // does not prevent race conditions, it is pretty likely that we'll catch a
+  // redundant count that doesn't match the sample count.  We allow for a
+  // certain amount of slop before flagging this as an inconsistency. Even with
+  // an inconsistency, we'll snapshot it again (for UMA in about a half hour),
+  // so we'll eventually get the data, if it was not the result of a corruption.
+  static const int kCommonRaceBasedCountMismatch;
+
   // Check to see if bucket ranges, counts and tallies in the snapshot are
   // consistent with the bucket ranges and checksums in our histogram.  This can
   // produce a false-alarm if a race occurred in the reading of the data during
   // a SnapShot process, but should otherwise be false at all times (unless we
   // have memory over-writes, or DRAM failures).
-  virtual Inconsistencies FindCorruption(const SampleSet& snapshot) const;
+  virtual Inconsistencies FindCorruption(const HistogramSamples& samples) const;
 
   //----------------------------------------------------------------------------
   // Accessors for factory constuction, serialization and testing.
   //----------------------------------------------------------------------------
   virtual ClassType histogram_type() const;
   Sample declared_min() const { return declared_min_; }
   Sample declared_max() const { return declared_max_; }
   virtual Sample ranges(size_t i) const;
   virtual size_t bucket_count() const;
   const BucketRanges* bucket_ranges() const { return bucket_ranges_; }
 
   // Snapshot the current complete set of sample data.
   // Override with atomic/locked snapshot if needed.
-  virtual void SnapshotSample(SampleSet* sample) const;
+  virtual scoped_ptr<BucketHistogramSamples> SnapshotSamples() const;
 
   virtual bool HasConstructionArguments(Sample minimum,
                                         Sample maximum,
                                         size_t bucket_count);
  protected:
   // |bucket_count| and |ranges| should contain the underflow and overflow
   // buckets. See top comments for example.
   Histogram(const std::string& name,
             Sample minimum,
             Sample maximum,
@@ skipping 15 matching lines @@
 
   // Serialize the histogram's ranges to |*pickle|, returning true on success.
   // Most subclasses can leave this no-op implementation, but some will want to
   // override it, especially if the ranges cannot be re-derived from other
   // serialized parameters.
   virtual bool SerializeRanges(Pickle* pickle) const;
 
   // Method to override to skip the display of the i'th bucket if it's empty.
   virtual bool PrintEmptyBucket(size_t index) const;
 
-  //----------------------------------------------------------------------------
-  // Methods to override to create histogram with different bucket widths.
-  //----------------------------------------------------------------------------
-  // Find bucket to increment for sample value.
-  virtual size_t BucketIndex(Sample value) const;
   // Get normalized size, relative to the ranges(i).
   virtual double GetBucketSize(Count current, size_t i) const;
 
   // Return a string description of what goes in a given bucket.
   // Most commonly this is the numeric value, but in derived classes it may
   // be a name (or string description) given to the bucket.
   virtual const std::string GetAsciiBucketRange(size_t it) const;
 
-  //----------------------------------------------------------------------------
-  // Methods to override to create thread safe histogram.
-  //----------------------------------------------------------------------------
-  // Update all our internal data, including histogram
-  virtual void Accumulate(Sample value, Count count, size_t index);
-
  private:
   // Allow tests to corrupt our innards for testing purposes.
   FRIEND_TEST_ALL_PREFIXES(HistogramTest, CorruptBucketBounds);
   FRIEND_TEST_ALL_PREFIXES(HistogramTest, CorruptSampleCounts);
   FRIEND_TEST_ALL_PREFIXES(HistogramTest, Crc32SampleHash);
   FRIEND_TEST_ALL_PREFIXES(HistogramTest, Crc32TableTest);
 
   friend class StatisticsRecorder;  // To allow it to delete duplicates.
   friend class StatisticsRecorderTest;
 
   //----------------------------------------------------------------------------
   // Helpers for emitting Ascii graphic.  Each method appends data to output.
 
   void WriteAsciiImpl(bool graph_it,
                       const std::string& newline,
                       std::string* output) const;
 
-  // Find out how large the (graphically) the largest bucket will appear to be.
-  double GetPeakBucketSize(const SampleSet& snapshot) const;
+  // Find out how large (graphically) the largest bucket will appear to be.
+  double GetPeakBucketSize(const BucketHistogramSamples& samples) const;
 
   // Write a common header message describing this histogram.
-  void WriteAsciiHeader(const SampleSet& snapshot,
-                        Count sample_count, std::string* output) const;
+  void WriteAsciiHeader(const BucketHistogramSamples& samples,
+                        Count sample_count,
+                        std::string* output) const;
 
   // Write information about previous, current, and next buckets.
   // Information such as cumulative percentage, etc.
   void WriteAsciiBucketContext(const int64 past, const Count current,
                                const int64 remaining, const size_t i,
                                std::string* output) const;
 
   // Write textual description of the bucket contents (relative to histogram).
   // Output is the count in the buckets, as well as the percentage.
   void WriteAsciiBucketValue(Count current, double scaled_sum,
                              std::string* output) const;
 
   // Produce actual graph (set of blank vs non blank char's) for a bucket.
   void WriteAsciiBucketGraph(double current_size, double max_size,
                              std::string* output) const;
 
   // Does not own this object. Should get from StatisticsRecorder.
   const BucketRanges* bucket_ranges_;
 
   Sample declared_min_;  // Less than this goes into counts_[0]
   Sample declared_max_;  // Over this goes into counts_[bucket_count_ - 1].
   size_t bucket_count_;  // Dimension of counts_[].
 
   // Finally, provide the state that changes with the addition of each new
   // sample.
-  SampleSet sample_;
+  scoped_ptr<BucketHistogramSamples> samples_;
 
   DISALLOW_COPY_AND_ASSIGN(Histogram);
 };
 
 //------------------------------------------------------------------------------
 
 // LinearHistogram is a more traditional histogram, with evenly spaced
 // buckets.
 class BASE_EXPORT LinearHistogram : public Histogram {
  public:
@@ skipping 110 matching lines @@
   static bool ValidateCustomRanges(const std::vector<Sample>& custom_ranges);
   static BucketRanges* CreateBucketRangesFromCustomRanges(
       const std::vector<Sample>& custom_ranges);
 
   DISALLOW_COPY_AND_ASSIGN(CustomHistogram);
 };
 
 }  // namespace base
 
 #endif  // BASE_METRICS_HISTOGRAM_H_