| 1 | /******************************************************************************* |
| 2 | * Copyright (c) 2016 Ericsson |
| 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.analysis.timing.core.tests.segmentstore.statistics; |
| 11 | |
| 12 | import static org.junit.Assert.assertEquals; |
| 13 | |
| 14 | import java.util.ArrayList; |
| 15 | import java.util.List; |
| 16 | import java.util.Random; |
| 17 | |
| 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; |
| 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; |
| 42 | private static final double APPROX_ERROR = 0.0001; |
| 43 | |
| 44 | private static void testOnlineVsOffline(List<@NonNull ISegment> fixture) { |
| 45 | validate(new OfflineStatisticsCalculator(fixture), getSegStoreStat(fixture)); |
| 46 | } |
| 47 | |
| 48 | /** |
| 49 | * Test incrementing |
| 50 | */ |
| 51 | @Test |
| 52 | public void climbTest() { |
| 53 | List<@NonNull ISegment> fixture = new ArrayList<>(); |
| 54 | for (int i = 0; i < MEDIUM_AMOUNT_OF_SEGMENTS; i++) { |
| 55 | fixture.add(createDummySegment(i, i * 2)); |
| 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); |
| 62 | assertEquals("Min Segment", 0, sss.getMinSegment().getLength()); |
| 63 | assertEquals("Max Segment", 99, sss.getMaxSegment().getLength()); |
| 64 | testOnlineVsOffline(fixture); |
| 65 | } |
| 66 | |
| 67 | private static SegmentStoreStatistics getSegStoreStat(List<@NonNull ISegment> fixture) { |
| 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() { |
| 80 | List<@NonNull ISegment> fixture = new ArrayList<>(); |
| 81 | for (int i = MEDIUM_AMOUNT_OF_SEGMENTS; i >= 0; i--) { |
| 82 | fixture.add(createDummySegment(i, i * 2)); |
| 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); |
| 89 | assertEquals("Min Segment", 0, sss.getMinSegment().getLength()); |
| 90 | assertEquals("Max Segment", 100, sss.getMaxSegment().getLength()); |
| 91 | testOnlineVsOffline(fixture); |
| 92 | } |
| 93 | |
| 94 | /** |
| 95 | * Test small |
| 96 | */ |
| 97 | @Test |
| 98 | public void smallTest() { |
| 99 | List<@NonNull ISegment> fixture = new ArrayList<>(); |
| 100 | for (int i = 1; i >= 0; i--) { |
| 101 | fixture.add(createDummySegment(i, i * 2)); |
| 102 | } |
| 103 | testOnlineVsOffline(fixture); |
| 104 | } |
| 105 | |
| 106 | /** |
| 107 | * Test large |
| 108 | */ |
| 109 | @Test |
| 110 | public void largeTest() { |
| 111 | List<@NonNull ISegment> fixture = new ArrayList<>(); |
| 112 | for (int i = 1; i <= LARGE_AMOUNT_OF_SEGMENTS; i++) { |
| 113 | fixture.add(createDummySegment(i, i * 2)); |
| 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); |
| 125 | List<@NonNull ISegment> fixture = new ArrayList<>(); |
| 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)); |
| 129 | fixture.add(createDummySegment(start, end)); |
| 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); |
| 141 | List<@NonNull ISegment> fixture = new ArrayList<>(); |
| 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; |
| 146 | fixture.add(createDummySegment(start, end)); |
| 147 | } |
| 148 | testOnlineVsOffline(fixture); |
| 149 | } |
| 150 | |
| 151 | /** |
| 152 | * Test statistics nodes being merged. Two contiguous blocks. |
| 153 | */ |
| 154 | @Test |
| 155 | public void mergeStatisticsNodesTest() { |
| 156 | // calculates stats for all the segments |
| 157 | SegmentStoreStatistics expected = new SegmentStoreStatistics(); |
| 158 | // calculates stats for half of the segments |
| 159 | SegmentStoreStatistics a = new SegmentStoreStatistics(); |
| 160 | // calculates stats for another half of the segments |
| 161 | SegmentStoreStatistics b = new SegmentStoreStatistics(); |
| 162 | List<@NonNull ISegment> fixture = new ArrayList<>(); |
| 163 | for (int i = 0; i < 10; i++) { |
| 164 | ISegment seg = new BasicSegment(i, i * 2 + 2); |
| 165 | expected.update(seg); |
| 166 | a.update(seg); |
| 167 | fixture.add(seg); |
| 168 | } |
| 169 | for (int i = 0; i < 10; i++) { |
| 170 | ISegment seg = new BasicSegment(i, i * 2 + 2); |
| 171 | expected.update(seg); |
| 172 | b.update(seg); |
| 173 | fixture.add(seg); |
| 174 | } |
| 175 | a.merge(b); |
| 176 | OfflineStatisticsCalculator offlineExpected = new OfflineStatisticsCalculator(fixture); |
| 177 | // Compare the expected stats with the offline algorithm |
| 178 | validate(offlineExpected, expected); |
| 179 | // Compare the results of the merge with the expected results |
| 180 | validate(expected, a); |
| 181 | } |
| 182 | |
| 183 | /** |
| 184 | * Test statistics nodes being merged. Two random blocks. |
| 185 | */ |
| 186 | @Test |
| 187 | public void mergeStatisticsRandomNodesTest() { |
| 188 | // calculates stats for all the segments |
| 189 | SegmentStoreStatistics expected = new SegmentStoreStatistics(); |
| 190 | // calculates stats for half of the segments, randomly |
| 191 | SegmentStoreStatistics a = new SegmentStoreStatistics(); |
| 192 | // calculates stats for the other half of the segments |
| 193 | SegmentStoreStatistics b = new SegmentStoreStatistics(); |
| 194 | List<@NonNull ISegment> fixture = new ArrayList<>(); |
| 195 | Random rnd = new Random(); |
| 196 | rnd.setSeed(10); |
| 197 | int size = rnd.nextInt(1000); |
| 198 | int size2 = rnd.nextInt(1000); |
| 199 | for (int i = 0; i < size; i++) { |
| 200 | int start = Math.abs(rnd.nextInt(100000000)); |
| 201 | final int delta = Math.abs(rnd.nextInt(1000)); |
| 202 | int end = start + delta * delta; |
| 203 | ISegment seg = new BasicSegment(start, end); |
| 204 | expected.update(seg); |
| 205 | a.update(seg); |
| 206 | fixture.add(seg); |
| 207 | } |
| 208 | for (int i = 0; i < size2; i++) { |
| 209 | int start = Math.abs(rnd.nextInt(100000000)); |
| 210 | final int delta = Math.abs(rnd.nextInt(1000)); |
| 211 | int end = start + delta * delta; |
| 212 | ISegment seg = new BasicSegment(start, end); |
| 213 | expected.update(seg); |
| 214 | b.update(seg); |
| 215 | fixture.add(seg); |
| 216 | } |
| 217 | a.merge(b); |
| 218 | assertEquals(size + size2, a.getNbSegments()); |
| 219 | OfflineStatisticsCalculator offlineExpected = new OfflineStatisticsCalculator(fixture); |
| 220 | // Compare the expected stats with the offline algorithm |
| 221 | validate(offlineExpected, expected); |
| 222 | // Compare the results of the merge with the expected results |
| 223 | validate(expected, a); |
| 224 | } |
| 225 | |
| 226 | /** |
| 227 | * Test statistics nodes being merged. Two overlapping blocks. |
| 228 | */ |
| 229 | @Test |
| 230 | public void mergeStatisticsOverlappingNodesTest() { |
| 231 | // calculates stats for all the segments |
| 232 | SegmentStoreStatistics expected = new SegmentStoreStatistics(); |
| 233 | // calculates stats for half of the segments |
| 234 | SegmentStoreStatistics a = new SegmentStoreStatistics(); |
| 235 | // calculates stats for the other half of the segments |
| 236 | SegmentStoreStatistics b = new SegmentStoreStatistics(); |
| 237 | List<@NonNull ISegment> fixture = new ArrayList<>(); |
| 238 | for (int i = 0; i < 100; i++) { |
| 239 | BasicSegment seg = new BasicSegment(i, i * 2 + 2); |
| 240 | expected.update(seg); |
| 241 | if ((i & 2) != 0) { |
| 242 | a.update(seg); |
| 243 | } else { |
| 244 | b.update(seg); |
| 245 | } |
| 246 | fixture.add(seg); |
| 247 | } |
| 248 | a.merge(b); |
| 249 | OfflineStatisticsCalculator offlineExpected = new OfflineStatisticsCalculator(fixture); |
| 250 | validate(offlineExpected, expected); |
| 251 | validate(expected, a); |
| 252 | } |
| 253 | |
| 254 | private static @NonNull SegmentStoreStatistics fillSmallStatistics() { |
| 255 | SegmentStoreStatistics stats = new SegmentStoreStatistics(); |
| 256 | for (int i = 0; i < 10; i++) { |
| 257 | BasicSegment seg = new BasicSegment(i, i * 2 + 2); |
| 258 | stats.update(seg); |
| 259 | } |
| 260 | return stats; |
| 261 | } |
| 262 | |
| 263 | /** |
| 264 | * Test statistics nodes being merged. corner cases. |
| 265 | */ |
| 266 | @Test |
| 267 | public void mergeStatisticsCorenerCaseNodesTest() { |
| 268 | ISegment segment = new BasicSegment(1, 5); |
| 269 | |
| 270 | // Control statistics, not to be modified |
| 271 | SegmentStoreStatistics noSegments = new SegmentStoreStatistics(); |
| 272 | SegmentStoreStatistics oneSegment = new SegmentStoreStatistics(); |
| 273 | oneSegment.update(segment); |
| 274 | |
| 275 | // The segment store statistics to test |
| 276 | SegmentStoreStatistics testStats = new SegmentStoreStatistics(); |
| 277 | SegmentStoreStatistics testStats2 = new SegmentStoreStatistics(); |
| 278 | |
| 279 | // Test merging empty stats on a non-empty one |
| 280 | testStats.update(segment); |
| 281 | testStats.merge(testStats2); |
| 282 | validate(oneSegment, testStats); |
| 283 | validate(noSegments, testStats2); |
| 284 | |
| 285 | // Test merging on an empty stats |
| 286 | testStats2.merge(testStats); |
| 287 | validate(oneSegment, testStats); |
| 288 | validate(oneSegment, testStats2); |
| 289 | |
| 290 | // Fill a small segment store and add the one extra segment to it |
| 291 | SegmentStoreStatistics expected = fillSmallStatistics(); |
| 292 | expected.update(segment); |
| 293 | |
| 294 | // Test merging stats with only 1 segment |
| 295 | testStats = fillSmallStatistics(); |
| 296 | testStats.merge(testStats2); |
| 297 | validate(oneSegment, testStats2); |
| 298 | validate(expected, testStats); |
| 299 | |
| 300 | // Test merging on stats with only 1 segment |
| 301 | testStats = fillSmallStatistics(); |
| 302 | testStats2.merge(testStats); |
| 303 | validate(fillSmallStatistics(), testStats); |
| 304 | validate(expected, testStats2); |
| 305 | |
| 306 | } |
| 307 | |
| 308 | private static void validate(SegmentStoreStatistics expected, SegmentStoreStatistics toBeTested) { |
| 309 | assertEquals("# of Segments", expected.getNbSegments(), toBeTested.getNbSegments()); |
| 310 | assertEquals("Total duration", expected.getTotal(), toBeTested.getTotal(), ERROR * expected.getTotal()); |
| 311 | assertEquals("Average", expected.getAverage(), toBeTested.getAverage(), ERROR * expected.getAverage()); |
| 312 | assertEquals("Min", expected.getMin(), toBeTested.getMin()); |
| 313 | assertEquals("Max", expected.getMax(), toBeTested.getMax()); |
| 314 | assertEquals("Min Segment", expected.getMinSegment().getLength(), toBeTested.getMinSegment().getLength()); |
| 315 | assertEquals("Max Segment", expected.getMaxSegment().getLength(), toBeTested.getMaxSegment().getLength()); |
| 316 | assertEquals("Standard Deviation", expected.getStdDev(), toBeTested.getStdDev(), APPROX_ERROR * expected.getStdDev()); |
| 317 | } |
| 318 | |
| 319 | private static void validate(OfflineStatisticsCalculator osc, SegmentStoreStatistics sss) { |
| 320 | assertEquals("# of Segments", osc.count(), sss.getNbSegments()); |
| 321 | assertEquals("Total duration", osc.getTotal(), sss.getTotal(), ERROR * osc.getTotal()); |
| 322 | assertEquals("Average", osc.getAvg(), sss.getAverage(), ERROR * osc.getAvg()); |
| 323 | assertEquals("Min", osc.getMin(), sss.getMin()); |
| 324 | assertEquals("Max", osc.getMax(), sss.getMax()); |
| 325 | assertEquals("Min Segment", osc.getMin(), sss.getMinSegment().getLength()); |
| 326 | assertEquals("Max Segment", osc.getMax(), sss.getMaxSegment().getLength()); |
| 327 | assertEquals("Standard Deviation", osc.getStdDev(), sss.getStdDev(), ERROR * osc.getStdDev()); |
| 328 | } |
| 329 | |
| 330 | private static @NonNull BasicSegment createDummySegment(int start, int end) { |
| 331 | return new BasicSegment(start, end); |
| 332 | } |
| 333 | } |