Commit | Line | Data |
---|---|---|
6545af8e GB |
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; | |
41cd76a0 | 73 | private final String fShortName; |
6545af8e GB |
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 | |
41cd76a0 GB |
85 | * @param shortName |
86 | * A short name for this scenario (at most 40 characters, | |
87 | * otherwise it will be truncated in the DB) | |
6545af8e GB |
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 | */ | |
41cd76a0 | 101 | public HistoryTreeBackendBenchmark(String name, String shortName, int nbAttrib, int nbAvgIntervals, int nbLoops, HTBValues values, IIntervalDistribution distributionMethod) { |
6545af8e | 102 | fName = name; |
41cd76a0 | 103 | fShortName = shortName; |
6545af8e GB |
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[][] { | |
41cd76a0 GB |
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 }, | |
6545af8e GB |
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); | |
41cd76a0 | 260 | perf.tagAsSummary(pmBuild, TEST_BUILDING_ID + fShortName, Dimension.CPU_TIME); |
6545af8e GB |
261 | |
262 | PerformanceMeter pmSingleQuery = perf.createPerformanceMeter(TEST_PREFIX + TEST_SINGLE_QUERY_ID + fName); | |
41cd76a0 | 263 | perf.tagAsSummary(pmSingleQuery, TEST_SINGLE_QUERY_ID + fShortName, Dimension.CPU_TIME); |
6545af8e GB |
264 | |
265 | PerformanceMeter pmFullQuery = perf.createPerformanceMeter(TEST_PREFIX + TEST_FULL_QUERY_ID + fName); | |
41cd76a0 | 266 | perf.tagAsSummary(pmFullQuery, TEST_FULL_QUERY_ID + fShortName, Dimension.CPU_TIME); |
6545af8e GB |
267 | |
268 | PerformanceMeter pmRangeQuery = perf.createPerformanceMeter(TEST_PREFIX + TEST_QUERY_RANGE_ID + fName); | |
41cd76a0 | 269 | perf.tagAsSummary(pmRangeQuery, TEST_QUERY_RANGE_ID + fShortName, Dimension.CPU_TIME); |
6545af8e GB |
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 | } |