statesystem/org.eclipse.tracecompass.segmentstore.core.tests/perf/org/eclipse/tracecompass/analysis/timing/core/tests/store/SegmentStoreBenchmark.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.store;
  11
  12 import static org.junit.Assert.assertNotNull;
  13
  14 import java.text.DecimalFormat;
  15 import java.text.Format;
  16 import java.util.Arrays;
  17 import java.util.Comparator;
  18 import java.util.Random;
  19
  20 import org.eclipse.jdt.annotation.NonNull;
  21 import org.eclipse.tracecompass.internal.segmentstore.core.arraylist.ArrayListStore;
  22 import org.eclipse.tracecompass.internal.segmentstore.core.arraylist.LazyArrayListStore;
  23 import org.eclipse.tracecompass.internal.segmentstore.core.treemap.TreeMapStore;
  24 import org.eclipse.tracecompass.segmentstore.core.BasicSegment;
  25 import org.eclipse.tracecompass.segmentstore.core.ISegment;
  26 import org.eclipse.tracecompass.segmentstore.core.ISegmentStore;
  27 import org.eclipse.tracecompass.segmentstore.core.SegmentComparators;
  28 import org.junit.FixMethodOrder;
  29 import org.junit.Test;
  30 import org.junit.runner.RunWith;
  31 import org.junit.runners.MethodSorters;
  32 import org.junit.runners.Parameterized;
  33 import org.junit.runners.Parameterized.Parameters;
  34
  35 /**
  36  * Segmentstore benchmarks, tests the performance for loads and reads.
  37  *
  38  * NOTE : Do not add this to isTracecompassFastYet, it is not information that
  39  * is interesting for users, it is for developpers.
  40  *
  41  * @category benchmark
  42  *
  43  * @author Matthew Khouzam
  44  *
  45  */
  46 @FixMethodOrder(MethodSorters.NAME_ASCENDING)
  47 @RunWith(Parameterized.class)
  48 public class SegmentStoreBenchmark {
  49
  50     private final ISegmentStore<@NonNull ISegment> fSegStore;
  51     private final String fName;
  52     private static final Format FORMAT = new DecimalFormat("###,###.##"); //$NON-NLS-1$
  53
  54     /**
  55      * @return The arrays of parameters
  56      */
  57     @Parameters(name = "{index}: {0}")
  58     public static Iterable<Object[]> getParameters() {
  59         return Arrays.asList(new Object[][] {
  60                 { "Array list store", new ArrayListStore<>() },
  61                 { "Lazy array list store", new LazyArrayListStore<>() },
  62                 { "Treemap store", new TreeMapStore<>() },
  63         });
  64     }
  65
  66     /**
  67      * Constructor
  68      *
  69      * @param name
  70      *            The name of this test
  71      * @param segStore
  72      *            The segment store to fill for the benchmarks
  73      */
  74     public SegmentStoreBenchmark(String name, ISegmentStore<@NonNull ISegment> segStore) {
  75         fSegStore = segStore;
  76         fName = name;
  77     }
  78
  79     /**
  80      * Add elements in order
  81      */
  82     @Test
  83     public void test1AddInOrder() {
  84         int size = 1;
  85         int[] fuzz = { 0 };
  86         run(size, fuzz, new Object() {
  87         }.getClass().getEnclosingMethod().getName());
  88     }
  89
  90     /**
  91      * Add elements almost in order, this represents a typical degenerate use
  92      * case.
  93      */
  94     @Test
  95     public void test2AddFuzzyOrder() {
  96         int size = 1000;
  97         int[] fuzz = new int[size];
  98         Random rng = new Random(10);
  99         for (int i = 0; i < size; i++) {
 100             fuzz[i] = rng.nextInt(1000);
 101         }
 102         String name = new Object() {
 103         }.getClass().getEnclosingMethod().getName();
 104         assertNotNull(name);
 105         run(size, fuzz, name);
 106     }
 107
 108     /**
 109      * Add elements almost in order, this represents a typical degenerate use
 110      * case, then iterate over the list.
 111      */
 112     @Test
 113     public void test3AddFuzzyOrderThenIterate() {
 114         int size = 1000;
 115         int[] fuzz = new int[size];
 116         Random rng = new Random(10);
 117         for (int i = 0; i < size; i++) {
 118             fuzz[i] = rng.nextInt(1000);
 119         }
 120         String name = new Object() {
 121         }.getClass().getEnclosingMethod().getName();
 122         assertNotNull(name);
 123         runIterate(size, fuzz, name);
 124     }
 125
 126     /**
 127      * Add elements almost in order, this represents a typical degenerate use
 128      * case, and iterate while building then when done.
 129      */
 130     @Test
 131     public void test4AddFuzzyOrderThenIterateThenAddThenIterate() {
 132         int size = 1000;
 133         int[] fuzz = new int[size];
 134         Random rng = new Random(10);
 135         for (int i = 0; i < size; i++) {
 136             fuzz[i] = rng.nextInt(1000);
 137         }
 138         String name = new Object() {
 139         }.getClass().getEnclosingMethod().getName();
 140         assertNotNull(name);
 141         runIterateAddIterate(size, fuzz, name);
 142     }
 143
 144     /**
 145      * Test adding elements in a random order, this is an atypical degenerate
 146      * use case.
 147      */
 148     @Test
 149     public void test5AddRandomOrder() {
 150         int size = 1000;
 151         int[] fuzz = new int[size];
 152         Random rng = new Random(10);
 153         for (int i = 0; i < size; i++) {
 154             fuzz[i] = Math.abs(rng.nextInt());
 155         }
 156         String name = new Object() {
 157         }.getClass().getEnclosingMethod().getName();
 158         assertNotNull(name);
 159         runIterate(size, fuzz, name);
 160     }
 161
 162     /**
 163      * Test adding elements in a random order then iterate over the list, this
 164      * is an atypical degenerate use case.
 165      */
 166     @Test
 167     public void test6AddRandomOrderThenIterate() {
 168         int size = 1000;
 169         int[] fuzz = new int[size];
 170         Random rng = new Random(10);
 171         for (int i = 0; i < size; i++) {
 172             fuzz[i] = Math.abs(rng.nextInt());
 173         }
 174         String name = new Object() {
 175         }.getClass().getEnclosingMethod().getName();
 176         assertNotNull(name);
 177         runIterate(size, fuzz, name);
 178     }
 179
 180     /**
 181      * Test adding elements in a random order then iterate over the list then
 182      * add more then iterate again, this is an atypical degenerate use case.
 183      */
 184     @Test
 185     public void test7AddRandomOrderThenIterateThenAddThenIterate() {
 186         int size = 1000;
 187         int[] fuzz = new int[size];
 188         Random rng = new Random(10);
 189         for (int i = 0; i < size; i++) {
 190             fuzz[i] = rng.nextInt(1000);
 191         }
 192         String name = new Object() {
 193         }.getClass().getEnclosingMethod().getName();
 194         assertNotNull(name);
 195         runIterateAddIterate(size, fuzz, name);
 196     }
 197
 198     /**
 199      * Test adding elements in a random order then iterate over the list, this
 200      * is an atypical degenerate use case.
 201      */
 202     @Test
 203     public void test8AddFuzzyOrderThenIterateByStartTime() {
 204         int size = 1000;
 205         int[] fuzz = new int[size];
 206         Random rng = new Random(10);
 207         for (int i = 0; i < size; i++) {
 208             fuzz[i] = rng.nextInt(1000);
 209         }
 210         String name = new Object() {
 211         }.getClass().getEnclosingMethod().getName();
 212         assertNotNull(name);
 213         runIterateCompare(size, fuzz, name, SegmentComparators.INTERVAL_START_COMPARATOR);
 214     }
 215
 216     /**
 217      * Test adding elements in a random order then iterate over the list, this
 218      * is an atypical degenerate use case.
 219      */
 220     @Test
 221     public void test9AddFuzzyOrderThenIterateByEndTime() {
 222         int size = 1000;
 223         int[] fuzz = new int[size];
 224         Random rng = new Random(10);
 225         for (int i = 0; i < size; i++) {
 226             fuzz[i] = rng.nextInt(1000);
 227         }
 228         String name = new Object() {
 229         }.getClass().getEnclosingMethod().getName();
 230         assertNotNull(name);
 231         runIterateCompare(size, fuzz, name, SegmentComparators.INTERVAL_END_COMPARATOR);
 232     }
 233
 234     /**
 235      * Test adding elements in a random order then iterate over the list, this
 236      * is an atypical degenerate use case.
 237      */
 238     @Test
 239     public void testAAddFuzzyOrderThenIterateByDuration() {
 240         int size = 1000;
 241         int[] fuzz = new int[size];
 242         Random rng = new Random(10);
 243         for (int i = 0; i < size; i++) {
 244             fuzz[i] = rng.nextInt(1000);
 245         }
 246         String name = new Object() {
 247         }.getClass().getEnclosingMethod().getName();
 248         assertNotNull(name);
 249         runIterateCompare(size, fuzz, name, SegmentComparators.INTERVAL_LENGTH_COMPARATOR);
 250     }
 251
 252     private void runIterateCompare(int size, int[] fuzz, String method, @NonNull Comparator<@NonNull ISegment> comparator) {
 253         long start = System.nanoTime();
 254         populate(size, fuzz, fSegStore);
 255         long startTime = fuzz[0];
 256         long endTime = fSegStore.size() - 1 + fuzz[fSegStore.size() % size];
 257         iterateCompare(startTime, endTime, fSegStore, comparator);
 258         long end = System.nanoTime();
 259         long duration = end - start;
 260         outputResults(duration, method);
 261     }
 262
 263     private void run(int size, int[] fuzz, String method) {
 264         long duration = populate(size, fuzz, fSegStore);
 265         outputResults(duration, method);
 266     }
 267
 268     private static long populate(int size, int[] fuzz, ISegmentStore<@NonNull ISegment> store) {
 269         store.clear();
 270         long start = System.nanoTime();
 271         populate(size, fuzz, store, 1000000);
 272         long end = System.nanoTime();
 273         return end - start;
 274     }
 275
 276     private void runIterate(int size, int[] fuzz, String method) {
 277         long duration = addAndIterate(size, fuzz, fSegStore);
 278
 279         outputResults(duration, method);
 280     }
 281
 282     private static long addAndIterate(int size, int[] fuzz, ISegmentStore<@NonNull ISegment> store) {
 283         long start = System.nanoTime();
 284         populate(size, fuzz, store);
 285         iterate(store);
 286         long end = System.nanoTime();
 287         return end - start;
 288     }
 289
 290     private void runIterateAddIterate(int size, int[] fuzz, String method) {
 291         long duration = runIterateAddIterate(size, fuzz, fSegStore);
 292         outputResults(duration, method);
 293     }
 294
 295     private static long runIterateAddIterate(int size, int[] fuzz, ISegmentStore<@NonNull ISegment> store) {
 296         store.clear();
 297         long start = System.nanoTime();
 298         for (int i = 0; i < 50000; i++) {
 299             long startTime = i + fuzz[i % size];
 300             store.add(new BasicSegment(startTime, startTime + 10));
 301         }
 302         iterate(store);
 303         for (int i = 50000; i < 100000; i++) {
 304             long startTime = i + fuzz[i % size];
 305             store.add(new BasicSegment(startTime, startTime + 10));
 306         }
 307         iterate(store);
 308         long end = System.nanoTime();
 309         return end - start;
 310     }
 311
 312     private static Object iterate(ISegmentStore<@NonNull ISegment> store) {
 313         Object shutupCompilerWarnings = null;
 314         for (ISegment elem : store) {
 315             shutupCompilerWarnings = elem;
 316         }
 317         return shutupCompilerWarnings;
 318     }
 319
 320     private static Object iterateCompare(long startTime, long endTime, ISegmentStore<@NonNull ISegment> store, @NonNull Comparator<@NonNull ISegment> comparator) {
 321         Object shutupCompilerWarnings = null;
 322         for (ISegment elem : store.getIntersectingElements(startTime, endTime, comparator)) {
 323             shutupCompilerWarnings = elem;
 324         }
 325         return shutupCompilerWarnings;
 326     }
 327
 328     private static void populate(int size, int[] fuzz, ISegmentStore<@NonNull ISegment> store, int count) {
 329         for (int i = 0; i < count; i++) {
 330             long start = i + fuzz[i % size];
 331             store.add(new BasicSegment(start, start + 10));
 332         }
 333     }
 334
 335     private void outputResults(long duration, String method) {
 336         System.out.println(fName + ": Time taken for test " + method + ": " + FORMAT.format(duration));
 337     }
 338 }