Commit | Line | Data |
---|---|---|
e06c9955 | 1 | /******************************************************************************* |
658401c8 | 2 | * Copyright (c) 2016 Ericsson |
e06c9955 MK |
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 | ||
658401c8 | 10 | package org.eclipse.tracecompass.analysis.timing.core.tests.segmentstore.statistics; |
e06c9955 MK |
11 | |
12 | import static org.junit.Assert.assertEquals; | |
13 | ||
14 | import java.util.ArrayList; | |
e06c9955 MK |
15 | import java.util.List; |
16 | import java.util.Random; | |
17 | ||
18 | import org.eclipse.jdt.annotation.NonNull; | |
5b901f94 | 19 | import org.eclipse.tracecompass.analysis.timing.core.segmentstore.statistics.SegmentStoreStatistics; |
660d4ed9 | 20 | import org.eclipse.tracecompass.segmentstore.core.BasicSegment; |
e06c9955 MK |
21 | import org.eclipse.tracecompass.segmentstore.core.ISegment; |
22 | import org.junit.Test; | |
23 | ||
24 | /** | |
ea66bbfe | 25 | * Test the segment store statistics calculations. This is done with two tests. |
e06c9955 MK |
26 | * <ol> |
27 | * <li>test the values vs some sample points calculated by hand (sanity test) | |
28 | * </li> | |
29 | * <li>2- test exhaustively vs a reference implementation.</li> | |
30 | * </ol> | |
31 | * | |
32 | * @author Matthew Khouzam | |
e06c9955 MK |
33 | */ |
34 | public class SegmentStoreStatisticsTest { | |
35 | ||
36 | private static final int MEDIUM_AMOUNT_OF_SEGMENTS = 100; | |
37 | private static final int LARGE_AMOUNT_OF_SEGMENTS = 1000000; | |
38 | ||
39 | private static final double NO_ERROR = 0.0; | |
40 | private static final double ERROR = 0.000001; | |
381e1541 | 41 | private static final double APPROX_ERROR = 0.0001; |
e06c9955 | 42 | |
381e1541 MK |
43 | private static void testOnlineVsOffline(List<@NonNull ISegment> fixture) { |
44 | validate(new OfflineStatisticsCalculator(fixture), getSegStoreStat(fixture)); | |
e06c9955 MK |
45 | } |
46 | ||
47 | /** | |
48 | * Test incrementing | |
49 | */ | |
50 | @Test | |
51 | public void climbTest() { | |
ae2cf482 | 52 | List<@NonNull ISegment> fixture = new ArrayList<>(MEDIUM_AMOUNT_OF_SEGMENTS); |
e06c9955 | 53 | for (int i = 0; i < MEDIUM_AMOUNT_OF_SEGMENTS; i++) { |
660d4ed9 | 54 | fixture.add(createDummySegment(i, i * 2)); |
e06c9955 MK |
55 | } |
56 | SegmentStoreStatistics sss = getSegStoreStat(fixture); | |
57 | assertEquals("Average", 49.5, sss.getAverage(), ERROR); | |
58 | assertEquals("Min", 0, sss.getMin()); | |
59 | assertEquals("Max", 99, sss.getMax()); | |
60 | assertEquals("Standard Deviation", 29.0, sss.getStdDev(), 0.02); | |
a1e4b7e8 BH |
61 | assertEquals("Min Segment", 0, sss.getMinSegment().getLength()); |
62 | assertEquals("Max Segment", 99, sss.getMaxSegment().getLength()); | |
e06c9955 MK |
63 | testOnlineVsOffline(fixture); |
64 | } | |
65 | ||
381e1541 | 66 | private static SegmentStoreStatistics getSegStoreStat(List<@NonNull ISegment> fixture) { |
e06c9955 MK |
67 | SegmentStoreStatistics sss = new SegmentStoreStatistics(); |
68 | for (ISegment seg : fixture) { | |
69 | sss.update(seg); | |
70 | } | |
71 | return sss; | |
72 | } | |
73 | ||
74 | /** | |
ea66bbfe | 75 | * Test with segments of decrementing size |
e06c9955 MK |
76 | */ |
77 | @Test | |
78 | public void decrementingTest() { | |
ae2cf482 | 79 | List<@NonNull ISegment> fixture = new ArrayList<>(MEDIUM_AMOUNT_OF_SEGMENTS); |
e06c9955 | 80 | for (int i = MEDIUM_AMOUNT_OF_SEGMENTS; i >= 0; i--) { |
660d4ed9 | 81 | fixture.add(createDummySegment(i, i * 2)); |
e06c9955 MK |
82 | } |
83 | SegmentStoreStatistics sss = getSegStoreStat(fixture); | |
84 | assertEquals("Average", 50, sss.getAverage(), NO_ERROR); | |
85 | assertEquals("Min", 0, sss.getMin()); | |
86 | assertEquals("Max", 100, sss.getMax()); | |
87 | assertEquals("Standard Deviation", 29.3, sss.getStdDev(), 0.01); | |
a1e4b7e8 BH |
88 | assertEquals("Min Segment", 0, sss.getMinSegment().getLength()); |
89 | assertEquals("Max Segment", 100, sss.getMaxSegment().getLength()); | |
e06c9955 MK |
90 | testOnlineVsOffline(fixture); |
91 | } | |
92 | ||
93 | /** | |
ea66bbfe | 94 | * Test a data set with a small number of segments |
e06c9955 MK |
95 | */ |
96 | @Test | |
97 | public void smallTest() { | |
381e1541 | 98 | List<@NonNull ISegment> fixture = new ArrayList<>(); |
e06c9955 | 99 | for (int i = 1; i >= 0; i--) { |
660d4ed9 | 100 | fixture.add(createDummySegment(i, i * 2)); |
e06c9955 MK |
101 | } |
102 | testOnlineVsOffline(fixture); | |
103 | } | |
104 | ||
105 | /** | |
ea66bbfe | 106 | * Test a data set with a large number of segments |
e06c9955 MK |
107 | */ |
108 | @Test | |
109 | public void largeTest() { | |
ae2cf482 | 110 | List<@NonNull ISegment> fixture = new ArrayList<>(LARGE_AMOUNT_OF_SEGMENTS); |
e06c9955 | 111 | for (int i = 1; i <= LARGE_AMOUNT_OF_SEGMENTS; i++) { |
660d4ed9 | 112 | fixture.add(createDummySegment(i, i * 2)); |
e06c9955 MK |
113 | } |
114 | testOnlineVsOffline(fixture); | |
115 | } | |
116 | ||
117 | /** | |
ea66bbfe | 118 | * Test a random dataset where the distribution follows white noise |
e06c9955 MK |
119 | */ |
120 | @Test | |
121 | public void noiseTest() { | |
122 | Random rnd = new Random(); | |
123 | rnd.setSeed(1234); | |
ae2cf482 | 124 | List<@NonNull ISegment> fixture = new ArrayList<>(LARGE_AMOUNT_OF_SEGMENTS); |
e06c9955 MK |
125 | for (int i = 1; i <= LARGE_AMOUNT_OF_SEGMENTS; i++) { |
126 | int start = Math.abs(rnd.nextInt(100000000)); | |
127 | int end = start + Math.abs(rnd.nextInt(1000000)); | |
660d4ed9 | 128 | fixture.add(createDummySegment(start, end)); |
e06c9955 MK |
129 | } |
130 | testOnlineVsOffline(fixture); | |
131 | } | |
132 | ||
133 | /** | |
ea66bbfe | 134 | * Test a random dataset where the distribution follows gaussian noise |
e06c9955 MK |
135 | */ |
136 | @Test | |
137 | public void gaussianNoiseTest() { | |
138 | Random rnd = new Random(); | |
139 | rnd.setSeed(1234); | |
ae2cf482 | 140 | List<@NonNull ISegment> fixture = new ArrayList<>(LARGE_AMOUNT_OF_SEGMENTS); |
e06c9955 MK |
141 | for (int i = 1; i <= LARGE_AMOUNT_OF_SEGMENTS; i++) { |
142 | int start = Math.abs(rnd.nextInt(100000000)); | |
143 | final int delta = Math.abs(rnd.nextInt(1000)); | |
144 | int end = start + delta * delta; | |
660d4ed9 | 145 | fixture.add(createDummySegment(start, end)); |
e06c9955 MK |
146 | } |
147 | testOnlineVsOffline(fixture); | |
148 | } | |
149 | ||
ae2cf482 MK |
150 | /** |
151 | * Test building a statistics store with streams | |
152 | */ | |
153 | @Test | |
154 | public void streamBuildingTest() { | |
155 | SegmentStoreStatistics expected = new SegmentStoreStatistics(); | |
156 | List<@NonNull ISegment> fixture = new ArrayList<>(LARGE_AMOUNT_OF_SEGMENTS); | |
157 | for (long i = 0; i < LARGE_AMOUNT_OF_SEGMENTS; i++) { | |
158 | fixture.add(new BasicSegment(i, i + 2)); | |
159 | } | |
160 | fixture.forEach(e -> expected.update(e)); | |
161 | SegmentStoreStatistics actual = fixture.stream() | |
162 | .<@NonNull SegmentStoreStatistics> collect(SegmentStoreStatistics::new, SegmentStoreStatistics::update, SegmentStoreStatistics::merge); | |
163 | validate(expected, actual); | |
164 | } | |
165 | ||
166 | /** | |
167 | * Test building a statistics store with parallel streams | |
168 | */ | |
169 | @Test | |
170 | public void parallelStreamBuildingTest() { | |
171 | SegmentStoreStatistics expected = new SegmentStoreStatistics(); | |
172 | List<@NonNull ISegment> fixture = new ArrayList<>(LARGE_AMOUNT_OF_SEGMENTS); | |
173 | for (long i = 0; i < LARGE_AMOUNT_OF_SEGMENTS; i++) { | |
174 | fixture.add(new BasicSegment(i, i + 2)); | |
175 | } | |
176 | fixture.forEach(e -> expected.update(e)); | |
177 | SegmentStoreStatistics actual = fixture.parallelStream() | |
178 | .<@NonNull SegmentStoreStatistics> collect(SegmentStoreStatistics::new, SegmentStoreStatistics::update, SegmentStoreStatistics::merge); | |
179 | validate(expected, actual); | |
180 | } | |
181 | ||
381e1541 MK |
182 | /** |
183 | * Test statistics nodes being merged. Two contiguous blocks. | |
184 | */ | |
185 | @Test | |
186 | public void mergeStatisticsNodesTest() { | |
187 | // calculates stats for all the segments | |
188 | SegmentStoreStatistics expected = new SegmentStoreStatistics(); | |
189 | // calculates stats for half of the segments | |
190 | SegmentStoreStatistics a = new SegmentStoreStatistics(); | |
191 | // calculates stats for another half of the segments | |
192 | SegmentStoreStatistics b = new SegmentStoreStatistics(); | |
193 | List<@NonNull ISegment> fixture = new ArrayList<>(); | |
194 | for (int i = 0; i < 10; i++) { | |
195 | ISegment seg = new BasicSegment(i, i * 2 + 2); | |
196 | expected.update(seg); | |
197 | a.update(seg); | |
198 | fixture.add(seg); | |
199 | } | |
200 | for (int i = 0; i < 10; i++) { | |
201 | ISegment seg = new BasicSegment(i, i * 2 + 2); | |
202 | expected.update(seg); | |
203 | b.update(seg); | |
204 | fixture.add(seg); | |
205 | } | |
206 | a.merge(b); | |
207 | OfflineStatisticsCalculator offlineExpected = new OfflineStatisticsCalculator(fixture); | |
208 | // Compare the expected stats with the offline algorithm | |
209 | validate(offlineExpected, expected); | |
210 | // Compare the results of the merge with the expected results | |
211 | validate(expected, a); | |
212 | } | |
213 | ||
214 | /** | |
215 | * Test statistics nodes being merged. Two random blocks. | |
216 | */ | |
217 | @Test | |
218 | public void mergeStatisticsRandomNodesTest() { | |
219 | // calculates stats for all the segments | |
220 | SegmentStoreStatistics expected = new SegmentStoreStatistics(); | |
221 | // calculates stats for half of the segments, randomly | |
222 | SegmentStoreStatistics a = new SegmentStoreStatistics(); | |
223 | // calculates stats for the other half of the segments | |
224 | SegmentStoreStatistics b = new SegmentStoreStatistics(); | |
225 | List<@NonNull ISegment> fixture = new ArrayList<>(); | |
226 | Random rnd = new Random(); | |
227 | rnd.setSeed(10); | |
228 | int size = rnd.nextInt(1000); | |
229 | int size2 = rnd.nextInt(1000); | |
230 | for (int i = 0; i < size; i++) { | |
231 | int start = Math.abs(rnd.nextInt(100000000)); | |
232 | final int delta = Math.abs(rnd.nextInt(1000)); | |
233 | int end = start + delta * delta; | |
234 | ISegment seg = new BasicSegment(start, end); | |
235 | expected.update(seg); | |
236 | a.update(seg); | |
237 | fixture.add(seg); | |
238 | } | |
239 | for (int i = 0; i < size2; i++) { | |
240 | int start = Math.abs(rnd.nextInt(100000000)); | |
241 | final int delta = Math.abs(rnd.nextInt(1000)); | |
242 | int end = start + delta * delta; | |
243 | ISegment seg = new BasicSegment(start, end); | |
244 | expected.update(seg); | |
245 | b.update(seg); | |
246 | fixture.add(seg); | |
247 | } | |
248 | a.merge(b); | |
249 | assertEquals(size + size2, a.getNbSegments()); | |
250 | OfflineStatisticsCalculator offlineExpected = new OfflineStatisticsCalculator(fixture); | |
251 | // Compare the expected stats with the offline algorithm | |
252 | validate(offlineExpected, expected); | |
253 | // Compare the results of the merge with the expected results | |
254 | validate(expected, a); | |
255 | } | |
256 | ||
257 | /** | |
258 | * Test statistics nodes being merged. Two overlapping blocks. | |
259 | */ | |
260 | @Test | |
261 | public void mergeStatisticsOverlappingNodesTest() { | |
262 | // calculates stats for all the segments | |
263 | SegmentStoreStatistics expected = new SegmentStoreStatistics(); | |
264 | // calculates stats for half of the segments | |
265 | SegmentStoreStatistics a = new SegmentStoreStatistics(); | |
266 | // calculates stats for the other half of the segments | |
267 | SegmentStoreStatistics b = new SegmentStoreStatistics(); | |
268 | List<@NonNull ISegment> fixture = new ArrayList<>(); | |
269 | for (int i = 0; i < 100; i++) { | |
270 | BasicSegment seg = new BasicSegment(i, i * 2 + 2); | |
271 | expected.update(seg); | |
272 | if ((i & 2) != 0) { | |
273 | a.update(seg); | |
274 | } else { | |
275 | b.update(seg); | |
276 | } | |
277 | fixture.add(seg); | |
278 | } | |
279 | a.merge(b); | |
280 | OfflineStatisticsCalculator offlineExpected = new OfflineStatisticsCalculator(fixture); | |
281 | validate(offlineExpected, expected); | |
282 | validate(expected, a); | |
283 | } | |
284 | ||
285 | private static @NonNull SegmentStoreStatistics fillSmallStatistics() { | |
286 | SegmentStoreStatistics stats = new SegmentStoreStatistics(); | |
287 | for (int i = 0; i < 10; i++) { | |
288 | BasicSegment seg = new BasicSegment(i, i * 2 + 2); | |
289 | stats.update(seg); | |
290 | } | |
291 | return stats; | |
292 | } | |
293 | ||
294 | /** | |
ea66bbfe | 295 | * Test corner cases when merging statistics nodes |
381e1541 MK |
296 | */ |
297 | @Test | |
ea66bbfe | 298 | public void mergeStatisticsCornerCaseNodesTest() { |
381e1541 MK |
299 | ISegment segment = new BasicSegment(1, 5); |
300 | ||
301 | // Control statistics, not to be modified | |
302 | SegmentStoreStatistics noSegments = new SegmentStoreStatistics(); | |
303 | SegmentStoreStatistics oneSegment = new SegmentStoreStatistics(); | |
304 | oneSegment.update(segment); | |
305 | ||
306 | // The segment store statistics to test | |
307 | SegmentStoreStatistics testStats = new SegmentStoreStatistics(); | |
308 | SegmentStoreStatistics testStats2 = new SegmentStoreStatistics(); | |
309 | ||
310 | // Test merging empty stats on a non-empty one | |
311 | testStats.update(segment); | |
312 | testStats.merge(testStats2); | |
313 | validate(oneSegment, testStats); | |
314 | validate(noSegments, testStats2); | |
315 | ||
316 | // Test merging on an empty stats | |
317 | testStats2.merge(testStats); | |
318 | validate(oneSegment, testStats); | |
319 | validate(oneSegment, testStats2); | |
320 | ||
321 | // Fill a small segment store and add the one extra segment to it | |
322 | SegmentStoreStatistics expected = fillSmallStatistics(); | |
323 | expected.update(segment); | |
324 | ||
325 | // Test merging stats with only 1 segment | |
326 | testStats = fillSmallStatistics(); | |
327 | testStats.merge(testStats2); | |
328 | validate(oneSegment, testStats2); | |
329 | validate(expected, testStats); | |
330 | ||
331 | // Test merging on stats with only 1 segment | |
332 | testStats = fillSmallStatistics(); | |
333 | testStats2.merge(testStats); | |
334 | validate(fillSmallStatistics(), testStats); | |
335 | validate(expected, testStats2); | |
336 | ||
337 | } | |
338 | ||
339 | private static void validate(SegmentStoreStatistics expected, SegmentStoreStatistics toBeTested) { | |
340 | assertEquals("# of Segments", expected.getNbSegments(), toBeTested.getNbSegments()); | |
341 | assertEquals("Total duration", expected.getTotal(), toBeTested.getTotal(), ERROR * expected.getTotal()); | |
342 | assertEquals("Average", expected.getAverage(), toBeTested.getAverage(), ERROR * expected.getAverage()); | |
343 | assertEquals("Min", expected.getMin(), toBeTested.getMin()); | |
344 | assertEquals("Max", expected.getMax(), toBeTested.getMax()); | |
345 | assertEquals("Min Segment", expected.getMinSegment().getLength(), toBeTested.getMinSegment().getLength()); | |
346 | assertEquals("Max Segment", expected.getMaxSegment().getLength(), toBeTested.getMaxSegment().getLength()); | |
347 | assertEquals("Standard Deviation", expected.getStdDev(), toBeTested.getStdDev(), APPROX_ERROR * expected.getStdDev()); | |
348 | } | |
349 | ||
350 | private static void validate(OfflineStatisticsCalculator osc, SegmentStoreStatistics sss) { | |
351 | assertEquals("# of Segments", osc.count(), sss.getNbSegments()); | |
352 | assertEquals("Total duration", osc.getTotal(), sss.getTotal(), ERROR * osc.getTotal()); | |
353 | assertEquals("Average", osc.getAvg(), sss.getAverage(), ERROR * osc.getAvg()); | |
354 | assertEquals("Min", osc.getMin(), sss.getMin()); | |
355 | assertEquals("Max", osc.getMax(), sss.getMax()); | |
356 | assertEquals("Min Segment", osc.getMin(), sss.getMinSegment().getLength()); | |
357 | assertEquals("Max Segment", osc.getMax(), sss.getMaxSegment().getLength()); | |
358 | assertEquals("Standard Deviation", osc.getStdDev(), sss.getStdDev(), ERROR * osc.getStdDev()); | |
359 | } | |
360 | ||
660d4ed9 MK |
361 | private static @NonNull BasicSegment createDummySegment(int start, int end) { |
362 | return new BasicSegment(start, end); | |
e06c9955 MK |
363 | } |
364 | } |