statesystem/org.eclipse.tracecompass.statesystem.core.tests/perf/org/eclipse/tracecompass/statesystem/core/tests/perf/historytree/HistoryTreeBackendBenchmark.java

   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 }