Bug 1383210 - Use precomputed histogram buckets r?gfritzsche
The log and exp calls in base::Histogram::InitializeBucketRange()
were showing up in profiles. This patch uses the precomputed
buckets for exponential histograms instead of computing them at
runtime. Though linear histograms do show up in the profile that
prompted this change, they contribute much less, and due to the
trivial nature of generating these, it's unlikely that a static
cache would provide much if any speedup.
MozReview-Commit-ID: IavFwoWjFhk
--- a/ipc/chromium/src/base/histogram.cc
+++ b/ipc/chromium/src/base/histogram.cc
@@ -79,42 +79,36 @@ 0x2d02ef8dL,
typedef Histogram::Count Count;
// static
const size_t Histogram::kBucketCount_MAX = 16384u;
Histogram* Histogram::FactoryGet(Sample minimum,
Sample maximum,
size_t bucket_count,
- Flags flags) {
+ Flags flags,
+ const int* buckets) {
+ DCHECK(buckets);
Histogram* histogram(NULL);
// Defensive code.
if (minimum < 1)
minimum = 1;
if (maximum > kSampleType_MAX - 1)
maximum = kSampleType_MAX - 1;
histogram = new Histogram(minimum, maximum, bucket_count);
- histogram->InitializeBucketRange();
+ histogram->InitializeBucketRangeFromData(buckets);
histogram->SetFlags(flags);
DCHECK_EQ(HISTOGRAM, histogram->histogram_type());
DCHECK(histogram->HasConstructorArguments(minimum, maximum, bucket_count));
return histogram;
}
-Histogram* Histogram::FactoryTimeGet(TimeDelta minimum,
- TimeDelta maximum,
- size_t bucket_count,
- Flags flags) {
- return FactoryGet(minimum.InMilliseconds(), maximum.InMilliseconds(),
- bucket_count, flags);
-}
-
void Histogram::Add(int value) {
if (value > kSampleType_MAX - 1)
value = kSampleType_MAX - 1;
if (value < 0)
value = 0;
size_t index = BucketIndex(value);
DCHECK_GE(value, ranges(index));
DCHECK_LT(value, ranges(index + 1));
@@ -273,49 +267,20 @@ Histogram::Histogram(TimeDelta minimum,
Initialize();
}
Histogram::~Histogram() {
// Just to make sure most derived class did this properly...
DCHECK(ValidateBucketRanges());
}
-// Calculate what range of values are held in each bucket.
-// We have to be careful that we don't pick a ratio between starting points in
-// consecutive buckets that is sooo small, that the integer bounds are the same
-// (effectively making one bucket get no values). We need to avoid:
-// ranges_[i] == ranges_[i + 1]
-// To avoid that, we just do a fine-grained bucket width as far as we need to
-// until we get a ratio that moves us along at least 2 units at a time. From
-// that bucket onward we do use the exponential growth of buckets.
-void Histogram::InitializeBucketRange() {
- double log_max = log(static_cast<double>(declared_max()));
- double log_ratio;
- double log_next;
- size_t bucket_index = 1;
- Sample current = declared_min();
- SetBucketRange(bucket_index, current);
- while (bucket_count() > ++bucket_index) {
- double log_current;
- log_current = log(static_cast<double>(current));
- // Calculate the count'th root of the range.
- log_ratio = (log_max - log_current) / (bucket_count() - bucket_index);
- // See where the next bucket would start.
- log_next = log_current + log_ratio;
- int next;
- next = static_cast<int>(floor(exp(log_next) + 0.5));
- if (next > current)
- current = next;
- else
- ++current; // Just do a narrow bucket, and keep trying.
- SetBucketRange(bucket_index, current);
- }
+void Histogram::InitializeBucketRangeFromData(const int* buckets) {
+ ranges_.assign(buckets, buckets + bucket_count());
ResetRangeChecksum();
-
- DCHECK_EQ(bucket_count(), bucket_index);
+ DCHECK(ValidateBucketRanges());
}
bool Histogram::PrintEmptyBucket(size_t index) const {
return true;
}
size_t Histogram::BucketIndex(Sample value) const {
// Use simple binary search. This is very general, but there are better
--- a/ipc/chromium/src/base/histogram.h
+++ b/ipc/chromium/src/base/histogram.h
@@ -175,21 +175,18 @@ class Histogram {
};
//----------------------------------------------------------------------------
// minimum should start from 1. 0 is invalid as a minimum. 0 is an implicit
// default underflow bucket.
static Histogram* FactoryGet(Sample minimum,
Sample maximum,
size_t bucket_count,
- Flags flags);
- static Histogram* FactoryTimeGet(base::TimeDelta minimum,
- base::TimeDelta maximum,
- size_t bucket_count,
- Flags flags);
+ Flags flags,
+ const int* buckets);
virtual ~Histogram();
void Add(int value);
void Subtract(int value);
// This method is an interface, used only by BooleanHistogram.
virtual void AddBoolean(bool value);
@@ -243,18 +240,18 @@ class Histogram {
size_t bucket_count);
// Return true iff the range_checksum_ matches current ranges_ vector.
bool HasValidRangeChecksum() const;
protected:
Histogram(Sample minimum, Sample maximum, size_t bucket_count);
Histogram(TimeDelta minimum, TimeDelta maximum, size_t bucket_count);
- // Initialize ranges_ mapping.
- void InitializeBucketRange();
+ // Initialize ranges_ mapping from raw data.
+ void InitializeBucketRangeFromData(const int* buckets);
// 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.
--- a/toolkit/components/telemetry/TelemetryHistogram.cpp
+++ b/toolkit/components/telemetry/TelemetryHistogram.cpp
@@ -235,17 +235,17 @@ const HistogramID kRecordingInitiallyDis
//
// The core storage access functions.
// They wrap access to the histogram storage and lookup caches.
namespace {
// Factory function for histogram instances.
Histogram*
-internal_CreateHistogramInstance(const HistogramInfo& info);
+internal_CreateHistogramInstance(const HistogramInfo& info, int bucketsOffset);
bool
internal_IsHistogramEnumId(HistogramID aID)
{
static_assert(((HistogramID)-1 > 0), "ID should be unsigned.");
return aID < HistogramCount;
}
@@ -260,17 +260,18 @@ internal_GetHistogramById(HistogramID hi
MOZ_ASSERT(sessionType < SessionType::Count);
Histogram* h = gHistogramStorage[histogramId][uint32_t(processId)][uint32_t(sessionType)];
if (h || !instantiate) {
return h;
}
const HistogramInfo& info = gHistogramInfos[histogramId];
- h = internal_CreateHistogramInstance(info);
+ const int bucketsOffset = gExponentialBucketLowerBoundIndex[histogramId];
+ h = internal_CreateHistogramInstance(info, bucketsOffset);
MOZ_ASSERT(h);
gHistogramStorage[histogramId][uint32_t(processId)][uint32_t(sessionType)] = h;
return h;
}
// Look up a keyed histogram by id.
KeyedHistogram*
internal_GetKeyedHistogramById(HistogramID histogramId, ProcessID processId,
@@ -451,17 +452,17 @@ internal_CheckHistogramArguments(const H
return NS_ERROR_ILLEGAL_VALUE;
}
}
return NS_OK;
}
Histogram*
-internal_CreateHistogramInstance(const HistogramInfo& passedInfo)
+internal_CreateHistogramInstance(const HistogramInfo& passedInfo, int bucketsOffset)
{
if (NS_FAILED(internal_CheckHistogramArguments(passedInfo))) {
MOZ_ASSERT(false, "Failed histogram argument checks.");
return nullptr;
}
// To keep the code simple we map all the calls to expired histograms to the same histogram instance.
// We create that instance lazily when needed.
@@ -478,17 +479,18 @@ internal_CreateHistogramInstance(const H
info.bucketCount = 3;
info.histogramType = nsITelemetry::HISTOGRAM_LINEAR;
}
Histogram::Flags flags = Histogram::kNoFlags;
Histogram* h = nullptr;
switch (info.histogramType) {
case nsITelemetry::HISTOGRAM_EXPONENTIAL:
- h = Histogram::FactoryGet(info.min, info.max, info.bucketCount, flags);
+ h = Histogram::FactoryGet(info.min, info.max, info.bucketCount, flags,
+ &gExponentialBucketLowerBounds[bucketsOffset]);
break;
case nsITelemetry::HISTOGRAM_LINEAR:
case nsITelemetry::HISTOGRAM_CATEGORICAL:
h = LinearHistogram::FactoryGet(info.min, info.max, info.bucketCount, flags);
break;
case nsITelemetry::HISTOGRAM_BOOLEAN:
h = BooleanHistogram::FactoryGet(flags);
break;
@@ -674,17 +676,18 @@ KeyedHistogram::GetHistogram(const nsCSt
KeyedHistogramMapType& map = mHistogramMap;
#endif
KeyedHistogramEntry* entry = map.GetEntry(key);
if (entry) {
*histogram = entry->mData;
return NS_OK;
}
- Histogram* h = internal_CreateHistogramInstance(mHistogramInfo);
+ int bucketsOffset = gExponentialBucketLowerBoundIndex[mId];
+ Histogram* h = internal_CreateHistogramInstance(mHistogramInfo, bucketsOffset);
if (!h) {
return NS_ERROR_FAILURE;
}
h->ClearFlags(Histogram::kUmaTargetedHistogramFlag);
*histogram = h;
entry = map.PutEntry(key);
--- a/toolkit/components/telemetry/gen-histogram-data.py
+++ b/toolkit/components/telemetry/gen-histogram-data.py
@@ -131,16 +131,47 @@ def write_histogram_static_asserts(outpu
for histogram in histograms:
kind = histogram.kind()
if kind not in table:
raise Exception('Unknown kind "%s" for histogram "%s".' % (kind, histogram.name()))
fn = table[kind]
fn(output, histogram)
+def write_exponential_histogram_ranges(output, histograms):
+ # For now we use this as a special cache only for exponential histograms,
+ # which require exp and log calls that show up in profiles. Initialization
+ # of other histograms also shows up in profiles, but it's unlikely that we
+ # would see much speedup since calculating their buckets is fairly trivial,
+ # and grabbing them from static data would likely incur a CPU cache miss.
+ print("const int gExponentialBucketLowerBounds[] = {", file=output)
+ for histogram in histograms:
+ if histogram.kind() == 'exponential':
+ ranges = histogram.ranges()
+ print(','.join(map(str, ranges)), ',', file=output)
+ print("};", file=output)
+
+ print("const int gExponentialBucketLowerBoundIndex[] = {", file=output)
+ offset = 0
+ for histogram in histograms:
+ cpp_guard = histogram.cpp_guard()
+ if cpp_guard:
+ print("#if defined(%s)" % cpp_guard, file=output)
+
+ if histogram.kind() == 'exponential':
+ print("%d," % offset, file=output)
+ offset += histogram.n_buckets()
+ else:
+ print("-1,", file=output)
+
+ if cpp_guard:
+ print("#endif", file=output)
+ print("};", file=output)
+
+
def write_debug_histogram_ranges(output, histograms):
ranges_lengths = []
# Collect all the range information from individual histograms.
# Write that information out as well.
print("#ifdef DEBUG", file=output)
print("const int gBucketLowerBounds[] = {", file=output)
for histogram in histograms:
@@ -185,14 +216,15 @@ def main(output, *filenames):
try:
histograms = list(histogram_tools.from_files(filenames))
except ParserError as ex:
print("\nError processing histograms:\n" + str(ex) + "\n")
sys.exit(1)
print(banner, file=output)
write_histogram_table(output, histograms)
+ write_exponential_histogram_ranges(output, histograms)
write_histogram_static_asserts(output, histograms)
write_debug_histogram_ranges(output, histograms)
if __name__ == '__main__':
main(sys.stdout, *sys.argv[1:])