From 2cf23303144969fd66d88dd105b09d17fda989d0 Mon Sep 17 00:00:00 2001 From: twerth Date: Mon, 13 Aug 2018 04:53:15 -0700 Subject: Add new class to create cpu usage time series. RELNOTES: None PiperOrigin-RevId: 208462186 --- .../build/lib/profiler/CpuUsageTimeSeries.java | 87 ++++++++++++++++++++++ .../build/lib/profiler/CpuUsageTimeSeriesTest.java | 79 ++++++++++++++++++++ 2 files changed, 166 insertions(+) create mode 100644 src/main/java/com/google/devtools/build/lib/profiler/CpuUsageTimeSeries.java create mode 100644 src/test/java/com/google/devtools/build/lib/profiler/CpuUsageTimeSeriesTest.java (limited to 'src') diff --git a/src/main/java/com/google/devtools/build/lib/profiler/CpuUsageTimeSeries.java b/src/main/java/com/google/devtools/build/lib/profiler/CpuUsageTimeSeries.java new file mode 100644 index 0000000000..faadb7357a --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/profiler/CpuUsageTimeSeries.java @@ -0,0 +1,87 @@ +// Copyright 2018 The Bazel Authors. All rights reserved. +// +// 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.google.devtools.build.lib.profiler; + +import java.util.Arrays; + +/** + * Converts a set of ranges into a graph by counting the number of ranges that are active at any + * point in time. Time is split into equal-sized buckets, and we compute one value per bucket. If a + * range partially overlaps a bucket, then the bucket is incremented by the fraction of overlap. + */ +public class CpuUsageTimeSeries { + private final long startTimeMillis; + private final long bucketSizeMillis; + private static final int INITIAL_SIZE = 100; + private double[] data = new double[INITIAL_SIZE]; + + public CpuUsageTimeSeries(long startTimeMillis, long bucketSizeMillis) { + this.startTimeMillis = startTimeMillis; + this.bucketSizeMillis = bucketSizeMillis; + } + + public void addRange(long startTimeMillis, long endTimeMillis) { + addRange(startTimeMillis, endTimeMillis, /* value= */ 1); + } + + /** Adds a new range to the time series, by increasing every affected bucket by value. */ + public void addRange(long rangeStartMillis, long rangeEndMillis, double value) { + // Compute times relative to start and their positions in the data array. + rangeStartMillis -= startTimeMillis; + rangeEndMillis -= startTimeMillis; + int startPosition = (int) (rangeStartMillis / bucketSizeMillis); + int endPosition = (int) (rangeEndMillis / bucketSizeMillis); + + // Assume we add the following range R: + // ---------------------------------- + // | |ssRRR|RRRRR|Reeee| | + // ---------------------------------- + // we cannot just add value to each affected bucket but have to correct the values for the first + // and last bucket by calculating the size of 's' and 'e'. + double missingStartFraction = + ((double) (rangeStartMillis - bucketSizeMillis * startPosition)) / bucketSizeMillis; + double missingEndFraction = + ((double) (bucketSizeMillis * (endPosition + 1) - rangeEndMillis)) / bucketSizeMillis; + + if (startPosition < 0) { + startPosition = 0; + missingStartFraction = 0; + } + if (endPosition < startPosition) { + endPosition = startPosition; + missingEndFraction = 0; + } + + // Resize data array if necessary so it can at least fit endPosition. + if (endPosition >= data.length) { + data = Arrays.copyOf(data, Math.max(endPosition + 1, 2 * data.length)); + } + + // Do the actual update. + for (int i = startPosition; i <= endPosition; i++) { + double fraction = 1; + if (i == startPosition) { + fraction -= missingStartFraction; + } + if (i == endPosition) { + fraction -= missingEndFraction; + } + data[i] += fraction * value; + } + } + + public double[] toDoubleArray(int len) { + return Arrays.copyOf(data, len); + } +} diff --git a/src/test/java/com/google/devtools/build/lib/profiler/CpuUsageTimeSeriesTest.java b/src/test/java/com/google/devtools/build/lib/profiler/CpuUsageTimeSeriesTest.java new file mode 100644 index 0000000000..9d375308c9 --- /dev/null +++ b/src/test/java/com/google/devtools/build/lib/profiler/CpuUsageTimeSeriesTest.java @@ -0,0 +1,79 @@ +// Copyright 2018 The Bazel Authors. All rights reserved. +// +// 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.google.devtools.build.lib.profiler; + +import static com.google.common.truth.Truth.assertThat; + +import java.util.Arrays; +import org.junit.Test; +import org.junit.runner.RunWith; +import org.junit.runners.JUnit4; + +/** Tests for {@link CpuUsageTimeSeries}. */ +@RunWith(JUnit4.class) +public final class CpuUsageTimeSeriesTest { + @Test + public void testAddRange() { + CpuUsageTimeSeries cpuUsageTimeSeries = new CpuUsageTimeSeries(42, 100); + cpuUsageTimeSeries.addRange(42, 142); + cpuUsageTimeSeries.addRange(442, 542); + double[] values = cpuUsageTimeSeries.toDoubleArray(5); + assertThat(values).usingTolerance(1.0e-10).containsExactly(1, 0, 0, 0, 1).inOrder(); + } + + @Test + public void testAddRangeWithValue() { + CpuUsageTimeSeries cpuUsageTimeSeries = new CpuUsageTimeSeries(42, 100); + cpuUsageTimeSeries.addRange(42, 242, 3); + cpuUsageTimeSeries.addRange(442, 542, 0.5); + double[] values = cpuUsageTimeSeries.toDoubleArray(5); + assertThat(values).usingTolerance(1.0e-10).containsExactly(3, 3, 0, 0, .5).inOrder(); + } + + @Test + public void testAddRangeOverlappingWithValue() { + CpuUsageTimeSeries cpuUsageTimeSeries = new CpuUsageTimeSeries(42, 100); + cpuUsageTimeSeries.addRange(42, 242, 3); + cpuUsageTimeSeries.addRange(142, 442, 0.5); + double[] values = cpuUsageTimeSeries.toDoubleArray(5); + assertThat(values).usingTolerance(1.0e-10).containsExactly(3, 3.5, 0.5, 0.5, 0).inOrder(); + } + + @Test + public void testAddRangeFractions() { + CpuUsageTimeSeries cpuUsageTimeSeries = new CpuUsageTimeSeries(42, 100); + cpuUsageTimeSeries.addRange(92, 267); + double[] values = cpuUsageTimeSeries.toDoubleArray(5); + assertThat(values).usingTolerance(1.0e-10).containsExactly(0.5, 1, 0.25, 0, 0).inOrder(); + } + + @Test + public void testAddRangeWithValueFractions() { + CpuUsageTimeSeries cpuUsageTimeSeries = new CpuUsageTimeSeries(42, 100); + cpuUsageTimeSeries.addRange(92, 267, 3); + double[] values = cpuUsageTimeSeries.toDoubleArray(5); + assertThat(values).usingTolerance(1.0e-10).containsExactly(1.5, 3, 0.75, 0, 0).inOrder(); + } + + @Test + public void testResize() { + CpuUsageTimeSeries cpuUsageTimeSeries = new CpuUsageTimeSeries(0, 100); + cpuUsageTimeSeries.addRange(0, 100 * 100 + 1, 42); + double[] values = cpuUsageTimeSeries.toDoubleArray(101); + double[] expected = new double[101]; + Arrays.fill(expected, 0, expected.length - 1, 42); + expected[expected.length - 1] = 0.42; + assertThat(values).usingTolerance(1.0e-10).containsExactly(expected).inOrder(); + } +} -- cgit v1.2.3