Run junit automation tests on LambdaTest cloud grid
Perform automation testing on 3000+ real desktop and mobile devices online.
package org.hamcrest;
@SuppressWarnings("UnusedDeclaration")
public class CoreMatchers {
/**
* Creates a matcher that matches if the examined object matches <b>ALL</b> of the specified matchers.
* For example:
* <pre>assertThat("myValue", allOf(startsWith("my"), containsString("Val")))</pre>
*/
public static <T> org.hamcrest.Matcher<T> allOf(java.lang.Iterable<org.hamcrest.Matcher<? super T>> matchers) {
return org.hamcrest.core.AllOf.<T>allOf(matchers);
}
/**
* Creates a matcher that matches if the examined object matches <b>ALL</b> of the specified matchers.
* For example:
* <pre>assertThat("myValue", allOf(startsWith("my"), containsString("Val")))</pre>
*/
@SafeVarargs
public static <T> org.hamcrest.Matcher<T> allOf(org.hamcrest.Matcher<? super T>... matchers) {
return org.hamcrest.core.AllOf.<T>allOf(matchers);
}
/**
* Creates a matcher that matches if the examined object matches <b>ANY</b> of the specified matchers.
* For example:
* <pre>assertThat("myValue", anyOf(startsWith("foo"), containsString("Val")))</pre>
*/
public static <T> org.hamcrest.core.AnyOf<T> anyOf(java.lang.Iterable<org.hamcrest.Matcher<? super T>> matchers) {
return org.hamcrest.core.AnyOf.<T>anyOf(matchers);
}
/**
* Creates a matcher that matches if the examined object matches <b>ANY</b> of the specified matchers.
* For example:
* <pre>assertThat("myValue", anyOf(startsWith("foo"), containsString("Val")))</pre>
*/
@SafeVarargs
public static <T> org.hamcrest.core.AnyOf<T> anyOf(org.hamcrest.Matcher<? super T>... matchers) {
return org.hamcrest.core.AnyOf.<T>anyOf(matchers);
}
/**
* Creates a matcher that matches when both of the specified matchers match the examined object.
* For example:
* <pre>assertThat("fab", both(containsString("a")).and(containsString("b")))</pre>
*/
public static <LHS> org.hamcrest.core.CombinableMatcher.CombinableBothMatcher<LHS> both(org.hamcrest.Matcher<? super LHS> matcher) {
return org.hamcrest.core.CombinableMatcher.both(matcher);
}
/**
* Creates a matcher that matches when either of the specified matchers match the examined object.
* For example:
* <pre>assertThat("fan", either(containsString("a")).or(containsString("b")))</pre>
*/
public static <LHS> org.hamcrest.core.CombinableMatcher.CombinableEitherMatcher<LHS> either(org.hamcrest.Matcher<? super LHS> matcher) {
return org.hamcrest.core.CombinableMatcher.either(matcher);
}
/**
* Wraps an existing matcher, overriding its description with that specified. All other functions are
* delegated to the decorated matcher, including its mismatch description.
* For example:
* <pre>describedAs("a big decimal equal to %0", equalTo(myBigDecimal), myBigDecimal.toPlainString())</pre>
*
* @param description
* the new description for the wrapped matcher
* @param matcher
* the matcher to wrap
* @param values
* optional values to insert into the tokenised description
*/
public static <T> org.hamcrest.Matcher<T> describedAs(java.lang.String description, org.hamcrest.Matcher<T> matcher, java.lang.Object... values) {
return org.hamcrest.core.DescribedAs.describedAs(description, matcher, values);
}
/**
* Creates a matcher for {@link Iterable}s that only matches when a single pass over the
* examined {@link Iterable} yields items that are all matched by the specified
* <code>itemMatcher</code>.
* For example:
* <pre>assertThat(Arrays.asList("bar", "baz"), everyItem(startsWith("ba")))</pre>
*
* @param itemMatcher
* the matcher to apply to every item provided by the examined {@link Iterable}
*/
public static <U> org.hamcrest.Matcher<java.lang.Iterable<? extends U>> everyItem(org.hamcrest.Matcher<U> itemMatcher) {
return org.hamcrest.core.Every.everyItem(itemMatcher);
}
/**
* Decorates another Matcher, retaining its behaviour, but allowing tests
* to be slightly more expressive.
* For example:
* <pre>assertThat(cheese, is(equalTo(smelly)))</pre>
* instead of:
* <pre>assertThat(cheese, equalTo(smelly))</pre>
*/
public static <T> org.hamcrest.Matcher<T> is(org.hamcrest.Matcher<T> matcher) {
return org.hamcrest.core.Is.is(matcher);
}
/**
* A shortcut to the frequently used <code>is(equalTo(x))</code>.
* For example:
* <pre>assertThat(cheese, is(smelly))</pre>
* instead of:
* <pre>assertThat(cheese, is(equalTo(smelly)))</pre>
*/
public static <T> org.hamcrest.Matcher<T> is(T value) {
return org.hamcrest.core.Is.is(value);
}
/**
* Provided to cause compile time error when used in preference to a possible runtime error if
* this was not here.
*
* <p>This method was removed upstream between Hamcrest 1.1 and 1.3 in favour of the
* instanceOf(Class) method. Unfortunately, existing usages of it could still compile against the
* {@link #is(Object)} method instead. Although not every existing usage would compile
* successfully it is possible that some could and that would result in a change in the runtime
* behavior that could be difficult to detect and fix. This change aims to turn any significant
* usage of this method into a compile time error.
*
* @deprecated Use instanceOf(SomeClass.class) instead.
*/
public static void is(java.lang.Class<?> type) {
}
/**
* A shortcut to the frequently used <code>is(instanceOf(SomeClass.class))</code>.
* For example:
* <pre>assertThat(cheese, isA(Cheddar.class))</pre>
* instead of:
* <pre>assertThat(cheese, is(instanceOf(Cheddar.class)))</pre>
*/
public static <T> org.hamcrest.Matcher<T> isA(java.lang.Class<T> type) {
return org.hamcrest.core.Is.isA(type);
}
/**
* Creates a matcher that always matches, regardless of the examined object.
*/
public static org.hamcrest.Matcher<java.lang.Object> anything() {
return org.hamcrest.core.IsAnything.anything();
}
/**
* Creates a matcher that always matches, regardless of the examined object, but describes
* itself with the specified {@link String}.
*
* @param description
* a meaningful {@link String} used when describing itself
*/
public static org.hamcrest.Matcher<java.lang.Object> anything(java.lang.String description) {
return org.hamcrest.core.IsAnything.anything(description);
}
/**
* Creates a matcher for {@link Iterable}s that only matches when a single pass over the
* examined {@link Iterable} yields at least one item that is matched by the specified
* <code>itemMatcher</code>. Whilst matching, the traversal of the examined {@link Iterable}
* will stop as soon as a matching item is found.
* For example:
* <pre>assertThat(Arrays.asList("foo", "bar"), hasItem(startsWith("ba")))</pre>
*
* @param itemMatcher
* the matcher to apply to items provided by the examined {@link Iterable}
*/
public static <T> org.hamcrest.Matcher<java.lang.Iterable<? super T>> hasItem(org.hamcrest.Matcher<? super T> itemMatcher) {
return org.hamcrest.core.IsCollectionContaining.<T>hasItem(itemMatcher);
}
/**
* Creates a matcher for {@link Iterable}s that only matches when a single pass over the
* examined {@link Iterable} yields at least one item that is equal to the specified
* <code>item</code>. Whilst matching, the traversal of the examined {@link Iterable}
* will stop as soon as a matching item is found.
* For example:
* <pre>assertThat(Arrays.asList("foo", "bar"), hasItem("bar"))</pre>
*
* @param item
* the item to compare against the items provided by the examined {@link Iterable}
*/
public static <T> org.hamcrest.Matcher<java.lang.Iterable<? super T>> hasItem(T item) {
return org.hamcrest.core.IsCollectionContaining.<T>hasItem(item);
}
/**
* Creates a matcher for {@link Iterable}s that matches when consecutive passes over the
* examined {@link Iterable} yield at least one item that is matched by the corresponding
* matcher from the specified <code>itemMatchers</code>. Whilst matching, each traversal of
* the examined {@link Iterable} will stop as soon as a matching item is found.
* For example:
* <pre>assertThat(Arrays.asList("foo", "bar", "baz"), hasItems(endsWith("z"), endsWith("o")))</pre>
*
* @param itemMatchers
* the matchers to apply to items provided by the examined {@link Iterable}
*/
@SafeVarargs
public static <T> org.hamcrest.Matcher<java.lang.Iterable<T>> hasItems(org.hamcrest.Matcher<? super T>... itemMatchers) {
return org.hamcrest.core.IsCollectionContaining.<T>hasItems(itemMatchers);
}
/**
* Creates a matcher for {@link Iterable}s that matches when consecutive passes over the
* examined {@link Iterable} yield at least one item that is equal to the corresponding
* item from the specified <code>items</code>. Whilst matching, each traversal of the
* examined {@link Iterable} will stop as soon as a matching item is found.
* For example:
* <pre>assertThat(Arrays.asList("foo", "bar", "baz"), hasItems("baz", "foo"))</pre>
*
* @param items
* the items to compare against the items provided by the examined {@link Iterable}
*/
@SafeVarargs
public static <T> org.hamcrest.Matcher<java.lang.Iterable<T>> hasItems(T... items) {
return org.hamcrest.core.IsCollectionContaining.<T>hasItems(items);
}
/**
* Creates a matcher that matches when the examined object is logically equal to the specified
* <code>operand</code>, as determined by calling the {@link java.lang.Object#equals} method on
* the <b>examined</b> object.
*
* <p>If the specified operand is <code>null</code> then the created matcher will only match if
* the examined object's <code>equals</code> method returns <code>true</code> when passed a
* <code>null</code> (which would be a violation of the <code>equals</code> contract), unless the
* examined object itself is <code>null</code>, in which case the matcher will return a positive
* match.</p>
*
* <p>The created matcher provides a special behaviour when examining <code>Array</code>s, whereby
* it will match if both the operand and the examined object are arrays of the same length and
* contain items that are equal to each other (according to the above rules) <b>in the same
* indexes</b>.</p>
* For example:
* <pre>
* assertThat("foo", equalTo("foo"));
* assertThat(new String[] {"foo", "bar"}, equalTo(new String[] {"foo", "bar"}));
* </pre>
*/
public static <T> org.hamcrest.Matcher<T> equalTo(T operand) {
return org.hamcrest.core.IsEqual.equalTo(operand);
}
/**
* Creates an {@link org.hamcrest.core.IsEqual} matcher that does not enforce the values being
* compared to be of the same static type.
*/
public static org.hamcrest.Matcher<java.lang.Object> equalToObject(java.lang.Object operand) {
return org.hamcrest.core.IsEqual.equalToObject(operand);
}
/**
* Creates a matcher that matches when the examined object is an instance of the specified <code>type</code>,
* as determined by calling the {@link java.lang.Class#isInstance(Object)} method on that type, passing the
* the examined object.
*
* <p>The created matcher forces a relationship between specified type and the examined object, and should be
* used when it is necessary to make generics conform, for example in the JMock clause
* <code>with(any(Thing.class))</code></p>
* For example:
* <pre>assertThat(new Canoe(), instanceOf(Canoe.class));</pre>
*/
public static <T> org.hamcrest.Matcher<T> any(java.lang.Class<T> type) {
return org.hamcrest.core.IsInstanceOf.any(type);
}
/**
* Creates a matcher that matches when the examined object is an instance of the specified <code>type</code>,
* as determined by calling the {@link java.lang.Class#isInstance(Object)} method on that type, passing the
* the examined object.
*
* <p>The created matcher assumes no relationship between specified type and the examined object.</p>
* For example:
* <pre>assertThat(new Canoe(), instanceOf(Paddlable.class));</pre>
*/
public static <T> org.hamcrest.Matcher<T> instanceOf(java.lang.Class<?> type) {
return org.hamcrest.core.IsInstanceOf.instanceOf(type);
}
/**
* Creates a matcher that wraps an existing matcher, but inverts the logic by which
* it will match.
* For example:
* <pre>assertThat(cheese, is(not(equalTo(smelly))))</pre>
*
* @param matcher
* the matcher whose sense should be inverted
*/
public static <T> org.hamcrest.Matcher<T> not(org.hamcrest.Matcher<T> matcher) {
return org.hamcrest.core.IsNot.not(matcher);
}
/**
* A shortcut to the frequently used <code>not(equalTo(x))</code>.
* For example:
* <pre>assertThat(cheese, is(not(smelly)))</pre>
* instead of:
* <pre>assertThat(cheese, is(not(equalTo(smelly))))</pre>
*
* @param value
* the value that any examined object should <b>not</b> equal
*/
public static <T> org.hamcrest.Matcher<T> not(T value) {
return org.hamcrest.core.IsNot.not(value);
}
/**
* A shortcut to the frequently used <code>not(nullValue())</code>.
* For example:
* <pre>assertThat(cheese, is(notNullValue()))</pre>
* instead of:
* <pre>assertThat(cheese, is(not(nullValue())))</pre>
*/
public static org.hamcrest.Matcher<java.lang.Object> notNullValue() {
return org.hamcrest.core.IsNull.notNullValue();
}
/**
* A shortcut to the frequently used <code>not(nullValue(X.class)). Accepts a
* single dummy argument to facilitate type inference.</code>.
* For example:
* <pre>assertThat(cheese, is(notNullValue(X.class)))</pre>
* instead of:
* <pre>assertThat(cheese, is(not(nullValue(X.class))))</pre>
*
* @param type
* dummy parameter used to infer the generic type of the returned matcher
*/
public static <T> org.hamcrest.Matcher<T> notNullValue(java.lang.Class<T> type) {
return org.hamcrest.core.IsNull.notNullValue(type);
}
/**
* Creates a matcher that matches if examined object is <code>null</code>.
* For example:
* <pre>assertThat(cheese, is(nullValue())</pre>
*/
public static org.hamcrest.Matcher<java.lang.Object> nullValue() {
return org.hamcrest.core.IsNull.nullValue();
}
/**
* Creates a matcher that matches if examined object is <code>null</code>. Accepts a
* single dummy argument to facilitate type inference.
* For example:
* <pre>assertThat(cheese, is(nullValue(Cheese.class))</pre>
*
* @param type
* dummy parameter used to infer the generic type of the returned matcher
*/
public static <T> org.hamcrest.Matcher<T> nullValue(java.lang.Class<T> type) {
return org.hamcrest.core.IsNull.nullValue(type);
}
/**
* Creates a matcher that matches only when the examined object is the same instance as
* the specified target object.
*
* @param target
* the target instance against which others should be assessed
*/
public static <T> org.hamcrest.Matcher<T> sameInstance(T target) {
return org.hamcrest.core.IsSame.sameInstance(target);
}
/**
* Creates a matcher that matches only when the examined object is the same instance as
* the specified target object.
*
* @param target
* the target instance against which others should be assessed
*/
public static <T> org.hamcrest.Matcher<T> theInstance(T target) {
return org.hamcrest.core.IsSame.theInstance(target);
}
/**
* Creates a matcher that matches if the examined {@link String} contains the specified
* {@link String} anywhere.
* For example:
* <pre>assertThat("myStringOfNote", containsString("ring"))</pre>
*
* @param substring
* the substring that the returned matcher will expect to find within any examined string
*/
public static org.hamcrest.Matcher<java.lang.String> containsString(java.lang.String substring) {
return org.hamcrest.core.StringContains.containsString(substring);
}
/**
* Creates a matcher that matches if the examined {@link String} contains the specified
* {@link String} anywhere, ignoring case.
* For example:
* <pre>assertThat("myStringOfNote", containsString("ring"))</pre>
*
* @param substring
* the substring that the returned matcher will expect to find within any examined string
*/
public static org.hamcrest.Matcher<java.lang.String> containsStringIgnoringCase(java.lang.String substring) {
return org.hamcrest.core.StringContains.containsStringIgnoringCase(substring);
}
/**
* <p>
* Creates a matcher that matches if the examined {@link String} starts with the specified
* {@link String}.
* </p>
* For example:
* <pre>assertThat("myStringOfNote", startsWith("my"))</pre>
*
* @param prefix
* the substring that the returned matcher will expect at the start of any examined string
*/
public static org.hamcrest.Matcher<java.lang.String> startsWith(java.lang.String prefix) {
return org.hamcrest.core.StringStartsWith.startsWith(prefix);
}
/**
* <p>
* Creates a matcher that matches if the examined {@link String} starts with the specified
* {@link String}, ignoring case
* </p>
* For example:
* <pre>assertThat("myStringOfNote", startsWith("my"))</pre>
*
* @param prefix
* the substring that the returned matcher will expect at the start of any examined string
*/
public static org.hamcrest.Matcher<java.lang.String> startsWithIgnoringCase(java.lang.String prefix) {
return org.hamcrest.core.StringStartsWith.startsWithIgnoringCase(prefix);
}
/**
* Creates a matcher that matches if the examined {@link String} ends with the specified
* {@link String}.
* For example:
* <pre>assertThat("myStringOfNote", endsWith("Note"))</pre>
*
* @param suffix
* the substring that the returned matcher will expect at the end of any examined string
*/
public static org.hamcrest.Matcher<java.lang.String> endsWith(java.lang.String suffix) {
return org.hamcrest.core.StringEndsWith.endsWith(suffix);
}
/**
* Creates a matcher that matches if the examined {@link String} ends with the specified
* {@link String}, ignoring case.
* For example:
* <pre>assertThat("myStringOfNote", endsWith("Note"))</pre>
*
* @param suffix
* the substring that the returned matcher will expect at the end of any examined string
*/
public static org.hamcrest.Matcher<java.lang.String> endsWithIgnoringCase(java.lang.String suffix) {
return org.hamcrest.core.StringEndsWith.endsWithIgnoringCase(suffix);
}
}
// CPP program to demonstrate processing
// time of sorted and unsorted array
#include <iostream>
#include <algorithm>
#include <ctime>
using namespace std;
const int N = 100001;
int main()
{
int arr[N];
// Assign random values to array
for (int i=0; i<N; i++)
arr[i] = rand()%N;
// for loop for unsorted array
int count = 0;
double start = clock();
for (int i=0; i<N; i++)
if (arr[i] < N/2)
count++;
double end = clock();
cout << "Time for unsorted array :: "
<< ((end - start)/CLOCKS_PER_SEC)
<< endl;
sort(arr, arr+N);
// for loop for sorted array
count = 0;
start = clock();
for (int i=0; i<N; i++)
if (arr[i] < N/2)
count++;
end = clock();
cout << "Time for sorted array :: "
<< ((end - start)/CLOCKS_PER_SEC)
<< endl;
return 0;
}
Already sorted 32995 milliseconds
Shuffled 125944 milliseconds
Already sorted 18610 milliseconds
Shuffled 133304 milliseconds
Already sorted 17942 milliseconds
Shuffled 107858 milliseconds
void run(vector<int>& v, const string& label)
{
auto t0 = system_clock::now();
sort(v.begin(), v.end());
auto t1 = system_clock::now();
cout << label
<< duration_cast<microseconds>(t1 — t0).count()
<< " milliseconds\n";
}
void tst()
{
vector<int> v(1'000'000);
iota(v.begin(), v.end(), 0);
run(v, "already sorted ");
std::shuffle(v.begin(), v.end(), std::mt19937{ std::random_device{}() });
run(v, "shuffled ");
}
#include <algorithm>
#include <ctime>
#include <iostream>
int main() {
int data[32768]; const int l = sizeof data / sizeof data[0];
for (unsigned c = 0; c < l; ++c)
data[c] = std::rand() % 256;
// sort 200-element segments, not the whole array
for (unsigned c = 0; c + 200 <= l; c += 200)
std::sort(&data[c], &data[c + 200]);
clock_t start = clock();
long long sum = 0;
for (unsigned i = 0; i < 100000; ++i) {
for (unsigned c = 0; c < sizeof data / sizeof(int); ++c) {
if (data[c] >= 128)
sum += data[c];
}
}
std::cout << static_cast<double>(clock() - start) / CLOCKS_PER_SEC << std::endl;
std::cout << "sum = " << sum << std::endl;
}
% Processing time with Sorted data vs unsorted data
%==========================================================================
% Generate data
arraySize = 32768
sum = 0;
% Generate random integer data from range 0 to 255
data = randi(256, arraySize, 1);
%Sort the data
data1= sort(data); % data1= data when no sorting done
%Start a stopwatch timer to measure the execution time
tic;
for i=1:100000
for j=1:arraySize
if data1(j)>=128
sum=sum + data1(j);
end
end
end
toc;
ExeTimeWithSorting = toc - tic;
a: Elapsed time (without sorting) = 3479.880861 seconds.
b: Elapsed time (with sorting ) = 2377.873098 seconds.
a: Elapsed time (without sorting) = 19.8761 sec.
b: Elapsed time (with sorting ) = 7.37778 sec.
____________________________________________________________________________________
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
___________________________________________ Straight road
|_________________________________________|Longer road
// sort backwards (higher values first), may be in some other part of the code
std::sort(data, data + arraySize, std::greater<int>());
for (unsigned c = 0; c < arraySize; ++c) {
if (data[c] < 128) {
break;
}
sum += data[c];
}
MOV R0, #0 // R0 = sum = 0
MOV R1, #0 // R1 = c = 0
ADR R2, data // R2 = addr of data array (put this instruction outside outer loop)
.inner_loop // Inner loop branch label
LDRB R3, [R2, R1] // R3 = data[c]
CMP R3, #128 // compare R3 to 128
ADDGE R0, R0, R3 // if R3 >= 128, then sum += data[c] -- no branch needed!
ADD R1, R1, #1 // c++
CMP R1, #arraySize // compare c to arraySize
BLT inner_loop // Branch to inner_loop if c < arraySize
if (expression)
{
// Run 1
} else {
// Run 2
}
O Route 1 /-------------------------------
/|\ /
| ---------##/
/ \ \
\
Route 2 \--------------------------------
bool a, b, c, d;
c = a && b;
d = a || b;
bool a, b, c, d;
if (a != 0) {
if (b != 0) {
c = 1;
}
else {
goto CFALSE;
}
}
else {
CFALSE:
c = 0;
}
if (a == 0) {
if (b == 0) {
d = 0;
}
else {
goto DTRUE;
}
}
else {
DTRUE:
d = 1;
}
char a = 0, b = 1, c, d;
c = a & b;
d = a | b;
char a = 0, b;
b = a ^ 1;
bool a; double x, y, z;
a = x > y && z < 5.0;
if (likely( everything_is_ok ))
{
/* Do something */
}
if (unlikely(very_improbable_condition))
{
/* Do something */
}
data[c] = std::rand() % 256;
A) if (data[c] >= 128)
/\
/ \
/ \
true / \ false
/ \
/ \
/ \
/ \
B) sum += data[c]; C) for loop or print().
int i= 0, j, k= arraySize;
while (i < k)
{
j= (i + k) >> 1;
if (data[j] >= 128)
k= j;
else
i= j;
}
sum= 0;
for (; i < arraySize; i++)
sum+= data[i];
int i, k, j= (i + k) >> 1;
for (i= 0, k= arraySize; i < k; (data[j] >= 128 ? k : i)= j)
j= (i + k) >> 1;
for (sum= 0; i < arraySize; i++)
sum+= data[i];
// Test
clock_t start = clock();
long long a[] = {0, 0};
long long sum;
for (unsigned i = 0; i < 100000; ++i)
{
// Primary loop
for (unsigned c = 0; c < arraySize; ++c)
{
int j = (data[c] >> 7);
a[j] += data[c];
}
}
double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;
sum = a[1];
// Declare and then fill in the lookup table
int lut[256];
for (unsigned c = 0; c < 256; ++c)
lut[c] = (c >= 128) ? c : 0;
// Use the lookup table after it is built
for (unsigned i = 0; i < 100000; ++i)
{
// Primary loop
for (unsigned c = 0; c < arraySize; ++c)
{
sum += lut[data[c]];
}
}
if (x < node->value)
node = node->pLeft;
else
node = node->pRight;
i = (x < node->value);
node = node->link[i];
if (data[c] >= 128)
sum += data[c];
for (int i = 0; i < max; i++)
if (condition)
sum++;
Condition Pattern Time (ms)
-------------------------------------------------------
(i & 0×80000000) == 0 T repeated 322
(i & 0xffffffff) == 0 F repeated 276
(i & 1) == 0 TF alternating 760
(i & 3) == 0 TFFFTFFF… 513
(i & 2) == 0 TTFFTTFF… 1675
(i & 4) == 0 TTTTFFFFTTTTFFFF… 1275
(i & 8) == 0 8T 8F 8T 8F … 752
(i & 16) == 0 16T 16F 16T 16F … 490
for (int i = 0; i < array.Length; ++i)
{
// Use array[i]
}
// Generate data
int arraySize = 32768;
int[] data = new int[arraySize];
Random random = new Random(0);
for (int c = 0; c < arraySize; ++c)
{
data[c] = random.Next(256);
}
/*To keep the spirit of the code intact, I'll make a separate lookup table
(I assume we cannot modify 'data' or the number of loops)*/
int[] lookup = new int[256];
for (int c = 0; c < 256; ++c)
{
lookup[c] = (c >= 128) ? c : 0;
}
// Test
DateTime startTime = System.DateTime.Now;
long sum = 0;
for (int i = 0; i < 100000; ++i)
{
// Primary loop
for (int j = 0; j < arraySize; ++j)
{
/* Here you basically want to use simple operations - so no
random branches, but things like &, |, *, -, +, etc. are fine. */
sum += lookup[data[j]];
}
}
DateTime endTime = System.DateTime.Now;
Console.WriteLine(endTime - startTime);
Console.WriteLine("sum = " + sum);
Console.ReadLine();
==32551== Branches: 656,645,130 ( 656,609,208 cond + 35,922 ind)
==32551== Mispredicts: 169,556 ( 169,095 cond + 461 ind)
==32551== Mispred rate: 0.0% ( 0.0% + 1.2% )
==32555== Branches: 655,996,082 ( 655,960,160 cond + 35,922 ind)
==32555== Mispredicts: 164,073,152 ( 164,072,692 cond + 460 ind)
==32555== Mispred rate: 25.0% ( 25.0% + 1.2% )
Bc Bcm Bi Bim
10,001 4 0 0 for (unsigned i = 0; i < 10000; ++i)
. . . . {
. . . . // primary loop
327,690,000 10,016 0 0 for (unsigned c = 0; c < arraySize; ++c)
. . . . {
327,680,000 10,006 0 0 if (data[c] >= 128)
0 0 0 0 sum += data[c];
. . . . }
. . . . }
Bc Bcm Bi Bim
10,001 4 0 0 for (unsigned i = 0; i < 10000; ++i)
. . . . {
. . . . // primary loop
327,690,000 10,038 0 0 for (unsigned c = 0; c < arraySize; ++c)
. . . . {
327,680,000 164,050,007 0 0 if (data[c] >= 128)
0 0 0 0 sum += data[c];
. . . . }
. . . . }
perf stat ./sumtest_sorted
Performance counter stats for './sumtest_sorted':
11808.095776 task-clock # 0.998 CPUs utilized
1,062 context-switches # 0.090 K/sec
14 CPU-migrations # 0.001 K/sec
337 page-faults # 0.029 K/sec
26,487,882,764 cycles # 2.243 GHz
41,025,654,322 instructions # 1.55 insns per cycle
6,558,871,379 branches # 555.455 M/sec
567,204 branch-misses # 0.01% of all branches
11.827228330 seconds time elapsed
Performance counter stats for './sumtest_unsorted':
28877.954344 task-clock # 0.998 CPUs utilized
2,584 context-switches # 0.089 K/sec
18 CPU-migrations # 0.001 K/sec
335 page-faults # 0.012 K/sec
65,076,127,595 cycles # 2.253 GHz
41,032,528,741 instructions # 0.63 insns per cycle
6,560,579,013 branches # 227.183 M/sec
1,646,394,749 branch-misses # 25.10% of all branches
28.935500947 seconds time elapsed
perf record -e branch-misses ./sumtest_unsorted
perf annotate -d sumtest_unsorted
Percent | Source code & Disassembly of sumtest_unsorted
------------------------------------------------
...
: sum += data[c];
0.00 : 400a1a: mov -0x14(%rbp),%eax
39.97 : 400a1d: mov %eax,%eax
5.31 : 400a1f: mov -0x20040(%rbp,%rax,4),%eax
4.60 : 400a26: cltq
0.00 : 400a28: add %rax,-0x30(%rbp)
...
for (unsigned i = 0; i < 100000; ++i)
{
for (unsigned j = 0; j < arraySize; ++j)
{
if (data[j] >= 128)
sum += data[j];
}
}
for (unsigned j = 0; j < arraySize; ++j)
{
for (unsigned i = 0; i < 100000; ++i)
{
if (data[j] >= 128)
sum += data[j];
}
}
for (unsigned j = 0; j < arraySize; ++j)
{
if (data[j] >= 128)
{
for (unsigned i = 0; i < 100000; ++i)
{
sum += data[j];
}
}
}
for (unsigned j = 0; j < arraySize; ++j)
{
if (data[j] >= 128)
{
sum += data[j] * 100000;
}
}
if (data[c] >= 128)
sum += data[c];
sum += data[c] >=128 ? data[c] : 0;
int max1(int a, int b) {
if (a > b)
return a;
else
return b;
}
int max2(int a, int b) {
return a > b ? a : b;
}
:max1
movl %edi, -4(%rbp)
movl %esi, -8(%rbp)
movl -4(%rbp), %eax
cmpl -8(%rbp), %eax
jle .L2
movl -4(%rbp), %eax
movl %eax, -12(%rbp)
jmp .L4
.L2:
movl -8(%rbp), %eax
movl %eax, -12(%rbp)
.L4:
movl -12(%rbp), %eax
leave
ret
:max2
movl %edi, -4(%rbp)
movl %esi, -8(%rbp)
movl -4(%rbp), %eax
cmpl %eax, -8(%rbp)
cmovge -8(%rbp), %eax
leave
ret
if (data[c] >= 128)
sum += data[c];
T = branch taken
N = branch not taken
data[] = 0, 1, 2, 3, 4, ... 126, 127, 128, 129, 130, ... 250, 251, 252, ...
branch = N N N N N ... N N T T T ... T T T ...
= NNNNNNNNNNNN ... NNNNNNNTTTTTTTTT ... TTTTTTTTTT (easy to predict)
data[] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118, 14, 150, 177, 182, ...
branch = T, T, N, T, T, T, T, N, T, N, N, T, T, T ...
= TTNTTTTNTNNTTT ... (completely random - impossible to predict)
if (data[c] >= 128)
sum += data[c];
int t = (data[c] - 128) >> 31;
sum += ~t & data[c];
// CPP program to demonstrate processing
// time of sorted and unsorted array
#include <iostream>
#include <algorithm>
#include <ctime>
using namespace std;
const int N = 100001;
int main()
{
int arr[N];
// Assign random values to array
for (int i=0; i<N; i++)
arr[i] = rand()%N;
// for loop for unsorted array
int count = 0;
double start = clock();
for (int i=0; i<N; i++)
if (arr[i] < N/2)
count++;
double end = clock();
cout << "Time for unsorted array :: "
<< ((end - start)/CLOCKS_PER_SEC)
<< endl;
sort(arr, arr+N);
// for loop for sorted array
count = 0;
start = clock();
for (int i=0; i<N; i++)
if (arr[i] < N/2)
count++;
end = clock();
cout << "Time for sorted array :: "
<< ((end - start)/CLOCKS_PER_SEC)
<< endl;
return 0;
}
Already sorted 32995 milliseconds
Shuffled 125944 milliseconds
Already sorted 18610 milliseconds
Shuffled 133304 milliseconds
Already sorted 17942 milliseconds
Shuffled 107858 milliseconds
void run(vector<int>& v, const string& label)
{
auto t0 = system_clock::now();
sort(v.begin(), v.end());
auto t1 = system_clock::now();
cout << label
<< duration_cast<microseconds>(t1 — t0).count()
<< " milliseconds\n";
}
void tst()
{
vector<int> v(1'000'000);
iota(v.begin(), v.end(), 0);
run(v, "already sorted ");
std::shuffle(v.begin(), v.end(), std::mt19937{ std::random_device{}() });
run(v, "shuffled ");
}
#include <algorithm>
#include <ctime>
#include <iostream>
int main() {
int data[32768]; const int l = sizeof data / sizeof data[0];
for (unsigned c = 0; c < l; ++c)
data[c] = std::rand() % 256;
// sort 200-element segments, not the whole array
for (unsigned c = 0; c + 200 <= l; c += 200)
std::sort(&data[c], &data[c + 200]);
clock_t start = clock();
long long sum = 0;
for (unsigned i = 0; i < 100000; ++i) {
for (unsigned c = 0; c < sizeof data / sizeof(int); ++c) {
if (data[c] >= 128)
sum += data[c];
}
}
std::cout << static_cast<double>(clock() - start) / CLOCKS_PER_SEC << std::endl;
std::cout << "sum = " << sum << std::endl;
}
% Processing time with Sorted data vs unsorted data
%==========================================================================
% Generate data
arraySize = 32768
sum = 0;
% Generate random integer data from range 0 to 255
data = randi(256, arraySize, 1);
%Sort the data
data1= sort(data); % data1= data when no sorting done
%Start a stopwatch timer to measure the execution time
tic;
for i=1:100000
for j=1:arraySize
if data1(j)>=128
sum=sum + data1(j);
end
end
end
toc;
ExeTimeWithSorting = toc - tic;
a: Elapsed time (without sorting) = 3479.880861 seconds.
b: Elapsed time (with sorting ) = 2377.873098 seconds.
a: Elapsed time (without sorting) = 19.8761 sec.
b: Elapsed time (with sorting ) = 7.37778 sec.
____________________________________________________________________________________
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
___________________________________________ Straight road
|_________________________________________|Longer road
// sort backwards (higher values first), may be in some other part of the code
std::sort(data, data + arraySize, std::greater<int>());
for (unsigned c = 0; c < arraySize; ++c) {
if (data[c] < 128) {
break;
}
sum += data[c];
}
MOV R0, #0 // R0 = sum = 0
MOV R1, #0 // R1 = c = 0
ADR R2, data // R2 = addr of data array (put this instruction outside outer loop)
.inner_loop // Inner loop branch label
LDRB R3, [R2, R1] // R3 = data[c]
CMP R3, #128 // compare R3 to 128
ADDGE R0, R0, R3 // if R3 >= 128, then sum += data[c] -- no branch needed!
ADD R1, R1, #1 // c++
CMP R1, #arraySize // compare c to arraySize
BLT inner_loop // Branch to inner_loop if c < arraySize
if (expression)
{
// Run 1
} else {
// Run 2
}
O Route 1 /-------------------------------
/|\ /
| ---------##/
/ \ \
\
Route 2 \--------------------------------
bool a, b, c, d;
c = a && b;
d = a || b;
bool a, b, c, d;
if (a != 0) {
if (b != 0) {
c = 1;
}
else {
goto CFALSE;
}
}
else {
CFALSE:
c = 0;
}
if (a == 0) {
if (b == 0) {
d = 0;
}
else {
goto DTRUE;
}
}
else {
DTRUE:
d = 1;
}
char a = 0, b = 1, c, d;
c = a & b;
d = a | b;
char a = 0, b;
b = a ^ 1;
bool a; double x, y, z;
a = x > y && z < 5.0;
if (likely( everything_is_ok ))
{
/* Do something */
}
if (unlikely(very_improbable_condition))
{
/* Do something */
}
data[c] = std::rand() % 256;
A) if (data[c] >= 128)
/\
/ \
/ \
true / \ false
/ \
/ \
/ \
/ \
B) sum += data[c]; C) for loop or print().
int i= 0, j, k= arraySize;
while (i < k)
{
j= (i + k) >> 1;
if (data[j] >= 128)
k= j;
else
i= j;
}
sum= 0;
for (; i < arraySize; i++)
sum+= data[i];
int i, k, j= (i + k) >> 1;
for (i= 0, k= arraySize; i < k; (data[j] >= 128 ? k : i)= j)
j= (i + k) >> 1;
for (sum= 0; i < arraySize; i++)
sum+= data[i];
// Test
clock_t start = clock();
long long a[] = {0, 0};
long long sum;
for (unsigned i = 0; i < 100000; ++i)
{
// Primary loop
for (unsigned c = 0; c < arraySize; ++c)
{
int j = (data[c] >> 7);
a[j] += data[c];
}
}
double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;
sum = a[1];
// Declare and then fill in the lookup table
int lut[256];
for (unsigned c = 0; c < 256; ++c)
lut[c] = (c >= 128) ? c : 0;
// Use the lookup table after it is built
for (unsigned i = 0; i < 100000; ++i)
{
// Primary loop
for (unsigned c = 0; c < arraySize; ++c)
{
sum += lut[data[c]];
}
}
if (x < node->value)
node = node->pLeft;
else
node = node->pRight;
i = (x < node->value);
node = node->link[i];
if (data[c] >= 128)
sum += data[c];
for (int i = 0; i < max; i++)
if (condition)
sum++;
Condition Pattern Time (ms)
-------------------------------------------------------
(i & 0×80000000) == 0 T repeated 322
(i & 0xffffffff) == 0 F repeated 276
(i & 1) == 0 TF alternating 760
(i & 3) == 0 TFFFTFFF… 513
(i & 2) == 0 TTFFTTFF… 1675
(i & 4) == 0 TTTTFFFFTTTTFFFF… 1275
(i & 8) == 0 8T 8F 8T 8F … 752
(i & 16) == 0 16T 16F 16T 16F … 490
for (int i = 0; i < array.Length; ++i)
{
// Use array[i]
}
// Generate data
int arraySize = 32768;
int[] data = new int[arraySize];
Random random = new Random(0);
for (int c = 0; c < arraySize; ++c)
{
data[c] = random.Next(256);
}
/*To keep the spirit of the code intact, I'll make a separate lookup table
(I assume we cannot modify 'data' or the number of loops)*/
int[] lookup = new int[256];
for (int c = 0; c < 256; ++c)
{
lookup[c] = (c >= 128) ? c : 0;
}
// Test
DateTime startTime = System.DateTime.Now;
long sum = 0;
for (int i = 0; i < 100000; ++i)
{
// Primary loop
for (int j = 0; j < arraySize; ++j)
{
/* Here you basically want to use simple operations - so no
random branches, but things like &, |, *, -, +, etc. are fine. */
sum += lookup[data[j]];
}
}
DateTime endTime = System.DateTime.Now;
Console.WriteLine(endTime - startTime);
Console.WriteLine("sum = " + sum);
Console.ReadLine();
==32551== Branches: 656,645,130 ( 656,609,208 cond + 35,922 ind)
==32551== Mispredicts: 169,556 ( 169,095 cond + 461 ind)
==32551== Mispred rate: 0.0% ( 0.0% + 1.2% )
==32555== Branches: 655,996,082 ( 655,960,160 cond + 35,922 ind)
==32555== Mispredicts: 164,073,152 ( 164,072,692 cond + 460 ind)
==32555== Mispred rate: 25.0% ( 25.0% + 1.2% )
Bc Bcm Bi Bim
10,001 4 0 0 for (unsigned i = 0; i < 10000; ++i)
. . . . {
. . . . // primary loop
327,690,000 10,016 0 0 for (unsigned c = 0; c < arraySize; ++c)
. . . . {
327,680,000 10,006 0 0 if (data[c] >= 128)
0 0 0 0 sum += data[c];
. . . . }
. . . . }
Bc Bcm Bi Bim
10,001 4 0 0 for (unsigned i = 0; i < 10000; ++i)
. . . . {
. . . . // primary loop
327,690,000 10,038 0 0 for (unsigned c = 0; c < arraySize; ++c)
. . . . {
327,680,000 164,050,007 0 0 if (data[c] >= 128)
0 0 0 0 sum += data[c];
. . . . }
. . . . }
perf stat ./sumtest_sorted
Performance counter stats for './sumtest_sorted':
11808.095776 task-clock # 0.998 CPUs utilized
1,062 context-switches # 0.090 K/sec
14 CPU-migrations # 0.001 K/sec
337 page-faults # 0.029 K/sec
26,487,882,764 cycles # 2.243 GHz
41,025,654,322 instructions # 1.55 insns per cycle
6,558,871,379 branches # 555.455 M/sec
567,204 branch-misses # 0.01% of all branches
11.827228330 seconds time elapsed
Performance counter stats for './sumtest_unsorted':
28877.954344 task-clock # 0.998 CPUs utilized
2,584 context-switches # 0.089 K/sec
18 CPU-migrations # 0.001 K/sec
335 page-faults # 0.012 K/sec
65,076,127,595 cycles # 2.253 GHz
41,032,528,741 instructions # 0.63 insns per cycle
6,560,579,013 branches # 227.183 M/sec
1,646,394,749 branch-misses # 25.10% of all branches
28.935500947 seconds time elapsed
perf record -e branch-misses ./sumtest_unsorted
perf annotate -d sumtest_unsorted
Percent | Source code & Disassembly of sumtest_unsorted
------------------------------------------------
...
: sum += data[c];
0.00 : 400a1a: mov -0x14(%rbp),%eax
39.97 : 400a1d: mov %eax,%eax
5.31 : 400a1f: mov -0x20040(%rbp,%rax,4),%eax
4.60 : 400a26: cltq
0.00 : 400a28: add %rax,-0x30(%rbp)
...
for (unsigned i = 0; i < 100000; ++i)
{
for (unsigned j = 0; j < arraySize; ++j)
{
if (data[j] >= 128)
sum += data[j];
}
}
for (unsigned j = 0; j < arraySize; ++j)
{
for (unsigned i = 0; i < 100000; ++i)
{
if (data[j] >= 128)
sum += data[j];
}
}
for (unsigned j = 0; j < arraySize; ++j)
{
if (data[j] >= 128)
{
for (unsigned i = 0; i < 100000; ++i)
{
sum += data[j];
}
}
}
for (unsigned j = 0; j < arraySize; ++j)
{
if (data[j] >= 128)
{
sum += data[j] * 100000;
}
}
if (data[c] >= 128)
sum += data[c];
sum += data[c] >=128 ? data[c] : 0;
int max1(int a, int b) {
if (a > b)
return a;
else
return b;
}
int max2(int a, int b) {
return a > b ? a : b;
}
:max1
movl %edi, -4(%rbp)
movl %esi, -8(%rbp)
movl -4(%rbp), %eax
cmpl -8(%rbp), %eax
jle .L2
movl -4(%rbp), %eax
movl %eax, -12(%rbp)
jmp .L4
.L2:
movl -8(%rbp), %eax
movl %eax, -12(%rbp)
.L4:
movl -12(%rbp), %eax
leave
ret
:max2
movl %edi, -4(%rbp)
movl %esi, -8(%rbp)
movl -4(%rbp), %eax
cmpl %eax, -8(%rbp)
cmovge -8(%rbp), %eax
leave
ret
if (data[c] >= 128)
sum += data[c];
T = branch taken
N = branch not taken
data[] = 0, 1, 2, 3, 4, ... 126, 127, 128, 129, 130, ... 250, 251, 252, ...
branch = N N N N N ... N N T T T ... T T T ...
= NNNNNNNNNNNN ... NNNNNNNTTTTTTTTT ... TTTTTTTTTT (easy to predict)
data[] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118, 14, 150, 177, 182, ...
branch = T, T, N, T, T, T, T, N, T, N, N, T, T, T ...
= TTNTTTTNTNNTTT ... (completely random - impossible to predict)
if (data[c] >= 128)
sum += data[c];
int t = (data[c] - 128) >> 31;
sum += ~t & data[c];
