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
.store
;
12 import static org
.junit
.Assert
.assertNotNull
;
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
;
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
;
36 * Segmentstore benchmarks, tests the performance for loads and reads.
38 * NOTE : Do not add this to isTracecompassFastYet, it is not information that
39 * is interesting for users, it is for developpers.
43 * @author Matthew Khouzam
46 @FixMethodOrder(MethodSorters
.NAME_ASCENDING
)
47 @RunWith(Parameterized
.class)
48 public class SegmentStoreBenchmark
{
50 private final ISegmentStore
<@NonNull ISegment
> fSegStore
;
51 private final String fName
;
52 private static final Format FORMAT
= new DecimalFormat("###,###.##"); //$NON-NLS-1$
55 * @return The arrays of parameters
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
<>() },
70 * The name of this test
72 * The segment store to fill for the benchmarks
74 public SegmentStoreBenchmark(String name
, ISegmentStore
<@NonNull ISegment
> segStore
) {
80 * Get the number of segments to add to the segment store
82 * @return The number of segments to add to the segment store
84 protected long getSegmentStoreSize() {
89 * Add elements in order
92 public void test1AddInOrder() {
95 run(size
, fuzz
, new Object() {
96 }.getClass().getEnclosingMethod().getName());
100 * Add elements almost in order, this represents a typical degenerate use
104 public void test2AddFuzzyOrder() {
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);
111 String name
= new Object() {
112 }.getClass().getEnclosingMethod().getName();
114 run(size
, fuzz
, name
);
118 * Add elements almost in order, this represents a typical degenerate use
119 * case, then iterate over the list.
122 public void test3AddFuzzyOrderThenIterate() {
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);
129 String name
= new Object() {
130 }.getClass().getEnclosingMethod().getName();
132 runIterate(size
, fuzz
, name
);
136 * Add elements almost in order, this represents a typical degenerate use
137 * case, and iterate while building then when done.
140 public void test4AddFuzzyOrderThenIterateThenAddThenIterate() {
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);
147 String name
= new Object() {
148 }.getClass().getEnclosingMethod().getName();
150 runIterateAddIterate(size
, fuzz
, name
);
154 * Test adding elements in a random order, this is an atypical degenerate
158 public void test5AddRandomOrder() {
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());
165 String name
= new Object() {
166 }.getClass().getEnclosingMethod().getName();
168 runIterate(size
, fuzz
, name
);
172 * Test adding elements in a random order then iterate over the list, this
173 * is an atypical degenerate use case.
176 public void test6AddRandomOrderThenIterate() {
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());
183 String name
= new Object() {
184 }.getClass().getEnclosingMethod().getName();
186 runIterate(size
, fuzz
, name
);
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.
194 public void test7AddRandomOrderThenIterateThenAddThenIterate() {
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);
201 String name
= new Object() {
202 }.getClass().getEnclosingMethod().getName();
204 runIterateAddIterate(size
, fuzz
, name
);
208 * Test adding elements in a random order then iterate over the list, this
209 * is an atypical degenerate use case.
212 public void test8AddFuzzyOrderThenIterateByStartTime() {
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);
219 String name
= new Object() {
220 }.getClass().getEnclosingMethod().getName();
222 runIterateCompare(size
, fuzz
, name
, SegmentComparators
.INTERVAL_START_COMPARATOR
);
226 * Test adding elements in a random order then iterate over the list, this
227 * is an atypical degenerate use case.
230 public void test9AddFuzzyOrderThenIterateByEndTime() {
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);
237 String name
= new Object() {
238 }.getClass().getEnclosingMethod().getName();
240 runIterateCompare(size
, fuzz
, name
, SegmentComparators
.INTERVAL_END_COMPARATOR
);
244 * Test adding elements in a random order then iterate over the list, this
245 * is an atypical degenerate use case.
248 public void testAAddFuzzyOrderThenIterateByDuration() {
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);
255 String name
= new Object() {
256 }.getClass().getEnclosingMethod().getName();
258 runIterateCompare(size
, fuzz
, name
, SegmentComparators
.INTERVAL_LENGTH_COMPARATOR
);
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
);
272 private void run(int size
, int[] fuzz
, String method
) {
273 long duration
= populate(size
, fuzz
, fSegStore
);
274 outputResults(duration
, method
);
278 private long populate(int size
, int[] fuzz
, ISegmentStore
<@NonNull ISegment
> store
) {
280 long start
= System
.nanoTime();
281 populate(size
, fuzz
, store
, getSegmentStoreSize());
282 long end
= System
.nanoTime();
286 private void runIterate(int size
, int[] fuzz
, String method
) {
287 long duration
= addAndIterate(size
, fuzz
, fSegStore
);
289 outputResults(duration
, method
);
292 private long addAndIterate(int size
, int[] fuzz
, ISegmentStore
<@NonNull ISegment
> store
) {
293 long start
= System
.nanoTime();
294 populate(size
, fuzz
, store
);
296 long end
= System
.nanoTime();
300 private void runIterateAddIterate(int size
, int[] fuzz
, String method
) {
301 long duration
= runIterateAddIterate(size
, fuzz
, fSegStore
);
302 outputResults(duration
, method
);
305 private static long runIterateAddIterate(int size
, int[] fuzz
, ISegmentStore
<@NonNull ISegment
> store
) {
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));
313 for (int i
= 50000; i
< 100000; i
++) {
314 long startTime
= i
+ fuzz
[i
% size
];
315 store
.add(new BasicSegment(startTime
, startTime
+ 10));
318 long end
= System
.nanoTime();
322 private static Object
iterate(ISegmentStore
<@NonNull ISegment
> store
) {
323 Object shutupCompilerWarnings
= null;
324 for (ISegment elem
: store
) {
325 shutupCompilerWarnings
= elem
;
327 return shutupCompilerWarnings
;
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
;
335 return shutupCompilerWarnings
;
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));
345 private void outputResults(long duration
, String method
) {
346 System
.out
.println(fName
+ ": Time taken for test " + method
+ ": " + FORMAT
.format(duration
));