1 /*******************************************************************************
2 * Copyright (c) 2016 Ericsson
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 *******************************************************************************/
10 package org
.eclipse
.tracecompass
.analysis
.timing
.core
.tests
.segmentstore
.statistics
;
12 import static org
.junit
.Assert
.assertEquals
;
14 import java
.util
.ArrayList
;
15 import java
.util
.List
;
16 import java
.util
.Random
;
18 import org
.eclipse
.jdt
.annotation
.NonNull
;
19 import org
.eclipse
.tracecompass
.analysis
.timing
.core
.segmentstore
.statistics
.SegmentStoreStatistics
;
20 import org
.eclipse
.tracecompass
.segmentstore
.core
.BasicSegment
;
21 import org
.eclipse
.tracecompass
.segmentstore
.core
.ISegment
;
22 import org
.junit
.Test
;
25 * Test the segment store statistics calculations. This is done with two tests.
27 * <li>test the values vs some sample points calculated by hand (sanity test)
29 * <li>2- test exhaustively vs a reference implementation.</li>
32 * @author Matthew Khouzam
34 public class SegmentStoreStatisticsTest
{
36 private static final int MEDIUM_AMOUNT_OF_SEGMENTS
= 100;
37 private static final int LARGE_AMOUNT_OF_SEGMENTS
= 1000000;
39 private static final double NO_ERROR
= 0.0;
40 private static final double ERROR
= 0.000001;
41 private static final double APPROX_ERROR
= 0.0001;
43 private static void testOnlineVsOffline(List
<@NonNull ISegment
> fixture
) {
44 validate(new OfflineStatisticsCalculator(fixture
), getSegStoreStat(fixture
));
51 public void climbTest() {
52 List
<@NonNull ISegment
> fixture
= new ArrayList
<>(MEDIUM_AMOUNT_OF_SEGMENTS
);
53 for (int i
= 0; i
< MEDIUM_AMOUNT_OF_SEGMENTS
; i
++) {
54 fixture
.add(createDummySegment(i
, i
* 2));
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);
61 assertEquals("Min Segment", 0, sss
.getMinSegment().getLength());
62 assertEquals("Max Segment", 99, sss
.getMaxSegment().getLength());
63 testOnlineVsOffline(fixture
);
66 private static SegmentStoreStatistics
getSegStoreStat(List
<@NonNull ISegment
> fixture
) {
67 SegmentStoreStatistics sss
= new SegmentStoreStatistics();
68 for (ISegment seg
: fixture
) {
75 * Test with segments of decrementing size
78 public void decrementingTest() {
79 List
<@NonNull ISegment
> fixture
= new ArrayList
<>(MEDIUM_AMOUNT_OF_SEGMENTS
);
80 for (int i
= MEDIUM_AMOUNT_OF_SEGMENTS
; i
>= 0; i
--) {
81 fixture
.add(createDummySegment(i
, i
* 2));
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);
88 assertEquals("Min Segment", 0, sss
.getMinSegment().getLength());
89 assertEquals("Max Segment", 100, sss
.getMaxSegment().getLength());
90 testOnlineVsOffline(fixture
);
94 * Test a data set with a small number of segments
97 public void smallTest() {
98 List
<@NonNull ISegment
> fixture
= new ArrayList
<>();
99 for (int i
= 1; i
>= 0; i
--) {
100 fixture
.add(createDummySegment(i
, i
* 2));
102 testOnlineVsOffline(fixture
);
106 * Test a data set with a large number of segments
109 public void largeTest() {
110 List
<@NonNull ISegment
> fixture
= new ArrayList
<>(LARGE_AMOUNT_OF_SEGMENTS
);
111 for (int i
= 1; i
<= LARGE_AMOUNT_OF_SEGMENTS
; i
++) {
112 fixture
.add(createDummySegment(i
, i
* 2));
114 testOnlineVsOffline(fixture
);
118 * Test a random dataset where the distribution follows white noise
121 public void noiseTest() {
122 Random rnd
= new Random();
124 List
<@NonNull ISegment
> fixture
= new ArrayList
<>(LARGE_AMOUNT_OF_SEGMENTS
);
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));
128 fixture
.add(createDummySegment(start
, end
));
130 testOnlineVsOffline(fixture
);
134 * Test a random dataset where the distribution follows gaussian noise
137 public void gaussianNoiseTest() {
138 Random rnd
= new Random();
140 List
<@NonNull ISegment
> fixture
= new ArrayList
<>(LARGE_AMOUNT_OF_SEGMENTS
);
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
;
145 fixture
.add(createDummySegment(start
, end
));
147 testOnlineVsOffline(fixture
);
151 * Test building a statistics store with streams
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));
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
);
167 * Test building a statistics store with parallel streams
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));
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
);
183 * Test statistics nodes being merged. Two contiguous blocks.
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
);
200 for (int i
= 0; i
< 10; i
++) {
201 ISegment seg
= new BasicSegment(i
, i
* 2 + 2);
202 expected
.update(seg
);
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
);
215 * Test statistics nodes being merged. Two random blocks.
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();
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
);
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
);
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
);
258 * Test statistics nodes being merged. Two overlapping blocks.
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
);
280 OfflineStatisticsCalculator offlineExpected
= new OfflineStatisticsCalculator(fixture
);
281 validate(offlineExpected
, expected
);
282 validate(expected
, a
);
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);
295 * Test corner cases when merging statistics nodes
298 public void mergeStatisticsCornerCaseNodesTest() {
299 ISegment segment
= new BasicSegment(1, 5);
301 // Control statistics, not to be modified
302 SegmentStoreStatistics noSegments
= new SegmentStoreStatistics();
303 SegmentStoreStatistics oneSegment
= new SegmentStoreStatistics();
304 oneSegment
.update(segment
);
306 // The segment store statistics to test
307 SegmentStoreStatistics testStats
= new SegmentStoreStatistics();
308 SegmentStoreStatistics testStats2
= new SegmentStoreStatistics();
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
);
316 // Test merging on an empty stats
317 testStats2
.merge(testStats
);
318 validate(oneSegment
, testStats
);
319 validate(oneSegment
, testStats2
);
321 // Fill a small segment store and add the one extra segment to it
322 SegmentStoreStatistics expected
= fillSmallStatistics();
323 expected
.update(segment
);
325 // Test merging stats with only 1 segment
326 testStats
= fillSmallStatistics();
327 testStats
.merge(testStats2
);
328 validate(oneSegment
, testStats2
);
329 validate(expected
, testStats
);
331 // Test merging on stats with only 1 segment
332 testStats
= fillSmallStatistics();
333 testStats2
.merge(testStats
);
334 validate(fillSmallStatistics(), testStats
);
335 validate(expected
, testStats2
);
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());
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());
361 private static @NonNull BasicSegment
createDummySegment(int start
, int end
) {
362 return new BasicSegment(start
, end
);