From 6545af8ea8bc55649c1b07318d9e5c24e700f76a Mon Sep 17 00:00:00 2001 From: =?utf8?q?Genevi=C3=A8ve=20Bastien?= Date: Thu, 18 Feb 2016 22:38:36 -0500 Subject: [PATCH] ss: Add benchmarks for the threaded history tree MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit This adds a new benchmark for the threaded history tree backend. It benchmarks the insertion of intervals in the state system, single, full queries and history range queries. Change-Id: I4ac8eea4a6979c4f70b6d584b26ad3fc92ae4900 Signed-off-by: Geneviève Bastien Reviewed-on: https://git.eclipse.org/r/66891 Reviewed-by: Hudson CI Reviewed-by: Alexandre Montplaisir Tested-by: Alexandre Montplaisir --- .../alltests/perf/RunAllPerfTests.java | 2 + .../.classpath | 1 + .../META-INF/MANIFEST.MF | 5 +- .../build.properties | 3 +- .../HistoryTreeBackendBenchmark.java | 361 ++++++++++++++++++ 5 files changed, 370 insertions(+), 2 deletions(-) create mode 100644 statesystem/org.eclipse.tracecompass.statesystem.core.tests/perf/org/eclipse/tracecompass/statesystem/core/tests/perf/historytree/HistoryTreeBackendBenchmark.java diff --git a/releng/org.eclipse.tracecompass.alltests/src/org/eclipse/tracecompass/alltests/perf/RunAllPerfTests.java b/releng/org.eclipse.tracecompass.alltests/src/org/eclipse/tracecompass/alltests/perf/RunAllPerfTests.java index bd4561d736..629f3abd96 100644 --- a/releng/org.eclipse.tracecompass.alltests/src/org/eclipse/tracecompass/alltests/perf/RunAllPerfTests.java +++ b/releng/org.eclipse.tracecompass.alltests/src/org/eclipse/tracecompass/alltests/perf/RunAllPerfTests.java @@ -31,6 +31,8 @@ import org.junit.runners.Suite; org.eclipse.tracecompass.pcap.core.tests.perf.trace.PcapReadBenchmark.class, org.eclipse.tracecompass.pcap.core.tests.perf.trace.PcapSeekBenchmark.class, + org.eclipse.tracecompass.statesystem.core.tests.perf.historytree.HistoryTreeBackendBenchmark.class, + org.eclipse.tracecompass.tmf.core.tests.perf.synchronization.TimestampTransformBenchmark.class, org.eclipse.tracecompass.tmf.ctf.core.tests.perf.experiment.ExperimentBenchmark.class diff --git a/statesystem/org.eclipse.tracecompass.statesystem.core.tests/.classpath b/statesystem/org.eclipse.tracecompass.statesystem.core.tests/.classpath index ee8a85abcd..28bdb00faf 100644 --- a/statesystem/org.eclipse.tracecompass.statesystem.core.tests/.classpath +++ b/statesystem/org.eclipse.tracecompass.statesystem.core.tests/.classpath @@ -13,5 +13,6 @@ + diff --git a/statesystem/org.eclipse.tracecompass.statesystem.core.tests/META-INF/MANIFEST.MF b/statesystem/org.eclipse.tracecompass.statesystem.core.tests/META-INF/MANIFEST.MF index ebbd065add..29aee82e2f 100644 --- a/statesystem/org.eclipse.tracecompass.statesystem.core.tests/META-INF/MANIFEST.MF +++ b/statesystem/org.eclipse.tracecompass.statesystem.core.tests/META-INF/MANIFEST.MF @@ -10,9 +10,12 @@ Bundle-RequiredExecutionEnvironment: JavaSE-1.8 Require-Bundle: org.junit;bundle-version="4.0.0", org.eclipse.core.runtime, org.eclipse.core.resources, + org.eclipse.test.performance, org.eclipse.tracecompass.common.core, org.eclipse.tracecompass.statesystem.core Export-Package: org.eclipse.tracecompass.statesystem.core.tests, + org.eclipse.tracecompass.statesystem.core.tests.perf.historytree, org.eclipse.tracecompass.statesystem.core.tests.shared.utils Import-Package: com.google.common.base, - com.google.common.collect + com.google.common.collect, + org.apache.commons.io diff --git a/statesystem/org.eclipse.tracecompass.statesystem.core.tests/build.properties b/statesystem/org.eclipse.tracecompass.statesystem.core.tests/build.properties index a1ac2971c8..8575a8446a 100644 --- a/statesystem/org.eclipse.tracecompass.statesystem.core.tests/build.properties +++ b/statesystem/org.eclipse.tracecompass.statesystem.core.tests/build.properties @@ -12,7 +12,8 @@ source.. = src/,\ stubs/,\ - shared/ + shared/,\ + perf/ output.. = bin/ bin.includes = META-INF/,\ .,\ diff --git a/statesystem/org.eclipse.tracecompass.statesystem.core.tests/perf/org/eclipse/tracecompass/statesystem/core/tests/perf/historytree/HistoryTreeBackendBenchmark.java b/statesystem/org.eclipse.tracecompass.statesystem.core.tests/perf/org/eclipse/tracecompass/statesystem/core/tests/perf/historytree/HistoryTreeBackendBenchmark.java new file mode 100644 index 0000000000..dda43543bf --- /dev/null +++ b/statesystem/org.eclipse.tracecompass.statesystem.core.tests/perf/org/eclipse/tracecompass/statesystem/core/tests/perf/historytree/HistoryTreeBackendBenchmark.java @@ -0,0 +1,361 @@ +/******************************************************************************* + * Copyright (c) 2016 École Polytechnique de Montréal + * + * All rights reserved. This program and the accompanying materials are + * made available under the terms of the Eclipse Public License v1.0 which + * accompanies this distribution, and is available at + * http://www.eclipse.org/legal/epl-v10.html + *******************************************************************************/ + +package org.eclipse.tracecompass.statesystem.core.tests.perf.historytree; + +import static org.junit.Assert.fail; + +import java.io.File; +import java.io.IOException; +import java.util.Arrays; +import java.util.List; +import java.util.PriorityQueue; +import java.util.Queue; +import java.util.Random; + +import org.apache.commons.io.FileUtils; +import org.eclipse.jdt.annotation.NonNull; +import org.eclipse.test.performance.Dimension; +import org.eclipse.test.performance.Performance; +import org.eclipse.test.performance.PerformanceMeter; +import org.eclipse.tracecompass.common.core.NonNullUtils; +import org.eclipse.tracecompass.internal.statesystem.core.backend.historytree.HistoryTreeBackend; +import org.eclipse.tracecompass.statesystem.core.ITmfStateSystemBuilder; +import org.eclipse.tracecompass.statesystem.core.StateSystemFactory; +import org.eclipse.tracecompass.statesystem.core.StateSystemUtils; +import org.eclipse.tracecompass.statesystem.core.backend.IStateHistoryBackend; +import org.eclipse.tracecompass.statesystem.core.backend.StateHistoryBackendFactory; +import org.eclipse.tracecompass.statesystem.core.exceptions.AttributeNotFoundException; +import org.eclipse.tracecompass.statesystem.core.exceptions.StateSystemDisposedException; +import org.eclipse.tracecompass.statesystem.core.exceptions.StateValueTypeException; +import org.eclipse.tracecompass.statesystem.core.statevalue.ITmfStateValue; +import org.eclipse.tracecompass.statesystem.core.statevalue.TmfStateValue; +import org.junit.Test; +import org.junit.runner.RunWith; +import org.junit.runners.Parameterized; +import org.junit.runners.Parameterized.Parameters; + +import com.google.common.collect.ImmutableList; + +/** + * This class benchmarks writing intervals to the state system and querying them + * using a history tree backend + * + * @author Geneviève Bastien + */ +@RunWith(Parameterized.class) +public class HistoryTreeBackendBenchmark { + + private static final @NonNull String TEST_PREFIX = "org.eclipse.tracecompass#History Tree Backend#"; + private static final @NonNull String TEST_BUILDING_ID = "Build: "; + private static final @NonNull String TEST_SINGLE_QUERY_ID = "Single Queries: "; + private static final @NonNull String TEST_FULL_QUERY_ID = "Full Queries: "; + private static final @NonNull String TEST_QUERY_RANGE_ID = "Query History Range: "; + private static final @NonNull String ROOT_NODE = "root"; + private static final int QUEUE_SIZE = 10000; + private static final long SEED = 5575784704147L; + private static final int QUERY_COUNT = 100; + private static final int INTERVAL_AVG_TIME = 1000; + + /* Values for the average case */ + private static final int DEFAULT_NB_ATTRIB = 1500; + private static final int DEFAULT_NB_INTERVALS = 500; + private static final int DEFAULT_LOOP_COUNT = 40; + + private File fTempFile; + private final String fName; + private final int fNbAttrib; + private final int fNbAvgIntervals; + private final int fNbLoops; + private final HTBValues fValues; + private final IIntervalDistribution fDistributionMethod; + + /** + * Constructor + * + * @param name + * The name of the test + * @param nbAttrib + * The number of attributes + * @param nbAvgIntervals + * An idea on the number of intervals per attributes. The exact + * number will depend on the interval time distribution + * @param nbLoops + * The number of times to execute the benchmark + * @param values + * The values to put in the history tree + * @param distributionMethod + * A distribution method that will return the next interval + * duration according to an algorithm + */ + public HistoryTreeBackendBenchmark(String name, int nbAttrib, int nbAvgIntervals, int nbLoops, HTBValues values, IIntervalDistribution distributionMethod) { + fName = name; + fNbAttrib = nbAttrib; + fNbAvgIntervals = nbAvgIntervals; + fNbLoops = nbLoops; + fValues = values; + fDistributionMethod = distributionMethod; + } + + /* A list of values to use for the intervals */ + private enum HTBValues { + INTEGERS(ImmutableList.of(TmfStateValue.newValueInt(1), TmfStateValue.newValueInt(2), TmfStateValue.newValueInt(3))), + STRINGS(ImmutableList.of(TmfStateValue.newValueString("abc"), TmfStateValue.newValueString("def"), TmfStateValue.newValueString("wihi!"))), + LONGS(ImmutableList.of(TmfStateValue.newValueLong(Long.MAX_VALUE), TmfStateValue.newValueLong(1L), TmfStateValue.newValueLong(1234567L))), + DOUBLES(ImmutableList.of(TmfStateValue.newValueDouble(Double.MAX_VALUE), TmfStateValue.newValueDouble(1.0), TmfStateValue.newValueDouble(123.456))); + + private final List fValues; + + private HTBValues(List values) { + fValues = values; + } + + public List getValues() { + return fValues; + } + } + + @FunctionalInterface + private static interface IIntervalDistribution { + long getNextEndTime(Random randomGenerator, long limit); + } + + /* Generate interval duration uniformly distributed in the range [1, 2l] */ + private static IIntervalDistribution UNIFORM = (r, l) -> { + long nextLong = r.nextLong(); + long nextDelta = l + (nextLong % l); + return nextDelta; + }; + + /* + * Generates interval duration in the range [1, 2l] with 75% between [0.5l, + * 1.5l] + */ + private static IIntervalDistribution CLOSER_TO_LIMIT = (r, l) -> { + /* + * This method will return interval time closer to the specified limit + */ + double nextDouble = r.nextDouble(); + int sign = (nextDouble < 0) ? -1 : 1; + long nextDelta = l + (long) (Math.sqrt(nextDouble) * l * sign); + return nextDelta; + }; + + /* + * Generates interval duration in the range [1, 2l] with 75% between [0.5l, + * 1.5l], but with 10% outliers between [2l, 5l] + */ + private static IIntervalDistribution CLOSER_TO_LIMIT_10_PERCENT_OUTLIERS = (r, l) -> { + long nextLong = Math.abs(r.nextLong()); + /* Is this an outlier */ + if ((nextLong % 100) < 10) { + /* Create an outlier that can go up to 5 times the limit */ + return l + (((nextLong % 3) + 1) * l) + (nextLong % l); + } + /* Otherwise follow a distribution with more values around the limit */ + double nextDouble = r.nextDouble(); + int sign = (nextDouble < 0) ? -1 : 1; + long nextDelta = l + (long) (Math.sqrt(nextDouble) * l * sign); + return nextDelta; + }; + + /** + * @return The arrays of parameters + */ + @Parameters(name = "{index}: {0}") + public static Iterable getParameters() { + return Arrays.asList(new Object[][] { + { "Average case: 1500 attributes, integers, interval duration random around limit l with 75% within [0.5l, 1.5l]", DEFAULT_NB_ATTRIB, DEFAULT_NB_INTERVALS, DEFAULT_LOOP_COUNT, HTBValues.INTEGERS, CLOSER_TO_LIMIT }, + { "Vertical scaling (more attributes)", 3500, DEFAULT_NB_INTERVALS, 5, HTBValues.INTEGERS, CLOSER_TO_LIMIT }, + { "Horizontal scaling (more intervals/attribute)", DEFAULT_NB_ATTRIB, 20000, 10, HTBValues.INTEGERS, CLOSER_TO_LIMIT }, + { "Interval durations uniformly distributed within [1, 2l]", DEFAULT_NB_ATTRIB, DEFAULT_NB_INTERVALS, DEFAULT_LOOP_COUNT, HTBValues.INTEGERS, UNIFORM }, + { "Interval durations with 10% outliers > 2l", DEFAULT_NB_ATTRIB, DEFAULT_NB_INTERVALS, DEFAULT_LOOP_COUNT, HTBValues.INTEGERS, CLOSER_TO_LIMIT_10_PERCENT_OUTLIERS }, + { "Data type: strings", DEFAULT_NB_ATTRIB, DEFAULT_NB_INTERVALS, DEFAULT_LOOP_COUNT, HTBValues.STRINGS, CLOSER_TO_LIMIT }, + { "Data type: longs", DEFAULT_NB_ATTRIB, DEFAULT_NB_INTERVALS, DEFAULT_LOOP_COUNT, HTBValues.LONGS, CLOSER_TO_LIMIT }, + { "Data type: doubles", DEFAULT_NB_ATTRIB, DEFAULT_NB_INTERVALS, DEFAULT_LOOP_COUNT, HTBValues.DOUBLES, CLOSER_TO_LIMIT }, + }); + } + + /** + * Create the temporary file for this history tree + */ + private void createFile() { + try { + fTempFile = File.createTempFile("tmpStateSystem", null); + } catch (IOException e) { + fail(e.getMessage()); + } + } + + /** + * Delete the temporary history tree file after the test + */ + private void deleteFile() { + if (fTempFile != null) { + fTempFile.delete(); + fTempFile = null; + } + } + + private static class QuarkEvent implements Comparable { + private final int fQuark; + private long fNextEventTime; + private final List fPossibleValues; + private int fNextValue = 0; + + public QuarkEvent(int quark, long nextEventTime, List valuesList) { + fQuark = quark; + fNextEventTime = nextEventTime; + fPossibleValues = valuesList; + } + + public int getQuark() { + return fQuark; + } + + public long getNextEventTime() { + return fNextEventTime; + } + + public void setNextEventTime(long t) { + fNextEventTime = t; + } + + public ITmfStateValue getNextValue() { + ITmfStateValue value = fPossibleValues.get(fNextValue); + fNextValue++; + if (fNextValue >= fPossibleValues.size()) { + fNextValue = 0; + } + return value; + } + + @Override + public int compareTo(QuarkEvent other) { + return Long.compare(fNextEventTime, other.getNextEventTime()); + } + } + + /** + * Benchmarks creating, single querying and full querying the state system + */ + @Test + public void testBenchmark() { + /* Check arguments */ + long totalTime = this.fNbAvgIntervals * INTERVAL_AVG_TIME; + + Performance perf = Performance.getDefault(); + PerformanceMeter pmBuild = perf.createPerformanceMeter(TEST_PREFIX + TEST_BUILDING_ID + fName); + perf.tagAsSummary(pmBuild, TEST_BUILDING_ID + fName, Dimension.CPU_TIME); + + PerformanceMeter pmSingleQuery = perf.createPerformanceMeter(TEST_PREFIX + TEST_SINGLE_QUERY_ID + fName); + perf.tagAsSummary(pmSingleQuery, TEST_SINGLE_QUERY_ID + fName, Dimension.CPU_TIME); + + PerformanceMeter pmFullQuery = perf.createPerformanceMeter(TEST_PREFIX + TEST_FULL_QUERY_ID + fName); + perf.tagAsSummary(pmFullQuery, TEST_FULL_QUERY_ID + fName, Dimension.CPU_TIME); + + PerformanceMeter pmRangeQuery = perf.createPerformanceMeter(TEST_PREFIX + TEST_QUERY_RANGE_ID + fName); + perf.tagAsSummary(pmRangeQuery, TEST_QUERY_RANGE_ID + fName, Dimension.CPU_TIME); + + for (int i = 0; i < fNbLoops; i++) { + try { + /* Create the state system */ + createFile(); + IStateHistoryBackend backend = StateHistoryBackendFactory.createHistoryTreeBackendNewFile(TEST_BUILDING_ID, NonNullUtils.checkNotNull(fTempFile), 1, 1, QUEUE_SIZE); + ITmfStateSystemBuilder ss = StateSystemFactory.newStateSystem(backend); + + /* Initialize the attributes */ + Queue quarkEvents = new PriorityQueue<>(fNbAttrib); + Random randomGenerator = new Random(SEED); + int rootQuark = ss.getQuarkAbsoluteAndAdd(ROOT_NODE); + + /* Create all attributes before testing */ + for (int j = 0; j < fNbAttrib; j++) { + int quark = ss.getQuarkRelativeAndAdd(rootQuark, String.valueOf(j)); + quarkEvents.add(new QuarkEvent(quark, (Math.abs(randomGenerator.nextLong()) % INTERVAL_AVG_TIME) + 1, fValues.getValues())); + } + + /* Adds random intervals to the state system */ + pmBuild.start(); + while (true) { + QuarkEvent quarkEvent = quarkEvents.poll(); + if (quarkEvent == null) { + break; + } + long eventTime = quarkEvent.getNextEventTime(); + ss.modifyAttribute(eventTime, quarkEvent.getNextValue(), quarkEvent.getQuark()); + long nextDelta = fDistributionMethod.getNextEndTime(randomGenerator, INTERVAL_AVG_TIME); + long nextEndTime = eventTime + nextDelta; + if (nextEndTime <= totalTime) { + quarkEvent.setNextEventTime(nextEndTime); + quarkEvents.add(quarkEvent); + } + } + ss.closeHistory(totalTime); + pmBuild.stop(); + + /* + * Benchmark the single queries: for each random timestamp, + * query a random attribute + */ + List subAttributes = ss.getSubAttributes(rootQuark, false); + pmSingleQuery.start(); + for (int j = 0; j < QUERY_COUNT; j++) { + long ts = getNextRandomValue(randomGenerator, totalTime); + int attrib = (int) getNextRandomValue(randomGenerator, subAttributes.size()); + ss.querySingleState(ts, attrib); + } + pmSingleQuery.stop(); + + /* Benchmark the history range query of 10 attributes */ + pmRangeQuery.start(); + for (int j = 0; j < 10; j++) { + int attrib = (int) getNextRandomValue(randomGenerator, subAttributes.size()); + StateSystemUtils.queryHistoryRange(ss, attrib, ss.getStartTime(), ss.getCurrentEndTime()); + } + pmRangeQuery.stop(); + + /* Benchmark the full queries */ + pmFullQuery.start(); + for (int j = 0; j < QUERY_COUNT; j++) { + long ts = getNextRandomValue(randomGenerator, totalTime); + ss.queryFullState(ts); + } + pmFullQuery.stop(); + + /* Output some data on the file */ + if (i == 0) { + if (backend instanceof HistoryTreeBackend) { + HistoryTreeBackend htBackend = (HistoryTreeBackend) backend; + System.out.println("History tree file size: " + FileUtils.byteCountToDisplaySize(htBackend.getFileSize())); + System.out.println("Average node usage: " + htBackend.getAverageNodeUsage()); + } + } + deleteFile(); + } catch (IOException | StateValueTypeException | AttributeNotFoundException | StateSystemDisposedException e) { + fail(e.getMessage()); + } finally { + deleteFile(); + } + } + pmBuild.commit(); + pmSingleQuery.commit(); + pmFullQuery.commit(); + pmRangeQuery.commit(); + } + + /** + * Get a next random value between 1 and a boundary. + */ + private static long getNextRandomValue(Random randomGenerator, long limit) { + long nextLong = Math.abs(randomGenerator.nextLong()); + long nextDelta = (nextLong % limit) + 1; + return nextDelta; + } +} -- 2.34.1