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      * Get the number of segments to add to the segment store
  81      *
  82      * @return The number of segments to add to the segment store
  83      */
  84     protected long getSegmentStoreSize() {
  85         return 1000000;
  86     }
  87
  88     /**
  89      * Add elements in order
  90      */
  91     @Test
  92     public void test1AddInOrder() {
  93         int size = 1;
  94         int[] fuzz = { 0 };
  95         run(size, fuzz, new Object() {
  96         }.getClass().getEnclosingMethod().getName());
  97     }
  98
  99     /**
 100      * Add elements almost in order, this represents a typical degenerate use
 101      * case.
 102      */
 103     @Test
 104     public void test2AddFuzzyOrder() {
 105         int size = 1000;
 106         int[] fuzz = new int[size];
 107         Random rng = new Random(10);
 108         for (int i = 0; i < size; i++) {
 109             fuzz[i] = rng.nextInt(1000);
 110         }
 111         String name = new Object() {
 112         }.getClass().getEnclosingMethod().getName();
 113         assertNotNull(name);
 114         run(size, fuzz, name);
 115     }
 116
 117     /**
 118      * Add elements almost in order, this represents a typical degenerate use
 119      * case, then iterate over the list.
 120      */
 121     @Test
 122     public void test3AddFuzzyOrderThenIterate() {
 123         int size = 1000;
 124         int[] fuzz = new int[size];
 125         Random rng = new Random(10);
 126         for (int i = 0; i < size; i++) {
 127             fuzz[i] = rng.nextInt(1000);
 128         }
 129         String name = new Object() {
 130         }.getClass().getEnclosingMethod().getName();
 131         assertNotNull(name);
 132         runIterate(size, fuzz, name);
 133     }
 134
 135     /**
 136      * Add elements almost in order, this represents a typical degenerate use
 137      * case, and iterate while building then when done.
 138      */
 139     @Test
 140     public void test4AddFuzzyOrderThenIterateThenAddThenIterate() {
 141         int size = 1000;
 142         int[] fuzz = new int[size];
 143         Random rng = new Random(10);
 144         for (int i = 0; i < size; i++) {
 145             fuzz[i] = rng.nextInt(1000);
 146         }
 147         String name = new Object() {
 148         }.getClass().getEnclosingMethod().getName();
 149         assertNotNull(name);
 150         runIterateAddIterate(size, fuzz, name);
 151     }
 152
 153     /**
 154      * Test adding elements in a random order, this is an atypical degenerate
 155      * use case.
 156      */
 157     @Test
 158     public void test5AddRandomOrder() {
 159         int size = 1000;
 160         int[] fuzz = new int[size];
 161         Random rng = new Random(10);
 162         for (int i = 0; i < size; i++) {
 163             fuzz[i] = Math.abs(rng.nextInt());
 164         }
 165         String name = new Object() {
 166         }.getClass().getEnclosingMethod().getName();
 167         assertNotNull(name);
 168         runIterate(size, fuzz, name);
 169     }
 170
 171     /**
 172      * Test adding elements in a random order then iterate over the list, this
 173      * is an atypical degenerate use case.
 174      */
 175     @Test
 176     public void test6AddRandomOrderThenIterate() {
 177         int size = 1000;
 178         int[] fuzz = new int[size];
 179         Random rng = new Random(10);
 180         for (int i = 0; i < size; i++) {
 181             fuzz[i] = Math.abs(rng.nextInt());
 182         }
 183         String name = new Object() {
 184         }.getClass().getEnclosingMethod().getName();
 185         assertNotNull(name);
 186         runIterate(size, fuzz, name);
 187     }
 188
 189     /**
 190      * Test adding elements in a random order then iterate over the list then
 191      * add more then iterate again, this is an atypical degenerate use case.
 192      */
 193     @Test
 194     public void test7AddRandomOrderThenIterateThenAddThenIterate() {
 195         int size = 1000;
 196         int[] fuzz = new int[size];
 197         Random rng = new Random(10);
 198         for (int i = 0; i < size; i++) {
 199             fuzz[i] = rng.nextInt(1000);
 200         }
 201         String name = new Object() {
 202         }.getClass().getEnclosingMethod().getName();
 203         assertNotNull(name);
 204         runIterateAddIterate(size, fuzz, name);
 205     }
 206
 207     /**
 208      * Test adding elements in a random order then iterate over the list, this
 209      * is an atypical degenerate use case.
 210      */
 211     @Test
 212     public void test8AddFuzzyOrderThenIterateByStartTime() {
 213         int size = 1000;
 214         int[] fuzz = new int[size];
 215         Random rng = new Random(10);
 216         for (int i = 0; i < size; i++) {
 217             fuzz[i] = rng.nextInt(1000);
 218         }
 219         String name = new Object() {
 220         }.getClass().getEnclosingMethod().getName();
 221         assertNotNull(name);
 222         runIterateCompare(size, fuzz, name, SegmentComparators.INTERVAL_START_COMPARATOR);
 223     }
 224
 225     /**
 226      * Test adding elements in a random order then iterate over the list, this
 227      * is an atypical degenerate use case.
 228      */
 229     @Test
 230     public void test9AddFuzzyOrderThenIterateByEndTime() {
 231         int size = 1000;
 232         int[] fuzz = new int[size];
 233         Random rng = new Random(10);
 234         for (int i = 0; i < size; i++) {
 235             fuzz[i] = rng.nextInt(1000);
 236         }
 237         String name = new Object() {
 238         }.getClass().getEnclosingMethod().getName();
 239         assertNotNull(name);
 240         runIterateCompare(size, fuzz, name, SegmentComparators.INTERVAL_END_COMPARATOR);
 241     }
 242
 243     /**
 244      * Test adding elements in a random order then iterate over the list, this
 245      * is an atypical degenerate use case.
 246      */
 247     @Test
 248     public void testAAddFuzzyOrderThenIterateByDuration() {
 249         int size = 1000;
 250         int[] fuzz = new int[size];
 251         Random rng = new Random(10);
 252         for (int i = 0; i < size; i++) {
 253             fuzz[i] = rng.nextInt(1000);
 254         }
 255         String name = new Object() {
 256         }.getClass().getEnclosingMethod().getName();
 257         assertNotNull(name);
 258         runIterateCompare(size, fuzz, name, SegmentComparators.INTERVAL_LENGTH_COMPARATOR);
 259     }
 260
 261     private void runIterateCompare(int size, int[] fuzz, String method, @NonNull Comparator<@NonNull ISegment> comparator) {
 262         long start = System.nanoTime();
 263         populate(size, fuzz, fSegStore);
 264         long startTime = fuzz[0];
 265         long endTime = fSegStore.size() - 1 + fuzz[fSegStore.size() % size];
 266         iterateCompare(startTime, endTime, fSegStore, comparator);
 267         long end = System.nanoTime();
 268         long duration = end - start;
 269         outputResults(duration, method);
 270     }
 271
 272     private void run(int size, int[] fuzz, String method) {
 273         long duration = populate(size, fuzz, fSegStore);
 274         outputResults(duration, method);
 275     }
 276
 277
 278     private long populate(int size, int[] fuzz, ISegmentStore<@NonNull ISegment> store) {
 279         store.clear();
 280         long start = System.nanoTime();
 281         populate(size, fuzz, store, getSegmentStoreSize());
 282         long end = System.nanoTime();
 283         return end - start;
 284     }
 285
 286     private void runIterate(int size, int[] fuzz, String method) {
 287         long duration = addAndIterate(size, fuzz, fSegStore);
 288
 289         outputResults(duration, method);
 290     }
 291
 292     private long addAndIterate(int size, int[] fuzz, ISegmentStore<@NonNull ISegment> store) {
 293         long start = System.nanoTime();
 294         populate(size, fuzz, store);
 295         iterate(store);
 296         long end = System.nanoTime();
 297         return end - start;
 298     }
 299
 300     private void runIterateAddIterate(int size, int[] fuzz, String method) {
 301         long duration = runIterateAddIterate(size, fuzz, fSegStore);
 302         outputResults(duration, method);
 303     }
 304
 305     private static long runIterateAddIterate(int size, int[] fuzz, ISegmentStore<@NonNull ISegment> store) {
 306         store.clear();
 307         long start = System.nanoTime();
 308         for (int i = 0; i < 50000; i++) {
 309             long startTime = i + fuzz[i % size];
 310             store.add(new BasicSegment(startTime, startTime + 10));
 311         }
 312         iterate(store);
 313         for (int i = 50000; i < 100000; i++) {
 314             long startTime = i + fuzz[i % size];
 315             store.add(new BasicSegment(startTime, startTime + 10));
 316         }
 317         iterate(store);
 318         long end = System.nanoTime();
 319         return end - start;
 320     }
 321
 322     private static Object iterate(ISegmentStore<@NonNull ISegment> store) {
 323         Object shutupCompilerWarnings = null;
 324         for (ISegment elem : store) {
 325             shutupCompilerWarnings = elem;
 326         }
 327         return shutupCompilerWarnings;
 328     }
 329
 330     private static Object iterateCompare(long startTime, long endTime, ISegmentStore<@NonNull ISegment> store, @NonNull Comparator<@NonNull ISegment> comparator) {
 331         Object shutupCompilerWarnings = null;
 332         for (ISegment elem : store.getIntersectingElements(startTime, endTime, comparator)) {
 333             shutupCompilerWarnings = elem;
 334         }
 335         return shutupCompilerWarnings;
 336     }
 337
 338     private static void populate(int size, int[] fuzz, ISegmentStore<@NonNull ISegment> store, long count) {
 339         for (int i = 0; i < count; i++) {
 340             long start = (long) i + fuzz[i % size];
 341             store.add(new BasicSegment(start, start + 10));
 342         }
 343     }
 344
 345     private void outputResults(long duration, String method) {
 346         System.out.println(fName + ": Time taken for test " + method + ": " + FORMAT.format(duration));
 347     }
 348 }