DoubleHistogram.java
/*
* Written by Gil Tene of Azul Systems, and released to the public domain,
* as explained at http://creativecommons.org/publicdomain/zero/1.0/
*
* @author Gil Tene
*/
package org.HdrHistogram;
import java.io.*;
import java.lang.reflect.Constructor;
import java.lang.reflect.InvocationTargetException;
import java.nio.ByteBuffer;
import java.util.Iterator;
import java.util.zip.DataFormatException;
import java.util.zip.Deflater;
/**
* <h3>A floating point values High Dynamic Range (HDR) Histogram</h3>
* <p>
* It is important to note that {@link DoubleHistogram} is not thread-safe, and does not support safe concurrent
* recording by multiple threads. If concurrent operation is required, consider using
* {@link ConcurrentDoubleHistogram}, {@link SynchronizedDoubleHistogram},
* or (recommended) {@link DoubleRecorder} or {@link SingleWriterDoubleRecorder} which are intended for this purpose.
* <p>
* {@link DoubleHistogram} supports the recording and analyzing sampled data value counts across a
* configurable dynamic range of floating point (double) values, with configurable value precision within the range.
* Dynamic range is expressed as a ratio between the highest and lowest non-zero values trackable within the histogram
* at any given time. Value precision is expressed as the number of significant [decimal] digits in the value recording,
* and provides control over value quantization behavior across the value range and the subsequent value resolution at
* any given level.
* <p>
* Auto-ranging: Unlike integer value based histograms, the specific value range tracked by a {@link
* DoubleHistogram} is not specified upfront. Only the dynamic range of values that the histogram can cover is
* (optionally) specified. E.g. When a {@link DoubleHistogram} is created to track a dynamic range of
* 3600000000000 (enough to track values from a nanosecond to an hour), values could be recorded into into it in any
* consistent unit of time as long as the ratio between the highest and lowest non-zero values stays within the
* specified dynamic range, so recording in units of nanoseconds (1.0 thru 3600000000000.0), milliseconds (0.000001
* thru 3600000.0) seconds (0.000000001 thru 3600.0), hours (1/3.6E12 thru 1.0) will all work just as well.
* <p>
* Auto-resizing: When constructed with no specified dynamic range (or when auto-resize is turned on with {@link
* DoubleHistogram#setAutoResize}) a {@link DoubleHistogram} will auto-resize its dynamic range to
* include recorded values as they are encountered. Note that recording calls that cause auto-resizing may take
* longer to execute, as resizing incurs allocation and copying of internal data structures.
* <p>
* Attempts to record non-zero values that range outside of the specified dynamic range (or exceed the limits of
* of dynamic range when auto-resizing) may results in {@link ArrayIndexOutOfBoundsException} exceptions, either
* due to overflow or underflow conditions. These exceptions will only be thrown if recording the value would have
* resulted in discarding or losing the required value precision of values already recorded in the histogram.
* <p>
* See package description for {@link org.HdrHistogram} for details.
*/
public class DoubleHistogram extends EncodableHistogram implements DoubleValueRecorder, Serializable {
private static final double highestAllowedValueEver; // A value that will keep us from multiplying into infinity.
private long configuredHighestToLowestValueRatio;
private volatile double currentLowestValueInAutoRange;
private volatile double currentHighestValueLimitInAutoRange;
AbstractHistogram integerValuesHistogram;
// volatile double doubleToIntegerValueConversionRatio;
// volatile double integerToDoubleValueConversionRatio;
private boolean autoResize = false;
/**
* Construct a new auto-resizing DoubleHistogram using a precision stated as a number
* of significant decimal digits.
*
* @param numberOfSignificantValueDigits Specifies the precision to use. This is the number of significant
* decimal digits to which the histogram will maintain value resolution
* and separation. Must be a non-negative integer between 0 and 5.
*/
public DoubleHistogram(final int numberOfSignificantValueDigits) {
this(2, numberOfSignificantValueDigits, Histogram.class, null);
setAutoResize(true);
}
/**
* Construct a new auto-resizing DoubleHistogram using a precision stated as a number
* of significant decimal digits.
*
* The {@link org.HdrHistogram.DoubleHistogram} will use the specified AbstractHistogram subclass
* for tracking internal counts (e.g. {@link org.HdrHistogram.Histogram},
* {@link org.HdrHistogram.ConcurrentHistogram}, {@link org.HdrHistogram.SynchronizedHistogram},
* {@link org.HdrHistogram.IntCountsHistogram}, {@link org.HdrHistogram.ShortCountsHistogram}).
*
* @param numberOfSignificantValueDigits Specifies the precision to use. This is the number of significant
* decimal digits to which the histogram will maintain value resolution
* and separation. Must be a non-negative integer between 0 and 5.
* @param internalCountsHistogramClass The class to use for internal counts tracking
*/
public DoubleHistogram(final int numberOfSignificantValueDigits,
final Class<? extends AbstractHistogram> internalCountsHistogramClass) {
this(2, numberOfSignificantValueDigits, internalCountsHistogramClass, null);
setAutoResize(true);
}
/**
* Construct a new DoubleHistogram with the specified dynamic range (provided in
* {@code highestToLowestValueRatio}) and using a precision stated as a number of significant
* decimal digits.
*
* @param highestToLowestValueRatio specifies the dynamic range to use
* @param numberOfSignificantValueDigits Specifies the precision to use. This is the number of significant
* decimal digits to which the histogram will maintain value resolution
* and separation. Must be a non-negative integer between 0 and 5.
*/
public DoubleHistogram(final long highestToLowestValueRatio, final int numberOfSignificantValueDigits) {
this(highestToLowestValueRatio, numberOfSignificantValueDigits, Histogram.class);
}
/**
* Construct a new DoubleHistogram with the specified dynamic range (provided in
* {@code highestToLowestValueRatio}) and using a precision stated as a number of significant
* decimal digits.
*
* The {@link org.HdrHistogram.DoubleHistogram} will use the specified AbstractHistogram subclass
* for tracking internal counts (e.g. {@link org.HdrHistogram.Histogram},
* {@link org.HdrHistogram.ConcurrentHistogram}, {@link org.HdrHistogram.SynchronizedHistogram},
* {@link org.HdrHistogram.IntCountsHistogram}, {@link org.HdrHistogram.ShortCountsHistogram}).
*
* @param highestToLowestValueRatio specifies the dynamic range to use.
* @param numberOfSignificantValueDigits Specifies the precision to use. This is the number of significant
* decimal digits to which the histogram will maintain value resolution
* and separation. Must be a non-negative integer between 0 and 5.
* @param internalCountsHistogramClass The class to use for internal counts tracking
*/
protected DoubleHistogram(final long highestToLowestValueRatio,
final int numberOfSignificantValueDigits,
final Class<? extends AbstractHistogram> internalCountsHistogramClass) {
this(highestToLowestValueRatio, numberOfSignificantValueDigits, internalCountsHistogramClass, null);
}
DoubleHistogram(final long highestToLowestValueRatio,
final int numberOfSignificantValueDigits,
final Class<? extends AbstractHistogram> internalCountsHistogramClass,
AbstractHistogram internalCountsHistogram) {
this(
highestToLowestValueRatio,
numberOfSignificantValueDigits,
internalCountsHistogramClass,
internalCountsHistogram,
false
);
}
private DoubleHistogram(final long highestToLowestValueRatio,
final int numberOfSignificantValueDigits,
final Class<? extends AbstractHistogram> internalCountsHistogramClass,
AbstractHistogram internalCountsHistogram,
boolean mimicInternalModel) {
try {
if (highestToLowestValueRatio < 2) {
throw new IllegalArgumentException("highestToLowestValueRatio must be >= 2");
}
if ((highestToLowestValueRatio * Math.pow(10.0, numberOfSignificantValueDigits)) >= (1L << 61)) {
throw new IllegalArgumentException(
"highestToLowestValueRatio * (10^numberOfSignificantValueDigits) must be < (1L << 61)");
}
if (internalCountsHistogramClass == AtomicHistogram.class) {
throw new IllegalArgumentException(
"AtomicHistogram cannot be used as an internal counts histogram (does not support shifting)." +
" Use ConcurrentHistogram instead.");
}
long integerValueRange = deriveIntegerValueRange(highestToLowestValueRatio, numberOfSignificantValueDigits);
final AbstractHistogram valuesHistogram;
double initialLowestValueInAutoRange;
if (internalCountsHistogram == null) {
// Create the internal counts histogram:
Constructor<? extends AbstractHistogram> histogramConstructor =
internalCountsHistogramClass.getConstructor(long.class, long.class, int.class);
valuesHistogram =
histogramConstructor.newInstance(
1L,
(integerValueRange - 1),
numberOfSignificantValueDigits
);
// We want the auto-ranging to tend towards using a value range that will result in using the
// lower tracked value ranges and leave the higher end empty unless the range is actually used.
// This is most easily done by making early recordings force-shift the lower value limit to
// accommodate them (forcing a force-shift for the higher values would achieve the opposite).
// We will therefore start with a very high value range, and let the recordings autoAdjust
// downwards from there:
initialLowestValueInAutoRange = Math.pow(2.0, 800);
} else if (mimicInternalModel) {
Constructor<? extends AbstractHistogram> histogramConstructor =
internalCountsHistogramClass.getConstructor(AbstractHistogram.class);
valuesHistogram = histogramConstructor.newInstance(internalCountsHistogram);
initialLowestValueInAutoRange = Math.pow(2.0, 800);
} else {
// Verify that the histogram we got matches:
if ((internalCountsHistogram.getLowestDiscernibleValue() != 1) ||
(internalCountsHistogram.getHighestTrackableValue() != integerValueRange - 1) ||
internalCountsHistogram.getNumberOfSignificantValueDigits() != numberOfSignificantValueDigits) {
throw new IllegalStateException("integer values histogram does not match stated parameters.");
}
valuesHistogram = internalCountsHistogram;
// Derive initialLowestValueInAutoRange from valuesHistogram's integerToDoubleValueConversionRatio:
initialLowestValueInAutoRange =
internalCountsHistogram.getIntegerToDoubleValueConversionRatio() *
internalCountsHistogram.subBucketHalfCount;
}
// Set our double tracking range and internal histogram:
init(highestToLowestValueRatio, initialLowestValueInAutoRange, valuesHistogram);
} catch (NoSuchMethodException | IllegalAccessException |
InstantiationException | InvocationTargetException ex) {
throw new IllegalArgumentException(ex);
}
}
/**
* Construct a {@link org.HdrHistogram.DoubleHistogram} with the same range settings as a given source,
* duplicating the source's start/end timestamps (but NOT it's contents)
* @param source The source histogram to duplicate
*/
public DoubleHistogram(final DoubleHistogram source) {
this(source.configuredHighestToLowestValueRatio,
source.getNumberOfSignificantValueDigits(),
source.integerValuesHistogram.getClass(),
source.integerValuesHistogram,
true);
this.autoResize = source.autoResize;
setTrackableValueRange(source.currentLowestValueInAutoRange, source.currentHighestValueLimitInAutoRange);
}
private void init(final long configuredHighestToLowestValueRatio, final double lowestTrackableUnitValue,
final AbstractHistogram integerValuesHistogram) {
this.configuredHighestToLowestValueRatio = configuredHighestToLowestValueRatio;
this.integerValuesHistogram = integerValuesHistogram;
long internalHighestToLowestValueRatio =
deriveInternalHighestToLowestValueRatio(configuredHighestToLowestValueRatio);
setTrackableValueRange(lowestTrackableUnitValue, lowestTrackableUnitValue * internalHighestToLowestValueRatio);
}
private void setTrackableValueRange(final double lowestValueInAutoRange, final double highestValueInAutoRange) {
this.currentLowestValueInAutoRange = lowestValueInAutoRange;
this.currentHighestValueLimitInAutoRange = highestValueInAutoRange;
double integerToDoubleValueConversionRatio = lowestValueInAutoRange / getLowestTrackingIntegerValue();
integerValuesHistogram.setIntegerToDoubleValueConversionRatio(integerToDoubleValueConversionRatio);
}
double getDoubleToIntegerValueConversionRatio() {
return integerValuesHistogram.getDoubleToIntegerValueConversionRatio();
}
//
//
// Auto-resizing control:
//
//
public boolean isAutoResize() {
return autoResize;
}
public void setAutoResize(boolean autoResize) {
this.autoResize = autoResize;
}
//
//
//
// Value recording support:
//
//
//
/**
* Record a value in the histogram
*
* @param value The value to be recorded
* @throws ArrayIndexOutOfBoundsException (may throw) if value cannot be covered by the histogram's range
*/
@Override
public void recordValue(final double value) throws ArrayIndexOutOfBoundsException {
recordSingleValue(value);
}
/**
* Record a value in the histogram (adding to the value's current count)
*
* @param value The value to be recorded
* @param count The number of occurrences of this value to record
* @throws ArrayIndexOutOfBoundsException (may throw) if value cannot be covered by the histogram's range
*/
@Override
public void recordValueWithCount(final double value, final long count) throws ArrayIndexOutOfBoundsException {
recordCountAtValue(count, value);
}
/**
* Record a value in the histogram.
* <p>
* To compensate for the loss of sampled values when a recorded value is larger than the expected
* interval between value samples, Histogram will auto-generate an additional series of decreasingly-smaller
* (down to the expectedIntervalBetweenValueSamples) value records.
* <p>
* Note: This is a at-recording correction method, as opposed to the post-recording correction method provided
* by {@link #copyCorrectedForCoordinatedOmission(double)}.
* The use cases for these two methods are mutually exclusive, and only one of the two should be be used on
* a given data set to correct for the same coordinated omission issue.
* <p>
* See notes in the description of the Histogram calls for an illustration of why this corrective behavior is
* important.
*
* @param value The value to record
* @param expectedIntervalBetweenValueSamples If expectedIntervalBetweenValueSamples is larger than 0, add
* auto-generated value records as appropriate if value is larger
* than expectedIntervalBetweenValueSamples
* @throws ArrayIndexOutOfBoundsException (may throw) if value cannot be covered by the histogram's range
*/
@Override
public void recordValueWithExpectedInterval(final double value, final double expectedIntervalBetweenValueSamples)
throws ArrayIndexOutOfBoundsException {
recordValueWithCountAndExpectedInterval(value, 1, expectedIntervalBetweenValueSamples);
}
private void recordCountAtValue(final long count, final double value) throws ArrayIndexOutOfBoundsException {
int throwCount = 0;
while (true) {
if ((value < currentLowestValueInAutoRange) || (value >= currentHighestValueLimitInAutoRange)) {
// Zero is valid and needs no auto-ranging, but also rare enough that we should deal
// with it on the slow path...
autoAdjustRangeForValue(value);
}
try {
integerValuesHistogram.recordConvertedDoubleValueWithCount(value, count);
return;
} catch (IndexOutOfBoundsException ex) {
// A race that would pass the auto-range check above and would still take an AIOOB
// can only occur due to a value that would have been valid becoming invalid due
// to a concurrent adjustment operation. Such adjustment operations can happen no
// more than 64 times in the entire lifetime of the Histogram, which makes it safe
// to retry with no fear of live-locking.
if (++throwCount > 64) {
// For the retry check to not detect an out of range attempt after 64 retries
// should be theoretically impossible, and would indicate a bug.
throw new ArrayIndexOutOfBoundsException(
"BUG: Unexpected non-transient AIOOB Exception caused by:\n" + ex);
}
}
}
}
private void recordSingleValue(final double value) throws ArrayIndexOutOfBoundsException {
int throwCount = 0;
while (true) {
if ((value < currentLowestValueInAutoRange) || (value >= currentHighestValueLimitInAutoRange)) {
// Zero is valid and needs no auto-ranging, but also rare enough that we should deal
// with it on the slow path...
autoAdjustRangeForValue(value);
}
try {
integerValuesHistogram.recordConvertedDoubleValue(value);
return;
} catch (IndexOutOfBoundsException ex) {
// A race that would pass the auto-range check above and would still take an AIOOB
// can only occur due to a value that would have been valid becoming invalid due
// to a concurrent adjustment operation. Such adjustment operations can happen no
// more than 64 times in the entire lifetime of the Histogram, which makes it safe
// to retry with no fear of live-locking.
if (++throwCount > 64) {
// For the retry check to not detect an out of range attempt after 64 retries
// should be theoretically impossible, and would indicate a bug.
throw new ArrayIndexOutOfBoundsException(
"BUG: Unexpected non-transient AIOOB Exception caused by:\n" + ex);
}
}
}
}
private void recordValueWithCountAndExpectedInterval(final double value, final long count,
final double expectedIntervalBetweenValueSamples)
throws ArrayIndexOutOfBoundsException {
recordCountAtValue(count, value);
if (expectedIntervalBetweenValueSamples <= 0)
return;
for (double missingValue = value - expectedIntervalBetweenValueSamples;
missingValue >= expectedIntervalBetweenValueSamples;
missingValue -= expectedIntervalBetweenValueSamples) {
recordCountAtValue(count, missingValue);
}
}
//
//
//
// Shift and auto-ranging support:
//
//
//
private void autoAdjustRangeForValue(final double value) {
// Zero is always valid, and doesn't need auto-range adjustment:
if (value == 0.0) {
return;
}
autoAdjustRangeForValueSlowPath(value);
}
private synchronized void autoAdjustRangeForValueSlowPath(final double value) {
try {
if (value < currentLowestValueInAutoRange) {
if (value < 0.0) {
throw new ArrayIndexOutOfBoundsException("Negative values cannot be recorded");
}
do {
int shiftAmount =
findCappedContainingBinaryOrderOfMagnitude(
Math.ceil(currentLowestValueInAutoRange / value) - 1.0);
shiftCoveredRangeToTheRight(shiftAmount);
}
while (value < currentLowestValueInAutoRange);
} else if (value >= currentHighestValueLimitInAutoRange) {
if (value > highestAllowedValueEver) {
throw new ArrayIndexOutOfBoundsException(
"Values above " + highestAllowedValueEver + " cannot be recorded");
}
do {
// If value is an exact whole multiple of currentHighestValueLimitInAutoRange, it "belongs" with
// the next level up, as it crosses the limit. With floating point values, the simplest way to
// make this shift on exact multiple values happen (but not for any just-smaller-than-exact-multiple
// values) is to use a value that is 1 ulp bigger in computing the ratio for the shift amount:
int shiftAmount =
findCappedContainingBinaryOrderOfMagnitude(
Math.ceil((value + Math.ulp(value)) / currentHighestValueLimitInAutoRange) - 1.0);
shiftCoveredRangeToTheLeft(shiftAmount);
}
while (value >= currentHighestValueLimitInAutoRange);
}
} catch (ArrayIndexOutOfBoundsException ex) {
throw new ArrayIndexOutOfBoundsException("The value " + value +
" is out of bounds for histogram, current covered range [" +
currentLowestValueInAutoRange + ", " + currentHighestValueLimitInAutoRange +
") cannot be extended any further.\n"+
"Caused by: " + ex);
}
}
private void shiftCoveredRangeToTheRight(final int numberOfBinaryOrdersOfMagnitude) {
// We are going to adjust the tracked range by effectively shifting it to the right
// (in the integer shift sense).
//
// To counter the right shift of the value multipliers, we need to left shift the internal
// representation such that the newly shifted integer values will continue to return the
// same double values.
// Initially, new range is the same as current range, to make sure we correctly recover
// from a shift failure if one happens:
double newLowestValueInAutoRange = currentLowestValueInAutoRange;
double newHighestValueLimitInAutoRange = currentHighestValueLimitInAutoRange;
try {
double shiftMultiplier = 1.0 / (1L << numberOfBinaryOrdersOfMagnitude);
// First, temporarily change the highest value in auto-range without changing conversion ratios.
// This is done to force new values higher than the new expected highest value to attempt an
// adjustment (which is synchronized and will wait behind this one). This ensures that we will
// not end up with any concurrently recorded values that would need to be discarded if the shift
// fails. If this shift succeeds, the pending adjustment attempt will end up doing nothing.
currentHighestValueLimitInAutoRange *= shiftMultiplier;
double newIntegerToDoubleValueConversionRatio =
getIntegerToDoubleValueConversionRatio() * shiftMultiplier;
// First shift the values, to give the shift a chance to fail:
// Shift integer histogram left, increasing the recorded integer values for current recordings
// by a factor of (1 << numberOfBinaryOrdersOfMagnitude):
// (no need to shift any values if all recorded values are at the 0 value level:)
if (getTotalCount() > integerValuesHistogram.getCountAtIndex(0)) {
// Apply the shift:
try {
integerValuesHistogram.shiftValuesLeft(numberOfBinaryOrdersOfMagnitude,
newIntegerToDoubleValueConversionRatio);
} catch (ArrayIndexOutOfBoundsException ex) {
// Failed to shift, try to expand size instead:
handleShiftValuesException(numberOfBinaryOrdersOfMagnitude, ex);
// First expand the highest limit to reflect successful size expansion:
newHighestValueLimitInAutoRange /= shiftMultiplier;
// Successfully expanded histogram range by numberOfBinaryOrdersOfMagnitude, but not
// by shifting (shifting failed because there was not room to shift left into). Instead,
// we grew the max value without changing the value mapping. Since we were trying to
// shift values left to begin with, trying to shift the left again will work (we now
// have room to shift into):
integerValuesHistogram.shiftValuesLeft(numberOfBinaryOrdersOfMagnitude,
newIntegerToDoubleValueConversionRatio);
}
}
// Shift (or resize) was successful. Adjust new range to reflect:
newLowestValueInAutoRange *= shiftMultiplier;
newHighestValueLimitInAutoRange *= shiftMultiplier;
} finally {
// Set the new range to either the successfully changed one, or the original one:
setTrackableValueRange(newLowestValueInAutoRange, newHighestValueLimitInAutoRange);
}
}
private void shiftCoveredRangeToTheLeft(final int numberOfBinaryOrdersOfMagnitude) {
// We are going to adjust the tracked range by effectively shifting it to the right
// (in the integer shift sense).
//
// To counter the left shift of the value multipliers, we need to right shift the internal
// representation such that the newly shifted integer values will continue to return the
// same double values.
// Initially, new range is the same as current range, to make sure we correctly recover
// from a shift failure if one happens:
double newLowestValueInAutoRange = currentLowestValueInAutoRange;
double newHighestValueLimitInAutoRange = currentHighestValueLimitInAutoRange;
try {
double shiftMultiplier = 1.0 * (1L << numberOfBinaryOrdersOfMagnitude);
double newIntegerToDoubleValueConversionRatio =
getIntegerToDoubleValueConversionRatio() * shiftMultiplier;
// First, temporarily change the lowest value in auto-range without changing conversion ratios.
// This is done to force new values lower than the new expected lowest value to attempt an
// adjustment (which is synchronized and will wait behind this one). This ensures that we will
// not end up with any concurrently recorded values that would need to be discarded if the shift
// fails. If this shift succeeds, the pending adjustment attempt will end up doing nothing.
currentLowestValueInAutoRange *= shiftMultiplier;
// First shift the values, to give the shift a chance to fail:
// Shift integer histogram right, decreasing the recorded integer values for current recordings
// by a factor of (1 << numberOfBinaryOrdersOfMagnitude):
// (no need to shift any values if all recorded values are at the 0 value level:)
if (getTotalCount() > integerValuesHistogram.getCountAtIndex(0)) {
// Apply the shift:
try {
integerValuesHistogram.shiftValuesRight(numberOfBinaryOrdersOfMagnitude,
newIntegerToDoubleValueConversionRatio);
// Shift was successful. Adjust new range to reflect:
newLowestValueInAutoRange *= shiftMultiplier;
newHighestValueLimitInAutoRange *= shiftMultiplier;
} catch (ArrayIndexOutOfBoundsException ex) {
// Failed to shift, try to expand size instead:
handleShiftValuesException(numberOfBinaryOrdersOfMagnitude, ex);
// Successfully expanded histogram range by numberOfBinaryOrdersOfMagnitude, but not
// by shifting (shifting failed because there was not room to shift right into). Instead,
// we grew the max value without changing the value mapping. Since we were trying to
// shift values right to begin with to make room for a larger value than we had had
// been able to fit before, no shift is needed, as the value should now fit. So rather
// than shifting and adjusting both lowest and highest limits, we'll end up just
// expanding newHighestValueLimitInAutoRange to indicate the newly expanded range.
// We therefore reverse-scale the newLowestValueInAutoRange before letting the later
// code scale both up:
newLowestValueInAutoRange /= shiftMultiplier;
}
}
// Shift (or resize) was successful. Adjust new range to reflect:
newLowestValueInAutoRange *= shiftMultiplier;
newHighestValueLimitInAutoRange *= shiftMultiplier;
} finally {
// Set the new range to either the successfully changed one, or the original one:
setTrackableValueRange(newLowestValueInAutoRange, newHighestValueLimitInAutoRange);
}
}
private void handleShiftValuesException(final int numberOfBinaryOrdersOfMagnitude, Exception ex) {
if (!autoResize) {
throw new ArrayIndexOutOfBoundsException("Value outside of histogram covered range.\nCaused by: " + ex);
}
long highestTrackableValue = integerValuesHistogram.getHighestTrackableValue();
int currentContainingOrderOfMagnitude = findContainingBinaryOrderOfMagnitude(highestTrackableValue);
int newContainingOrderOfMagnitude = numberOfBinaryOrdersOfMagnitude + currentContainingOrderOfMagnitude;
if (newContainingOrderOfMagnitude > 63) {
throw new ArrayIndexOutOfBoundsException(
"Cannot resize histogram covered range beyond (1L << 63) / (1L << " +
(integerValuesHistogram.subBucketHalfCountMagnitude) + ") - 1.\n" +
"Caused by: " + ex);
}
long newHighestTrackableValue = (1L << newContainingOrderOfMagnitude) - 1;
integerValuesHistogram.resize(newHighestTrackableValue);
integerValuesHistogram.highestTrackableValue = newHighestTrackableValue;
configuredHighestToLowestValueRatio <<= numberOfBinaryOrdersOfMagnitude;
}
//
//
//
// Clearing support:
//
//
//
/**
* Reset the contents and stats of this histogram
*/
@Override
public void reset() {
integerValuesHistogram.reset();
double initialLowestValueInAutoRange = Math.pow(2.0, 800);
init(configuredHighestToLowestValueRatio, initialLowestValueInAutoRange, integerValuesHistogram);
}
//
//
//
// Copy support:
//
//
//
/**
* Create a copy of this histogram, complete with data and everything.
*
* @return A distinct copy of this histogram.
*/
public DoubleHistogram copy() {
final DoubleHistogram targetHistogram =
new DoubleHistogram(configuredHighestToLowestValueRatio, getNumberOfSignificantValueDigits());
targetHistogram.setTrackableValueRange(currentLowestValueInAutoRange, currentHighestValueLimitInAutoRange);
integerValuesHistogram.copyInto(targetHistogram.integerValuesHistogram);
return targetHistogram;
}
/**
* Get a copy of this histogram, corrected for coordinated omission.
* <p>
* To compensate for the loss of sampled values when a recorded value is larger than the expected
* interval between value samples, the new histogram will include an auto-generated additional series of
* decreasingly-smaller (down to the expectedIntervalBetweenValueSamples) value records for each count found
* in the current histogram that is larger than the expectedIntervalBetweenValueSamples.
*
* Note: This is a post-correction method, as opposed to the at-recording correction method provided
* by {@link #recordValueWithExpectedInterval(double, double) recordValueWithExpectedInterval}. The two
* methods are mutually exclusive, and only one of the two should be be used on a given data set to correct
* for the same coordinated omission issue.
* by
* <p>
* See notes in the description of the Histogram calls for an illustration of why this corrective behavior is
* important.
*
* @param expectedIntervalBetweenValueSamples If expectedIntervalBetweenValueSamples is larger than 0, add
* auto-generated value records as appropriate if value is larger
* than expectedIntervalBetweenValueSamples
* @return a copy of this histogram, corrected for coordinated omission.
*/
public DoubleHistogram copyCorrectedForCoordinatedOmission(final double expectedIntervalBetweenValueSamples) {
final DoubleHistogram targetHistogram =
new DoubleHistogram(configuredHighestToLowestValueRatio, getNumberOfSignificantValueDigits());
targetHistogram.setTrackableValueRange(currentLowestValueInAutoRange, currentHighestValueLimitInAutoRange);
targetHistogram.addWhileCorrectingForCoordinatedOmission(this, expectedIntervalBetweenValueSamples);
return targetHistogram;
}
/**
* Copy this histogram into the target histogram, overwriting it's contents.
*
* @param targetHistogram the histogram to copy into
*/
public void copyInto(final DoubleHistogram targetHistogram) {
targetHistogram.reset();
targetHistogram.add(this);
targetHistogram.setStartTimeStamp(integerValuesHistogram.startTimeStampMsec);
targetHistogram.setEndTimeStamp(integerValuesHistogram.endTimeStampMsec);
}
/**
* Copy this histogram, corrected for coordinated omission, into the target histogram, overwriting it's contents.
* (see {@link #copyCorrectedForCoordinatedOmission} for more detailed explanation about how correction is applied)
*
* @param targetHistogram the histogram to copy into
* @param expectedIntervalBetweenValueSamples If expectedIntervalBetweenValueSamples is larger than 0, add
* auto-generated value records as appropriate if value is larger
* than expectedIntervalBetweenValueSamples
*/
public void copyIntoCorrectedForCoordinatedOmission(final DoubleHistogram targetHistogram,
final double expectedIntervalBetweenValueSamples) {
targetHistogram.reset();
targetHistogram.addWhileCorrectingForCoordinatedOmission(this, expectedIntervalBetweenValueSamples);
targetHistogram.setStartTimeStamp(integerValuesHistogram.startTimeStampMsec);
targetHistogram.setEndTimeStamp(integerValuesHistogram.endTimeStampMsec);
}
//
//
//
// Add support:
//
//
//
/**
* Add the contents of another histogram to this one.
*
* @param fromHistogram The other histogram.
* @throws ArrayIndexOutOfBoundsException (may throw) if values in fromHistogram's cannot be
* covered by this histogram's range
*/
public void add(final DoubleHistogram fromHistogram) throws ArrayIndexOutOfBoundsException {
int arrayLength = fromHistogram.integerValuesHistogram.countsArrayLength;
AbstractHistogram fromIntegerHistogram = fromHistogram.integerValuesHistogram;
for (int i = 0; i < arrayLength; i++) {
long count = fromIntegerHistogram.getCountAtIndex(i);
if (count > 0) {
recordValueWithCount(
fromIntegerHistogram.valueFromIndex(i) *
fromHistogram.getIntegerToDoubleValueConversionRatio(),
count);
}
}
}
/**
* Add the contents of another histogram to this one, while correcting the incoming data for coordinated omission.
* <p>
* To compensate for the loss of sampled values when a recorded value is larger than the expected
* interval between value samples, the values added will include an auto-generated additional series of
* decreasingly-smaller (down to the expectedIntervalBetweenValueSamples) value records for each count found
* in the current histogram that is larger than the expectedIntervalBetweenValueSamples.
*
* Note: This is a post-recording correction method, as opposed to the at-recording correction method provided
* by {@link #recordValueWithExpectedInterval(double, double) recordValueWithExpectedInterval}. The two
* methods are mutually exclusive, and only one of the two should be be used on a given data set to correct
* for the same coordinated omission issue.
* by
* <p>
* See notes in the description of the Histogram calls for an illustration of why this corrective behavior is
* important.
*
* @param fromHistogram Other histogram. highestToLowestValueRatio and numberOfSignificantValueDigits must match.
* @param expectedIntervalBetweenValueSamples If expectedIntervalBetweenValueSamples is larger than 0, add
* auto-generated value records as appropriate if value is larger
* than expectedIntervalBetweenValueSamples
* @throws ArrayIndexOutOfBoundsException (may throw) if values exceed highestTrackableValue
*/
public void addWhileCorrectingForCoordinatedOmission(final DoubleHistogram fromHistogram,
final double expectedIntervalBetweenValueSamples) {
final DoubleHistogram toHistogram = this;
for (HistogramIterationValue v : fromHistogram.integerValuesHistogram.recordedValues()) {
toHistogram.recordValueWithCountAndExpectedInterval(
v.getValueIteratedTo() * getIntegerToDoubleValueConversionRatio(),
v.getCountAtValueIteratedTo(), expectedIntervalBetweenValueSamples);
}
}
/**
* Subtract the contents of another histogram from this one.
*
* @param otherHistogram The other histogram.
* @throws ArrayIndexOutOfBoundsException (may throw) if values in fromHistogram's cannot be
* covered by this histogram's range
*/
public void subtract(final DoubleHistogram otherHistogram) {
int arrayLength = otherHistogram.integerValuesHistogram.countsArrayLength;
AbstractHistogram otherIntegerHistogram = otherHistogram.integerValuesHistogram;
for (int i = 0; i < arrayLength; i++) {
long otherCount = otherIntegerHistogram.getCountAtIndex(i);
if (otherCount > 0) {
double otherValue = otherIntegerHistogram.valueFromIndex(i) *
otherHistogram.getIntegerToDoubleValueConversionRatio();
if (getCountAtValue(otherValue) < otherCount) {
throw new IllegalArgumentException("otherHistogram count (" + otherCount + ") at value " +
otherValue + " is larger than this one's (" + getCountAtValue(otherValue) + ")");
}
recordValueWithCount(otherValue, -otherCount);
}
}
}
//
//
//
// Comparison support:
//
//
//
/**
* Determine if this histogram is equivalent to another.
*
* @param other the other histogram to compare to
* @return True if this histogram are equivalent with the other.
*/
public boolean equals(final Object other){
if ( this == other ) {
return true;
}
if ( !(other instanceof DoubleHistogram) ) {
return false;
}
DoubleHistogram that = (DoubleHistogram) other;
return integerValuesHistogram.equals(that.integerValuesHistogram);
}
@Override
public int hashCode() {
return integerValuesHistogram.hashCode();
}
//
//
//
// Histogram structure querying support:
//
//
//
/**
* Get the total count of all recorded values in the histogram
* @return the total count of all recorded values in the histogram
*/
public long getTotalCount() {
return integerValuesHistogram.getTotalCount();
}
/**
* get the current lowest (non zero) trackable value the automatically determined range
* (keep in mind that this can change because it is auto ranging)
* @return current lowest trackable value the automatically determined range
*/
double getCurrentLowestTrackableNonZeroValue() {
return currentLowestValueInAutoRange;
}
/**
* get the current highest trackable value in the automatically determined range
* (keep in mind that this can change because it is auto ranging)
* @return current highest trackable value in the automatically determined range
*/
double getCurrentHighestTrackableValue() {
return currentHighestValueLimitInAutoRange;
}
/**
* Get the current conversion ratio from interval integer value representation to double units.
* (keep in mind that this can change because it is auto ranging). This ratio can be useful
* for converting integer values found in iteration, although the preferred form for accessing
* iteration values would be to use the
* {@link org.HdrHistogram.HistogramIterationValue#getDoubleValueIteratedTo() getDoubleValueIteratedTo()}
* and
* {@link org.HdrHistogram.HistogramIterationValue#getDoubleValueIteratedFrom() getDoubleValueIteratedFrom()}
* accessors to {@link org.HdrHistogram.HistogramIterationValue} iterated values.
*
* @return the current conversion ratio from interval integer value representation to double units.
*/
public double getIntegerToDoubleValueConversionRatio() {
return integerValuesHistogram.integerToDoubleValueConversionRatio;
}
/**
* get the configured numberOfSignificantValueDigits
* @return numberOfSignificantValueDigits
*/
public int getNumberOfSignificantValueDigits() {
return integerValuesHistogram.numberOfSignificantValueDigits;
}
/**
* get the Dynamic range of the histogram: the configured ratio between the highest trackable value and the
* lowest trackable non zero value at any given time.
* @return the dynamic range of the histogram, expressed as the ratio between the highest trackable value
* and the lowest trackable non zero value at any given time.
*/
public long getHighestToLowestValueRatio() {
return configuredHighestToLowestValueRatio;
}
/**
* Get the size (in value units) of the range of values that are equivalent to the given value within the
* histogram's resolution. Where "equivalent" means that value samples recorded for any two
* equivalent values are counted in a common total count.
*
* @param value The given value
* @return The lowest value that is equivalent to the given value within the histogram's resolution.
*/
public double sizeOfEquivalentValueRange(final double value) {
return integerValuesHistogram.sizeOfEquivalentValueRange((long)(value * getDoubleToIntegerValueConversionRatio())) *
getIntegerToDoubleValueConversionRatio();
}
/**
* Get the lowest value that is equivalent to the given value within the histogram's resolution.
* Where "equivalent" means that value samples recorded for any two
* equivalent values are counted in a common total count.
*
* @param value The given value
* @return The lowest value that is equivalent to the given value within the histogram's resolution.
*/
public double lowestEquivalentValue(final double value) {
return integerValuesHistogram.lowestEquivalentValue((long)(value * getDoubleToIntegerValueConversionRatio())) *
getIntegerToDoubleValueConversionRatio();
}
/**
* Get the highest value that is equivalent to the given value within the histogram's resolution.
* Where "equivalent" means that value samples recorded for any two
* equivalent values are counted in a common total count.
*
* @param value The given value
* @return The highest value that is equivalent to the given value within the histogram's resolution.
*/
public double highestEquivalentValue(final double value) {
double nextNonEquivalentValue = nextNonEquivalentValue(value);
// Theoretically, nextNonEquivalentValue - ulp(nextNonEquivalentValue) == nextNonEquivalentValue
// is possible (if the ulp size switches right at nextNonEquivalentValue), so drop by 2 ulps and
// increment back up to closest within-ulp value.
double highestEquivalentValue = nextNonEquivalentValue - (2 * Math.ulp(nextNonEquivalentValue));
while (highestEquivalentValue + Math.ulp(highestEquivalentValue) < nextNonEquivalentValue) {
highestEquivalentValue += Math.ulp(highestEquivalentValue);
}
return highestEquivalentValue;
}
/**
* Get a value that lies in the middle (rounded up) of the range of values equivalent the given value.
* Where "equivalent" means that value samples recorded for any two
* equivalent values are counted in a common total count.
*
* @param value The given value
* @return The value lies in the middle (rounded up) of the range of values equivalent the given value.
*/
public double medianEquivalentValue(final double value) {
return integerValuesHistogram.medianEquivalentValue((long)(value * getDoubleToIntegerValueConversionRatio())) *
getIntegerToDoubleValueConversionRatio();
}
/**
* Get the next value that is not equivalent to the given value within the histogram's resolution.
* Where "equivalent" means that value samples recorded for any two
* equivalent values are counted in a common total count.
*
* @param value The given value
* @return The next value that is not equivalent to the given value within the histogram's resolution.
*/
public double nextNonEquivalentValue(final double value) {
return integerValuesHistogram.nextNonEquivalentValue((long)(value * getDoubleToIntegerValueConversionRatio())) *
getIntegerToDoubleValueConversionRatio(); }
/**
* Determine if two values are equivalent with the histogram's resolution.
* Where "equivalent" means that value samples recorded for any two
* equivalent values are counted in a common total count.
*
* @param value1 first value to compare
* @param value2 second value to compare
* @return True if values are equivalent to within the histogram's resolution.
*/
public boolean valuesAreEquivalent(final double value1, final double value2) {
return (lowestEquivalentValue(value1) == lowestEquivalentValue(value2));
}
/**
* Provide a (conservatively high) estimate of the Histogram's total footprint in bytes
*
* @return a (conservatively high) estimate of the Histogram's total footprint in bytes
*/
public int getEstimatedFootprintInBytes() {
return integerValuesHistogram._getEstimatedFootprintInBytes();
}
//
//
//
// Timestamp and tag support:
//
//
//
/**
* get the start time stamp [optionally] stored with this histogram
* @return the start time stamp [optionally] stored with this histogram
*/
public long getStartTimeStamp() {
return integerValuesHistogram.getStartTimeStamp();
}
/**
* Set the start time stamp value associated with this histogram to a given value.
* @param timeStampMsec the value to set the time stamp to, [by convention] in msec since the epoch.
*/
public void setStartTimeStamp(final long timeStampMsec) {
integerValuesHistogram.setStartTimeStamp(timeStampMsec);
}
/**
* get the end time stamp [optionally] stored with this histogram
* @return the end time stamp [optionally] stored with this histogram
*/
public long getEndTimeStamp() {
return integerValuesHistogram.getEndTimeStamp();
}
/**
* Set the end time stamp value associated with this histogram to a given value.
* @param timeStampMsec the value to set the time stamp to, [by convention] in msec since the epoch.
*/
public void setEndTimeStamp(final long timeStampMsec) {
integerValuesHistogram.setEndTimeStamp(timeStampMsec);
}
/**
* get the tag string [optionally] associated with this histogram
* @return tag string [optionally] associated with this histogram
*/
public String getTag() {
return integerValuesHistogram.getTag();
}
/**
* Set the tag string associated with this histogram
* @param tag the tag string to associate with this histogram
*/
public void setTag(String tag) {
integerValuesHistogram.setTag(tag);
}
//
//
//
// Histogram Data access support:
//
//
//
/**
* Get the lowest recorded value level in the histogram
*
* @return the Min value recorded in the histogram
*/
public double getMinValue() {
return integerValuesHistogram.getMinValue() * getIntegerToDoubleValueConversionRatio();
}
/**
* Get the highest recorded value level in the histogram
*
* @return the Max value recorded in the histogram
*/
public double getMaxValue() {
return highestEquivalentValue(integerValuesHistogram.getMaxValue() * getIntegerToDoubleValueConversionRatio());
}
/**
* Get the lowest recorded non-zero value level in the histogram
*
* @return the lowest recorded non-zero value level in the histogram
*/
public double getMinNonZeroValue() {
return integerValuesHistogram.getMinNonZeroValue() * getIntegerToDoubleValueConversionRatio();
}
/**
* Get the highest recorded value level in the histogram as a double
*
* @return the highest recorded value level in the histogram as a double
*/
@Override
public double getMaxValueAsDouble() {
return getMaxValue();
}
/**
* Get the computed mean value of all recorded values in the histogram
*
* @return the mean value (in value units) of the histogram data
*/
public double getMean() {
return integerValuesHistogram.getMean() * getIntegerToDoubleValueConversionRatio();
}
/**
* Get the computed standard deviation of all recorded values in the histogram
*
* @return the standard deviation (in value units) of the histogram data
*/
public double getStdDeviation() {
return integerValuesHistogram.getStdDeviation() * getIntegerToDoubleValueConversionRatio();
}
/**
* Get the value at a given percentile.
* When the percentile is > 0.0, the value returned is the value that the given the given
* percentage of the overall recorded value entries in the histogram are either smaller than
* or equivalent to. When the percentile is 0.0, the value returned is the value that all value
* entries in the histogram are either larger than or equivalent to.
* <p>
* Note that two values are "equivalent" in this statement if
* {@link org.HdrHistogram.DoubleHistogram#valuesAreEquivalent} would return true.
*
* @param percentile The percentile for which to return the associated value
* @return The value that the given percentage of the overall recorded value entries in the
* histogram are either smaller than or equivalent to. When the percentile is 0.0, returns the
* value that all value entries in the histogram are either larger than or equivalent to.
*/
public double getValueAtPercentile(final double percentile) {
return integerValuesHistogram.getValueAtPercentile(percentile) * getIntegerToDoubleValueConversionRatio();
}
/**
* Get the percentile at a given value.
* The percentile returned is the percentile of values recorded in the histogram that are smaller
* than or equivalent to the given value.
* <p>
* Note that two values are "equivalent" in this statement if
* {@link org.HdrHistogram.DoubleHistogram#valuesAreEquivalent} would return true.
*
* @param value The value for which to return the associated percentile
* @return The percentile of values recorded in the histogram that are smaller than or equivalent
* to the given value.
*/
public double getPercentileAtOrBelowValue(final double value) {
return integerValuesHistogram.getPercentileAtOrBelowValue((long)(value * getDoubleToIntegerValueConversionRatio()));
}
/**
* Get the count of recorded values within a range of value levels (inclusive to within the histogram's resolution).
*
* @param lowValue The lower value bound on the range for which
* to provide the recorded count. Will be rounded down with
* {@link DoubleHistogram#lowestEquivalentValue lowestEquivalentValue}.
* @param highValue The higher value bound on the range for which to provide the recorded count.
* Will be rounded up with {@link DoubleHistogram#highestEquivalentValue highestEquivalentValue}.
* @return the total count of values recorded in the histogram within the value range that is
* {@literal >=} lowestEquivalentValue(<i>lowValue</i>) and {@literal <=} highestEquivalentValue(<i>highValue</i>)
*/
public double getCountBetweenValues(final double lowValue, final double highValue)
throws ArrayIndexOutOfBoundsException {
return integerValuesHistogram.getCountBetweenValues(
(long)(lowValue * getDoubleToIntegerValueConversionRatio()),
(long)(highValue * getDoubleToIntegerValueConversionRatio())
);
}
/**
* Get the count of recorded values at a specific value (to within the histogram resolution at the value level).
*
* @param value The value for which to provide the recorded count
* @return The total count of values recorded in the histogram within the value range that is
* {@literal >=} lowestEquivalentValue(<i>value</i>) and {@literal <=} highestEquivalentValue(<i>value</i>)
*/
public long getCountAtValue(final double value) throws ArrayIndexOutOfBoundsException {
return integerValuesHistogram.getCountAtValue((long)(value * getDoubleToIntegerValueConversionRatio()));
}
/**
* Provide a means of iterating through histogram values according to percentile levels. The iteration is
* performed in steps that start at 0% and reduce their distance to 100% according to the
* <i>percentileTicksPerHalfDistance</i> parameter, ultimately reaching 100% when all recorded histogram
* values are exhausted.
* <p>
* @param percentileTicksPerHalfDistance The number of iteration steps per half-distance to 100%.
* @return An {@link java.lang.Iterable}{@literal <}{@link DoubleHistogramIterationValue}{@literal >}
* through the histogram using a
* {@link DoublePercentileIterator}
*/
public Percentiles percentiles(final int percentileTicksPerHalfDistance) {
return new Percentiles(this, percentileTicksPerHalfDistance);
}
/**
* Provide a means of iterating through histogram values using linear steps. The iteration is
* performed in steps of <i>valueUnitsPerBucket</i> in size, terminating when all recorded histogram
* values are exhausted.
*
* @param valueUnitsPerBucket The size (in value units) of the linear buckets to use
* @return An {@link java.lang.Iterable}{@literal <}{@link DoubleHistogramIterationValue}{@literal >}
* through the histogram using a
* {@link DoubleLinearIterator}
*/
public LinearBucketValues linearBucketValues(final double valueUnitsPerBucket) {
return new LinearBucketValues(this, valueUnitsPerBucket);
}
/**
* Provide a means of iterating through histogram values at logarithmically increasing levels. The iteration is
* performed in steps that start at <i>valueUnitsInFirstBucket</i> and increase exponentially according to
* <i>logBase</i>, terminating when all recorded histogram values are exhausted.
*
* @param valueUnitsInFirstBucket The size (in value units) of the first bucket in the iteration
* @param logBase The multiplier by which bucket sizes will grow in each iteration step
* @return An {@link java.lang.Iterable}{@literal <}{@link DoubleHistogramIterationValue}{@literal >}
* through the histogram using
* a {@link DoubleLogarithmicIterator}
*/
public LogarithmicBucketValues logarithmicBucketValues(final double valueUnitsInFirstBucket,
final double logBase) {
return new LogarithmicBucketValues(this, valueUnitsInFirstBucket, logBase);
}
/**
* Provide a means of iterating through all recorded histogram values using the finest granularity steps
* supported by the underlying representation. The iteration steps through all non-zero recorded value counts,
* and terminates when all recorded histogram values are exhausted.
*
* @return An {@link java.lang.Iterable}{@literal <}{@link DoubleHistogramIterationValue}{@literal >}
* through the histogram using
* a {@link DoubleRecordedValuesIterator}
*/
public RecordedValues recordedValues() {
return new RecordedValues(this);
}
/**
* Provide a means of iterating through all histogram values using the finest granularity steps supported by
* the underlying representation. The iteration steps through all possible unit value levels, regardless of
* whether or not there were recorded values for that value level, and terminates when all recorded histogram
* values are exhausted.
*
* @return An {@link java.lang.Iterable}{@literal <}{@link DoubleHistogramIterationValue}{@literal >}
* through the histogram using a {@link DoubleAllValuesIterator}
*/
public AllValues allValues() {
return new AllValues(this);
}
// Percentile iterator support:
/**
* An {@link java.lang.Iterable}{@literal <}{@link DoubleHistogramIterationValue}{@literal >} through
* the histogram using a {@link DoublePercentileIterator}
*/
public class Percentiles implements Iterable<DoubleHistogramIterationValue> {
final DoubleHistogram histogram;
final int percentileTicksPerHalfDistance;
private Percentiles(final DoubleHistogram histogram, final int percentileTicksPerHalfDistance) {
this.histogram = histogram;
this.percentileTicksPerHalfDistance = percentileTicksPerHalfDistance;
}
/**
* @return A {@link DoublePercentileIterator}{@literal <}{@link DoubleHistogramIterationValue}{@literal >}
*/
public Iterator<DoubleHistogramIterationValue> iterator() {
return new DoublePercentileIterator(histogram, percentileTicksPerHalfDistance);
}
}
// Linear iterator support:
/**
* An {@link java.lang.Iterable}{@literal <}{@link DoubleHistogramIterationValue}{@literal >} through
* the histogram using a {@link DoubleLinearIterator}
*/
public class LinearBucketValues implements Iterable<DoubleHistogramIterationValue> {
final DoubleHistogram histogram;
final double valueUnitsPerBucket;
private LinearBucketValues(final DoubleHistogram histogram, final double valueUnitsPerBucket) {
this.histogram = histogram;
this.valueUnitsPerBucket = valueUnitsPerBucket;
}
/**
* @return A {@link DoubleLinearIterator}{@literal <}{@link DoubleHistogramIterationValue}{@literal >}
*/
public Iterator<DoubleHistogramIterationValue> iterator() {
return new DoubleLinearIterator(histogram, valueUnitsPerBucket);
}
}
// Logarithmic iterator support:
/**
* An {@link java.lang.Iterable}{@literal <}{@link DoubleHistogramIterationValue}{@literal >} through
* the histogram using a {@link DoubleLogarithmicIterator}
*/
public class LogarithmicBucketValues implements Iterable<DoubleHistogramIterationValue> {
final DoubleHistogram histogram;
final double valueUnitsInFirstBucket;
final double logBase;
private LogarithmicBucketValues(final DoubleHistogram histogram,
final double valueUnitsInFirstBucket, final double logBase) {
this.histogram = histogram;
this.valueUnitsInFirstBucket = valueUnitsInFirstBucket;
this.logBase = logBase;
}
/**
* @return A {@link DoubleLogarithmicIterator}{@literal <}{@link DoubleHistogramIterationValue}{@literal >}
*/
public Iterator<DoubleHistogramIterationValue> iterator() {
return new DoubleLogarithmicIterator(histogram, valueUnitsInFirstBucket, logBase);
}
}
// Recorded value iterator support:
/**
* An {@link java.lang.Iterable}{@literal <}{@link DoubleHistogramIterationValue}{@literal >} through
* the histogram using a {@link DoubleRecordedValuesIterator}
*/
public class RecordedValues implements Iterable<DoubleHistogramIterationValue> {
final DoubleHistogram histogram;
private RecordedValues(final DoubleHistogram histogram) {
this.histogram = histogram;
}
/**
* @return A {@link DoubleRecordedValuesIterator}{@literal <}{@link HistogramIterationValue}{@literal >}
*/
public Iterator<DoubleHistogramIterationValue> iterator() {
return new DoubleRecordedValuesIterator(histogram);
}
}
// AllValues iterator support:
/**
* An {@link java.lang.Iterable}{@literal <}{@link DoubleHistogramIterationValue}{@literal >} through
* the histogram using a {@link DoubleAllValuesIterator}
*/
public class AllValues implements Iterable<DoubleHistogramIterationValue> {
final DoubleHistogram histogram;
private AllValues(final DoubleHistogram histogram) {
this.histogram = histogram;
}
/**
* @return A {@link DoubleAllValuesIterator}{@literal <}{@link HistogramIterationValue}{@literal >}
*/
public Iterator<DoubleHistogramIterationValue> iterator() {
return new DoubleAllValuesIterator(histogram);
}
}
/**
* Produce textual representation of the value distribution of histogram data by percentile. The distribution is
* output with exponentially increasing resolution, with each exponentially decreasing half-distance containing
* five (5) percentile reporting tick points.
*
* @param printStream Stream into which the distribution will be output
* <p>
* @param outputValueUnitScalingRatio The scaling factor by which to divide histogram recorded values units in
* output
*/
public void outputPercentileDistribution(final PrintStream printStream,
final Double outputValueUnitScalingRatio) {
outputPercentileDistribution(printStream, 5, outputValueUnitScalingRatio);
}
//
//
//
// Textual percentile output support:
//
//
//
/**
* Produce textual representation of the value distribution of histogram data by percentile. The distribution is
* output with exponentially increasing resolution, with each exponentially decreasing half-distance containing
* <i>dumpTicksPerHalf</i> percentile reporting tick points.
*
* @param printStream Stream into which the distribution will be output
* <p>
* @param percentileTicksPerHalfDistance The number of reporting points per exponentially decreasing half-distance
* <p>
* @param outputValueUnitScalingRatio The scaling factor by which to divide histogram recorded values units in
* output
*/
public void outputPercentileDistribution(final PrintStream printStream,
final int percentileTicksPerHalfDistance,
final Double outputValueUnitScalingRatio) {
outputPercentileDistribution(printStream, percentileTicksPerHalfDistance, outputValueUnitScalingRatio, false);
}
/**
* Produce textual representation of the value distribution of histogram data by percentile. The distribution is
* output with exponentially increasing resolution, with each exponentially decreasing half-distance containing
* <i>dumpTicksPerHalf</i> percentile reporting tick points.
*
* @param printStream Stream into which the distribution will be output
* <p>
* @param percentileTicksPerHalfDistance The number of reporting points per exponentially decreasing half-distance
* <p>
* @param outputValueUnitScalingRatio The scaling factor by which to divide histogram recorded values units in
* output
* @param useCsvFormat Output in CSV format if true. Otherwise use plain text form.
*/
public void outputPercentileDistribution(final PrintStream printStream,
final int percentileTicksPerHalfDistance,
final Double outputValueUnitScalingRatio,
final boolean useCsvFormat) {
integerValuesHistogram.outputPercentileDistribution(printStream,
percentileTicksPerHalfDistance,
outputValueUnitScalingRatio / getIntegerToDoubleValueConversionRatio(),
useCsvFormat);
}
//
//
//
// Serialization support:
//
//
//
private static final long serialVersionUID = 42L;
private void writeObject(final ObjectOutputStream o)
throws IOException
{
o.writeLong(configuredHighestToLowestValueRatio);
o.writeDouble(currentLowestValueInAutoRange);
o.writeObject(integerValuesHistogram);
}
private void readObject(final ObjectInputStream o)
throws IOException, ClassNotFoundException {
final long configuredHighestToLowestValueRatio = o.readLong();
final double lowestValueInAutoRange = o.readDouble();
AbstractHistogram integerValuesHistogram = (AbstractHistogram) o.readObject();
init(configuredHighestToLowestValueRatio, lowestValueInAutoRange, integerValuesHistogram);
}
//
//
//
// Encoding/Decoding support:
//
//
//
/**
* Get the capacity needed to encode this histogram into a ByteBuffer
* @return the capacity needed to encode this histogram into a ByteBuffer
*/
@Override
public int getNeededByteBufferCapacity() {
return integerValuesHistogram.getNeededByteBufferCapacity();
}
private int getNeededByteBufferCapacity(final int relevantLength) {
return integerValuesHistogram.getNeededByteBufferCapacity(relevantLength);
}
private static final int DHIST_encodingCookie = 0x0c72124e;
private static final int DHIST_compressedEncodingCookie = 0x0c72124f;
static boolean isDoubleHistogramCookie(int cookie) {
return isCompressedDoubleHistogramCookie(cookie) || isNonCompressedDoubleHistogramCookie(cookie);
}
static boolean isCompressedDoubleHistogramCookie(int cookie) {
return (cookie == DHIST_compressedEncodingCookie);
}
static boolean isNonCompressedDoubleHistogramCookie(int cookie) {
return (cookie == DHIST_encodingCookie);
}
/**
* Encode this histogram into a ByteBuffer
* @param buffer The buffer to encode into
* @return The number of bytes written to the buffer
*/
synchronized public int encodeIntoByteBuffer(final ByteBuffer buffer) {
long maxValue = integerValuesHistogram.getMaxValue();
int relevantLength = integerValuesHistogram.getLengthForNumberOfBuckets(
integerValuesHistogram.getBucketsNeededToCoverValue(maxValue));
if (buffer.capacity() < getNeededByteBufferCapacity(relevantLength)) {
throw new ArrayIndexOutOfBoundsException("buffer does not have capacity for " +
getNeededByteBufferCapacity(relevantLength) + " bytes");
}
buffer.putInt(DHIST_encodingCookie);
buffer.putInt(getNumberOfSignificantValueDigits());
buffer.putLong(configuredHighestToLowestValueRatio);
return integerValuesHistogram.encodeIntoByteBuffer(buffer) + 16;
}
/**
* Encode this histogram in compressed form into a byte array
* @param targetBuffer The buffer to encode into
* @param compressionLevel Compression level (for java.util.zip.Deflater).
* @return The number of bytes written to the buffer
*/
@Override
synchronized public int encodeIntoCompressedByteBuffer(
final ByteBuffer targetBuffer,
final int compressionLevel) {
targetBuffer.putInt(DHIST_compressedEncodingCookie);
targetBuffer.putInt(getNumberOfSignificantValueDigits());
targetBuffer.putLong(configuredHighestToLowestValueRatio);
return integerValuesHistogram.encodeIntoCompressedByteBuffer(targetBuffer, compressionLevel) + 16;
}
/**
* Encode this histogram in compressed form into a byte array
* @param targetBuffer The buffer to encode into
* @return The number of bytes written to the array
*/
public int encodeIntoCompressedByteBuffer(final ByteBuffer targetBuffer) {
return encodeIntoCompressedByteBuffer(targetBuffer, Deflater.DEFAULT_COMPRESSION);
}
private static final Class[] constructorArgTypes = {long.class, int.class, Class.class, AbstractHistogram.class};
static <T extends DoubleHistogram> T constructHistogramFromBuffer(
int cookie,
final ByteBuffer buffer,
final Class<T> doubleHistogramClass,
final Class<? extends AbstractHistogram> histogramClass,
final long minBarForHighestToLowestValueRatio) throws DataFormatException {
int numberOfSignificantValueDigits = buffer.getInt();
long configuredHighestToLowestValueRatio = buffer.getLong();
final AbstractHistogram valuesHistogram;
if (isNonCompressedDoubleHistogramCookie(cookie)) {
valuesHistogram =
AbstractHistogram.decodeFromByteBuffer(buffer, histogramClass, minBarForHighestToLowestValueRatio);
} else if (isCompressedDoubleHistogramCookie(cookie)) {
valuesHistogram =
AbstractHistogram.decodeFromCompressedByteBuffer(buffer, histogramClass, minBarForHighestToLowestValueRatio);
} else {
throw new IllegalArgumentException("The buffer does not contain a DoubleHistogram");
}
try {
Constructor<T> doubleHistogramConstructor =
doubleHistogramClass.getDeclaredConstructor(constructorArgTypes);
T histogram =
doubleHistogramConstructor.newInstance(
configuredHighestToLowestValueRatio,
numberOfSignificantValueDigits,
histogramClass,
valuesHistogram
);
histogram.setAutoResize(true);
return histogram;
} catch (NoSuchMethodException | InstantiationException |
IllegalAccessException | InvocationTargetException ex) {
throw new IllegalStateException("Unable to construct DoubleHistogram of type " + doubleHistogramClass);
}
}
/**
* Construct a new DoubleHistogram by decoding it from a ByteBuffer.
* @param buffer The buffer to decode from
* @param minBarForHighestToLowestValueRatio Force highestTrackableValue to be set at least this high
* @return The newly constructed DoubleHistogram
*/
public static DoubleHistogram decodeFromByteBuffer(
final ByteBuffer buffer,
final long minBarForHighestToLowestValueRatio) {
return decodeFromByteBuffer(buffer, Histogram.class, minBarForHighestToLowestValueRatio);
}
/**
* Construct a new DoubleHistogram by decoding it from a ByteBuffer, using a
* specified AbstractHistogram subclass for tracking internal counts (e.g. {@link org.HdrHistogram.Histogram},
* {@link org.HdrHistogram.ConcurrentHistogram}, {@link org.HdrHistogram.SynchronizedHistogram},
* {@link org.HdrHistogram.IntCountsHistogram}, {@link org.HdrHistogram.ShortCountsHistogram}).
*
* @param buffer The buffer to decode from
* @param internalCountsHistogramClass The class to use for internal counts tracking
* @param minBarForHighestToLowestValueRatio Force highestTrackableValue to be set at least this high
* @return The newly constructed DoubleHistogram
*/
public static DoubleHistogram decodeFromByteBuffer(
final ByteBuffer buffer,
final Class<? extends AbstractHistogram> internalCountsHistogramClass,
long minBarForHighestToLowestValueRatio) {
try {
int cookie = buffer.getInt();
if (!isNonCompressedDoubleHistogramCookie(cookie)) {
throw new IllegalArgumentException("The buffer does not contain a DoubleHistogram");
}
DoubleHistogram histogram = constructHistogramFromBuffer(cookie, buffer,
DoubleHistogram.class, internalCountsHistogramClass,
minBarForHighestToLowestValueRatio);
return histogram;
} catch (DataFormatException ex) {
throw new RuntimeException(ex);
}
}
/**
* Construct a new DoubleHistogram by decoding it from a compressed form in a ByteBuffer.
* @param buffer The buffer to decode from
* @param minBarForHighestToLowestValueRatio Force highestTrackableValue to be set at least this high
* @return The newly constructed DoubleHistogram
* @throws DataFormatException on error parsing/decompressing the buffer
*/
public static DoubleHistogram decodeFromCompressedByteBuffer(
final ByteBuffer buffer,
final long minBarForHighestToLowestValueRatio) throws DataFormatException {
return decodeFromCompressedByteBuffer(buffer, Histogram.class, minBarForHighestToLowestValueRatio);
}
/**
* Construct a new DoubleHistogram by decoding it from a compressed form in a ByteBuffer, using a
* specified AbstractHistogram subclass for tracking internal counts (e.g. {@link org.HdrHistogram.Histogram},
* {@link org.HdrHistogram.AtomicHistogram}, {@link org.HdrHistogram.SynchronizedHistogram},
* {@link org.HdrHistogram.IntCountsHistogram}, {@link org.HdrHistogram.ShortCountsHistogram}).
*
* @param buffer The buffer to decode from
* @param internalCountsHistogramClass The class to use for internal counts tracking
* @param minBarForHighestToLowestValueRatio Force highestTrackableValue to be set at least this high
* @return The newly constructed DoubleHistogram
* @throws DataFormatException on error parsing/decompressing the buffer
*/
public static DoubleHistogram decodeFromCompressedByteBuffer(
final ByteBuffer buffer,
Class<? extends AbstractHistogram> internalCountsHistogramClass,
long minBarForHighestToLowestValueRatio) throws DataFormatException {
int cookie = buffer.getInt();
if (!isCompressedDoubleHistogramCookie(cookie)) {
throw new IllegalArgumentException("The buffer does not contain a compressed DoubleHistogram");
}
DoubleHistogram histogram = constructHistogramFromBuffer(cookie, buffer,
DoubleHistogram.class, internalCountsHistogramClass,
minBarForHighestToLowestValueRatio);
return histogram;
}
/**
* Construct a new DoubleHistogram by decoding it from a String containing a base64 encoded
* compressed histogram representation.
*
* @param base64CompressedHistogramString A string containing a base64 encoding of a compressed histogram
* @return A DoubleHistogram decoded from the string
* @throws DataFormatException on error parsing/decompressing the input
*/
public static DoubleHistogram fromString(final String base64CompressedHistogramString)
throws DataFormatException {
return decodeFromCompressedByteBuffer(
ByteBuffer.wrap(Base64Helper.parseBase64Binary(base64CompressedHistogramString)),
0);
}
//
//
//
// Internal helper methods:
//
//
//
private long deriveInternalHighestToLowestValueRatio(final long externalHighestToLowestValueRatio) {
// Internal dynamic range needs to be 1 order of magnitude larger than the containing order of magnitude.
// e.g. the dynamic range that covers [0.9, 2.1) is 2.33x, which on it's own would require 4x range to
// cover the contained order of magnitude. But (if 1.0 was a bucket boundary, for example, the range
// will actually need to cover [0.5..1.0) [1.0..2.0) [2.0..4.0), mapping to an 8x internal dynamic range.
long internalHighestToLowestValueRatio =
1L << (findContainingBinaryOrderOfMagnitude(externalHighestToLowestValueRatio) + 1);
return internalHighestToLowestValueRatio;
}
private long deriveIntegerValueRange(final long externalHighestToLowestValueRatio,
final int numberOfSignificantValueDigits) {
long internalHighestToLowestValueRatio =
deriveInternalHighestToLowestValueRatio(externalHighestToLowestValueRatio);
// We cannot use the bottom half of bucket 0 in an integer values histogram to represent double
// values, because the required precision does not exist there. We therefore need the integer
// range to be bigger, such that the entire double value range can fit in the upper halves of
// all buckets. Compute the integer value range that will achieve this:
long lowestTackingIntegerValue = AbstractHistogram.numberOfSubBuckets(numberOfSignificantValueDigits) / 2;
long integerValueRange = lowestTackingIntegerValue * internalHighestToLowestValueRatio;
return integerValueRange;
}
private long getLowestTrackingIntegerValue() {
return integerValuesHistogram.subBucketHalfCount;
}
private static int findContainingBinaryOrderOfMagnitude(final long longNumber) {
int pow2ceiling = 64 - Long.numberOfLeadingZeros(longNumber); // smallest power of 2 containing value
return pow2ceiling;
}
private static int findContainingBinaryOrderOfMagnitude(final double doubleNumber) {
long longNumber = (long) Math.ceil(doubleNumber);
return findContainingBinaryOrderOfMagnitude(longNumber);
}
private int findCappedContainingBinaryOrderOfMagnitude(final double doubleNumber) {
if (doubleNumber > configuredHighestToLowestValueRatio) {
return (int) (Math.log(configuredHighestToLowestValueRatio)/Math.log(2));
}
if (doubleNumber > Math.pow(2.0, 50)) {
return 50;
}
return findContainingBinaryOrderOfMagnitude(doubleNumber);
}
static {
// We don't want to allow the histogram to shift and expand into value ranges that could equate
// to infinity (e.g. 1024.0 * (Double.MAX_VALUE / 1024.0) == Infinity). So lets makes sure the
// highestAllowedValueEver cap is a couple of binary orders of magnitude away from MAX_VALUE:
// Choose a highestAllowedValueEver that is a nice power of 2 multiple of 1.0 :
double value = 1.0;
while (value < Double.MAX_VALUE / 4.0) {
value *= 2;
}
highestAllowedValueEver = value;
}
}