diff options
3 files changed, 275 insertions, 18 deletions
diff --git a/core/java/com/android/internal/expresslog/Histogram.java b/core/java/com/android/internal/expresslog/Histogram.java index 2f3b662af6a7..65fbb03bf967 100644 --- a/core/java/com/android/internal/expresslog/Histogram.java +++ b/core/java/com/android/internal/expresslog/Histogram.java @@ -16,10 +16,14 @@ package com.android.internal.expresslog; +import android.annotation.FloatRange; +import android.annotation.IntRange; import android.annotation.NonNull; import com.android.internal.util.FrameworkStatsLog; +import java.util.Arrays; + /** Histogram encapsulates StatsD write API calls */ public final class Histogram { @@ -28,7 +32,8 @@ public final class Histogram { /** * Creates Histogram metric logging wrapper - * @param metricId to log, logging will be no-op if metricId is not defined in the TeX catalog + * + * @param metricId to log, logging will be no-op if metricId is not defined in the TeX catalog * @param binOptions to calculate bin index for samples * @hide */ @@ -39,6 +44,7 @@ public final class Histogram { /** * Logs increment sample count for automatically calculated bin + * * @param sample value * @hide */ @@ -52,6 +58,7 @@ public final class Histogram { public interface BinOptions { /** * Returns bins count to be used by a histogram + * * @return bins count used to initialize Options, including overflow & underflow bins * @hide */ @@ -61,6 +68,7 @@ public final class Histogram { * Returns bin index for the input sample value * index == 0 stands for underflow * index == getBinsCount() - 1 stands for overflow + * * @return zero based index * @hide */ @@ -76,17 +84,19 @@ public final class Histogram { private final float mBinSize; /** - * Creates otpions for uniform (linear) sized bins - * @param binCount amount of histogram bins. 2 bin indexes will be calculated - * automatically to represent undeflow & overflow bins - * @param minValue is included in the first bin, values less than minValue - * go to underflow bin + * Creates options for uniform (linear) sized bins + * + * @param binCount amount of histogram bins. 2 bin indexes will be calculated + * automatically to represent underflow & overflow bins + * @param minValue is included in the first bin, values less than minValue + * go to underflow bin * @param exclusiveMaxValue is included in the overflow bucket. For accurate - measure up to kMax, then exclusiveMaxValue + * measure up to kMax, then exclusiveMaxValue * should be set to kMax + 1 * @hide */ - public UniformOptions(int binCount, float minValue, float exclusiveMaxValue) { + public UniformOptions(@IntRange(from = 1) int binCount, float minValue, + float exclusiveMaxValue) { if (binCount < 1) { throw new IllegalArgumentException("Bin count should be positive number"); } @@ -99,7 +109,7 @@ public final class Histogram { mExclusiveMaxValue = exclusiveMaxValue; mBinSize = (mExclusiveMaxValue - minValue) / binCount; - // Implicitly add 2 for the extra undeflow & overflow bins + // Implicitly add 2 for the extra underflow & overflow bins mBinCount = binCount + 2; } @@ -120,4 +130,92 @@ public final class Histogram { return (int) ((sample - mMinValue) / mBinSize + 1); } } + + /** Used by Histogram to map data sample to corresponding bin for scaled bins */ + public static final class ScaledRangeOptions implements BinOptions { + // store minimum value per bin + final long[] mBins; + + /** + * Creates options for scaled range bins + * + * @param binCount amount of histogram bins. 2 bin indexes will be calculated + * automatically to represent underflow & overflow bins + * @param minValue is included in the first bin, values less than minValue + * go to underflow bin + * @param firstBinWidth used to represent first bin width and as a reference to calculate + * width for consecutive bins + * @param scaleFactor used to calculate width for consecutive bins + * @hide + */ + public ScaledRangeOptions(@IntRange(from = 1) int binCount, int minValue, + @FloatRange(from = 1.f) float firstBinWidth, + @FloatRange(from = 1.f) float scaleFactor) { + if (binCount < 1) { + throw new IllegalArgumentException("Bin count should be positive number"); + } + + if (firstBinWidth < 1.f) { + throw new IllegalArgumentException( + "First bin width invalid (should be 1.f at minimum)"); + } + + if (scaleFactor < 1.f) { + throw new IllegalArgumentException( + "Scaled factor invalid (should be 1.f at minimum)"); + } + + // precalculating bins ranges (no need to create a bin for underflow reference value) + mBins = initBins(binCount + 1, minValue, firstBinWidth, scaleFactor); + } + + @Override + public int getBinsCount() { + return mBins.length + 1; + } + + @Override + public int getBinForSample(float sample) { + if (sample < mBins[0]) { + // goes to underflow + return 0; + } else if (sample >= mBins[mBins.length - 1]) { + // goes to overflow + return mBins.length; + } + + return lower_bound(mBins, (long) sample) + 1; + } + + // To find lower bound using binary search implementation of Arrays utility class + private static int lower_bound(long[] array, long sample) { + int index = Arrays.binarySearch(array, sample); + // If key is not present in the array + if (index < 0) { + // Index specify the position of the key when inserted in the sorted array + // so the element currently present at this position will be the lower bound + return Math.abs(index) - 2; + } + return index; + } + + private static long[] initBins(int count, int minValue, float firstBinWidth, + float scaleFactor) { + long[] bins = new long[count]; + bins[0] = minValue; + double lastWidth = firstBinWidth; + for (int i = 1; i < count; i++) { + // current bin minValue = previous bin width * scaleFactor + double currentBinMinValue = bins[i - 1] + lastWidth; + if (currentBinMinValue > Integer.MAX_VALUE) { + throw new IllegalArgumentException( + "Attempted to create a bucket larger than maxint"); + } + + bins[i] = (long) currentBinMinValue; + lastWidth *= scaleFactor; + } + return bins; + } + } } diff --git a/core/tests/expresslog/src/com/android/internal/expresslog/ScaledRangeOptionsTest.java b/core/tests/expresslog/src/com/android/internal/expresslog/ScaledRangeOptionsTest.java new file mode 100644 index 000000000000..ee62d7528818 --- /dev/null +++ b/core/tests/expresslog/src/com/android/internal/expresslog/ScaledRangeOptionsTest.java @@ -0,0 +1,167 @@ +/* + * Copyright (C) 2023 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package com.android.internal.expresslog; + +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.assertTrue; + +import androidx.test.filters.SmallTest; + +import org.junit.Test; +import org.junit.runner.RunWith; +import org.junit.runners.JUnit4; + +@RunWith(JUnit4.class) +@SmallTest +public class ScaledRangeOptionsTest { + private static final String TAG = ScaledRangeOptionsTest.class.getSimpleName(); + + @Test + public void testGetBinsCount() { + Histogram.ScaledRangeOptions options1 = new Histogram.ScaledRangeOptions(1, 100, 100, 2); + assertEquals(3, options1.getBinsCount()); + + Histogram.ScaledRangeOptions options10 = new Histogram.ScaledRangeOptions(10, 100, 100, 2); + assertEquals(12, options10.getBinsCount()); + } + + @Test(expected = IllegalArgumentException.class) + public void testConstructZeroBinsCount() { + new Histogram.ScaledRangeOptions(0, 100, 100, 2); + } + + @Test(expected = IllegalArgumentException.class) + public void testConstructNegativeBinsCount() { + new Histogram.ScaledRangeOptions(-1, 100, 100, 2); + } + + @Test(expected = IllegalArgumentException.class) + public void testConstructNegativeFirstBinWidth() { + new Histogram.ScaledRangeOptions(10, 100, -100, 2); + } + + @Test(expected = IllegalArgumentException.class) + public void testConstructTooSmallFirstBinWidth() { + new Histogram.ScaledRangeOptions(10, 100, 0.5f, 2); + } + + @Test(expected = IllegalArgumentException.class) + public void testConstructNegativeScaleFactor() { + new Histogram.ScaledRangeOptions(10, 100, 100, -2); + } + + @Test(expected = IllegalArgumentException.class) + public void testConstructTooSmallScaleFactor() { + new Histogram.ScaledRangeOptions(10, 100, 100, 0.5f); + } + + @Test(expected = IllegalArgumentException.class) + public void testConstructTooBigScaleFactor() { + new Histogram.ScaledRangeOptions(10, 100, 100, 500.f); + } + + @Test(expected = IllegalArgumentException.class) + public void testConstructTooBigBinRange() { + new Histogram.ScaledRangeOptions(100, 100, 100, 10.f); + } + + @Test + public void testBinIndexForRangeEqual1() { + Histogram.ScaledRangeOptions options = new Histogram.ScaledRangeOptions(10, 1, 1, 1); + assertEquals(12, options.getBinsCount()); + + assertEquals(11, options.getBinForSample(11)); + + for (int i = 0, bins = options.getBinsCount(); i < bins; i++) { + assertEquals(i, options.getBinForSample(i)); + } + } + + @Test + public void testBinIndexForRangeEqual2() { + // this should produce bin otpions similar to linear histogram with bin width 2 + Histogram.ScaledRangeOptions options = new Histogram.ScaledRangeOptions(10, 1, 2, 1); + assertEquals(12, options.getBinsCount()); + + for (int i = 0, bins = options.getBinsCount(); i < bins; i++) { + assertEquals(i, options.getBinForSample(i * 2)); + assertEquals(i, options.getBinForSample(i * 2 - 1)); + } + } + + @Test + public void testBinIndexForRangeEqual5() { + Histogram.ScaledRangeOptions options = new Histogram.ScaledRangeOptions(2, 0, 5, 1); + assertEquals(4, options.getBinsCount()); + for (int i = 0; i < 2; i++) { + for (int sample = 0; sample < 5; sample++) { + assertEquals(i + 1, options.getBinForSample(i * 5 + sample)); + } + } + } + + @Test + public void testBinIndexForRangeEqual10() { + Histogram.ScaledRangeOptions options = new Histogram.ScaledRangeOptions(10, 1, 10, 1); + assertEquals(0, options.getBinForSample(0)); + assertEquals(options.getBinsCount() - 2, options.getBinForSample(100)); + assertEquals(options.getBinsCount() - 1, options.getBinForSample(101)); + + final float binSize = (101 - 1) / 10f; + for (int i = 1, bins = options.getBinsCount() - 1; i < bins; i++) { + assertEquals(i, options.getBinForSample(i * binSize)); + } + } + + @Test + public void testBinIndexForScaleFactor2() { + final int binsCount = 10; + final int minValue = 10; + final int firstBinWidth = 5; + final int scaledFactor = 2; + + Histogram.ScaledRangeOptions options = new Histogram.ScaledRangeOptions( + binsCount, minValue, firstBinWidth, scaledFactor); + assertEquals(binsCount + 2, options.getBinsCount()); + long[] binCounts = new long[10]; + + // precalculate max valid value - start value for the overflow bin + int lastBinStartValue = minValue; //firstBinMin value + int lastBinWidth = firstBinWidth; + for (int binIdx = 2; binIdx <= binsCount + 1; binIdx++) { + lastBinStartValue = lastBinStartValue + lastBinWidth; + lastBinWidth *= scaledFactor; + } + + // underflow bin + for (int i = 1; i < minValue; i++) { + assertEquals(0, options.getBinForSample(i)); + } + + for (int i = 10; i < lastBinStartValue; i++) { + assertTrue(options.getBinForSample(i) > 0); + assertTrue(options.getBinForSample(i) <= binsCount); + binCounts[options.getBinForSample(i) - 1]++; + } + + // overflow bin + assertEquals(binsCount + 1, options.getBinForSample(lastBinStartValue)); + + for (int i = 1; i < binsCount; i++) { + assertEquals(binCounts[i], binCounts[i - 1] * 2L); + } + } +} diff --git a/core/tests/expresslog/src/com/android/internal/expresslog/UniformOptionsTest.java b/core/tests/expresslog/src/com/android/internal/expresslog/UniformOptionsTest.java index 9fa6d0634fbe..037dbb32c2f8 100644 --- a/core/tests/expresslog/src/com/android/internal/expresslog/UniformOptionsTest.java +++ b/core/tests/expresslog/src/com/android/internal/expresslog/UniformOptionsTest.java @@ -24,11 +24,11 @@ import org.junit.runner.RunWith; import org.junit.runners.JUnit4; @RunWith(JUnit4.class) +@SmallTest public class UniformOptionsTest { private static final String TAG = UniformOptionsTest.class.getSimpleName(); @Test - @SmallTest public void testGetBinsCount() { Histogram.UniformOptions options1 = new Histogram.UniformOptions(1, 100, 1000); assertEquals(3, options1.getBinsCount()); @@ -38,25 +38,21 @@ public class UniformOptionsTest { } @Test(expected = IllegalArgumentException.class) - @SmallTest public void testConstructZeroBinsCount() { new Histogram.UniformOptions(0, 100, 1000); } @Test(expected = IllegalArgumentException.class) - @SmallTest public void testConstructNegativeBinsCount() { new Histogram.UniformOptions(-1, 100, 1000); } @Test(expected = IllegalArgumentException.class) - @SmallTest public void testConstructMaxValueLessThanMinValue() { new Histogram.UniformOptions(10, 1000, 100); } @Test - @SmallTest public void testBinIndexForRangeEqual1() { Histogram.UniformOptions options = new Histogram.UniformOptions(10, 1, 11); for (int i = 0, bins = options.getBinsCount(); i < bins; i++) { @@ -65,7 +61,6 @@ public class UniformOptionsTest { } @Test - @SmallTest public void testBinIndexForRangeEqual2() { Histogram.UniformOptions options = new Histogram.UniformOptions(10, 1, 21); for (int i = 0, bins = options.getBinsCount(); i < bins; i++) { @@ -75,7 +70,6 @@ public class UniformOptionsTest { } @Test - @SmallTest public void testBinIndexForRangeEqual5() { Histogram.UniformOptions options = new Histogram.UniformOptions(2, 0, 10); assertEquals(4, options.getBinsCount()); @@ -87,7 +81,6 @@ public class UniformOptionsTest { } @Test - @SmallTest public void testBinIndexForRangeEqual10() { Histogram.UniformOptions options = new Histogram.UniformOptions(10, 1, 101); assertEquals(0, options.getBinForSample(0)); @@ -101,7 +94,6 @@ public class UniformOptionsTest { } @Test - @SmallTest public void testBinIndexForRangeEqual90() { final int binCount = 10; final int minValue = 100; |