1/*
2 * Copyright (C) 2016 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17package android.perftests.utils;
18
19import android.app.Activity;
20import android.app.Instrumentation;
21import android.os.Bundle;
22import android.os.Debug;
23import android.support.test.InstrumentationRegistry;
24import android.util.Log;
25
26import java.io.File;
27import java.util.ArrayList;
28import java.util.Collections;
29import java.util.concurrent.TimeUnit;
30
31/**
32 * Provides a benchmark framework.
33 *
34 * Example usage:
35 * // Executes the code while keepRunning returning true.
36 *
37 * public void sampleMethod() {
38 *     BenchmarkState state = new BenchmarkState();
39 *
40 *     int[] src = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
41 *     while (state.keepRunning()) {
42 *         int[] dest = new int[src.length];
43 *         System.arraycopy(src, 0, dest, 0, src.length);
44 *     }
45 *     System.out.println(state.summaryLine());
46 * }
47 */
48public final class BenchmarkState {
49
50    private static final String TAG = "BenchmarkState";
51    private static final boolean ENABLE_PROFILING = false;
52
53    private static final int NOT_STARTED = 0;  // The benchmark has not started yet.
54    private static final int WARMUP = 1; // The benchmark is warming up.
55    private static final int RUNNING = 2;  // The benchmark is running.
56    private static final int FINISHED = 3;  // The benchmark has stopped.
57
58    private int mState = NOT_STARTED;  // Current benchmark state.
59
60    private static final long WARMUP_DURATION_NS = ms2ns(250); // warm-up for at least 250ms
61    private static final int WARMUP_MIN_ITERATIONS = 16; // minimum iterations to warm-up for
62
63    // TODO: Tune these values.
64    private static final long TARGET_TEST_DURATION_NS = ms2ns(500); // target testing for 500 ms
65    private static final int MAX_TEST_ITERATIONS = 1000000;
66    private static final int MIN_TEST_ITERATIONS = 10;
67    private static final int REPEAT_COUNT = 5;
68
69    private long mStartTimeNs = 0;  // Previously captured System.nanoTime().
70    private boolean mPaused;
71    private long mPausedTimeNs = 0; // The System.nanoTime() when the pauseTiming() is called.
72    private long mPausedDurationNs = 0;  // The duration of paused state in nano sec.
73
74    private int mIteration = 0;
75    private int mMaxIterations = 0;
76
77    private int mRepeatCount = 0;
78
79    // Statistics. These values will be filled when the benchmark has finished.
80    // The computation needs double precision, but long int is fine for final reporting.
81    private long mMedian = 0;
82    private double mMean = 0.0;
83    private double mStandardDeviation = 0.0;
84    private long mMin = 0;
85
86    // Individual duration in nano seconds.
87    private ArrayList<Long> mResults = new ArrayList<>();
88
89    private static final long ms2ns(long ms) {
90        return TimeUnit.MILLISECONDS.toNanos(ms);
91    }
92
93    /**
94     * Calculates statistics.
95     */
96    private void calculateSatistics() {
97        final int size = mResults.size();
98        if (size <= 1) {
99            throw new IllegalStateException("At least two results are necessary.");
100        }
101
102        Collections.sort(mResults);
103        mMedian = size % 2 == 0 ? (mResults.get(size / 2) + mResults.get(size / 2 + 1)) / 2 :
104                mResults.get(size / 2);
105
106        mMin = mResults.get(0);
107        for (int i = 0; i < size; ++i) {
108            long result = mResults.get(i);
109            mMean += result;
110            if (result < mMin) {
111                mMin = result;
112            }
113        }
114        mMean /= (double) size;
115
116        for (int i = 0; i < size; ++i) {
117            final double tmp = mResults.get(i) - mMean;
118            mStandardDeviation += tmp * tmp;
119        }
120        mStandardDeviation = Math.sqrt(mStandardDeviation / (double) (size - 1));
121    }
122
123    // Stops the benchmark timer.
124    // This method can be called only when the timer is running.
125    public void pauseTiming() {
126        if (mPaused) {
127            throw new IllegalStateException(
128                    "Unable to pause the benchmark. The benchmark has already paused.");
129        }
130        mPausedTimeNs = System.nanoTime();
131        mPaused = true;
132    }
133
134    // Starts the benchmark timer.
135    // This method can be called only when the timer is stopped.
136    public void resumeTiming() {
137        if (!mPaused) {
138            throw new IllegalStateException(
139                    "Unable to resume the benchmark. The benchmark is already running.");
140        }
141        mPausedDurationNs += System.nanoTime() - mPausedTimeNs;
142        mPausedTimeNs = 0;
143        mPaused = false;
144    }
145
146    private void beginWarmup() {
147        mStartTimeNs = System.nanoTime();
148        mIteration = 0;
149        mState = WARMUP;
150    }
151
152    private void beginBenchmark(long warmupDuration, int iterations) {
153        if (ENABLE_PROFILING) {
154            File f = new File(InstrumentationRegistry.getContext().getDataDir(), "benchprof");
155            Log.d(TAG, "Tracing to: " + f.getAbsolutePath());
156            Debug.startMethodTracingSampling(f.getAbsolutePath(), 16 * 1024 * 1024, 100);
157        }
158        mMaxIterations = (int) (TARGET_TEST_DURATION_NS / (warmupDuration / iterations));
159        mMaxIterations = Math.min(MAX_TEST_ITERATIONS,
160                Math.max(mMaxIterations, MIN_TEST_ITERATIONS));
161        mPausedDurationNs = 0;
162        mIteration = 0;
163        mRepeatCount = 0;
164        mState = RUNNING;
165        mStartTimeNs = System.nanoTime();
166    }
167
168    private boolean startNextTestRun() {
169        final long currentTime = System.nanoTime();
170        mResults.add((currentTime - mStartTimeNs - mPausedDurationNs) / mMaxIterations);
171        mRepeatCount++;
172        if (mRepeatCount >= REPEAT_COUNT) {
173            if (ENABLE_PROFILING) {
174                Debug.stopMethodTracing();
175            }
176            calculateSatistics();
177            mState = FINISHED;
178            return false;
179        }
180        mPausedDurationNs = 0;
181        mIteration = 0;
182        mStartTimeNs = System.nanoTime();
183        return true;
184    }
185
186    /**
187     * Judges whether the benchmark needs more samples.
188     *
189     * For the usage, see class comment.
190     */
191    public boolean keepRunning() {
192        switch (mState) {
193            case NOT_STARTED:
194                beginWarmup();
195                return true;
196            case WARMUP:
197                mIteration++;
198                // Only check nanoTime on every iteration in WARMUP since we
199                // don't yet have a target iteration count.
200                final long duration = System.nanoTime() - mStartTimeNs;
201                if (mIteration >= WARMUP_MIN_ITERATIONS && duration >= WARMUP_DURATION_NS) {
202                    beginBenchmark(duration, mIteration);
203                }
204                return true;
205            case RUNNING:
206                mIteration++;
207                if (mIteration >= mMaxIterations) {
208                    return startNextTestRun();
209                }
210                if (mPaused) {
211                    throw new IllegalStateException(
212                            "Benchmark step finished with paused state. " +
213                            "Resume the benchmark before finishing each step.");
214                }
215                return true;
216            case FINISHED:
217                throw new IllegalStateException("The benchmark has finished.");
218            default:
219                throw new IllegalStateException("The benchmark is in unknown state.");
220        }
221    }
222
223    private long mean() {
224        if (mState != FINISHED) {
225            throw new IllegalStateException("The benchmark hasn't finished");
226        }
227        return (long) mMean;
228    }
229
230    private long median() {
231        if (mState != FINISHED) {
232            throw new IllegalStateException("The benchmark hasn't finished");
233        }
234        return mMedian;
235    }
236
237    private long min() {
238        if (mState != FINISHED) {
239            throw new IllegalStateException("The benchmark hasn't finished");
240        }
241        return mMin;
242    }
243
244    private long standardDeviation() {
245        if (mState != FINISHED) {
246            throw new IllegalStateException("The benchmark hasn't finished");
247        }
248        return (long) mStandardDeviation;
249    }
250
251    private String summaryLine() {
252        StringBuilder sb = new StringBuilder();
253        sb.append("Summary: ");
254        sb.append("median=").append(median()).append("ns, ");
255        sb.append("mean=").append(mean()).append("ns, ");
256        sb.append("min=").append(min()).append("ns, ");
257        sb.append("sigma=").append(standardDeviation()).append(", ");
258        sb.append("iteration=").append(mResults.size()).append(", ");
259        // print out the first few iterations' number for double checking.
260        int sampleNumber = Math.min(mResults.size(), 16);
261        for (int i = 0; i < sampleNumber; i++) {
262            sb.append("No ").append(i).append(" result is ").append(mResults.get(i)).append(", ");
263        }
264        return sb.toString();
265    }
266
267    public void sendFullStatusReport(Instrumentation instrumentation, String key) {
268        Log.i(TAG, key + summaryLine());
269        Bundle status = new Bundle();
270        status.putLong(key + "_median", median());
271        status.putLong(key + "_mean", mean());
272        status.putLong(key + "_min", min());
273        status.putLong(key + "_standardDeviation", standardDeviation());
274        instrumentation.sendStatus(Activity.RESULT_OK, status);
275    }
276}
277