Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
AbstractHistogram.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(s):
Gil Tene
  
  
  package org.HdrHistogram;
 
 import java.io.*;
This non-public AbstractHistogramBase super-class separation is meant to bunch "cold" fields separately from "hot" fields, in an attempt to force the JVM to place the (hot) fields commonly used in the value recording code paths close together. Subclass boundaries tend to be strongly control memory layout decisions in most practical JVM implementations, making this an effective method for control filed grouping layout.
 
 
 abstract class AbstractHistogramBase {
     static AtomicLong constructionIdentityCount = new AtomicLong(0);
 
     // "Cold" accessed fields. Not used in the recording code path:
     long identityCount;
 
     long highestTrackableValue;
     long lowestTrackableValue;
 
     int bucketCount;
     int subBucketCount;
     int countsArrayLength;
 
 }

A High Dynamic Range (HDR) Histogram

AbstractHistogram supports the recording and analyzing sampled data value counts across a configurable integer value range with configurable value precision within the range. Value precision is expressed as the number of significant 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.

For example, a Histogram could be configured to track the counts of observed integer values between 0 and 3,600,000,000 while maintaining a value precision of 3 significant digits across that range. Value quantization within the range will thus be no larger than 1/1,000th (or 0.1%) of any value. This example Histogram could be used to track and analyze the counts of observed response times ranging between 1 microsecond and 1 hour in magnitude, while maintaining a value resolution of 1 microsecond up to 1 millisecond, a resolution of 1 millisecond (or better) up to one second, and a resolution of 1 second (or better) up to 1,000 seconds. At it's maximum tracked value (1 hour), it would still maintain a resolution of 3.6 seconds (or better).

