Additional conditional statement speeds up program execution

Question

After reading Why is a sorted array processed faster than an unsorted array? , I added another test in the primary loop. This additional test seems to speed up program execution.

int main() { // Generate data const unsigned arraySize = 32768; int data[arraySize]; for (unsigned c = 0; c < arraySize; ++c) data[c] = std::rand() % 256; //Don't sort the array //std::sort(data, data + arraySize); // Test clock_t start = clock(); long long sum = 0; for (unsigned i = 0; i < 100000; ++i) { // Primary loop for (unsigned c = 0; c < arraySize; ++c) { if (data[c] >= 128) sum += data[c]; //With this additional test, execution becomes faster if (data[c] < 128) sum += data[c]; } } double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC; std::cout << elapsedTime << std::endl; std::cout << "sum = " << sum << std::endl; } 

I get about 4.2 seconds with an extra test and 18 seconds without an extra test. Should an extra test make the program slower rather than speed it up?

Answer 1

Because of this particular additional test, the equivalent code for this is:

 for (unsigned i = 0; i < 100000; ++i) { // Primary loop for (unsigned c = 0; c < arraySize; ++c) { if (data[c] >= 128) sum += data[c]; //With this additional test, execution becomes faster if (data[c] < 128) sum += data[c]; } } 

becomes the following:

 for (unsigned i = 0; i < 100000; ++i) { // Primary loop for (unsigned c = 0; c < arraySize; ++c) { sum += data[c];//because exactly one condition is guaranteed to be //true in each iteration (in your code)! //the equivalent is as if there is no condition at all! } } 

therefore it becomes faster.

Due to the unusual additional test and identical body, the compiler is able to optimize the code by removing the if conditions. When you have one if , the compiler cannot do this.

Try writing this:

 sum -= data[c]; //the body is not identical anymore! 

in one of the conditions if . I am sure that the compiler will not be able to optimize the code. Now it should publish a slower machine code.

---

Please note that the outer loop can be completely eliminated, although it does not depend heavily on the additional test:

 // Primary loop for (unsigned c = 0; c < arraySize; ++c) { sum += 100000 * data[c]; } 

or that:

 // Primary loop for (unsigned c = 0; c < arraySize; ++c) { sum += data[c]; } sum = 100000 * sum; //multiple once!