How to use Is class of org.hamcrest.core package

Best junit code snippet using org.hamcrest.core.Is

Run junit automation tests on LambdaTest cloud grid

Perform automation testing on 3000+ real desktop and mobile devices online.

copy
1package org.hamcrest;
2
3@SuppressWarnings("UnusedDeclaration")
4public class CoreMatchers {
5
6  /**
7   * Creates a matcher that matches if the examined object matches <b>ALL</b> of the specified matchers.
8   * For example:
9   * <pre>assertThat("myValue", allOf(startsWith("my"), containsString("Val")))</pre>
10   */
11  public static <T> org.hamcrest.Matcher<T> allOf(java.lang.Iterable<org.hamcrest.Matcher<? super T>> matchers) {
12    return org.hamcrest.core.AllOf.<T>allOf(matchers);
13  }
14
15  /**
16   * Creates a matcher that matches if the examined object matches <b>ALL</b> of the specified matchers.
17   * For example:
18   * <pre>assertThat("myValue", allOf(startsWith("my"), containsString("Val")))</pre>
19   */
20  @SafeVarargs
21  public static <T> org.hamcrest.Matcher<T> allOf(org.hamcrest.Matcher<? super T>... matchers) {
22    return org.hamcrest.core.AllOf.<T>allOf(matchers);
23  }
24
25
26  /**
27   * Creates a matcher that matches if the examined object matches <b>ANY</b> of the specified matchers.
28   * For example:
29   * <pre>assertThat("myValue", anyOf(startsWith("foo"), containsString("Val")))</pre>
30   */
31  public static <T> org.hamcrest.core.AnyOf<T> anyOf(java.lang.Iterable<org.hamcrest.Matcher<? super T>> matchers) {
32    return org.hamcrest.core.AnyOf.<T>anyOf(matchers);
33  }
34
35  /**
36   * Creates a matcher that matches if the examined object matches <b>ANY</b> of the specified matchers.
37   * For example:
38   * <pre>assertThat("myValue", anyOf(startsWith("foo"), containsString("Val")))</pre>
39   */
40  @SafeVarargs
41  public static <T> org.hamcrest.core.AnyOf<T> anyOf(org.hamcrest.Matcher<? super T>... matchers) {
42    return org.hamcrest.core.AnyOf.<T>anyOf(matchers);
43  }
44
45  /**
46   * Creates a matcher that matches when both of the specified matchers match the examined object.
47   * For example:
48   * <pre>assertThat("fab", both(containsString("a")).and(containsString("b")))</pre>
49   */
50  public static <LHS> org.hamcrest.core.CombinableMatcher.CombinableBothMatcher<LHS> both(org.hamcrest.Matcher<? super LHS> matcher) {
51    return org.hamcrest.core.CombinableMatcher.both(matcher);
52  }
53
54  /**
55   * Creates a matcher that matches when either of the specified matchers match the examined object.
56   * For example:
57   * <pre>assertThat("fan", either(containsString("a")).or(containsString("b")))</pre>
58   */
59  public static <LHS> org.hamcrest.core.CombinableMatcher.CombinableEitherMatcher<LHS> either(org.hamcrest.Matcher<? super LHS> matcher) {
60    return org.hamcrest.core.CombinableMatcher.either(matcher);
61  }
62
63  /**
64   * Wraps an existing matcher, overriding its description with that specified.  All other functions are
65   * delegated to the decorated matcher, including its mismatch description.
66   * For example:
67   * <pre>describedAs("a big decimal equal to %0", equalTo(myBigDecimal), myBigDecimal.toPlainString())</pre>
68   * 
69   * @param description
70   *     the new description for the wrapped matcher
71   * @param matcher
72   *     the matcher to wrap
73   * @param values
74   *     optional values to insert into the tokenised description
75   */
76  public static <T> org.hamcrest.Matcher<T> describedAs(java.lang.String description, org.hamcrest.Matcher<T> matcher, java.lang.Object... values) {
77    return org.hamcrest.core.DescribedAs.describedAs(description, matcher, values);
78  }
79
80  /**
81   * Creates a matcher for {@link Iterable}s that only matches when a single pass over the
82   * examined {@link Iterable} yields items that are all matched by the specified
83   * <code>itemMatcher</code>.
84   * For example:
85   * <pre>assertThat(Arrays.asList("bar", "baz"), everyItem(startsWith("ba")))</pre>
86   * 
87   * @param itemMatcher
88   *     the matcher to apply to every item provided by the examined {@link Iterable}
89   */
90  public static <U> org.hamcrest.Matcher<java.lang.Iterable<? extends U>> everyItem(org.hamcrest.Matcher<U> itemMatcher) {
91    return org.hamcrest.core.Every.everyItem(itemMatcher);
92  }
93
94  /**
95   * Decorates another Matcher, retaining its behaviour, but allowing tests
96   * to be slightly more expressive.
97   * For example:
98   * <pre>assertThat(cheese, is(equalTo(smelly)))</pre>
99   * instead of:
100   * <pre>assertThat(cheese, equalTo(smelly))</pre>
101   */
102  public static <T> org.hamcrest.Matcher<T> is(org.hamcrest.Matcher<T> matcher) {
103    return org.hamcrest.core.Is.is(matcher);
104  }
105
106  /**
107   * A shortcut to the frequently used <code>is(equalTo(x))</code>.
108   * For example:
109   * <pre>assertThat(cheese, is(smelly))</pre>
110   * instead of:
111   * <pre>assertThat(cheese, is(equalTo(smelly)))</pre>
112   */
113  public static <T> org.hamcrest.Matcher<T> is(T value) {
114    return org.hamcrest.core.Is.is(value);
115  }
116
117  /**
118   * Provided to cause compile time error when used in preference to a possible runtime error if
119   * this was not here.
120   *
121   * <p>This method was removed upstream between Hamcrest 1.1 and 1.3 in favour of the
122   * instanceOf(Class) method. Unfortunately, existing usages of it could still compile against the
123   * {@link #is(Object)} method instead. Although not every existing usage would compile
124   * successfully it is possible that some could and that would result in a change in the runtime
125   * behavior that could be difficult to detect and fix. This change aims to turn any significant
126   * usage of this method into a compile time error.
127   *
128   * @deprecated Use instanceOf(SomeClass.class) instead.
129   */
130  public static void is(java.lang.Class<?> type) {
131  }
132
133  /**
134   * A shortcut to the frequently used <code>is(instanceOf(SomeClass.class))</code>.
135   * For example:
136   * <pre>assertThat(cheese, isA(Cheddar.class))</pre>
137   * instead of:
138   * <pre>assertThat(cheese, is(instanceOf(Cheddar.class)))</pre>
139   */
140  public static <T> org.hamcrest.Matcher<T> isA(java.lang.Class<T> type) {
141    return org.hamcrest.core.Is.isA(type);
142  }
143
144  /**
145   * Creates a matcher that always matches, regardless of the examined object.
146   */
147  public static org.hamcrest.Matcher<java.lang.Object> anything() {
148    return org.hamcrest.core.IsAnything.anything();
149  }
150
151  /**
152   * Creates a matcher that always matches, regardless of the examined object, but describes
153   * itself with the specified {@link String}.
154   * 
155   * @param description
156   *     a meaningful {@link String} used when describing itself
157   */
158  public static org.hamcrest.Matcher<java.lang.Object> anything(java.lang.String description) {
159    return org.hamcrest.core.IsAnything.anything(description);
160  }
161
162  /**
163   * Creates a matcher for {@link Iterable}s that only matches when a single pass over the
164   * examined {@link Iterable} yields at least one item that is matched by the specified
165   * <code>itemMatcher</code>.  Whilst matching, the traversal of the examined {@link Iterable}
166   * will stop as soon as a matching item is found.
167   * For example:
168   * <pre>assertThat(Arrays.asList("foo", "bar"), hasItem(startsWith("ba")))</pre>
169   * 
170   * @param itemMatcher
171   *     the matcher to apply to items provided by the examined {@link Iterable}
172   */
173  public static <T> org.hamcrest.Matcher<java.lang.Iterable<? super T>> hasItem(org.hamcrest.Matcher<? super T> itemMatcher) {
174    return org.hamcrest.core.IsCollectionContaining.<T>hasItem(itemMatcher);
175  }
176
177  /**
178   * Creates a matcher for {@link Iterable}s that only matches when a single pass over the
179   * examined {@link Iterable} yields at least one item that is equal to the specified
180   * <code>item</code>.  Whilst matching, the traversal of the examined {@link Iterable}
181   * will stop as soon as a matching item is found.
182   * For example:
183   * <pre>assertThat(Arrays.asList("foo", "bar"), hasItem("bar"))</pre>
184   * 
185   * @param item
186   *     the item to compare against the items provided by the examined {@link Iterable}
187   */
188  public static <T> org.hamcrest.Matcher<java.lang.Iterable<? super T>> hasItem(T item) {
189    return org.hamcrest.core.IsCollectionContaining.<T>hasItem(item);
190  }
191
192  /**
193   * Creates a matcher for {@link Iterable}s that matches when consecutive passes over the
194   * examined {@link Iterable} yield at least one item that is matched by the corresponding
195   * matcher from the specified <code>itemMatchers</code>.  Whilst matching, each traversal of
196   * the examined {@link Iterable} will stop as soon as a matching item is found.
197   * For example:
198   * <pre>assertThat(Arrays.asList("foo", "bar", "baz"), hasItems(endsWith("z"), endsWith("o")))</pre>
199   * 
200   * @param itemMatchers
201   *     the matchers to apply to items provided by the examined {@link Iterable}
202   */
203  @SafeVarargs
204  public static <T> org.hamcrest.Matcher<java.lang.Iterable<T>> hasItems(org.hamcrest.Matcher<? super T>... itemMatchers) {
205    return org.hamcrest.core.IsCollectionContaining.<T>hasItems(itemMatchers);
206  }
207
208  /**
209   * Creates a matcher for {@link Iterable}s that matches when consecutive passes over the
210   * examined {@link Iterable} yield at least one item that is equal to the corresponding
211   * item from the specified <code>items</code>.  Whilst matching, each traversal of the
212   * examined {@link Iterable} will stop as soon as a matching item is found.
213   * For example:
214   * <pre>assertThat(Arrays.asList("foo", "bar", "baz"), hasItems("baz", "foo"))</pre>
215   * 
216   * @param items
217   *     the items to compare against the items provided by the examined {@link Iterable}
218   */
219  @SafeVarargs
220  public static <T> org.hamcrest.Matcher<java.lang.Iterable<T>> hasItems(T... items) {
221    return org.hamcrest.core.IsCollectionContaining.<T>hasItems(items);
222  }
223
224  /**
225   * Creates a matcher that matches when the examined object is logically equal to the specified
226   * <code>operand</code>, as determined by calling the {@link java.lang.Object#equals} method on
227   * the <b>examined</b> object.
228   * 
229   * <p>If the specified operand is <code>null</code> then the created matcher will only match if
230   * the examined object's <code>equals</code> method returns <code>true</code> when passed a
231   * <code>null</code> (which would be a violation of the <code>equals</code> contract), unless the
232   * examined object itself is <code>null</code>, in which case the matcher will return a positive
233   * match.</p>
234   * 
235   * <p>The created matcher provides a special behaviour when examining <code>Array</code>s, whereby
236   * it will match if both the operand and the examined object are arrays of the same length and
237   * contain items that are equal to each other (according to the above rules) <b>in the same
238   * indexes</b>.</p> 
239   * For example:
240   * <pre>
241   * assertThat("foo", equalTo("foo"));
242   * assertThat(new String[] {"foo", "bar"}, equalTo(new String[] {"foo", "bar"}));
243   * </pre>
244   */
245  public static <T> org.hamcrest.Matcher<T> equalTo(T operand) {
246    return org.hamcrest.core.IsEqual.equalTo(operand);
247  }
248
249  /**
250   * Creates an {@link org.hamcrest.core.IsEqual} matcher that does not enforce the values being
251   * compared to be of the same static type.
252   */
253  public static org.hamcrest.Matcher<java.lang.Object> equalToObject(java.lang.Object operand) {
254    return org.hamcrest.core.IsEqual.equalToObject(operand);
255  }
256
257  /**
258   * Creates a matcher that matches when the examined object is an instance of the specified <code>type</code>,
259   * as determined by calling the {@link java.lang.Class#isInstance(Object)} method on that type, passing the
260   * the examined object.
261   * 
262   * <p>The created matcher forces a relationship between specified type and the examined object, and should be
263   * used when it is necessary to make generics conform, for example in the JMock clause
264   * <code>with(any(Thing.class))</code></p>
265   * For example:
266   * <pre>assertThat(new Canoe(), instanceOf(Canoe.class));</pre>
267   */
268  public static <T> org.hamcrest.Matcher<T> any(java.lang.Class<T> type) {
269    return org.hamcrest.core.IsInstanceOf.any(type);
270  }
271
272  /**
273   * Creates a matcher that matches when the examined object is an instance of the specified <code>type</code>,
274   * as determined by calling the {@link java.lang.Class#isInstance(Object)} method on that type, passing the
275   * the examined object.
276   * 
277   * <p>The created matcher assumes no relationship between specified type and the examined object.</p>
278   * For example:
279   * <pre>assertThat(new Canoe(), instanceOf(Paddlable.class));</pre>
280   */
281  public static <T> org.hamcrest.Matcher<T> instanceOf(java.lang.Class<?> type) {
282    return org.hamcrest.core.IsInstanceOf.instanceOf(type);
283  }
284
285  /**
286   * Creates a matcher that wraps an existing matcher, but inverts the logic by which
287   * it will match.
288   * For example:
289   * <pre>assertThat(cheese, is(not(equalTo(smelly))))</pre>
290   * 
291   * @param matcher
292   *     the matcher whose sense should be inverted
293   */
294  public static <T> org.hamcrest.Matcher<T> not(org.hamcrest.Matcher<T> matcher) {
295    return org.hamcrest.core.IsNot.not(matcher);
296  }
297
298  /**
299   * A shortcut to the frequently used <code>not(equalTo(x))</code>.
300   * For example:
301   * <pre>assertThat(cheese, is(not(smelly)))</pre>
302   * instead of:
303   * <pre>assertThat(cheese, is(not(equalTo(smelly))))</pre>
304   * 
305   * @param value
306   *     the value that any examined object should <b>not</b> equal
307   */
308  public static <T> org.hamcrest.Matcher<T> not(T value) {
309    return org.hamcrest.core.IsNot.not(value);
310  }
311
312  /**
313   * A shortcut to the frequently used <code>not(nullValue())</code>.
314   * For example:
315   * <pre>assertThat(cheese, is(notNullValue()))</pre>
316   * instead of:
317   * <pre>assertThat(cheese, is(not(nullValue())))</pre>
318   */
319  public static org.hamcrest.Matcher<java.lang.Object> notNullValue() {
320    return org.hamcrest.core.IsNull.notNullValue();
321  }
322
323  /**
324   * A shortcut to the frequently used <code>not(nullValue(X.class)). Accepts a
325   * single dummy argument to facilitate type inference.</code>.
326   * For example:
327   * <pre>assertThat(cheese, is(notNullValue(X.class)))</pre>
328   * instead of:
329   * <pre>assertThat(cheese, is(not(nullValue(X.class))))</pre>
330   * 
331   * @param type
332   *     dummy parameter used to infer the generic type of the returned matcher
333   */
334  public static <T> org.hamcrest.Matcher<T> notNullValue(java.lang.Class<T> type) {
335    return org.hamcrest.core.IsNull.notNullValue(type);
336  }
337
338  /**
339   * Creates a matcher that matches if examined object is <code>null</code>.
340   * For example:
341   * <pre>assertThat(cheese, is(nullValue())</pre>
342   */
343  public static org.hamcrest.Matcher<java.lang.Object> nullValue() {
344    return org.hamcrest.core.IsNull.nullValue();
345  }
346
347  /**
348   * Creates a matcher that matches if examined object is <code>null</code>. Accepts a
349   * single dummy argument to facilitate type inference.
350   * For example:
351   * <pre>assertThat(cheese, is(nullValue(Cheese.class))</pre>
352   * 
353   * @param type
354   *     dummy parameter used to infer the generic type of the returned matcher
355   */
356  public static <T> org.hamcrest.Matcher<T> nullValue(java.lang.Class<T> type) {
357    return org.hamcrest.core.IsNull.nullValue(type);
358  }
359
360  /**
361   * Creates a matcher that matches only when the examined object is the same instance as
362   * the specified target object.
363   * 
364   * @param target
365   *     the target instance against which others should be assessed
366   */
367  public static <T> org.hamcrest.Matcher<T> sameInstance(T target) {
368    return org.hamcrest.core.IsSame.sameInstance(target);
369  }
370
371  /**
372   * Creates a matcher that matches only when the examined object is the same instance as
373   * the specified target object.
374   * 
375   * @param target
376   *     the target instance against which others should be assessed
377   */
378  public static <T> org.hamcrest.Matcher<T> theInstance(T target) {
379    return org.hamcrest.core.IsSame.theInstance(target);
380  }
381
382  /**
383   * Creates a matcher that matches if the examined {@link String} contains the specified
384   * {@link String} anywhere.
385   * For example:
386   * <pre>assertThat("myStringOfNote", containsString("ring"))</pre>
387   * 
388   * @param substring
389   *     the substring that the returned matcher will expect to find within any examined string
390   */
391  public static org.hamcrest.Matcher<java.lang.String> containsString(java.lang.String substring) {
392    return org.hamcrest.core.StringContains.containsString(substring);
393  }
394
395  /**
396   * Creates a matcher that matches if the examined {@link String} contains the specified
397   * {@link String} anywhere, ignoring case.
398   * For example:
399   * <pre>assertThat("myStringOfNote", containsString("ring"))</pre>
400   * 
401   * @param substring
402   *     the substring that the returned matcher will expect to find within any examined string
403   */
404  public static org.hamcrest.Matcher<java.lang.String> containsStringIgnoringCase(java.lang.String substring) {
405    return org.hamcrest.core.StringContains.containsStringIgnoringCase(substring);
406  }
407
408  /**
409   * <p>
410   * Creates a matcher that matches if the examined {@link String} starts with the specified
411   * {@link String}.
412   * </p>
413   * For example:
414   * <pre>assertThat("myStringOfNote", startsWith("my"))</pre>
415   * 
416   * @param prefix
417   *      the substring that the returned matcher will expect at the start of any examined string
418   */
419  public static org.hamcrest.Matcher<java.lang.String> startsWith(java.lang.String prefix) {
420    return org.hamcrest.core.StringStartsWith.startsWith(prefix);
421  }
422
423  /**
424   * <p>
425   * Creates a matcher that matches if the examined {@link String} starts with the specified
426   * {@link String}, ignoring case
427   * </p>
428   * For example:
429   * <pre>assertThat("myStringOfNote", startsWith("my"))</pre>
430   * 
431   * @param prefix
432   *      the substring that the returned matcher will expect at the start of any examined string
433   */
434  public static org.hamcrest.Matcher<java.lang.String> startsWithIgnoringCase(java.lang.String prefix) {
435    return org.hamcrest.core.StringStartsWith.startsWithIgnoringCase(prefix);
436  }
437
438  /**
439   * Creates a matcher that matches if the examined {@link String} ends with the specified
440   * {@link String}.
441   * For example:
442   * <pre>assertThat("myStringOfNote", endsWith("Note"))</pre>
443   * 
444   * @param suffix
445   *      the substring that the returned matcher will expect at the end of any examined string
446   */
447  public static org.hamcrest.Matcher<java.lang.String> endsWith(java.lang.String suffix) {
448    return org.hamcrest.core.StringEndsWith.endsWith(suffix);
449  }
450
451  /**
452   * Creates a matcher that matches if the examined {@link String} ends with the specified
453   * {@link String}, ignoring case.
454   * For example:
455   * <pre>assertThat("myStringOfNote", endsWith("Note"))</pre>
456   * 
457   * @param suffix
458   *      the substring that the returned matcher will expect at the end of any examined string
459   */
460  public static org.hamcrest.Matcher<java.lang.String> endsWithIgnoringCase(java.lang.String suffix) {
461    return org.hamcrest.core.StringEndsWith.endsWithIgnoringCase(suffix);
462  }
463
464}
465
Full Screen
copy
1// CPP program to demonstrate processing
2// time of sorted and unsorted array
3#include <iostream>
4#include <algorithm>
5#include <ctime>
6using namespace std;
7
8const int N = 100001;
9
10int main()
11{
12    int arr[N];
13
14    // Assign random values to array
15    for (int i=0; i<N; i++)
16        arr[i] = rand()%N;
17
18    // for loop for unsorted array
19    int count = 0;
20    double start = clock();
21    for (int i=0; i<N; i++)
22        if (arr[i] < N/2)
23            count++;
24
25    double end = clock();
26    cout << "Time for unsorted array :: "
27        << ((end - start)/CLOCKS_PER_SEC)
28        << endl;
29    sort(arr, arr+N);
30
31    // for loop for sorted array
32    count = 0;
33    start = clock();
34
35    for (int i=0; i<N; i++)
36        if (arr[i] < N/2)
37            count++;
38
39    end = clock();
40    cout << "Time for sorted array :: "
41        << ((end - start)/CLOCKS_PER_SEC)
42        << endl;
43
44    return 0;
45}
46
Full Screen
copy
1Already sorted    32995 milliseconds
2Shuffled          125944 milliseconds
3
4Already sorted    18610 milliseconds
5Shuffled          133304 milliseconds
6
7Already sorted    17942 milliseconds
8Shuffled          107858 milliseconds
9
Full Screen
copy
1void run(vector<int>& v, const string& label)
2{
3    auto t0 = system_clock::now();
4    sort(v.begin(), v.end());
5    auto t1 = system_clock::now();
6    cout << label
7         << duration_cast<microseconds>(t1 — t0).count()
8         << " milliseconds\n";
9}
10
11void tst()
12{
13    vector<int> v(1'000'000);
14    iota(v.begin(), v.end(), 0);
15    run(v, "already sorted ");
16    std::shuffle(v.begin(), v.end(), std::mt19937{ std::random_device{}() });
17    run(v, "shuffled    ");
18}
19
Full Screen
copy
1#include <algorithm>
2#include <ctime>
3#include <iostream>
4
5int main() {
6    int data[32768]; const int l = sizeof data / sizeof data[0];
7
8    for (unsigned c = 0; c < l; ++c)
9        data[c] = std::rand() % 256;
10
11    // sort 200-element segments, not the whole array
12    for (unsigned c = 0; c + 200 <= l; c += 200)
13        std::sort(&data[c], &data[c + 200]);
14
15    clock_t start = clock();
16    long long sum = 0;
17
18    for (unsigned i = 0; i < 100000; ++i) {
19        for (unsigned c = 0; c < sizeof data / sizeof(int); ++c) {
20            if (data[c] >= 128)
21                sum += data[c];
22        }
23    }
24
25    std::cout << static_cast<double>(clock() - start) / CLOCKS_PER_SEC << std::endl;
26    std::cout << "sum = " << sum << std::endl;
27}
28
Full Screen
copy
1% Processing time with Sorted data vs unsorted data
2%==========================================================================
3% Generate data
4arraySize = 32768
5sum = 0;
6% Generate random integer data from range 0 to 255
7data = randi(256, arraySize, 1);
8
9
10%Sort the data
11data1= sort(data); % data1= data  when no sorting done
12
13
14%Start a stopwatch timer to measure the execution time
15tic;
16
17for i=1:100000
18
19    for j=1:arraySize
20
21        if data1(j)>=128
22            sum=sum + data1(j);
23        end
24    end
25end
26
27toc;
28
29ExeTimeWithSorting = toc - tic;
30
Full Screen
copy
1  a: Elapsed time (without sorting) = 3479.880861 seconds.
2  b: Elapsed time (with sorting ) = 2377.873098 seconds.
3
Full Screen
copy
1  a: Elapsed time (without sorting) = 19.8761 sec.
2  b: Elapsed time (with sorting ) = 7.37778 sec.
3
Full Screen
copy
1____________________________________________________________________________________
2- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
3TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
4
Full Screen
copy
1___________________________________________ Straight road
2 |_________________________________________|Longer road
3
Full Screen
copy
1 // sort backwards (higher values first), may be in some other part of the code
2 std::sort(data, data + arraySize, std::greater<int>());
3
4 for (unsigned c = 0; c < arraySize; ++c) {
5       if (data[c] < 128) {
6              break;
7       }
8       sum += data[c];               
9 }
10
Full Screen
copy
1MOV R0, #0   // R0 = sum = 0
2MOV R1, #0   // R1 = c = 0
3ADR R2, data // R2 = addr of data array (put this instruction outside outer loop)
4.inner_loop  // Inner loop branch label
5    LDRB R3, [R2, R1]   // R3 = data[c]
6    CMP R3, #128        // compare R3 to 128
7    ADDGE R0, R0, R3    // if R3 >= 128, then sum += data[c] -- no branch needed!
8    ADD R1, R1, #1      // c++
9    CMP R1, #arraySize  // compare c to arraySize
10    BLT inner_loop      // Branch to inner_loop if c < arraySize
11
Full Screen
copy
1if (expression)
2{
3    // Run 1
4} else {
5    // Run 2
6}
7
Full Screen
copy
1 O      Route 1  /-------------------------------
2/|\             /
3 |  ---------##/
4/ \            \
5                \
6        Route 2  \--------------------------------
7
Full Screen
copy
1bool a, b, c, d;
2if (a != 0) {
3    if (b != 0) {
4        c = 1;
5    }
6    else {
7        goto CFALSE;
8    }
9}
10else {
11    CFALSE:
12    c = 0;
13}
14if (a == 0) {
15    if (b == 0) {
16        d = 0;
17    }
18    else {
19        goto DTRUE;
20    }
21}
22else {
23    DTRUE:
24    d = 1;
25}
26
Full Screen
copy
1char a = 0, b = 1, c, d;
2c = a & b;
3d = a | b;
4
Full Screen
copy
1bool a; double x, y, z;
2a = x > y && z < 5.0;
3
Full Screen
copy
1if (likely( everything_is_ok ))
2{
3    /* Do something */
4}
5
Full Screen
copy
1if (unlikely(very_improbable_condition))
2{
3    /* Do something */    
4}
5
Full Screen
copy
1                        A) if (data[c] >= 128)
2                                /\
3                               /  \
4                              /    \
5                        true /      \ false
6                            /        \
7                           /          \
8                          /            \
9                         /              \
10              B) sum += data[c];          C) for loop or print().
11
Full Screen
copy
1int i= 0, j, k= arraySize;
2while (i < k)
3{
4  j= (i + k) >> 1;
5  if (data[j] >= 128)
6    k= j;
7  else
8    i= j;
9}
10sum= 0;
11for (; i < arraySize; i++)
12  sum+= data[i];
13
Full Screen
copy
1int i, k, j= (i + k) >> 1;
2for (i= 0, k= arraySize; i < k; (data[j] >= 128 ? k : i)= j)
3  j= (i + k) >> 1;
4for (sum= 0; i < arraySize; i++)
5  sum+= data[i];
6
Full Screen
copy
1// Test
2clock_t start = clock();
3long long a[] = {0, 0};
4long long sum;
5
6for (unsigned i = 0; i < 100000; ++i)
7{
8    // Primary loop
9    for (unsigned c = 0; c < arraySize; ++c)
10    {
11        int j = (data[c] >> 7);
12        a[j] += data[c];
13    }
14}
15
16double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;
17sum = a[1];
18
Full Screen
copy
1// Declare and then fill in the lookup table
2int lut[256];
3for (unsigned c = 0; c < 256; ++c)
4    lut[c] = (c >= 128) ? c : 0;
5
6// Use the lookup table after it is built
7for (unsigned i = 0; i < 100000; ++i)
8{
9    // Primary loop
10    for (unsigned c = 0; c < arraySize; ++c)
11    {
12        sum += lut[data[c]];
13    }
14}
15
Full Screen
copy
1if (x < node->value)
2    node = node->pLeft;
3else
4    node = node->pRight;
5
Full Screen
copy
1i = (x < node->value);
2node = node->link[i];
3
Full Screen
copy
1for (int i = 0; i < max; i++)
2    if (condition)
3        sum++;
4
Full Screen
copy
1Condition                Pattern             Time (ms)
2-------------------------------------------------------
3(i & 0Ă—80000000) == 0    T repeated          322
4
5(i & 0xffffffff) == 0    F repeated          276
6
7(i & 1) == 0             TF alternating      760
8
9(i & 3) == 0             TFFFTFFF…           513
10
11(i & 2) == 0             TTFFTTFF…           1675
12
13(i & 4) == 0             TTTTFFFFTTTTFFFF…   1275
14
15(i & 8) == 0             8T 8F 8T 8F …       752
16
17(i & 16) == 0            16T 16F 16T 16F …   490
18
Full Screen
copy
1for (int i = 0; i < array.Length; ++i)
2{
3   // Use array[i]
4}
5
Full Screen
copy
1// Generate data
2int arraySize = 32768;
3int[] data = new int[arraySize];
4
5Random random = new Random(0);
6for (int c = 0; c < arraySize; ++c)
7{
8    data[c] = random.Next(256);
9}
10
11/*To keep the spirit of the code intact, I'll make a separate lookup table
12(I assume we cannot modify 'data' or the number of loops)*/
13
14int[] lookup = new int[256];
15
16for (int c = 0; c < 256; ++c)
17{
18    lookup[c] = (c >= 128) ? c : 0;
19}
20
21// Test
22DateTime startTime = System.DateTime.Now;
23long sum = 0;
24
25for (int i = 0; i < 100000; ++i)
26{
27    // Primary loop
28    for (int j = 0; j < arraySize; ++j)
29    {
30        /* Here you basically want to use simple operations - so no
31        random branches, but things like &, |, *, -, +, etc. are fine. */
32        sum += lookup[data[j]];
33    }
34}
35
36DateTime endTime = System.DateTime.Now;
37Console.WriteLine(endTime - startTime);
38Console.WriteLine("sum = " + sum);
39Console.ReadLine();
40
Full Screen
copy
1==32551== Branches:        656,645,130  (  656,609,208 cond +    35,922 ind)
2==32551== Mispredicts:         169,556  (      169,095 cond +       461 ind)
3==32551== Mispred rate:            0.0% (          0.0%     +       1.2%   )
4
Full Screen
copy
1==32555== Branches:        655,996,082  (  655,960,160 cond +  35,922 ind)
2==32555== Mispredicts:     164,073,152  (  164,072,692 cond +     460 ind)
3==32555== Mispred rate:           25.0% (         25.0%     +     1.2%   )
4
Full Screen
copy
1          Bc    Bcm Bi Bim
2      10,001      4  0   0      for (unsigned i = 0; i < 10000; ++i)
3           .      .  .   .      {
4           .      .  .   .          // primary loop
5 327,690,000 10,016  0   0          for (unsigned c = 0; c < arraySize; ++c)
6           .      .  .   .          {
7 327,680,000 10,006  0   0              if (data[c] >= 128)
8           0      0  0   0                  sum += data[c];
9           .      .  .   .          }
10           .      .  .   .      }
11
Full Screen
copy
1          Bc         Bcm Bi Bim
2      10,001           4  0   0      for (unsigned i = 0; i < 10000; ++i)
3           .           .  .   .      {
4           .           .  .   .          // primary loop
5 327,690,000      10,038  0   0          for (unsigned c = 0; c < arraySize; ++c)
6           .           .  .   .          {
7 327,680,000 164,050,007  0   0              if (data[c] >= 128)
8           0           0  0   0                  sum += data[c];
9           .           .  .   .          }
10           .           .  .   .      }
11
Full Screen
copy
1 Performance counter stats for './sumtest_sorted':
2
3  11808.095776 task-clock                #    0.998 CPUs utilized          
4         1,062 context-switches          #    0.090 K/sec                  
5            14 CPU-migrations            #    0.001 K/sec                  
6           337 page-faults               #    0.029 K/sec                  
726,487,882,764 cycles                    #    2.243 GHz                    
841,025,654,322 instructions              #    1.55  insns per cycle        
9 6,558,871,379 branches                  #  555.455 M/sec                  
10       567,204 branch-misses             #    0.01% of all branches        
11
12  11.827228330 seconds time elapsed
13
Full Screen
copy
1 Performance counter stats for './sumtest_unsorted':
2
3  28877.954344 task-clock                #    0.998 CPUs utilized          
4         2,584 context-switches          #    0.089 K/sec                  
5            18 CPU-migrations            #    0.001 K/sec                  
6           335 page-faults               #    0.012 K/sec                  
765,076,127,595 cycles                    #    2.253 GHz                    
841,032,528,741 instructions              #    0.63  insns per cycle        
9 6,560,579,013 branches                  #  227.183 M/sec                  
10 1,646,394,749 branch-misses             #   25.10% of all branches        
11
12  28.935500947 seconds time elapsed
13
Full Screen
copy
1perf record -e branch-misses ./sumtest_unsorted
2perf annotate -d sumtest_unsorted
3
Full Screen
copy
1 Percent |      Source code & Disassembly of sumtest_unsorted
2------------------------------------------------
3...
4         :                      sum += data[c];
5    0.00 :        400a1a:       mov    -0x14(%rbp),%eax
6   39.97 :        400a1d:       mov    %eax,%eax
7    5.31 :        400a1f:       mov    -0x20040(%rbp,%rax,4),%eax
8    4.60 :        400a26:       cltq   
9    0.00 :        400a28:       add    %rax,-0x30(%rbp)
10...
11
Full Screen
copy
1for (unsigned i = 0; i < 100000; ++i)
2{
3    for (unsigned j = 0; j < arraySize; ++j)
4    {
5        if (data[j] >= 128)
6            sum += data[j];
7    }
8}
9
Full Screen
copy
1for (unsigned j = 0; j < arraySize; ++j)
2{
3    for (unsigned i = 0; i < 100000; ++i)
4    {
5        if (data[j] >= 128)
6            sum += data[j];
7    }
8}
9
Full Screen
copy
1for (unsigned j = 0; j < arraySize; ++j)
2{
3    if (data[j] >= 128)
4    {
5        for (unsigned i = 0; i < 100000; ++i)
6        {
7            sum += data[j];
8        }
9    }
10}
11
Full Screen
copy
1for (unsigned j = 0; j < arraySize; ++j)
2{
3    if (data[j] >= 128)
4    {
5        sum += data[j] * 100000;
6    }
7}
8
Full Screen
copy
1int max1(int a, int b) {
2    if (a > b)
3        return a;
4    else
5        return b;
6}
7
Full Screen
copy
1int max2(int a, int b) {
2    return a > b ? a : b;
3}
4
Full Screen
copy
1:max1
2    movl    %edi, -4(%rbp)
3    movl    %esi, -8(%rbp)
4    movl    -4(%rbp), %eax
5    cmpl    -8(%rbp), %eax
6    jle     .L2
7    movl    -4(%rbp), %eax
8    movl    %eax, -12(%rbp)
9    jmp     .L4
10.L2:
11    movl    -8(%rbp), %eax
12    movl    %eax, -12(%rbp)
13.L4:
14    movl    -12(%rbp), %eax
15    leave
16    ret
17
18:max2
19    movl    %edi, -4(%rbp)
20    movl    %esi, -8(%rbp)
21    movl    -4(%rbp), %eax
22    cmpl    %eax, -8(%rbp)
23    cmovge  -8(%rbp), %eax
24    leave
25    ret
26
Full Screen
copy
1T = branch taken
2N = branch not taken
3
4data[] = 0, 1, 2, 3, 4, ... 126, 127, 128, 129, 130, ... 250, 251, 252, ...
5branch = N  N  N  N  N  ...   N    N    T    T    T  ...   T    T    T  ...
6
7       = NNNNNNNNNNNN ... NNNNNNNTTTTTTTTT ... TTTTTTTTTT  (easy to predict)
8
Full Screen
copy
1data[] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118,  14, 150, 177, 182, ...
2branch =   T,   T,   N,   T,   T,   T,   T,  N,   T,   N,   N,   T,   T,   T  ...
3
4       = TTNTTTTNTNNTTT ...   (completely random - impossible to predict)
5
Full Screen
copy
1int t = (data[c] - 128) >> 31;
2sum += ~t & data[c];
3
Full Screen
copy
1// CPP program to demonstrate processing
2// time of sorted and unsorted array
3#include <iostream>
4#include <algorithm>
5#include <ctime>
6using namespace std;
7
8const int N = 100001;
9
10int main()
11{
12    int arr[N];
13
14    // Assign random values to array
15    for (int i=0; i<N; i++)
16        arr[i] = rand()%N;
17
18    // for loop for unsorted array
19    int count = 0;
20    double start = clock();
21    for (int i=0; i<N; i++)
22        if (arr[i] < N/2)
23            count++;
24
25    double end = clock();
26    cout << "Time for unsorted array :: "
27        << ((end - start)/CLOCKS_PER_SEC)
28        << endl;
29    sort(arr, arr+N);
30
31    // for loop for sorted array
32    count = 0;
33    start = clock();
34
35    for (int i=0; i<N; i++)
36        if (arr[i] < N/2)
37            count++;
38
39    end = clock();
40    cout << "Time for sorted array :: "
41        << ((end - start)/CLOCKS_PER_SEC)
42        << endl;
43
44    return 0;
45}
46
Full Screen
copy
1Already sorted    32995 milliseconds
2Shuffled          125944 milliseconds
3
4Already sorted    18610 milliseconds
5Shuffled          133304 milliseconds
6
7Already sorted    17942 milliseconds
8Shuffled          107858 milliseconds
9
Full Screen
copy
1void run(vector<int>& v, const string& label)
2{
3    auto t0 = system_clock::now();
4    sort(v.begin(), v.end());
5    auto t1 = system_clock::now();
6    cout << label
7         << duration_cast<microseconds>(t1 — t0).count()
8         << " milliseconds\n";
9}
10
11void tst()
12{
13    vector<int> v(1'000'000);
14    iota(v.begin(), v.end(), 0);
15    run(v, "already sorted ");
16    std::shuffle(v.begin(), v.end(), std::mt19937{ std::random_device{}() });
17    run(v, "shuffled    ");
18}
19
Full Screen
copy
1#include <algorithm>
2#include <ctime>
3#include <iostream>
4
5int main() {
6    int data[32768]; const int l = sizeof data / sizeof data[0];
7
8    for (unsigned c = 0; c < l; ++c)
9        data[c] = std::rand() % 256;
10
11    // sort 200-element segments, not the whole array
12    for (unsigned c = 0; c + 200 <= l; c += 200)
13        std::sort(&data[c], &data[c + 200]);
14
15    clock_t start = clock();
16    long long sum = 0;
17
18    for (unsigned i = 0; i < 100000; ++i) {
19        for (unsigned c = 0; c < sizeof data / sizeof(int); ++c) {
20            if (data[c] >= 128)
21                sum += data[c];
22        }
23    }
24
25    std::cout << static_cast<double>(clock() - start) / CLOCKS_PER_SEC << std::endl;
26    std::cout << "sum = " << sum << std::endl;
27}
28
Full Screen
copy
1% Processing time with Sorted data vs unsorted data
2%==========================================================================
3% Generate data
4arraySize = 32768
5sum = 0;
6% Generate random integer data from range 0 to 255
7data = randi(256, arraySize, 1);
8
9
10%Sort the data
11data1= sort(data); % data1= data  when no sorting done
12
13
14%Start a stopwatch timer to measure the execution time
15tic;
16
17for i=1:100000
18
19    for j=1:arraySize
20
21        if data1(j)>=128
22            sum=sum + data1(j);
23        end
24    end
25end
26
27toc;
28
29ExeTimeWithSorting = toc - tic;
30
Full Screen
copy
1  a: Elapsed time (without sorting) = 3479.880861 seconds.
2  b: Elapsed time (with sorting ) = 2377.873098 seconds.
3
Full Screen
copy
1  a: Elapsed time (without sorting) = 19.8761 sec.
2  b: Elapsed time (with sorting ) = 7.37778 sec.
3
Full Screen
copy
1____________________________________________________________________________________
2- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
3TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
4
Full Screen
copy
1___________________________________________ Straight road
2 |_________________________________________|Longer road
3
Full Screen
copy
1 // sort backwards (higher values first), may be in some other part of the code
2 std::sort(data, data + arraySize, std::greater<int>());
3
4 for (unsigned c = 0; c < arraySize; ++c) {
5       if (data[c] < 128) {
6              break;
7       }
8       sum += data[c];               
9 }
10
Full Screen
copy
1MOV R0, #0   // R0 = sum = 0
2MOV R1, #0   // R1 = c = 0
3ADR R2, data // R2 = addr of data array (put this instruction outside outer loop)
4.inner_loop  // Inner loop branch label
5    LDRB R3, [R2, R1]   // R3 = data[c]
6    CMP R3, #128        // compare R3 to 128
7    ADDGE R0, R0, R3    // if R3 >= 128, then sum += data[c] -- no branch needed!
8    ADD R1, R1, #1      // c++
9    CMP R1, #arraySize  // compare c to arraySize
10    BLT inner_loop      // Branch to inner_loop if c < arraySize
11
Full Screen
copy
1if (expression)
2{
3    // Run 1
4} else {
5    // Run 2
6}
7
Full Screen
copy
1 O      Route 1  /-------------------------------
2/|\             /
3 |  ---------##/
4/ \            \
5                \
6        Route 2  \--------------------------------
7
Full Screen
copy
1bool a, b, c, d;
2if (a != 0) {
3    if (b != 0) {
4        c = 1;
5    }
6    else {
7        goto CFALSE;
8    }
9}
10else {
11    CFALSE:
12    c = 0;
13}
14if (a == 0) {
15    if (b == 0) {
16        d = 0;
17    }
18    else {
19        goto DTRUE;
20    }
21}
22else {
23    DTRUE:
24    d = 1;
25}
26
Full Screen
copy
1char a = 0, b = 1, c, d;
2c = a & b;
3d = a | b;
4
Full Screen
copy
1bool a; double x, y, z;
2a = x > y && z < 5.0;
3
Full Screen
copy
1if (likely( everything_is_ok ))
2{
3    /* Do something */
4}
5
Full Screen
copy
1if (unlikely(very_improbable_condition))
2{
3    /* Do something */    
4}
5
Full Screen
copy
1                        A) if (data[c] >= 128)
2                                /\
3                               /  \
4                              /    \
5                        true /      \ false
6                            /        \
7                           /          \
8                          /            \
9                         /              \
10              B) sum += data[c];          C) for loop or print().
11
Full Screen
copy
1int i= 0, j, k= arraySize;
2while (i < k)
3{
4  j= (i + k) >> 1;
5  if (data[j] >= 128)
6    k= j;
7  else
8    i= j;
9}
10sum= 0;
11for (; i < arraySize; i++)
12  sum+= data[i];
13
Full Screen
copy
1int i, k, j= (i + k) >> 1;
2for (i= 0, k= arraySize; i < k; (data[j] >= 128 ? k : i)= j)
3  j= (i + k) >> 1;
4for (sum= 0; i < arraySize; i++)
5  sum+= data[i];
6
Full Screen
copy
1// Test
2clock_t start = clock();
3long long a[] = {0, 0};
4long long sum;
5
6for (unsigned i = 0; i < 100000; ++i)
7{
8    // Primary loop
9    for (unsigned c = 0; c < arraySize; ++c)
10    {
11        int j = (data[c] >> 7);
12        a[j] += data[c];
13    }
14}
15
16double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;
17sum = a[1];
18
Full Screen
copy
1// Declare and then fill in the lookup table
2int lut[256];
3for (unsigned c = 0; c < 256; ++c)
4    lut[c] = (c >= 128) ? c : 0;
5
6// Use the lookup table after it is built
7for (unsigned i = 0; i < 100000; ++i)
8{
9    // Primary loop
10    for (unsigned c = 0; c < arraySize; ++c)
11    {
12        sum += lut[data[c]];
13    }
14}
15
Full Screen
copy
1if (x < node->value)
2    node = node->pLeft;
3else
4    node = node->pRight;
5
Full Screen
copy
1i = (x < node->value);
2node = node->link[i];
3
Full Screen
copy
1for (int i = 0; i < max; i++)
2    if (condition)
3        sum++;
4
Full Screen
copy
1Condition                Pattern             Time (ms)
2-------------------------------------------------------
3(i & 0Ă—80000000) == 0    T repeated          322
4
5(i & 0xffffffff) == 0    F repeated          276
6
7(i & 1) == 0             TF alternating      760
8
9(i & 3) == 0             TFFFTFFF…           513
10
11(i & 2) == 0             TTFFTTFF…           1675
12
13(i & 4) == 0             TTTTFFFFTTTTFFFF…   1275
14
15(i & 8) == 0             8T 8F 8T 8F …       752
16
17(i & 16) == 0            16T 16F 16T 16F …   490
18
Full Screen
copy
1for (int i = 0; i < array.Length; ++i)
2{
3   // Use array[i]
4}
5
Full Screen
copy
1// Generate data
2int arraySize = 32768;
3int[] data = new int[arraySize];
4
5Random random = new Random(0);
6for (int c = 0; c < arraySize; ++c)
7{
8    data[c] = random.Next(256);
9}
10
11/*To keep the spirit of the code intact, I'll make a separate lookup table
12(I assume we cannot modify 'data' or the number of loops)*/
13
14int[] lookup = new int[256];
15
16for (int c = 0; c < 256; ++c)
17{
18    lookup[c] = (c >= 128) ? c : 0;
19}
20
21// Test
22DateTime startTime = System.DateTime.Now;
23long sum = 0;
24
25for (int i = 0; i < 100000; ++i)
26{
27    // Primary loop
28    for (int j = 0; j < arraySize; ++j)
29    {
30        /* Here you basically want to use simple operations - so no
31        random branches, but things like &, |, *, -, +, etc. are fine. */
32        sum += lookup[data[j]];
33    }
34}
35
36DateTime endTime = System.DateTime.Now;
37Console.WriteLine(endTime - startTime);
38Console.WriteLine("sum = " + sum);
39Console.ReadLine();
40
Full Screen
copy
1==32551== Branches:        656,645,130  (  656,609,208 cond +    35,922 ind)
2==32551== Mispredicts:         169,556  (      169,095 cond +       461 ind)
3==32551== Mispred rate:            0.0% (          0.0%     +       1.2%   )
4
Full Screen
copy
1==32555== Branches:        655,996,082  (  655,960,160 cond +  35,922 ind)
2==32555== Mispredicts:     164,073,152  (  164,072,692 cond +     460 ind)
3==32555== Mispred rate:           25.0% (         25.0%     +     1.2%   )
4
Full Screen
copy
1          Bc    Bcm Bi Bim
2      10,001      4  0   0      for (unsigned i = 0; i < 10000; ++i)
3           .      .  .   .      {
4           .      .  .   .          // primary loop
5 327,690,000 10,016  0   0          for (unsigned c = 0; c < arraySize; ++c)
6           .      .  .   .          {
7 327,680,000 10,006  0   0              if (data[c] >= 128)
8           0      0  0   0                  sum += data[c];
9           .      .  .   .          }
10           .      .  .   .      }
11
Full Screen
copy
1          Bc         Bcm Bi Bim
2      10,001           4  0   0      for (unsigned i = 0; i < 10000; ++i)
3           .           .  .   .      {
4           .           .  .   .          // primary loop
5 327,690,000      10,038  0   0          for (unsigned c = 0; c < arraySize; ++c)
6           .           .  .   .          {
7 327,680,000 164,050,007  0   0              if (data[c] >= 128)
8           0           0  0   0                  sum += data[c];
9           .           .  .   .          }
10           .           .  .   .      }
11
Full Screen
copy
1 Performance counter stats for './sumtest_sorted':
2
3  11808.095776 task-clock                #    0.998 CPUs utilized          
4         1,062 context-switches          #    0.090 K/sec                  
5            14 CPU-migrations            #    0.001 K/sec                  
6           337 page-faults               #    0.029 K/sec                  
726,487,882,764 cycles                    #    2.243 GHz                    
841,025,654,322 instructions              #    1.55  insns per cycle        
9 6,558,871,379 branches                  #  555.455 M/sec                  
10       567,204 branch-misses             #    0.01% of all branches        
11
12  11.827228330 seconds time elapsed
13
Full Screen
copy
1 Performance counter stats for './sumtest_unsorted':
2
3  28877.954344 task-clock                #    0.998 CPUs utilized          
4         2,584 context-switches          #    0.089 K/sec                  
5            18 CPU-migrations            #    0.001 K/sec                  
6           335 page-faults               #    0.012 K/sec                  
765,076,127,595 cycles                    #    2.253 GHz                    
841,032,528,741 instructions              #    0.63  insns per cycle        
9 6,560,579,013 branches                  #  227.183 M/sec                  
10 1,646,394,749 branch-misses             #   25.10% of all branches        
11
12  28.935500947 seconds time elapsed
13
Full Screen
copy
1perf record -e branch-misses ./sumtest_unsorted
2perf annotate -d sumtest_unsorted
3
Full Screen
copy
1 Percent |      Source code & Disassembly of sumtest_unsorted
2------------------------------------------------
3...
4         :                      sum += data[c];
5    0.00 :        400a1a:       mov    -0x14(%rbp),%eax
6   39.97 :        400a1d:       mov    %eax,%eax
7    5.31 :        400a1f:       mov    -0x20040(%rbp,%rax,4),%eax
8    4.60 :        400a26:       cltq   
9    0.00 :        400a28:       add    %rax,-0x30(%rbp)
10...
11
Full Screen
copy
1for (unsigned i = 0; i < 100000; ++i)
2{
3    for (unsigned j = 0; j < arraySize; ++j)
4    {
5        if (data[j] >= 128)
6            sum += data[j];
7    }
8}
9
Full Screen
copy
1for (unsigned j = 0; j < arraySize; ++j)
2{
3    for (unsigned i = 0; i < 100000; ++i)
4    {
5        if (data[j] >= 128)
6            sum += data[j];
7    }
8}
9
Full Screen
copy
1for (unsigned j = 0; j < arraySize; ++j)
2{
3    if (data[j] >= 128)
4    {
5        for (unsigned i = 0; i < 100000; ++i)
6        {
7            sum += data[j];
8        }
9    }
10}
11
Full Screen
copy
1for (unsigned j = 0; j < arraySize; ++j)
2{
3    if (data[j] >= 128)
4    {
5        sum += data[j] * 100000;
6    }
7}
8
Full Screen
copy
1int max1(int a, int b) {
2    if (a > b)
3        return a;
4    else
5        return b;
6}
7
Full Screen
copy
1int max2(int a, int b) {
2    return a > b ? a : b;
3}
4
Full Screen
copy
1:max1
2    movl    %edi, -4(%rbp)
3    movl    %esi, -8(%rbp)
4    movl    -4(%rbp), %eax
5    cmpl    -8(%rbp), %eax
6    jle     .L2
7    movl    -4(%rbp), %eax
8    movl    %eax, -12(%rbp)
9    jmp     .L4
10.L2:
11    movl    -8(%rbp), %eax
12    movl    %eax, -12(%rbp)
13.L4:
14    movl    -12(%rbp), %eax
15    leave
16    ret
17
18:max2
19    movl    %edi, -4(%rbp)
20    movl    %esi, -8(%rbp)
21    movl    -4(%rbp), %eax
22    cmpl    %eax, -8(%rbp)
23    cmovge  -8(%rbp), %eax
24    leave
25    ret
26
Full Screen
copy
1T = branch taken
2N = branch not taken
3
4data[] = 0, 1, 2, 3, 4, ... 126, 127, 128, 129, 130, ... 250, 251, 252, ...
5branch = N  N  N  N  N  ...   N    N    T    T    T  ...   T    T    T  ...
6
7       = NNNNNNNNNNNN ... NNNNNNNTTTTTTTTT ... TTTTTTTTTT  (easy to predict)
8
Full Screen
copy
1data[] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118,  14, 150, 177, 182, ...
2branch =   T,   T,   N,   T,   T,   T,   T,  N,   T,   N,   N,   T,   T,   T  ...
3
4       = TTNTTTTNTNNTTT ...   (completely random - impossible to predict)
5
Full Screen
copy
1int t = (data[c] - 128) >> 31;
2sum += ~t & data[c];
3
Full Screen