See package description for org.HdrHistogram for details.

 
 
 public abstract class AbstractHistogram extends AbstractHistogramBase implements Serializable {
     // "Hot" accessed fields (used in the the value recording code path) are bunched here, such
     // that they will have a good chance of ending up in the same cache line as the totalCounts and
     // counts array reference fields that subclass implementations will typically add.
     int unitMagnitude;
     int subBucketHalfCount;
     long subBucketMask;
     // Sub-classes will typically add a totalCount field and a counts array field, which will likely be laid out
     // right around here due to the subclass layout rules in most practical JVM implementations.
 
     // Abstract, counts-type dependent methods to be provided by subclass implementations:
 
     abstract long getCountAtIndex(int index);
 
     abstract void incrementCountAtIndex(int index);
 
     abstract void addToCountAtIndex(int indexlong value);
 
     abstract long getTotalCount();
 
     abstract void setTotalCount(long totalCount);
 
     abstract void incrementTotalCount();
 
     abstract void addToTotalCount(long value);
 
     abstract void clearCounts();
    
    
Create a copy of this histogram, complete with data and everything.

Returns:
A distinct copy of this histogram.
 
     abstract public AbstractHistogram copy();

    
Get a copy of this histogram, corrected for coordinated omission.

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 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

See notes in the description of the Histogram calls for an illustration of why this corrective behavior is important.

Parameters:
expectedIntervalBetweenValueSamples If expectedIntervalBetweenValueSamples is larger than 0, add auto-generated value records as appropriate if value is larger than expectedIntervalBetweenValueSamples
Throws:
java.lang.ArrayIndexOutOfBoundsException
    abstract public AbstractHistogram copyCorrectedForCoordinatedOmission(final long expectedIntervalBetweenValueSamples);

    
Provide a (conservatively high) estimate of the Histogram's total footprint in bytes

Returns:
a (conservatively high) estimate of the Histogram's total footprint in bytes
    abstract public int getEstimatedFootprintInBytes();

    
Copy this histogram into the target histogram, overwriting it's contents.

Parameters:
targetHistogram
Returns:
A distinct copy of this histogram.
    public void copyInto(AbstractHistogram targetHistogram) {
        targetHistogram.reset();
        targetHistogram.add(this);
    }

    
Copy this histogram, corrected for coordinated omission, into the target histogram, overwriting it's contents. (see copyCorrectedForCoordinatedOmission(long) for more detailed explanation about how correction is applied)

Parameters:
targetHistogram
expectedIntervalBetweenValueSamples
    public void copyIntoCorrectedForCoordinatedOmission(AbstractHistogram targetHistogramfinal long expectedIntervalBetweenValueSamples) {
        targetHistogram.reset();
        targetHistogram.addWhileCorrectingForCoordinatedOmission(thisexpectedIntervalBetweenValueSamples);
    }


    
provide an overrideable point for initializing the state of TotalCount. Useful for implementations that would represent totalCount as something other than a primitive value (e.g. AtomicHistogram).
    void initTotalCount() {
    }

    
Construct a Histogram given the Lowest and Highest values to be tracked and a number of significant decimal digits. Providing a lowestTrackableValue is useful is situations where the units used for the histogram's values are much smaller that the minimal accuracy required. E.g. when tracking time values stated in nanosecond units, where the minimal accuracy required is a microsecond, the proper value for lowestTrackableValue would be 1000.

Parameters:
lowestTrackableValue The lowest value that can be tracked (distinguished from 0) by the histogram. Must be a positive integer that is >= 1. May be internally rounded down to nearest power of 2.
highestTrackableValue The highest value to be tracked by the histogram. Must be a positive integer that is >= (2 * lowestTrackableValue).
numberOfSignificantValueDigits 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 AbstractHistogram(final long lowestTrackableValuefinal long highestTrackableValuefinal int numberOfSignificantValueDigits) {
        // Verify argument validity
        if (lowestTrackableValue < 1) {
            throw new IllegalArgumentException("lowestTrackableValue must be >= 1");
        }
        if (highestTrackableValue < 2 * lowestTrackableValue) {
            throw new IllegalArgumentException("highestTrackableValue must be >= 2 * lowestTrackableValue");
        }
        if ((numberOfSignificantValueDigits < 0) || (numberOfSignificantValueDigits > 5)) {
            throw new IllegalArgumentException("numberOfSignificantValueDigits must be between 0 and 6");
        }
        initTotalCount();
        init(lowestTrackableValuehighestTrackableValuenumberOfSignificantValueDigits, 0);
    }
    private void init(final long lowestTrackableValuefinal long highestTrackableValuefinal int numberOfSignificantValueDigitslong totalCount) {
        this. = highestTrackableValue;
        this. = numberOfSignificantValueDigits;
        this. = lowestTrackableValue;
        final long largestValueWithSingleUnitResolution = 2 * (long) Math.pow(10, numberOfSignificantValueDigits);
         = (int) Math.floor(Math.log(lowestTrackableValue)/Math.log(2));
        // We need to maintain power-of-two subBucketCount (for clean direct indexing) that is large enough to
        // provide unit resolution to at least largestValueWithSingleUnitResolution. So figure out
        // largestValueWithSingleUnitResolution's nearest power-of-two (rounded up), and use that:
        int subBucketCountMagnitude = (int) Math.ceil(Math.log(largestValueWithSingleUnitResolution)/Math.log(2));
         = ((subBucketCountMagnitude > 1) ? subBucketCountMagnitude : 1) - 1;
         = (int) Math.pow(2, ( + 1));
         =  / 2;
         = ( - 1) << ;
        // determine exponent range needed to support the trackable value with no overflow:
        long trackableValue = ( - 1) << ;
        int bucketsNeeded = 1;
        while (trackableValue < highestTrackableValue) {
            trackableValue <<= 1;
            bucketsNeeded++;
        }
        this. = bucketsNeeded;
         = ( + 1) * ( / 2);
        setTotalCount(totalCount);
         = new HistogramData(this);
    }


    
get the configured lowestTrackableValue

Returns:
lowestTrackableValue
    public long getLowestTrackableValue() {
        return ;
    }

    
get the configured highestTrackableValue

Returns:
highestTrackableValue
    public long getHighestTrackableValue() {
        return ;
    }

    
get the configured numberOfSignificantValueDigits

Returns:
numberOfSignificantValueDigits
    public int getNumberOfSignificantValueDigits() {
        return ;
    }
    private int countsArrayIndex(final int bucketIndexfinal int subBucketIndex) {
        assert(subBucketIndex < );
        assert(bucketIndex < );
        assert(bucketIndex == 0 || (subBucketIndex >= ));
        // Calculate the index for the first entry in the bucket:
        // (The following is the equivalent of ((bucketIndex + 1) * subBucketHalfCount) ):
        int bucketBaseIndex = (bucketIndex + 1) << ;
        // Calculate the offset in the bucket:
        int offsetInBucket = subBucketIndex - ;
        // The following is the equivalent of ((subBucketIndex  - subBucketHalfCount) + bucketBaseIndex;
        return bucketBaseIndex + offsetInBucket;
    }
    long getCountAt(final int bucketIndexfinal int subBucketIndex) {
        return getCountAtIndex(countsArrayIndex(bucketIndexsubBucketIndex));
    }
    private static void arrayAdd(final AbstractHistogram toHistogramfinal AbstractHistogram fromHistogram) {
        if (fromHistogram.countsArrayLength != toHistogram.countsArrayLengththrow new IndexOutOfBoundsException();
        for (int i = 0; i < fromHistogram.countsArrayLengthi++)
            toHistogram.addToCountAtIndex(ifromHistogram.getCountAtIndex(i));
    }
    int getBucketIndex(final long value) {
        int pow2ceiling = 64 - Long.numberOfLeadingZeros(value | ); // smallest power of 2 containing value
        return  pow2ceiling -  - ( + 1);
    }
    int getSubBucketIndex(long valueint bucketIndex) {
        return  (int)(value >> (bucketIndex + ));
    }
    private void recordCountAtValue(final long countfinal long valuethrows ArrayIndexOutOfBoundsException {
        // Dissect the value into bucket and sub-bucket parts, and derive index into counts array:
        int bucketIndex = getBucketIndex(value);
        int subBucketIndex = getSubBucketIndex(valuebucketIndex);
        int countsIndex = countsArrayIndex(bucketIndexsubBucketIndex);
        addToCountAtIndex(countsIndexcount);
        addToTotalCount(count);
    }
    private void recordSingleValue(final long valuethrows ArrayIndexOutOfBoundsException {
        // Dissect the value into bucket and sub-bucket parts, and derive index into counts array:
        int bucketIndex = getBucketIndex(value);
        int subBucketIndex = getSubBucketIndex(valuebucketIndex);
        int countsIndex = countsArrayIndex(bucketIndexsubBucketIndex);
        incrementCountAtIndex(countsIndex);
        incrementTotalCount();
    }
    private void recordValueWithCountAndExpectedInterval(final long valuefinal long count,
                                                         final long expectedIntervalBetweenValueSamplesthrows ArrayIndexOutOfBoundsException {
        recordCountAtValue(countvalue);
        if (expectedIntervalBetweenValueSamples <=0)
            return;
        for (long missingValue = value - expectedIntervalBetweenValueSamples;
             missingValue >= expectedIntervalBetweenValueSamples;
             missingValue -= expectedIntervalBetweenValueSamples) {
            recordCountAtValue(countmissingValue);
        }
    }

    
Record a value in the histogram.

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.

Note: This is a at-recording correction method, as opposed to the post-recording correction method provided by getHistogramCorrectedForCoordinatedOmission. 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.

See notes in the description of the Histogram calls for an illustration of why this corrective behavior is important.

Parameters:
value The value to record
expectedIntervalBetweenValueSamples If expectedIntervalBetweenValueSamples is larger than 0, add auto-generated value records as appropriate if value is larger than expectedIntervalBetweenValueSamples
Throws:
java.lang.ArrayIndexOutOfBoundsException
    public void recordValueWithExpectedInterval(final long valuefinal long expectedIntervalBetweenValueSamplesthrows ArrayIndexOutOfBoundsException {
        recordValueWithCountAndExpectedInterval(value, 1, expectedIntervalBetweenValueSamples);
    }

    

Deprecated:
Record a value in the histogram. This deprecated method has identical behavior to recordValueWithExpectedInterval(). It was renamed to avoid ambiguity.
Parameters:
value The value to record
expectedIntervalBetweenValueSamples If expectedIntervalBetweenValueSamples is larger than 0, add auto-generated value records as appropriate if value is larger than expectedIntervalBetweenValueSamples
Throws:
java.lang.ArrayIndexOutOfBoundsException
    public void recordValue(final long valuefinal long expectedIntervalBetweenValueSamplesthrows ArrayIndexOutOfBoundsException {
        recordValueWithExpectedInterval(valueexpectedIntervalBetweenValueSamples);
    }


    
Record a value in the histogram (adding to the value's current count)

Parameters:
value The value to be recorded
count The number of occurrences of this value to record
Throws:
java.lang.ArrayIndexOutOfBoundsException
    public void recordValueWithCount(final long valuefinal long countthrows ArrayIndexOutOfBoundsException {
        recordCountAtValue(countvalue);
    }

    
Record a value in the histogram

Parameters:
value The value to be recorded
Throws:
java.lang.ArrayIndexOutOfBoundsException
    public void recordValue(final long valuethrows ArrayIndexOutOfBoundsException {
        recordSingleValue(value);
    }

    
Reset the contents and stats of this histogram
    public void reset() {
        clearCounts();
    }

    
Add the contents of another histogram to this one

Parameters:
fromHistogram The other histogram. highestTrackableValue and largestValueWithSingleUnitResolution must match.
    public void add(final AbstractHistogram fromHistogram) {
        if (( != fromHistogram.highestTrackableValue) ||
                ( != fromHistogram.numberOfSignificantValueDigits) ||
                ( != fromHistogram.bucketCount) ||
                ( != fromHistogram.subBucketCount))
            throw new IllegalArgumentException("Cannot add histograms with incompatible ranges");
        arrayAdd(thisfromHistogram);
        setTotalCount(getTotalCount() + fromHistogram.getTotalCount());
    }

    
Add the contents of another histogram to this one, while correcting the incoming data for coordinated omission.

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 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

See notes in the description of the Histogram calls for an illustration of why this corrective behavior is important.

Parameters:
fromHistogram The other histogram. highestTrackableValue and largestValueWithSingleUnitResolution must match.
expectedIntervalBetweenValueSamples If expectedIntervalBetweenValueSamples is larger than 0, add auto-generated value records as appropriate if value is larger than expectedIntervalBetweenValueSamples
Throws:
java.lang.ArrayIndexOutOfBoundsException
    public void addWhileCorrectingForCoordinatedOmission(final AbstractHistogram fromHistogramfinal long expectedIntervalBetweenValueSamples) {
        final AbstractHistogram toHistogram = this;
        for (HistogramIterationValue v : fromHistogram.getHistogramData().recordedValues()) {
            toHistogram.recordValueWithCountAndExpectedInterval(v.getValueIteratedTo(),
                    v.getCountAtValueIteratedTo(), expectedIntervalBetweenValueSamples);
        }
    }

    
Determine if this histogram had any of it's value counts overflow. Since counts are kept in fixed integer form with potentially limited range (e.g. int and short), a specific value range count could potentially overflow, leading to an inaccurate and misleading histogram representation. This method accurately determines whether or not an overflow condition has happened in an IntHistogram or ShortHistogram.

Returns:
True if this histogram has had a count value overflow.
    public boolean hasOverflowed() {
        // On overflow, the totalCount accumulated counter will (always) not match the total of counts
        long totalCounted = 0;
        for (int i = 0; i < i++) {
            totalCounted += getCountAtIndex(i);
        }
        return (totalCounted != getTotalCount());
    }

    
Determine if this histogram is equivalent to another.

Parameters:
other the other histogram to compare to
Returns:
True if this histogram are equivalent with the other.
    public boolean equals(Object other){
        if ( this == other ) return true;
        if ( !(other instanceof AbstractHistogram) ) return false;
        AbstractHistogram that = (AbstractHistogram)other;
        if (( != that.highestTrackableValue) ||
                ( != that.numberOfSignificantValueDigits))
            return false;
        if ( != that.countsArrayLength)
            return false;
        if (getTotalCount() != that.getTotalCount())
            return false;
        return true;
    }

    
Provide access to the histogram's data set.

Returns:
a HistogramData that can be used to query stats and iterate through the default (corrected) data set.
    public HistogramData getHistogramData() {
        return ;
    }

    
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.

Parameters:
value The given value
Returns:
The lowest value that is equivalent to the given value within the histogram's resolution.
    public long sizeOfEquivalentValueRange(final long value) {
        int bucketIndex = getBucketIndex(value);
        int subBucketIndex = getSubBucketIndex(valuebucketIndex);
        long distanceToNextValue =
                (1 << (  + ((subBucketIndex >= ) ? (bucketIndex + 1) : bucketIndex)));
        return distanceToNextValue;
    }

    
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.

Parameters:
value The given value
Returns:
The lowest value that is equivalent to the given value within the histogram's resolution.
    public long lowestEquivalentValue(final long value) {
        int bucketIndex = getBucketIndex(value);
        int subBucketIndex = getSubBucketIndex(valuebucketIndex);
        long thisValueBaseLevel = valueFromIndex(bucketIndexsubBucketIndex);
        return thisValueBaseLevel;
    }

    
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.

Parameters:
value The given value
Returns:
The highest value that is equivalent to the given value within the histogram's resolution.
    public long highestEquivalentValue(final long value) {
        return nextNonEquivalentValue(value) - 1;
    }

    
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.

Parameters:
value The given value
Returns:
The value lies in the middle (rounded up) of the range of values equivalent the given value.
    public long medianEquivalentValue(final long value) {
        return (lowestEquivalentValue(value) + (sizeOfEquivalentValueRange(value) >> 1));
    }

    
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.

Parameters:
value The given value
Returns:
The next value that is not equivalent to the given value within the histogram's resolution.
    public long nextNonEquivalentValue(final long value) {
        return lowestEquivalentValue(value) + sizeOfEquivalentValueRange(value);
    }

    
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.

Parameters:
value1 first value to compare
value2 second value to compare
Returns:
True if values are equivalent with the histogram's resolution.
    public boolean valuesAreEquivalent(final long value1final long value2) {
        return (lowestEquivalentValue(value1) == lowestEquivalentValue(value2));
    }
    private static final long serialVersionUID = 42L;
    private void writeObject(final ObjectOutputStream o)
            throws IOException
    {
        o.writeLong(getTotalCount()); // Needed because overflow situations may lead this to differ from counts totals
    }
    private void readObject(final ObjectInputStream o)
            throws IOExceptionClassNotFoundException {
        final long lowestTrackableValue = o.readLong();
        final long highestTrackableValue = o.readLong();
        final int numberOfSignificantValueDigits = o.readInt();
        final long totalCount = o.readLong();
        init(lowestTrackableValuehighestTrackableValuenumberOfSignificantValueDigitstotalCount);
        setTotalCount(totalCount);
    }
    static final long valueFromIndex(int bucketIndexint subBucketIndexint unitMagnitude)
    {
        return ((longsubBucketIndex) << ( bucketIndex + unitMagnitude);
    }
New to GrepCode? Check out our FAQ X