| 1 | /******************************************************************************* |
| 2 | * Copyright (c) 2016 École Polytechnique de Montréal |
| 3 | * |
| 4 | * All rights reserved. This program and the accompanying materials are |
| 5 | * made available under the terms of the Eclipse Public License v1.0 which |
| 6 | * accompanies this distribution, and is available at |
| 7 | * http://www.eclipse.org/legal/epl-v10.html |
| 8 | *******************************************************************************/ |
| 9 | |
| 10 | package org.eclipse.tracecompass.statesystem.core.tests.perf.historytree; |
| 11 | |
| 12 | import static org.junit.Assert.fail; |
| 13 | |
| 14 | import java.io.File; |
| 15 | import java.io.IOException; |
| 16 | import java.util.Arrays; |
| 17 | import java.util.List; |
| 18 | import java.util.PriorityQueue; |
| 19 | import java.util.Queue; |
| 20 | import java.util.Random; |
| 21 | |
| 22 | import org.apache.commons.io.FileUtils; |
| 23 | import org.eclipse.jdt.annotation.NonNull; |
| 24 | import org.eclipse.test.performance.Dimension; |
| 25 | import org.eclipse.test.performance.Performance; |
| 26 | import org.eclipse.test.performance.PerformanceMeter; |
| 27 | import org.eclipse.tracecompass.common.core.NonNullUtils; |
| 28 | import org.eclipse.tracecompass.internal.statesystem.core.backend.historytree.HistoryTreeBackend; |
| 29 | import org.eclipse.tracecompass.statesystem.core.ITmfStateSystemBuilder; |
| 30 | import org.eclipse.tracecompass.statesystem.core.StateSystemFactory; |
| 31 | import org.eclipse.tracecompass.statesystem.core.StateSystemUtils; |
| 32 | import org.eclipse.tracecompass.statesystem.core.backend.IStateHistoryBackend; |
| 33 | import org.eclipse.tracecompass.statesystem.core.backend.StateHistoryBackendFactory; |
| 34 | import org.eclipse.tracecompass.statesystem.core.exceptions.AttributeNotFoundException; |
| 35 | import org.eclipse.tracecompass.statesystem.core.exceptions.StateSystemDisposedException; |
| 36 | import org.eclipse.tracecompass.statesystem.core.exceptions.StateValueTypeException; |
| 37 | import org.eclipse.tracecompass.statesystem.core.statevalue.ITmfStateValue; |
| 38 | import org.eclipse.tracecompass.statesystem.core.statevalue.TmfStateValue; |
| 39 | import org.junit.Test; |
| 40 | import org.junit.runner.RunWith; |
| 41 | import org.junit.runners.Parameterized; |
| 42 | import org.junit.runners.Parameterized.Parameters; |
| 43 | |
| 44 | import com.google.common.collect.ImmutableList; |
| 45 | |
| 46 | /** |
| 47 | * This class benchmarks writing intervals to the state system and querying them |
| 48 | * using a history tree backend |
| 49 | * |
| 50 | * @author Geneviève Bastien |
| 51 | */ |
| 52 | @RunWith(Parameterized.class) |
| 53 | public class HistoryTreeBackendBenchmark { |
| 54 | |
| 55 | private static final @NonNull String TEST_PREFIX = "org.eclipse.tracecompass#History Tree Backend#"; |
| 56 | private static final @NonNull String TEST_BUILDING_ID = "Build: "; |
| 57 | private static final @NonNull String TEST_SINGLE_QUERY_ID = "Single Queries: "; |
| 58 | private static final @NonNull String TEST_FULL_QUERY_ID = "Full Queries: "; |
| 59 | private static final @NonNull String TEST_QUERY_RANGE_ID = "Query History Range: "; |
| 60 | private static final @NonNull String ROOT_NODE = "root"; |
| 61 | private static final int QUEUE_SIZE = 10000; |
| 62 | private static final long SEED = 5575784704147L; |
| 63 | private static final int QUERY_COUNT = 100; |
| 64 | private static final int INTERVAL_AVG_TIME = 1000; |
| 65 | |
| 66 | /* Values for the average case */ |
| 67 | private static final int DEFAULT_NB_ATTRIB = 1500; |
| 68 | private static final int DEFAULT_NB_INTERVALS = 500; |
| 69 | private static final int DEFAULT_LOOP_COUNT = 40; |
| 70 | |
| 71 | private File fTempFile; |
| 72 | private final String fName; |
| 73 | private final String fShortName; |
| 74 | private final int fNbAttrib; |
| 75 | private final int fNbAvgIntervals; |
| 76 | private final int fNbLoops; |
| 77 | private final HTBValues fValues; |
| 78 | private final IIntervalDistribution fDistributionMethod; |
| 79 | |
| 80 | /** |
| 81 | * Constructor |
| 82 | * |
| 83 | * @param name |
| 84 | * The name of the test |
| 85 | * @param shortName |
| 86 | * A short name for this scenario (at most 40 characters, |
| 87 | * otherwise it will be truncated in the DB) |
| 88 | * @param nbAttrib |
| 89 | * The number of attributes |
| 90 | * @param nbAvgIntervals |
| 91 | * An idea on the number of intervals per attributes. The exact |
| 92 | * number will depend on the interval time distribution |
| 93 | * @param nbLoops |
| 94 | * The number of times to execute the benchmark |
| 95 | * @param values |
| 96 | * The values to put in the history tree |
| 97 | * @param distributionMethod |
| 98 | * A distribution method that will return the next interval |
| 99 | * duration according to an algorithm |
| 100 | */ |
| 101 | public HistoryTreeBackendBenchmark(String name, String shortName, int nbAttrib, int nbAvgIntervals, int nbLoops, HTBValues values, IIntervalDistribution distributionMethod) { |
| 102 | fName = name; |
| 103 | fShortName = shortName; |
| 104 | fNbAttrib = nbAttrib; |
| 105 | fNbAvgIntervals = nbAvgIntervals; |
| 106 | fNbLoops = nbLoops; |
| 107 | fValues = values; |
| 108 | fDistributionMethod = distributionMethod; |
| 109 | } |
| 110 | |
| 111 | /* A list of values to use for the intervals */ |
| 112 | private enum HTBValues { |
| 113 | INTEGERS(ImmutableList.of(TmfStateValue.newValueInt(1), TmfStateValue.newValueInt(2), TmfStateValue.newValueInt(3))), |
| 114 | STRINGS(ImmutableList.of(TmfStateValue.newValueString("abc"), TmfStateValue.newValueString("def"), TmfStateValue.newValueString("wihi!"))), |
| 115 | LONGS(ImmutableList.of(TmfStateValue.newValueLong(Long.MAX_VALUE), TmfStateValue.newValueLong(1L), TmfStateValue.newValueLong(1234567L))), |
| 116 | DOUBLES(ImmutableList.of(TmfStateValue.newValueDouble(Double.MAX_VALUE), TmfStateValue.newValueDouble(1.0), TmfStateValue.newValueDouble(123.456))); |
| 117 | |
| 118 | private final List<ITmfStateValue> fValues; |
| 119 | |
| 120 | private HTBValues(List<ITmfStateValue> values) { |
| 121 | fValues = values; |
| 122 | } |
| 123 | |
| 124 | public List<ITmfStateValue> getValues() { |
| 125 | return fValues; |
| 126 | } |
| 127 | } |
| 128 | |
| 129 | @FunctionalInterface |
| 130 | private static interface IIntervalDistribution { |
| 131 | long getNextEndTime(Random randomGenerator, long limit); |
| 132 | } |
| 133 | |
| 134 | /* Generate interval duration uniformly distributed in the range [1, 2l] */ |
| 135 | private static IIntervalDistribution UNIFORM = (r, l) -> { |
| 136 | long nextLong = r.nextLong(); |
| 137 | long nextDelta = l + (nextLong % l); |
| 138 | return nextDelta; |
| 139 | }; |
| 140 | |
| 141 | /* |
| 142 | * Generates interval duration in the range [1, 2l] with 75% between [0.5l, |
| 143 | * 1.5l] |
| 144 | */ |
| 145 | private static IIntervalDistribution CLOSER_TO_LIMIT = (r, l) -> { |
| 146 | /* |
| 147 | * This method will return interval time closer to the specified limit |
| 148 | */ |
| 149 | double nextDouble = r.nextDouble(); |
| 150 | int sign = (nextDouble < 0) ? -1 : 1; |
| 151 | long nextDelta = l + (long) (Math.sqrt(nextDouble) * l * sign); |
| 152 | return nextDelta; |
| 153 | }; |
| 154 | |
| 155 | /* |
| 156 | * Generates interval duration in the range [1, 2l] with 75% between [0.5l, |
| 157 | * 1.5l], but with 10% outliers between [2l, 5l] |
| 158 | */ |
| 159 | private static IIntervalDistribution CLOSER_TO_LIMIT_10_PERCENT_OUTLIERS = (r, l) -> { |
| 160 | long nextLong = Math.abs(r.nextLong()); |
| 161 | /* Is this an outlier */ |
| 162 | if ((nextLong % 100) < 10) { |
| 163 | /* Create an outlier that can go up to 5 times the limit */ |
| 164 | return l + (((nextLong % 3) + 1) * l) + (nextLong % l); |
| 165 | } |
| 166 | /* Otherwise follow a distribution with more values around the limit */ |
| 167 | double nextDouble = r.nextDouble(); |
| 168 | int sign = (nextDouble < 0) ? -1 : 1; |
| 169 | long nextDelta = l + (long) (Math.sqrt(nextDouble) * l * sign); |
| 170 | return nextDelta; |
| 171 | }; |
| 172 | |
| 173 | /** |
| 174 | * @return The arrays of parameters |
| 175 | */ |
| 176 | @Parameters(name = "{index}: {0}") |
| 177 | public static Iterable<Object[]> getParameters() { |
| 178 | return Arrays.asList(new Object[][] { |
| 179 | { "Average case: 1500 attributes, integers, interval duration random around limit l with 75 percent within [0.5l, 1.5l]", "Average case", DEFAULT_NB_ATTRIB, DEFAULT_NB_INTERVALS, DEFAULT_LOOP_COUNT, HTBValues.INTEGERS, CLOSER_TO_LIMIT }, |
| 180 | { "Vertical scaling (more attributes)", "Vertical scaling", 3500, DEFAULT_NB_INTERVALS, 5, HTBValues.INTEGERS, CLOSER_TO_LIMIT }, |
| 181 | { "Horizontal scaling (more intervals/attribute)", "Horizontal scaling", DEFAULT_NB_ATTRIB, 20000, 10, HTBValues.INTEGERS, CLOSER_TO_LIMIT }, |
| 182 | { "Interval durations uniformly distributed within [1, 2l]", "Uniform distribution of intervals", DEFAULT_NB_ATTRIB, DEFAULT_NB_INTERVALS, DEFAULT_LOOP_COUNT, HTBValues.INTEGERS, UNIFORM }, |
| 183 | { "Interval durations with 10 percent outliers > 2l", "Distribution with outliers", DEFAULT_NB_ATTRIB, DEFAULT_NB_INTERVALS, DEFAULT_LOOP_COUNT, HTBValues.INTEGERS, CLOSER_TO_LIMIT_10_PERCENT_OUTLIERS }, |
| 184 | { "Data type: strings", "Data type: strings", DEFAULT_NB_ATTRIB, DEFAULT_NB_INTERVALS, DEFAULT_LOOP_COUNT, HTBValues.STRINGS, CLOSER_TO_LIMIT }, |
| 185 | { "Data type: longs", "Data type: longs", DEFAULT_NB_ATTRIB, DEFAULT_NB_INTERVALS, DEFAULT_LOOP_COUNT, HTBValues.LONGS, CLOSER_TO_LIMIT }, |
| 186 | { "Data type: doubles", "Data type: doubles", DEFAULT_NB_ATTRIB, DEFAULT_NB_INTERVALS, DEFAULT_LOOP_COUNT, HTBValues.DOUBLES, CLOSER_TO_LIMIT }, |
| 187 | }); |
| 188 | } |
| 189 | |
| 190 | /** |
| 191 | * Create the temporary file for this history tree |
| 192 | */ |
| 193 | private void createFile() { |
| 194 | try { |
| 195 | fTempFile = File.createTempFile("tmpStateSystem", null); |
| 196 | } catch (IOException e) { |
| 197 | fail(e.getMessage()); |
| 198 | } |
| 199 | } |
| 200 | |
| 201 | /** |
| 202 | * Delete the temporary history tree file after the test |
| 203 | */ |
| 204 | private void deleteFile() { |
| 205 | if (fTempFile != null) { |
| 206 | fTempFile.delete(); |
| 207 | fTempFile = null; |
| 208 | } |
| 209 | } |
| 210 | |
| 211 | private static class QuarkEvent implements Comparable<QuarkEvent> { |
| 212 | private final int fQuark; |
| 213 | private long fNextEventTime; |
| 214 | private final List<ITmfStateValue> fPossibleValues; |
| 215 | private int fNextValue = 0; |
| 216 | |
| 217 | public QuarkEvent(int quark, long nextEventTime, List<ITmfStateValue> valuesList) { |
| 218 | fQuark = quark; |
| 219 | fNextEventTime = nextEventTime; |
| 220 | fPossibleValues = valuesList; |
| 221 | } |
| 222 | |
| 223 | public int getQuark() { |
| 224 | return fQuark; |
| 225 | } |
| 226 | |
| 227 | public long getNextEventTime() { |
| 228 | return fNextEventTime; |
| 229 | } |
| 230 | |
| 231 | public void setNextEventTime(long t) { |
| 232 | fNextEventTime = t; |
| 233 | } |
| 234 | |
| 235 | public ITmfStateValue getNextValue() { |
| 236 | ITmfStateValue value = fPossibleValues.get(fNextValue); |
| 237 | fNextValue++; |
| 238 | if (fNextValue >= fPossibleValues.size()) { |
| 239 | fNextValue = 0; |
| 240 | } |
| 241 | return value; |
| 242 | } |
| 243 | |
| 244 | @Override |
| 245 | public int compareTo(QuarkEvent other) { |
| 246 | return Long.compare(fNextEventTime, other.getNextEventTime()); |
| 247 | } |
| 248 | } |
| 249 | |
| 250 | /** |
| 251 | * Benchmarks creating, single querying and full querying the state system |
| 252 | */ |
| 253 | @Test |
| 254 | public void testBenchmark() { |
| 255 | /* Check arguments */ |
| 256 | long totalTime = this.fNbAvgIntervals * INTERVAL_AVG_TIME; |
| 257 | |
| 258 | Performance perf = Performance.getDefault(); |
| 259 | PerformanceMeter pmBuild = perf.createPerformanceMeter(TEST_PREFIX + TEST_BUILDING_ID + fName); |
| 260 | perf.tagAsSummary(pmBuild, TEST_BUILDING_ID + fShortName, Dimension.CPU_TIME); |
| 261 | |
| 262 | PerformanceMeter pmSingleQuery = perf.createPerformanceMeter(TEST_PREFIX + TEST_SINGLE_QUERY_ID + fName); |
| 263 | perf.tagAsSummary(pmSingleQuery, TEST_SINGLE_QUERY_ID + fShortName, Dimension.CPU_TIME); |
| 264 | |
| 265 | PerformanceMeter pmFullQuery = perf.createPerformanceMeter(TEST_PREFIX + TEST_FULL_QUERY_ID + fName); |
| 266 | perf.tagAsSummary(pmFullQuery, TEST_FULL_QUERY_ID + fShortName, Dimension.CPU_TIME); |
| 267 | |
| 268 | PerformanceMeter pmRangeQuery = perf.createPerformanceMeter(TEST_PREFIX + TEST_QUERY_RANGE_ID + fName); |
| 269 | perf.tagAsSummary(pmRangeQuery, TEST_QUERY_RANGE_ID + fShortName, Dimension.CPU_TIME); |
| 270 | |
| 271 | for (int i = 0; i < fNbLoops; i++) { |
| 272 | try { |
| 273 | /* Create the state system */ |
| 274 | createFile(); |
| 275 | IStateHistoryBackend backend = StateHistoryBackendFactory.createHistoryTreeBackendNewFile(TEST_BUILDING_ID, NonNullUtils.checkNotNull(fTempFile), 1, 1, QUEUE_SIZE); |
| 276 | ITmfStateSystemBuilder ss = StateSystemFactory.newStateSystem(backend); |
| 277 | |
| 278 | /* Initialize the attributes */ |
| 279 | Queue<QuarkEvent> quarkEvents = new PriorityQueue<>(fNbAttrib); |
| 280 | Random randomGenerator = new Random(SEED); |
| 281 | int rootQuark = ss.getQuarkAbsoluteAndAdd(ROOT_NODE); |
| 282 | |
| 283 | /* Create all attributes before testing */ |
| 284 | for (int j = 0; j < fNbAttrib; j++) { |
| 285 | int quark = ss.getQuarkRelativeAndAdd(rootQuark, String.valueOf(j)); |
| 286 | quarkEvents.add(new QuarkEvent(quark, (Math.abs(randomGenerator.nextLong()) % INTERVAL_AVG_TIME) + 1, fValues.getValues())); |
| 287 | } |
| 288 | |
| 289 | /* Adds random intervals to the state system */ |
| 290 | pmBuild.start(); |
| 291 | while (true) { |
| 292 | QuarkEvent quarkEvent = quarkEvents.poll(); |
| 293 | if (quarkEvent == null) { |
| 294 | break; |
| 295 | } |
| 296 | long eventTime = quarkEvent.getNextEventTime(); |
| 297 | ss.modifyAttribute(eventTime, quarkEvent.getNextValue(), quarkEvent.getQuark()); |
| 298 | long nextDelta = fDistributionMethod.getNextEndTime(randomGenerator, INTERVAL_AVG_TIME); |
| 299 | long nextEndTime = eventTime + nextDelta; |
| 300 | if (nextEndTime <= totalTime) { |
| 301 | quarkEvent.setNextEventTime(nextEndTime); |
| 302 | quarkEvents.add(quarkEvent); |
| 303 | } |
| 304 | } |
| 305 | ss.closeHistory(totalTime); |
| 306 | pmBuild.stop(); |
| 307 | |
| 308 | /* |
| 309 | * Benchmark the single queries: for each random timestamp, |
| 310 | * query a random attribute |
| 311 | */ |
| 312 | List<Integer> subAttributes = ss.getSubAttributes(rootQuark, false); |
| 313 | pmSingleQuery.start(); |
| 314 | for (int j = 0; j < QUERY_COUNT; j++) { |
| 315 | long ts = getNextRandomValue(randomGenerator, totalTime); |
| 316 | int attrib = (int) getNextRandomValue(randomGenerator, subAttributes.size()); |
| 317 | ss.querySingleState(ts, attrib); |
| 318 | } |
| 319 | pmSingleQuery.stop(); |
| 320 | |
| 321 | /* Benchmark the history range query of 10 attributes */ |
| 322 | pmRangeQuery.start(); |
| 323 | for (int j = 0; j < 10; j++) { |
| 324 | int attrib = (int) getNextRandomValue(randomGenerator, subAttributes.size()); |
| 325 | StateSystemUtils.queryHistoryRange(ss, attrib, ss.getStartTime(), ss.getCurrentEndTime()); |
| 326 | } |
| 327 | pmRangeQuery.stop(); |
| 328 | |
| 329 | /* Benchmark the full queries */ |
| 330 | pmFullQuery.start(); |
| 331 | for (int j = 0; j < QUERY_COUNT; j++) { |
| 332 | long ts = getNextRandomValue(randomGenerator, totalTime); |
| 333 | ss.queryFullState(ts); |
| 334 | } |
| 335 | pmFullQuery.stop(); |
| 336 | |
| 337 | /* Output some data on the file */ |
| 338 | if (i == 0) { |
| 339 | if (backend instanceof HistoryTreeBackend) { |
| 340 | HistoryTreeBackend htBackend = (HistoryTreeBackend) backend; |
| 341 | System.out.println("History tree file size: " + FileUtils.byteCountToDisplaySize(htBackend.getFileSize())); |
| 342 | System.out.println("Average node usage: " + htBackend.getAverageNodeUsage()); |
| 343 | } |
| 344 | } |
| 345 | deleteFile(); |
| 346 | } catch (IOException | StateValueTypeException | AttributeNotFoundException | StateSystemDisposedException e) { |
| 347 | fail(e.getMessage()); |
| 348 | } finally { |
| 349 | deleteFile(); |
| 350 | } |
| 351 | } |
| 352 | pmBuild.commit(); |
| 353 | pmSingleQuery.commit(); |
| 354 | pmFullQuery.commit(); |
| 355 | pmRangeQuery.commit(); |
| 356 | } |
| 357 | |
| 358 | /** |
| 359 | * Get a next random value between 1 and a boundary. |
| 360 | */ |
| 361 | private static long getNextRandomValue(Random randomGenerator, long limit) { |
| 362 | long nextLong = Math.abs(randomGenerator.nextLong()); |
| 363 | long nextDelta = (nextLong % limit) + 1; |
| 364 | return nextDelta; |
| 365 | } |
| 366 | } |