An additional conditional statement is making a program faster

Question

After reading the Why is it faster to process a sorted array than an unsorted array?, I added one additional test in the primary loop. It seems that this additional test is making the program faster.

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.2sec with the additional test and 18 sec without the additional test. Shouldn't the additional test make the program slower instead of making it faster?

Nawaz · Answer 1 · 2012-12-01T21:09:52.913

7

Because of that particular additional test, the equivalent code of this:

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 this:

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!
  }
}

which is why it becomes faster.

It is because of the unusual additional test and the identical body, the compiler is able to optimize the code, removing the if conditions. When you've one if, then the compiler cannot do that.

Try writing this:

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

in one of the if condition. I'm sure the compiler will not be able to optimize the code. It should emit slower machine code now.

Note that the outer loop can be omitted entirely, though it doesn't much depend on the additional test::

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

or, this:

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

edited Dec 01 '12 at 21:09

answered Dec 01 '12 at 20:32

Nawaz

353,942
115
666
851

Worth noting it's compiler optimization due to the changed context. Normally, this wouldn't have happened and the additional condition would slow the execution. – SomeWittyUsername Dec 01 '12 at 20:34
1

The outer loop is there just to measure the run time, I would say – Tengis Dec 01 '12 at 20:42
@icepack, what do you mean "normally". Isn't compiler optimization normal? – Dec 01 '12 at 20:53
2

@Sancho Compiler optimization is normal. But this particular optimization is unusual because it's rare in practice and the compiler would need to recognize that both tests are exact compliments and that the body is identical. – Mysticial Dec 01 '12 at 21:03
1

@Sancho, yes it's normal but usually you won't have a code with 2 conditions instead of having none. – SomeWittyUsername Dec 01 '12 at 21:03
Just tried this with MSVS2012 and it seems like VC11 can't optimize this. – kiwon Dec 03 '12 at 21:46
@Nawaz, in release with full optimization – kiwon Dec 04 '12 at 15:40
@kiwon: Alright. The optimizations are up to the compilers after all. – Nawaz Dec 04 '12 at 15:49

An additional conditional statement is making a program faster

1 Answers1