analysis/org.eclipse.tracecompass.analysis.timing.core.tests/src/org/eclipse/tracecompass/analysis/timing/core/tests/segmentstore/statistics/SegmentStoreStatisticsTest.java

   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<>(MEDIUM_AMOUNT_OF_SEGMENTS);
  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<>(MEDIUM_AMOUNT_OF_SEGMENTS);
  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<>(LARGE_AMOUNT_OF_SEGMENTS);
 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<>(LARGE_AMOUNT_OF_SEGMENTS);
 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<>(LARGE_AMOUNT_OF_SEGMENTS);
 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 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
 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
 362     private static @NonNull BasicSegment createDummySegment(int start, int end) {
 363         return new BasicSegment(start, end);
 364     }
 365 }