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